Formats et encodage des instructions

Au niveau de l’assembleur, une instruction est une ligne de texte. Le CPU, lui, lit des octets. L’ISA fixe la façon dont chaque instruction s’écrit en bits : quels bits choisissent l’opération, lesquels désignent les registres, où vont les constantes et les adresses. Cette disposition est le format d’instruction, et c’est l’une des choses les plus difficiles à changer une fois un processeur commercialisé. Le x86 décode encore des instructions disposées pour le 8086 en 1978.

Ce qu’une instruction doit dire

Toute instruction a besoin d’un opcode, le champ qui dit quoi faire. La plupart doivent aussi dire où sont leurs opérandes. Les ISA diffèrent par le nombre d’adresses d’opérandes que porte chaque instruction :

Moins d’adresses rendent chaque instruction plus courte, mais demandent plus d’instructions : calculer a = b + c prend une seule instruction à trois adresses, mais un chargement, une addition et un rangement sur une machine à pile. Les conceptions RISC modernes sont des machines à registres à trois adresses. Le x86 est à deux adresses, avec un opérande autorisé en mémoire.

Longueur fixe ou variable

• Longueur fixe : toutes les instructions ont la même taille — 32 bits sur ARM64 et RISC-V de base. Le décodage est simple et rapide : l’instruction suivante commence toujours 4 octets plus loin, donc un CPU peut en décoder plusieurs à la fois. Mais les instructions simples gaspillent des bits, et les constantes doivent tenir dans les champs restants.
• Longueur variable : une instruction prend autant d’octets qu’il lui en faut — de 1 à 15 sur x86. Le code est plus dense, ce qui aide le cache d’instructions. Mais le décodeur ne peut pas savoir où commence l’instruction suivante tant qu’il n’a pas déterminé la longueur de celle-ci.

Beaucoup d’ISA à longueur fixe ont ajouté une forme compressée de 16 bits pour la densité : Thumb sur l’ARM 32 bits, et l’extension C sur RISC-V.

Les concepteurs arbitrent entre plusieurs contraintes. Des instructions plus courtes, c’est plus d’instructions par ligne de cache et par cycle de lecture, et la bande passante mémoire est rare. Il faut de la place dans l’espace des opcodes pour chaque opération, et pour celles qu’on ajoutera au fil des décennies. Et chaque champ d’adresse doit être assez large pour les registres ou la mémoire qu’il désigne.

Les opcodes expansibles

Un format fixe peut quand même donner plus de bits d’opcode à certaines instructions qu’à d’autres. Prenons une instruction de 16 bits avec un opcode de 4 bits et trois champs de registre de 4 bits. Normalement, cela permet 16 instructions à trois registres. Mais si une valeur d’opcode, 1111, signifie « l’opcode continue dans le champ suivant », l’espace se subdivise :

Chacune des 65 536 combinaisons de bits est utilisée : 15 × 4096 + 14 × 256 + 31 × 16 + 16 = 65 536. La même idée — des opcodes courts pour les instructions qui ont besoin de beaucoup de bits d’opérandes, des opcodes plus longs pour les autres — se retrouve dans presque tous les encodages réels, y compris les octets d’échappement du x86.

x86-64 : visite champ par champ

Une instruction x86-64 est une suite de champs facultatifs autour d’un opcode obligatoire :

Le total est plafonné à 15 octets. L’opcode lui-même dit peu de chose : le décodeur doit le reconnaître entièrement avant même de savoir si un octet ModRM suit. Le texte de Tanenbaum donne 0xFF comme octet d’échappement ; c’est en réalité 0x0F. 0xFF est un opcode ordinaire, utilisé pour inc, dec, call, jmp et push sur la mémoire.

Tapez une instruction dans l’encodeur : il montre chaque champ, avec les bits de ModRM et de SIB détaillés :

03 44 8b 08 : l’opcode 03 signifie « ajouter un opérande registre-ou-mémoire à un registre de 32 bits ». Le ModRM 44 vaut 01 000 100 : mod 01 indique la mémoire avec un déplacement de 8 bits, reg 000 est eax, et rm 100 annonce un octet SIB. Le SIB 8b vaut 10 001 011 : échelle ×4, index rcx, base rbx. Puis vient le déplacement, 08.

