Comment faire des bandes de bits sur des données de pixels?

J’ai 3 tampons contenant des données de bit R, V, B fonctionnant sur un processeur 32 bits

J’ai besoin de combiner les trois octets de la manière suivante:

R[0] = 0b r1r2r3r4r5r6r7r8 G[0] = 0b g1g2g3g4g5g6g7g8 B[0] = 0b b1b2b3b4b5b6b7b8 int32_t Out = 0b r1g1b1r2g2b2r3g3 b3r4g4b4r5g5b5r6 g6b6r7g7b7r8g8b8 xxxxxxxx 

où xxxxxxxx continue sur chacun des octets suivants dans les tampons.

Je cherche un moyen optimal de les combiner. Mon approche n’est certainement pas efficace.

Voici mon approche

 static void rgbcombineline(uint8_t line) { uint32_t i, bit; uint8_t bitMask, rByte, gByte, bByte; uint32_t ByteExp, rgbByte; uint8_t *strPtr = (uint8_t*)&ByteExp; for (i = 0; i < (LCDpixelsCol / 8); i++) { rByte = rDispbuff[line][i]; gByte = gDispbuff[line][i]; bByte = bDispbuff[line][i]; bitMask = 0b00000001; ByteExp = 0; for(bit = 0; bit > bit) <> bit) <> bit); ByteExp |= (rgbByte << 3*bit); bitMask <<= 1; } TempLinebuff[((i*3)+0) +2] = *(strPtr + 2); TempLinebuff[((i*3)+1) +2] = *(strPtr + 1); TempLinebuff[((i*3)+2) +2] = *(strPtr + 0); } } 

Si vous pouvez économiser 1024 octets, vous pouvez obtenir le résultat souhaité avec une seule table de recherche à 256 éléments:

 uint32_t lookup[256] = { 0, 1, 8, 9, 64, 65, ... /* map abcdefgh to a00b00c00d00e00f00g00h */ }; uint32_t result = (lookup[rByte] << 2) | (lookup[gByte] << 1) | lookup[bByte]; 

Cela utilise seulement 3 consultations, 2 équipes et 2 or opérations, ce qui devrait fournir une accélération acceptable.

Si vous disposez de plus d'espace, vous pouvez utiliser trois tables de recherche pour éliminer également les décalages (bien que cela puisse entraîner une dégradation des performances de la mémoire cache, veillez donc toujours à définir le profil à vérifier!)

Vous pouvez utiliser une multiplication par une constante “magique” pour répliquer les bits. Utilisez ensuite des décalages binarys pour extraire les bits nécessaires et un masquage binary pour les combiner. La constante “magique” est une valeur binary de 17 bits 10000000100000001. Lorsqu’elle est multipliée par celle-ci, tout nombre de 8 bits est concaténé à lui-même 3 fois.

 r1r2r3r4r5r6r7r8 * M = r1 r2r3r4r5r6r7r8r1r2r3r4 r5 r6r7r8r1r2r3r4r5r6r7r7r8
 r1r2r3r4r5r6r7r8 * M shr 2 = 0 0 r1 r2 r3r4r5r6r7r8r1r2r3r4r5 r6 r7r8r1r2r3r4r5r6
 r1r2r3r4r5r6r7r8 * M shr 4 = 0 0 0 0 r1r2 r3 r4r5r6r7r8r1r2r3r4r5r6 r7 r8r1r2r3r4
 r1r2r3r4r5r6r7r8 * M shr 6 = 0 0 0 0 0 0 r1r2r3 r4 r5r6r7r8r1r2r3r4r5r6r7 r8 r1r2

Les bits en gras sont ceux qui sont aux bons endroits.

Si vous utilisez ce code de masquage

 R * M & 0b100000000000100000000000 | (R * M >> 2) & 0b000100000000000100000000 | (R * M >> 4) & 0b000000100000000000100000 | (R * M >> 6) & 0b000000000100000000000100 

vous obtiendrez les bits “rouges” combinés de la bonne manière:

 r1 0 0 r2 0 0 r3 0 0 r4 0 0 r5 0 0 r6 0 0 r7 0 0 r8 0 0 

Combinez ensuite les bits “bleu” et “vert” de la même manière.


