Fonctionnement d'un ordinateur/Les circuits de décalage et de rotation

Dans ce chapitre, nous allons voir des opérations appelées les décalages et les rotations. Nous allons voir ce que sont ces opérations, puis les nombreux circuits qui permettent d'implémenter ces opérations. Mais expliquons d'abord les différentes opérations de décalage et de rotation.

Les opérations de décalage

Les décalages décalent un nombre de un ou plusieurs rangs vers la gauche, ou la droite. Il existe plusieurs opérations de décalage différentes et on peut les classer en plusieurs types. Dans les grandes lignes, on distingue les rotations, les décalages logiques et les décalages arithmétiques. Elles se distinguent sur plusieurs points, les principaux étant les suivants :

• ce qu'on fait des bits qui sortent du nombre lors du décalage ;
• comment on remplit les vides qui apparaissent lors du décalage ;
• la manière dont est géré le signe du nombre décalé.

Décalages, gestion des bits entrants et sortants

Pour comprendre les deux premiers points, prenons l'exemple ci-contre. L'exemple montre le décalage de deux rangs vers la droite, d'un opérande de 8 bits valant 01011101. On obtient 010111 : les deux bits de poids forts sont vides et les deux bits de poids faible (01) sortent du nombre. Et cela vaut pour tout décalage : d'un côté le décalage fait sortir des bits du nombre, de l'autre certains bits sont inconnus ce qui laisse des vides dans le nombre. Si on décale de n rangs, alors cela laissera n vides et fera sortir n bits. Ces deux points, la gestion des vides et des bits sortants, sont assez liés.

Le différents types de décalages

Au-delà de la distinction assez intuitive entre les décalages vers la gauche et vers la droite, parlons de ce qu'on fait des bits qui sortent du nombre lors du décalage. Que fait-on de ces bits ?

La première solution est de les faire rentrer de l'autre côté, de les remettre au début du nombre décalé. L'opération en question est alors appelée une rotation. Il existe des rotations à droite et à gauche.

MSB : bit de poids fort (Most Significant Bit) LSB : bit de poids faible (Least Significant Bit)

Rotation à gauche.

Rotation à droite.

L'autre solution est d'oublier les bits sortants. L’opération est alors appelée un décalage, qui peut être soit un décalage logique, soit un décalage arithmétique. Le fait que l'on oublie les bits sortants fait que les vides ne sont pas remplis et qu'il faut trouver de quoi les combler. Et c'est là qu'on peut faire la distinction entre décalages logiques et arithmétiques.

Avec un décalage logique, les vides sont remplis par des zéros, aussi bien pour un décalage à gauche et un décalage à droite.

Décalage logique à gauche.

Décalage logique à droite.

Décalage arithmétique à droite.

Avec un décalage arithmétique, la situation est différente pour un décalage à gauche et à droite. Le principe des décalages arithmétique est qu'ils conservent le bit de signe de l'opérande décalé (qui est supposé être signé), contrairement aux autres décalages. Pour un décalage à droite, les vides dans les vides de poids forts sont remplis par le bit de signe. Ce remplissage est une sorte d'extension de signe, ce qui fait que la conservation du signe est automatique.

Décalage arithmétique à gauche qui ne conserve pas le bit de signe.

Pour un décalage à gauche, les vides sont remplis par des zéros, comme pour un décalage logique. Mais pour ce qui est de la conservation du bit de signe, c'est plus compliqué. On a deux écoles : la première ne conserve pas le bit de signe, la seconde le fait. Dans le premier cas, le décalage est identique à un décalage logique à gauche. Dans le second cas, le bit de signe n'est pas concerné par le décalage et il se produit une forme particulière de débordement d'entier.

L'utilité principale des opérations de décalage est qu'elles permettent de faire simplement des multiplications ou divisions par une puissance de 2. Un décalage logique/arithmétique correspond à une multiplication ou division entière par 2^n : multiplication pour les décalages à gauche, division pour les décalages à droite. Les décalages logiques fonctionnent seulement pour les entiers non signés, alors que les décalages arithmétiques fonctionnent sur les entiers signés. Le fait est qu'un décalage logique ne préserve pas le bit de signe.

Modulo et quotient d'une division par une puissance de deux en binaire

Les arrondis lors des décalages

Les décalages à droite entraînent l'apparition d'arrondis. Lorsqu'on effectue un décalage à droite, les bits qui sortent du résultat sont perdus. L’équivalent en décimal est que les chiffres après la virgule sont perdus, ce qui arrondit le résultat. Mais cet arrondi dépend de la représentation des nombres utilisé. Pour comprendre pourquoi, il faut faire un rapide rappel sur les types d'arrondis en décimal.

