Преобразование 0x1234 в 0x11223344

Ответ 1

Это можно сделать, используя SSE2 следующим образом:

void ExpandSSE2(unsigned __int64 in, unsigned __int64 &outLo, unsigned __int64 &outHi) {
  __m128i const mask = _mm_set1_epi16((short)0xF00F);
  __m128i const mul0 = _mm_set1_epi16(0x0011);
  __m128i const mul1 = _mm_set1_epi16(0x1000);
  __m128i       v;

  v = _mm_cvtsi64_si128(in); // Move the 64-bit value to a 128-bit register
  v = _mm_unpacklo_epi8(v, v);  // 0x12   -> 0x1212
  v = _mm_and_si128(v, mask);   // 0x1212 -> 0x1002
  v = _mm_mullo_epi16(v, mul0); // 0x1002 -> 0x1022
  v = _mm_mulhi_epu16(v, mul1); // 0x1022 -> 0x0102
  v = _mm_mullo_epi16(v, mul0); // 0x0102 -> 0x1122

  outLo = _mm_extract_epi64(v, 0);
  outHi = _mm_extract_epi64(v, 1);
}

Конечно, вы хотите поместить кишки функции во внутренний цикл и вытащить константы. Вы также захотите пропустить регистры x64 и загрузить значения непосредственно в 128-разрядные регистры SSE. Пример того, как это сделать, см. В реализации SSE2 в тесте производительности ниже.

По своей сути, существует пять инструкций, которые выполняют операцию по четырем цветовым значениям за раз. Таким образом, это всего лишь 1,25 инструкций для каждого значения цвета. Следует также отметить, что SSE2 доступен в любом месте x64.

Тесты производительности для ассортимента решений здесь Несколько человек отметили, что единственный способ узнать, что быстрее, чтобы запустить код, и это неоспоримо верно. Поэтому я собрал несколько решений в тест производительности, чтобы мы могли сравнивать яблоки с яблоками. Я выбрал решения, которые, как я чувствовал, значительно отличались от других, чтобы требовать тестирования. Все решения, считываемые из памяти, работают с данными и записываются в память. На практике некоторые из решений SSE потребуют дополнительной осторожности в отношении выравнивания и обработки случаев, когда во входных данных не обрабатываются еще полные 16 байтов. Код, который я тестировал, является x64, скомпилированным под освобождением, используя Visual Studio 2013, работающий на частоте 4 х ГГц ядро ​​ . i7

Вот мои результаты:

ExpandOrig:               56.234 seconds  // From asker original question
ExpandSmallLUT:           30.209 seconds  // From Dmitry answer
ExpandLookupSmallOneLUT:  33.689 seconds  // from Dmitry answer
ExpandLookupLarge:        51.312 seconds  // A straightforward lookup table
ExpandAShelly:            43.829 seconds  // From AShelly answer
ExpandAShellyMulOp:       43.580 seconds  // AShelly answer with an optimization
ExpandSSE4:               17.854 seconds  // My original SSE4 answer
ExpandSSE4Unroll:         17.405 seconds  // My original SSE4 answer with loop unrolling
ExpandSSE2:               17.281 seconds  // My current SSE2 answer
ExpandSSE2Unroll:         17.152 seconds  // My current SSE2 answer with loop unrolling

В результатах теста выше вы увидите, что я включил код акита, три реализации таблицы поиска, включая реализацию небольшой таблицы поиска, предложенную в ответ Дмитрия. Также включено решение AShelly, а также версия с оптимизацией, которую я сделал (операцию можно устранить). Я включил мою первоначальную реализацию SSE4, а также более совершенную версию SSE2, которую я сделал позже (теперь это отражено в качестве ответа), а также развернутые версии обоих, поскольку они были самыми быстрыми здесь, и я хотел посмотреть, сколько разворачивает их ускорение, Я также включил SSE4 реализацию ответа AShelly.

До сих пор я должен объявить себя победителем. Но источник ниже, поэтому каждый может протестировать его на своей платформе и включить свое собственное решение в тестирование, чтобы убедиться, что они сделали решение еще быстрее.

#define DATA_SIZE_IN  ((unsigned)(1024 * 1024 * 128))
#define DATA_SIZE_OUT ((unsigned)(2 * DATA_SIZE_IN))
#define RERUN_COUNT   500

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <utility>
#include <emmintrin.h> // SSE2
#include <tmmintrin.h> // SSSE3
#include <smmintrin.h> // SSE4

