Logicielsmoto.com

Petit quizz..

Que fait le code de 256 octets (exactement) qu'il faut charger à partir de $A000 sur un TO7,8,9, ou 9+ ? (rahh autant de hexgits ca me rappelle l'époque hebdogiiiciel et ses cours d'asm 6809e. J'espère ne pas m'être trompé dans la recopie).

Bon évidemment vu la taille du truc, j'ai du faire un peu de concession à l'optimisation CPU pure car les octets partent très vite. Un simple cmpd #label c'est déjà 4 octets de partis, idem pour les données (il est dur de remplacer des FCB par des LDD/STD: ca prend toujours plus de place via les opcodes). Il a fallu faire plusieurs versions et utiliser diverses astuces au plusieurs chausse-pieds pour faire tenir cela dans 1/4 de Ko.

En fait, ce n'est pas tellement les premières optimisations de taille qui sont dures (on gagne les octets par trentaine), mais c'est surtout la fin quand on a déjà gagné beaucoup et qu'il reste 3 ou 4 octets de trop (voir 1 ou 2) et qu'on se demande comment gagner encore de la place sans perdre une fonction (par exemple: la sortie propre du programme). Mais bon c'est réussi, ça tient dans 16x16 octets. Ouf! Je suis content d'avoir fini ca A noter que malgré les astuces, le code est propre et retourne au basic sur simple appui du bouton souris ou crayon-optique.

Alors oui bon c'est bien joli le tableau de données hexadécimales, mais que fait il au juste ce code? Je laisse cela à la sagacité du lecteur. voyons: Pour décoder les opcodes on peut utiliser cette table (je le trouve pratique). Pour ma part je les ai produit avec le C6809 de Préhisto (promis un de ces 4 je testerais tes patchs qui attendent depuis un petit moment)... :

Comme indice je peux ajouter que c'est un truc que je voulais faire depuis un petit moment et qui contient pas mal de trucs & astuces sympa dont je discuterais volontiers ici plus tard.

sam \(^_^)/

edit: une version plus "recopiable":

effet sympatique

ca m'a pris un peu de temps pour comprendre que c6809 limitait à 8 la taille des FCB, pas pratique pour refaire un .asm dans le genre


(je tiens à disposition un .sap en autoload pour ceux qui rechigneraient à taper les codes hexa directement).

_________________
http://www.alternative-system.com

Oh honte à moi de ne pas avoir mis un code asm avec des FCB pour faciliter la reprise.

Cette façon de reprendre le code est vraiment super, Gilles! Moi j'aurais bêtement recopié les nombres dans la partie DATA d'un prog basic et jouer du READ et POKE pour remplir la mémoire. Si on veut se marrer, on peut construire une chaine basic et faire un "poke &hA000, chaine$" pour recopier les 256 octets d'un coup... Encore que je me demande si le basic n'a pas une limite 255 sur la longueur de chaine.

Je garde l'idée pour une autre occasion (pas tout de suite car il y a pleins de truc à voir dans ce chausse pied).

En attendant, la version K7 est aussi disponible. A lancer en tapant en haut de l'écran (faire RAZ avant) dans le Basic1.0 ou plus. Ah tiens le nom du binaire donne un nouvel indice.

sam.

Pour voir ce que ca donne sans to7 sous la main, voici une petite video:

(ci-joint: durée limitée à 60jours).

Quelques infos techniques.

Comme le nom l'indique "kefrens", il s'agit d'un effet similaire aux kefrens bars dont on peut voir une version javascript en 256octets sur pouet.net:Comme le code javascript est compacté, donc difficile à lire, en voici une version en pseudo-basic (toutes les vars sont des nombres flottants et le sinus est calculé en radians): En fait l'effet est simple. Par contre il requiert des nombres flottants, des multiplications signées, ainsi que des sinus. Le challenge a donc été de caler tout cela dans 256 octets sans trop sacrifier de vitesse.

