Convertir 0x1234 en 0x11223344

Question

Comment puis-je augmenter le nombre hexadécimal 0x1234 à 0x11223344 dans une manière très performante?

unsigned int c = 0x1234, b;
b = (c & 0xff) << 4 | c & 0xf | (c & 0xff0) << 8
        | (c & 0xff00) << 12 | (c & 0xf000) << 16;
printf("%p -> %p\n", c, b);

Sortie:

0x1234 -> 0x11223344

J'en ai besoin pour la conversion des couleurs. Les utilisateurs fournissent leurs données dans le formulaire 0xARGB, et j'ai besoin de le convertir en 0xAARRGGBB. Et oui, il pourrait y avoir des millions, parce que chacun peut être un pixel. 1000x1000 pixels est égal à un million.

Le cas réel est encore plus compliqué, car une seule valeur de 32 bits contient à la fois de premier plan et les couleurs de fond. Donc, 0xARGBargb devenir: [ 0xAARRGGBB, 0xaarrggbb ]

Oh oui, encore une chose, dans une application réelle j'ai aussi nier l'alpha, parce que dans OpenGL 0xFF est pas transparent et 0x00 est le plus transparent, ce qui est gênant dans la plupart des cas, parce que d'habitude, vous avez juste besoin d'un RGB de la partie et la transparence est supposé être non-présent.

Answer 1

Cela peut être fait en utilisant SSE2 comme suit:

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);
}

Bien sûr, vous voulez mettre les entrailles de la fonction dans une boucle intérieure et tirez sur les constantes. Vous aurez aussi envie de sauter le x64 les registres et les valeurs de la charge directement sur 128 bits des registres SSE. Pour un exemple de la façon de procéder, reportez-vous à la SSE2 mise en œuvre dans le test de performance ci-dessous.

À la base, il y a 5 instructions effectuer l'opération sur les 4 valeurs de couleur à la fois. Donc, c'est seulement d'environ 1,25 instructions par valeur de couleur. Il convient également de noter que SSE2 est disponible n'importe où x64 est disponible.

Des tests de Performance pour un assortiment de solutions ici
Quelques personnes ont mentionné que la seule façon de savoir ce qui est plus rapide à exécuter le code, c'est incontestable. J'ai donc compilé quelques-unes des solutions dans un test de performance afin que nous puissions comparer des pommes avec des pommes. J'ai choisi les solutions que j'ai ressenties ont été significativement différente de celle des autres suffisamment pour passer des tests. Toutes les solutions de lecture de la mémoire, opèrent sur les données, et d'écrire de nouveau à la mémoire. Dans la pratique, certaines de l'ESS solutions nécessitent davantage de soins autour de l'alignement et le traitement des cas quand il n'y a pas d'autre de 16 octets à traiter dans les données d'entrée. Le code que j'ai testé est x64 compilé sous version à l'aide de VS2013 en cours d'exécution sur un 4+GHz i7.

Voici mes résultats:

ExpandOrig:               56.234 seconds  // from askers original question
ExpandSmallLUT:           30.209 seconds  // from Dmitry's answer
ExpandLookupSmallOneLUT:  33.689 seconds  // from Dmitry's answer
ExpandLookupLarge:        51.312 seconds  // a straightforward lookup table
ExpandAShelly:            43.829 seconds  // from AShelly's answer
ExpandAShellyMulOp:       43.580 seconds  // AShelly's 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

Dans les résultats du test ci-dessus, vous verrez que j'inclus la askers code, trois table de recherche implémentations y compris la petite table de la mise en œuvre proposée dans Dmitry réponse. AShelly de la solution est également inclus, ainsi qu'une version avec une optimisation que j'ai fait (une opération peut être éliminé). J'ai inclus mon original SSE4 mise en œuvre, ainsi que d'un supérieur SSE2 version que j'ai faite plus tard (maintenant compte que la réponse), ainsi que le déroulé des versions de fois depuis qu'ils ont été le plus rapide ici et je voulais voir comment beaucoup de dérouler accéléré. J'ai aussi inclus un SSE4 mise en œuvre de AShelly de réponse.

Jusqu'à présent, je dois me déclarer vainqueur. Mais la source est en bas, donc n'importe qui peut le tester sur leur plate-forme, et disposent de leur propre solution dans les tests pour voir si ils ont mis au point une solution encore plus rapide.

#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 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's 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's 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's 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's 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's 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;
}

NOTE:
J'ai eu un SSE4 mise en œuvre ici d'abord. J'ai trouvé un moyen de mettre en œuvre cette aide SSE2, ce qui est mieux car il sera exécuté sur plusieurs plates-formes. Le SSE2 mise en œuvre est également plus rapide. Donc, la solution présentées dans la partie supérieure est maintenant le SSE2 mise en œuvre et de ne pas le SSE4. Le SSE4 mise en œuvre peut encore être vu dans les tests de performance ou de modifier l'histoire.

Answer 2

Je ne suis pas sûr de ce que le plus efficace serait, mais c'est un peu plus courte:

#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;
}

---

