Jeu d'instructions CLMUL

Carry-less Multiplication (CLMUL) est une extension du jeu d'instructions x86 utilisé par les microprocesseurs d’Intel et d’AMD qui a été proposé par Intel en mars 2008^[1] et mis à disposition dans les processeurs Intel Westmere annoncés au début de 2010. Mathématiquement, l’instruction implémente la multiplication des polynômes sur le corps fini GF(2) où la chaîne de bits $a_{0}a_{1}\ldots a_{63}$ représente le polynôme $a_{0}+a_{1}X+a_{2}X^{2}+\cdots +a_{63}X^{63}$ . L’instruction CLMUL permet également une implémentation plus efficace de la multiplication étroitement liée sur des corps finis plus grands GF(2^k) que le jeu d’instructions traditionnel^[2].

L’une des utilisations de ces instructions est d’améliorer la vitesse des applications effectuant le chiffrement par bloc en Galois/Counter Mode, qui dépend de la multiplication sur le corps fini GF(2^k). Une autre application est le calcul rapide des valeurs CRC^[3], y compris celles utilisées pour implémenter l’algorithme Deflate de la fenêtre glissante (en) LZ77 dans zlib et pngcrush (en)^[4].

ARMv8 dispose également d’une version de CLMUL. SPARC appelle sa version XMULX, pour « XOR multiplication ».

Nouvelles instructions

L'instruction calcule le produit sans retenue (en) 128 bits de deux valeurs 64 bits. La destination est un registre XMM 128 bits. La source peut être un autre registre XMM ou la mémoire. Un opérande immédiat spécifie quelles moitiés des opérandes 128 bits sont multipliées. Des mnémoniques spécifiant des valeurs spécifiques de l'opérande immédiat sont aussi définis :

Instruction	Opcode	Description
`PCLMULQDQ xmmreg,xmmrm,imm`	`[rmi: 66 0f 3a 44 /r ib]`	Effectue la multiplication sans retenue de deux polynômes 64 bits sur le corps fini GF(2)[X].
`PCLMULLQLQDQ xmmreg,xmmrm`	`[rm: 66 0f 3a 44 /r 00]`	Multiplie les deux moitiés basses des deux registres.
`PCLMULHQLQDQ xmmreg,xmmrm`	`[rm: 66 0f 3a 44 /r 01]`	Multiplie la moitié haute du registre de destination par la moitié basse du registre source.
`PCLMULLQHQDQ xmmreg,xmmrm`	`[rm: 66 0f 3a 44 /r 10]`	Multiplie la moitié basse du registre de destination par la moitié haute du registre source.
`PCLMULHQHQDQ xmmreg,xmmrm`	`[rm: 66 0f 3a 44 /r 11]`	Multiplie les deux moitiés hautes des deux registres.

Une version vectorisée EVEX (VPCLMULQDQ) existe dans AVX-512.

Références

↑ (en-US) « Intel Software Network - Archivé depuis l'original », Intel (consulté le 5 avril 2008)
↑ (en) Shay Gueron et Michael E. Kounavis, « Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode – Rev 2.02 » [PDF], Intel, 20 avril 2014
↑ (en-US) « Fast CRC Computation for Generic Polynomials Using PCLMULQDQ »
↑ (en-US) Vlad Krasnov, « Fighting Cancer: The Unexpected Benefit Of Open Sourcing Our Code », CloudFlare, 8 juillet 2015 (consulté le 4 septembre 2016)

Portail de l’informatique

[1] (en-US) « Intel Software Network - Archivé depuis l'original », Intel (consulté le 5 avril 2008)

[2] (en) Shay Gueron et Michael E. Kounavis, « Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode – Rev 2.02 » [PDF], Intel, 20 avril 2014

[3] (en-US) « Fast CRC Computation for Generic Polynomials Using PCLMULQDQ »

[4] (en-US) Vlad Krasnov, « Fighting Cancer: The Unexpected Benefit Of Open Sourcing Our Code », CloudFlare, 8 juillet 2015 (consulté le 4 septembre 2016)

[1]

[2]

[3]

[4]