Réordonner peu

Question

Je dois faire une réorganisation arbitraire d'une valeur de 7 bits (oui, je sais que je devrais utiliser une table) et je me demande s'il existe des bidouilles pour le faire.

Exemple:

// <b0, b1, b2, b3, b4, b5, b6> -> <b3, b2, b4, b1, b5, b0, b6>

// the naive way
out =
   (0x020 & In) << 5 |
   (0x008 & In) << 2 |
   (0x040 & In)      |
   (0x012 & In) >> 1 |
   (0x004 & In) >> 2 |
   (0x001 & In) >> 3;

// 6 ANDs, 5 ORs, 5 shifts = 16 ops

modifier: Je pensais à quelque chose dans le genre de this

Juste pour le plaisir et parce que j’étais AFTK, je cherche une solution brutale pour trouver des solutions de la forme:

((In * C1) >> C2) & 0x7f

Aucune solution trouvée.

Answer 1

Consultez la sortie du compilateur de votre "naïf". code, cela pourrait vous surprendre. Une fois, j’ai fait quelque chose comme ça et le compilateur (VC ++ 2005) a complètement changé les valeurs de tous les ands et décalages pour les rendre plus efficaces, par exemple, je suis sûr que cela effacerait votre " (0x001 & In). > > 3 ".

Mais oui, si le remaniement est une fonction fixe, une table est probablement préférable.

Mettre à jour

Pour rire, j’ai jeté un œil à la sortie du compilateur de VC ++ 2005 ....

J'ai d'abord essayé une valeur constante pour " Dans " mais le compilateur n'a pas été dupe, il a généré ce code:

mov eax,469h

c'est à dire. complètement optimisé.

Alors ... j'ai essayé une entrée correcte et j'ai obtenu ceci:

00401D4F  mov         eax,ecx 
00401D51  and         eax,20h 
00401D54  shl         eax,3 
00401D57  mov         edx,ecx 
00401D59  and         edx,8 
00401D5C  or          eax,edx 
00401D5E  mov         edx,ecx 
00401D60  sar         edx,1 
00401D62  and         edx,2 
00401D65  or          edx,ecx 
00401D67  sar         edx,1 
00401D69  shl         eax,2 
00401D6C  and         edx,9 
00401D6F  or          eax,edx 
00401D71  and         ecx,40h 
00401D74  or          eax,ecx 

Cela fait quatre équipes, cinq ET / OU, quatre OR - pas mal pour six entrées. Probablement mieux que la plupart des gens pourraient le faire à la main.

Il est probablement également optimisé pour une exécution dans le désordre, donc il y aura moins de cycles d'horloge qu'il n'y parait. : -)

Answer 2

La première étape semble consister à comprendre une solution mathématique et à l’optimiser.

voir ici le piratage de bits

Answer 3

Il existe de nombreuses méthodes de bidouillage pour les opérations courantes, c’est-à-dire pour inverser l’ordre des bits dans un mot de 32 bits (10 décales, ET et OU, AFAICR).

Dans ce cas, avec un mappage apparemment complètement arbitraire d'une entrée à l'autre, je ne vois aucun moyen de la nettoyer.

Utilisez une table de recherche:)

Answer 4

Avant d’optimiser, assurez-vous que votre méthode "naïve" correspond à vos intentions. Si je transforme votre code en une fonction et exécute cette boucle:

for (b=0;b<7;b++)
{
    i=1<<b;
    printf("%d: %02x -> %02x\n", b, i, shuffle(i));
}

Il produit cette sortie qui contredit les commentaires. En fait, il perd des bits.

0: 01 -> 00
1: 02 -> 01
2: 04 -> 01
3: 08 -> 20
4: 10 -> 08
5: 20 -> 00
6: 40 -> 40

Pour obtenir le mélange que vous décrivez, je le coderais comme suit:

   //    0 1 2 3 4 5 6 
   //-> 3 2 4 1 5 0 6
   (0x001 & In) << 3 |
   (0x004 & In) << 2 |
   (0x020 & In)      |
   (0x012 & In) << 1 |
   (0x008 & In) >> 2 |
   (0x020 & In) >> 5 ;