Retro-tech : l’algorithme Double Dabble

Aujourd’hui, nous disposons de microcontrôleurs puissants. Ces microcontrôleurs sont assez performants pour que nous puissions coder « confortablement » sans nous soucier d’optimiser chaque cycle machine. Lorsqu’on veut afficher une valeur sur un écran LCD, on a recours à des bibliothèques très avancées (comme l’excellente bibliothèque LVGL), et on n’a pas à se préoccuper des détails de conversion des valeurs binaires en décimal.

Il n’en a pas toujours été ainsi. Dans les années 80, à l’époque des Motorola 6800 et autres PIC (j’ai appris à programmer sur un PIC !), les fréquences d’horloge étaient de l’ordre du MHz, avec des architectures 8 bits, pas de FPU, etc.
Pour essayer de mettre des chiffres sur ces évolutions, on est passé d’environ 0,001 MFLOPS à plus de 100 MFLOPS sur les microcontrôleurs d’aujourd’hui à 3 euros. Un 386 était composé de 275 000 transistors, un processeur moderne d’environ 10 milliard de transistors. Un rapport 10000 donc…

Un autre monde ! Les ressources matérielles étaient tellement restreintes que ces microcontrôleurs étaient programmés en assembleur, et chaque cycle d’horloge était critique pour les « gros » développements. Je pense notamment à Mario Bros et aux premiers jeux NES, écrits intégralement en assembleur (quel travail !). C’est d’ailleurs dingue de penser qu’un tel jeu tenait dans 32 Ko de programme seulement...

À cette époque, il fallait être astucieux, faire beaucoup avec peu. C’est dans cette logique que l’algorithme Double Dabble a été développé.

Présentation de l’algorithme Double Dabble

L’algorithme Double Dabble est une méthode efficace pour convertir un nombre binaire en Code Décimal Binaire (BCD). Le BCD est un système où chaque chiffre décimal est représenté par son équivalent binaire sur 4 bits. C’est une étape préliminaire à l’affichage d’un sprite correspondant au bon chiffre par exemple. Ou l’allumage des bonnes LED sur un afficheurs 7 segments…

Cet algorithme est particulièrement efficace car il évite les divisions ou multiplications coûteuses par 10 nécessaires pour une conversion directe du binaire en décimal.
Il fonctionne en utilisant principalement deux opérations : le décalage de bits du nombre à convertir vers la droite (qui s’exécute généralement en un seul cycle d’horloge). Il y a autant d’itérations que de bit à traiter. Et une addition si une condition est remplie.
Il est facile à coder en assembleur, le langage privilégié à l'époque pour sa proximité avec le matériel et son efficacité.

Exemple d’application

On admet deux ensembles dans le registre : les bits constituant le nombre à convertir et le reste des bits qui sont initialement à zéro. Par exemple, avec le nombre 11110011 (243 en base 10), le registre se présenterait au début comme suit :

En partant du registre initial, l'algorithme effectue n itérations (soit 8 dans l'exemple). À chaque itération, le registre est décalé d'un bit vers la gauche. Avant d'effectuer cette opération, la partie au format BCD est analysée, décimale par décimale. Si une décimale en BCD (4 bits) est plus grande que 4 alors on lui ajoute 3. Cet incrément permet de s'assurer qu'une valeur de 5, après incrémentation et décalage, devient 16 et se propage correctement à la décimale suivante.

Les étapes complètes dans le cas de 243 :

La suite de 0 à gauche du nombre va progressivement recevoir le résultat du calcul qui sera codé en BCD. Chaque nibble (4 bits) constitue une décimale, par exemple le nombre 127 est codé comme suit :

Dans le cas du nombre 243, on s'attend à obtenir ceci à gauche du registre :

Au total, 8 décalages ont été effectués et la partie de droite s'est vidée. À gauche du registre, on obtient le résultat en BCD comme attendu :

L’algorithme Double Dabble est un témoignage de l'ingéniosité des ingénieurs face aux contraintes matérielles sévères. Il y avait une forme de poésie dans ces contraintes, une élégance technique qui transparaissait dans les jeux de l'époque. C'est cette esthétique, née de la limitation, qui je crois continue de fasciner encore aujourd'hui.
La créativité s'exprime lorsque elle rencontre des limitations. Si je me permettais des propos un peu "réac", je dirais que les triples A d'aujourd'hui en sont un triste exemple : on a l'impression de toujours jouer au même jeu.