Duplication de bits de 8 bits à 32 bits

Il n'y a que 256 valeurs 8 bits, donc une simple table de recherche occuperait 1 Ko, et la recherche est triviale. Il est difficile de croire que n'importe quel bithack aurait des performances supérieures.

Cela fonctionnerait:

unsigned int eToTW (unsigned char a) {     
    return (a & 1 << 7 ? ((unsigned) 0xf) << 28 : 0x0) | 
           (a & 1 << 6 ? 0xf << 24 : 0x0) | 
           (a & 1 << 5 ? 0xf << 20 : 0x0) | 
           (a & 1 << 4 ? 0xf << 16 : 0x0) | 
           (a & 1 << 3 ? 0xf << 12 : 0x0) |
           (a & 1 << 2 ? 0xf << 8 : 0x0) |
           (a & 1 << 1 ? 0xf << 4 : 0x0) |
           (a & 1 ? 0xf : 0x0);
}

ou ceci:

unsigned int eToTW (unsigned char a) {
    unsigned int output = 0;

    output |= a & (1 << 7) ? ((unsigned) 0xf) << 28 : 0x0;
    output |= a & (1 << 6) ? 0xf << 24 : 0x0;
    output |= a & (1 << 5) ? 0xf << 20 : 0x0;
    output |= a & (1 << 4) ? 0xf << 16 : 0x0;

    output |= a & (1 << 3) ? 0xf << 12 : 0x0;
    output |= a & (1 << 2) ? 0xf << 8 : 0x0;
    output |= a & (1 << 1) ? 0xf << 4 : 0x0;
    output |= a & 1 ? 0xf : 0x0;

    return output;
}

encore une autre solution:

unsigned int eToTW (unsigned char a) {
    unsigned int output = 0;

    output |= a & 0x80 ? ((unsigned) 0xf) << 28 : 0x0;
    output |= a & 0x40 ? 0xf << 24 : 0x0;
    output |= a & 0x20 ? 0xf << 20 : 0x0;
    output |= a & 0x10 ? 0xf << 16 : 0x0;

    output |= a & 0x8 ? 0xf << 12 : 0x0;
    output |= a & 0x4 ? 0xf << 8 : 0x0;
    output |= a & 0x2 ? 0xf << 4 : 0x0;
    output |= a & 0x1 ? 0xf : 0x0;

    return output;
}

Une table de recherche, comme suggéré dans la réponse de rici , fournira les meilleures performances sur la plupart des plates-formes. Si vous préférez une approche bidimensionnelle, la solution optimale dépendra des capacités matérielles de votre processeur, par ex. à quelle vitesse sont les décalages, a-t-il des opérations logiques à trois entrées (comme mon GPU), combien d'instructions entières peut-il exécuter en parallèle? Une solution consiste à transporter chaque bit vers le lsb de son quartet cible, puis à remplir chaque quartet avec sa valeur lsb dans un deuxième temps (un bout du chapeau à chqrlie pour suggérer l'utilisation de lsb au lieu de msb):

