Le problème
Sur Atari ST, Lore of the Ember tiendra sur deux disquettes double densité. Pas de format maison, pas de pistes en plus : des disquettes de 720 Ko ordinaires, comme on avait l'habitude d'utiliser. Cinq actes, quatre niveaux par acte, cinq boss, l'intro, l'écran titre et le programme : tout doit y entrer.
Or la première disquette était déjà presque pleine. Le programme et son module d'accueil, l'écran titre, l'intro, l'écran d'attente et le premier niveau y occupaient 642 Ko sur 711 utilisables. Il restait 69 Ko, et le niveau 2, avec son jeu de tuiles et sa carte, en demande 85. Il ne rentrait plus.
La plupart des jeux de l'époque utilisaient le même système : rien n'y est stocké en clair. Chaque fichier est compressé, et le jeu le décompresse au moment de le charger. C'est ce que j'ai fait.
Le format : ZX0
J'ai choisi ZX0, d'Einar Saukas. C'est un format de la famille LZ77, pensé pour les petites machines : le fichier compressé n'est qu'une suite de trois sortes de blocs.
- Des littéraux : « recopie tels quels les N octets qui suivent ».
- Une copie avec le même décalage que la précédente : « recopie N octets pris à la même distance en arrière que la dernière fois ».
- Une copie avec un nouveau décalage : « recopie N octets pris D octets en arrière ».
Les nombres (les longueurs, les décalages) sont écrits en codes gamma d'Elias entrelacés : un petit nombre prend peu de bits, un grand en prend davantage, et le décompresseur les lit bit par bit sans jamais connaître leur taille à l'avance. Le décalage, lui, est coupé en deux : la partie haute en code gamma, la partie basse dans un octet entier.
Tout l'intérêt est du côté de la décompression. Elle tient en quelques dizaines d'instructions 68000 et elle va vite : c'est le même décompresseur qui sert déjà à l'intro et à l'écran d'attente.
Le compresseur : salvador
Trouver la meilleure façon de découper un fichier en blocs est le travail du compresseur, et c'est lui qui est lent. Mon outil d'origine cherchait le découpage optimal ; je l'ai remplacé par salvador, d'Emmanuel Marty. Il produit le même format, avec une densité quasiment identique, en une seconde ou deux par fichier.
Un détail de format m'a posé souci : ZX0 existe en deux saveurs, et le décompresseur que j'avais écrit pour l'intro lit la seconde. Dans la version standard, seule la partie haute des décalages a ses bits inversés ; dans celle que lit le jeu, ce sont les bits de tous les codes gamma, longueurs comprises. Plutôt que de toucher au décompresseur, mon outil d'emballage corrige la sortie de salvador : il relit le flux, repère chaque bit de longueur et le retourne. Les bits restent à la même place, seul leur sens change, et rien n'est perdu.
Chaque fichier compressé est ensuite relu par un décompresseur de référence, qui doit redonner l'original octet pour octet. Sinon, la disquette ne se fabrique pas.
Décompresser sans mémoire en plus
Le jeu tient dans un méga-octet, au millier d'octets près. Pas question d'ajouter un second tampon pour y lire le fichier compressé avant de le décompresser.
La solution est classique : la décompression sur place. Le fichier compressé est lu à la fin du tampon de destination, et le décompresseur écrit depuis le début. Il avance plus lentement dans sa lecture qu'il n'écrit, puisque chaque bit lu produit plusieurs octets, mais il est parti avec une large avance. Tant que l'écriture ne rattrape jamais la lecture, rien n'est écrasé avant d'avoir été lu.
Ce « tant que » se vérifie : à chaque fichier, mon outil simule la décompression et note de combien l'écriture s'approche au plus de la lecture. Si le tampon du jeu n'a pas cette marge, le fichier reste en clair, et le jeu le lit comme avant. Il reconnaît un fichier compressé à son en-tête de huit octets : une signature, puis la taille une fois décompressé.
Le piège de l'adresse impaire
La première disquette compressée plantait au premier chargement. Le décompresseur partait copier des octets depuis une adresse absurde, et le programme s'arrêtait net.
La cause était en amont. Le fichier compressé fait une longueur quelconque, et je le posais exactement à la fin du tampon : selon sa taille, il commençait donc à une adresse impaire. Or la lecture de la disquette passe par le DMA, qui ne sait écrire qu'aux adresses paires. Les octets arrivaient tous décalés d'un cran. Le décompresseur lisait un flux qu'il ne reconnaissait plus, et à la première copie, il allait chercher ses octets n'importe où.
Le correctif tient en une ligne : le fichier est posé à l'adresse paire juste en dessous, un octet plus tôt si besoin, et mon outil compte cet octet dans sa marge.
Ce que ça donne
| Place sur la disquette | En clair | Compressé |
|---|---|---|
| Écran titre (logo, titre et son animation) | 82 Ko | 9 Ko |
| Niveau 1 (tuiles et carte) | 66 Ko | 16 Ko |
| Niveau 2 (tuiles et carte) | 85 Ko | 19 Ko |
La première disquette est passée de 69 Ko libres sans le niveau 2 à 173 Ko libres avec lui. La version pour disque dur, elle, reste en clair : la place n'y manque pas, et elle charge sans rien décompresser.
La suite
Le plus gros fichier de la disquette reste le programme lui-même : 340 Ko, presque la moitié. Il se compresse à peu près de moitié. Mais il ne peut pas se décompresser tout seul : il faudra un petit lanceur qui le lise compressé, le décompresse en mémoire, remette ses adresses en place et lui passe la main, le tout sans dépasser le méga-octet. C'est le prochain chantier, et après lui, il ne restera qu'à ranger : le lancement et l'acte I sur la première disquette, les quatre autres actes sur la seconde.
Laisser un commentaire