Triceraprog
La programmation depuis le Crétacé

  • VG5000µ, SetPoint en C ()

    Après cette implémentation en assembleur Z80 d'une fonction setpoint qui affiche, de manière assez basique, un point à l'écran, je me pose la question d'utiliser un langage de plus haut niveau... mais pas trop.

    J'ai une assez longue expérience du C et la question que je me pose est : qu'est-ce que ça donne de programmer en C pour générer du code sur Z80.

    Programmer en C a quelques avantages a priori : c'est nettement plus concis et lisible que de l'assembleur, j'y suis plus habitué et c'est portable sur de nombreuses plateformes. C'est le cas d'autres langages, mais le choix naturel pour moi puisque écrire du C m'est habituel. En tout cas bien plus habituel que d'écrire directement de l'assembleur Z80.

    Premier essai

    Voici le code C d'un premier essai :

    #include <stdint.h> // Afin d'utiliser les types standards
    
    void setpoint(uint16_t x, uint8_t y) // Définition de la fonction
                                         // En entrée, les coordonnées
                                         // Pas de valeur de retour (void)
    {
        const uint8_t zx = x / 2;       // Les mêmes calculs qu'en BASIC
        const uint8_t rx = x & 2;
    
        const uint8_t zy = y / 3;
        const uint8_t ry = y - (zy * 3);
    
        const uint8_t ch = 1 << (ry * 2 + rx);
    
        const uint16_t address = 0x4000 + zy * 80 + zx * 2;
        const uint8_t at = *((uint8_t*)address + 1);
    
        uint8_t old = 64;
    
        if (at & 0x80 == 0x80) {
            old = *((uint8_t*)address);
        }
    
        if (old & 0x80 == 0x80) {
            old = 64;
        }
    
        uint8_t new = ch | old;
    
        *((uint8_t*)address) = new;
        *((uint8_t*)address+1) = 224;
    }
    
    int main() // Je dois ajouter une fonction `main` pour que le fichier CRT puisse en trouver une.
    {
        return 0;
    }
    

    J'ai globalement laissé les mêmes noms de variable que j'ai utilisé dans la version BASIC, et les mêmes calculs. C'est un portage simple, sans trop se poser de questions.


    Le compilateur SCCZ80

    Afin de transformer le code C en code machine, il me faut un compilateur qui sache sortir du langage machine Z80. J'en connais deux, mais il en existe d'autres. Le premier fait parti de l'environnement complet z88dk et se nomme SCCZ80. L'autre est SDCC, pour Small Device C Compiler. Ce dernier peut générer du code pour de nombreux microprocesseurs. Il peut être aussi utilisé par l'environnement spécialisé z80 qu'est z88dk.

    Je commence avec SCCZ80 : zcc +vg5k -O3 -m c_setpoint_basic.c

    • +vg5k indique que à la suite que ma plateforme cible est un VG5000µ,
    • -O3 indique que je veux optimiser le code au niveau maximum,
    • -m indique que je veux générer un fichier avec des informations sur le résultat,
    • et enfin le nom du fichier en C.


    Pour que la compilation fonctionne, je dois ajouter une fonction main(). En effet, le CRT (C Run Time) va chercher cette fonction main() pour l'appeler au démarrage. Or pour utiliser la fonction -m du compilateur, je dois construire une application complète.

    Je pourrais tenter de compiler seulement le fichier .c en fichier objet (.o), malheureusement, comme on va le voir juste après, SCCZ80 appelle de nombreuses fonctions... Bref, c'est plus simple de faire une application complète.

    Et cela me permet d'aller voir dans le fichier .map la taille de la fonction setpoint telle que compilée pour ce compilateur.

    251 octets.

    La fonction écrite à la main fait 196 octets, fonctions de multiplication et division comprises. Ici, c'est 251 octets sans les appels aux nombreuses fonctions donc le compilateur se sert.


    Le compilateur SDCC

    Avant d'aller plus loin, un petit essai avec SDCC donne 125 octets, auquel il faut ajouter la fonction de division, 42 octets, pour un total de 167 octets. C'est beaucoup mieux. C'est même mieux que le code écrit directement en assembleur, qui ne l'oublions pas utilise une table assez importante pour la division. Le code manuel du setpoint hors appels de fonction reste plus petit.

    Par contre, SDCC fait grand usage des registres IX et IY. Et IX est strictement réservé par la ROM du VG5000µ, il faut l'utiliser avec des grandes précautions. Le fichier CRT du VG5000µ le préserve en sauvant sa valeur, et part du principe que l'on configure l'assembleur pour échanger l'utilisation de IY et IX (pour au final ne pas utiliser IX).


    Pourquoi c'est si gros ?

    Je reviens en premier lieu sur la compilation en SCCZ80. Ce compilateur part sur une stratégie : la compilation d'un programme entier doit donner un exécutable petit. Pour cela, les fonctions les plus courantes sont factorisées dans des routines assembleurs utilisées par le compilateur.

    C'est le cas par exemple pour les fonctions de division et de multiplication. Mais c'est aussi le cas pour des services comme « aller chercher un entier sur la pile », utile dans le modèle C pour le passage de paramètres aux fonctions.

    En regardant le code généré, on peut voir aussi beaucoup de manipulations de registres pour essayer de faire les calculs sur 8 bits que je demande. Ça à l'air un peu trop complexe. Et si on essayait de partir sur une base de calculs en 16 bits ?

    Pour cela, je change les types uint8_t du code source ci-dessus en uint16_t.

    216 octets ! Voici qui est beaucoup mieux.

    Le compilateur SCCZ80 a donc l'air de mieux travailler avec des entiers de 16 bits. Cela est en partie du à l'utilisation de ces routines annexes, qui sont écrites avec un modèle sur 16 bits en tête. En demandant des calculs sur 8 bits, j'oblige le compilateur à sans cesse passer de 8 à 16 bits et inversement.

    Et SDCC ? ... 183 octets. Là, ce n'est pas bon. De son côté, SDCC était plus efficace à faire ses opérations sur du 8 bits.

    SDCC contrairement à SCCZ80, a pour objectif principal la vitesse d'exécution, quitte à avoir du code machine plus gros. Pour cela, certaines stratégies sont employées. Ici, tous les calculs sont faits sur place, avec des manipulations de registres, à l'exception notable de la division.

    Du coup, travailler sur les registres 16 bits est un peu plus compliqué et cela a un impact direct sur la taille du code.


    Est-ce qu'on peut aider ?

    Première idée, puisque SDCC passe beaucoup de temps à récupérer les arguments de la fonctions, c'est de repasser ceux-ci sur 8 bits.

    void setpoint(uint8_t x, uint8_t y)
    

    Avec moins d'instruction d'accès à la pile, on fait gagner 10 octets à SDCC. Pas négligeable. Côté SCCZ80, c'est un gain de 3 octets. C'est toujours ça.

    On peut aussi aider en utilisant une fonction de division par 3 spécialisé, comme en assembleur, sous cette forme :

    static uint8_t div3_table[] = {
        0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,
        6,6,6,7,7,7,8,8,8,9,9,9,10,10,10,11,11,11,
        12,12,12,13,13,13,14,14,14,15,15,15,16,16,16,17,17,17,
        18,18,18,19,19,19,20,20,20,21,21,21,22,22,22,23,23,23
    };
    
    uint8_t div3(uint8_t dividend)
    {
        return div3_table[dividend];
    }
    

    La fonction de division générique utilisée pour SCCZ80 fait 37 octets et pour SDCC, 42 octets. La fonction par tableau utilisée ici est plus grosse, mais plus rapide.

    Côté SCCZ80, on descend à 212 octets... Soit 1 octet de gain. Pas top. Côté SDCC, ça remonte même à 177 octets (ou 176 en jouant sur les tailles des types entiers).


    Conventions d'appel

    Lorsque l'on appelle une fonction avec des paramètres, il y a plusieurs moyens de les transmettre. On peut passer par une convention basée sur l'utilisation de registres, ou bien passer par la pile par exemple. Par défaut, les deux compilateurs passent pas la pile. Cependant, on peut indiquer à la fonction que l'on préfère passer par une autre convention lorsqu'il n'y a qu'un paramètre à la fonction.

    Pour cela, on modifie la fonction div3 comme ceci :

    uint8_t div3(uint8_t dividend) __z88dk_fastcall
    {
        return div3_table[dividend];
    }
    

    Côté SDCC, la fonction div3 fond grâce au passage du paramètre et de la valeur de retour par le registre l. Plus besoin de mécanisme pour aller chercher la valeur dans la pile, calcul qui était généré de manière assez complexe par SDCC. La fonction passe de 27 octets à... 10 octets !

    Le code généré est tout de même étrange :

    _div3:
        ld  c, l                ; Sauvegarde de L dans C
        ld  de,_div3_table+0
        ld  l,c                 ; Récupération de C dans L... mais pourquoi ?
        ld  h,0x00
        add hl, de
        ld  l, (hl)
    l_div3_00101:
        ret
    

    Ce petit tour de passe-passe entre les registres C et L est inutile. L n'est pas utilisé entre temps, et C n'est pas utilisé ensuite. Voilà de quoi gagner 2 octets supplémentaire en réécrivant la fonction à la main.

    Côté appelant, setpoint est aussi un peu simplifié et tombe à 174 octets.

    Utilisons SCCZ80 à présent avec la même convention d'appel. La fonction initiale n'était pas très grosse, avec ses 14 octets, elle passe à 14 octets. Mais là encore les compilateur génère des choses étranges :

    ._div3
        push    hl          ; HL est poussé sur la pile
        ld  de,_div3_table
        pop hl              ; HL est récupéré de la pile
        push    hl          ; pour y être immédiatement remis
        ld  h,0
        add hl,de
        ld  l,(hl)
        ld  h,0
        pop bc              ; pour que la valeur soit ignorée...
        ret
    

    Ces push et pop du registre HL sont rigoureusement inutiles. Il n'y a pas de valeur à préserver. Et au final, le contenu de la pile est extrait dans un registre dont on ne s'est pas servi BC mais qui du coup est invalidé. Ce sont donc 4 octets à économiser (et pas mal de cycles d'exécutions) en enlevant ces instructions. Cela nous amène à 10 octets.

    La différence, si on oubli ces instructions inutiles, entre les deux codes générés est le LD H,0 (2 octets) pour s'assurer que la valeur de retour sur 16 bits est valide avec SCCZ80. SDCC ne prend pas cette précaution, à la charge de l'appelant de n'utiliser que la valeur du registre 8 bits L.


    Et l'inlining ?

    Une possibilité de compilation de l'appel d'une fonction est... de ne pas l'appeler, mais plutôt de faire comme si son code était « sur place ». C'est le mot-clé anglais « inline » qui nous permet de spécifier cela.

    Côté positif, si le code de la fonction lui-même est petit par rapport au code nécessaire au passage des paramètres et code de retour, cela peut-être gagnant d'injecter le code sur place. Côté négatif, il est possible que ce code injecté un peu partout fasse augmenter la taille du code final.

    inline uint8_t div3(uint8_t dividend)
    {
        return div3_table[dividend];
    }
    

    Avec SCCZ80, je ne suis pas allé bien loin. L'utilisation de « inline » fait émettre des erreurs au compilateur. Je ne me suis pas penché plus sur le problème.

    Avec SDCC par contre, non seulement le mot clé est pris en compte, mais le code est réduit de pas mal : 161 octets. Et forcément, pas de code généré pour div3. C'est plus petit que ce que j'avais écrit à la main (ce qui peut aussi s'expliquer par mes compétences limitées en assembleur Z80).


    Conclusion

    Le C est utilisable pour générer du code Z80. Les compilateurs utilisent des versions réduites du C actuel, mais néanmoins très corrects. Le bon côté est que le temps d'écriture du code, pour certaines opérations, est réduit, en tout cas pour moi.

    Par contre, il est nécessaire de garder le code généré à l’œil. Celui-ci peut rapidement être gourmand ou générer des choses inutiles. Il faut alors se poser la question d'adapter se code et de le passer en assembleur, en perdant au passage la portabilité.

    Cette portabilité reste limitée, puisqu'il est nécessaire d'aider fortement le compilateur.


  • VG5000µ, SetPoint en ASM, afficher le point ()

    À présent que l'on sait diviser par 3, reprenons l'affichage d'un point à l'écran. Pour rappel.

    En entrée, nous avons : des coordonnées X et Y, comprises entre 0 et 79 pour X et 0 et 74 pour Y.

    En effet de bord, c'est-à-dire en modification de l'état de la machine, nous voulons : le point correspondant à l'écran qui prend la couleur d'encre définie.

    Pour cette version, la procédure ne prendra pas d'information de couleur, je me contenterai d'utiliser la couleur d'encre 0 (noir) sur fond 6 (bleu), qui est la combinaison à l'initialisation de la machine.

    Les étapes, d'après les articles précédents, sont donc :

    • À partir de X et Y, trouver les coordonnées du caractère à modifier à l'écran
    • À partir de X et Y, trouver les coordonnées à l’intérieur du caractère semi-graphique
    • À partir de coordonnées du caractère, calculer l'adresse mémoire écran correspondante
    • Récupérer les valeurs pour la paire d'adresse mémoire
    • Si le caractère présent n'était pas un caractère semi-graphique standard, considérer qu'il était complètement éteint (valeur 0 pour le caractère)
    • Modifier la valeur du caractère récupéré en fonction des coordonnées à l'intérieur du caractère semi-graphique
    • Modifier la mémoire écran avec les nouvelles valeurs

    Comme le code est plutôt long, je vais changer de méthode. Le code entier va suivre, commenté au maximum en ligne.

    Le Code

            ; La procédure se nomme 'setpoint' et sera appelée avec `call setpoint`
            ;
            ; Les coordonnées (x,y) du point à allumer sont mises dans, respectivement
            ; L et H. Autrement dit, HL contient yx.
            ;
            ; C'est le format utilisé par la ROM du VG5000µ pour ses coordonnées de
            ; curseur. Autant le garder.
            ;
    setpoint:
            ; La procédure sauve tous les registres exceptés IX et IY.
            ;
            ; On pourrait aussi considérer que c'est à l'appelant de veiller à
            ; garder ses registres intègres
            ;
            ; Ce n'est pas le plus efficace, mais pour le moment, c'est le plus sûr.
            push    hl
            push    bc
            push    af
            push    de
    
            ; Pour le moment :
            ; - HL contient les coordonnées (y,x)
            ; - Les autres registres sont libres
    
            ld      a,h             ; On travaille sur y
            call    div3            ; Que l'on divise par 3
            ld      d,a             ; Et donc D contient y/3
    
            ld      a,l             ; On travaille sur x
    
            ; La ligne suivante ne fonctionne que si C (le Drapeau de retenue)
            ; est bien à zéro (ce qui est assuré avec le div_3 utilisé)
            ; Sinon, il faudrait utiliser `srl a`, qui est codé sur deux octets plutôt que 1
            rra                     ; On divise A par 2
            ld      e,a             ; Et donc D contient x/2
    
            ; À ce point :
            ; - DE contient les coordonnées (y/3,x/2)
            ; - HL contient toujours les coordonnées (y,x)
            ; - Les autres registres sont libres
    
            ; B sera utilisé temporairement
            ld      a,l             ; On travaille à nouveau sur x
            and     $01             ; On ne garde de A que le bit de poids faible.
            ld      b,a             ; Et donc B contient x modulo 2 (le reste de la division entière par 2)
    
            ld      a,h             ; On travaille à nouveau sur y
            sub     d               ; On soustrait D, qui contient y/3 (partie entière)
            sub     d               ; Une seconde fois
            sub     d               ; Puis une troisième fois.
                                    ; Et donc A contient y modulo 3
    
            ; On remarque ici qu'une fonction qui retournerait en même temps le quotient
            ; ET le reste de la division entière pourrait faire gagner un peu de temps...
    
                                    ; On travaille dessus immédiatement sur (y modulo 3)
                                    ; Dorénavant, j'utiliserai le signe % pour modulo.
    
            add     a               ; A contient à présent (y % 3) * 2
            add     b               ; A contient à présent (y % 3) * 2 + (x % 2)
    
            ; Petit point :
            ; - A contient la puissance de 2 nécessaire à trouver le bon caractère
            ; - DE contient toujours les coordonnées (y/3,x/2)
            ; - BC ne contient plus rien d'intéressant
            ; - HL ne contient plus rien d'intéressant
            ;   À vrai dire, HL n'est plus utile depuis le ld a,h précédent
    
            or      a               ; Équivalent à cp $0 mais plus conci et rapide
                                    ; Le résultat de cette comparaison de A avec 0
                                    ; va être conservé par les drapeaux jusqu'au
                                    ; JR suivant, car les instructions LD n'altèrent
                                    ; par les drapeaux.
    
            ; Il faut à présent calculer la valeur 2 à la puissance A
    
            ld      b,a             ; On charge B avec la valeur A. B va servir de
                                    ; compteur de boucle.
            ld      a,1             ; On initialise le résultat à 1
    
            jr      z,no_power      ; Si A était égal à zéro, on n'a rien besoin
                                    ; de calculer, donc on passe à la suite.
    
            ; La boucle suivante décale vers la gauche le contenu de A de 1 position
            ; Autrement dit, A est multiplié par 2 à chaque tour de boucle.
            ; À la fin de la boucle, A contient donc 2 puissance B.
    power_of_2:
            rla                     ;
            djnz    power_of_2
    
    no_power:
            ; A contient l'index du caractère semi-graphique à aller chercher.
            ; On sauve cette valeur pour plus tard dans la pile.
            push af
    
            ; Petit point :
            ; - HL est libre
            ; - BC est libre
            ; - DE contient les coordonnées (y/3, x/2)
            ; - A est sauvé sur la pile, on pourra donc l'utiliser pour des calculs
    
            ; L'objectif est à présent d'aller calculer l'adresse mémoire du caractère
            ; à changer dans la plage mémoire dédiée en RAM.
    
            ; La fonction de multiplication que j'utilise ici, et qui n'aura pas
            ; son article dédié, utilise HL et DE. DE est transféré dans BC.
            ld      b,d
            ld      c,e
    
            ; Et donc à présent DE est libre
            ; Et BC contient (y/3, x/2)
    
            ; Le premier calcul à faire est (y/3)*80
            ld      h,80            ; H contient 80
            ld      e,b             ; E contient y / 3
    
            call    mult            ; Appel de la multiplication
                                    ; À présent, HL contient (y/3)*80
    
            ; Le second calcul à faire est d'arrondir X à l'entier pair
            ; inférieur le plus proche. Pour cela, (x/2)*2, en utilisant
            ; une division entière donne le ŕésultat.
    
            ld      a,c             ; A contient x/2 (division entière)
            add     a               ; A contient (x/2)*2 (division entière)
    
            ; Petit point :
            ; - HL contient le déplacement mémoire sur le début de la ligne
            ; - A contient le déplacement en colonnes sur la ligne
            ; - BC est libre
            ; - DE est libre
    
            ; Il faut donc additionner HL et A pour avoir l'index mémoire.
            ; Le Z80 ne peut pas faire ça directement. Il faut donc charger
            ; A dans un registre 16 bits. BC par exemple.
            ld      b,0
            ld      c,a
    
            add     hl,bc           ; HL contient à présent (x/2)*2 + (y/3)*80
    
            ; On se ressert de BC pour indiquer la base de l'adresse mémoire vidéo
            ; auquel on ajoute l'index, pour obtenir l'adresse mémoire dans HL.
            ld      bc,$4000
            add     hl,bc
    
            ; Il est temps d'aller chercher les informations déjà présentes
            ; en mémoire. Pour cela, on a besoin des deux adresses HL et HL+1
            ; (voir les articles sur l'agencement de la mémoire vidéo)
            ld      b,h
            ld      c,l
    
            inc     bc              ; BC contient HL + 1
    
            ld      a,(bc)          ; A contient donc la valeur d'attribut du caractère
            bit     7,a             ; Ce qui nous intéresse est sont bit numéro 7
            jr      z,set_base_char ; S'il est à 0, ce n'est pas un caractère semi-graphique
    
                                    ; Sinon, on a besoin de connaître la valeur actuelle de ce
                                    ; caractère
    
            ld      a,(hl)          ; On récupère la valeur du caractère semi-graphique
                                    ; actuellement à l'écran dans A
    
            ; Si le caractère fait partie de la place 64 à 127 (les caractères pleins)
            ; alors on continue plus loin.
            bit     7,a
            jr      z,char_ok
    
    set_base_char:
            ld      a,64            ; Dans le cas où le caractère à l'écran n'était pas
                                    ; semi-grapique plein, on part sur une base du
                                    ; caractère 64, qui est le caractère semi-graphique
                                    ; 'tout éteint'
    char_ok:
            pop     de              ; Recupération dans D de l'index du caractère calculé.
                                    ; Cette valeur vient du 'push af' effectué plus haut.
    
            or      d               ; Une opération bit à bit 'OU' entre l'ancienne valeur
                                    ; et le nouvel index donne le nouveau caractère.
    
            ld      (hl),a          ; Ce caractère est placé à l'écran
    
            ld      a,224           ; Et dans cette implémentation, on fixe les attributs
            ld      (bc),a          ; selon les valeurs de couleurs à l'allumage du VG5000µ
                                    ; Une amélioration sera d'aller chercher dans les variables
                                    ; systèmes quels sont les couleurs courantes.
    
            ; La routine se termine, on restitue la valeur de tous les registres
            ; utilisés pour revenir à l'appelant.
            pop de
            pop af
            pop bc
            pop hl
    
    
            ret
    
    div3:                           ; Entrée: registre A, Sortie: valeur divisée par 3, dans A
            exx                     ;
            ld      hl,div3_table
            ld      b,0
            ld      c,a
            add     hl,bc
            ld      a,(hl)
    
            exx                     ;
            ret
    
    div3_table:
            defb    0,0,0,1,1,1,2,2,2,3,3,3,4,4,4,5,5,5 ; 18
            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
    
    mult:                           ; Entrée, registre H et registre E
                                    ; Sortie, le registre HL comtient le résultat
                                    ; de l'opération H * E
                                    ; Utilise HL, B, DE
            ld      d,0
            ld      l,d
            ld      b,8
    mult_loop:
            add     hl,hl
            jr      nc,mult_skip
            add     hl,de
    mult_skip:
            djnz    mult_loop
            ret
    

    Comment est-ce que ça s'utilise ?

    Cette routine s'utilise donc en mettant dans HL les coordonnées (y, x) du point à afficher. Elle pourrait être améliorée en déterminant si on veut afficher ou éteindre le point, spécifier les couleurs ou les récupérer des variables systèmes. Il y a probablement quelque optimisations qui trainent.

    Toujours est-il que par rapport à la routine est basique, l'exécution sera beaucoup plus rapide. Il serait possible d'être encore plus réactif en s'adressant directement au processeur vidéo. Mais je préférais utiliser le buffer vidéo en RAM pour plus de simplicité. Une implémetnation utilisant le processeur vidéo peut se trouver dans la bibliothèque d'affichage de Z88DK pour le VG5000µ. Z88DK est tout un système, basé sur un compilateur C, pour programmer les machines Z80.

    Pour revenir à l'utilisation de cette routine, voici un exemple qui affiche plusieurs lignes horizontales à l'écran.

            org     $7000
    
            ; Sauvegarde des registres utilisés.
            push    hl
            push    bc
    
            ld      h,$0A           ; La coordonnée y est 10 ($A en hexa)
            ld      b,25            ; On prépare une boucle de 25 itérations
    loop_1:
            ld      c,b             ; Sauvegarde temporaire de la boucle externe
                                    ; afin de préparer une boucle interne
    
            ld      l,$10           ; La coordonnée x est 16 ($10 en hexa)
            ld      b,40            ; On prépare une boucle de 40 itérations
    loop_2:
            call    setpoint        ; On affiche un point
            inc     l               ; On incrémente la coordonnée x de 1
            djnz    loop_2          ; Et on boucle
                                    ; Ce qui affiche une ligne de 40 pixels de large
                                    ; à la coordonnée y courante.
    
            ld      b,c             ; Récupération de l'index de boucle externe
    
            inc     h               ; On incrémente la coordonnée y deux fois
            inc     h               ; on "saute" donc une ligne.
    
            djnz    loop_1          ; Et on recommence ceci 25 fois.
                                    ; On affiche donc 25 lignes les unes sous les autres
                                    ; séparées à chaque fois par une hauteur d'un pixel
    
            ; Restauration des registres utilisés et retour à l'appelant
            pop     bc
            pop     hl
    
            ret
    

    Résultat

    Affichage des résultats de tests dans MAME


  • 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.


Page 1 / 10 (suivant) »