Comment insérer des zéros entre les bits d’une bitmap?

J’ai un code très performant qui effectue des manipulations de bits. Il peut être réduit au problème bien défini suivant:

À partir d’un bitmap 13 bits, construisez un bitmap 26 bits contenant les bits originaux espacés de manière égale .

Pour illustrer:

0000000000000000000abcdefghijklm (input, 32 bits) 0000000a0b0c0d0e0f0g0h0i0j0k0l0m (output, 32 bits) 

Je l’ai actuellement implémenté de la manière suivante en C:

 if (input & (1 << 12)) output |= 1 << 24; if (input & (1 << 11)) output |= 1 << 22; if (input & (1 << 10)) output |= 1 << 20; ... 

Mon compilateur (MS Visual Studio) a transformé ceci en ce qui suit:

 test eax,1000h jne 0064F5EC or edx,1000000h ... (repeated 13 times with minor differences in constants) 

Je me demande si je peux le faire plus vite. J’aimerais que mon code soit écrit en C, mais le passage en langage assembleur est possible.

  • Puis-je utiliser certaines instructions MMX / SSE pour traiter tous les bits à la fois?
  • Peut-être que je peux utiliser la multiplication? (multiplier par 0x11111111 ou une autre constante magique)
  • Serait-il préférable d’utiliser l’instruction condition-set (SETcc) plutôt que l’instruction condition-jump? Si oui, comment puis-je faire en sorte que le compilateur produise ce code pour moi?
  • Une autre idée comment faire plus vite?
  • Avez-vous une idée de la transformation inverse d’un bitmap (je dois l’implémenter aussi, mais c’est moins critique)?

Faites-le avec une table de recherche. 2 ^ 13, cela ressemble à beaucoup d’entrées mais elles vont facilement s’intégrer dans le cache du CPU

Oh, et s’il y a des ordures dans les 19 autres bits, vous devez d’abord les masquer.

Il existe un moyen astucieux de faire cela qui peut être utile ici. Cela résout en fait un problème un peu plus général de mélange de bits. Votre problème a une entrée de:

 +---------------+---------------+---------------+---------------+ |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|0 0 0 abcde|fghijklm| +---------------+---------------+---------------+---------------+ 

…. mais considérons tous les bits:

 +---------------+---------------+---------------+---------------+ |ABCDEFGH|IJKLMNOP|QRS abcde|fghijklm| +---------------+---------------+---------------+---------------+ 

et essayer de les entrelacer tous comme suit:

 +---------------+---------------+---------------+---------------+ |AQBRCSD a|E b F c G d H e|I f J g K h L i|M j N k O l P m| +---------------+---------------+---------------+---------------+ 

Pour la première étape, considérons la moitié médiane de l’entrée:

 bit 31 24 16 8 0 vvvvv +---------------+---------------+---------------+---------------+ | |IJKLMNOP|QRS abcde| | +---------------+---------------+---------------+---------------+ 

Construisez la valeur sur 8 bits: { I^Q , J^R , K^S , L^a , M^b , N^c , O^d , P^e }.

Si nous-exclusif-OU cette valeur de 8 bits avec les bits [15: 8], et également exclusif-OU de la même valeur de 8 bits avec les bits [23:16], nous échangerons les deux octets du milieu: par exemple, le bit 23 (à l’origine I ) deviendra I ^ (I^Q) = Q et le bit 15 (à l’origine Q ) deviendra Q ^ (I^Q) = I

Pour ce faire: tmp = (input ^ (input >> 8)) & 0x0000ff00; :

 +---------------+---------------+---------------+---------------+ |ABCDEFGH|IJKLMNOP|QRS abcde|fghijklm| input +---------------+---------------+---------------+---------------+ exclusive-OR with: +---------------+---------------+---------------+---------------+ |0 0 0 0 0 0 0 0|ABCDEFGH|IJKLMNOP|QRS abcde| input >> 8 +---------------+---------------+---------------+---------------+ -->|want these bits|<-- mask (bitwise AND) with 0x0000ff00: +---------------+---------------+---------------+---------------+ |0 0 0 0 0 0 0 0|0 0 0 0 0 0 0 0|1 1 1 1 1 1 1 1|0 0 0 0 0 0 0 0| 0x0000ff00 +---------------+---------------+---------------+---------------+ 

