Quel est le moyen le plus rapide de faire pivoter les bits d’un bloc 8×8 sur des bits?

Je ne suis pas sûr du terme exact pour ce que j’essaie de faire. J’ai un bloc de bits 8x8 stocké dans 8 bytes , chaque octet stockant une ligne. Quand j’ai terminé, j’aimerais que chaque octet stocke une colonne.

Par exemple, quand j’ai fini:

 Byte0out = Byte0inBit0 + Byte1inBit0 + Byte2inBit0 + Byte3inBit0 + ... Byte1out = Byte0inBit1 + Byte1inBit1 + Byte2inBit1 + Byte3inBit1 + ... 

Quelle est la façon la plus simple de faire cela en C qui fonctionne bien?

Ce code est directement écrit dans “Hacker’s Delight” – Figure 7-2 Transposition d’une masortingce 8×8 bits , je n’en prends pas le crédit:

 void transpose8(unsigned char A[8], int m, int n, unsigned char B[8]) { unsigned x, y, t; // Load the array and pack it into x and y. x = (A[0]<<24) | (A[m]<<16) | (A[2*m]<<8) | A[3*m]; y = (A[4*m]<<24) | (A[5*m]<<16) | (A[6*m]<<8) | A[7*m]; t = (x ^ (x >> 7)) & 0x00AA00AA; x = x ^ t ^ (t << 7); t = (y ^ (y >> 7)) & 0x00AA00AA; y = y ^ t ^ (t << 7); t = (x ^ (x >>14)) & 0x0000CCCC; x = x ^ t ^ (t <<14); t = (y ^ (y >>14)) & 0x0000CCCC; y = y ^ t ^ (t <<14); t = (x & 0xF0F0F0F0) | ((y >> 4) & 0x0F0F0F0F); y = ((x << 4) & 0xF0F0F0F0) | (y & 0x0F0F0F0F); x = t; B[0]=x>>24; B[n]=x>>16; B[2*n]=x>>8; B[3*n]=x; B[4*n]=y>>24; B[5*n]=y>>16; B[6*n]=y>>8; B[7*n]=y; } 

Je n’ai pas vérifié si cela tournait dans la direction souhaitée, sinon vous auriez peut-être besoin d’ajuster le code.

Gardez également à l’esprit les types de données et les tailles – int & unsigned (int) peut ne pas être en 32 bits sur votre plate-forme.

BTW, je soupçonne que le livre (Hacker’s Delight) est essentiel pour le genre de travail que vous faites … vérifiez-le, il y a plein de choses géniales là-dedans.

Si vous recherchez la solution la plus simple:

 /* not tested, not even comstackd */ char bytes_in[8]; char bytes_out[8]; /* please fill bytes_in[] here with some pixel-crap */ memset(bytes_out, 0, 8); for(int i = 0; i < 8; i++) { for(int j = 0; j < 8; j++) { bytes_out[i] = (bytes_out[i] << 1) | ((bytes_in[j] >> (7 - i)) & 0x01); } } 

Si vous recherchez la solution la plus rapide:

Comment transposer une masortingce de bits dans l’assemblage en utilisant SSE2.

Prototype Lisp:

 (declaim (optimize (speed 3) (safety 0))) (defun bit-transpose (a) (declare (type (simple-array unsigned-byte 1) a)) (let ((b (make-array 8 :element-type '(unsigned-byte 8)))) (dotimes (j 8) (dotimes (i 8) (setf (ldb (byte 1 i) (aref bj)) (ldb (byte 1 j) (aref ai))))) b)) 

Voici comment vous pouvez exécuter le code:

 #+nil (bit-transpose (make-array 8 :element-type 'unsigned-byte :initial-contents '(1 2 3 4 5 6 7 8))) ;; => #(85 102 120 128 0 0 0 0) 

Parfois, je désassemble du code pour vérifier qu’il n’y a pas d’appels inutiles aux fonctions de sécurité.

 #+nil (disassemble #'bit-transpose) 

Ceci est une référence. Exécutez la fonction assez souvent pour traiter une image HDTV (binary).

 #+nil (time (let ((a (make-array 8 :element-type 'unsigned-byte :initial-contents '(1 2 3 4 5 6 7 8))) (b (make-array 8 :element-type 'unsigned-byte :initial-contents '(1 2 3 4 5 6 7 8)))) (dotimes (i (* (/ 1920 8) (/ 1080 8))) (bit-transpose a)))) 

Cela n’a pris que 51ms. Notez que je consum beaucoup, car la fonction alloue constamment de nouveaux tableaux de 8 octets. Je suis sûr qu’une implémentation en C peut être modifiée beaucoup plus.

 Evaluation took: 0.051 seconds of real time 0.052004 seconds of total run time (0.052004 user, 0.000000 system) 101.96% CPU 122,179,503 processor cycles 1,048,576 bytes consed 

Voici quelques autres cas de test:

 #+nil (loop for j below 12 collect (let ((l (loop for i below 8 collect (random 255)))) (list l (bit-transpose (make-array 8 :element-type 'unsigned-byte :initial-contents l))))) ;; => (((111 97 195 202 47 124 113 164) #(87 29 177 57 96 243 111 140)) ;; ((180 192 70 173 167 41 30 127) #(184 212 221 232 193 185 134 27)) ;; ((244 86 149 57 191 65 129 178) #(124 146 23 24 159 153 35 213)) ;; ((227 244 139 35 38 65 214 64) #(45 93 82 4 66 27 227 71)) ;; ((207 62 236 89 50 64 157 120) #(73 19 71 207 218 150 173 69)) ;; ((89 211 149 140 233 72 193 192) #(87 2 12 57 7 16 243 222)) ;; ((97 144 19 13 135 198 238 33) #(157 116 120 72 6 193 97 114)) ;; ((145 119 3 85 41 202 79 134) #(95 230 202 112 11 18 106 161)) ;; ((42 153 67 166 175 190 114 21) #(150 125 184 51 226 121 68 58)) ;; ((58 232 38 210 137 254 19 112) #(80 109 36 51 233 167 170 58)) ;; ((27 245 1 197 208 221 21 101) #(239 1 234 33 115 130 186 58)) ;; ((66 204 110 232 46 67 37 34) #(96 181 86 30 0 220 47 10))) 

Maintenant, je veux vraiment voir comment mon code se compare à la solution C d’Andrejs Cainikovs ( Edit: je pense que c’est faux ):

 #include  unsigned char bytes_in[8]={1,2,3,4,5,6,7,8}; unsigned char bytes_out[8]; /* please fill bytes_in[] here with some pixel-crap */ void bit_transpose(){ memset(bytes_out, 0, 8); int i,j; for(i = 0; i < 8; i++) for(j = 0; j < 8; j++) bytes_out[i] = (bytes_out[i] << 1) | ((bytes_in[j] >> (7 - i)) & 0x01); } int main() { int j,i; for(j=0;j<100;j++) for(i=0;i<(1920/8*1080/8);i++) bit_transpose(); return 0; } 

Et en le comparant:

 wg@hp:~/0803/so$ gcc -O3 trans.c wg@hp:~/0803/so$ time ./a.out real 0m0.249s user 0m0.232s sys 0m0.000s 

Chaque boucle sur l’image HDTV prend 2,5 ms. C'est beaucoup plus rapide que mon Lisp non optimisé.

Malheureusement, le code C ne donne pas les mêmes résultats que mon lisp:

 #include  int main() { int j,i; bit_transpose(); for(i=0;i<8;i++) printf("%d ",(int)bytes_out[i]); return 0; } wg@hp:~/0803/so$ ./a.out 0 0 0 0 1 30 102 170 

Cela ressemble beaucoup à une routine dite “Chunky to Planar” utilisée sur les écrans utilisant des plans bitmap. Le lien suivant utilise l’assembleur MC68K pour son code, mais fournit un bon aperçu du problème (en supposant que j’ai bien compris la question):

http://membres.multimania.fr/amycoders/sources/c2ptut.html

Vous voulez vraiment faire quelque chose comme ça avec les instructions SIMD avec quelque chose comme le support du vecteur vectoriel GCC: http://ds9a.nl/gcc-simd/example.html

Si vous vouliez une solution optimisée, vous utiliseriez les extensions SSE en x86. Vous devrez utiliser 4 de ces opcodes SIMD. MOVQ – move 8 octets PSLLW – mots logiques décalés à gauche empaquetés PMOVMSKB – octet de masque de déplacement empaquetés et 2 opcodes x86 normaux LEA – adresse effective de chargement MOV – move

 byte[] m = byte[8]; //input byte[] o = byte[8]; //output LEA ecx, [o] // ecx = the address of the output array/masortingx MOVQ xmm0, [m] // xmm0 = 0|0|0|0|0|0|0|0|m[7]|m[6]|m[5]|m[4]|m[3]|m[2]|m[1]|m[0] PMOVMSKB eax, xmm0 // eax = m[7][7]...m[0][7] the high bit of each byte MOV [ecx+7], al // o[7] is now the last column PSLLW xmm0, 1 // shift 1 bit to the left PMOVMSKB eax, xmm0 MOV [ecx+6], al PSLLW xmm0, 1 PMOVMSKB eax, xmm0 MOV [ecx+5], al PSLLW xmm0, 1 PMOVMSKB eax, xmm0 MOV [ecx+4], al PSLLW xmm0, 1 PMOVMSKB eax, xmm0 MOV [ecx+3], al PSLLW xmm0, 1 PMOVMSKB eax, xmm0 MOV [ecx+2], al PSLLW xmm0, 1 PMOVMSKB eax, xmm0 MOV [ecx+1], al PSLLW xmm0, 1 PMOVMSKB eax, xmm0 MOV [ecx], al 

25 opcodes / instructions x86 par opposition à la solution de boucles empilées pour … avec 64 itérations. Désolé, la notation n’est pas la syntaxe de style ATT acceptée par les compilateurs c / c ++.

Ceci est similaire à la colonne get dans un problème de tableau de bits et peut être résolu efficacement en considérant ces octets d’entrée comme 8 octets d’un entier de 64 bits. Si le bit 0 est le moins significatif et que l’octet 0 est le premier octet du tableau, je suppose que vous souhaitez effectuer les opérations suivantes.

 b07 b06 b05 b04 b03 b02 b01 b00 b70 b60 b50 b40 b30 b20 b10 b00 b17 b16 b15 b14 b13 b12 b11 b10 b71 b61 b51 b41 b31 b21 b11 b01 b27 b26 b25 b24 b23 b22 b21 b20 b72 b62 b52 b42 b32 b22 b12 b02 b37 b36 b35 b34 b33 b32 b31 b30 => b73 b63 b53 b43 b33 b23 b13 b03 b47 b46 b45 b44 b43 b42 b41 b40 => b74 b64 b54 b44 b34 b24 b14 b04 b57 b56 b55 b54 b53 b52 b51 b50 b75 b65 b55 b45 b35 b25 b15 b05 b67 b66 b65 b64 b63 b62 b61 b60 b76 b66 b56 b46 b36 b26 b16 b06 b77 b76 b75 b74 b73 b72 b71 b70 b77 b67 b57 b47 b37 b27 b17 b07 

avec bXY, le nombre de bits Y de l’octet X. Masquage des 7 premières colonnes et lecture du tableau sous la forme d’un uint64_t, nous aurons

 0000000h 0000000g 0000000f 0000000e 0000000d 0000000c 0000000b 0000000a 

dans little endian, avec abcdefgh sont respectivement b00 à b70. Il suffit maintenant de multiplier cette valeur par le nombre magique 0x2040810204081 pour obtenir une valeur avec hgfedcba dans le MSB, qui est la forme inversée du résultat.

 uint8_t get_byte(uint64_t masortingx, unsigned col) { const uint64_t column_mask = 0x8080808080808080ull; const uint64_t magic = 0x2040810204081ull; return ((masortingx << (7 - col)) & column_mask) * magic >> 56; } // You may need to change the endianness if you address the data in a different way uint64_t block8x8 = ((uint64_t)byte[7] << 56) | ((uint64_t)byte[6] << 48) | ((uint64_t)byte[5] << 40) | ((uint64_t)byte[4] << 32) | ((uint64_t)byte[3] << 24) | ((uint64_t)byte[2] << 16) | ((uint64_t)byte[1] << 8) | (uint64_t)byte[0]; for (int i = 0; i < 8; i++) byte_out[i] = get_byte(block8x8, i); 

En réalité, vous devriez lire directement dans un tableau de 8 octets pour ne pas avoir à combiner les octets plus tard, mais vous devez aligner le tableau correctement

Dans AVX2, Intel a introduit à cette fin l’ instruction PDEP (accessible via l’ _pext_u64 ) dans le jeu d’ instructions BMI2 afin que la fonction puisse être exécutée dans une seule instruction

 data[i] = _pext_u64(masortingx, column_mask << (7 - col)); 

Vous trouverez plus de moyens de transposer le tableau dans le wiki de programmation d'échecs.