Une disquette 3 pouces et demi posée sur une table en bois, éclairée par une lanterne, avec une étiquette écrite à la main : Lore of the Ember, Disk 1

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 ».
La phrase « la pierre, la braise, la pierre » décompressée en cinq blocs : 11 littéraux, une copie de 3 octets pris 11 en arrière, 6 littéraux, une copie de 2 octets avec le même décalage, puis une copie de 9 octets pris 22 en arrière
Une phrase de 31 octets, décompressée bloc par bloc. Les flèches partent de ce qui était déjà écrit : près de la moitié du texte n'est jamais stockée, seulement désignée.

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.

Trois états d'un même tampon : le flux compressé posé à la fin, puis la partie décompressée qui grandit depuis le début pendant que la lecture garde son avance, puis le fichier entier décompressé
Un seul tampon : le fichier compressé arrive à la fin, le fichier décompressé se construit depuis le début.

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.

Trois rangées de cases mémoire de $1000 à $1009. Le flux demandé à partir de $1003 ; le DMA l'écrit à partir de $1002, et le décompresseur lit B au lieu de A ; posé à $1002, il lit A
Le DMA de la disquette ne sait pas commencer sur une adresse impaire : il écrit à partir de l'adresse paire juste en dessous, et tout le flux glisse d'un octet.

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.

Deux barres de 711 Ko. Avant : programme 340 Ko, module d'accueil 38, intro 107, écran d'attente 7, écran titre 82, niveau 1 66, et 69 Ko libres où le niveau 2, 85 Ko, ne rentre pas. Après : écran titre 9 Ko, niveau 1 16, niveau 2 19, et 173 Ko libres
La première disquette, comptée en blocs de 1 Ko. Le programme, son module d'accueil et l'intro n'ont pas encore bougé.

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.