L’encodage a ses bizarreries, et chacune se voit dans un désassemblage :

• mov eax, DWORD PTR [rsp+8] exige un octet SIB (8b 44 24 08), car rm = 100, le code de rsp, a été réservé pour dire « un SIB suit ».
• mov eax, DWORD PTR [rbp] exige un déplacement nul (8b 45 00), car mod 00 avec rm = 101 a été réservé à l’adressage relatif à rip.
• r8–r15 exigent un octet REX pour fournir le quatrième bit de registre, et r12 hérite en plus de la règle SIB de rsp :

45 8b 04 24 : le REX 45 a R à 1 (la destination est le registre 8 + 0 = r8d) et B à 1 (la base est 8 + 4 = r12). L’octet SIB n’est là que parce que les trois bits bas de r12, 100, sont les mêmes que ceux de rsp.

Quelques autres motifs à reconnaître :

• 48 83 c0 01 est add rax, 1. 48 est REX.W pour des opérandes de 64 bits, et 83 est la forme avec un immédiat de 8 bits étendu avec le signe : les petites constantes prennent un octet au lieu de quatre.
• 0f af c1 est imul eax, ecx. 0f renvoie à la table d’opcodes sur deux octets, où vivent la plupart des instructions ajoutées après le 8086.
• 66 89 d8 est mov ax, bx. Le préfixe 66 fait passer une instruction de 32 bits à 16 bits.
• f0 83 07 01 est lock add DWORD PTR [rdi], 1 : un incrément atomique.

ARM64 et RISC-V : des champs fixes

Dans un format fixe de 32 bits, chaque champ est au même endroit dans toutes les instructions de son type. Le add w0, w1, w2 de l’ARM64 vaut 0x0b020020 :

Le add a0, a1, a2 du RISC-V vaut 0x00c58533, au format R : funct7 | rs2 | rs1 | funct3 | rd | opcode = 0000000 | 01100 | 01011 | 000 | 01010 | 0110011. Les numéros de registre a2 = 12, a1 = 11 et a0 = 10 se lisent directement dans les bits. Un décodeur RISC-V sait où se trouve chaque champ de registre avant même de savoir ce que fait l’instruction, et peut donc commencer à lire les registres tôt. C’est tout l’intérêt d’un format régulier.

Pourquoi c’est important pour lire des binaires

Comme les instructions x86 ont une longueur variable, un désassembleur doit trouver où chacune commence. Décodez à partir du mauvais octet et vous obtenez un autre flux d’instructions, tout à fait valide en apparence :

Ces cinq octets sont mov eax, 0x909090c3. Sautez le premier octet — décodez c3 90 90 90 — et la même mémoire se lit comme un ret suivi de nop. Des instructions cachées dans d’autres instructions : c’est pourquoi les désassembleurs peuvent être trompés par des techniques d’anti-désassemblage, et c’est là que la programmation orientée retour (ROP) trouve beaucoup de ses « gadgets » : des séquences d’octets utiles au milieu du propre code d’un programme. Sur ARM64 ou RISC-V, avec des instructions fixes et alignées, c’est impossible : chaque instruction commence sur une frontière de 4 octets.

À retenir

• Un format d’instruction fixe l’emplacement de l’opcode et des champs d’opérandes. Les ISA vont des machines sans adresse (à pile) aux machines à trois adresses (à registres).
• Les formats à longueur fixe (ARM64, RISC-V : 32 bits) se décodent facilement en parallèle. Les formats à longueur variable (x86 : 1 à 15 octets) sont plus denses mais doivent être décodés l’un après l’autre.
• Les opcodes expansibles donnent des opcodes courts aux instructions qui ont besoin de beaucoup de bits d’opérandes, et des opcodes longs aux autres.
• Le x86-64 encode une instruction en préfixes, REX, opcode, ModRM, SIB, déplacement, immédiat. Ses bizarreries — l’octet SIB pour rsp, le déplacement nul pour rbp, REX pour r8–r15 — se voient dans chaque désassemblage.
• La longueur variable permet de cacher des instructions dans d’autres, ce qui compte pour les désassembleurs et les exploits.