Structures de données pour eForth

publication: 3 mars 2023 / mis à jour 9 novembre 2024

Préambule

eFORTH est une version 32 bits du langage FORTH. Ceux qui ont pratiqué FORTH depuis ses débuts ont programmé avec des versions 16 bits. Cette taille de données est déterminée par la taille des éléments déposés sur la pile de données. Pour connaître la taille en octets des éléments, il faut exécuter le mot cell. Exécution de ce mot pour eFORTH:

cell .  \ display 4

La valeur 4 signifie que la taille des éléments déposés sur la pile de donnéees est de 4 octets, soit 4x8 bits = 32 bits.

Avec une version FORTH 16 bits, cell empilera la valeur 2. De même, si vous utilisez une version 64 bits, cell empilera la valeur 8.

Les tableaux en FORTH

Nous allons commencer par des structures assez simples: les tableaux. Nous n'aborderons que les tableaux à une ou deux dimensions.

Tableau de données à une dimension

C'est le type de tableau le plus simple. Pour créer un tableau de ce type, on utilise le mot create suivi du nom du tableau à créer:

create temperatures 
    34 ,    37 ,    42 ,    36 ,    25 ,    12 ,

Dans ce tableau, on stocke 6 valeurs: 34, 37....12. Pour récupérer une valeur, il suffit d'utiliser le mot @ en incrémentant l'adresse empilée par temperatures avec le décalage souhaité:

temperatures        \ push addr on stack 
    0 cell *        \ calculate offset 0 
    +               \ add offset to addr 
    @ .             \ display 34 
 
temperatures        \ push addr on stack 
    1 cell *        \ calculate offset 0 
    +               \ add offset to addr 
    @ .             \ display 37

On peut factoriser le code d'accès à la valeur souhaitée en définissant un mot qui va calculer cette adresse:

: temp@ ( index --  value ) 
    cell * temperatures + @ 
  ; 
0 temp@ .   \ display 34 
2 temp@ .   \ display 42

Vous noterez que pour n valeurs stockées dans ce tableau, ici 6 valeurs, l'index d'accès doit toujours être dans l'intervalle [0..n-1].

Mots de définition de tableaux

Voici comment créer un mot de définition de tableaux d'entiers à une dimension:

: array ( comp: --  | exec: index  -- addr ) 
    create 
    does> 
        swap cell * + 
  ; 
array myTemps 
    21 ,    32 ,    45 ,    44 ,    28 ,    12 , 
0 myTemps @ .   \ display 21 
5 myTemps @ .   \ display 12

Dans notre exemple, nous stockons 6 valeurs comprises entre 0 et 255. Il est aisé de créer une variante de array pour gérer nos données de manière plus compacte:

: arrayC ( comp: --  | exec: index  -- addr ) 
    create 
    does> 
        + 
  ; 
arrayC myCTemps 
    21 c,   32 c,   45 c,   44 c,   28 c,   12 c, 
0 myCTemps c@ .     \ display 21 
5 myCTemps c@ .     \ display 12

Avec cette variante, on stocke les mêmes valeurs dans quatre fois moins d'espace mémoire.

Lire et écrire dans un tableau

Il est tout à fait possible de créer un tableau vide de n éléments et d'écrire et lire des valeurs dans ce tableau:

arrayC myCTemps 
    6 allot             \ allocate 6 bytes 
    0 myCTemps 6 0 fill \ fill this 6 bytes with value 0 
32 0 myCTemps c!        \ store 32 in myCTemps[0] 
25 5 myCTemps c!        \ store 25 in myCTemps[5] 
0 myCTemps c@ .         \ display 32

Dans notre exemple, le tableau contient 6 éléments. Avec eFORTH, il y a assez d'espace mémoire pour traiter des tableaux bien plus grands, avec 1.000 ou 10.000 éléments par exemple. Il est facile de créer des tableaux à plusieurs dimensions. Exemple de tableau à deux dimensions:

63 constant SCR_WIDTH 
16 constant SCR_HEIGHT 
create mySCREEN 
    SCR_WIDTH SCR_HEIGHT * allot            \ allocate 63 * 16 bytes 
    mySCREEN SCR_WIDTH SCR_HEIGHT * bl fill \ fill this memory with 'space'

Ici, on définit un tableau à deux dimensions nommé mySCREEN qui sera un écran virtuel de 16 lignes et 63 colonnes.

Il suffit de réserver un espace mémoire qui soit le produit des dimensions X et Y du tableau à utiliser. Voyons maintenant comment gérer ce tableau à deux dimensions:

