Ouvrir le menu principal

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

< Les opérations bit à bit

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.

Sections

Inverser l'ordre des bitsModifier

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 nulsModifier

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 chaines de caractère. Les chaines 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 chaine est indiquée par un octet nul. Si traiter la chaine octet par octet, les bibliothèques standard préfèrent traiter la chaine mot par mot, ce qui est plus rapide. Pour identifier correctement la fin de la chaine, 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 branchementsModifier

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.

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

unsigned FindFirstZeroByte (unsigned word)
{
    unsigned b0 = (word & 0xFF) == 0 ;
    unsigned b1 = (word >> 8 & 0xFF) == 0 ;
    unsigned b2 = (word >> 16 & 0xFF) == 0 ;
    unsigned b3 = (word >> 24 & 0xFF) == 0 ;
    unsigned b4 = (word >> 32 & 0xFF) == 0 ;
    unsigned b5 = (word >> 40 & 0xFF) == 0 ;
    unsigned b6 = (word >> 48 & 0xFF) == 0 ;
    unsigned b7 = (word >> 56 & 0xFF) == 0 ;

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

On peut remplacer les masques précédents par les suivants, qui économisent quelques opérations :

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 (b7)
    {
        return 7 ;
    }
    else if (b6)
    {
        return 6 ;
    }
    else if (b5)
    {
        return 5 ;
    }
    else if (b4)
    {
        return 4 ;
    }
    else if (b3)
    {
        return 3 ;
    }
    else if (b2)
    {
        return 2 ;
    }
    else if (b1)
    {
        return 1 ;
    }
    else if (b0)
    {
        return 0 ;
    }
    else
    {
        return 8 ;
    }
}

Version avec prédicats et masquesModifier

Les conditions à la fin du code peuvent se remplacer par un calcul élémentaire. Pour cela, il suffit d'additionner les bits entre eux de manière à donner le résultat voulu. Si vous établissez la table de vérité du calcul, vous devriez trouver l'équation suivante :

 

Le code devient donc :

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 ;

    return b0 + (b0 & b1) + (b0 & b1 & b2) + (b0 & b1 & b2 & b3) ;
}

Ce code peut s'implémenter sans aucun branchement : il suffit que la comparaison avec zéro soit implémentée avec du code branch-free. Pour cela, il suffit d'utiliser le code pour le prédicat d'égalité, comme vu dans le chapitre précédent. Néanmoins, ce calcul est tout sauf optimal : il effectue chaque comparaison l'une après l'autre, alors que les calculs peuvent être faits en parallèle.

Calcul en parallèleModifier

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 :

 

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.

 

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) ;
}