Une estimation approximative du nombre d’opérations:

  • Multiplications: 3
  • Changements de bits: 9
  • Au niveau du bit ET: 12
  • Au niveau du bit OU: 11

Vous pouvez utiliser une table de taille 64 contenant des valeurs en bits pour 6 bits, puis extraire 2 bits chacun de r, g et b et utiliser table pour une recherche plus rapide. L’utilisation de la taille 512 ou 4096 peut être plus efficace.

 /* Converts bits abcdefghijkl to adgjbehkcfil */ static const uint32_t bitSsortingpLookUp[4096] = { /* Hard coded values, can be generate with some script */ ... }; ... rByte = rDispbuff[line][i]; // rByte, gByte, bByte should be unit32 gByte = gDispbuff[line][i]; bByte = bDispbuff[line][i]; uMSB = ((rByte << 4) & 0x0F00) | (gByte & 0x00F0) | ((bByte >> 4) & 0x000F); // r7r6r5r4g7g6g5g4b7b6b5b4 uLSB = ((rByte << 8) & 0x0F00) | ((gByte << 4) & 0x00F0) | (bByte & 0x000F); // r3r2r1r0g3g2g1g0b3b2b1b0 stuffed_value = (bitStripLookUp[uMSB] << 12) | bitStripLookUp[uLSB]; 

