un rien de mise au point

Bonne petite journée bien remplie ... Le nouveau système de debugging pour Bilou avance, avec déjà la possibilité de placer des "breakpoints" sur les transition de la machine d'état, et l'affichage des coordonnées des zones de test. Je n'ai pas encore toutes les fonctions souhaitées, bien sûr. Je dois encore rajouter la possibilité d'interrompre l'exécution lorsqu'un nouveau monstre apparaît dans le voisinage immédiat de Bilou, histoire de pouvoir faire un break *aussi* sur les transitions des monstres proches.

Par contre, le jeu est actuellement interrompu immédiatement après la collision qui m'intéresse -- et non pas immédiatement avant, comme je l'aurais voulu :-/

At last a little day off. I've been working a bit on the in-game debugger for Bilou, giving it the ability to set breakpoints on state transitions. That's not yet covering 10% of the desired features, but it can already be somehow handy. Unfortunately, the game is interrupted *right after* the collision of interest, rather than *right before* it happens... I need to think about that a bit more, but first, some dish-washing is waiting for me: I've got some friends at home last Friday, and the glasses aren't clean yet...

Tracking Memory Bugs

malloc et free sont des outils formidables, mais quand on s'est un peu embrouillé dans son code, ça devient vite une plaie. Je m'explique: le système d'allocation dynamique ne fonctionne pas "magiquement": il conserve autour des blocs libres et occupés des informations : taille de la zone, prochaine zone libre, etc. Elles sont évidemment importantes lorsqu'une zone libre est allouée ou qu'une zone occupée est libérée, mais elles servent aussi lors d'opérations de "compaction" (pensez au defrag du disque windows, vous n'êtes pas loin). Si on dépasse l'espace alloué pour une zone A, on peut facilement aller écraser les informations de contrôle d'une zone B. Du coup, on perd le lien entre la cause de l'erreur (le code qui gère A) et ses conséquences (erreur lors de la libération ou de l'allocation de B).

Dynamic memory allocation is a key aspect of programming that both open new horizons and puzzle newbie programmers. Unfortunately, it can also become a real nightmare for the seasoned programmer who has overestimated his skills, even just temporarily. malloc and free are not built from magic out of the void*, of course. They are algorithms that use small memory headers to maintain internal information about which block is free, how big is what, etc. This information is used when allocating/freeing blocks, of course, but also in the process of coercing small, contiguous free blocks into a larger one to avoid excessive memory fragmentation.
The problem is, that if code responsible for block A trashes information about block B (e.g. due to a buffer overflow bug), the error remains latent until block B is used again, and by then, you completely lost the knowledge that A is the faulty guy.

Ca fait un moment que je traine un bug de ce genre dans runme, sans trop savoir si c'est mon code qui est en faute ou celui de NTXM, le module player que j'y ai intégré. Bug plus ou moins facile à reproduire d'une révision à l'autre, mais que je sais être lié à une erreur de gestion de mémoire grâce au "crash code address" indiqué sur l'écran "guru meditation". Ces dernières semaines, j'ai pas mal avancé dans la gestion des erreurs et j'ai maintenant une fonction die() qui peut reprendre la main en cas de guru meditation ou d'exception C++ non traitée. Elle peut à présent tenter de retourner au moonshell, mais aussi afficher le contenu de n'importe quelle zone de mémoire de la DS. De quoi étudier la situation de manière un peu plus méthodique.

I know that I've got such a bug in runme (hence the lack of releases and the extensive use of gedsdemo). It's reappearing now and then and then hides again for a few releases. I've already proceed to a few code sanitization steps, but it doesn't look like i've been effective. With my recent findings (__cxa_terminate) and the introduction of a die() loop that replace main() after a guru meditation has been notified, I've given myself a memory inspection tool that let me follow "valid blocks" (starting the list from entries in __malloc_av_, the entry point of free lists) up to a faulty block that precedes the one where malloc/free() triggered an exception due to a wrong size.

Now, the goal is to trace back the owner of this memory block ... to be continued.
Un papier ... un bic ... pas mal de patience et la DS branchée sur chargeur ... C'est parti.

BBL metadata.

Voilà. Une fois qu'on dispose de tout un jeu de .BBL avec les tileset correspondant, c'est bien plus simple de reconstituer le rôle des 20 bytes de contrôle ... C'est ce que fait de son mieux ce petit outil "bblmeta.pl" que je vous offre également.

Chaque ligne rappelle le numéro du bloc (en hexa) et sa position dans l'image générée par bbl2png (le premier, par exemple, r02 c12 correspond au premier canon, tourné vers la gauche sur la 3eme ligne de l'image). Suit ensuite les "flags" tels que lus dans le fichier .BBL puis l'interprétation de ces flags par le script bblmeta.pl

J'ai repris la technique des répertoires UNIX: un '-' chaque fois qu'il n'y a rien à signaler, une lettre sinon. Ainsi "B--a-K" serait un bloc solide (B) animé qui interagit avec une clé (probablement une porte). "--g-+-" est un bonus qui rapporte uniquement des points, etc. Pour être exhaustif, je dirais que le programme reconnait:

1. Bloc, Floor, Wall ou ciel (-)
2. Pickme : l'objet peut être ramassé pour l'inventaire
3. g, l ou r : gravité normale, vers la gauche ou la droite. Les autres combinaisons ne sont pas reconnues.
4. a : bloc animé,
5. t: réagit au contact
6. bonus/malus : H=hitpoints, x=kills, + : score
7. L = 1UP, K=clé/porte.

En plus de ces "flags", certaines valeurs sont indiquées dans une liste entre parenthèse, comme la succession des blocs pour une animation, le nombre de hitpoints ou de clés, ou de points modifiés lors d'un contact , le numéro du monstre tiré (pour les blocs qui tirent des monstres), etc.

Here comes a second funny PERL script. It extracts meta-data from .BBL (Background BLocks), .CBL (Character BLocks) and .MBL (Monster BLocks) produced by RSD Game-Maker. If you used to write games with that editor, feel free to use that tool to retrieve all meaningful elements and port your old funware to some new platform. If you do so (or just plan to do so), please share the joy and post a comment.

This tool is a kind of "preliminary" reverse-engineering tool. It can tell you roughly what are the properties of individual blocks but detailed information may need to be looked up in the 40-digits hex string. Each line describes a block. Right to left you'll have the following information :

1c (r01 c13): 400100000000000000ffff1b64001c0400010000  --ga-x-  (a1b,100)(h-1)
^    coords   |--- complete hex dump of meta-data ---|  |flags|  |---details--|
+- block number

On the right side, "flags" tell you roughly what are the properties of your block. here you see an Animated block that has downwards Gravity and that hurts the player (x) on contact. Details tell you that it animates to block 1b after 100 ticks and that hitpoints are reduced by 1 on contact. On the left, you have block number (block #x pixels are located at bytes x*420..x*420+399 in xBL file) and the row/column coordinates on the picture generated by my former bbl2png.pl script.
Bref, ce n'est certainement pas aussi souple que l'éditeur du game-maker (et d'ailleurs, ce n'est pas un éditeur, juste un outil d'inspection), mais ça capturera la plus grande partie des cas que l'on retrouve dans un jeu de plates-forme comme les Badman.

Hope it Helps ^_^
PS: 1st byte is the index of the generated monster (0x40 = no monster generated), thus byte 2 is likely the delay between two such generations.

Petits Pas

vouaip. Petit progrès sur SEDS, qui sait (enfin) effacer ce qui ne vous plaît plus. C'est pas ultra-ergonomique (pressez R pour activer le curseur, déplacez le curseur sur le bloc qui vous déplaît puis pressez X pour l'effacer), mais ça marche.

Il faut dire que pour l'instant, j'essaie au maximum de me concentrer sur un fichu article reprenant mes travaux de thèse pour un journal, et qu'en plus, j'ai du faire une "pause sans écran" pendant une ou deux semaines, mes petits yeux ayant dit "stop, on en peut plus" :-/

Bref, je vais vous laisser vous rendre compte que j'ai pratiquement triplé la taille de mon post précédent (sur l'appleman), uploadé plein d'images et tout, et aller porter le dernier Maliki à ma fée avant que Morpheus ne l'emporte. Moi j'attaque les robots d'Asimov ;)

