Comment obtenir des sommes de contrôle pour les modèles striés

Question

J'ai un nombre de 64 bits (mais seuls les 42 bits de poids faible sont utilisés) et je dois calculer la somme des 4 bits à n, n+m, n+m*2 et n+m*3 (note:tout ce qui peut produire une somme > 4 n'est pas valide) pour un m fixe et chaque valeur de n qui place tous les bits dans le nombre

à titre d'exemple en utilisant m=3 et étant donné le nombre de 16 bits

0010 1011 0110 0001

j'ai besoin de calculer

2, 3, 1, 2, 3, 0, 3

Quelqu'un a-t-il des idées (cool) sur la manière de procéder ?Je suis d'accord avec un peu de bidouillage.

---

Ma pensée actuelle est de faire des copies décalées de l'entrée pour aligner les valeurs à additionner, puis de construire une arborescence logique pour créer un additionneur 4x 1 bit.

v1 = In;
v2 = In<<3;
v3 = In<<6;
v4 = In<<9;

a1 = v1 ^ v2;
a2 = v1 & v2;
b1 = v3 ^ v4;
b2 = v3 & v4;
c2 = a1 & b1;
d2 = a2 ^ b2;

o1 = a1 ^ b1;
o2 = c2 ^ d2;
o4 = a2 & b2;

Cela se termine avec des bits du résultat répartis sur 3 entiers différents, mais bon.

modifier:en fait, j'ai besoin de l'histogramme des sommes, donc je fais un nombre de bits de o4, o2&o1, o2 et o1 me donne ce que je veux.

---

une deuxième solution utilise une fonction de hachage parfaite

arr = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];

for(int i = 0; i < N; i++)
{
   out[i] = arr[(In & 0b1001001001) % 30]; 
   In >>= 1;
}

Cela fonctionne en notant que les 4 bits sélectionnés ne peuvent prendre que 16 modèles et que (en devinant et en vérifiant) ils peuvent être hachés en 0-15 en utilisant le mod 30.A partir de là, un tableau de valeurs calculées donne la somme nécessaire.En fait, seules 3 des 4 foulées dont j'ai besoin fonctionnent de cette façon.

---

p.s.

La correction l'emporte rapidement.Le rapide l’emporte clairement.Je m'attends à exécuter cela des millions de fois.

Answer 1

Peut-être que je suis fou, mais je m'amuse: D Cette solution est basée sur l'utilisation du parallélisme des données et simulant un processeur vectoriel sans utiliser vraiment l'intrinssique SSE ou quelque chose de similaire.

unsigned short out[64];
const unsigned long long mask      = 0x0249024902490249ul;
const unsigned long long shiftmask = 0x0001000100010001ul;

unsigned long long t = (unsigned short)(in >> 38) | (unsigned long long)(unsigned short)(in >> 39) > 40) > 41) << 48;
t &= mask;
*((unsigned long long*)(out + 38)) = (t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask);

[... snipsnap ...]

t = (unsigned short)(in >> 2) | (unsigned long long)(unsigned short)(in >> 3) > 4) > 5) << 48;
t &= mask;
*((unsigned long long*)(out + 2)) = (t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask);

t = (unsigned short)in | (unsigned long long)(unsigned short)(in >> 1) << 16;
t &= mask;
*((unsigned int*)out) = (unsigned int)((t & shiftmask) + (t >> 3 & shiftmask) + (t >> 6 & shiftmask) + (t >> 9 & shiftmask));

---

En réorganisant les calculs, nous pouvons réduire encore davantage le temps d'exécution, car cela réduit considérablement le nombre de fois où quelque chose est chargé dans le QWORD.Quelques autres optimisations sont assez évidentes et plutôt mineures, mais résument une autre accélération intéressante.

unsigned short out[64];
const unsigned long long Xmask = 0x249024902490249ull;
const unsigned long long Ymask = 0x7000700070007u;

unsigned long long x = (in >> 14 & 0xFFFFu) | (in >> 20 & 0xFFFFu) > 26 & 0xFFFFu) > 32) << 48;
unsigned long long y;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[32] = (unsigned short)(y >> 48);
out[26] = (unsigned short)(y >> 32);
out[20] = (unsigned short)(y >> 16);
out[14] = (unsigned short)(y      );

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[33] = (unsigned short)(y >> 48);
out[27] = (unsigned short)(y >> 32);
out[21] = (unsigned short)(y >> 16);
out[15] = (unsigned short)(y      );

[snisnap]

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[37] = (unsigned short)(y >> 48);
out[31] = (unsigned short)(y >> 32);
out[25] = (unsigned short)(y >> 16);
out[19] = (unsigned short)(y      );

x >>= 1;
x &= 0xFFFF000000000000ul;
x |= (in & 0xFFFFu) | (in >> 5 & 0xFFFFu) > 10 & 0xFFFFu) << 32;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[38] = (unsigned short)(y >> 48);
out[10] = (unsigned short)(y >> 32);
out[ 5] = (unsigned short)(y >> 16);
out[ 0] = (unsigned short)(y      );

[snipsnap]

x >>= 1;
y = x & Xmask;
y += y >> 6;
y += y >> 3;
y &= Ymask;
out[ 9] = (unsigned short)(y >> 16);
out[ 4] = (unsigned short)(y      );

Temps d'exécution pour 50 millions d'exécutions en C++ natif (toutes les sorties vérifiées pour correspondre ^^) compilées en binaire 64 bits sur mon PC :
Solution basée sur un tableau :~5700 ms
Solution naïve codée en dur :~4200 ms
La première solution :~2400 ms
La deuxième solution :~1600 ms

Answer 2

Une suggestion que je ne veux pas coder pour le moment est d'utiliser une boucle, un tableau pour contenir des résultats partiels et des constantes pour récupérer les bits m à la fois.

loop 
   s[3*i] += x & (1 << 0);
   s[3*i+1] += x & (1 << 1);
   s[3*i+2] += x & (1 << 2);
   x >> 3;

Cela sélectionnera trop de bits dans chaque somme.Mais vous pouvez également suivre les résultats intermédiaires et soustraire les sommes au fur et à mesure, pour tenir compte de la partie qui n'est peut-être plus là.

loop 
   s[3*i] += p[3*i]   = x & (1 << 0);
   s[3*i+1] += p[3*i+1] = x & (1 << 1);
   s[3*i+2] += p[3*i+2] = x & (1 << 2);

   s[3*i] -= p[3*i-10];
   s[3*i+1] -= p[3*i-9];
   s[3*i+2] -= p[3*i-8];
   x >> 3;

avec la vérification des limites appropriées, bien sûr.

L’approche la plus rapide consiste simplement à coder en dur les sommes elles-mêmes.

s[0] = (x & (1<<0)) + (x & (1<<3)) + (x & (1<<6)) + (x & (1<<9));

etc.(Les changements se produisent au moment de la compilation.)