Christian Couderc

2 connectés # #

Exemples et astuces d'utilisation des
"look-up tables " ou "tables de conversions"

Maj : 06/09/02

Utilisation des "look-up tables "

Le tableau (array) est une méthode très pratique et rapide pour transformer une valeur en utilisant une table de conversion (look-up table). Une table est pré-calculée ou remplie à la main. En une instruction, la valeur contenue dans un registre sert de pointeur pour renvoyer le contenu du tableau.
Les tables sont d'un usage constant, en particulier pour encoder (et décoder) les claviers. Suivant l'action, les touches ont des affectations différentes. Il y a une table par action ou par combinaison de touches "verrous " (majuscules, control, alt...), les possibilités sont illimitées.

Le seul inconvénient de cette méthode est de consommer de l'espace mémoire. Un tableau de 8 bits d'entrée et de 8 bits de sortie, occupe une page de 256 octets, mais si vous augmentez les dimensions la petite mémoire du Pic sera vite saturé. Procédé à manier avec modération. Il évite parfois un gros calcul et sera souvent employé, surtout en une seule page.
Les contrôleurs possèdent des instructions du type :
Ramener la valeur contenue à la position (offset contenu dans un registre) d'un tableau dont l'adresse de début est fixée (registre ou adresse absolue).

Exemple d'utilisation : Balayage d'un clavier matricé 4*4 en autorisant toutes les combinaisons de 16 touches.

Autre exemple : transformer un alphabet en supprimant les accents, en convertissant majuscules en minuscules, en éliminant les caractères spéciaux…

Autre exemple : Affichage d'une vitesse à partir d'un temps. Il faut diviser une constante par le temps obtenu sur un timer 16 bits ou plus. La division est une opération lourde, il est possible de l'éviter en précalculant les résultats une seule fois et en les mettant en tableau. Le résultat s'obtient immédiatement en utilisant la variable (nombre de cycles trouvés) comme pointeur. Diverses astuces permettent de diminuer la taille des tables en utilisant des interpolations et en groupant les tables par plages de valeurs utiles.

Les "look-up tables " servent aussi à remplacer la division quand elle n'existe pas ou que la vitesse est nécessaire. Deux exemples montreront une application classique, obtenir l'inverse d'un nombre.

Remarque : Les deux orthographes "lookup " et "look-up " sont équivalentes.

Voici un exemple réel d'une utilisation pour supprimer les accents et les caractères indésirables, famille 8051.
La table initiale est d'abord chargée avec <valeur de sortie = adresse basse>, c'est à dire qu'elle rend le caractère en entrée.
Il suffit alors d'aller changer les quelques caractères désirés (surtout sans se décaler !).
Notez la beauté de ce code très rapide (Oh le bouffon...!). J'ai du l'écrire car il fallait aller très vite dans un noyau multitâche sans toucher aucun registre. L'incrément sert à faire pointer automatiquement le zéro de la table après le ret. Ce bloc peut donc être placé à n'importe qu'elle adresse dans le code.

Voici un exemple réel d'une utilisation d'une table de filtrage de 128 octets pour supprimer les accents et les caractères indésirables.

accent: clr ACC.7 ;
inc ACC ;
movc A,@A+PC ;
ret ;

