Les opérations bit à bit/Manipulations intra-mots

Dans cette section, nous allons voir des manipulations qui modifient ou travaillent à l'intérieur d'un mot/d'une variable/d'un registre. Nous allons voir comment échanger deux portions à l'intérieur d'un mot, comment inverser les bits d'un mot, détecter les octets nuls, et bien d'autres.

Inverser l'ordre des bits

Inverser l'ordre des bits d'un nombre est une opération qui est assez peu courante. Cependant, elle peut être très utile dans certains algorithmes, comme ceux qui impliquent des transformées de Fourier. Pour inverser les bits d'un nombre, il suffit d'inverser les bits en position paire et impaire, puis inverser les groupes de deux bits adjacents, puis des groupes de 4 bits, et ainsi de suite jusqu’à obtenir le bon résultat. Pour cela, on peut réutiliser les masques du calcul de la population count pour sélectionner les bits/groupes de bits, et de faire quelques décalages. Le code obtenu devrait être celui-ci pour des entiers de 32 bits :

unsigned BitReverse (unsigned x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1 ;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2 ;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4 ;
    x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8 ;
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16 ;

    return x ;
}

Les deux dernières lignes peuvent être remplacées par une seule ligne de code, qui fait l'échange entre quatre groupes de bits.

unsigned BitReverse (unsigned x)
{
    x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1 ;
    x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2 ;
    x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >> 4 ;
    x = x << 24 | (x & FF00) << 8 | ( (x >> 8) & 0xFF00 ) | x >> 24 ;

    return x ;
}

Identification des octets nuls

Dans cette section, nous allons voir comment détecter les octets nuls dans un mot/registre (pour rappel, un mot est un groupe de plusieurs octets et/ou bytes qui a la taille d'un registre). Cet algorithme est très utilisé dans des langages comme le C, notamment dans leur bibliothèque standard, pour utiliser les chaînes de caractère. Les chaînes de caractères du C sont stockées sous la forme d'un tableau d'octets, chaque octet codant un caractère et la fin de la chaîne est indiquée par un octet nul. Au lieu de traiter la chaîne octet par octet, les bibliothèques standard préfèrent traiter la chaîne mot par mot, ce qui est plus rapide. Pour identifier correctement la fin de la chaîne, les algorithmes utilisés doivent donc déterminer si un octet est nul dans un mot. Mais cet algorithme peut avoir d'autres utilisations, que nous ne détaillerons pas ici. Par exemple, ce code peut servir à savoir si un mot contient un octet égal à x (et non à 0). Pour cela, il suffit de faire un XOR entre chaque octet et la valeur x. Si les deux octets sont égaux et seulement si c'est le cas, l'octet sera mis à 0. On peut ensuite utiliser le code qui détermine si un octet est nul.

Version avec branchements

Dans ce qui va suivre, chaque octet sera noté de 0 à n-1 pour un mot de n octets, avec 0 l'octet de poids faible et n-1 l'octet de poids fort. L'algorithme que nous allons voir renvoie un nombre qui indique la position du premier octet nul. La valeur renvoyée est égale à n si aucun octet n'est nul dans le mot. Pour les exemples qui vont suivre, nous allons prendre un mot de 64 bits, qui a donc 8 octets numérotés de 0 à 7. Cet algorithme va commencer par calculer un booléen/bit pour chaque octet, qui indique s'il est nul ou non : il vaut 0 s'il est nul et 1 sinon. Il va ensuite combiner ces booléens/bits pour déterminer la valeur de retour.

Le code utilisé dans ce chapitre suppose que l'ordre des octets est little endian où l'octet de poids faible du mot se situe en premier dans la séquence d'octet le représentant en mémoire. Pour l'ordre big endian, il suffit de changer l'ordre des noms de variables dans le code.

La version qui utilise des branchements va masquer chaque octet et tester si celui-ci est nul :

unsigned FindFirstZeroByte (unsigned word)
{
    unsigned b0 = (word & 0xFF) == 0 ;
    unsigned b1 = (word & 0xFF00) == 0 ;
    unsigned b2 = (word & 0xFF0000) == 0 ;
    unsigned b3 = (word & 0xFF000000) == 0 ;
    unsigned b4 = (word & 0xFF00000000) == 0 ;
    unsigned b5 = (word & 0xFF0000000000) == 0 ;
    unsigned b6 = (word & 0xFF000000000000) == 0 ;
    unsigned b7 = (word & 0xFF00000000000000) == 0 ;

    if (b0)
    {
        return 0 ;
    }
    else if (b1)
    {
        return 1 ;
    }
    else if (b2)
    {
        return 2 ;
    }
    else if (b3)
    {
        return 3 ;
    }
    else if (b4)
    {
        return 4 ;
    }
    else if (b5)
    {
        return 5 ;
    }
    else if (b6)
    {
        return 6 ;
    }
    else if (b7)
    {
        return 7 ;
    }
    else
    {
        return 8 ;
    }
}

Calcul en parallèle

Pour faire le calcul plus rapidement, il faut effectuer toutes les comparaisons en même temps, en utilisant des opérations bit à bit et des calculs arithmétiques. Le calcul que nous allons voir utilise ce principe. Il va placer les bits b0, b1, ..., b7, dans le bit de poids fort de chaque octet, comme le font les prédicats de comparaison. Ainsi, ce calcul va remplacer tous les octets nuls par 0xxx xxxx et tous les bytes non nuls par 1xxx xxx. Une solution qui marche pour les octets inférieurs à 1000 000 est d'additionner 0111 111 : en faisant cela, tous les octets nuls deviendront 0111 1111 alors que les octets non-nuls dépasseront 0111 1111. Ces derniers deviendront donc des octets de la forme 1xxx xxxx. Mais comme dit plus haut, cela ne fonctionne que pour les octets inférieurs à 1000 0000. Le problème avec ces octets est que le résultat déborde de l'octet, modifiant les résultats des autres octets. Pour faire l'addition correctement, il faut donc mettre à 0 le bit de poids fort de chaque octet pour éviter le débordement. Pour mettre le bit de poids fort à 0, il faut faire un masque avec 0x7F. Enfin, il faut additionner 0x7F (0111 1111). Le calcul effectué sur tous les octets en même temps est donc :

$x=(x.0x7F7F7F7F)+0x7F7F7F7F$

Pour prendre en compte les octets supérieurs à 1000 0000, il faut simplement faire un OU entre le résultat précédent et l'octet en question. Comme cela, si l'octet dépasse 1000 0000, le bit de poids fort du résultat sera mis à 1. Ce qui corrige le résultat précédent.

$x=((x.0x7F7F7F7F)+0x7F7F7F7F)|x$

Le code devient donc :

unsigned FindFirstZeroByte (unsigned x)
{
    unsigned word = x = ( (x & 0x7F7F7F7F) + 0x7F7F7F7F ) | x ;

    unsigned b0 = word >> 7 ;
    unsigned b1 = word >> 15 ;
    unsigned b2 = word >> 23 ;
    unsigned b3 = word >> 31 ;
    unsigned b4 = word >> 39 ;
    unsigned b5 = word >> 47 ;
    unsigned b6 = word >> 55 ;
    unsigned b7 = word >> 63 ;

    /* return b0 + (b0 & b1) + (b0 & b1 & b2) + (b0 & b1 & b2 & b3) ; */
    return b0 ? 0 : b1 ? 1 : b2 ? 2 : b3 ? 3 : b4 ? 4 : b5 ? 5 : b6 ? 6 : b7 ? 7 : 8;
}