Maintenant, la valeur de 8 bits dont nous avons besoin est en bits [15: 8], avec tous les autres bits 0. Nous pouvons maintenant effectuer le swap avec

 input ^= (tmp ^ (tmp << 8)); 

résultant en:

 +---------------+---------------+---------------+---------------+ |ABCDEFGH|QRS abcde|IJKLMNOP|fghijklm| input +---------------+---------------+---------------+---------------+ 

Pour la prochaine étape, divisez pour mieux conquérir ... effectuez un échange similaire entre les bits du milieu de la moitié gauche:

 +---------------+---------------+---------------+---------------+ |ABCDEFGH|QRS abcde| | | +---------------+---------------+---------------+---------------+ becomes +---------------+---------------+---------------+---------------+ |ABCDQRS a|EFGH bcde| | | +---------------+---------------+---------------+---------------+ 

... et la moitié droite:

 +---------------+---------------+---------------+---------------+ | | |IJKLMNOP|fghijklm| +---------------+---------------+---------------+---------------+ becomes +---------------+---------------+---------------+---------------+ | | |IJKL fghi|MNOP jklm| +---------------+---------------+---------------+---------------+ 

Nous pouvons utiliser exactement le même truc que dans la première étape, et comme nous voulons effectuer exactement la même opération sur les deux moitiés 16 bits du mot 32 bits, nous pouvons les effectuer en parallèle:

 tmp = (input ^ (input >> 4)) & 0x00f000f0; 

construit les deux paires de 4 bits que nous allons utiliser pour le swap, puis

 input ^= (tmp ^ (tmp << 4)); 

fait réellement l'échange.

Nous pouvons continuer à appliquer le même principe jusqu'à la fin de l'échange. Les bits qui participent à l'échange à chaque point sont marqués d'un # :

 +---------------+---------------+---------------+---------------+ |ABCDEFGH|IJKLMNOP|QRS abcde|fghijklm| +---------------+---------------+---------------+---------------+ ###############/############### +---------------+---------------+---------------+---------------+ |ABCDEFGH|QRS abcde|IJKLMNOP|fghijklm| +---------------+---------------+---------------+---------------+ #######/####### #######/####### +---------------+---------------+---------------+---------------+ |ABCDQRS a|EFGH bcde|IJKL fghi|MNOP jklm| +---------------+---------------+---------------+---------------+ ###/### ###/### ###/### ###/### +---------------+---------------+---------------+---------------+ |ABQRCDS a|EF bc GH de|IJ fg KL hi|MN jk OP lm| +---------------+---------------+---------------+---------------+ #/# #/# #/# #/# #/# #/# #/# #/# +---------------+---------------+---------------+---------------+ |AQBRCSD a|E b F c G d G e|I f J g K h L i|M j N k O l P m| +---------------+---------------+---------------+---------------+ 

Code:

 tmp = (input ^ (input >> 8)) & 0x0000ff00; input ^= (tmp ^ (tmp << 8)); tmp = (input ^ (input >> 4)) & 0x00f000f0; input ^= (tmp ^ (tmp << 4)); tmp = (input ^ (input >> 2)) & 0x0c0c0c0c; input ^= (tmp ^ (tmp << 2)); tmp = (input ^ (input >> 1)) & 0x22222222; input ^= (tmp ^ (tmp << 1)); /* = output */ 

L'opération inverse peut être effectuée en effectuant les 4 étapes à l'envers:

 tmp = (input ^ (input >> 1)) & 0x22222222; input ^= (tmp ^ (tmp << 1)); /* = output */ tmp = (input ^ (input >> 2)) & 0x0c0c0c0c; input ^= (tmp ^ (tmp << 2)); tmp = (input ^ (input >> 4)) & 0x00f000f0; input ^= (tmp ^ (tmp << 4)); tmp = (input ^ (input >> 8)) & 0x0000ff00; input ^= (tmp ^ (tmp << 8)); 

bien que vous puissiez peut-être améliorer ceci pour votre application particulière, si on sait que tous les bits sont nuls: voir ma réponse à une autre question ici .


