Voici le descriptif d'un article sur l'affichage de sprites en code g‚n‚r‚. Si vous etes int‚ress‚ par cet article faites le moins savoir rapidement afin qu'il paraisse d'autant plus vite. L'AFFICHAGE DE SPRITES EN CODE GENERE INTRODUCTION Le code g‚n‚r‚ est une technique trŠs efficace en assembleur pour optimiser la vitesse de certaines routines. Attention, il ne s'agit pas de pr‚calcul mais bien de g‚n‚ration de programme 68000. En fait, cette technique s'appa- rente surtout … un clonage, c'est … dire que l'on ‚crit un programme qui va en cr‚er un second beaucoup plus grand. Actuellement, le code g‚n‚r‚ a ‚t‚ exclusivement utilis‚ dans les d‚mos (… moins qu'un jeu ?) et notamment dans les cas suivants : affichage de sprites (l'inventeur de cette id‚e est Philippe PAMART sur Amstrad en 1986 et votre serviteur le pionnier (et inventeur du terme de code g‚n‚r‚) sur ST), rafraichissement de scrolling (cf TCB), routine de droite (cf Mr BEE), fullscreens (cf MCODER ou ZARATHOUSTRA), de meme la majorit‚ de mes d‚mos est en code g‚n‚r‚. La cr‚ation d'une copperlist sur Amiga est un exemple simplifi‚ de code g‚n‚r‚. Dans cet article, je vais m'attacher … vous d‚crire les am‚liorations successives qu'on peut apporter … l'affichage de sprites. Je me bornerais … travailler sur des routines de sprites non clipp‚s (qui ne sortent pas sur les cot‚s) et qui ne m‚morisent pas l'image du fond. AU DEBUT ETAIT LE PREDECALAGE L'affichage de sprites est une tache ingrate et peu valorisante sur ST. En effet, on d‚ploie ‚norm‚ment d'efforts pour faire (mal) en soft ce que d'autres machines font avec leur hard. De plus la m‚moire ‚cran (dont la lin‚arit‚ est bien pens‚e : les plans se suivent...) ne facilite pas la tache... Donc si l'on veut afficher rapidement quelques sprites, on est vite … cours de temps machine si on d‚cale les sprites en temps r‚el (actuellement et aprŠs 1 an d'efforts la routine la plus rapide d'affichage de sprite d‚cal‚s/clipp‚s en temps r‚el est celle que j'ai utilis‚e dans Toki et elle n'affiche que 8 sprites 3/4 de 32*32 pixels sans effacement en 50 images/s, … ce propos je remercie Zarathoustra de m'avoir fait gagner 4 cycles tous les 16 pixels). La technique qui vient naturellement … l'esprit est le pr‚d‚calage des sprites qui peut etre am‚lior‚e avec un pr‚masquage. Exemple typique : MOVEM.L (A0)+,D0-D5 ;lit 16 pixels ;D0=masque pour l'affichage ;D1=forme plans 0 et 1 ;D2=forme plans 2 et 3 AND.L D0,(A1) ;masque l'‚cran OR.L D1,(A1)+ ;affiche les plans 0 et 1 AND.L D0,(A1) ;masque l'‚cran OR.L D2,(A1)+ ;affiche les plans 2 et 3 ... LEA 160-d(A1),A1 ;passage … la ligne suivante ... Routine bien connue de nombreux programmeurs (n'est pas Marlon ?). Cette routine est facilement am‚liorable mais retenons le principe de base : LECTURE/MASQUAGE PAR AND/AFFICHAGE PAR OR. DE L'OPTIMISATION Supposons maintenant que l'on veuille ‚crire une d‚mo qui affiche le maximum de sprites de 32*32 pixels de la meme forme en 50 images par seconde. Avec la m‚thode pr‚c‚dente on doit pouvoir arriver … afficher 15 ou 16 sprites mais certains programmeurs en affichent 20 … 25 !!! Et cela sans utiliser de sprites qui se suivent (immondes unlimited bobs). Leur secret est trŠs simple : au lieu d'avoir une seule routine d'affichage pour tous les d‚calages, ils ont une routine d'affichage par d‚calage c'est … dire qu'ils ont 16 routines d'affichage pour chaque sprite !!! On peut ruser en n'utilisant que des coordonn‚es paires afin d'avoir 8 sprites au lieu des 16 (cf l'‚cran d'Adso-Ziggy dans l'European Demos). Bien ‚videmment, ‡a bouffe un maximum de place en m‚moire mais on ne va pas s'arreter sur si peu, la vitesse justifie les moyens. L'autre problŠme est que les sprites ne peuvent pas etre clipp‚s simplement (ils ne doivent surtout pas d‚border sur les cot‚s). Maintenant que l'on a 16 routines pour afficher chacun des ‚tats du sprite, nous allons chercher … am‚liorer encore l'affichage. La premiŠre chose qui vient … l'esprit c'est de ne pas afficher les zones vides occup‚es par le sprite. Supposons que nous ayons une boule, nous n'avons pas … afficher ce qui est vide autour. Dans le meme ordre d'id‚e, on s'aper‡oit que l'on peut afficher sans rien masquer ce qui est … l'int‚rieur de ce meme sprite c'est … dire qu'on peut recopier par MOVE.L au lieu de faire un AND.L et un OR.L quand rien n'est transparent … cet endroit (par exemple au centre). A ce moment, chaque routine de sprite ressemble … quelquechose comme ‡a : AND.L #xxxx,(A0) OR.L #xxxx,(A0)+ AND.L #xxxx,(A0) OR.L #xxxx,(A0)+ ;affichage normal MOVE.L #xxxx,(A0)+ MOVE.L #xxxx,(A0)+ ;affiche sans fond ADDQ #8,A0 ;rien … afficher LEA 160-xx(A0),A0 ;passage … la ligne suivante Remarquez que j'ai mis des xxxx qui repr‚sentent les valeurs courantes au lieu de passer par les registres comme avant. Si on g‚nŠre une seule routine d'affichage avec des lectures de tables et 16 tables contenant les pr‚d‚calages de sprites, on tombe sur une technique, trouv‚e par Nick des Carebears, et qui semble avoir ‚t‚ utilis‚e dans Seven Gates of Jambala. ENCORE DE L'OPTIMISATION... Avant de poursuivre, prenons le temps de r‚fl‚chir aprŠs avoir pos‚ une nouvelle notation. Appelons : A, la donn‚e … afficher=source B, le masque d'effa‡age=mask C, la donn‚e de l'‚cran=destination L'affichage d'un sprite s'effectue par : C=(C AND B) OR A Nous avons d‚j… vu 2 cas : 1) A=0 et B=$FFFFFFFF -> C=C 2) B=0 -> C=A D'autres valeurs simples sont : 3) A=0 -> C=(C AND B) on gagne un OR 4) B=$FFFFFFFF -> C=(C OR A) on gagne un AND 5) A=NOT(B) -> C=(C OR A) on gagne un AND A ce stade, l'‚criture d'un g‚n‚rateur de code est trŠs simple mais on peut encore faire mieux. ENCORE ? L'am‚lioration suivante est moins ‚vidente : il suffit de stocker les valeurs des donn‚es les plus utilis‚es dans les registres D0 … D7 et ainsi on gagne 8 cycles … chaque fois que l'on doit utiliser une de ces donn‚es. Je ne connais pas de sprite avec lequel cette technique ne marche pas ! Malheureusement, nous sommes oblig‚s d'effectuer 2 passes au lieu d'une seule pr‚c‚demment parce qu'on ne peut pas deviner quelles seront les valeurs les plus utilis‚es... Donc : 1Šre passe : calcul des fr‚quences des donn‚es 2Šme passe : g‚n‚ration du code Maintenant, le code ressemble … : MOVE.L #xxxxx,D0 MOVE.L #xxxxx,D1 ... AND.L D0,(A0) OR.L D1,(A0)+ ... LEA 160-xx(A0),A0 ;passage … la ligne suivante H‚las, bien vite, on se rend compte que cette assignation rigide des registres est p‚nalisante parce souvent plus de 8 valeurs sont r‚p‚t‚es dans les donn‚es et que les registres sont utilis‚s seulement … certains endroits. Il faut donc ‚crire un g‚n‚rateur DYNAMIQUE des registres, c'est … dire que les registres seront charg‚s quand on en aura besoin et qu'ils seront libres quand leur contenu sera devenu inutile. AND.L #xxxxx,(A0) MOVE.L #xxxxx,D0 ;on utilise D0 plusieurs fois OR.L D0,(A0)+ ; … partir de cet endroit Le problŠme principal est l'assignation coh‚rente des registres qu'aucun programmeur n'a actuellement r‚solu : les registres sont parfois charg‚s pour n'etre utilis‚s qu'une ou deux fois. TOUJOURS ! DŠs que l'impl‚mentation dynamique est effectu‚e, le code va d‚j… beaucoup plus vite, mais comment peut-on faire mieux ? Simplement en optimisant le code au fur et … mesure de la g‚n‚ration. Voici une liste que j'espŠre exhaustive de toutes les optimisations connues : - mettre des offsets quand on a moins de 4 instructions entre 2 LEA ou ADDQ - transformer les LEA d(An),An en ADDQ - utiliser des AND.W/OR.W/AND.B/OR.B quand les AND.L/OR.L peuvent etre r‚duits (donc utiliser les registres en .B ou .W) - utiliser les registres An dans le cas de MOVE.L r‚p‚t‚s ex : MOVE.L A1,(A0)+ on ne peut pas utiliser les registres An avec OR ou AND. - mettre des MOVEM.L quand plusieurs MOVE.L de suite - gagner des registres avec : OR.B #$80,xxx -> TAS xxx (ne marche pas sur Amiga !!!) MOVE.B #$FF,xxx -> ST xxx CLR.B/W/L xxxx au lieu de MOVE.B/W/L #0,xxxx BSET/BCLR xxxx au lieu de OR ou AND avec 1 seul bit … changer - gagner des cycles avec : MOVEP.W/L au lieu de 2 (ou 4) MOVE.B ADDQ remplace OR si les bits mis … 1 ont ‚t‚ effac‚s avant ex : AND #$FFFE,D0 OR #1,D0 -> ADDQ #1,D0 - faire les OR avant les AND ex : AND #$F000,D0 AND #B OR #$100,D0 OR #A donne : OR #$100,D0 OR #A AND #$F100,D0 AND #(A OR B) cette astuce permet d'avoir certaines valeurs plus fr‚quemment... - am‚liorer le chargement des registres : MOVE.L #xxx,Dn -> MOVEQ.L #xxx,Dn quand -128<=xxx<=127 chargement en "rafale" par MOVEM.L transvaser les valeurs de registre … registre et utiliser une des instructions suivantes : EXT.B/.W,NOT.B/.W,ADDQ.B/.W,SUBQ.B/.W,SWAP, NOT.B/.W,NEG.B/.W ex : MOVE.L #$F000FFFE,D0 MOVE.L #$F0000001,D1 mieux : MOVE.L D0,D1 NOT D0 DAMNED, ENCORE DES CONSEILS, MAIS QUAND SE TAIRA-T-IL ? Arriv‚ … ce point l…, je vous conseille de r‚fl‚chir aux suggestions suivantes : - mettre un compteur de cycles pour ‚viter d'avoir … chronom‚trer les routines g‚n‚r‚es - le g‚n‚rateur doit pouvoir g‚n‚rer n'importe quelle configuration de plans (1,2,3 ou 4 plans) - le g‚n‚rateur doit pouvoir laisser n'importe quel registre libre (afin d'int‚grer le code en full-screen ou laisser des registres aux routines d'interruptions) - optimiser le code final … la main (ce que je n'oublie pas de faire, merci) - faire toutes les configurations possibles de couleur ex : avec un sprite en 3 couleurs (=2 plans) dessiner tous les sprites possibles en m‚langeant les couleurs, g‚n‚rer et prendre la routine la plus rapide. avec 3 couleurs on a 3!=6 possibilit‚s : 123,132,213,231,312,321 avec 16 couleurs, laissez tomber ! (16!=beaucoup trop) - le mieux est de stocker le masque dans la source du sprite car cela permet d'utiliser la couleur 0 dans le sprite … g‚n‚rer. Aussi voici une petite routine qui permet de convertir un sprite dans le format d‚sir‚ (avec recolorage du sprite). ********************************* - si le fond est d'une couleur uniforme : - si les sprites affich‚s ne se superposent pas, on n'est pas oblig‚ de g‚n‚rer les AND (ex: loader Transbeauce 2 disk 1) - si les sprites affich‚s se superposent, celui qui est en dessous de tous les autres peut etre affich‚ en MOVE (n'est-ce pas Adso ?) - dans tous les cas, le mieux est de g‚n‚rer des routines d'effa‡age pour chacun des d‚calages des sprites (avec MOVEM.L, s'il vous plait). De plus vous vous apercevrez que les routines d'effa‡age se ressemblent toutes ‚norm‚ment, donc, pour gagner de la place on peut les regrouper (ex: toujours TB2 disk 1)... - l'optimisation ultime dans un tel g‚n‚rateur est la r‚organisation totale de l'affichage du sprite. Le sprite ne doit pas obligatoirement etre affich‚ de haut en bas mais par exemple en commen‡ant par la 1Šre ligne puis la derniŠre puis la 2Šme puis l'avant derniŠre puis la 3Šme... Le gain est faramineux quand le sprite est sym‚trique verticalement mais doit etre plus difficile … ‚valuer quand le sprite n'a pas de sym‚trie particuliŠre. Plusieurs ball-d‚mos utilisent cette astuce mais dans ces d‚mos, le code ‚tait g‚n‚r‚ … la main... FINALEMENT Voil…, j'espŠre que cela vous donnera envie d'‚crire un super-g‚n‚rateur de code mais … d‚faut vous trouverez ci-dessous le listing du mien. Toutefois, celui-ci date de 2 ans (d‚j…) et n'utilise pas toutes les optimisations que j'ai d‚crites ci-dessus (notamment les MOVEM.L, arghh). Il effectue son travail en 2 passes mais est trŠs lent (caract‚ristique commune … tous les -bons- g‚n‚rateurs). J'ai vu un g‚n‚rateur 7 passes (par Alain Boisram‚) et Altair m'a signal‚ que le sien ramait en 24 passes (!!!). Apparemment les meilleurs en ce moment sont ceux de Terence du groupe Prism et d'Alain Boisram‚ mais le mien est assur‚ment le plus versatile parce qu'il permet de g‚n‚rer n'importe quelle configuration de plans, qu'il ne bugge pas (!!) et qu'il marche sur tout ST (je travaille avec 512K). Si vous trouvez de nouvelles techniques, faites-en profiter les autres. MCODER.