Indexing my Thesis

Okay. For those who have missed it so far, i'm writing down my PhD thesis ... and it's built with Latex.

Updating and completing a 1 year-old Latex document with new parts coming from conference paper, autonomic thoughts, etc. is some challenge i haven't met so far, so i'm upgrading my toolset as well.

Au cas où vous auriez loupé un épisode, je suis en train de rédiger ma thèse. Et je fais ça en Latex. Un document commencé il y a plus d'un an que je dois compléter avec des articles de conférence, etc. Bref, un des plus gros challenges auxquels j'ai eu à faire face jusqu'ici.

Le défi d'aujoud'hui ? Garder le fil de ce dont j'ai parlé, et où j'en ai parlé tandis que je fusionne et réorganise tous les bazars. En gros, construire et utiliser un index pour mon document.

Today's challenge: how to keep track of what i'm talking about in the different part and see whether merging/reorganizing things would help. In a word, building and working with an index of terms in my manuscript.

http://www.dtr.isy.liu.se/latexindex.html is a first good reference. Just adding \usepackage{makeidx}, and \makeindex \printindex to the document structure, and voilà. (oh, well, almost. I also have to make sure i properly call the makeindex command between latex calls :P)

Un petit peu de googling, et j'ai trouvé comment me servir de \usepackage{makeidx} de \makeindex et \printindex (oh, ne pas oublier d'appeler makeindex sur la ligne de commande, au passage). Reste à remplacer ici et là les \emph{protected tags} par quelque-chose comme \index{tags!protected}\emph{protected tags} ... dans près de 70,000 mots répartis sur 37 fichiers source ... de quoi devenir dingue si on ne fait pas un peu attention.

Now, i'm starting to do mass-replacement of "\emph{protected tags}" with "\index{tags!protected}\emph{protected tags}" ... in those +70000 words split in 37 source files ... Time for something to automate grep/open-file/query-replace, no?