En décimal, on peut arrondir de deux manières : soit on arrondit à l'entier au-dessus, soit on arrondi à l'entier au-dessous. Par exemple, prenons la division 29/4, qui a pour résultat 7.25. Cela donne 7 dans le premier cas et 8 dans le second. Pour un résultat négatif, c'est la même chose, mais le fait que le signe soit inversé change la donne. Par exemple, prenons le résultat de -29 / 4, soit -7.25. On peut l'arrondir soit à -7, soit à -8. En combinant les deux cas négatifs avec les deux cas positifs, on se trouve face à quatre possibilités :

• l'arrondi vers la plus basse valeur absolue (vers zéro), qui donne respectivement 7 et -7 dans l'exemple précédent.
• l'arrondi vers la plus basse valeur (vers moins l'infini), qui donne -8 et 7 dans l'exemple précédent ;
• l'arrondi vers la plus haute valeur (vers plus l'infini), qui donne -7 et 8 dans l'exemple précédent ;
• l'arrondi vers la plus haute valeur absolue (vers l'infini), qui donne 8 et -8 dans l'exemple précédent.

En binaire, c'est la même chose. Par exemple, 11100,1010 peut s'arrondir en 11100 ou en 11101, suivant qu'on arrondisse vers le bas ou vers le haut, et la même chose est possible pour les nombres négatifs. Vu que les bits sortants sont simplement éliminés, on pourrait croire que cela correspond à un arrondi vers zéro (vers la valeur inférieure). C'est bien le cas pour les décalages logiques, peu importe la représentation, l'arrondi se fait vers zéro (vu que tous les nombres sont traités comme positifs). Mais pour les décalages arithmétiques, tout dépend de la représentation binaire utilisée. L'arrondi se fait bien vers zéro en complément à 1, mais pas en complément à deux, où l'arrondi se fait à la valeur inférieure, vers moins l'infini.

Précisons que ces arrondis n'ont lieu que si le résultat du décalage n'est pas exact. Pour un décalage d'un rang, à savoir une division par deux, seuls les nombres impairs donnent un arrondi, pas les nombres pairs. De manière générale, pour un décalage de n rangs, les nombres divisibles par 2^n ne donnent pas d'arrondi, alors que les autres si.

Les débordements d'entiers lors des décalages

Les décalages peuvent aussi causer des débordements d'entier. Pour rappel un débordement d'entier est une situation où le résultat d'un calcul devient trop gros pour être codé. Pour donner un exemple, prenons une situation équivalente mais en décimal. Par exemple supposons que l'ordinateur sur lequel vous travailler manipule des données codées sur 5 chiffres décimaux, pas plus. Si on prend le nombre 4512, le décalage à gauche d'un cran donne 45120, qui tient sur 5 chiffres : on n'a pas de débordement. Mais si je prends le nombre 97426, un décalage à gauche d'un cran donne 974260, ce qui ne tient pas dans 5 chiffres : on a un débordement d’entier. Celui-ci se traduit par le fait qu'un chiffre non-nul sorte du nombre. La même chose a lieu en binaire, avec les décalages à gauche : si au moins un bit non-nul sorte à gauche, c'est un débordement d'entier.

La manière habituelle de gérer les débordements d'entiers est simplement de ne rien faire, mais de prévenir qu'un débordement a eu lieu. Pour cela, le circuit qui effectue le décalage a une sortie qui indique qu'un débordement a eu lieu lors du décalage. Cette sortie fournit un simple bit qui vaut 1 en cas de débordement et 0 sinon (ou l'inverse). Une autre solution est de corriger le débordement, mais elle est utilisée uniquement pour les opérations arithmétiques, pas pour les décalages.

Toujours est-il que déterminer l’occurrence d'un débordement n'est pas compliqué. Pour les décalages logiques, il suffit de prendre les bits sortants et de vérifier qu'un au moins d'entre eux vaut 1. Une simple porte OU sur les bits sortants fait l'affaire. Pour les décalages arithmétiques, il faut aussi tenir compte de la présence du bit de signe. Si le nombre décalé est positif, seuls des zéros doivent sortir, la présence d'un 1 indiquant un débordement d'entier. Pour un nombre négatif, c'est l'inverse : seuls des 1 doivent sortir (du fait des règles d'extension de signe), alors que l’occurrence d'un zéro trahit un débordement d'entier. Pour résumer le tout, les bits sortants sont censés être égaux au bit de signe, un débordement a eu lieu dans le cas contraire. L’occurrence d'un débordement se détermine en décomposant le décalage en une succession de décalages de 1 bit. Si un seul de ces décalages de 1 rang altère le bit de signe (change sa valeur), alors on a un débordement.