Après expérimentation, il apparait que l'on peut remplacer les nombres flottants par des nombres en virgule fixe 8.8 sans trop d'erreurs numériques. Ainsi sur 16 bits on peut représenter des nombres de -128.0 à 127.0 par pas de 1/256 (environ 0.5% de précision). Le passage des floats au fixed-point se fait facilement L'avantage des nombres fixpt est que l'addition se fait de la même façon qu'une addition 16bits sans aucun sur-coût. La multiplication est à peine plus difficile:c'est à dire une multiplication signée 16bits * 16bits (résultat sur 32) dont on élimine les 8 bits de poids faible: Point intéressant, dans l'algo on multiplie deux sinus, c'est à dire deux nombres entre -1.0 et 1.0, c'est à dire des nombres entiers signés dans [-256, 256]. Cela signifie que si on se restreint aux nombres positifs, N1 et P1 sont soit 0, soit 1. Donc parmi les 4 multiplications 8x8 à faire, une seule doit réellement être faite: N2P2, les autres ne sont qu'un jeu de masque de bits. En gros le code de la multiplication se réduit à: Il est facile de voir que comparé au calcul en nombre à virgule flottante, les fixpt sont beaucoup beaucoup plus rapide.

Pour les sinus, c'est plus dur car les fixpt n'aident pas. L'utilisation d'une table pré-calculée pour l'intervalle -pi..pi est une bonne idée, mais elle prend 1608 octets (pi vaut environ 804 en fixpt8.8). Ca se complique....

sam (la ROM peut être?)

La rom, ben non. C'est galère à utiliser, ca prend pleins de temps CPU et d'octets. En plus la rom offre des calculs bien trop précis pour notre représentation fixpt 8.8 (1/256 de précision). Enfin je ne suis pas sur que l'extramon existe sur TO7. Donc il faut une autre solution. La solution se trouve dans les approximations polynomiales. En fait dans l'intervalle -PI..PI, si on considère la fonction suivante: on constate qu'on s'éloigne assez peu de la valeur de SIN(V).

Cette approximation est vraiment facile à mettre en oeuvre car elle ne nécessite que 3 multiplications signées, dont deux par des constantes.

La multiplication par des constantes est intéressante car on peut la réaliser à coups de décalages et d'additions. Hélas sur le 6809 cela prend beaucoup d'instructions, et dans le cadre de 256 octets, ces derniers sont comptés, donc dans l'algo on ne peut bénéficier de la multiplication rapide par des constantes.

Autre point important: cette approximation ne marche bien que si V est entre -PI et PI. Or dans l'algo on a des valeurs de A qui ne cesse de croitre et dépasse très vite l'intervalle. Le truc est de travailler "modulo 2PI", c'est à dire qu'on effectue l'addition A = A + 88 (en fait A = A + 9, car 88 modulo 2PI vaut 9/256) mais dès que le résultat dépasse PI, on soustrait 2PI pour rester dans l'intervalle [-PI, PI]. Avec ca les calculs des sinus restent toujours suffisamment bon pour la précision souhaitée.

sam (et les multiplications signées dans tout ca?)

Tiens, j'ai l'habitude d'utiliser des angles entre 0 et 255 plutôt que 0 et Pi. C'est un peu bizarre comme unité mais on s'habitue, ça fait le modulo gratuitement ce qui est bien pratique. Par contre il faut utiliser un autre polynôme, bien sur

Si je compte bien, alors si on dit que 2PI=255, l'unité vaut 40. La précision est donc 1/40 au lieu de 1/256, c'est à dire 6 fois moins bonne (2%) qu'avec l'unité à 256 (0.3%) pour les abscisses. Mais si on a pas besoin d'une grande précision, alors 256 est pas mal. Maintenant économiser les octets du modulo est tentant:Le cmpd #TWO_PI/2 coute 4 octets. C'est énorme!

Si on veut préserver une précision similaire, il faudrait prendre PI au plus proche de 3.14159*256 (800 et quelque) tout en étant une puissance de 2. PI=1024 semble être un bon candidat. Il faudra que je teste ce que ca donne. Avec 2PI=2048, le modulo signé entre -PI et PI devient soit On gagne 3 octets. Pas mal! Mais en fait on doit pouvoir faire mieux en travaillant avec des nombres positifs, mais en effectuant la soustraction de 2048 uniquement pour le calcul du polynome du sinus en s'épargnant le "suba #8" final. A voir...

Mh.. je dis peut être une bêtise, mais il me semble que :

CLRA
ADDD ,X

peut être remplacé par

LEAX B,X

?

Ah oui les multiplications. On peut bien sur faire comme indiqué ci-dessus, mais on peut faire bien plus court: Hein, ca fait une multiplication ce truc? En fait oui, en plus signée. Vraiment? Et oui.

Ca mérite une explication. Sqrtab est un tableau contenant les valeurs de pour toutes les valeurs de v dans le double de plage qui nous intéresse. Ici à cause du sinus, v varie entre -PI et PI in nous faut donc réserver la plage -2PI..2PI, soit environ 3.3Ko. Ca tient dans la RAM.