: xySCRaddr { x y -- addr } 
    SCR_WIDTH y * 
    x + mySCREEN + 
  ; 
: SCR@ ( x y -- c ) 
    xySCRaddr c@ 
  ; 
: SCR! ( c x y -- ) 
    xySCRaddr c! 
  ; 
char X 15 5 SCR!    \ store char X at col 15 line 5 
15 5 SCR@ emit      \ display X

Exemple pratique de gestion d'écran

Voici comment afficher la table des caractères disponibles:

: tableChars ( -- ) 
 
    base @ >r  hex 
    128 32 do 
       16 0 do 
            j i + dup . space emit space space 
       loop 
       cr 
    16 +loop 
    256 160 do 
       16 0 do 
            j i + dup . space emit space space 
       loop 
       cr 
    16 +loop 
    cr 
    r> base ! 
  ; 
tableChars

Voici le résultat de l'exécution de tableChars:

Ces caractères sont ceux du jeu ASCII MS-DOS. Certains de ces caractères sont semi-graphiques. Voici une insertion très simple d'un de ces caractères dans notre écran virtuel:

$db dup 5 2 SCR!     6 2 SCR! 
$b2 dup 7 3 SCR!     8 3 SCR! 
$b1 dup 9 4 SCR!    10 4 SCR!

Voyons maintenant comment afficher le contenu de notre écran virtuel. Si on considère chaque ligne de l'acran virtuel comme chaîne alphanumérique, il suffit de définir ce mot pour afficher une des lignes de notre écran virtuel:

: dispLine { numLine -- } 
    SCR_WIDTH numLine * 
    mySCREEN + SCR_WIDTH type 
  ;

Au passage, on va créer une définition permettant d'afficher n fois un même caractère:

: nEmit ( c n -- ) 
    for 
        aft dup emit then 
    next 
    drop 
  ;

Et maintenant, on définit le mot permettant d'afficher le contenu de notre écran virtuel. Pour bien voir le contenu de cet écran virtuel, on l'encadre avec des caractères spéciaux:

: dispScreen 
    0 0 at-xy 
    \ display upper border 
    $da emit    $c4 SCR_WIDTH nEmit    $bf emit    cr 
    \ display content virtual screen 
    SCR_HEIGHT 0 do 
        $b3 emit    i dispLine         $b3 emit    cr 
    loop 
    \ display bottom border 
    $c0 emit    $c4 SCR_WIDTH nEmit    $d9 emit    cr 
  ;

L'exécution de notre mot dispScreen affiche ceci:

Dans notre exemple d'écran virtuel, nous montrons que la gestion d'un tableau à deux dimensions a une application concrète. Notre écran virtuel est accessible en écriture et en lecture. Ici, nous affichons notre écran virtuel dans le fenêtre du terminal.

Gestion de structures complexes

eFORTH dispose du vocabulaire structures. Le contenu de ce vocabulaire permet de définir des structures de données complexes.

Voici un exemple trivial de structure:

structures 
struct YMDHMS 
    ptr field ->YMDHMS-year 
    ptr field ->YMDHMS-month 
    ptr field ->YMDHMS-day 
    ptr field ->YMDHMS-hour 
    ptr field ->YMDHMS-min 
    ptr field ->YMDHMS-sec

Ici, on définit la structure YMDHMS. Cette structure gère les accesseurs ->YMDHMS-year ->YMDHMS-month ->YMDHMS-day ->YMDHMS-hour ->YMDHMS-min et ->YMDHMS-sec.

Le mot YMDHMS a comme seule utilité d'initailiser les accesseurs. Voici comment sont utilisés ces accesseurs:

create DateTime 
    YMDHMS allot 
 
2022 DateTime ->YMDHMS-year  ! 
  03 DateTime ->YMDHMS-month ! 
  21 DateTime ->YMDHMS-day   ! 
  22 DateTime ->YMDHMS-hour  ! 
  36 DateTime ->YMDHMS-min   ! 
  15 DateTime ->YMDHMS-sec   ! 
 
: .date ( date -- ) 
    >r 
    ."  YEAR: " r@ ->YMDHMS-year    @ . cr 
    ." MONTH: " r@ ->YMDHMS-month   @ . cr 
    ."   DAY: " r@ ->YMDHMS-day     @ . cr 
    ."    HH: " r@ ->YMDHMS-hour    @ . cr 
    ."    MM: " r@ ->YMDHMS-min     @ . cr 
    ."    SS: " r@ ->YMDHMS-sec     @ . cr 
    r> drop 
  ; 
 
DateTime .date

Règles de nommage des structures et accesseurs

