Les opérations bit à bit/Les débordements de puissance de deux

Dans cette section, nous allons aborder les opérations qui font intervenir des nombres de la forme $2^{n}$ et $2^{n}-1$. Vous pouvez vous demander pourquoi un chapitre sur les opérations avec les puissances de deux, et pas sur les puissances de 3, 4, 5 ou autres. Le fait est qu'en binaire, les puissances de deux ont un rôle tout particulier à jouer, en lien avec le fait que le binaire est la base 2. En binaire, les puissances de deux ont un rôle équivalent à celui des puissances de 10 en décimal. Dans la numération décimale de tous les jours, les nombres comme 10, 100, 1000 sont particuliers. Certaines opérations sont drastiquement plus simples avec des nombres qu'avec les autres : pensez notamment aux divisions et multiplications par 10 ! En binaire, c'est la même chose avec les puissances de deux.

En théorie, nous aurions dû commencer par voir les multiplications et divisions par une puissance de deux, qui peuvent se remplacer par des décalages. Mais nous avons vu tout ce qu'il a à savoir sur le sujet dans les chapitres précédents. Aussi, nous allons directement commencer par voir une astuce très utile pour gérer ce qui s'appelle les accès mémoire non-alignés. Nous allons ensuite passer du temps sur une opération assez simple, qui permet de calculer la puissance de $2^{n}$ qui est immédiatement supérieure à un nombre $x$ donné. Cette opération est à la base de calculs arithmétiques ou logiques plus complexes, comme le calcul du logarithme d'un nombre entier.

Détection d'un débordement de puissance de deux

Comme vous le savez peut-être, certaines architectures demandent aux accès mémoire de respecter des contraintes d'alignement. Pour rappel, la mémoire est alors découpée en blocs dont la taille est égale à la largeur du bus de données. Quand on accède à une donnée, il est préférable que celle-ci soit intégralement contenue dans un bloc : l'accès mémoire est alors dit aligné. Mais si la donnée est à cheval sur deux blocs, l'accès mémoire est dit non-aligné et cela peut poser problème. Si certaines architectures gèrent parfaitement les accès non-alignés, d'autres ne permettent pas de tels accès. Pour diverses raisons, il est possible pour un programmeur de détecter si un accès mémoire sera ou non aligné.

Un problème similaire apparait lorsque l'on doit charger une donnée depuis la mémoire RAM, sur les systèmes à mémoire virtuelle. Cette fois-ci, la mémoire virtuelle divise la RAM en pages, les données pouvant être à cheval sur deux pages. Détecter de tels chevauchements est alors une nécessité pour le système d’exploitation. Il se trouve qu'aussi bien la taille des pages que la largeur des blocs de RAM alignés sont des puissances de deux.

Gérer les accès non-alignés demande donc de détecter quand une donnée est à cheval entre deux blocs. Détecter les accès non-alignés est primordial et, fort heureusement, se fait avec quelques calculs particulièrement simples. Pour cela, il existe plusieurs solutions différentes.

La méthode avec des divisions

L'adresse $A$ peut se calculer à partir d'autres paramètres, comme la taille des blocs. Déjà, il faut savoir que chaque bloc a une taille qui s'exprime en bytes. Avec un système d'alignement ou de page, chaque bloc est numéroté en partant de zéro, ce numéro étant l'équivalent de l'adresse pour les bytes. L'adresse d'un bloc est par convention l'adresse du premier byte du bloc, celui dont l'adresse est la plus basse. Elle se calcule donc en multipliant le numéro du bloc par sa taille. Une donnée à l'intérieur d'un bloc est généralement localisée à une certaine distance de l'adresse de base, elle est placée quelques bytes plus loin que la base du bloc. Dit autrement, l'adresse $A$ d'une donnée s'écrit comme suit :

$A=N\times T+P$, avec $T$ la taille d'un bloc, $N$ le numéro du bloc et $P$ la position de la donnée par rapport à l'adresse de base du bloc.

Pages et blocs ont une taille qui est presque toujours une puissance de deux, ce qui est une norme tacite. Ce qui fait que l'on a :

$A=N\times 2^{n}+P$

L'adresse de $A+L$ s'écrit de la même manière, sauf que le numéro du bloc et la position dans le bloc sont potentiellement différents.

Notons que l'on peut trouver N et P à partir de A assez simplement. Il suffit en effet de diviser A par $2^{n}$ : N sera alors le quotient et P sera le reste de la division. Et c'est très utile pour détecter un accès non-aligné. Il suffit de diviser $A$ et $A+L$ par $2^{n}$, et de comparer les numéro de bloc obtenus. Si les deux numéros de bloc sont identiques, cela signifie que la donnée est toute entière dans le même bloc. Par contre, si les deux sont différents, cela signifie que le début de la donnée à l'adresse $A$ est dans un bloc, mais que la fin de la donnée $A+L$ est dans un autre bloc : il y a donc débordement.