Enfin, avec tout ça, j'ai enfin réussi à "réparer" mon tileset de forêt et j'en ai profité pour faire un peu le ménage (virer les vieilles pommes et les souches qui ne servaient plus à rien ;) Restera à pouvoir "extraire" les anims et autres sprites, mais ça, ce sera une autre histoire, parce que là, je suis impatient d'essayer d'implémenter les tiles pentus.

*edit*: oh, et j'ai réussi à faire de "spr2png" un convertisseur reconnu par Image Magick. prochaine étape, en faire un vrai type mime reconnu par gnome et les autres ^_^

tiles extraction ...

Un autre petit outil en Perl (basé sur la bibliothèque de manipulation d'images Imlib) qui décortique une image et identifie les tiles uniques (8x8) et le nombre de couleurs utilisées...
Il ne fallait pas grand chose pour en faire un convertisseur .gif->.spr un peu plus automatisé. Je m'y suis attelé ^_^. L'outil en question s'appelle "imlib2spr.pl" et est disponible dans le CVS du projet 'runme'.

I've been working on a new small (PERL) tool for SEDS/runme. "imlib2spr.pl" is using the "imlib" package to open your .gif, .png ... pictures and identify uniques tiles and colors so that it can then convert them into .spr files.
It also builds a map of how to reuse those tiles to get the initial image back.

Mais pourquoi chercher à transformer une image .gif en un tas de tuiles, me demanderez-vous. Okay, certaines images contiennent des zones un peu répétitives et pourront donc prendre moins de place en VRAM... et c'est tout ?

Ooh non! Notre DS est effectivement capable d'afficher directement des images 'bitmap' (c'est ce que je fais quand vous envoyez à runme un fichier .pcx), mais avec une taille maximale de 256x256 ou de 512x512, selon la configuration d'écran choisie. Impeccable tant que vous voulez une image fixe, mais imaginons que je veux faire scroller horizontalement une image de 320 pixels de large, je fais quoi ?