Une structure est définie par le mot struct. Le nom choisi dépend du contexte d'utilisation. Il ne doit pas être trop long, pour rester lisible. Ici, une structure définissant uen couleur dans la librairie SDL:

struct SDL_Color ( -- n )

Cette structure a comme nom SDL_Color. Ce nom a été choisi car cette structure porte le même nom dans la librairie en langage C.

Voici la définition, en Forth, des accesseurs correspondant à cette structure SDL_Color:

struct SDL_Color ( -- n ) 
     i8 field ->Color-r 
     i8 field ->Color-g 
     i8 field ->Color-b 
     i8 field ->Color-a

Chaque définition commence par un mot indiquant la taille du champ de donnée dans la structure, ici i8.

Ce mot i8 est suivi du mot field qui va nommer l'accesseur, ->Color-r par exemple.

On peut choisir un nom d'accesseur à sa convenance, exemple:

i8 field red-color

i8 field colorRed

Mais ces noms finissent rapidement par rendre un programme difficile à déchiffrer. Pour cette raison, il est souhaitable de précéder un nom d'accesseurs par ->. On fait suivre par le nom de la structure, ici Color, suivi d'un tiret et un nom discriminant, ici r:

i8 field ->Color-r

Autre exemple:

struct SDL_GenericEvent 
    i32 field ->GenericEvent-type 
    i32 field ->GenericEvent-timestamp

Ici, on définit la structure SDL_GenericEvent et deux accesseurs 32 bits: ->GenericEvent-type et ->GenericEvent-timestamp.

Par la suite, si on retrouve l'accesseur ->GenericEvent-type dans un programme, on saura immédiatement que c'est un accesseur associé à la structure GenericEvent.

Choix de la taille des champs dans une structure

La taille d'un champ dans une structure est définie par un de ces mot:

ptr pour pointer une donnée sur la taille de une cellule, 8 octets pour eForth Windows
i64 pour pointer une donnée sur 8 octet (64b its)
i32 pour pointer une donnée sur 4 octet (32 bits)
i16 pour pointer une donnée sur 2 octet (16 bits)
i8 pour pointer une donnée sur 1 octet (8 bits)

Pour eForth Windows, les mots ptr et i64 ont la même action.

On ne peut pas gérer des champs de taille variable, pour une chaîne de caractères par exemple.

Si on doit définir un champ d'une taille spéciale, on définira ce type ainsi:

strutures definition 
    10 10 typer phoneNum 
     5  5 typer zipCode

On peut aussi s'en passer en utilisant la taille de données directement. Exemple:

structures 
struct City 
     5  field ->City-zip 
    64  field ->City-name

Si on exécute City, ce mot empilera la taille totale de la structure, ici la valeur 69. On utilisera cette valeur pour réserver le nombre de caractères requis pour des données:

create BORDEAUX 
    City allot

Nous n'allons pas entrer dans le détail de la gestion des champs de notre structure City.

Pour ce qui concerne les champs définis par i8 à i64, on ne peut pas utiliser les seuls mots @ et ! pour lire et écrire des valeurs numériques dans ces champs.

Voici les mots permettant d'accéder aux données en fonction de leur taille:

	i8	i16	i32	i64
fetch	C@	UW@	UL@	@
store	C!	W!	L!	!

On avait défini le mot DateTime qui est un tableau simple de 6 cellules 64 bits consécutives. L'accès à chacune des cellules est réalisée par l'intermédiaire de l'accesseur correspondant. On peut redéfinir l'espace alloué de notre structure YMDHMS en utilisant i8 et i16:

structures 
struct cYMDHMS 
    i16 field ->cYMDHMS-year 
    i8  field ->cYMDHMS-month 
    i8  field ->cYMDHMS-day 
    i8  field ->cYMDHMS-hour 
    i8  field ->cYMDHMS-min 
    i8  field ->cYMDHMS-sec 
 
create cDateTime 
    cYMDHMS allot 
 
2022 cDateTime ->cYMDHMS-year  w! 
  03 cDateTime ->cYMDHMS-month c! 
  21 cDateTime ->cYMDHMS-day   c! 
  22 cDateTime ->cYMDHMS-hour  c! 
  36 cDateTime ->cYMDHMS-min   c! 
  15 cDateTime ->cYMDHMS-sec   c!

Il est conseillé de factoriser l'emploi des accesseurs dans une définition globale:

: date!  { year month day hour min sec addr -- } 
    year    addr ->cYMDHMS-year  w! 
    month   addr ->cYMDHMS-month c! 
    day     addr ->cYMDHMS-day   c! 
    hour    addr ->cYMDHMS-hour  c! 
    min     addr ->cYMDHMS-min   c! 
    sec     addr ->cYMDHMS-sec   c! 
  ; 
