Site logo

Triceraprog
La programmation depuis le Crétacé

  • Compression de donnees, compter les repetitions ()

    Dès le début de l'informatique, même si je ne saurais pas dater exactement quand, il a été question de stocker ou transmettre des données de manière efficace. Comment stocker ou transmettre un maximum de données avec un minimum d'espace ou de bande passante ? La compression de données répond à cette problématique avec des algorithmes qui repèrent l'information redondante pour la représenter de manière plus concise, ou bien qui éliminent des données jugées'(selon certains critères) moins utiles que d'autres.

    Dans ce premier article, nous allons voir ce que j'imagine être la plus simple des méthodes et qui vient souvent à l'esprit en premier lorsque l'on découvre le sujet : la compression RLE (Run Length Encoding).

    Le flux d'entrée

    Imaginons une image en niveaux de gris que l'on pourrait représenter de cette manière :

    ................
    ....#######.....
    ..##@@@@@@@##...
    .##@OOOOOOO@##..
    .#@OoooooooO@#..
    #@OoooooooooO@#.
    #@OoooooooooO@#.
    #@OoooooooooO@#.
    #@OoooooooooO@#.
    #@OoooooooooO@#.
    #@OoooooooooO@#.
    .#@OoooooooO@#..
    .##@OOOOOOO@##..
    ..##@@@@@@@##...
    ....#######.....
    ................
    

    Les niveaux de gris sont représentés par des caractères, et chaque caractère représente un pixel de l'image. L'image est de 16 lignes et 16 colonnes, soit 256 éléments. Ne nous occupons pas pour le moment de comment coder ces éléments. Ce sont juste des éléments.

    L'idée générale

    L'idée de la compression RLE vient de la constatation rapide qu'il existe des suites de données identiques dans les données, et que l'on peut même facilement énoncer. Par exemple, sur la première ligne, on peut dire qu'il y a 16 fois la valeur .. Sur la deuxième ligne, on peut dire qu'il y a 4 fois la valeur . puis 7 fois la valeur # puis 5 fois la valeur .. Et ainsi de suite.

    C'est le principe de la compression RLE : on va remplacer les suites d'éléments identiques par deux éléments : le nombre de répétitions et la valeur répétée. Par exemple, la première ligne devient (16, '.'), la deuxième ligne devient (4, '.'), (7, '#'), (5, '.').

    Voilà ce que cela donne pour l'image complète, si on met toutes les lignes bout à bout (sans les sauts de ligne) :

    (20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (1,@), (7,O), (1,@), (2,#), (3,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (3,.), (2,#), (1,@), (7,O), (1,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)
    

    Ce qui donne 89 couples de valeurs, soit 178 éléments au total. Contre 256 éléments dans l'image d'origine. On a donc bien réduit le nombre d'éléments nécessaires pour représenter l'image.

    Mais attention, ce qui permet la réduction, ce sont les suites de même valeur.

    Si les données sont constituées de valeurs souvent changeantes, la compression ne va pas bien fonctionner, voire donner plus d´éléments en sortie. Par exemple, si l'image n'etait constituée que de valeurs différentes de leurs précédentes, on devrait à chaque fois écrire (1, élément), et donc au final doubler le nombre d'éléments nécessaires. Pas très efficace.

    Codage du flux compressé

    Jusqu'à maintenant, on n'a parlé que d'éléments. Cependant, ces éléments doivent être codés d'une manière ou d'une autre pour être stockés sur la machine. Par exemple, on peut considérer assez facilement que le flux d'entrée est codé en caractères sur 8 bits. C'est trop pour 4 valeurs différentes (2 bits sont suffisants), mais on peut imaginer avoir d'autres valeurs sur les 256 possibles dans d'autres images.

    On va donc garder cette représentation en 8 bits pour les éléments valeurs. Même en sortie.

    Pour le nombre de répétitions, il faut faire un choix sur le plus grand nombre de répétitions possibles. Ces choix vont dépendre de la nature des données. Pour un premier choix, on va faire simple : 256 répetition maximum. Une image de 16x16 éléments monochrome serait donc codée par deux valeurs en 8 bits : (0, valeur). En effet, comme une répéition de 0 n'a pas de sens, on se sert du 0 pour coder 256.

    Deux octets au lieu de 256, c'est pas mal. Mais on peut aussi imaginer que les images monochromes ne sont pas représentatives.

    En prenant un octet pour les répétitions et un octet pour la valeur, le codage et le décodage sont très simples et la taille pour l'image exemple est de 178 octets, soit 178 octets pour 256 éléments.

    Peut-on faire mieux ?

    Oui. Il y a plusieurs manières différentes de coder un flux compressé RLE. La méthode indiquée précédemment est la plus simple. Mais on peut en imaginer d'autres.

    Par exemple, on peut réserver une plage de nombres dans l'indication des répétitions pour indiquer un nombre d'octets à suivre qui seront recopiés tels quels (parce qu'ils ne présentaient pas de répétition en entrée).

    Par exemple, sur un morceau en entrée comme :

    ....#.#.#.....
    

    On code les valeurs

    (r4, '.'), (c5, '#.#.#'), (r3, '.')
    

    r signifie "répétition" et c signifie "copie".

    D'un point de vue codage, on peut choisir que les valeurs 0 à 127 représentent des répétitions, et les valeurs 128 à 255 représentent des copies.

    Voilà ce que cela donne pour l'image complète avec cette méthode :

    (20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (129,@), (7,O), (129,@), (2,#), (3,.), (131,#@O), (7,o), (131,O@#), (2,.), (131,#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (131,O@#), (2,.), (131,#@O), (7,o), (131,O@#), (3,.), (2,#), (129,@), (7,O), (129,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)
    

    47 éléments au lieu de 89. Des éléments de taille variable cependant. Ici la taille en octets est de 136 plutôt que 178. Ce qui est un nouveau gain (au prix d'une toute petite complexité supplémentaire à traiter à la décompression)

    Peut-on faire encore mieux ?

    Vous pouvez trouver d'autres manières de coder un flux compressé RLE. En fonction de la plateforme, de la nature des données, de la taille des éléments, etc, il est possible de trouver des ajustements et des variations qui permettent de gagner de la place.

    Conclusion

    La compression RLE est une méthode simple à comprendre et à implémenter. Le temps de compression et de décompression sont très rapides car les calculs sont très simples.

    Elle peut donner de bons résultats sur des données avec beaucoup de plages de même valeur. C'est aussi une méthode non destructive : une fois décompressées, les données sont identiques à l'original avant compression.

    Dans un prochain article, nous verrons une autre méthode de compression classique et qui fonctionne bien sur des répétitions de motifs.

    Supplément

    Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.


  • PHC-25, et Z80 en IM 2 ()

    Ça y est, la nouvelle saison des Retro Programmers United for Obscure System a démarré. Et cette fois, c'est le PHC-25 qui est à l'honneur. Un ordinateur de Sanyo à base de Z80 (d'un clone plus précisément) et d'un MC6845 (... un clone aussi) et plutôt bien fourni en mémoire vive pour cette classe de machines : 16 ko de RAM et 6 ko pour la VRAM, accessible directement par le Z80 (avec des contraintes de timing si on veut éviter des parasites graphiques).

    Bien entendu, comme toutes les machines concernées par cette game jam, le PHC-25 est un ordinateur qui n'a pas une grande logithèque, et pas non plus beaucoup d'activité ni de documentation. C'est le principe.

    Pour cette Jam, je suis parti sur l'idée que le programme sera en assembleur. Certains vont certainement encore faire des miracles en BASIC, mais ce n'est pas ma tasse de thé, même si je l'ai enté par le passé. Avec la communauté des participants, nous nous sommes donc penchés sur la compréhension de la machine. Pas facile là encore car nous ne sommes pas nombreux à avoir un PHC-25, il faut donc continuellement passer par les bonnes âmes qui peuvent lancer nos tests.

    Après quelques jours, j'ai commencé à mettre mes notes, un programme d'exemple et une manière de packager un programme assembleur sur gitlab. C'est principalement le résultat d'un travail de recherche collectif.

    J'ai pu aussi corriger deux petits trucs dans MAME, qui reste loin d'être parfait pour le PHC-25, mais qui est un tout petit peu mieux qu'il y a deux semaines. La machine reste assez simple et peu exotique par rapport à d'autres que l'on a traitées auparavant.

    IM 2

    Lors de nos discussions et analyse, il est apparu que la ROM du PHC-25 lançait une ISR (Interrupt Service Routine) à chaque synchronisation verticale. C'est classique. Pendant cette ISR, la ROM fait les modifications en VRAM en fonction des modifications d'affichages demandées par le BASIC, cela pour éviter les parasites graphiques. Il y a aussi une lecture du clavier, la gestion du son,...

    Mais aucune possibilité de reroutage. Là où l'on trouve dans d'autres machines un « hook » sur lequel on peut attacher son propre code, ici, il n'y a rien.

    La proposition a été faite de passer le Z80 en IM 2, afin de gérer entièrement l'interruption. Cela fonctionne, et ce que je vais expliquer ici. À noter que l'IM 2 est une fonctionnalité du Z80 et que la grande partie de ce qui suit est valable pour d'autres machines similaires à base de Z80.

    Interrupt Mode ?

    Le Z80 peut fonctionner selon trois modes d'interruption. Le mode 0 est le mode par défaut. C'est un mode reliquat du 8080. Dans ce mode, lorsque l'interruption est reçue, le Z80 va lire l'instruction suivante qui va lui être présentée depuis un mécanisme externe. Généralement, c'est une instruction RST qui est utilisée, afin de brancher à l'une des routines RESTART du Z80.

    Mais la plupart, si ce n'est toutes, des machines familiales à base de Z80 utilisent le mode 1, qui est beaucoup plus simple. Dans ce mode, lorsque l'interruption est reçue, le Z80 branche tout simplement à l'adresse fixe 0x0038, à partir de laquelle on place l'ISR. C'est ce que fait le PHC-25. Mais comme son ISR n'offre pas de moyen d'extension, on est vite limité si on veut prendre les choses en main.

    Le mode 2, ou IM 2, est un mode qui est normalement fait pour être utilisé avec un contrôleur d'interruption externe. Dans ce mode, l'interruption est suivie d'une valeur paire sur 8 bits. Cette valeur est utilisée comme index dans une table d'adresses d'ISRs. Le Z80 va lire l'adresse de l'ISR à partir de cette table, puis il va brancher à cette adresse.

    Cependant, le PHC-25 n'a pas de contrôleur d'interruption externe. Ainsi, la valeur reçue peut être un peu n'importe quoi (et même pas forcément paire). L'astuce consiste donc à utiliser une table dont toutes les entrées pointent vers la même adresse. Comme l'index peut-être paire ou impaire, cela implique une contrainte supplémentaire : l'adresse de l'ISR doit être composée de deux octets identiques ($FEFE par exemple). Autre petit piège, comme la valeur 255 peut-être reçue, la table doit contenir 257 octets, et non pas 256 uniquement.

    En pratique

    Voici le code commenté pour mettre en place l'IM 2 sur le PHC-25 :

        ; Code pour l'assembleur SjASMPlus
    
        org $c009   ; Adresse de départ du programme.
                    ; On commence à $C009, car c'est l'adresse de départ
                    ; avec le chargeur BASIC utilisé. Mais vous pouvez
                    ; adapter.
    
    start:
        call install_im2    ; Le programme démarre par l'installation de l'IM 2
    
    infinite_loop:
        halt                ; Attente de l'interruption
        jp infinite_loop    ; Puis boucle
    
    
        ; Installation de l'IM 2
    install_im2:
        di      ; On commence par désactiver les interruptions
                ; Comme on va modifier la configuration,
                ; on ne veut pas qu'elles se déclenchent pendant ce temps
    
    
        ; Déplace la pile
        ; Peut-être optionnel, mais comme ça, on sait où elle est
        ; On ne pourra pas retourner dans la ROM, mais de toute façon
        ; elle ne fonctionnerait pas en IM2.
        pop hl                  ; sauve l'adresse de retour de la routine
        ld  sp,$fffe            ; place la pile à $FFFE
        push hl                 ; Pousse l'adresse de retour sur la pile
                                ; À présent, le RET peut retourner à l'endroit de l'appel
    
    
        ; Remplit la table des vecteurs d'interruption
        ld      hl,$fe00        ; La table démarre en $FE00
        ld      e,l
        ld      d,h
        inc     de              ; Idiome de remplissage de mémoire
        ld      bc,257          ; De longueur 257 octets
        ld      a,$fd           ; Contenant l'adresse $fdfd
        ld      (hl),a
        ldir                    ; Remplissage de mémoire
    
        ; On place un saut vers l'ISR dans le vecteur d'interruption
        ld      hl,$fdfd        ; L'adresse du vecteur
        ld      a,$c3           ; Instruction de saut (JP) vers xxxx
        ld      (hl),a
        inc     hl
        ld      de,isr          ; L'adresse de l'ISR
        ld      (hl),e
        inc     hl
        ld      (hl),d          ; Met l'adresse de l'ISR après l'instruction JP
    
        ; Place la table des vecteurs d'interruption ($FExx)
        ld      a,$fe
        ld      i,a             ; Met l'adresse haute à $FE
        im      2               ; Commute en Mode d'Interruption 2
    
        ; All set
        ei                      ; Réactive les interruptions
        ret
    
    char:
        db      32
    
        ; Routine de service d'interruption
        ; Appelée au début de la synchronisation verticale
        ; Affiche un caractère en haut à gauche de l'écran
        ; (en mode SCREEN 1)
    isr:
        ld      hl,char
        ld      a,(hl)
        inc     (hl)
        ld      hl,$6000
        ld      (hl),a
        ei
        reti
    

  • Récréation Famicom ()

    Et puisque ces temps-ci, je m'intéresse à la Famicom, en ayant commencé par le Family Basic , j'ai voulu faire une petite image 3D de la console.

    Un recréation da la Famicom


  • Family BASIC, le BASIC sur Famicom ()

    L'hiver dernier, j'ai découvert le Family Basic, ou Famibe, un BASIC pour la Famicom (le petit nom de la Family Computer de Nintendo, dont la version occidentale donnera la Nintendo Entertainment System, ou NES).

    Le Family Basic, qui vient dans une boite bien visible sur une étagère, comprend une cartouche, un clavier et un manuel. Le clavier est un vrai clavier et est assez agréable à utiliser. Il se branche sur le port d'extension en façade de la console, là où se branchent les périphériques d'entrées supplémentaires, les deux manettes étant connectées à la console « en dur ».

    La cartouche est plus haute que les cartouches Famicom classiques, presque la taille d'une cartouche NES. Dedans, il y a de la rom PRG (le programme), de la rom CHR (les données graphiques) et de la RAM (la mémoire vive) supplémentaire. Cette RAM peut d'ailleurs être alimentée par piles lorsque la console est éteinte, ce qui permet de garder des programmes en mémoire.

    Quant au manuel, en japonais, il est assez fourni et explique comment utiliser le BASIC, comment utiliser les particularités de celui-ci et contient des listings de programmes à taper, avec des explications.

    Ce BASIC est plutôt intéressant, et même si la mémoire vive est très limitées (2ko sur les version 1 et 2 de la cartouche, 4ko sur la version 3), il est possible de faire des choses intéressantes.

    Il y a eu plusieurs versions du Family Basic. La première, sortie en 1984, semble ne pas avoir été très fiable et a pu être échangée contre une version 2 (il semble exister une version 2.0 et une version 2.1). Ces deux versions ont une cartouche de couleur noire. La version 3, dans une cartouche rouge et sortie en 1985, est beaucoup plus intéressante : plus de commandes et plus de mémoire vive.

    J'ai résumé quelques-unes de mes expériences dans une vidéos que vous pouvez voir ci-dessous.

    Un article en anglais, qui donne plus d'informations que ce présent petit article est disponible sur le site Nerdly Pleasures.


  • Instance Peertube pour Triceraprog ()

    Un projet que j'avais depuis un moment maintenant était de mettre en place une instance Peertube pour ce site. J'ai profité d'un changement de version majeur de Peertube pour réactiver ce projet et c'est maintenant chose faite.

    J'ai ai donc mis les deux vidéos sur le BASIC et celle sur le LOGO.


Page 1 / 23 (suivant) »

Tous les tags

3d (15), 6809 (1), 8bits (1), Affichage (24), AgonLight (2), Altaïr (1), Amstrad CPC (1), Apple (1), Aquarius (2), ASM (30), Atari (1), Atari 800 (1), Atari ST (2), Automatisation (4), BASIC (31), BASIC-80 (4), C (3), Calculs (1), CDC (1), Clion (1), cmake (1), Commodore (1), Commodore PET (1), Compression (1), CPU (1), Debug (5), Dithering (2), Divers (1), EF9345 (1), Émulation (7), Famicom (2), Forth (3), Game Jam (1), Hector (3), Histoire (1), Hooks (4), i8008 (1), Image (17), Jeu (14), Jeu Vidéo (4), Livre (1), Logo (2), Machine virtuelle (2), Magazine (1), MAME (1), Matra Alice (3), MDLC (7), Micral (2), Motorola (1), MSX (1), Musée (2), Nintendo Switch (1), Nombres (3), Optimisation (1), Outils (3), Pascaline (1), Peertube (1), PHC-25 (1), Photo (2), Programmation (5), Python (1), ROM (15), RPUfOS (5), Salon (1), SC-3000 (1), Schéma (5), Synthèse (15), Tortue (1), Triceraprog (1), VG5000 (62), VIC-20 (1), Vidéo (1), Z80 (21), z88dk (1)

Les derniers articles

Compression de donnees, compter les repetitions
PHC-25, et Z80 en IM 2
Récréation Famicom
Family BASIC, le BASIC sur Famicom
Instance Peertube pour Triceraprog
Environnement de développement pour Picthorix
Un jeu en Forth pour Hector HRX : Picthorix
Yeno SC-3000 et condensateurs
Suite de tests pour VG5000µ
Un peu d'Atari ST

Atom Feed

Réseaux