Well, another google search pointed me at Sam teachs yourself Xemacs in 24 hours where they had a very nice explanation on regexp-query-replace and how to use the etags tool to operate on many file at a time. Roughly, all i have to do is invoking "wasp/phd> etags *.tex" to produce a condensed TAGS file for the current directory and then invoke M-x tags-query-replace to replace all the instances of the text with index-augmented text (well, i'm prompted whether i want the replacement or not ;)


Heureusement, il y a Sam, pour m'aider à comprendre le fonctionnement de etags de manière à invoquer M-x regexp-query-replace et remplacer tous ces mots l'un après l'autre en un clin d'oeil.
Allez, les windoziens. Qui dit mieux ?

edit: plein d'autres trucs latex en FAQ sur cette page

Beware of DmaCopy()

Hop. Entre deux transparents pour ACNM'07 et la navette pour IM'07, j'ai profité du portable emprunté à mon oncle pour faire un peu de HomeBrew. Il faut dire qu'avec son lecteur de carte SD et ubuntu "feisty", c'est méchamment plus pratique.

J'avais un problème avec le "scrolling" de la zone de travail, que j'utilise abondamment pour faire des tiles qui peuvent s'emboiter, et plus étonnant, celà n'arrivait que sur une 'vraie DS' ... aucun problème dans desmume (pour une fois). A force de chercher des failles hardware sur mon Network Processor pour ma thèse, j'en suis venu à suspecter les fameuses "commandes de copie DMA"...

Between two slides for the ACNM'07 workshop and the shuttle to IEEE IM'07, i'm enjoying my uncle's laptop for homebrew coding. With embedded SD card reader and the "feisty" Ubuntu, it's *way* better than playing with my regular hardware ...
So i took the opportunity to debug something odd occuring when "scrolling" the working grid -- some feature i'm heavily using to make tiles that ... tile. While it worked flawlessly in desmume emulator, it seemed to miss the first click on scroll button on real DS hardware ... As i'm looking for hardware issues on a Network Processor for my PhD thesis, i suddenly suspected something wrong with DMA copies.

Et j'avais raison. Le code du "scroll" proprement dit, c'est quelque-chose comme

for (i=0;i<16;i++) {
char extra=data[i*16]; // save first pixel
for (j=0;j<15;;j++) data[i*16+j]=data[i*16+j+1]; // shift row
data[15+i*16]=extra; // get back first pixel
}

après quoi, j'appelais à nouveau ma méthode "render" du widget "grid", laquelle faisait gentillement:
I first used to shift the working space (data[] array) in place, (see above), and then called the gridWidget::render() method which issued row-per-row DMA copies as below:

for (i=0;i<16;i++)
 dmaCopy(/*from, char*/data+16*i,
         /*to, uint16 */VRAM+ROWSIZE*i,
         /*bytesize*/16);

Ouais. Bin si vous avez du code pareil qui se comporte bizarrement, courrez bien vite remplacer les "dmaCopy" par des "memcpy" bien gentils. Je n'ai pas le fin mot de l'histoire, mais n'oublions pas que tout ce que le processeur ARM lit/modifie passe par un cache, alors que les déplacement DMA, pas. En clair, pour peut que la commande DMA se mette à lire notre ligne de données avant que le cache n'ait été réécrit en mémoire centrale, c'est foutu.

Well, if you have something like that in your code and that the code behaves weirdly, do a rush query-replace of dmaCopy with standard memcpy. I haven't investigated this down to the nitty-gritty details, but we should keep in mind that the ARM processor read/writes goes through a cache while DMA memory transfers typically operate directly on physical DRAM rows... So to make it clearly, a DMA command could very well start moving the bits _before_ the content of the cache has been committed to main memory. And bang, we're doomed.

That's what computer scientists call a race condition. wuuzaa.
En informatique, ça s'appelle "une condition de course". Géant, non?

Edit: stellar date 2009.05.29, Cornarac (the author of TONC, a major reference in GBA programming) has published an impressive and detailed tutorial on caching and dma : http://www.coranac.com/2009/05/28/dma-vs-arm9-fight/

BadmanDS est mal baré ...

Après le nettoyage des sources de Apple Rumble, j'ai voulu en profiter pour essayer de faire un petit "navigateur de niveau" du Game-Maker sur la DS ...

aouaich.

Bin les gars, c'est mal embarqué. Ma technique de "tiles à moitié transparents" répartis sur 2 plans, ça aurait presque pu marcher ... sauf qu'il y a des endroits où un tile devra nous montrer 2 blocs (lorsque les coins se touchent). Résultat
- soit je balaie la map pour trouver des quelles combinaisons nécessitent un tile dédié (en gros, je regarde tous les blocs voisins présent dans le niveau)
- soit je passe à 4 plans, mais je perd définitivement toute possibilité de construire des effets intéressants.
- soit je fais faire le gros boulot à un script Perl qui considèrera la map entière comme un gros BMP à découper efficacement en tiles 8x8

Bref, j'ai pas encore trouvé le truc ultime, mais ça s'annonce compromis.

Apple Rumble: sources release

Okay, chances that i will still work on Apple Rumble are (very) slim. That was a demo game. So below you'll find the link to get the sources, libraries i used, modified version of Desmume (not that i think it'll be practical to play in the emulator).