Entrelacement avec des opérateurs de bits

 inline unsigned interleave(unsigned n) { n = ((n << 18) | (n << 9) | n) & 0007007007; // 000000111 000000111 000000111 n = ((n << 6) | (n << 3) | n) & 0444444444; // 100100100 100100100 100100100 return n; } unsigned r = interleave(rByte); unsigned g = interleave(gByte); unsigned b = interleave(bByte); unsigned rgb = r | (g >> 1) | (b >> 2); TempLinebuff[((i*3)+0) +2] = rgb >> 16; TempLinebuff[((i*3)+1) +2] = rgb >> 8; TempLinebuff[((i*3)+2) +2] = rgb; 

Solution de table de consultation

 #define EXPANDBIT(x, n) (((x) & (1 << (n))) << (3*(n)))) #define EXPAND8BIT(a) (EXPANDBIT(a, 0) | EXPANDBIT(a, 1) | EXPANDBIT(a, 2) | EXPANDBIT(a, 3) | \ EXPANDBIT(a, 4) | EXPANDBIT(a, 5) | EXPANDBIT(a, 6) | EXPANDBIT(a, 7)) #define EXPAND16(A) EXPAND8BIT(16*(A)+ 0), EXPAND8BIT(16*(A)+ 1), EXPAND8BIT(16*(A)+ 2), EXPAND8BIT(16*(A)+ 3), \ EXPAND8BIT(16*(A)+ 4), EXPAND8BIT(16*(A)+ 5), EXPAND8BIT(16*(A)+ 6), EXPAND8BIT(16*(A)+ 7), \ EXPAND8BIT(16*(A)+ 8), EXPAND8BIT(16*(A)+ 9), EXPAND8BIT(16*(A)+10), EXPAND8BIT(16*(A)+11), \ EXPAND8BIT(16*(A)+12), EXPAND8BIT(16*(A)+13), EXPAND8BIT(16*(A)+14), EXPAND8BIT(16*(A)+15) const uint32_t LUT[256] = { EXPAND16( 0), EXPAND16( 1), EXPAND16( 2), EXPAND16( 3), EXPAND16( 4), EXPAND16( 5), EXPAND16( 6), EXPAND16( 7), EXPAND16( 8), EXPAND16( 9), EXPAND16(10), EXPAND16(11), EXPAND16(12), EXPAND16(13), EXPAND16(14), EXPAND16(15) }; output = LUT[rByte] | LUT[gByte] << 1 | LUT[bByte] << 2; 

La taille de la table de consultation peut être augmentée si nécessaire


Sur x86 avec BMI2, il existe un support matériel avec instruction PDEP accessible via l’ _pdep_u32 insortingnsèque _pdep_u32 . La solution est maintenant beaucoup plus simple

 output = _pdep_u32(rByte, 044444444U << 8) | _pdep_u32(gByte, 022222222U << 8) | _pdep_u32(bByte, 011111111U << 8); 

Une autre façon est

entrelacement par multiplication et masque avec cette technique d'emballage

Ceci est pour les architectures sans instruction de repository de bit matériel mais avec multiplicateurs rapides

 uint32_t expand8bits(uint8_t b) { uint64_t MAGIC = 0x8040201008040201; uint64_t MASK = 0x8080808080808080; uint64_t expanded8bits = htobe64((MAGIC*b) & MASK); uint64_t result = expanded8bits*0x2108421 & 0x9249000000009000; // no need to shift if you want to get the bits in the high part return ((result | (result << 30)) & (044444444ULL << 8)) >> 32; } uint32_t ssortingpeBits(uint8_t rByte, uint8_t gByte, uint8_t bByte) { return expand8bits(rByte) | (expand8bits(gByte) >> 1) | (expand8bits(bByte) >> 2); } 

La façon dont cela fonctionne est comme ça

  • La première étape étend les bits d’entrée de abcdefgh à a0000000 b0000000 c0000000 d0000000 e0000000 f0000000 g0000000 h0000000 et expand8bits dans expand8bits
  • Ensuite, nous rapprochons les bits espacés en les multipliant et en les masquant à l'étape suivante. Après ce result contient a00b00c00d00e00f00000000000000000000000000000000000000000000000000 et sera prêt à être fusionné en une seule valeur

Le nombre magique pour rapprocher les bits est calculé comme ceci

  a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000 × 10000100001000010000100001 (0x2108421) ──────────────────────────────────────────────────────────────── a0000000b0000000c0000000d0000000e0000000f0000000g0000000h0000000 000b0000000c0000000d0000000e0000000f0000000g0000000h0000000 + 000000c0000000d0000000e0000000f0000000g0000000h0000000 0c0000000d0000000e0000000f0000000g0000000h0000000 0000d0000000e0000000f0000000g0000000h0000000 0000000e0000000f0000000g0000000h0000000 ──────────────────────────────────────────────────────────────── ac0bd0cebd0ce0dfce0df0egdf0eg0fheg0fh0g0fh0g00h0g00h0000h0000000 & 1001001001001001000000000000000000000000000000001001000000000000 (0x9249000000009000) ──────────────────────────────────────────────────────────────── a00b00c00d00e00f00000000000000000000000000000000g00h000000000000 

expand8bits peut aussi être implémenté en utilisant seulement la multiplication de nombres magiques 32 bits comme celle-ci, qui peut être plus simple

 uint32_t expand8bits(uint8_t b) { const uint8_t RMASK_1458 = 0b10011001; const uint32_t MAGIC_1458 = 0b00000001000001010000010000000000U; const uint32_t MAGIC_2367 = 0b00000000010100000101000000000000U; const uint32_t MASK_BIT1458 = 0b10000000010010000000010000000000U; const uint32_t MASK_BIT2367 = 0b00010010000000010010000000000000U; return (((b & RMASK_1458) * MAGIC_1458) & MASK_BIT1458) | (((b & ~RMASK_1458) * MAGIC_2367) & MASK_BIT2367); } 

Nous divisons ici le nombre de 8 bits en deux parties de 4 bits, l'une avec les bits 1, 4, 5, 8 et les autres, avec les bits 2, 3, 6, 7. Les nombres magiques sont comme ceci

  a00de00h 0bc00fg0 × 00000001000001010000010000000000 × 00000000010100000101000000000000 ──────────────────────────────── ──────────────────────────────── a00de00h 0bc00fg0 + a00de00h + 0bc00fg0 a00de00h 0bc00fg0 a00de00h 0bc00fg0 ──────────────────────────────── ──────────────────────────────── a00de0ahadedehah0de00h0000000000 000bcbcfgfgbcbcfgfg0000000000000 & 10000000010010000000010000000000 & 00010010000000010010000000000000 ──────────────────────────────── ──────────────────────────────── a00000000d00e00000000h0000000000 000b00c00000000f00g0000000000000 

Voir

  • Qu'est-ce qu'un moyen rapide pour espacer des bits dans un mot?
  • Comment créer un octet sur 8 valeurs bool (et vice versa)?
  • Alternative portable efficace au PDEP sans utiliser BMI2?