Triceraprog
La programmation depuis le Crétacé

Dans le dernier article, j'avais écrit une première manière d'effectuer une division, en spécialisant la routine pour une division par 3 puisque c'est ce qui m'intéresse pour afficher un point à l'écran du VG5000µ.

Pour référence, cette routine nécessitait 15 octets en mémoire et son exécution pouvait prendre jusqu'à 695 cycles, ce qui est plutôt grand.

Micro optimisation

La première optimisation est une micro optimisation. On appelle micro optimisation une amélioration de la routine par un détail de fonctionnement, plutôt que par une réflexion sur l'ensemble de la méthode.

Ici, l'idée est de remplacer le couple push bc / pop bc en début et fin de la routine par un couple exx / exx. L'instruction exx du Z80 effectue un renommage des registres BC, DE et HL. Ces registres (ainsi que d'autres, mais qui ne sont pas touchés par cette instruction) existent en deux exemplaires dans le Z80. Un exemplaire de chaque registre est utilisé pendant que l'autre ne l'est pas. Il est possible d'échanger les rôles de ces paires.

On peut imaginer un aiguillage devant les registres. Le flux de données est aiguillé soit vers l'un des registres de la paire, soit vers l'autre. L'instruction exx s'occupe de modifier l'aiguillage des registres BC, DE et HL. Les registres inactifs sont nommés BC', DE' et HL'.

Puisqu'en entrée de la routine, je n'utilise que le registre A, mais que j'ai besoin des autres registres pour les calculs, je peux préserver les valeurs que les registres ont en entrée de fonction en utilisant l'autre série de registres.

Les instructions push bc et pop bc prennent chacun 3 cycles à s'exécuter. exx n'en prend qu'un. On passe donc de 6 cycles à 2, pour un gain de 4.

Ce n'est pas grand chose par rapport au temps d'exécution de la routine elle-même, c'est donc une micro optimisation. Mais elle est simple à faire. La routine passe de 15 octets à 13.

Une autre micro optimisation consiste à éviter un test en initialisant B à -1 plutôt que 0. Mais comme ce n'est pas sur cette routine avec des micros optimisations que l'on va vraiment gagner, je laisse de côté.

Division comme à l'école

La première méthode de division, celle de l'article précédent, se faisait par soustractions successives. Tant que l'on pouvait soustraire le diviseur du dividende, on le faisait, tout en comptant le nombre de fois que cette soustraction était faite. Ce nombre de soustractions est le résultat de la division.

Ce n'est pas comme cela que vous avez appris à diviser à l'école. Si on a appris la même méthode, à quelque chose comme ce qui suit.

Pour diviser (en base 10), 424 par 3, on pose :

   421 | 3
       |---
       |
       |

Puis on regarde si l'on peut diviser le premier 4 du dividende par 3. Oui, cela donne 1. On pose donc 1 dans le résultat et le résultat de la soustraction sous le 4 :

   421 | 3
  -3   |---
   -   | 1
   1   |

On passe au chiffre suivant, que l'on descend au niveau du 1. Cela donne 12, que l'on essaye de diviser par 3. Ok, cela donne 4, que l'on note dans le résultat. Le reste de la soustraction est noté sur la gauche du trait vertical :

   421 | 3
  -3   |---
   -   | 14
   12  |
  -12  |
   --
    0

On passe au chiffre suivant, que l'on descend au niveau du 0. Cela donne 1. On essaye de diviser par 3. Cela donne 0, car 1 est plus petit que 3. On note donc 0 à la suite du résultat, on soustrait sur la gauche (on soustrait 0 du coup) :

   421 | 3
  -3   |---
   -   | 140
   12  |
  -12  |
   --
    01
   - 0
    --
     1

Il n'y a plus de chiffre à traiter au dividende. Le résultat de la division est dans 140, et le reste 1.

Faire une division avec cette méthode, c'est dérouler un algorithme. Et on peut transposer ça à l'ordinateur. On ne peut pas utiliser de division en base 10 puisque c'est exactement ce qu'on essaie ici d'implémenter. Mais sous forme binaire, le processeur a les instructions nécessaires.

Faisons un essai. Divisons $101_{2}$ par $10_{2}$ (en binaire, indiqué par le petit 2, donc 5 par 2 en décimal) selon la même méthode.

   101 | 10
       |----
       |

On commence donc par prendre $1_{2}$ et essayer de diviser par $10_{2}$. Mais... il n'y a pas d'instruction de division sur le Z80 ! Qu'à cela ne tienne, nous sommes en binaire, et les deux seuls résultats possibles en binaire sont $0_{2}$ et $1_{2}$.

Autrement dit, soit le nombre que l'on considère est plus petit que le diviseur et le résultat est $0_{2}$, ce qui implique que l'on ne soustrait rien du tout au dividende. Soit le résultat est $1_{2}$, ce qui implique que l'on soustrait le diviseur au dividende.

Puis on adjoint à ce résultat le chiffre binaire suivant.

Autrement dit, nous n'avons besoin que de décalages et de soustractions.

   101 | 10
  -0   |----
   -   | 0
   10

On considère donc $10_{2}$ qui n'est pas plus petit que le diviseur (il est même égal). Le résultat à retenir est donc 1 et l'on soustrait le diviseur :

   101 | 10
  -0   |----
   -   | 01
   10
  -10
   --
   001

On considère $1_{2}$, qui est plus petit que le diviseur. On ne soustrait donc rien, on note 0 et... c'est terminé.

   101 | 10
  -0   |----
   -   | 010
   10
  -10
   --
   001
    -0
     -
     1

Le résultat de $101_{2}$ divisé par $10_{2}$ est donc $10_{2}$, reste $1_{2}$. Soit en base 10 : 5 divisé par 2 est égal à 2 reste 1.

Algorithme

Pour implémenter cet algorithme, j'ai besoin de plusieurs choses:

• De quoi retenir le nombre à considérer en cours,
• De quoi retenir ce qu'il reste du dividende à considérer,
• Le diviseur,
• De quoi retenir le résultat en cours.

Pour se simplifier la vie, on va considérer les 8 bits du dividende, même s'ils commencent par des 0. Lorsque l'on pose une division manuellement, on sait que des zéros en début de nombre donnent des zéros en début de résultat. Aucun de ces zéros ne sont significatifs.

Pour notre calcul, il est plus simple de dérouler l'algorithme sur l'intégralité du nombre en binaire.

Cela donne donc cela:

• Initialiser un registre comme compteur de bits à 8 (on a 8 bits à traiter)
• Initialiser un registre contenant le diviseur
• Initialiser un registre contenant le dividende (il est initialement dans A, mais ce registre, l'accumulateur, va être nécessaire pour certaines opérations)
• Initialiser un registre à 0 pour retenir le reste

Ensuite, tant que le compteur de bits est positif, on déroule ce qui suit:

• On décale les bits du résultat de 1 vers la gauche en insérant un 0 à droite
  • par exemple, si le résultat est actuellement 101, il devient 1010
• On décale les bits du dividende de 1 vers la gauche aussi, en insérant un 0
  • même chose
• On décale les bits de l'accumulateur de 1 vers la gauche, mais en insérant cette fois le bit qui est sorti du dividende par la gauche lors de l'opération précédente
  • par exemple, si le dividende était 11000000, il a été décalé en 10000000 et le 1 est sorti
  • si l'accumulateur contenait 00000010, il est décalé en 00000101.
• On compare le contenu de l'accumulateur avec le diviseur.
• Si l'accumulateur est égal ou plus grand que le diviseur:
  • on soustrait le diviseur de l'accumulateur
  • on ajoute 1 au résultat courant
• Sinon, rien... vu qu'on a décalé le résultat, il contient un 0 en dernière position.
• On décrémente le compteur de bits.

Registres

Les registres utilisés sont les suivants :

• B est utilisé pour le compteur de bits.
  • C'est un choix naturel sur le Z80 qui permet d'utiliser l'instruction DJNZ qui décrémente B et fait un saut conditionnel si B n'est pas égal à 0.
• C contient le diviseur.
• D contient le dividende (il faut donc y transférer A).
• E contient le résultat (qu'il faut donc initialiser à 0).

Le code

div3_3:                         ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
        exx                     ; Utilisation des registres secondaires
        ld      b,8             ; Initialisation du compteur de bits à 8
        ld      c,3             ; Initialisation du diviseur
        ld      d,a             ; Transfert du dividende dans D
        xor     a               ; Mise à 0 de l'accumulateur
        ld      e,a             ; Mise à 0 du résultat

div3_3_loop:
        sla     e               ; Décalage de E vers la gauche
                                ; Le drapeau `Carry` contient le bit fort de E (qui est 0)
        sla     d               ; Décalage de D vers la gauche
                                ; Le drapeau `Carry` contient le bit fort de D
        rla                     ; Décalage de A vers la gauche, avec récupération de la
                                ; valeur de `Carry`
        cp      c               ; Comparaison de C et A
        jr      c,div3_3_skip   ; Si C est plus grand que A, saut plus loin
        sub     c               ; Sinon, A est réduit de la valeur de C
        inc     e               ; Et E est augmenté de 1
div3_3_skip:
        djnz    div3_3_loop     ; B est décrémenté et s'il n'est pas égal à 0,
                                ; on repart en début de boucle

div3_3_end:
        ld      a,e             ; Le résultat est transféré dans A

        exx                     ; Échange des registres secondaires
        ret                     ; Retour à l'appelant.

Les instructions utilisées

Les instructions déjà utilisées dans les articles précédents ne sont pas répétées ici, les nouvelles sont :

• exx a déjà été expliqué en début d'article sur la micro optimisation.
• xor effectue une opération de ou exclusif pour chaque bit de même position entre l'accumulateur et le registre mentionné.
  • Dans un ou exclusif, le résultat est 1 uniquement si l'on des deux bits est à 1.
  • C'est impossible ici puisque l'opération est effectuée entre l'accumulateur et... l'accumulateur.
  • Le résultat est de mettre l'accumulateur à 0.
  • C'est un idiome classique, car un LD A,0 prend deux octets en mémoire et deux cycles, alors que XOR A ne prend qu'un seul octet et 1 cycle.
• xor a suivi de ld ?,a entre registre. C'est aussi un schéma classique.
  • Transférer entre deux registres prend un octet et un cycle, on profite donc d'avoir initialisé l'accumulateur pour initialiser un autre registre à la même valeur de manière efficace.
• djnz, comme indiqué au-dessus, effectue plusieurs opérations. Tout d'abord, B est décrémenté. Puis si B est égal à zéro, l'instruction se termine. Sinon, un branchement à lieu à l'adresse indiquée en paramètre.

Et c'est mieux ?

Un petit calcul donne pour cette nouvelle version :

• 23 octets... c'est moins bien que 12 octets avec les deux micro optimisations, certes.
• Entre 103 et 111 cycles en fonction du nombre de 1 dans le résultat.

Niveau vitesse, c'est beaucoup moins qu'avant la méthode précédente ! La routine est peut-être deux fois plus grosse, mais elle est beaucoup plus stable en temps d'exécution et en moyenne plus rapide.

Oui mais attention ! Si elle est plus rapide dans le cas général, dans le cadre de l'affichage d'un point, le nombre maximal à diviser est 75. Et pour 75, la vitesse de la première version est de 215. En fait, pour tout dividende inférieur à 36, la première version de la division par 3 est plus rapide.

Note de fin d'article : on peut micro-optimiser le code ci-dessous en se passant de E et en stockant le résultat dans D au fur et à mesure de son décalage (qui libère de l'espace au fur et à mesure). Cela évite deux LD et un SLA, ce qui rend la fonction compétitive plutôt vers 34.