;----> Table de conversion des accents
db 080h, 081h, 007h, 083h, 084h, 004h, 086h, 087h ; 80-87
; <‚> <…>
db 005h, 089h, 006h, 08Bh, 08Ch, 06Dh, 08Eh, 08Fh ; 88-8F
; <ˆ> <Š>
db 090h, 091h, 092h, 093h, 094h, 095h, 096h, 097h ; 90-97
db 098h, 099h, 09Ah, 09Bh, 09Ch, 09Dh, 09Eh, 09Fh ; 98-9F
db 0A0h, 0A1h, 0A2h, 0A3h, 0A4h, 0A5h, 0A6h, 0A7h ; A0-A7
db 0A8h, 0A9h, 0AAh, 0ABh, 0ACh, 0ADh, 0AEh, 0AFh ; A8-AF
db 0B0h, 0B1h, 0B2h, 0B3h, 0B4h, 0B5h, 0B6h, 0B7h ; B0-B7
db 0B8h, 0B9h, 0BAh, 0BBh, 0BCh, 0BDh, 0BEh, 0BFh ; B8-BF
db 0C0h, 0C1h, 0C2h, 0C3h, 0C4h, 0C5h, 0C6h, 0C7h ; C0-C7
db 0C8h, 0C9h, 0CAh, 0CBh, 0CCh, 0CDh, 0CEh, 0CFh ; C8-CF
db 0D0h, 0D1h, 0D2h, 0D3h, 0D4h, 0D5h, 0D6h, 0D7h ; D0-D7
db 0D8h, 0D9h, 0DAh, 0DBh, 0DCh, 0DDh, 0DEh, 0DFh ; D8-DF
db 0E0h, 0E1h, 0E2h, 0E3h, 0E4h, 0E5h, 0E6h, 0E7h ; E0-E7
db 0E8h, 0E9h, 0EAh, 0EBh, 0ECh, 0EDh, 0EEh, 0EFh ; E8-EF
db 0F0h, 0F1h, 0F2h, 0F3h, 0F4h, 0F5h, 0F6h, 0F7h ; F0-F7
db 0F8h, 0F9h, 0FAh, 0FBh, 0FCh, 0FDh, 0FEh, 0FFh ; F8-FF

Décodage d'afficheur 7 segments

Un autre exemple simple des "LUT ", destiné à décoder directement un afficheur 7 segments, le nibble (demi octet, 4 bits) commande directement les segments.

affhex: db 11111100b ;0
db 00110000b ;1
db 11011010b ;2
db 01111010b ;3
db 00110110b ;4
db 01101110b ;5
db 11101110b ;6
db 00111000b ;7
db 11111110b ;8
db 01111110b ;9
db 00000000b ;A tout éteint
db 11100110b ;B b
db 11000010b ;C c
db 11110010b ;D d
db 00000010b ;E moins central
db 01001010b ;F Trois barres horizontales

Remplissage d'afficheur graphique

Un autre exemple simple des "LUT ". table destinée à afficher de gros caractères sur un afficheur graphique, pixel par pîxel. Ici le chiffre 9 encadré par deux barres (plissez les yeux, vous verrez), Il y a une table de ce type pour chaque caractère dans une série de tailles. Dans cet exemple il y avait 5 tailles…

;----> Petit chiffre neuf
dw 0000000000000000b, 0000000000000000b ;
dw 0000111111111111b, 1111111111110000b ;
dw 0001000000000000b, 0000000000001000b ;
dw 0010000001111111b, 1111111000000100b ;
dw 0100000111111111b, 1111111110000010b ;
dw 0100001111111100b, 0011111111000010b ;
dw 0100011111100000b, 0000011111100010b ;
dw 0100111111000000b, 0000001111110010b ;
dw 0100111111000000b, 0000001111110010b ;
dw 0100111111000000b, 0000001111110010b ;
dw 0100111111000000b, 0000001111110010b ;
dw 0100111111000000b, 0000001111110010b ;
dw 0100111111000000b, 0000001111110010b ;
dw 0100011111100000b, 0000011111110010b ;
dw 0100001111111100b, 0011111111110010b ;
dw 0100000111111111b, 1111111111110010b ;
dw 0100000001111111b, 1111110111110010b ;
dw 0100000000011111b, 1100001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100000000000000b, 0000001111110010b ;
dw 0100111111100000b, 0000011111110010b ;
dw 0100011111111100b, 0011111111100010b ;
dw 0100001111111111b, 1111111111000010b ;
dw 0010000011111111b, 1111111100000100b ;
dw 0001000000000000b, 0000000000001000b ;
dw 0000111111111111b, 1111111111110000b ;
dw 0000000000000000b, 0000000000000000b ;