Le code ASM ci-dessus calcule en fait c'est à dire Si on développe(*), on obtient miraculeusement EUREKA! On vient d'effectuer une multiplication en virgule fixe en utilisant uniquement additions. Qui plus est, la formule marche indépendamment du signe de u et de v à partir du moment ou (u+v) et (u-v) restent dans l'intervalle réservé de sqrtab. Bref on a obtenu une multiplication signée rapide, et ça c'est cool!

Cette technique du tableau pré-calculé des valeurs carrée est utilisé dans les CPUs n'ayant pas d'instruction réalisant des multiplications built-in (PIC, 6502, etc..)
___
(*) Souvenez vous des identités remarquables qu'on dont on se demande à quoi elles peuvent bien servir en pratique. A noter que la démonstration n'est pas rigoureuse car dans le calcul des v*v/4, il y a des fractions de perdues. En toute rigueur il faudrait faire le calcul avec les couples (u, v) du type (pair, pair), (pair, impair) et (impair, impair). Mais cela ne change pas le résultat. Dans tous les cas on obtient bien le produit u*v.

Ca marcherait si X contenait la valeur à incrémenter, mais X pointe ici sur une valeur mémoire qu'on veut incrémenter. Pour avoir un équivalent il faudrait écrireAvec un joli code auto-modifiable à la clef. En fait on peut faire plus propre avec Il faudrait voir ce qui est plus avantageux entre les pshs/puls et le code auto-modifiable.

Par contre le "LEAX b,x" est signé et ici on veut faire une addition non signé. Pour arriver à faire cela, il faut prendre "ABX" qui a en plus l'avantage de ne couter qu'un seul octet et 3 cycles. Par contre j'ai l'impression que même avec le ABX, ca prend plus de cycles et d'octets que "CLRA; ADDD". Si on peut se passer du pshs en réorganisant le code autour, ça peut être avantageux, mais je pense que le coup du 2PI=2048 est plus prometteur.

En fait c'est pas évident, car PI=1024 signifie que l'unité vaut 326, dans ce cas, la multiplication fixedpt de U par V vaut: et on voit apparaitre une division par 326 là ou précédemment on avait une division par 256 laquelle était très simple à réaliser (Il suffisait d'ignorer un octet).

La division est une opération couteuse en pratique, mais dans le cas d'une division par une constante on peut transformer l'opération en une multiplication par une autre constante suivie par un gros décalage: La multiplication par 201 revient à quelque additions et décalages (201 = 1 + 8 + 64 + 128), mais il faut travailler sur 32bits à présent et les décalage sur 32bits sont couteux en instructions pour le pauvre 6809. C'est pas génial!

Finalement je crois que prendre l'unité à 256 et travailler modulo 2PI = 1608 est plus rapide et plus compact que d'essayer de simplifier le calcul du modulo.

Hein? C'est quoi cette arnaque. Bien sur que 3Ko tiennent en RAM, mais ça ne tient pas dans les 256octets du début. C'est quoi le truc?

Le truc: c'est simple, au lieu d'avoir les valeurs de sqrtab dans le code, il suffit de les calculer. Calculer comment? Avec le code du mul? C'est idiot, on tourne en rond! En même temps avec des sinus et des cosinus, tourner en rond présente une certaine logique

En fait pour calculer les valeurs consécutives des carrés, il n'est pas besoin de multiplier. Savoir additionner suffit: donne Bref en accumulant les entiers impairs consécutifs on énumère l'ensemble des carrés. Carrément cool, j'adore Cela peut s'étendre aux fixed-point 8.8 en remarquant que c'est à dire que cela revient à éliminer les 8 bits de poids faibles du carré des entiers qui seront donc calculés sur 24bits pour le coup. Grâce aux instructions d'addition avec carry sur 6809e, le cumul sur 24bit est trivial(code facilement optimisable).

C'est en cumulant toutes les optimisations présentées:

* calcul en fixpt 8.8 au lieu de floats,
* calcul du sinus à partir des multiplications,
* multiplication rapide à partir du tableau des valeurs carrés,
* initialisation du tableau des valeurs carrés via l'accumulation des nombres impairs

Qu'on peut arriver à faire tenir dans 256octets d'asm autonomes un algorithme javascript utilisant des bibliothèques externes et un browser de plusieurs Mo.

sam (a propos de javascript, voici une curiosité: une emulation de x86 faisant tourner un linux).