void ExpandOrig(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  unsigned u, v;
  do {
    // Read in data
    u  = *(unsigned const*)in;
    v  = u >> 16;
    u &= 0x0000FFFF;

    // Do computation
    u  =   (u & 0x00FF) << 4
         | (u & 0x000F)
         | (u & 0x0FF0) << 8
         | (u & 0xFF00) << 12
         | (u & 0xF000) << 16;
    v  =   (v & 0x00FF) << 4
         | (v & 0x000F)
         | (v & 0x0FF0) << 8
         | (v & 0xFF00) << 12
         | (v & 0xF000) << 16;

    // Store data
    *(unsigned*)(out)      = u;
    *(unsigned*)(out + 4)  = v;
    in                    += 4;
    out                   += 8;
  } while (in != past);
}

unsigned LutLo[256],
         LutHi[256];
void MakeLutLo(void) {
  for (unsigned i = 0, x; i < 256; ++i) {
    x        = i;
    x        = ((x & 0xF0) << 4) | (x & 0x0F);
    x       |= (x << 4);
    LutLo[i] = x;
  }
}
void MakeLutHi(void) {
  for (unsigned i = 0, x; i < 256; ++i) {
    x        = i;
    x        = ((x & 0xF0) << 20) | ((x & 0x0F) << 16);
    x       |= (x << 4);
    LutHi[i] = x;
  }
}

void ExpandLookupSmall(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  unsigned u, v;
  do {
    // Read in data
    u  = *(unsigned const*)in;
    v  = u >> 16;
    u &= 0x0000FFFF;

    // Do computation
    u = LutHi[u >> 8] | LutLo[u & 0xFF];
    v = LutHi[v >> 8] | LutLo[v & 0xFF];

    // Store data
    *(unsigned*)(out)      = u;
    *(unsigned*)(out + 4)  = v;
    in                    += 4;
    out                   += 8;
  } while (in != past);
}

void ExpandLookupSmallOneLUT(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  unsigned u, v;
  do {
    // Read in data
    u = *(unsigned const*)in;
    v = u >> 16;
    u &= 0x0000FFFF;

    // Do computation
    u = ((LutLo[u >> 8] << 16) | LutLo[u & 0xFF]);
    v = ((LutLo[v >> 8] << 16) | LutLo[v & 0xFF]);

    // Store data
    *(unsigned*)(out) = u;
    *(unsigned*)(out + 4) = v;
    in  += 4;
    out += 8;
  } while (in != past);
}

unsigned LutLarge[256 * 256];
void MakeLutLarge(void) {
  for (unsigned i = 0; i < (256 * 256); ++i)
    LutLarge[i] = LutHi[i >> 8] | LutLo[i & 0xFF];
}

void ExpandLookupLarge(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  unsigned u, v;
  do {
    // Read in data
    u  = *(unsigned const*)in;
    v  = u >> 16;
    u &= 0x0000FFFF;

    // Do computation
    u = LutLarge[u];
    v = LutLarge[v];

    // Store data
    *(unsigned*)(out)      = u;
    *(unsigned*)(out + 4)  = v;
    in                    += 4;
    out                   += 8;
  } while (in != past);
}

void ExpandAShelly(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  unsigned u, v, w, x;
  do {
    // Read in data
    u  = *(unsigned const*)in;
    v  = u >> 16;
    u &= 0x0000FFFF;

    // Do computation
    w  = (((u & 0xF0F) * 0x101) & 0xF000F) + (((u & 0xF0F0) * 0x1010) & 0xF000F00);
    x  = (((v & 0xF0F) * 0x101) & 0xF000F) + (((v & 0xF0F0) * 0x1010) & 0xF000F00);
    w += w * 0x10;
    x += x * 0x10;

    // Store data
    *(unsigned*)(out)      = w;
    *(unsigned*)(out + 4)  = x;
    in                    += 4;
    out                   += 8;
  } while (in != past);
}

void ExpandAShellyMulOp(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  unsigned u, v;
  do {
    // Read in data
    u = *(unsigned const*)in;
    v = u >> 16;
    u &= 0x0000FFFF;

    // Do computation
    u = ((((u & 0xF0F) * 0x101) & 0xF000F) + (((u & 0xF0F0) * 0x1010) & 0xF000F00)) * 0x11;
    v = ((((v & 0xF0F) * 0x101) & 0xF000F) + (((v & 0xF0F0) * 0x1010) & 0xF000F00)) * 0x11;

    // Store data
    *(unsigned*)(out) = u;
    *(unsigned*)(out + 4) = v;
    in += 4;
    out += 8;
  } while (in != past);
}