En guise de conclusion, ne croyez pas que qui que ce soit dise au sujet de la performance relative de l’une des méthodes suggérées ici sans les parsingr dans votre application . (En particulier, les grandes tables de consultation peuvent sembler bien meilleures, dans les simples micro-critères, qu’elles ne le sont en réalité dans une application réelle donnée, en raison de l’expulsion de grandes quantités d’autres données du cache, ce qui peut avoir un effet négatif sur la boucle externe. (s).)

Vous pourriez faire:

 ; eax = input bits shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,2 shr eax,1 shrd edx,eax,8 and edx,0x01555555 ; edx = output 

N’utilisez pas de twigs:

 output = (input & 1) | ((input & 2) << 1) | ((input & 4) << 2) | ((input & 8) << 3) | ((input & 16) << 4) /* etc. */ 

Voici une version peut-être plus facile à lire / à comprendre de la même chose:

 output = ((input & (1 << 0)) << 0) | ((input & (1 << 1)) << 1) | ((input & (1 << 2)) << 2) | ((input & (1 << 3)) << 3) | ((input & (1 << 4)) << 4) | ((input & (1 << 5)) << 5) | ((input & (1 << 6)) << 6) | ((input & (1 << 7)) << 7) | ((input & (1 << 8)) << 8) | ((input & (1 << 9)) << 9) | ((input & (1 << 10)) << 10) | ((input & (1 << 11)) << 11) | ((input & (1 << 12)) << 12); 

Je vais vous donner un algorithme qui fonctionne sans condition (uniquement des opérations d’addition et au niveau des bits), et je pense que ce sera plus rapide que votre solution actuelle.

Voici le code C pour 13 bits. Vous trouverez ci-dessous une illustration du fonctionnement de la méthode pour 3 bits, et la généralisation sera claire, je l’espère.

(Remarque: le code est déroulé en boucle. Un bon compilateur le fera pour vous, vous pouvez donc le condenser en boucle.)

 unsigned mask, output; unsigned x = input; mask = ((1<<13)-1) << 13; x = (x + mask) & ~mask; mask = ((1<<12)-1) << 12; x = (x + mask) & ~mask; ... mask = ((1<<3)-1) << 3; x = (x + mask) & ~mask; mask = ((1<<2)-1) << 2; x = (x + mask) & ~mask; mask = ((1<<1)-1) << 1; x = (x + mask) & ~mask; output = x; 

Maintenant, voici l'explication de la méthode pour 3 bits. L'état initial est '00abc'. Commencez par déplacer "a" deux places vers la gauche en ajoutant 01100, puis ANDing avec 10011 (ce qui se trouve être le PAS au niveau du nombre précédent du nombre). Voici comment cela fonctionne pour a = 0,1 (la première flèche correspond à l'addition, la deuxième flèche correspond à AND):

a = 0: 00abc = 000bc -> 011bc -> 000bc = a00bc
a = 1: 00abc = 001bc -> 100bc -> 100bc = a00bc

Ensuite, déplacez 'b' un endroit à gauche en ajoutant 00010 puis ANDing avec 10101:

b = 0: a00bc = a000c -> a001c -> a000c = a0b0c
b = 1: a00bc = a001c -> a010c -> a010c = a0b0c

C'est tout.

Premièrement, pour vos valeurs “26 bits”, le bit le plus élevé doit toujours être clair, c’est donc une valeur de 25 bits.

1) MMX (et / ou SSE) n’aidera pas, car le problème principal est qu’il n’existe pas de simples séries d’opérations arithmétiques ou booléennes qui donnent les résultats souhaités et que tout prend en charge les mêmes opérations arithmétiques et booléennes.

2) Je ne pouvais pas penser ou trouver une constante magique pour la multiplication.

3) Je ne vois pas de méthode d’utilisation d’une instruction de jeu de conditions (par exemple, SETcc) présentant des avantages par rapport aux instructions de décalage / ajout.

4) jdv et paul (ci-dessus) ont raison. Si vous devez effectuer cette conversion assez souvent pour que les performances importent, alors une table de recherche serait l’option la plus performante / la plus rapide sur les processeurs modernes. La table de correspondance “13 bits à 26 bits” indiquerait 2 ** 13 mots, ou 32 Ko. Sur les anciens processeurs (avec de petits caches L1), la différence relative entre la vitesse du processeur et la vitesse de la RAM n’est pas aussi grave qu’aujourd’hui.