Il est possible de déterminer l’occurrence d'un débordement en analysant l'opérande, sans même avoir à faire le décalage. Pour un décalage vers la gauche de $n$ rangs, on sait que les bits sortants sont les $n$ bits de poids fort de l'opérande. En clair, on peut déterminer si un débordement a lieu en sélectionnant seulement les $n$ bits de poids fort de l'opérande. Pour cela, on peut simplement prendre l'opérande et lui appliquer un masque adéquat. Par exemple, prenons le cas d'un débordement pour un décalage logique, qui a lieu si au moins un bit sortant est à 1. Il suffit de prendre l'opérande, conserver les $n$ rangs bits de poids fort et mettre les autres à zéro, puis faire un ET entre les bits du résultat. La même logique prévaut pour les décalages arithmétiques, même s'il faut faire quelques adaptations.

Calcul du bit de débordement pour un décalage à gauche de trois rangs.

Toujours est-il que le calcul des débordements peut se faire en parallèle du décalage, ce qui est utile. Précisons que le masque se calcule dans un circuit à part, qui ressemble beaucoup à un encodeur. Le masque calculé peut être utilisé sur certains circuits de décalages, pour transformer des rotations en décalage logiques, par exemple. Mais nous verrons cela plus tard.

Les décaleurs et rotateurs élémentaires

Décaleur - interface

Pour commencer, nous allons voir deux types de circuits : les décaleurs qui effectuent un décalage (logique ou arithmétique, peu importe) et les rotateurs qui effectuent une rotation. Les deux circuits sont conceptuellement séparés, même s’ils se ressemblent. Faire la distinction sera utile dans la suite du cours. Leur interface est la même pour tous les décaleurs et rotateurs élémentaires. On doit fournir l'opérande à décaler et le nombre de rangs qu'on veut décaler en entrée, et on récupère l'opérande décalé en sortie.

Nous allons d'abord voir comment créer un décaleur. Pour cela, on peut faire une remarque simple : décaler de 6 rangs, c'est équivalent à décaler de 4 rangs et redécaler le tout de 2 rangs. Même chose pour 7 rangs : cela consiste à décaler de 4 rangs, redécaler de 2 rangs et enfin redécaler d'un rang. En suivant l'idée jusqu'au bout, on peut créer un décaleur à partir de décaleurs plus simples, reliés en cascade, qu'on active ou désactive suivant le nombre de rangs. Les décaleurs élémentaires décalent par 1, 2, 4, 8, etc ; bref : par une puissance de 2. La raison à cela est que le nombre de rangs par lequel on va devoir décaler est un nombre codé en binaire, qui s'écrit donc sous la forme d'une somme de puissances de deux. Le énième bit du nombre de rang servira à actionner le décaleur par 2^n.

Décaleur logique - principe

La même logique s'applique pour les rotateurs, la seule différence étant qu'il faut remplacer les décaleurs par 1, 2, 4, 8, etc ; par des rotateurs par 1, 2, 4, 8, etc. Reste à savoir comment créer ces décaleurs qu'on peut activer ou désactiver à la demande. Surtout que le circuit n'est pas le même selon que l'on parle d'un décalage logique, d'un décalage arithmétique ou d'une rotation. Néanmoins, tous les circuits de décalage/rotation sont fabriqués avec des multiplexeurs à deux entrées et une sortie.

Le circuit décaleur logique

Commençons par étudier le cas du décalage logique par 4 rangs à droite. La sortie vaudra soit le nombre tel qu'il est passé en entrée (le décaleur est inactif), soit le nombre décalé de 4 rangs. Ainsi, si je prends un nombre A, composé des bits a7, a6, a5, a4, a3, a2, a1, a0 ; (cités dans l'ordre), le résultat sera :