Voilà. Il n'y a que très peu de chances que je bidouille encore Apple Rumble. C'était un jeu-démo pour essayer les sprites créés avec SEDS, en fait, donc je vous offre maintenant ses sources (GPL). J'y ajoute les bibliothèques que j'ai modifiées et 'ma' version de Desmume (pas que le jeu soit simple à jouer dans l'émulateur, mais je n'ai pas trouvé d'autre émulateur DS sous Linux qui supportait les cartes FLASH et les routines de décompression du BIOS.


download apple-rumble 0.1b

What's wrong with software ?

Xorg session grew to +400MB of space ... thunderbird is slowly reaching +200MB, firefox is regularly killed by the "Out of Memory" daemon while both physical and swap memory are full.

Okay, maybe trying to run Ubuntu Linux in 2007 on a 1GHz-512MB is a bad idea, but honnestly, i don't see why it shouldn't work. Even my media player tend to consume more and more memory as times goes.

I remember the time where this machine was running SuSE Linux 8.x and when i could happily run my X session for nearly one year without having to restart anything. And i'm not even using any resource-demanding desktop like Gnome or KDE, neither am i using fancy XGL effects. Is *that* the price to pay for anti-aliased fonts ?

Some days, i think i'll never completely drop Operating System Development.

inside caverns ...

Tout a commencé par un visiteur venu du forum gba-dev (qui m'a conduit à retourner lire le post "ces jeux que vous voudriez voir implémenté sur DS"). Puis de fil en aiguille je suis tombé là dessus: doukutsu/csds-mushrooms.nds

Les décors m'ont immédiatement plu. Et cette histoire de champignon dans les caves m'a conduit à une investigation du phénomène "Cave Story".

Après une causette "digital painting / pixel art" avec Toad J'ai eu envie d'essayer de redessiner moi-même des rochers "à la cave story". Quand on y regarde bien, ça n'a pas l'air si dur ... Des formes bien géométriques, et le même genre d'éclairage que les blocs-à-pointe des forteresses de SMB3. Tenez, prenez n'importe quel programme de dessin (même MS paint fait l'affaire) et dessinez un carré gris moyen puis coupez le sur les diagonales. Ajoutez un triangle gris-clair sur le dessus et gris-foncé sur le dessous, vous obtiendrez qqch comme le premier bloc de l'image ci-dessous. Déjà une impression de 3D. Les rochers de Cave Story sont sur le même moule, mais le carré est mis "sur pointe" le plus souvent.

Backgrounds in Cave Story are somehow impressive in how they produce a nice effect with rather simple pixel art. If take the time to stop and watch them, they aren't so far away from SMB3's "spiky block" that appear in fortress. Pick any drawing program (including MS-paint), draw a grey square and its diagonals, then paint the upper triangle in light-grey and the bottom triangle in dark grey, and you're done with a 3D-like feeling. Rocks in Cave Story background work the same way except most of the time the square is "on an corner", making it consistent with the up-left lighting source.


Le résultat: du pur pixel art. 4 couleurs (#081800, #102400, #212c08, #293808), et presqu'exclusivement réalisé avec les outils "crayon", "ligne" et "remplissage" d'un 'paint' classique.


C'était l'occasion d'essayer the Gimp comme outil pour mes jeux vidéo. Une image 64x64, c'est encore difficile à gérer pour SEDS. Le truc pour construire des rocs 'qui s'assemblent' ? j'ouvre deux fenêtre, l'une de 64x64 (zoomée) pour le dessin et une de 128x128 armée d'une grille magnétique 16x16 pour recomposer l'image. Quand j'ai fini un élément et que je voudrais dessiner quelque-chose qui va passer "à travers" le bord de l'image, je recopie l'image en cours dans chaque coin de ma fenêtre 128x128 et je n'ai plus qu'à resélectionner une zone de 64x64 plus au centre de l'image résultante ^_^

So i gave The Gimp a try as a tool for video game graphics (my own editor on the DS cannot deal with 64x64 chunks very well atm.). And to make sure my blocks "tile" well, i just used two window, one with 64x64 for edition and a second one (128x128) with a 16x16 magnetic grid that can be used to rebuild the full image. The trick is to avoid drawing near the borders. If you need to do so, copy the 64x64 edited image back in the 128x128 and grab the center of that 128x128 image back for edition ^_^

Evidemment, des cailloux tous pointus, ce n'est pas très intéressant. Si vous regardez ceux de Cave Story, il y a:

• des craquelures: commencez un triangle presque noir à la base d'un rocher et terminez par une ligne qui est "en biais" par rapport au triangle,
  
• des irrégularités: choisissez un des "versants" et, partant de la base, ajoutez une ligne de la tonalité suivante. Si au lieux d'être plat, votre versant fait quelque-chose comme "----___", et s'il était clair, il y aura un endroit plus sombre au niveau de la transition "--_"
• des replats: c'est à mon avis un des effets les plus intéressants et facile: imaginez un polygone qui entoure le "sommet" de votre rocher. Sur les versants clair, dessinez l'épaisseur de ce polygone avec la teinte intermédiaire. Sur les versants "intermédiaires", contournez le polygone avec du clair (il y a un emplacement sur le bord du replat qui prend plus la lumière). Gardez vous bien d'avoir quelque-chose qui ressemblerait à un passage en "négatif couleur
• des ombres. Je n'en ai pas mis, mais on pourrait rendre plus sombre la base du côté "clair" d'un bloc très proche d'un autre.
  

Of course, just showing off bunch of spiky rocks doesn't impress anyone. So what do Cave Story rocks feature to be good-looking ? Cracks (draw a dark triangle from the rock's base and end up with an line that drift a little from the triangle's orientation), irregularities (start from the rock base, and add a lighter/darker line going towards the top, as if the rock was suddenly larger), "floors" (just draw a polygon around the rock's top with a lighter tone) -- which are imho one of the most interresting effects in the rocks, but that i may have overused.

He's the Terror who makes Errors ...

Retour en 1994 ou quelque-part par là à l'age d'or de PPP Team Software (moi, mon frère, Pierrick et quelques autres dont Pascal). A l'aide du fabuleux Game-Maker de Recreational Software Design (RSD), nous enchaînions niveau sur niveau puis jeu sur jeu les mercredi après-midi.

Back in '94, in the golden age of PPP Team Software, where we were spending our lunchtime creating games with the RSD Game Maker. Badman has quickly become one of our "best-known" funny platformer hero, and is starring 3 games while he was initially meant to be just a mid-level boss for Bilou's Quest. "Badman 1" was one of our "real" game produced with RSD tools, where the "terror-who-makes-errors" crosses manatthan roofs, japanese waterfalls, nazi jails and haunted mansions looking for clues about a terrorist take over to take place during the football world cup. Since my bros came up with a collection of .mod songs, it's very tempting to revive the 'best' 4 levels of the game on the Nintendo DS for an "anniversary edition" ...

Parmi la collection de personnages loufoques dont nous avons fait nos héros, il y avait Badman, sans conteste un de ceux pour lequel il y a eu le plus d'efforts investis. Les images reprises ici sont des captures d'écran de Badman 1, un de nos premiers "vrais" jeux, même s'il était encore entaché de pas mal de blocs venant des jeux "démo" livrés avec le Game Maker... Puisque Piet a (par la suite) écrit des musiques qui colleraient à merveille avec certains de ses niveaux, la tentation est énorme de reprendre les niveaux les mieux aboutis (4 en fait) et d'en faire une version "anniversaire" sur la DS. J'ai un modplayer, donc c'est ok pour les musiques ... les maps et l'IA des ennemis était excessivement simple au point qu'un week-end devrait suffire à tout récupérer.

Le gros problème, ce sont les images. Là où toutes les consoles travaillent avec des tiles 8x8, le GameMaker fonctionnait avec des blocs 20x20, ce qui va terriblement compliquer la composition des graphismes, etc. Pour des éléments comme les blocs de terre ou les briques d'arrière plan, je pourrais à la rigueur m'en tirer en passant d'un bloc 20x20 à 25 tiles (pour reconstruire un méta-bloc 40x40), mais ça va clairement coincer dès qu'on voudra avoir un seul bloc plutôt qu'un mur entier (voir la cascade).

Pas question non-plus de 'zoomer' tous les persos en 16x16. Badman ne ressemblerait plus à rien (et il faudrait retoucher tous les sprites). Pas question (toujours) de devoir prendre en compte toutes les combinaisons de blocs voisins pour construire les tiles "de jonction". Il me reste tout de même un espoir, jouer sur les plans multiples (un bloc sur le plan 1, le suivant par transparence sur le plan 2, puis retour au plan 1, etc).

There are a couple of technical issues to achieve this, mostly due to the mismatch between Nintendo console tiles (8x8 pixels) and RSD tiles (20x20). Plus, RSD game maker tileset and maps are stored in a proprietary format that isn't documented anywhere. Palettes and blocks (BBL, MBL files) aren't very sophisticated, I know how to display them on a DOS screen since '97. But .map files (levels) are still a mystery. I'll give them a reverse-engineering try this lunchtime. Let's open a hex editor and have a look ...

Reste à briser les secrets des fichiers .MAP ... je jette un rapide coup d'oeil aux premiers niveau de Badman ... Toutes les map sont scindées en 2 parties, et la 2ème partie commence toujours à la position 20000, ce qui suggère une map de 100x100 (avec 2 bytes par bloc)

Presque tous les blocs possèdent un code c8xx, sauf un petit nombre, et les premiers bytes sont tous différents, e.g.

SONI.MAP: 000a@(8,13) 0105@(8,33) 0200@(33,21)
0306@(33,36) 040d@(33,51) 050d@(67,46)

facts:

• .maps file look to have two distinct parts, and the first one is 20,000 bytes long, which suggests a 100x100 map with 2 bytes worth of data per tile
• tiles where there is no monsters have the form 0xC8yy and tiles where there is a monster have the form 0xzzyy, where zz is a relatively small number, that is unique over the map. That suggests "C8" means "no monster" and that zz is the monster's index in some other table.
• The second part has 5 words (16-bit) per entry, where "0040 0000 ffff ffff 0000" seems to be a filler for "no monster here".
  
• words 2 and 3 in that list seems to be X and Y coordinates of the monster on the map, while word #1 could be the ID of the monster to be used (that is, in the .MON file).
  

Pour le fun, j'ai noté les coordonnées auxquelles ces blocs apparaissent, en plus de leur valeur.

(SONI.MAP)

0004e20 000e 0000 000d 0008 0000:000e 0000 0021
0004e30 0008 0000:000e 0000 0018 0021 0000:000e
0004e40 0000 0024 0021 0000:000e 0000 0033 0021
0004e50 0000:000e 0000 0049 0021 0000:0040 0000
0004e60 ffff ffff 0000 0040 0000 ffff ffff 0000
0004e70 0040 0000 ffff ffff 0000 0040 0000 ffff

Répétition de blocs "0040 0000 ffff ffff 0000" une fois un certain point passé... Dans la map Soni, il y a juste 6 entrées avant ce "remplissage", ce qui correspond au nombre de blocs "spéciaux" trouvés.

000e 0000 000d 0008 0000 (8,13)
000e 0000 0021 0008 0000 (8,33)
000e 0000 0018 0021 0000 ...

Les mots 2 et 3 correspondent aux coordonnées où sont enregistrés les monstres sur la map. Il serait logique de supposer qu'il y a une 'liste de monstre' et que le premier des 2 bytes encode le numéro du monstre dans la liste (pour le retrouver facilement lors de l'affichage du niveau). Le premier mot serait logiquement le numéro du monstre à utiliser, quant aux deux autres valeurs (toujours à 0), aucune idée, ma foi.

En tout, il y a 2000 bytes de monstres (la 2eme partie) dans chaque map... Soit 200 monstres possibles... C8 est le numéro 200, le monstre inexistant ^_^

Pour info, j'ai déjà un convertisseur de blocs & palettes vers le format SEDS.
Dernières news, j'ai aussi reverse-engineeré le format des fichiers .GAM du game-maker RSD.

* krribit *

Un peu de pioche dans mes vieilles images Deluxe Paint, ce matin, et j'ai notamment retrouvé un des arbres (et son décor) que j'avais fait pour bilou. Au départ, un dessin au porte-mine que j'avais scanné (du temps où il ne fallait pas trembler pour faire un bon résultat avec le scanner ISA racheté à Pascal), puis utilisé comme "calque de référence" pour reconstruire intégralement le résultat que vous avez là. Ma technique de remplissage à l'époque consistait à utiliser un dégradé "mélangé" par deluxe paint (avec un point de lumière approprié) puis à passer un coup de "smooth" sur le tout (flou gaussien, quoi).

Les champignons, etc. on subi plus ou moins le même sort avant d'être retransformés en simples silhouettes pour les besoins du dessin.

^^ one of my older trees for Bilou, first drawn on paper, then converted and colourized using Deluxe Paint II. By that time, my technique was mainly using gradients that i'd smooth afterwards. Not always looking good, unfortunately. Meanwhile, Team17 was releasing SuperFrog on Amiga, and i must say that i quite love how they made their trees... Among other things, because they aren't just background, but gameplay elements aswell thanks to the leaves-platforms you can put where you want (okay, you *must* put at least two oth them at the bottom).

A peu près à la même époque, une bande de joyeux driles nous sortaient SuperFrog sur Amiga, ensuite porté sur PC. Bin, je dois vous dire, j'aime bien les arbres de SuperFrog. leur côté sympa, d'abord, le tronc "ligneux" comme si il y avait plusieurs "tuyaux" indépendant qui avaient fusionné pour faire l'écorce, etc.

Et, surtout, ils font partie du level design par ces "branchages" sur lesquels notre héro vert peut courir et sauter. Tiens, et par curiosité, je me suis amusé à décrotiquer un peu le feuillage.

Tout d'abord, il faut trouver un repère pour la grille. Le bord du sol nous donne un bon indice, reste à superposer l'image avec elle-même (avec un peu de transparence dans Gimp) et à la décaler vers la droite jusqu'à ce qu'un carré net nous apparaisse au milieu de l'image toute floue.

Voilà. Un coup de "Image>Configure Grid" et on est parti.

Bon, clairement le "trou" dans le feuillage a été construit sur base de 4 blocs (je les appelle A,B,C,D si vous voulez bien). Capturons ces 4 blocs et faisons-en un calque séparé en mode "différence". En le promenant le long de notre grille, les pixels identiques vont se retrouver tout noirs (x-x=0) ... si jamais on voit un carré complet devenir tout noir, c'est que un de nos blocs (A,B,C ou D) a été utilisé à cet endroit de l'image.
C'est bien sur le cas pour le deuxième trou du feuillage, mais à pas mal d'autres endroits, on retrouve nos blocs, à quelques différences près (des feuilles au lieu du trous, ou certaines feuilles retirées pour faire le bord de l'abre).

Giving a closer look to those leaves, it looks like they're (too) built out of tiles (rather than having one, large bitmap for the tree as it is the case e.g. in Rayman). Just stack two copies of the screenshot on top of each other, give them proper transparency and slide one of the layer... after 16 pixels, you should see a square of the leaves that is "sharp" while the rest of the image is blurred. That sharp square identify an exact superposition of two 16x16 blocks. Bingo: we can configure our Grid in the Gimp to match the game's tileset.

Now, it is clear, too, that the 'hole' in the leaves comes from a 32x32 block ... let's see if we can find it at other places in the tree. To do this, i just pick a copy of "A,B,C,D" block in a separate layer in "difference" mode. As i move that pattern around, i'll get big black boxes when one of the 16x16 block match.
En répétant le processus, on peut identifier les différents blocs de l'arbre, chercher éventuellement des blocs de base supplémentaires, etc. En fait, ici, quasiment tout le feuillage est construit sur 4 blocs de base qui ont servi à la construction du "trou". Seules les platformes que l'on superpose au feuillage et quelques "raccords" sur le bord du feuillage font exception à cette règle.

Chapeau.

Oh, et pour ce qui est des couleurs, (#045624,#047604, #049a04) pour les feuillages (#645614, #544604, #343204) pour le tronc (allez, avec un petit pixel de (#8c7644 ou #746634 autour de la bouche) et (#242224) et quelques touches de brun foncé pour les ombres du feuillage (audacieux, mais ça a marché, visiblement).

Repeating this approach, we can identify almost all tiles of the leaves as being edited versions of one of the A,B,C or D tile. Nicely done. Only a few 'border leaves' seems to escape that rule. And all this with at most 10 background colours (probably 16 with eyes and blue sky) ... less than what i used in Bilou on QuickBasic!

Allez, ciao. Pixelisez bien.

more frogs for nostalgics