void ExpandSSE4(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  __m128i const mask0 = _mm_set1_epi16((short)0x8000),
                mask1 = _mm_set1_epi8(0x0F),
                mul = _mm_set1_epi16(0x0011);
  __m128i       u, v, w, x;
  do {
    // Read input into low 8 bytes of u and v
    u = _mm_load_si128((__m128i const*)in);

    v = _mm_unpackhi_epi8(u, u);      // Expand each single byte to two bytes
    u = _mm_unpacklo_epi8(u, u);      // Do it again for v
    w = _mm_srli_epi16(u, 4);         // Copy the value into w and shift it right half a byte
    x = _mm_srli_epi16(v, 4);         // Do it again for v
    u = _mm_blendv_epi8(u, w, mask0); // Select odd bytes from w, and even bytes from v, giving the the desired value in the upper nibble of each byte
    v = _mm_blendv_epi8(v, x, mask0); // Do it again for v
    u = _mm_and_si128(u, mask1);      // Clear the all the upper nibbles
    v = _mm_and_si128(v, mask1);      // Do it again for v
    u = _mm_mullo_epi16(u, mul);      // Multiply each 16-bit value by 0x0011 to duplicate the lower nibble in the upper nibble of each byte
    v = _mm_mullo_epi16(v, mul);      // Do it again for v

    // Write output
    _mm_store_si128((__m128i*)(out     ), u);
    _mm_store_si128((__m128i*)(out + 16), v);
    in  += 16;
    out += 32;
  } while (in != past);
}

void ExpandSSE4Unroll(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  __m128i const mask0  = _mm_set1_epi16((short)0x8000),
                mask1  = _mm_set1_epi8(0x0F),
                mul    = _mm_set1_epi16(0x0011);
  __m128i       u0, v0, w0, x0,
                u1, v1, w1, x1,
                u2, v2, w2, x2,
                u3, v3, w3, x3;
  do {
    // Read input into low 8 bytes of u and v
    u0 = _mm_load_si128((__m128i const*)(in     ));
    u1 = _mm_load_si128((__m128i const*)(in + 16));
    u2 = _mm_load_si128((__m128i const*)(in + 32));
    u3 = _mm_load_si128((__m128i const*)(in + 48));

    v0 = _mm_unpackhi_epi8(u0, u0);      // Expand each single byte to two bytes
    u0 = _mm_unpacklo_epi8(u0, u0);      // Do it again for v
    v1 = _mm_unpackhi_epi8(u1, u1);      // Do it again
    u1 = _mm_unpacklo_epi8(u1, u1);      // Again for u1
    v2 = _mm_unpackhi_epi8(u2, u2);      // Again for v1
    u2 = _mm_unpacklo_epi8(u2, u2);      // Again for u2
    v3 = _mm_unpackhi_epi8(u3, u3);      // Again for v2
    u3 = _mm_unpacklo_epi8(u3, u3);      // Again for u3
    w0 = _mm_srli_epi16(u0, 4);          // Copy the value into w and shift it right half a byte
    x0 = _mm_srli_epi16(v0, 4);          // Do it again for v
    w1 = _mm_srli_epi16(u1, 4);          // Again for u1
    x1 = _mm_srli_epi16(v1, 4);          // Again for v1
    w2 = _mm_srli_epi16(u2, 4);          // Again for u2
    x2 = _mm_srli_epi16(v2, 4);          // Again for v2
    w3 = _mm_srli_epi16(u3, 4);          // Again for u3
    x3 = _mm_srli_epi16(v3, 4);          // Again for v3
    u0 = _mm_blendv_epi8(u0, w0, mask0); // Select even bytes from w, and odd bytes from v, giving the the desired value in the upper nibble of each byte
    v0 = _mm_blendv_epi8(v0, x0, mask0); // Do it again for v
    u1 = _mm_blendv_epi8(u1, w1, mask0); // Again for u1
    v1 = _mm_blendv_epi8(v1, x1, mask0); // Again for v1
    u2 = _mm_blendv_epi8(u2, w2, mask0); // Again for u2
    v2 = _mm_blendv_epi8(v2, x2, mask0); // Again for v2
    u3 = _mm_blendv_epi8(u3, w3, mask0); // Again for u3
    v3 = _mm_blendv_epi8(v3, x3, mask0); // Again for v3
    u0 = _mm_and_si128(u0, mask1);       // Clear the all the upper nibbles
    v0 = _mm_and_si128(v0, mask1);       // Do it again for v
    u1 = _mm_and_si128(u1, mask1);       // Again for u1
    v1 = _mm_and_si128(v1, mask1);       // Again for v1
    u2 = _mm_and_si128(u2, mask1);       // Again for u2
    v2 = _mm_and_si128(v2, mask1);       // Again for v2
    u3 = _mm_and_si128(u3, mask1);       // Again for u3
    v3 = _mm_and_si128(v3, mask1);       // Again for v3
    u0 = _mm_mullo_epi16(u0, mul);       // Multiply each 16-bit value by 0x0011 to duplicate the lower nibble in the upper nibble of each byte
    v0 = _mm_mullo_epi16(v0, mul);       // Do it again for v
    u1 = _mm_mullo_epi16(u1, mul);       // Again for u1
    v1 = _mm_mullo_epi16(v1, mul);       // Again for v1
    u2 = _mm_mullo_epi16(u2, mul);       // Again for u2
    v2 = _mm_mullo_epi16(v2, mul);       // Again for v2
    u3 = _mm_mullo_epi16(u3, mul);       // Again for u3
    v3 = _mm_mullo_epi16(v3, mul);       // Again for v3

    // Write output
    _mm_store_si128((__m128i*)(out      ), u0);
    _mm_store_si128((__m128i*)(out +  16), v0);
    _mm_store_si128((__m128i*)(out +  32), u1);
    _mm_store_si128((__m128i*)(out +  48), v1);
    _mm_store_si128((__m128i*)(out +  64), u2);
    _mm_store_si128((__m128i*)(out +  80), v2);
    _mm_store_si128((__m128i*)(out +  96), u3);
    _mm_store_si128((__m128i*)(out + 112), v3);
    in  += 64;
    out += 128;
  } while (in != past);
}