Si vous ne pouvez pas utiliser 32 Ko pour la table de correspondance “13 bits à 25 bits”, vous pouvez fractionner la valeur 13 bits en une paire de valeurs (une valeur 6 bits et une valeur 7 bits), puis utilisez la table de recherche sur chacune de ces valeurs avant de combiner les résultats, comme ceci:

 mov ebx,eax ;ebx = 13-bit value shr eax,6 ;eax = highest 7 bits of value and ebx,0x003F ;ebx = lowest 6 bits of value mov eax,[lookup_table + eax*2] ;eax = highest 14-bits of result mov ebx,[lookup_table + ebx*2] ;eax = lowest 12-bits of result shl eax,12 or eax,ebx ;eax = 25-bit result 

Dans ce cas, la table de recherche contient 128 entrées (avec 2 octets par entrée), donc seulement 256 octets.

5) Pour l’opération inverse, une simple table de consultation vous coûterait 64 Mio (2 ** 25 * 2), ce qui n’est pas une bonne idée. Toutefois, vous pouvez scinder la valeur de 25 bits en une valeur de 13 bits et une valeur de 11 bits (valeur de 12 bits où le bit le plus élevé est toujours effacé), et utiliser une table d’entrées 8192 avec un octet par entrée (valeur totale). le coût est de 8 KiB). Il n’y a aucune raison pour que vous ne puissiez pas diviser les valeurs 25 bits en plus / morceaux plus petits (et utiliser un tableau beaucoup plus petit).

Sur les processeurs Intel x86 à partir de Haswell, vous pouvez utiliser une seule instruction BMI2 du BMI2 instructions BMI2 pour le faire:

 uint32_t interleave_zero_bits(uint32_t x) { return _pdep_u32(x, 0x55555555U); } 

Je pense que cela pourrait être pertinent, mais je ne suis pas complètement certain. Je connais des instructions MMX pour l’entrelacement d’octets de valeurs 32/64 bits, mais pas de bits individuels.

Vous n’avez pas spécifié la plate-forme sur laquelle il doit fonctionner, et j’aimerais essayer une approche différente de celle déjà publiée (j’aime la table de recherche, qui fonctionne bien jusqu’à ce que le nombre de bits augmente).

La plupart des plates-formes ont des instructions de décalage et de rotation distinctes. Presque toujours, une instruction inclut les indicateurs de report / dépassement, de sorte que vous pouvez “basculer” un peu comme vous le souhaitez. Disons que nous avons ces instructions: * SHIFTLEFT: effectue un décalage gauche et remplit le bit inférieur avec zéro. * ROTATELEFT: effectue un décalage vers la gauche, définit le bit le plus bas de l’ancienne valeur de l’indicateur de portage et définit le report du bit qui a été déplacé “out” à gauche.

Pseudocode:

 LOAD value into register A; LOAD 0 into register B; SHIFT register A (registerwidth-13) times; ROTATELEFT A ROTATELEFT B SHIFTLEFT B 

… répète 13 fois. Dérouler à votre guise.

Le premier quart de travail devrait mettre le bit le plus haut en place juste avant le report. ROTATELEFT A va pousser le MSB dans la retenue, ROTATELEFT B va pousser le bit dans le LSB de B et SHIFTLEFT B mettra le 0 dedans. Faites cela pour tous les bits.


Modifier / ajouté:

Vous pouvez faire le contraire (transformation de bitmap inverse) avec les mêmes instructions, comme ceci:

LOAD dans le registre A; LOAD 0 dans le registre B;

ROTATELEFT A; ROTATELEFT A; ROTATELEFT B; … répéter 13 fois puis SHIFTLEFT B; pour (registerwidth-13) fois.

LSB à porter; oubliez cela, passez au LSB suivant, mettez cela dans le registre cible, répétez l’opération pour tous les bits, puis alignez le résultat.

Vous pouvez toujours utiliser une boucle for:

 for (int i = 0; i < 13; i++) { output |= (input & (1 << i)) << i; } 

C'est plus court, mais je ne pense pas que ce soit beaucoup plus rapide.

Vérifiez si votre processeur prend en charge la permutation d’octets et de mots (pour la conversion endian) – si c’est le cas – lancez simplement une permutation dessus – ce serait quelques 6 (5) instructions plus courtes.