Triceraprog
La programmation depuis le Crétacé

  • VG5000µ, SetPoint en ASM, diviser par 3 sans diviser ()

    Les trois derniers articles sur la division on permit de s'attarder sur trois manière de diviser un nombre entier par 3.

    La méthode de cet article, qui sera le dernier avant de revenir à l'affichage d'un point, va diviser grâce à, globalement, une seule addition. Oui ! Une seule addition.

    L'idée

    Au tout début de la série d'articles sur la division, j'ai mis en place un système de tests pour m'assurer que mes bouts d'assembleurs faisaient ce qu'il étaient censés faire. Et pour cela, je comparais une série de divisions avec un tableau de résultats.

    Mais alors, pourquoi ne pas utiliser un tableau de résultats directement ? On stock quelque part le résultat de toutes les divisions par 3 des nombres entiers de 0 à 255, et on va piocher dedans. Facile à implémenter, ultra rapide.

    La contrepartie, évidemment, c'est que cela va prendre un peu de place. Mais voyons ce que cela donne.

    Le code

    Nul besoin d'une longue explication pour cette méthode. L'entier à diviser (le dividende) est dans le registre A, on l'ajoute à l'adresse du tableau des résultats pré-calculés, on récupère la valeur dans A et voilà !

    div3_5:                         ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
            exx                     ; Utilisation des registres secondaires
            ld      hl,div3_table   ; Chargement dans HL de l'adresse de la table des résultats
            ld      b,0             ; Mise à 0 de B
            ld      c,a             ; Placement de la valeur de A dans C
                                    ; On a donc à présent le registre BC qui contient le dividende
            add     hl,bc           ; Addition du dividende et de l'adresse du tableau
            ld      a,(hl)          ; Récupération du résultat
    
            exx                     ; Échange des registres secondaires
            ret                     ; Retour à l'appelant.
    
    div3_table:                     ; La table des résultats
            defb    0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5
            defb    6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,11
            defb    12,12,12,13,13,13,14,14,14,15,15,15,16,16,16,17,17,17
            defb    18,18,18,19,19,19,20,20,20,21,21,21,22,22,22,23,23,23
            defb    24,24,24,25,25,25,26,26,26,27,27,27,28,28,28,29,29,29
            defb    30,30,30,31,31,31,32,32,32,33,33,33,34,34,34,35,35,35
            defb    36,36,36,37,37,37,38,38,38,39,39,39,40,40,40,41,41,41
            defb    42,42,42,43,43,43,44,44,44,45,45,45,46,46,46,47,47,47
            defb    48,48,48,49,49,49,50,50,50,51,51,51,52,52,52,53,53,53
            defb    54,54,54,55,55,55,56,56,56,57,57,57,58,58,58,59,59,59
            defb    60,60,60,61,61,61,62,62,62,63,63,63,64,64,64,65,65,65
            defb    66,66,66,67,67,67,68,68,68,69,69,69,70,70,70,71,71,71
            defb    72,72,72,73,73,73,74,74,74,75,75,75,76,76,76,77,77,77
            defb    78,78,78,79,79,79,80,80,80,81,81,81,82,82,82,83,83,83
            defb    84,84,84,85,85,85
    

    Les instructions utilisées

    Il n'y a pas vraiment de nouvelles instructions utilisées ici, mais de nouvelles formes :

    • Comme on ne peut pas additionner directement les registres HL et A, on doit passer la valeur de A dans un registre 16 bits. BC est souvent utilisé, mais ça aurait pu être DE.
    • Comme on ne peut pas charger le contenu de A directement dans BC, on le fait en deux étapes. Le registre 16 bits BC est constitué des deux registres 8 bits B et C. On place donc 0 dans B et C prend la valeur de A.
    • LD A,(HL) récupère la valeur pointée par le registre HL, plutôt que la valeur de HL. C'est-à-dire que l'octet à l'adresse mémoire pointée par HL est récupérée, puis chargé dans A.

    C'est mieux du coup ?

    D'un point de vu code de la fonction elle-même, c'est nettement mieux, 11 octets seulement. Par contre suivi d'un tableau de 255 octets. C'est donc à la fois le code le plus concis jusqu'à maintenant, mais aussi la fonction la plus grosse dans sa globalité.

    Il est possible cependant de la réduire dans le cas présent. En effet, comme on ne divise que des numéros de lignes, on pourrait s'arrêter à 75 résultats. Cela donne 86 octets, c'est toujours plus imposant que les autres versions, mais un peu mieux.

    Attention aussi, l'accès au tableau n'est pas protégé. S´il est plus petit que 255, rien n'empêche l'appelant de passer une valeur qui va déborder. Cela donnera des résultats faux.

    D'un point de vu rapidité c'est constant et rapide : 15 cycles. Comme c'est une fonction très courte, il est possible aussi, au besoin, de l'inliner, c'est-à-dire de faire l'opération à l'endroit où elle est nécessaire plutôt que d'appeler une fonction. Cela économise le temps de mise en place et de retour de la fonction (les EXX et RET). On tombe alors à 10 cycles, que l'on peut potentiellement améliorer en utilisant les valeurs de registres au moment de l'appel.

    Difficile de faire plus rapide comme méthode (à quelques astuces potentielles prêt).

    Que choisir ?

    C'est la question. Nous voici avec quatre méthodes pour diviser par trois. Deux sont des méthodes générales de division, deux sont spécialisées dans la division par 3. La première question à se poser est donc de savoir de quoi on a besoin.

    Ensuite, nous avons des fonctions qui ont des compromis en terme de taille et de rapidité.

    C'est ici qu´utiliser une fonction s'avère utile. Pour le moment, le choix n'a pas d'importance. Les quatre fonctions demandent un dividende dans A et retournent le résultat dans A. Il est donc possible de remplacer l'une par l'autre et de continuer le développement de l'affichage du point.

    Il sera temps, ensuite, de choisir quelle méthode sera la plus adéquate.

    Spoiler : probablement aucune de celles-ci en l'état, car nous allons avoir besoin du reste de la division par 3...

    À la prochaine !


  • VG5000µ, SetPoint en ASM, diviser encore plus vite ()

    Dans le dernier article, j'avais cherché une version plus rapide pour effectuer une division par 3, toujours dans l'optique d'afficher un point à l'écran en transcrivant la routine écrite en BASIC vers de l'assembleur Z80.

    Le résultat était mitigé : une routine en moyenne plus rapide et plus stable, mais sur le domaine de définition considéré (le nombre de lignes graphiques du VG5000µ), pas entièrement gagnante.

    Dans cet article, je vais donc étudier une autre manière de faire, un peu différente. Alors que les deux premières implémentations permettait de diviser par n'importe quel nombre de 1 à 255, cette nouvelle version est spécialisée dans la division par 3.

    Est-ce que cette spécialisation permettra de gagner en performance et/ou en taille ?


    L'idée

    Le Z80 n'a pas d'instruction pour diviser de manière générale, cela a déjà été mentionné dans les articles précédents. Par contre, il est tout à fait possible de diviser par des multiples de 2. Il suffit de décaler un nombre d'un bit vers la droite pour diviser un nombre entier codé en binaire par 2.

    Exemple :

    \(00010010_{2}\) (18 en base 10) décalé vers la droite une fois donne \(00001001_{2}\) (9 en base 10).

    Il faut donc trouver une manière d'exprimer une division par trois à partir de divisions par des multiples de 2 aidées d’additions ou soustractions.

    Le calcul est le suivant : on remarque tout d'abord que n'importe quel nombre entier n peut s'écrire sous la forme \(n = 4\times a + b\), avec \(b\) inférieur à 4. Autrement dit, sous forme d'une division par 4 plus le reste de la division entière. Trouver \(a\) et \(b\) est donc simple. \(a\) est le résultat de la division entière (quotient) de \(n\) par \(4\). \(b\) le reste de la division entière de \(n\) par \(4\).

    Sous cette forme, par exemple, \(15\) s'écrit \(4\times3 + 3\).

    Puisque l'on veut diviser n par 3, écrivons le résultat à partir de cette forme \(\frac{n}{3} = \frac{4\times a + b}{3}\)

    On n'est pas très avancé, il faudrait trouver dans l'expression un terme ou une forme que l'on connaît déjà qui nous permettrait de converger vers le résultat.

    Sortons \(a\) de la fraction : \(\frac{n}{3} = \frac{3\times a}{3} + \frac{a + b}{3} = a + \frac{a + b}{3}\).

    Ça c'est intéressant. Le résultat que l'on cherche est égal à \(a\), donc le résultat de la division par \(4\) additionné à... un quelque chose. Et ce quelque chose est un nombre que l'on voudrait diviser par 3 !

    Appelons ce nombre \(n_{1}\), cela donne : \(\frac{n}{3} = a + \frac{n_{1}}{3}\).

    Ce terme \(\frac{n_{1}}{3}\) peut lui-même être écrit sous la forme : \(\frac{n_{1}}{3} = \frac{4\times a_{1} + b_{1}}{3} = a_{1} + \frac{a_{1} + b_{1}}{3}\), c'est-à-dire sous la forme d'une division par 4 de \(n_{1}\) et d'un quelque chose d'autre.

    Et ainsi de suite... Jusqu'à ce que \(n_{i}\) soit inférieur ou égal à 3. Dans ce cas, il y a deux cas : soit \(n_{i} = 3\) et diviser ce nombre par \(3\) donne \(1\). Soit \(n_{i} < 3\) et ce nombre divisé par \(3\) donne \(0\).


    Exemple

    Revoyons l'exemple avec 15 (pour plus de cohérence, j'ajoute l'indice 0 aux premiers termes) :

    \(\frac{15}{3} = \frac{4\times a_{0} + b_{0}}{3}\). On trouve les termes de la division par 4 : \(a_{0} = 3\), \(b_{0} = 3\)

    Donc \(\frac{15}{3} = 3 + \frac{3 + 3}{3} = 3 + n_{1}\).

    Il s'agit donc à présent de trouver \(\frac{n_{1}}{3} = \frac{3 + 3}{3} = \frac{6}{3} = \frac{4 \times a_{1} + b_{1}}{3}\).

    Comme \(6 = 4 \times 1 + 2\), on a \(a_{1} = 1\) et \(b_{1} = 2\).

    Donc \(\frac{n_{1}}{3} = 1 + \frac{1 + 2}{3} = 1 + \frac{3}{3}\). On est dans le cas où le nombre restant est égal à \(3\), on sait calculer facilement sa division par \(3\), c'est \(1\).

    Si on remonte tout ça dans l'expression initiale on a donc :

    \(\frac{15}{3} = 3 + (1 + (1)) = 5\)


    L'implémentation

    Pour cette implémentation, mis à part le dividende, nous avons besoin :

    • d'un résultat intermédiaire dans lequel on va additionner les différents termes \(a_{i}\) au fur et à mesure des itérations
      • dans l'exemple précédent, on y mettra la première fois \(3\), puis on y additionnera \(1\)
      • j'utiliserai pour ça le registre E.
    • d'un dividende intermédiaire à diviser par 3 (les termes \(n_{i}\))
      • ce nombre est le dividende donné au début
      • puis il est remplacé par la somme du quotient et du reste de la division par 4 du dividende actuel
      • j'utiliserai pour ça le registre A.


    J'aurai aussi besoin d'autres registres pour la division intermédiaire par 4.

    Les opérations seront :

    • Tant que le dividende actuel (A) est supérieur à 3 :
      • On sauve le dividende dans B.
      • On divise A par 4 (stocké temporairement dans D)
      • On ajoute A au résultat intermédiaire E
      • On récupère le dividende depuis B vers A
      • On prend le reste de la division de A par 4, qui reste dans A
      • On ajoute D à A, ce qui donne le nouveau dividende A
    • Si A est égal à 3, on ajoute 1 au résultat E. Sinon rien.


    Cette valse des registres est nécessaire car quelques opérations opérations utilisées ne sont possible, sur Z80, que sur l'accumulateur, et pas sur les autres registres.


    Le code

    div3_4:                         ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
            exx                     ; Utilisation des registres secondaires
            ld      c,3             ; Initialisation du diviseur
                                    ; Il est fixe dans cette implémentation
                                    ; mais est nécessaire pour la comparaison
            ld      e,0             ; Initialisation du résultat
    
    div3_4_loop:
            cp      c               ; Comparaison de `C` et `A`
                                    ; le registre `A` est implicite, le Z80
                                    ; ne peut comparer qu'avec le registre A
            jr      c,div3_4_exit   ; Branchement si A est inférieur à C (donc A < 3)
            jr      z,div3_4_end    ; Branchement si A est égal à C (donc A = 3)
    
    div3_4_cont:
            ld      b,a             ; A est sauvé dans B
            srl     a               ; A est décalé d'un bit vers la droite
            srl     a               ; A est décalé d'un bit vers la droite
                                    ; Ces deux décalages forment une division par 4
            ld      d,a             ; Le résultat de la division entière est
                                    ; stockée dans D
            ld      a,e             ; A prend la valeur du résultat intermédiaire A
                                    ; C'est nécessaire pour faire l'addition suivante.
                                    ; Le Z80 ne sait additionner qu'avec l'accumulateur
                                    ; quand on traite des valeurs sur 8 bits.
            add     a,d             ; On ajoute le résultat de la division et
                                    ; le résultat intermédiaire.
            ld      e,a             ; Ce résultat intermédiaire et remis dans E
            ld      a,b             ; Le dividende actuel est mis dans A afin de faire
                                    ; l'opération suivante.
            and     $03             ; Calcul du reste de la division par 4
            add     a,d             ; On ajoute à ce reste le quotient de la division
                                    ; Et donc A contient le nouveau dividende.
            jr      div3_4_loop     ; C'est donc reparti pour un tour.
    
    div3_4_end:
            inc     e               ; On arrive ici si le dernier dividende est 3.
                                    ; dans ce cas, on ajoute 1 au résultat final.
    div3_4_exit:
            ld      a,e             ; Le résultat final est stocké 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 :

    • srl décale le registre indiqué de 1 bit vers la droite. Le bit sortant est stocké dans le drapeau de retenu, mais ici, on ne l'utilise pas.
    • and effectue une opération bit à bit entre l'accumulateur et l'opérande. Le résultat de chaque bit est 1 uniquement si les bits de chaque terme étaient 1 sur la même position.
      • Exemple : 11111000 and 00011111 donne 00011000, car seuls le 2 bits centraux sont à 1 dans les deux termes.
      • Ici, on s'en sert pour prendre le reste de la division par 4. Pourquoi est-ce que ça donne ce résultat est laissé en exercice.

    Bon alors, c'est mieux ?

    Un petit calcul donne pour cette troisième version :

    • 29 octets. Encore plus grand.
    • Le nombre d'étapes maximum à faire donne 84 cycles. C'est un peu mieux. Dans le domaine de définition de l'affichage d'un point, le nombre à diviser le plus grand est 75, et cela donne alors 56 cycles.


    Ce qui fait que la première version n'est plus rapide que pour les nombres jusqu'à 5. Cette version est intéressante et offre un bon compromis entre taille du code et vitesse d'exécution. Au détriment de la flexibilité, puisque le calcul n'est valable que pour une division par 3.

    Le principe de l'algorithme pourrait être étendu à plus de nombres, mais au prix d'un taille plus grande et d'un fonctionnement un petit peu plus long. De toute façon ici, on ne s’intéresse qu'à une division par 3.

    La fois prochaine, on verra une dernière manière de faire, et puis on reviendra à l'étape suivante de l'affichage d'un point.


  • VG5000µ, SetPoint en ASM, diviser plus vite ()

    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.


  • Visite au Computer History Museum ()

    La semaine dernière, profitant d'un voyage à San Francisco, j'ai allongé un peu mon séjour pour pousser jusqu'à Mountain View et aller visiter un musée qui semblait fort intéressant. Le Musée de l'Histoire des Ordinateurs, ou dans le texte « Computer History Museum »

    Dépliant du musée

    Première chose à savoir si vous êtes à San Francisco même, que vous choisissiez le train (pas cher, mais long, avec changement) ou la voiture (plus cher, un peu moins long), prévoyez le trajet pour ne pas arriver trop tard. En effet, le musée ferme assez tôt : 17h.

    En voiture, tant qu'à visiter, vous pourrez faire un détour par la 280 pour passer par des endroits sympas ou la 1 pour des endroits encore plus sympa, à l'aller ou au retour. Ou opter par la 101 pour aller au plus direct (mais potentiellement aussi plus encombrée, vérifiez avant de partir).

    De notre côté (puisque nous étions deux), nous avons opté par un peu de balade sur le chemin.

    La plage

    Arrivé au musée et ayant acquitté notre droit d'entrée, après une petite explication de l'agencement à l'accueil et la remise d'un plan, nous voici parti pour une aventure d'environ quatre heures.

    Coup de bol ? Ce jour là, des étudiants du coin faisaient une démonstration à l'entrée d'appareils fonctionnels et d'artefacts divers (comme un reste de Silicon après découpage de Wafers). Les visiteurs pouvaient donc goûter au plaisir de perforation d'une carte (c'est un plaisir quand c'est dans un musée...).

    Performation de carte

    Puis la visite commence. Un petit film d'introduction peut être visionné, mais je ne l'ai pas fait, j'avais hâte de voir du concret.

    L'exposition principale est divisée en 20 zones thématiques et globalement chronologique. Globalement car les époques recouvertes par les thèmes se superposent dans l'histoire des ordinateurs. La première zone est consacrée au calcul, le besoin initial à la base de tout ça. Règles à calcul, bouliers (que l'on peut manipuler), métier de « calculateur » permettant de dresser les tables de fonctions.

    Règle à calcul

    Mais encore calculatrices, mécaniques tout d'abord puis électroniques (mais non programmables). Et que serait cet endroit sans la réplique de la sous-partie de démonstration de la Machine à Différences de Charles Babbage ? Près de là, les plans de la Machine Analytique du même inventeur, bien entendu avec mention des travaux d'Ada Lovelace.

    Machine à Différences

    Suit un très intéressant reportage sur la culture d'entreprise d'IBM au début du XXième siècle. Le musée est comme cela ponctué de nombreux reportages ou extraits de films, interviews et reportages d'époque. Il y en a vraiment beaucoup et malgré les quatre heures de visite, je n'ai pas tout pu regarder.

    Ce passage est dans la zone 2, consacrée aux cartes perforées, dont IBM fut un grand fournisseur.

    IBM, think

    De là, on passe en zone 3, consacrée aux calculateurs analogiques et des « batailles » qui s'ensuivent entre les modèles numériques et les modèles analogiques, ainsi que des fusions entre les deux systèmes.

    Une machine analogique câblée nous montre bien la similitude avec l'état de certaines bases de code actuelles...

    Calculateur Analogique


    Peut-être préférez-vous le câblage suivant.

    Autre calculateur Analogique


    Les zones suivantes sont consacrées à la naissance des ordinateurs ainsi qu'à l'histoire des premières compagnies à se lancer dans le secteur. On y trouve quelques ordinateurs à lampes de dimensions conséquentes, comme des morceaux d'ENIAC.

    Le musée présente aussi des blocs de bases d'un ordinateur dans leurs formes d'alors, et rappellent que des pistes initiales se tournaient vers la mécanique. Sur l'image suivante, une porte logique mécanique à gauche (a priori un inverseur), et une additionneur/soustracteur à lampe à droite.

    Portes


    La zone suivante, la 6, nous amène aux besoins de calculs en temps réel et nous rappelle les besoins de l'armée, toujours très gourmande en calculs pour la balistique. Et très avide d'information à des fins de surveillance dans une époque de guerre froide. Des éléments du système SAGE sont exposés.

    Système SAGE


    Tout cela demande de la puissance de calcul grandissante, et nous entrons à présent dans la zone 7, dédiée aux Mainframes. L'IBM 360 y trône en bonne place, avec ses beaux dérouleurs de bande rouge et bleus.

    IBM 360


    Et avec des possibilités de calculs grandissante vient les besoins en stockage grandissants eux aussi. La zone 8 s'intéresse à la mémoire, qu'elle soit persistante ou non. En partant de quelques artefacts très lointains, comme un système de stockage d'information Inca utilisant des cordes, on arrive sur des systèmes plus récents. Un mur de stockage présente de nombreux systèmes : lecteurs de disquettes, cartouches, cassettes, disques magnétiques...

    Tout ça, c'est bien beau, mais sans logiciel, cela ne va pas bien loin. C'est la zone 9 qui présente la programmation. Le musée est principalement focalisé sur le matériel, et si le logiciel est toujours dans l'air, ce n'est pas sont point central (voir plus loin pour la section déportée du musée). À un mur, une fresque généalogique des différents langages de programmation s’étale sur quelques mètres. C'est une version cependant très simplifiée, même si les jalons essentiels sont là.

    Une film explicatif constitue la principale attraction de la zone. Il faut dire que ce n'est pas si évident de montrer du logiciel dans un contexte de vieilles machines dont la plupart ne fonctionnent pas et qui étaient utilisées principalement pour des calculs scientifiques, militaires et des traitements administratifs.

    Ah si, tout de même, un badge DECUS rappelle que le principe du partage de logiciel via des sources de code ouvertes ne date pas d'hier, puisque le groupe a été créé en 1961 et que la pratique le précédait.

    DECUS


    Si les Mainframes, c'était du trop petit pour vous, la zone 10 en remet une couche avec une présentation de Super Ordinateurs. Forcément, vu la place que cela prend, il n'y a pas beaucoup de pièces. On y trouve aussi un cluster de PCs. Bien entendu, que serait une section Super Ordinateurs sans Cray.

    Un film rapide retrace au passage la vie de Seymour Cray et des particularités de ses ordinateurs.

    Cray


    Ils ont plein de petites LEDs qui clignotent et des petits leviers tous sympas, ils sont tout minis se sont les... Minis Ordinateurs de la zone 11. Des PDP-8, PDP-11, du HP, du CDC, un modèle de PDP-8 qui a servi pour des opérations chirurgicales du cerveau et a permis d'effectuer celles-ci avec endormissement du patient (car donc, apparemment, auparavant, le patient devait rester réveillé...)

    PDP-8

    Bien évidemment, la section évoque UNIX et présente un manuel d'époque.

    Puis l'on passe en zone 12, consacré à la logique numérique au cœur du fonctionnement de toutes ces machines jusqu'à nos tablettes et téléphones actuels. Quelques portes logiques peuvent être actionnées avec des interrupteurs (dommage, le Flip Flop ne fonctionnait pas à cause d'un bouton défectueux). Un film présente les étapes de fabrication d'un circuit intégré, et l'on peut regarder à la loupe plusieurs générations de ces puces. Quelques wafers de différentes tailles accompagnent le tout.

    La zone 13 est consacrée à la robotique et à l'intelligence artificielle, avec de nombreux robots vintage en exposition. Mes photos de cette section étant toutes floues, passons.

    En zone 14, on découvre la thématique de la création artistique à travers l'outil informatique. Ici, à côté d'un cube de PIXAR, de système SUN, de tables traçantes et de synthétiseurs, on trouve une machine au logo qui aura marqué une époque en image numérique.

    Silicon Graphic


    J'y ai découvert aussi un accessoire pour Commodore 64 que je ne connaissais pas du tout. Le Incredible Music Keyboard, qui se place au dessus de la coque d'un C64 pour le transformer en synthétiseur. J'aurais du mieux regarder la chaîne 8-Bit Keys, qui en fait une présentation.

    Incredible Music Keyboard


    La zone 15 s'intéresse au périphériques d'entrées et sorties. Le coin est plutôt fourni en périphériques exotiques, dont beaucoup étaient des idées... intéressantes. Et dont d'autres ont eu plus de succès. Et quoi de mieux pour accueillir le visiteur dans cette zone que le très à propos Xerox Alto.

    Xerox Alto


    La zone 16 est consacrée aux jeux vidéo. Pas de trucs renversants à ce niveau-là, beaucoup de musées de vieilleries informatiques se focalisant essentiellement sur le matériel de jeu, il est difficile de faire original. Trois pods de démonstrations permettent de jouer à des jeux assez différents : un jeu d'aventure textuel, Spacewar! et PAC-MAN. Les trois en « reproduction » (plutôt des recréations que de l'émulation j'ai l'impression... mais je n'en sais rien).

    Bref, passons ici aussi.

    La zone 17 présente l'ordinateur personnel. Le Micro, ça y est, l'ère grand public (ou presque) commence. C'est un IBM PC qui nous reçoit dans la zone. Vu la taille de ces nouvelles machines, de nombreuses pièces différentes sont présentées. Apple I et II, TRS-80, Commodore PET, Atari 800XL, Lisa,...

    IBM PC

    Mais aussi de l'exotisme (vu des Etats-Unis), avec un Smaky, un Amstrad 464, du Spectrum,... Un clone russe de ZX Spectrum.

    Et un Thomson TO7-70 ! Malheureusement un peu dans l'ombre.

    Thomson TO7-70


    Et puisqu'on est dans l'ordinateur français, un petit Micral.

    Micral

    Toute une partie est à l'honneur du Do It Yourself de l'époque : ces machines que l'on pouvait recevoir en kit, ou bien dont on ne recevait que des parties essentielles, à compléter ensuite, en suivant éventuellement un plan dans un magazine.

    Ici, un Altaïr 8800 côtoie (mais de pas trop près) un Imsai 8080. Mais aussi un EDUC-8 Australien (que je ne connaissais pas), une carte KIM-1 et de nombreux autres.

    Altair 8800


    De la zone 17 on passe à la zone... 18 ! Celle-ci présente l'informatique mobile. En partant des portatifs initiaux (et de publicités où l'on voit des utilisateurs suer avec le sourire en traînant une mallette de plomb signe de leur modernité), on passe par les ordinateurs portables de différentes époques et les organiseurs personnels.

    Le pôle interactif offre de soulever un Osborne 1 dans sa malette, pour juger du temps pendant lequel nous aurions pu garder le sourire en se baladant avec. On est loin des quelques centaines de grammes de tablettes actuelles.

    La zone 19 présente la mise en réseau, en commençant par le commencement : la mise en relation de personnes à distance. Télégraphe, puis téléphone, avec des cartes de l'évolution des lignes reliant les continents.

    Un petit bouton permet de retrouver le délicieux son d'une communication entre ordinateurs via Modem.

    Modem


    Est exposée aussi une des premières armoire à serveurs de Google, tout un tas de modems, de routeurs et autres matériels de communication. Des initiatives aussi, comme les ordinateurs communautaires hippies.

    Côtés ordinateurs associés à cette thématique, un NeXT Cube, mais aussi un Minitel, expliquant que bien avant l'essor grand public d'Internet, en France, il était possible d'aller chercher des renseignements en ligne ou de réserver un train.

    Minitel

    La dernière zone, la vingtième est une zone tournée vers l'avenir. Principalement un film interviewant quelques personnalités de la Silicon Valley. J'avoue ne pas l'avoir regardé. on sort avec cette zone de l'Histoire pour entrer dans l'actuel, et l'actuel est tous les jours.

    C'est ainsi que se termine la visite de l'exposition principale. Mais pas du musée.


    PDP-1 et Spacewars!

    Si la quasi totalité des machines exposées ne sont pas en fonctionnement, le musée possède deux salles consacrées à deux machines emblématiques restaurées et en état de fonctionnement.

    La première salle est celle du PDP-1.

    La vénérable machine n'est cependant allumée que deux fois par mois à un horaire bien précis... Et le jour de ma visite n'était pas un jour de démonstration. C'est dommage, mais tant pis.

    La démonstration consiste, entre autre, à lancer le jeu Spacewars! Il est même possible d'y jouer, avec des contrôles déportés dans la zone visiteur. Le stylo optique est aussi fonctionnel.

    PDP-1


    IBM 1401

    La seconde salle est encore plus vaste et est utilisée pour une installation d'IBM 1401. Un film explique l'histoire de sa restauration, qui aura été longue et fastidieuse.

    Là encore, il faut tomber le bon jour et la bonne heure pour la démonstration. C'était le bon jour, mais nous sommes arrivés après la mise en route, qui a lieu le matin.

    Mais même éteinte, la machine est impressionnante.

    IBM 1401


    Le reste

    Et ce n'est pas fini. Mais le musée allait fermer 30 minutes après et j'ai parcouru le reste un peu plus rapidement. J'ai dédié la majeure partie du temps restant à l'exposition sur Ada Lovelace, qui présente quelques manuscrits de sa main et lettres de Charles Babbage à son attention. Qui retrace aussi en quelques panneaux sa vie.

    À côté, une mini expo sur les transports automatisés, qui me semble est surtout une excuse pour présenter la voiture toute ronde de chez Google.

    Le dernier grand espace est dédié au logiciel sous différents aspects : jeu, musique, image, connaissance, simulation, industrie textile. Chaque poste montre l'évolution du travail dans ces domaines avec l'arrivé de l'informatique. Par exemple en juxtaposant le développement de pellicule en chambre noir et Photoshop.

    Exposition plutôt bien faite, mais que j'ai traversée un peu en coup de vent. Je n'étais pas venu pour cela.

    Conclusion

    Ce musée est fantastique. Les quatre heures passées, nullement suffisante pour tout voir dans les détails, sont passées très rapidement. Beaucoup de pièces intéressantes, des explications, des films d'archive, des reportages,...

    Si vous passez dans le coin, n'hésitez-pas !


  • VG5000µ, SetPoint en ASM, diviser ()

    À présent que j'ai un garde fou pour vérifier que je ne fais pas d'erreur d'inattention, me voilà près à diviser des nombres. Pour rappel j'ai besoin de diviser des nombres afin de faire les calculs permettant d'affiche le bon pixel à l'écran.

    Pour second rappel, le Z80, au cœur du VG5000µ (et de beaucoup d'autres ordinateurs de l'époque) n'a pas d'instruction de division.

    La division

    Lorsque je divise de manière entière a par b, je veux trouver le nombre c tel quel \(c * b = a\). Comme la division ne tombe pas toujours juste, j'ai aussi un reste r tel que \(c * b + r = a\).

    Autrement dit, combien de fois dois-je additionner b pour obtenir a (au reste près). Une manière de trouver le résultat est de soustraire b à a autant de fois que l'on peut sans passer sous 0.

    Par exemple, \(\frac{21}{7}\) se trouve comme ceci :

    21 - 7 = 14
    14 - 7 =  7
     7 - 7 =  0
    

    Il y a trois soustractions, et donc \(\frac{21}{7} = 3\)

    Un autre exemple avec \(\frac{17}{3}\) :

    17 - 3 = 14
    14 - 3 = 11
    11 - 3 = 8
     8 - 3 = 5
     5 - 3 = 2
    

    Il y a cinq soustractions, et il reste 2 à la fin, dont la soustraction de 5 donnerait -3. On s'arrête donc et \(\frac{17}{3} = 5 + \frac{2}{3}\)

    Un problème majeur de cette façon de faire est que plus le résultat est grand, plus il a fallu de calculs pour le trouver. Si on divise de grands chiffres par de petits, cet algorithme est lent.

    Il est par contre très facile à programmer. La séquence donne ceci :

    • Mettre le dividende (le nombre à diviser) dans A
    • Mettre le diviseur dans C
    • Mettre 0 dans B
    • Tant que A est supérieur à C
      • Soustraire C à A et mettre le résultat dans A
      • Ajouter 1 à B
    • Le quotient (le résultat de la division entière) est dans B
    • Le reste de la division entière est dans A

    Implémentation par soustractions

    Il y a des limitations bien entendu à faire cette division sur des registres 8 bits. Je ne pourrai pas traiter des nombres supérieurs à 255. Pour afficher un point, je n'en ai pas besoin, c'est donc très bien.

    Tout d'abord, je renseigne mon système de tests avec mes nouvelles informations :

    div3_input_data:
            defb    0,2,10,21,255
    div3_reference_data:
            defb    0,0,3,7,85
    
    div3_params:
            defw    div3_input_data
            defw    div3_reference_data
            defw    div3
            defm    "DIV3\0"
    

    Et j'ajoute le test à la liste :

    test_suite:
            ld      hl,id_params
            call    prepare_test
    
            ld      hl,div2_params
            call    prepare_test
    
            ld      hl,div3_params
            call    prepare_test
    
            ret
    

    Ce qui me permet de mettre au point le code et le vérifier :

    div3:                   ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
            push    bc              ; J'utilise les registres B et C, je les préserve
                                    ; Le temps de l'opération
            ld      c,3             ; Le registre C contient le diviseur
            ld      b,0             ; Le compteur B est préparé pour retenir
                                    ; Le nombre de soustractions effectuées
    
    div3_loop:
            cp      c               ; A et C sont comparés
            jr      c,div3_end      ; Si A était plus petit que C, alors une retenue a eu lieu
                                    ; le calcul est terminé
                                    ; Attention, ici C signifie Carry (retenue)
    
            sub     c               ; C est soustrait de A
            inc     b               ; B est augmenté de 1
            jr      div3_loop       ; La boucle est relancée
    
    div3_end:
            ld      a,b             ; Le résultat de la division est dans B, il est placé dans A
                                    ; À noter que A contenait le reste de la division.
                                    ; Cela pourra être intéressant pour plus tard.
    
            pop     bc              ; Les registres B et C sont restaurés
            ret                     ; Et la fonction est terminée
    


    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 :

    • cp: permet de comparer le registre A (qui est implicite et donc non noté) et le registre indiqué (ici, C). La comparaison se fait par soustraction de A et du registre, mais le résultat n'est pas retenu, seuls les drapeaux de résultat de l'opération le sont. Ainsi, en cas d'égalité par exemple, le drapeau Z sera à 1 (Zéro, car la soustraction de deux nombres égaux donne zéro). Ici, on cherche s'il y a eu une retenue, ce qui indique que le nombre dans le registre spécifié était plus grand que le nombre dans A, et donc le résultat de la soustraction était négatif.
    • sub: effectue une soustraction simple. On avait précédemment vu sbc, qui faisait une soustraction en tenant compte de la retenue du calcul précédent. sub n'en tient pas compte et soustrait simplement le registre mentionné du registre A, qui est implicite.

    Résultat

    Voici donc une première implémentation de division par 3, qui peut être généralisée à une division par n'importe quel nombre (inférieur à 255)

    Pour référence futur, le code de la fonction nécessite 15 octets de langage machine. L'exécution de la fonction nécessite \(15 + 8 * q\) cycles processeur, où \(q\) est le quotient, résultat de la division. Au pire, pour \(\frac{255}{3}\), la fonction prend donc 695 cycles. Ce qui n'est pas négligeable.

    Nous verrons plus tard si l'on peut faire mieux.

    Affichage des résultats de tests dans MAME avec la division par 3


Page 1 / 10 (suivant) »