#include <stdint.h>
uint32_t expand_bits_to_nibbles_mul2 (uint8_t x)
{
    const uint32_t spread4 = (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    const uint32_t extract = (1u << (3*4+3+16)) | (1u << (2*4+2+16)) | 
                             (1u << (1*4+1+16)) | (1u << (0*4+0+16)) |
                             (1u << (3*4+3+ 0)) | (1u << (2*4+2+ 0)) | 
                             (1u << (1*4+1+ 0)) | (1u << (0*4+0+ 0));
    const uint32_t nib_lsb = (1u << 28) | (1u << 24) | (1u << 20) | (1u << 16) |
                             (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    const uint32_t nib_msb = (nib_lsb << 3);
    const uint8_t bits_lo4 = (1u <<  3) | (1u <<  2) | (1u <<  1) | (1u <<  0);
    const uint8_t bits_hi4 = (1u <<  7) | (1u <<  6) | (1u <<  5) | (1u <<  4);
    uint32_t r;
    /* spread bits to their target nibbles */
    r = (((uint32_t)(x & bits_lo4) * (spread4 <<  0)) +  
         ((uint32_t)(x & bits_hi4) * (spread4 << 12)));
    /* extract appropriate bit in each nibble and move it into nibble's lsb */
    r = (((r & extract) + (nib_msb - extract)) >> 3) & nib_lsb;
    /* fill in each nibble with its lsb */
    r = (r << 4) - r;
    return r;
}

Quelques expériences rapides avec Compiler Explorer montrent que cela conduit à un code particulièrement efficace sur PowerPC64, par exemple.

Si le processeur a un multiplicateur d'entiers rapide, nous pourrions utiliser pour déplacer plusieurs bits en place en même temps. Ici, nous voudrions utiliser des groupes de trois bits source pour éviter les collisions:

#include <stdint.h>
uint32_t expand_bits_to_nibbles_mul (uint8_t x)
{
    const uint32_t spread3 = (1u <<  6) | (1u <<  3) | (1u <<  0);
    const uint8_t bits_lo3 = (1u <<  2) | (1u <<  1) | (1u <<  0);
    const uint8_t bits_md3 = (1u <<  5) | (1u <<  4) | (1u <<  3);
    const uint8_t bits_hi2 = (1u <<  7) | (1u <<  6);
    const uint32_t nib_lsb = (1u << 28) | (1u << 24) | (1u << 20) | (1u << 16) | 
                             (1u << 12) | (1u <<  8) | (1u <<  4) | (1u <<  0);
    uint32_t r;
    /* spread bits to lsb in each nibble */
    r = (((uint32_t)(x & bits_lo3) * (spread3 <<  0)) +
         ((uint32_t)(x & bits_md3) * (spread3 <<  9)) +
         ((uint32_t)(x & bits_hi2) * (spread3 << 18))) & nib_lsb;
    /* fill in nibbles */
    r = (r << 4) - r;
    return r;
}

Une autre variante utilisant la multiplication d'entiers, qui est potentiellement plus rapide sur certaines plates-formes, utilise une idée de cette réponse . Nous utilisons une multiplication pour étaler quatre bits à la fois, de sorte qu'ils atterrissent dans leur grignotage cible. Cependant, nous devons ensuite déplacer le bit dans le quartet vers le lsb du quartet avant de pouvoir étendre le lsb pour couvrir le quartet. Nous économisons potentiellement une multiplication au détriment de l'entretien ménager supplémentaire.

#include <stdint.h>
uint32_t expand_bits_to_nibbles (uint8_t x)
{
    uint32_t r;
    /* spread bits to lsb in each nibble */
    r = ((((uint32_t)x << (4*0-0)) & (1u << (4*0))) |
         (((uint32_t)x << (4*1-1)) & (1u << (4*1))) |
         (((uint32_t)x << (4*2-2)) & (1u << (4*2))) |
         (((uint32_t)x << (4*3-3)) & (1u << (4*3))) |
         (((uint32_t)x << (4*4-4)) & (1u << (4*4))) |
         (((uint32_t)x << (4*5-5)) & (1u << (4*5))) |
         (((uint32_t)x << (4*6-6)) & (1u << (4*6))) |
         (((uint32_t)x << (4*7-7)) & (1u << (4*7))));
    /* fill in nibbles */
    r = (r << 4) - r;
    return r;
}

C'est simple - résolvez le cas le plus simple, puis faites-en des plus complexes.

Cas 1: Dupliquer 1 bit en une valeur de 4 bits (le plus simple).

TEST_F(test, interleave)
{
    EXPECT_EQ(interleave(0x00), 0x00000000);
    EXPECT_EQ(interleave(0x11), 0x000F000F);
    EXPECT_EQ(interleave(0x22), 0x00F000F0);
    EXPECT_EQ(interleave(0x33), 0x00FF00FF);
    EXPECT_EQ(interleave(0x44), 0x0F000F00);
    EXPECT_EQ(interleave(0x55), 0x0F0F0F0F);
    EXPECT_EQ(interleave(0x66), 0x0FF00FF0);
    EXPECT_EQ(interleave(0x77), 0x0FFF0FFF);
    EXPECT_EQ(interleave(0x88), 0xF000F000);
    EXPECT_EQ(interleave(0x99), 0xF00FF00F);
    EXPECT_EQ(interleave(0xAA), 0xF0F0F0F0);
    EXPECT_EQ(interleave(0xBB), 0xF0FFF0FF);
    EXPECT_EQ(interleave(0xCC), 0xFF00FF00);
    EXPECT_EQ(interleave(0xDD), 0xFF0FFF0F);
    EXPECT_EQ(interleave(0xEE), 0xFFF0FFF0);
    EXPECT_EQ(interleave(0xFF), 0xFFFFFFFF);

    EXPECT_EQ(interleave(0x01), 0x0000000F);
    EXPECT_EQ(interleave(0x23), 0x00F000FF);
    EXPECT_EQ(interleave(0x45), 0x0F000F0F);
    EXPECT_EQ(interleave(0x67), 0x0FF00FFF);
    EXPECT_EQ(interleave(0x89), 0xF000F00F);
    EXPECT_EQ(interleave(0xAB), 0xF0F0F0FF);
    EXPECT_EQ(interleave(0xCD), 0xFF00FF0F);
    EXPECT_EQ(interleave(0xEF), 0xFFF0FFFF);
}

Cela peut être fait comme un simple ensemble de décalages:

uint32_t interleave(uint8_t value)
{
    uint32_t x = value;
    x = (x | (x << 12)) /* & 0x000F000F */; // GCC is not able to remove redundant & here
    x = (x | (x <<  6)) & 0x03030303;
    x = (x | (x <<  3)) & 0x11111111;
    x = (x << 4) - x;
    return x;
}

Ou d'une manière moins évidente mais plus rapide:

+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 0 | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D | E F G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 1 | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D | _ _ _ _ | _ _ _ _ | _ _ _ _ | E F G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 2 | _ _ _ _ | _ _ A B | _ _ _ _ | _ _ C D | _ _ _ _ | _ _ E F | _ _ _ _ | _ _ G H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 3 | _ _ _ A | _ _ _ B | _ _ _ C | _ _ _ D | _ _ _ E | _ _ _ F | _ _ _ G | _ _ _ H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+
| 4 | A A A A | B B B B | C C C C | D D D D | E E E E | F F F F | G G G G | H H H H |
+---+---------+---------+---------+---------+---------+---------+---------+---------+

Cette étape sera la dernière dans tous les cas suivants.

Cas 2: Dupliquer 2 bits en une valeur de 8 bits.

+---+---------+---------+---------+---------+
| 0 | _ _ _ _ | _ _ _ _ | _ _ _ _ | A B C D |
+---+---------+---------+---------+---------+
| 1 | _ _ _ _ | _ _ A B | _ _ _ _ | _ _ C D |
+---+---------+---------+---------+---------+
| 2 | _ _ _ A | _ _ _ B | _ _ _ C | _ _ _ D |
+---+---------+---------+---------+---------+
| 3 | A A A A | B B B B | C C C C | D D D D |
+---+---------+---------+---------+---------+

Cas 3: Dupliquez 4 bits en une valeur de 16 bits. Comment? Déplacez simplement 2 bits vers la partie supérieure pour en faire le boîtier 1! Divisez et conquérez!

+---+---------+---------+
| 0 | _ _ _ _ | _ _ A B |
+---+---------+---------+
| 1 | _ _ _ A | _ _ _ B |
+---+---------+---------+
| 2 | A A A A | B B B B |
+---+---------+---------+

Cas 4: Dupliquer 8 bits en une valeur 32 bits (l'original).

x = (x << 4) - x;

Peut être réalisé par le code ci-dessous:

x = (x << 0) | (x << 1) | (x << 2) | (x << 3);

Quelques cas de test pour vérifier que cela fonctionne:

+---+---------+
| 0 | _ _ _ A |
+---+---------+
| 1 | A A A A |
+---+---------+