2024 11 09 18 25 40 cDateTime date!

Avec date!, on ne s'occupe plus de savoir quels champs sont sur un ou deux octets dans la structure cYMDHMS.

Si on doit changer la taille d'un champ, seule la définition de date! devra être modifiée.

Voici comment lire les données dans cDateTime:

 
: .date { date -- } 
    ."  YEAR: " date ->cYMDHMS-year   uw@ . cr 
    ." MONTH: " date ->cYMDHMS-month   c@ . cr 
    ."   DAY: " date ->cYMDHMS-day     c@ . cr 
    ."    HH: " date ->cYMDHMS-hour    c@ . cr 
    ."    MM: " date ->cYMDHMS-min     c@ . cr 
    ."    SS: " date ->cYMDHMS-sec     c@ . cr 
  ; 
cDateTime .date    \ display: 
\  YEAR: 2024 
\ MONTH: 11 
\   DAY: 9 
\    HH: 18 
\    MM: 25 
\    SS: 40

Définition de sprites

On avait précédemment définit un écran virtuel comme tableau à deux dimensions. Les dimensions de ce tableau sont définies par deux constantes. Rappel de la définition de cet écran virtuel:

63 constant SCR_WIDTH 
16 constant SCR_HEIGHT 
create mySCREEN 
    SCR_WIDTH SCR_HEIGHT * allot            \ allocate 63 * 16 bytes 
    mySCREEN SCR_WIDTH SCR_HEIGHT * bl fill \ fill this memory with 'space'

L'inconvénient, avec cette méthode de programmation, les dimensions sont définies dans des constantes, donc en dehors du tableau. Il serait plus intéressant d'embarquer les dimensions du tableau dans le tableau. Pour ce faire, on va définir une structure adaptée à ce cas:

structures 
struct cARRAY 
    i8  field ->cARRAY-width 
    i8  field ->cARRAY-height 
    i8  field ->cARRAY-content 
 
: cArray-size@  { addr -- datas-size } 
    addr ->cARRAY-width  c@ 
    addr ->cARRAY-height c@ * 
  ; 
 
create myVscreen    \ define a screen 8x32 bytes 
    32 c,           \ compile width 
    08 c,           \ compile height 
    myVscreen cArray-size@ allot

Pour définir un sprite logiciel, on va mutualiser très simplement cette définition:

structures 
struct cARRAY 
    i8  field ->cARRAY-width 
    i8  field ->cARRAY-height 
    i8  field ->cARRAY-content 
 
: cArray-width@  { addr -- width } 
    addr ->cARRAY-width  c@ 
  ; 
 
: cArray-height@  { addr -- height } 
    addr ->cARRAY-height  c@ 
  ; 
 
: cArray-size@  { addr -- datas-size } 
    addr cArray-width@   
    addr cArray-height@ * 
  ;

Voici comment définir un sprite 5 x 7 octets:

create char3 
    5 c,  7 c,    \ compile width and height 
    $20 c,  $db c,  $db c,  $db c,  $20 c, 
    $db c,  $20 c,  $20 c,  $20 c,  $db c, 
    $20 c,  $20 c,  $20 c,  $20 c,  $db c, 
    $20 c,  $db c,  $db c,  $db c,  $20 c, 
    $20 c,  $20 c,  $20 c,  $20 c,  $db c, 
    $db c,  $20 c,  $20 c,  $20 c,  $db c, 
    $20 c,  $db c,  $db c,  $db c,  $20 c,

Pour l'affichage du sprite, à partir d'une position x y dans la fenêtre du terminal, une simple boucle suffit:

: .sprite { xpos ypos sprite-addr -- } 
    sprite-addr cArray-height@ 0 do 
        xpos ypos at-xy 
        sprite-addr cArray-width@ i *       \ calculate offset in sprite datas 
        sprite-addr ->cARRAY-content +      \ calculate real address for line n in sprite datas 
        sprite-addr cArray-width@ type      \ display line 
        1 +to ypos              \ increment y position 
    loop 
  ; 
 
0 constant blackColor 
1 constant redColor 
4 constant blueColor 
10 02 char3 .sprite 
redColor fg 
16 02 char3 .sprite 
blueColor fg 
22 02 char3 .sprite 
blackColor fg 
cr cr

Résultat de l'affichage de notre sprite:

Voilà. C'est tout. J'espère que le contenu de cet article vous aura donné quelques idées intéressantes que vous aimeriez partager...

Legal: site web personnel sans commerce / personal site without seling