Je passe à 512x512 ? le bitmap fera alors 256K, presque la totalité de la mémoire vidéo!
Je tronque à 256x256 et je redessine une colonne chaque fois que je me décale d'un pixel ? Bonjour le code!

Maybe you wonder why i'm trying so hard to split a picture into small tiles while i've shown with runme that it was fully possible to display a .pcx (and thus .gif and .bmp aswell) image straight on the screen. Well, the reason is scrolling. You very well can show a 256x256 image on the DS screen (which is 256x192) and side-scroll it again and again (using the 'scrolling wrap' hardware option). That will take you 64K worth of VRAM. Now if you want instead to side-scroll a 320x200 image, you'll get into trouble unless you're agree to devote 512K of VRAM just for your background image.

On the other side, once you have 'tiled' your background, you can easily repeat it as many times as you want: it's merely a matter of a few KB, and you can easily rewrite offscreen parts of the map as the scrolling goes so that you keep showing the right stuff at the right time, with a 64:1 reduction of the stress on VRAM.
Since we are running on gaming hardware, i think we should make the best possible use of it, shouldn't we?

Well, demo and code for that will follow once the 7.11.7 day is over.

Sous GBA, pas tout ces soucis: l'écran faisait 240 pixels de large et le mode bitmap 256x256 aussi, donc on avait tout loisir de redessiner des blocs dans la partie complètement masquée de l'écran, puis de scroller un peu, puis de redessiner, etc.

Eh bien, si l'on prend la peine de convertir notre bitmap en "tiles", on peut continuer ce petit jeu: une fois les tiles en mémoire, une "carte" peut très bien contenir deux fois l'image initiale sans nécessiter d'avantage de mémoire vidéo (allez, quand-même 1 ou 2K de plus, mais c'est quand même mieux que de passer de 64 à 256K, non?)

Bref, c'est Cyril qui sera content. Lui qui me proposait y'a pas 48 heures d'ajouter un mode "construisons notre map" dans SEDS ... On en est plus très loin ;)

à la base, c'était ça:

#!/usr/bin/perl
use Image::Imlib2;

$image = Image::Imlib2->load($ARGV[0]);
print STDERR "$ARGV[0]: ".$image->width."x".$image->height."\n";
while ($ty<$image->height) {
  $tx=0;
  while ($tx<$image->width) {
  foreach $y (0..7) {
    foreach $x(0..7) {
      ($r,$g,$b,$a) = $image->query_pixel($tx+$x,$ty+$y);
      $r=pack("C1",$r);
      $g=pack("C1",$g);
      $b=pack("C1",$b);
      $colors{"$r$g$b"}=$ncolors++ if !exists $colors{"$r$g$b"};
      $tile.=$colors{"$r$g$b"};
    }
  }
  $tiles{$tile}.="($tx,$ty)";
  $tx+=8;
  $tile="";
  $ntiles++;
}
$ty+=8;
print STDERR ".";
}


print scalar(keys(%tiles)) . "unique tiles (/$ntiles) detected\n";
print scalar(keys(%colors)) . "unique colors detected\n";

exit 0;

note: il nous faudra installer le package libimage-imlib2-perl pour faire fonctionner le tout.


rem: pendant ce temps-là, Globoeil nous faisait une release de son "virtual game maker DS" ...
à découvrir sur globoeil.fr/vgdms ...