Notons que faire la division en question demande juste de faire un décalage vers la droite, du moins sous condition que la taille du bloc soit une puissance de deux. C'est d'ailleurs une des raisons pour lesquelles les blocs/pages ont une taille égale à une puissance de deux. Faire ainsi simplifie de nombreux calculs d'adresse et permet des simplifications assez utiles.

La méthode avec le modulo

Il existe une seconde méthode qui une logique très simple. La donnée à charger commence à une adresse que nous noterons $A$ et a une longueur $L$. Un débordement de page/bloc a lieu quand il existe un multiple de $2^{n}$ entre $A$ et $A+L$. Cela traduit le fait que la donnée commence dans un premier bloc, atteint la limite du bloc (donc, une adresse multiple de $2^{n}$) et se poursuit au-delà. Reste à voir comment les opérations bit à bit nous aident pour détecter une telle situation.

Rappelons que l'on a :

$A=N\times 2^{n}+P_{0}$

Un débordement a lieu si, en ajoutant $L$, on passe au multiple de $2^{n}$ suivant. En clair, un débordement a lieu si :

$A+L=(N+1)\times 2^{n}+P_{1}$, avec $P_{1}\geq 0$

Soustrayons la première équation de la seconde :

$(A+L)-A=\left[(N+1)\times 2^{n}+r_{2}\right]-\left[N\times 2^{n}+P_{0}\right]$

Réorganisons les termes :

$L=\left[(N+1)\times 2^{n}-N\times 2^{n}\right]+\left[P_{1}-P_{0}\right]$

Simplifions :

$L=2^{n}+P_{1}-P_{0}$

Ajoutons $r_{0}$ des deux cotés :

$L+P_{0}=2^{n}+P_{1}$, avec, rappelons-le, $r_{2}\geq 0$

Pour le reformuler, le débordement implique que $P_{1}\geq 0$, ce qui implique que l'équation précédente est équivalente à l'inégalité suivante :

$L+P_{0}>2^{n}$

L'équation précédente dit que si la longueur dépasse ce qu'il manque à l'adresse pour atteindre le prochain multiple de $2^{n}$, alors c'est un débordement.

Sachant que le reste vaut par définition $P_{0}=A\mod 2^{n}$, on a :

$(A\mod 2^{n})+L\geq 2^{n}$

La méthode avec débordement d'entier

Une seconde méthode effectue un calcul similaire, si ce n'est que la comparaison est remplacée par un débordement d'entier. Le principe est très simple et se contente de remplacer l'adresse par le multiple de $2^{n}$ le plus grand possible qui soit adressable. Prenons par exemple une mémoire de 2^32 adresses, adressée par des adresses de 32 bits, découpée en page de 4096 octets. On suppose aussi que la machine travaille sur les mots/registres de 32 bits, comme les adresses. Sur 32 bits, l'adresse la plus grande qui soit multiple de 4096 est de 4294963200. Si à cette adresse on ajoute $L+A\mod 2^{n}$, un débordement se produit si $L+A\%2^{n}>4096$. En clair, le débordement d'entier traduit un débordement de page. On détecte donc un débordement de page si :

$4294963200+L+(A\%4096)>2^{32}$

Il se trouve que le calcul de $4294963200+(A\%4096)$ peut se réaliser sans faire l'addition. En effet, 4294963200 a déjà ses 12 bits de poids faible à 0. Tout ce qu'il faut faire est de remplacer les bits de poids forts de l'adresse par des 1, sans toucher aux bits sélectionnés par le modulo. L'application d'un masque est alors obligatoire, ce qui donne le code suivant :

$(A|4294963200)+L>2^{32}$

Ou encore :

$(A|-4096)+L>2^{32}$

On peut bien sûr généraliser les résultats précédents à toute autre valeur. Pour des adresses de $n$ bits et des pages/blocs de $m$ octets, on a :

$(A|-m)+L>2^{n}$

Le calcul du nombre de la forme $2^{n}$ immédiatement supérieur

Supposons que je veuille arrondir un nombre à puissance de deux immédiatement supérieure. Par exemple, je veux arrondir 5 à 8. Ou 25 à 32. Ou encore 250 à 256. Effectuer ce calcul peut sembler compliqué, si on ne prend pas le problème par le bon bout. Mais il y a une méthode simple pour faire ce calcul : il suffit de calculer non pas la puissance de deux, mais le nombre qui précède et de l'incrémenter. Le calcul de cette valeur, à savoir le nombre de la forme $2^{n}-1$ immédiatement supérieur, est en effet très simple à faire. Nous avions vu comment calculer ce nombre dans le chapitre sur la manipulation des bits de poids fort/faible. En fait, calculer ce nombre consiste juste à mettre à 1 tous les bits situés après le 1 de poids fort. En adaptant le code pour ce faire, on trouve :

unsigned NextPowerOf2 (unsigned n)
{
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return n++;
}

La décrémentation au début du code sert à gérer le cas où le nombre traité est lui-même une puissance de deux.