Si vous avez besoin de faire cela à plusieurs reprises et très rapidement, comme il est suggéré dans votre montage, vous pourriez envisager de générer une table de recherche et l'utilisation de la place. La fonction suivante dynamique alloue et initialise une telle table:

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;
}

Après que chaque conversion est tout simplement quelque chose comme:

result = lookuptable[input];

..ou peut-être:

result = lookuptable[input & 0xffff];

---

Ou un plus petit, plus de cache-friendly table de recherche (ou paire) peut être utilisé avec un recherche de chaque pour la haute et basse octets (comme indiqué par @LưuVĩnhPhúc dans les commentaires). Dans ce cas, la table de génération de code peut être:

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;
}

...et en option un deuxième tableau:

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;
}

...et pour convertir une valeur avec deux tables:

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

...ou avec un (juste le bas de la table ci-dessus):

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

Si la partie supérieure de la valeur (alpha?) ne change pas beaucoup, même l'unique grande table peuvent bien performer depuis consécutive, les recherches seraient plus proches dans le tableau.

---

J'ai pris le test de performance code @Apriorique posté, fait quelques ajustements, et l'ajout de tests pour les autres réponses, qu'il n'avait pas inclus à l'origine... ensuite compilé en trois versions avec des paramètres différents. L'un est 64 bits de code avec SSE4.1 activé, où le compilateur peut faire usage de l'ESS pour des optimisations... et puis les deux versions 32 bits, l'un avec l'ESS et l'autre sans. Bien que tous les trois ont été exécutés sur le même assez récent processeur, les résultats montrent comment la solution optimale peut changer en fonction des caractéristiques de processeur:

                           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

Les exécutables ont été compilés sur une version 64 bits de Linux avec gcc 4.8.1, à l'aide de -m64 -O3 -march=core2 -msse4.1, -m32 -O3 -march=core2 -msse4.1 et -m32 -O3 -march=core2 -mno-sse respectivement. @Apriorique de l'ESS, des tests ont été omis pour les 32-bit versions (s'est écrasé sur 32 bits avec l'ESS activé, et, évidemment, de ne pas travailler avec l'ESS désactivé).

Parmi les ajustements faite a été d'utiliser des données réelles de l'image au lieu de valeurs aléatoires (photos d'objets avec des arrière-plans transparents), qui a grandement amélioré la performance de la grande table de recherche, mais fait peu de différence pour les autres.

Essentiellement, les tables de gagner par un glissement de terrain lors de l'ESS est unnavailable (ou non)... et de la main codé de l'ESS, des solutions gagner autrement. Cependant, il est également à noter que lorsque le compilateur peut utiliser ESS pour les optimisations, la plupart de la manipulation de bits solutions ont été presque aussi rapide que la codées manuellement l'ESS, encore plus lentement, mais de façon marginale.

Answer 3

Voici une autre tentative, à l'aide de huit opérations:

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

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

---

*Notez que ce post contenait à l'origine tout à fait différente de code, basé sur l' Entrelacement de bits en Binaire les Nombres Magiques de Sean Anderson bithacks page. Mais ce n'était pas tout à fait ce que l'OP a été demandé. donc, il a été supprimé. La majorité des commentaires ci-dessous concernent que manquant de version.

Answer 4

Je voulais ajouter ce lien dans la réponse de la piscine parce que je pense qu'il est extrêmement important lorsque l'on parle d'optimisation, de se rappeler du matériel sont en cours d'exécution, ainsi que les technologies de compiler notre code de ladite plateforme. Ce lien est un blog à propos de la recherche dans l'optimisation d'un ensemble de code pour le PROCESSEUR pipeline. En fait je montre un exemple de cas où il essaie de simplifier le calcul vers le bas pour le moins réel des opérations mathématiques, et pourtant il était LOIN d'être la solution la plus optimale en termes de temps. J'ai vu un couple de réponses ici la parole à cet effet, et ils ont peut-être raison, ils ne peuvent pas. La seule façon de le savoir est de mesurer le temps à partir de début à la fin de votre snippit de code, en comparaison à d'autres. Lisez ce blog, c'est EXTRÊMEMENT intéressant.

http://lolengine.net/blog/2011/9/17/playing-with-the-cpu-pipeline

Je pense que je dois préciser que je suis dans ce cas particulier, va mettre TOUT le code jusqu'ici, sauf si j'ai vraiment essayé de multiples tentatives, et sommes en fait sur ce qui est particulièrement rapide à travers de multiples essais.

Answer 5

Je pense que la table de recherche de l'approche suggérée par Dimitri est un bon choix, mais je suggère d'aller plus loin et de générer la table au moment de la compilation; faire le travail au moment de la compilation sera bien évidemment de diminuer le temps d'exécution.

Tout d'abord, nous créons un moment de la compilation de la valeur, en utilisant l'une des méthodes suggérées:

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;
};

Et puis, nous créons le moment de la compilation de la table de choix avec quelle que soit la méthode que nous avons de disponible, je vous souhaite utiliser le C++14 entier de la séquence , mais je ne sais pas quel compilateur de l'OP. Une autre approche possible serait d'utiliser un assez laid macro:

#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

Voir la démo ici.

PS: L' Adam Liss approche pourrait être utilisée sans le C++11.