Décodage de clavier matricé

Un autre exemple simple des "LUT ". Décodage de 24 touches, par matriçage 6 lignes 4 colonnes. Un port un quart (deux bits pris sur un autre) est utilisé, les lignes pont mises en sortie et les colonnes en entrées, puis l'inverse, le code représente l'intersection donc la touche appuyée.

Le numéro de la trouche est rendu de 1 à 16 hexa (16+6=24 décimal). Le zéro est reservé pour "pas de touche valide appuyée ".

;----> Table de conversion des touches clavier souple
;----> c1 c2 c3 c4 Repérage physique
;----> P2.0 2.1 2.2 2.3
db 0Dh,14h,09h,04h ;Ligne 4 l6 P0.1
db 12h,13h,08h,03h ;Ligne 3 l5 P0.0
db 0Ch,0Ah,07h,02h ;Ligne 2 l4 P0.4
db 10h,17h,06h,01h ;Ligne 1 l3 P0.5
db 0Eh,15h,00h,05h ;Ligne 5 l2 P0.2
db 0Fh,16h,0Bh,11h ;Ligne 6 l1 P0.3

Voici un bout du hardware correspondant, les touches sont directement sur les fils des ports :

Petit fréquencemètre

Prenons comme autre exemple la réalisation d'un fréquencemètre. Notre contrôleur ne sait que compter des durées (par ses timers). Nous voulons traduire cela en fréquence d'un signal. Il va falloir inverser un temps (donc un nombre). La division, surtout de grands nombres, est longue et délicate pour un débutant. Beaucoup de contrôleurs ne disposent que de l'instruction multiplication 8 bits. Nous utiliserons donc une astuce pour exécuter l'opération. Il s'agit des "look-up tables ", en français "tables de conversions ".