void ExpandSSE2(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  __m128i const mask = _mm_set1_epi16((short)0xF00F),
                mul0 = _mm_set1_epi16(0x0011),
                mul1 = _mm_set1_epi16(0x1000);
  __m128i       u, v;
  do {
    // Read input into low 8 bytes of u and v
    u = _mm_load_si128((__m128i const*)in);

    v = _mm_unpackhi_epi8(u, u);      // Expand each single byte to two bytes
    u = _mm_unpacklo_epi8(u, u);      // Do it again for v

    u = _mm_and_si128(u, mask);
    v = _mm_and_si128(v, mask);
    u = _mm_mullo_epi16(u, mul0);
    v = _mm_mullo_epi16(v, mul0);
    u = _mm_mulhi_epu16(u, mul1);     // This can also be done with a right shift of 4 bits, but this seems to mesure faster
    v = _mm_mulhi_epu16(v, mul1);
    u = _mm_mullo_epi16(u, mul0);
    v = _mm_mullo_epi16(v, mul0);

    // write output
    _mm_store_si128((__m128i*)(out     ), u);
    _mm_store_si128((__m128i*)(out + 16), v);
    in  += 16;
    out += 32;
  } while (in != past);
}

void ExpandSSE2Unroll(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  __m128i const mask = _mm_set1_epi16((short)0xF00F),
                mul0 = _mm_set1_epi16(0x0011),
                mul1 = _mm_set1_epi16(0x1000);
  __m128i       u0, v0,
                u1, v1;
  do {
    // Read input into low 8 bytes of u and v
    u0 = _mm_load_si128((__m128i const*)(in     ));
    u1 = _mm_load_si128((__m128i const*)(in + 16));

    v0 = _mm_unpackhi_epi8(u0, u0);      // Expand each single byte to two bytes
    u0 = _mm_unpacklo_epi8(u0, u0);      // Do it again for v
    v1 = _mm_unpackhi_epi8(u1, u1);      // Do it again
    u1 = _mm_unpacklo_epi8(u1, u1);      // Again for u1

    u0 = _mm_and_si128(u0, mask);
    v0 = _mm_and_si128(v0, mask);
    u1 = _mm_and_si128(u1, mask);
    v1 = _mm_and_si128(v1, mask);

    u0 = _mm_mullo_epi16(u0, mul0);
    v0 = _mm_mullo_epi16(v0, mul0);
    u1 = _mm_mullo_epi16(u1, mul0);
    v1 = _mm_mullo_epi16(v1, mul0);

    u0 = _mm_mulhi_epu16(u0, mul1);
    v0 = _mm_mulhi_epu16(v0, mul1);
    u1 = _mm_mulhi_epu16(u1, mul1);
    v1 = _mm_mulhi_epu16(v1, mul1);

    u0 = _mm_mullo_epi16(u0, mul0);
    v0 = _mm_mullo_epi16(v0, mul0);
    u1 = _mm_mullo_epi16(u1, mul0);
    v1 = _mm_mullo_epi16(v1, mul0);

    // write output
    _mm_store_si128((__m128i*)(out     ), u0);
    _mm_store_si128((__m128i*)(out + 16), v0);
    _mm_store_si128((__m128i*)(out + 32), u1);
    _mm_store_si128((__m128i*)(out + 48), v1);

    in  += 32;
    out += 64;
  } while (in != past);
}

