Wikilivres

« Les opérations bit à bit/Les débordements de puissance de deux » : différence entre les versions

Navigation interactive dans l’historique
← Modification précédenteModification suivante →
Contenu supprimé Contenu ajouté
VisuelWikicode
mAucun résumé des modifications
Ligne 1 :
Dans cette section, nous allons aborder les opérations qui font intervenir des nombres de la forme <math>2^n</math> et <math>2^n - 1</math>. 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 <math>2^n</math> qui est immédiatement supérieure à un nombre <math>x</math> 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é.
 
Ligne 11 ⟶ 5 :
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 <math>A</math> 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 <math>A</math> d'une donnée s'écrit comme suit :
Ligne 27 ⟶ 21 :
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 <math>A</math> et a une longueur <math>L</math>. Un débordement de page/bloc a lieu quand il existe un multiple de <math>2^n</math> entre <math>A</math> et <math>A + L</math>. Cela traduit le fait que la donnée commence dans un premier bloc, atteint la limite du bloc (donc, une adresse multiple de <math>2^n</math>) et se poursuit au-delà. Reste à voir comment les opérations bit à bit nous aident pour détecter une telle situation.
Ligne 65 ⟶ 59 :
: <math>(A \mod 2^n) + L \geq 2^n</math>
 
===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 <math>2^n</math> 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 <math>L + A \mod 2^n</math>, un débordement se produit si <math>L + A \% 2^n > 4096</math>. En clair, le débordement d'entier traduit un débordement de page. On détecte donc un débordement de page si :
Ligne 82 ⟶ 76 :
 
: <math>(A | - m) + L > 2^{n}</math>
 
==Le calcul du nombre de la forme <math>2^n</math> 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 <math>2^n - 1</math> 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 :
 
<syntaxhighlight lang="c">
unsigned NextPowerOf2 (unsigned n)
{
n--;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
return n++;
}
</syntaxhighlight>
 
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.
 
{{NavChapitre | book=Les opérations bit à bit
Récupérée de « https://fr.wikibooks.org/wiki/Les_opérations_bit_à_bit/Les_débordements_de_puissance_de_deux »