Le principe est simple, c'est un tableau à deux entrées, pour les opérateurs, la sortie donnant le résultat immédiatement. Dans le cas de l'inversion, (division de 1 par l'opérateur, il n'y a qu'une seule entrée. la taille du tableau dépendra du résultat demandé. Entrée 8 bits, sortie 8 bits (0 à 255 décimal), une seule table de profondeur 1 octet, donc une seule page de 256 octets. Le résultat a souvent besoin d'être plus précis, sur 16 bits (compte jusqu'a 64000), il faudra deux pages.
Si maintenant vous voulez inverser un mot de 16 bits et sortir en 16 bits, c'est plus lourd !Iil faudra évidemment 2 fois 64000 adresses soit 128 ko de mémoire…
C'est énorme pour un petit contrôleur et donc peu réaliste. Nous ne parlons ici que d'un seul opérateur, alors imaginez maintenant que nous voulions utiliser la division de deux nombres de 16 bits avec résultat sur 16 bits. Il faudrait alors 128 * 128 = 16 Mo, des méga octets alors que nous travaillons avec des kilos…
Nous voyons donc que cette approche est irréaliste, mais heureusement il y a bien d'autres astuces.
Il faut limiter la taille des opérateurs au strict nécessaire pour la précision espérée.
Il ne faut pas diviser mais simplement inverser, car A/B = A * (1/B).
Il est difficile de diviser A par B, mais il est simple d'inverser B, puis de le multiplier par A.
La programmation utilise en permanence ce genre d'astuces magiques.
Il est même possible avec de petits moyens de manipuler des nombres énormes en scindant le problème, par exemple en recherchant des diviseurs entiers ou approchés et de faire des encadrements par approximations.

Calculer la vitesse des projectiles

Autre exemple utilisé pour calculer la vitesse des balles (voir la page). Un capteur mesure une durée de passage entre deux marqueurs et donne un résultat entre 500 et 1000 (pour les vitesse attendues) il faut sortir l'inverse qui sera le résultat, c'est une vitesse en mètres par seconde.
Nous avons étalonné le dispositif, pour 500 (coups d'horloge) la vitesse est de 600 m/s, donc pour 1000 elle sera de 300 m/s.
Nous allons donc utiliser une "look-up table " pour faire le calcul avec diverses astuces.
Tout d'abord nous allons réduire l'intervalle, comme on n'attend pas de temps inférieur à 500 (plus exactement de nombre de cycles, mais c'est proportionnel) ce n'est pas la peine de compter de 0 à 500, il suffira de compter à partir de 500 pris comme nouveau zéro.
Il suffit de décaler le pointeur pour que la valeur de 500 tombe sur le premier octet de la table.
Un petit test signalera une erreur si "<500 " ou ">1000 ".
Au premier octet de la table, correspondant à une entrée de 500, nous allons mettre le résultat attendu de 600 (m/s) et pour la dernière entrée à 1000, le résultat 300.

C'est bien le principe de ces tables. La valeur d'entrée est une adresse, un offset c'est à dire un décalage par rapport à un pointeur fixe visant le premier octet. la sortie est le contenu de la case pointée.

Nous optimiserons l'échelle en prenant une plage de 2 pages donc 512 valeurs.
Nous voyons que le résultat maximum de 1000 demande 10 bits (8 bits FF=255, 10 bits 3FF=1023), c'est ennuyeux car cela nous fait gaspiller le double de pages, il faudra aller d'abord chercher dans une table de 2 pages (sortie sur 8 bits) la partie haute, puis dans une autre table de 2 pages aussi, la partie basse et les coller.
Il faut faire mieux.
Nous attendons un résultat entre 300 et 600.
Pour commencer sortons entre 0 et 300 et ajoutons 300 ensuite, nous gagnons 1 bit, mais ce n'est pas assez.
Il faut alors :
Soit réduire la plage de valeurs d'entrée pour correspondre à une sortie enter 0 et 255 au lieu de 300, et alors nous n'avons qu'une seule table
Soit faire un petit test est scinder la plage en deux, nous aurons alors une table pour les rapides, une pour les lents. Nous avons maintenant une plage de 512 valeurs qui nous permet de presque doubler l'échelle des valeurs admises.
Soit si l'on s'obstine avec une seule table, il faudra compresser le résultat et multiplier ensuite par un facteur d'expansion, c'est peu élégant et lourd.

Il vaudra toujours mieux déclarer des "cas " (comme le "Case " des langages).
Si vitesse faible, table 1
Si vitesse moyenne table 2
Si vitesse élevée, table 3
Si vitesse hors limite message d'erreur.

Cette méthode est parfaite la précision est maximale et le résultat extrêmement rapide. Pour chaque cas l'offset sera différent et le résultat rendu sur une très grande plage avec virgule si nécessaire en n'utilisant que 3 pages de 256 octets. il suffit de faire une addition.
Il est évident que le remplissage des pages sera fait une fois pour toutes par un calcul sur un PC, par exemple avec une table Excel.
Il faudra sortir une courbe finale entrées/sorties sur toute l'étendue des valeurs pour s'assurer qu'il n'y a pas d'erreur grossière et que les diverses plages se raccordent bien. Le résultat sera ensuite copié "en dur ", c'est une liste de valeur importée.

Attention une table commence toujours à l'adresse xx00, en début d'une page, pour éviter les ennuis liés aux offsets relatifs négatifs.

Conclusion

Le but de ces exemples pédagogiques est de montrer quelques astuces de base donnant un excellent résultat avec un minimum de ressources, en utilisant une des techniques de programmation en microinformatique.

Cela est très différent sur une grosse machine où la division de nombres de taille quelconque ne pose aucun problème ni angoisse métaphysique.
Avec de petits moyens, la magie de l'assembleur compense.

* Page vue 877 fois IP : 3.137.159.17

Dernière retouche le 27 Juin 2019 à 13 h