void ExpandAShellySSE4(unsigned char const *in, unsigned char const *past, unsigned char *out) {
  __m128i const zero      = _mm_setzero_si128(),
                v0F0F     = _mm_set1_epi32(0x0F0F),
                vF0F0     = _mm_set1_epi32(0xF0F0),
                v0101     = _mm_set1_epi32(0x0101),
                v1010     = _mm_set1_epi32(0x1010),
                v000F000F = _mm_set1_epi32(0x000F000F),
                v0F000F00 = _mm_set1_epi32(0x0F000F00),
                v0011 = _mm_set1_epi32(0x0011);
  __m128i       u, v, w, x;
  do {
    // Read in data
    u = _mm_load_si128((__m128i const*)in);
    v = _mm_unpackhi_epi16(u, zero);
    u = _mm_unpacklo_epi16(u, zero);

    // original source: ((((a & 0xF0F) * 0x101) & 0xF000F) + (((a & 0xF0F0) * 0x1010) & 0xF000F00)) * 0x11;
    w = _mm_and_si128(u, v0F0F);
    x = _mm_and_si128(v, v0F0F);
    u = _mm_and_si128(u, vF0F0);
    v = _mm_and_si128(v, vF0F0);
    w = _mm_mullo_epi32(w, v0101); // _mm_mullo_epi32 is what makes this require SSE4 instead of SSE2
    x = _mm_mullo_epi32(x, v0101);
    u = _mm_mullo_epi32(u, v1010);
    v = _mm_mullo_epi32(v, v1010);
    w = _mm_and_si128(w, v000F000F);
    x = _mm_and_si128(x, v000F000F);
    u = _mm_and_si128(u, v0F000F00);
    v = _mm_and_si128(v, v0F000F00);
    u = _mm_add_epi32(u, w);
    v = _mm_add_epi32(v, x);
    u = _mm_mullo_epi32(u, v0011);
    v = _mm_mullo_epi32(v, v0011);

    // write output
    _mm_store_si128((__m128i*)(out     ), u);
    _mm_store_si128((__m128i*)(out + 16), v);
    in  += 16;
    out += 32;
  } while (in != past);
}