• soit le nombre composé des chiffres a7, a6, a5, a4, a3, a2, a1, a0 (on n'effectue pas de décalage) ;
• soit le nombre composé des chiffres 0, 0, 0, 0, a7, a6, a5, a4 (on effectue un décalage par 4).

Chaque bit de sortie peut prendre deux valeurs, qui valent soit zéro, soit un bit du nombre d'entrée. On peut donc utiliser un multiplexeur pour choisir quel bit envoyer sur la sortie. Par exemple, pour le choix du bit de poids fort du résultat, celui-ci vaut soit a7, soit 0 : il suffit d’utiliser un multiplexeur prenant le bit a7 sur son entrée 1, et un 0 sur son entrée 0.

Exemple d'un décaleur par 4.

Le tout peut être adapté pour créer des décaleurs par 1, par 2, par 8, etc. Il suffit de faire la même chose pour tous les autres bits, et le tour est joué. En utilisant des décaleurs basiques par 4, 2 et 1 bit, on obtient le circuit suivant :

Décaleur logique 8 bits.

Le circuit décaleur arithmétique

Les décalages arithmétiques sont basés sur le même principe, à une différence près : on n'envoie pas un zéro dans les bits de poids fort, mais le bit de signe (le bit de poids fort du nombre d'entrée). Un décaleur arithmétique ressemble beaucoup à un décaleur logique, la seule différence étant que c'est le bit de poids fort qui est relié aux entrées des multiplexeurs, là où c'était le zéro avec le décaleur logique. Par exemple, reprenons un nombre A, composé des bits a7, a6, a5, a4, a3, a2, a1, a0 ; (cités dans l'ordre). La sortie d'un décaleur arithmétique par 4 sera :

• soit le nombre composé des chiffres a7, a6, a5, a4, a3, a2, a1, a0 (on n'effectue pas de décalage) ;
• soit le nombre composé des chiffres a7, a7, a7, a7, a7, a6, a5, a4 (on effectue un décalage arithmétique par 4).

Exemple d'un décaleur arithmétique par 4

En combinant des décaleurs basiques par 4, 2 et 1 bits, on obtient le circuit suivant :

Décaleur arithmétique 8 bits

Le circuit rotateur

Les rotations sont elles aussi basées sur le même principe, sauf que ce sont les bits de poids faible qu'on injecte dans les bits de poids forts, au lieu d'un zéro ou du bit de signe. Le circuit est donc le même, sauf que les connexions ne sont pas identiques. Là où il y avait un zéro sur les entrées des multiplexeurs, on doit envoyer le bon bit de poids faible. Par exemple, reprenons un nombre A, composé des bits a7, a6, a5, a4, a3, a2, a1, a0 ; (cités dans l'ordre). La sortie d'un rotateur arithmétique par 4 sera :

• soit le nombre composé des chiffres a7, a6, a5, a4, a3, a2, a1, a0 (on n'effectue pas de décalage) ;
• soit le nombre composé des chiffres a3, a2, a1, a0, a7, a6, a5, a4 (on effectue un décalage arithmétique par 4).

Les barell shifters unidirectionnels

Barrel shifter - interface

Dans ce qui précède, on a appris à créer un circuit qui fait des décalages logiques, un autre pour les décalages arithmétiques et un autre pour les rotations. Il nous reste à voir les décaleurs-rotateurs, aussi appelés des barrel shifters, qui sont capables de faire à la fois des décalages et des rotations. Certains décaleur-rotateurs sont capables de faire des rotations et des décalages logiques, d'autres savent aussi réaliser les décalages arithmétiques en plus. Un tel circuit a la même interface qu'un décaleur, sauf qu'on rajoute une entrée qui précise quelle opération faire. Cette entrée indique s'il faut faire un décalage logique, un décalage arithmétique ou une rotation.

Précisons dès maintenant qu'il faut faire la différence entre un barrel shifter unidirectionnel et un barrel shifter bidirectionnel. La différence entre les deux tient dans le sens possible des décalages. Le barrel shifter unidirectionnel ne peut faire que des décalages à gauche ou que des décalages à droite, mais pas les deux. À l'inverse, un barrel shifter bidirectionnel peut faire des décalages à droite et à gauche, suivant ce qu'on lui demande. Dans cette section, nous allons nous concentrer sur les barrel shifters unidirectionnels, qui font des décalages/rotations vers la droite. Les explications seront valides aussi pour des décalages/rotations à gauche, avec quelques petites modifications triviales.

Il existe trois grandes méthodes pour fabriquer un décaleur-rotateur.

• La manière la plus naïve est de prendre un décaleur logique, un décaleur arithmétique et un rotateur, et de prendre le résultat adéquat suivant l’opération voulue. Le choix du bon résultat est effectué par une couche de multiplexeur adaptée. Mais cette solution est inutilement gourmande en multiplexeurs. Après tout, les trois circuits se ressemblent et partagent une même structure.
• Une autre solution, bien plus économe en multiplexeurs, élimine ces redondances en fusionnant les trois circuits en un seul. Elle part d'un circuit qui effectue des décalages logiques, auquel on ajoute des multiplexeurs pour le rendre capable de faire aussi les décalages arithmétiques et les rotations.
• La dernière méthode part d'un rotateur et on lui ajoute de quoi faire des décalages logiques.

Le décaleur-rotateur à base de multiplexeurs

Avec la seconde méthode, on part d'un circuit qui effectue des décalages logiques, auquel on ajoute des multiplexeurs pour le rendre capable de faire aussi les décalages arithmétiques et les rotations. Ces nouveaux multiplexeurs ne font que choisir les bits à envoyer sur les entrées des décaleurs. Par exemple, prenons un décalage/rotation par 4 crans. La seule différence entre décalage logique, arithmétique et rotation est ce qu'on met sur les 4 bits de poids fort : un 0 pour un décalage logique, le bit de poids fort pour un décalage arithmétique et les 4 bits de poids faible pour une rotation. Pour choisir entre ces trois valeurs, il suffit de rajouter des multiplexeurs.

Nous allons d'abord ajouter des multiplexeurs pour prendre en charge les rotations, un peu de la même manière qu'on modifie un décaleur logique pour lui faire faire aussi des décalages arithmétiques. Pour cela, prenons un décaleur par 4 et étudions les 4 bits de poids fort. Suivant le type de décalage, on doit envoyer soit un zéro, soit le bit de poids faible adéquat sur certaines entrées. Ce choix peut être réalisé par un multiplexeur, tant qu'il est commandé correctement. En clair, il suffit d'ajouter un ou plusieurs multiplexeurs pour chaque décaleur élémentaire par 1, 2, 4, etc. Ces multiplexeurs choisissent quoi envoyer sur l'entrée de l'ancienne couche : soit un 0 (décalage logique), soit le bit de poids faible (rotation). Notons qu'on doit utiliser un multiplexeur par entrée, contrairement au décaleur complet. La raison est qu'un décalage arithmétique envoie toujours le même bit dans les entrées de poids fort, alors qu'une rotation envoie un bit différent sur chaque entrée de poids fort, ce qui demande un multiplexeur par entrée.

Décaleur-rotateur par 4.

Il est possible d'étendre le décaleur logique pour lui permettre de faire des décalages arithmétiques. Pour cela, même recette que dans le cas précédent. Encore une fois, suivant le type de décalage, on doit envoyer soit un zéro, soit le bit de poids fort sur certaines entrées. Il est possible d'utiliser un seul multiplexeur dans ce cas précis, car on envoie le même bit sur les entrées de poids fort.

Exemple avec un décaleur par 4.

En combinant des décaleurs basiques par 4, 2 et 1 bits, on obtient un circuit qui fait tous les types de décalages. Pas étonnant que ce circuit soit nommé un décaleur complet. Notons qu'on peut se contenter d'un seul mutiplexeur pour tout le barrel shifter, en utilisant le câblage astucieusement. Après tout, le choix entre 0 ou bit de poids fort est le même pour toutes les entrées concernées. Autant ne le faire qu'une seule fois et connecter toutes les entrées concernées au multiplexeur.

Décaleur complet 8 bits

En utilisant les deux modifications en même temps, on se retrouve avec un barrel-shifter complet, capable de faire des décalages et rotations sur 4 bits.

Circuit de rotation partiel.

Les mask barrel shifters

Les mask barrel shifters sont des décaleurs-rotateurs basés autour d'un rotateur, qui est modifié afin de supporter les décalages logiques/arithmétiques. L'idée est de faire une rotation et de corriger le résultat si c'est un décalage qui est demandé. La correction à effectuer dépend du type de décalage demandé, suivant qu'il soit logique ou arithmétique.

Pour un décalage logique, il suffit de mettre les n bits de poids fort à zéro pour un décalage de n bits vers la droite (inversement, les n bits de poids faible pour un décalage vers la gauche). Et pour mettre des bits de poids fort à zéro sous une certaine condition, on doit utiliser un masque qui est calculé par un circuit dédié. Le circuit de calcul du masque est un encodeur modifié, qu'on peut concevoir avec les techniques des chapitres précédents.

Le circuit qui combine le masque avec le résultat de la rotation est composé d'une couche de portes ET et d'une couche de multiplexeurs. La couche de portes ET applique le masque sur le résultat du rotateur. Les multiplexeurs choisissent entre le résultat du rotateur et le résultat avec masque appliqué. Les multiplexeurs sont commandés par un bit de commande qui indique s'il faut faire un décalage ou une rotation.

Décaleur-rotateur basé sur un masque.

Les barrel shifters bidirectionnels (à double sens de décalage/rotation)

Le circuit précédent est capable d'effectuer des décalages et rotations, mais seulement vers la droite. On peut évidemment concevoir un circuit similaire capable de faire des décalages/rotations vers la gauche, mais il est intéressant d'essayer de créer un circuit capable de faire les deux. Un tel circuit est appelé un barrel shifter bidirectionnel. Notons qu'on doit obligatoirement fournir un bit qui indique dans quelle direction faire le décalage. Précédemment, nous avons vu qu'il existe deux méthodes pour créer un barrel shifter. La première se base sur un décaleur auquel on ajoute de quoi faire les rotations, alors que l'autre se base sur l'application d'un masque en sortie d'un rotateur. Dans ce qui va suivre, nous allons voir comment ces deux types de circuits peuvent être rendus bidirectionnels.

Barrel shifter bidirectionnel - interface

Les barrel shifters bidirectionnels basé sur des multiplexeurs

Commençons par voir comment rendre bidirectionnel un barrel shifter basé sur des multiplexeurs. Pour rappel, ces derniers sont basés sur un décaleur qu'on rend capable de faire des rotations en ajoutant des multiplexeurs.

Une première solution est d'utiliser des barrel shifters bidirectionnels série, série signifiant que les deux sens sont calculés en série, l'un après l'autre. Ils sont composés de décaleurs qui sont capables de faire des décalages/rotations vers la gauche et vers la droite. De tels décaleurs peuvent se concevoir de diverses façons, mais la plus simple se base sur le principe qui veut qu'un décaleur est composé de décaleurs de 1, 2, 4, 8 bits, etc. Chaque décaleur est en double : une version qui décale vers la gauche, et une autre qui décale vers la droite. Lors d'un décalage vers la droite, les décaleurs élémentaire à gauche sont désactivés alors que les décaleurs vers la droite sont actifs (et réciproquement lors d'un décalage à gauche). Le bit qui indique la direction du décalage est envoyé à chaque décaleur et lui indique s'il doit décaler ou non.

Décaleur bidirectionnel

Une autre solution, bien plus simple, est de prendre un décaleur/rotateur vers la gauche et un autre vers la droite, et de prendre la sortie adéquate en fonction de l'opération demandée. Le choix du résultat se fait encore une fois avec une couche de multiplexeurs. Le résultat est ce qu'on appelle un barrel shifter bidirectionnel parallèle, parallèle signifiant que les deux sens sont calculés en parallèle, en même temps. Notons que cette solution ressemble beaucoup à la précédente. À vrai dire, si on prend la première solution et qu'on regroupe ensemble les décaleur/rotateurs allant dans la même direction, on retombe sur un circuit presque identique à un barrel shifter bidirectionnel parallèle.

Les deux techniques précédentes utilisent beaucoup de portes logiques et il est possible de faire bien plus efficace. L'idée est simplement d'inverser l'ordre des bits avant de faire le décalage ou la rotation, puis de remettre le résultat dans l'ordre. Par exemple, pour faire un décalage à gauche, on inverse les bits du nombre à décaler, on fait un décalage à droite, puis on remet les bits dans l'ordre originel, et voilà ! Pour cela, il suffit de prendre un décaleur/rotateur à droite, et d'ajouter deux circuits qui inversent l'ordre des bits : un avant le décaleur/rotateur, un après. Ce circuit d'inversion est une simple couche de multiplexeurs. Le résultat est ce qu'on appelle un barrel shifter bidirectionnel à inversion de bits.

Barrel shifter à inversion de bits.

Le décaleur-rotateur bidirectionnel basé sur des masques

Dans cette section, nous allons voir concevoir un rotateur bidirectionnel avec des masques. Pour cela, il faut juste créer un rotateur bidirectionnel et utiliser des masques pour obtenir des décalages.

Pour créer le rotateur bidirectionnel, nous allons devoir étudier ce qui se passe quand on enchaine deux rotations successives. N'allons pas par quatre chemins : l'enchainement de deux rotations successives donne un résultat qui aurait pu être obtenu en ne faisant qu'une seule rotation. Par exemple, faire une rotation à droite par 5 rangs suivie d'une rotation à droite de 8 rangs est équivalent à faire une rotation à droite de 5+8 rangs, soit 13 rangs. Le résultat issu de la succession de deux rotations est identique à celui d'une rotation équivalente. Et on peut calculer le nombre de rangs de la rotation équivalente à partir des rangs des deux rotations initiales. Pour cela, il suffit d'additionner les rangs en question.

La logique est la même quand on enchaine des rotations à droite et à gauche. Il suffit de compter les rangs d'une rotation en les comptant positifs pour une rotation à droite et négatifs pour une rotation à gauche. Par exemple, une rotation de -5 rangs sera une rotation à gauche de 5 rangs, alors qu'une rotation de 10 rangs sera une rotation à droite de 10 rangs. On pourrait faire l'inverse, mais prenons cette convention pour l'explication qui suit. Toujours est-il qu'avec cette convention, l'addition des rangs donne le bon résultat pour la rotation équivalente. Par exemple, si je fais une rotation à droite de 15 rangs et une rotation à gauche de 6 rangs, le résultat sera une rotation de 15-6 rangs : c'est équivalent à une rotation à droite de 9 rangs.

Faisons dès maintenant remarquer quelque chose d'important. Prenons un nombre de n bits. Avec un peu de logique et quelques expériences, on remarque facilement qu'une rotation par $n$ ne fait rien, dans le sens où les bits reviennent à leur place initiale. Une rotation par $n$ est donc égale à pas de rotation du tout, ce qui est équivalent à faire une rotation par zéro rangs.

Pour le moment, ce détail nous permet de gérer le cas où l'addition de deux rangs donne un résultat supérieur à $n$. Par exemple, prenons une rotation par 56 rangs pour un nombre de 9 bits. La division nous dit que 56 = 9*6 + 2. En clair, faire un décalage par 56 rangs est équivalent à faire 6 rotations totales par 9, suivie d'une rotation par 2 rangs. Les rotations par 9 ne comptant pas, cela revient en fait à faire une rotation par 2 rangs. Le même raisonnement fonctionne dans le cas général, et revient à faire ce qu'on appelle une addition modulo n. C'est à dire qu'une fois le résultat de l'addition connu, on le divise par $n$ et l'on garde le reste de la division. Avec cette méthode, le nombre de rangs de la rotation équivalente est compris entre 0 et $n-1$.

Les additions modulo n seront notées comme suit : $(a+b)\mod n$.

Armé de ces explications, on peut maintenant expliquer comment fonctionne le rotateur bidirectionnel. L'idée derrière ce circuit est de remplacer une rotation à droitepar une rotation à gauche équivalente (ou inversement, mais nous allons supposer que le rotateur fait des rotations vers la gauche). Dans ce qui suit, nous utiliserons la notation suivante : $r_{\text{équivalent}}$ est le nombre de rangs de la rotation équivalente, $n$ la taille du nombre à décaler et $r$ le nombre de rangs du décalage initial. En soi, ce n'est pas compliqué de trouver une rotation équivalente : une rotation à droite de $r$ rangs est équivalente à une rotation de $r+n$ rangs, à une rotation de $r+2\times n$ rangs, et de manière générale à toute rotation de $r+k\times n$ rangs. La raison est que les rotations par n ne comptent pas, elles sont éliminées par la division par $n$. Pour résumer, on a :

$r_{\text{équivalent}}=(r\pm k\times n)\mod n$

Ls propriétés des calculs modulo n font que cela marche aussi quand on retranche n. Les bizarreries de l'arithmétique modulaire font que, quand on fait les additions modulo n, on peut remplacer tout nombre positif r par $r\pm k\times n$ sans changer les résultats. Mais tous les cas possibles ne nous intéressent pas. En effet, on sait que le nombre de rangs de la rotation équivalente est compris entre 0 et $n-1$. Le résultat que l'on recherche doit donc être compris entre 0 et $n-1$. Et seul un cas respecte cette contrainte : celui où l'on retranche n une seule fois. On a alors :

$r_{\text{équivalent}}=r-n$

L'équation nous dit qu'il est possible de remplacer une rotation à droite par une rotation à gauche équivalente. Par exemple, sur 8 bits et pour une rotation à droite de 6 bits, on a $r_{\text{équivalent}}=6-8=-2$. En clair, la rotation équivalente est ici une rotation à gauche de 2 crans. Vous pouvez essayer avec d'autres exemples, vous trouverez la même chose. Par exemple, sur 16 bits, une rotation à gauche de 3 rangs est équivalente à une rotation à droite de 13 rangs.

Le calcul ci-dessus peut être simplifié en utilisant quelques astuces. Sur la plupart des ordinateurs, n est égal à 8, 16, 32, 64, ou toute autre nombre de la forme $2^{n}$. Les cas où n vaut 3, 7, 14 ou autres sont tellement rares que l'on peut les considérer comme anecdotiques. De plus, $r$ est compris entre 0 et $n-1$. On peut donc coder le rang sur un nombre bien précis de bits, tel que n est la valeur haute de débordement (en clair, n-1 est la plus grande valeur codable, n entraine un débordement d'entier). Grâce à cela, on peut coder le nombre de rangs en complément à un ou en complément à deux. Rappelons que ces deux représentations des nombres utilisent l'arithmétique modulaire, c'est à dire que l'addition et la soustraction se font modulo n, et que leur principe est de représenter tout n négatif par un n positif équivalent. Ainsi, tout $r_{\text{équivalent}}$ négatif est codé par un $r$ positif équivalent. Et dans ces représentations, on a obligatoirement $r-n=-r$. En appliquant cette formule dans l'équation précédente, on a :

$r_{\text{équivalent}}=-r$

Reprenons l'exemple d'une rotation à gauche de 2 crans pour un nombre de 8 bits, ce qui est équivalent à une rotation de 6 crans à droite: on a bien 6 = -2 en complément à deux. Reste à faire le calcul ci-dessus par le circuit de rotation.

En complément à un, le calcul de l'opposé d'un nombre consiste simplement à inverser les bits de $r_{\text{initial}}$. En conséquence, le circuit est plus simple en complément à un. Le calcul du nombre de rangs demande juste un inverseur commandable, qu'on sait fabriquer depuis quelques chapitres.

Rotateur bidirectionnel en complément à un.

En complément à deux, le calcul est le suivant :

$r_{\text{équivalent}}={\overline {r_{\text{initial}}}}+1$

On pourrait utiliser un circuit pour faire l'addition, mais il y a une autre manière plus simple de faire. L'idée est simplement de prendre le circuit en complément à un et d'y ajouter de quoi corriger le résultat final. En clair, on fait le calcul comme en complément à un, mais la rotation effectuée ne sera pas équivalente, du fait du +1 dans le calcul. Ce +1 indique simplement qu'il faut décaler le résultat obtenu d'un cran supplémentaire. Pour cela, on ajoute un rotateur d'un cran à la fin du circuit.

Rotateur bidirectionnel en complément à deux.

On peut transformer ce circuit en décaleur-rotateur en appliquant la méthode vue plus haut, à savoir en appliquant un masque en sortie du rotateur. Le circuit obtenu est le suivant :

Décaleur rotateur bidirectionnel basé sur un masque.

Le barrel shifter de l'Intel 386

Le barrel shifter de l'Intel 386 est différent des barrel shifter vus précédemment. Il gère nativement décalages, rotations, et quelques autres opérations. Il a pour particularité de faire toutes ses opérations à partir de décalages à droite. Et pour que cela fonctionne, il manipule ses opérandes d'une manière assez inédite.

Pour comprendre pourquoi, précisons que l'Intel 386 est le tout premier processeur 32 bits d'Intel. Intuitivement, on se dirait que son barrel shifter prend un opérande de 32 bits, et fournit une sortie de 32 bits. Mais la réalité est qu'il prend un opérande de 64 bits, répartie dans deux registres de 32 bits chacun. Le barrel shifter est de 64 bits. La sortie du circuit correspond aux 32 bits de poids faible du résultat du décalage.

Registre 32 bits	Registre 32 bits
Barrel Shifter hybride 64 - 32 bits
Sortie 32 bits

Un point intéressant porte sur que le décaleur hybride 64-32 bits. Il était composé de deux sous-circuits, l'un suivant l'autre. Le premier décale le résultat par paquets de 4 rangs, à savoir de 0, 4, 8, 12, 16, 20, 24 ou 28 rangs. Le second décale le résultat du premier de 0, 1, 2 ou 3 rangs. Faire ainsi économise des transistors comparé à un barrel shifter usuel, du moins pour un barrel shifter hybride 64-32 bits.

Pour un décalage à droite logique, les 32 bits de poids fort sont remplis par des zéros, les 32 bits de poids faible sont remplis avec l'opérande à décaler. Le décalage se fait normalement. Les décalages arithmétiques se font d'une manière similaire, la seule différence étant que les 32 bits de poids fort sont remplis avec le bit de signe.

Pour un décalage à gauche, la situation est inversée. L'opérande est placé dans les 32 bits de poids fort, alors que les zéros sont dans les 32 bits de poids fort. Le barrel shifter fait un décalage à droite, qui émule le décalage à gauche. Pour un décalage à gauche de N rangs, il est émulé par un décalage à droite de 32 − N rangs.

Pour les rotations, les 32 bits de poids fort sont remplis avec l'opérande, idem avec les bits de poids faible. Les rotations à droite se font avec un simple décalage à droite, les rotations à gauche se font avec le même décalage mais le nombre de rangs est altéré (de la même manière qu'avec les décalages à droite).

	32 bits de poids fort	32 bits de poids faible	Nombre de rangs du décalage
Décalage à droite logique (N rangs)	0	Opérande	N
Décalage à droite arithmétique (N rangs)	Bit de signe x32	Opérande	N
Décalage à gauche (N rangs)	Opérande	0	32 - N
Rotation à droite (N rangs)	Opérande	Opérande	N
Rotation à gauche (N rangs)	Opérande	Opérande	32 − N

L'avantage d'un tel circuit est qu'il facilite l'implémentation de certaines opérations qu'on n'a pas encore abordées, comme des rotations avec retenue, ou l'opération Bit Test. Le processeur gérait aussi nativement des décalages sur 64 bits, deux instructions étaient prévues pour. Ce n'était pas très utile pour un processeur 32 bits, mais l'implémentation était aisée, alors pourquoi pas ?