int main() {
  unsigned char *const indat   = new unsigned char[DATA_SIZE_IN ],
                *const outdat0 = new unsigned char[DATA_SIZE_OUT],
                *const outdat1 = new unsigned char[DATA_SIZE_OUT],
                *      curout  = outdat0,
                *      lastout = outdat1,
                *      place;
  unsigned             start,
                       stop;

  place = indat + DATA_SIZE_IN - 1;
  do {
    *place = (unsigned char)rand();
  } while (place-- != indat);
  MakeLutLo();
  MakeLutHi();
  MakeLutLarge();

  for (unsigned testcount = 0; testcount < 1000; ++testcount) {
    // Solution posted by the asker
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandOrig(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandOrig:\t\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);

    // Dmitry small lookup table solution
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandLookupSmall(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandSmallLUT:\t\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // Dmitry small lookup table solution using only one lookup table
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandLookupSmallOneLUT(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandLookupSmallOneLUT:\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // Large lookup table solution
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandLookupLarge(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandLookupLarge:\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // AShelly Interleave bits by Binary Magic Numbers solution
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandAShelly(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandAShelly:\t\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // AShelly Interleave bits by Binary Magic Numbers solution optimizing out an addition
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandAShellyMulOp(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandAShellyMulOp:\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // My SSE4 solution
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandSSE4(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandSSE4:\t\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // My SSE4 solution unrolled
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandSSE4Unroll(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandSSE4Unroll:\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // My SSE2 solution
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandSSE2(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandSSE2:\t\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // My SSE2 solution unrolled
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandSSE2Unroll(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandSSE2Unroll:\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;

    // AShelly Interleave bits by Binary Magic Numbers solution implemented using SSE2
    start = clock();
    for (unsigned rerun = 0; rerun < RERUN_COUNT; ++rerun)
      ExpandAShellySSE4(indat, indat + DATA_SIZE_IN, curout);
    stop = clock();
    std::cout << "ExpandAShellySSE4:\t\t" << (((stop - start) / 1000) / 60) << ':' << (((stop - start) / 1000) % 60) << ":." << ((stop - start) % 1000) << std::endl;

    std::swap(curout, lastout);
    if (memcmp(outdat0, outdat1, DATA_SIZE_OUT))
      std::cout << "INCORRECT OUTPUT" << std::endl;
  }

  delete[] indat;
  delete[] outdat0;
  delete[] outdat1;
  return 0;
}

Примечание:

У меня сначала была реализация SSE4. Я нашел способ реализовать это с помощью SSE2, что лучше, потому что он будет работать на других платформах. Реализация SSE2 также выполняется быстрее. Итак, решение, представленное сверху, теперь является реализацией SSE2, а не SSE4. Реализация SSE4 все еще можно увидеть в тестах производительности или в истории изменений.

Ответ 2

Я не уверен, какой был бы самый эффективный способ, но это немного короче:

#include <stdio.h>

int main()
{
  unsigned x = 0x1234;

  x = (x << 8) | x;
  x = ((x & 0x00f000f0) << 4) | (x & 0x000f000f);
  x = (x << 4) | x;

  printf("0x1234 -> 0x%08x\n",x);

  return 0;
}

Если вам нужно сделать это многократно и очень быстро, как было предложено в вашем редактировании, вы могли бы рассмотреть возможность создания таблицы поиска и использования этого. Следующая функция динамически выделяет и инициализирует такую ​​таблицу:

unsigned *makeLookupTable(void)
{
  unsigned *tbl = malloc(sizeof(unsigned) * 65536);
  if (!tbl) return NULL;
  int i;
  for (i = 0; i < 65536; i++) {
    unsigned x = i;
    x |= (x << 8);
    x = ((x & 0x00f000f0) << 4) | (x & 0x000f000f);
    x |= (x << 4);

    /* Uncomment next line to invert the high byte as mentioned in the edit. */
    /* x = x ^ 0xff000000; */

    tbl[i] = x;
  }
  return tbl;
}

После этого каждое преобразование - это что-то вроде:

result = lookuptable[input];

.. или возможно:

result = lookuptable[input & 0xffff];

Или меньшая, более удобная для кэша таблица поиска (или пара) может использоваться с одним поиском каждого для байтов с высоким и низким (как отмечено в комментариях @LưuVĩnhPhúc). В этом случае код генерации таблицы может быть:

unsigned *makeLookupTableLow(void)
{
  unsigned *tbl = malloc(sizeof(unsigned) * 256);
  if (!tbl) return NULL;
  int i;
  for (i = 0; i < 256; i++) {
    unsigned x = i;
    x = ((x & 0xf0) << 4) | (x & 0x0f);
    x |= (x << 4);
    tbl[i] = x;
  }
  return tbl;
}

... и необязательную вторую таблицу:

unsigned *makeLookupTableHigh(void)
{
  unsigned *tbl = malloc(sizeof(unsigned) * 256);
  if (!tbl) return NULL;
  int i;
  for (i = 0; i < 256; i++) {
    unsigned x = i;
    x = ((x & 0xf0) << 20) | ((x & 0x0f) << 16);
    x |= (x << 4);

    /* uncomment next line to invert high byte */
    /* x = x ^ 0xff000000; */

    tbl[i] = x;
  }
  return tbl;
}

... и преобразовать значение в две таблицы:

result = hightable[input >> 8] | lowtable[input & 0xff];

... или с одним (только нижняя таблица выше):

result = (lowtable[input >> 8] << 16) | lowtable[input & 0xff];
result ^= 0xff000000; /* to invert high byte */

Если верхняя часть значения (alpha?) не сильно изменится, даже одна большая таблица может хорошо работать, так как последовательные поиски будут ближе друг к другу в таблице.

Я отправил код теста производительности @Apriori, внеся некоторые корректировки и добавил тесты для других ответов, которые он не включил первоначально... затем скомпилировал три версии с разными настройками. Один из них - это 64-разрядный код с включенным SSE4.1, где компилятор может использовать SSE для оптимизации... а затем две 32-разрядные версии, один с SSE и один без. Хотя все три были запущены на одном и том же довольно недавнем процессоре, результаты показывают, как оптимальное решение может меняться в зависимости от особенностей процессора:

                           64b SSE4.1  32b SSE4.1  32b no SSE
-------------------------- ----------  ----------  ----------
ExpandOrig           time:  3.502 s     3.501 s     6.260 s
ExpandLookupSmall    time:  3.530 s     3.997 s     3.996 s
ExpandLookupLarge    time:  3.434 s     3.419 s     3.427 s
ExpandIsalamon       time:  3.654 s     3.673 s     8.870 s
ExpandIsalamonOpt    time:  3.784 s     3.720 s     8.719 s
ExpandChronoKitsune  time:  3.658 s     3.463 s     6.546 s
ExpandEvgenyKluev    time:  6.790 s     7.697 s    13.383 s
ExpandIammilind      time:  3.485 s     3.498 s     6.436 s
ExpandDmitri         time:  3.457 s     3.477 s     5.461 s
ExpandNitish712      time:  3.574 s     3.800 s     6.789 s
ExpandAdamLiss       time:  3.673 s     5.680 s     6.969 s
ExpandAShelly        time:  3.524 s     4.295 s     5.867 s
ExpandAShellyMulOp   time:  3.527 s     4.295 s     5.852 s
ExpandSSE4           time:  3.428 s
ExpandSSE4Unroll     time:  3.333 s
ExpandSSE2           time:  3.392 s
ExpandSSE2Unroll     time:  3.318 s
ExpandAShellySSE4    time:  3.392 s

Исполняемые файлы были скомпилированы в 64-разрядном Linux с помощью gcc 4.8.1, используя -m64 -O3 -march=core2 -msse4.1, -m32 -O3 -march=core2 -msse4.1 и -m32 -O3 -march=core2 -mno-sse соответственно. Тесты @Apriori SSE были опущены для 32-битных сборок (разбился на 32-битный с включенным SSE и, очевидно, не будет работать с отключенным SSE).

Среди сделанных корректировок использовались фактические данные изображения вместо случайных значений (фотографии объектов с прозрачным фоном), что значительно улучшило производительность большой таблицы поиска, но мало что изменило для остальных.

По сути, поисковые таблицы выигрывают от оползня, когда SSE недоступен (или не используется)... и решения с ручным кодированием SSE выигрывают иначе. Тем не менее, также следует отметить, что, когда компилятор мог использовать SSE для оптимизации, большинство решений для обработки бит были почти такими же быстрыми, как и SSE с ручным кодированием, все еще медленнее, но только незначительно.

Ответ 3

Здесь другая попытка, использующая восемь операций:

b = (((c & 0x0F0F) * 0x0101) & 0x00F000F) + 
    (((c & 0xF0F0) * 0x1010) & 0xF000F00);
b += b * 0x10;

printf("%x\n",b); //Shows '0x11223344'

* Обратите внимание, что этот пост первоначально содержал совершенно другой код, основанный на чередовать биты по двоичным номерам магов на странице Binacks от Sean Anderson. Но это не совсем то, о чем спрашивал ОП. поэтому он удален. Большинство комментариев ниже относятся к отсутствующей версии.

Ответ 4

Я хотел бы добавить эту ссылку в пул ответов, потому что я думаю, что это чрезвычайно важно, когда речь идет об оптимизации, о том, чтобы вспомнить аппаратное обеспечение, на котором мы работаем, а также технологии, составляющие наш код для указанной платформы.

Сообщение в блоге Игра с конвейером CPU - это поиск оптимизатора кода для конвейерной обработки CPU. Это на самом деле показывает пример того, где он пытается упростить математику вплоть до наименьших фактических математических операций, но она была FAR с самого оптимального решения с точки зрения времени. Я видел пару ответов здесь, говорящих об этом, и они могут быть правильными, они могут и не быть. Единственный способ узнать - фактически измерить время от начала до конца вашего конкретного фрагмента кода по сравнению с другими. Прочтите этот блог; это ЧРЕЗВЫЧАЙНО интересно.

Я думаю, что я должен упомянуть, что я в этом конкретном случае не собираюсь вводить ЛЮБОЙ код здесь, если я действительно не попробовал несколько попыток и на самом деле получил это, особенно быстрее, через несколько попыток.

Ответ 5

Я думаю, что подход таблицы поиска, предложенный Dimitri, является хорошим выбором, но я предлагаю сделать еще один шаг и сгенерировать таблицу во время компиляции; выполнение работы во время компиляции, очевидно, уменьшит время выполнения.

Сначала мы создаем значение времени компиляции, используя любой из предложенных методов:

constexpr unsigned int transform1(unsigned int x)
{
  return ((x << 8) | x);
}

constexpr unsigned int transform2(unsigned int x)
{
  return (((x & 0x00f000f0) << 4) | (x & 0x000f000f));
}

constexpr unsigned int transform3(unsigned int x)
{
  return ((x << 4) | x);
}

constexpr unsigned int transform(unsigned int x)
{
  return transform3(transform2(transform1(x)));
}

// Dimitri version, using constexprs
template <unsigned int argb> struct aarrggbb_dimitri
{
  static const unsigned int value = transform(argb);
};

// Adam Liss version
template <unsigned int argb> struct aarrggbb_adamLiss
{
  static const unsigned int value =
    (argb & 0xf000) * 0x11000 +
    (argb & 0x0f00) * 0x01100 +
    (argb & 0x00f0) * 0x00110 +
    (argb & 0x000f) * 0x00011;
};

И затем мы создаем таблицу поиска времени компиляции любым доступным методом, я хочу использовать целочисленную последовательность С++ 14 , но я не знаю, какой компилятор будет использовать OP. Таким образом, еще один возможный подход - использовать довольно уродливый макрос:

#define EXPAND16(x) aarrggbb<x + 0>::value, \
aarrggbb<x + 1>::value, \
aarrggbb<x + 2>::value, \
aarrggbb<x + 3>::value, \
aarrggbb<x + 4>::value, \
aarrggbb<x + 5>::value, \
aarrggbb<x + 6>::value, \
... and so on

#define EXPAND EXPAND16(0), \
EXPAND16(0x10), \
EXPAND16(0x20), \
EXPAND16(0x30), \
EXPAND16(0x40), \
... and so on

... and so on

Смотрите демо здесь.

PS: Адам Лисс мог бы использоваться без С++ 11.

Ответ 6

Если умножение дешево и доступно 64-битная арифметика, вы можете использовать этот код:

uint64_t x = 0x1234;
x *= 0x0001000100010001ull;
x &= 0xF0000F0000F0000Full;
x *= 0x0000001001001001ull;
x &= 0xF0F0F0F000000000ull;
x = (x >> 36) * 0x11;
std::cout << std::hex << x << '\n';

Фактически, он использует ту же идею, что и оригинальная попытка AShelly.

Ответ 7

Это работает и может быть проще понять, но манипуляции с битами настолько дешевы, что я не буду сильно беспокоиться об эффективности.

#include <stdio.h>
#include <stdlib.h>

void main() {
  unsigned int c = 0x1234, b;

  b = (c & 0xf000) * 0x11000 + (c & 0x0f00) * 0x01100 +
      (c & 0x00f0) * 0x00110 + (c & 0x000f) * 0x00011;

  printf("%x -> %x\n", c, b);
} 

Ответ 8

Предполагая, что вы хотите всегда конвертировать 0xWXYZ в 0xWWXXYYZZ, я считаю, что ниже решение будет немного быстрее, чем вы предложили:

unsigned int c = 0x1234;     
unsigned int b = (c & 0xf) | ((c & 0xf0) << 4) |
                 ((c & 0xf00) << 8) | ((c & 0xf000) << 12);
b |= (b << 4);

Обратите внимание, что одна & (and) операция сохраняется из вашего решения.:-)
Демо.

Ответ 9

Другой способ:

DWORD OrVal(DWORD & nible_pos, DWORD input_val, DWORD temp_val, int shift)
{
    if (nible_pos==0)
        nible_pos = 0x0000000F;
    else
        nible_pos = nible_pos << 4;
    DWORD nible = input_val & nible_pos;
    temp_val |= (nible << shift);
    temp_val |= (nible << (shift + 4));
    return temp_val;
}

DWORD Converter2(DWORD input_val)
{
    DWORD nible_pos = 0x00000000;
    DWORD temp_val = 0x00000000;
    temp_val = OrVal(nible_pos, input_val, temp_val, 0);
    temp_val = OrVal(nible_pos, input_val, temp_val, 4);
    temp_val = OrVal(nible_pos, input_val, temp_val, 8);
    temp_val = OrVal(nible_pos, input_val, temp_val, 12);
    return temp_val;
}

DWORD val2 = Converter2(0x1234);

Оптимизированная версия (в 3 раза быстрее):

DWORD Converter3(DWORD input_val)
{
    DWORD nible_pos = 0;
    DWORD temp_val = 0;
    int shift = 0;
    DWORD bit_nible[4] = { 0x000F, 0x000F0, 0x0F00, 0xF000 };

    for ( ; shift < 16; shift+=4 )
    {
        if (nible_pos==0)
            nible_pos = 0x0000000F;
        else
            nible_pos = nible_pos << 4;
        DWORD nible = input_val & nible_pos;
        temp_val |= (nible << shift);
        temp_val |= (nible << (shift + 4));
    }

    return temp_val;
}

Ответ 10

Возможно, это может быть проще и эффективнее.

unsigned int g = 0x1234;
unsigned int ans = 0;

ans = ( ( g & 0xf000 ) << 16) + ( (g & 0xf00 ) << 12)
    + ( ( g&0xf0 ) << 8) + ( ( g&0xf ) << 4);

ans  = ( ans | ans>>4 );

printf("%p -> %p\n", g, ans);

Ответ 11

unsigned long transform(unsigned long n)
{

    /* n: 00AR
     *    00GB
     */
    n = ((n & 0xff00) << 8) | (n & 0x00ff);

    /* n: 0AR0
     *    0GB0
     */
    n <<= 4;

    /* n: AAR0
     *    GGB0
     */
    n |= (n & 0x0f000f00L) << 4;

    /* n: AARR
     *    GGBB
     */
    n |= (n & 0x00f000f0L) >> 4;

    return n;
}

Альфа и красные компоненты смещаются в более высокие 2 байта, где они принадлежат, и результат затем сдвигается налево на 4 бита, в результате каждый компонент находится именно там, где он должен быть.

В форме 0AR0 0GB0 комбинация бит-масок и левого сдвига OR с текущим значением. Это копирует компоненты A и G в позицию слева от них. То же самое делается для компонентов R и B, за исключением противоположного направления.

Ответ 12

Если вы сделаете это для OpenGL, я предлагаю вам использовать функцию glTexImageXD с набором параметров type до GL_UNSIGNED_SHORT_4_4_4_4. Ваш драйвер OpenGL должен сделать все остальное. И о инверсии прозрачности вы всегда можете манипулировать смешением с помощью функций glBlendFunc и glBlendEquation.

Ответ 13

В то время как другие работают с жесткой оптимизацией...

Возьмите это как лучший выбор:

std::string toAARRGGBB(const std::string &argb)
{
    std::string ret("0x");

    int start = 2; //"0x####";
                   // ^^ skipped

    for (int i = start;i < argb.length(); ++i)
    {
        ret += argb[i];
        ret += argb[i];
    }
    return ret;
}

int main()
{
    std::string argb = toAARRGGBB("0xACED"); //!!!
}

Ха-ха