Reverse Engineering Fantastic Dizzy

Fantastic Dizzy est un jeu de plateforme puzzle créé en 1991 par Codemasters. Elle fait partie de la série Dizzy . Malgré le fait que la série Dizzy soit toujours populaire et qu'elle crée des jeux amateurs ( Dizzy Age ), il semble que personne n'ait été impliqué dans le développement inverse des jeux originaux.


J'ai écrit quelques outils simples pour extraire, visualiser et empaqueter les ressources du jeu original. Outils publiés sur GitHub .

Déballage EXE

Le fichier binaire PCDIZZY.EXE est conditionné au format Microsoft EXEPack . Bien qu'il existe de nombreux outils Linux capables de décompresser de tels exécutables, aucun ne semble prendre en charge la version utilisée pour Fantastic Dizzy. Par conséquent, pour décompresser le fichier exécutable, j'ai utilisé la version DOS d' UNP . Après avoir déballé le fichier exécutable, il pourrait être téléchargé sur l'IDA. De manière pratique, la version décompressée du fichier binaire fonctionnait toujours bien, elle pouvait donc être déboguée à l'aide du débogueur DOSBox.

Fichiers de données

Il y a deux fichiers de données dans le jeu: DIZZY.NDX et DIZZY.RES. Les extensions, ainsi que la taille des fichiers, nous donnent un indice sur ce qu'elles peuvent contenir. Le fichier NDX est d'environ 8 Ko et le fichier RES d'environ 800 Ko. Puisque le jeu est écrit en C, nous pouvons rechercher des appels fopen dans l'IDA pour voir où les fichiers de données s'ouvrent. Dans les jeux DOS écrits en assembleur, vous devez pour cela rechercher les instructions en 21h (pour ouvrir le fichier ah = 3d). Le binaire Dizzy contient une fonction wrapper autour de fopen qui vous permet de spécifier le nom principal et l'extension de fichier. Cela nous amène au bloc de code suivant:


Il charge les fichiers DIZZY.RES et DIZZY.NDX et enregistre également les pointeurs de fichier dans des variables globales. Lors de l'ingénierie inverse des binaires DOS, un problème gênant se pose: les registres qu'ils contiennent sont de 16 bits, mais les pointeurs dans certains cas peuvent être de 32 bits. Ici, les pointeurs FILE * ont une taille de 32 bits et sont renvoyés de do_open_file à ax: dx. Notez que les chaînes sont également des pointeurs 32 bits et dizzy_basename est passé à la fonction appelante sur la pile (et cette auto-analyse IDA confuse - elle était considérée comme un argument de mode pour fopen).

En recherchant les occurrences de g_dizzy_res / ndx dans les xréfs, vous pouvez trouver où les fichiers sont lus. À ce stade, le débogueur DOSBox est utile car il existe une forte probabilité de nombreuses opérations de lecture de fichiers aléatoires, et l'utilisation d'un IDA pour déterminer les décalages de lecture serait un processus assez monotone. De bons conseils sur la construction et l'utilisation du débogueur DOSBox peuvent être trouvés ici .

Lorsque vous utilisez l'IDA et le débogueur DOSBox ensemble, il devient évident que le fichier NDX est utilisé comme index pour le fichier RES. Chaque entrée du fichier NDX prend 16 octets; il stocke l'identifiant du fragment, sa taille et son décalage dans le fichier RES. En regardant comment les données RES sont lues, vous pouvez voir que l'octet d'indicateur est d'abord vérifié dans le fichier NDX. Si le bit 0x80 n'est pas défini, les données sont lues directement à partir du fichier RES, sinon un chemin de code plus complexe est exécuté. L'indicateur est défini pour la plupart des fragments, donc avec un haut degré de probabilité, nous pouvons supposer qu'il dénote une sorte de compression utilisée pour ces fragments.

La compression

Le chemin de compression commence par lire dans la base du fragment RES deux mots de 32 bits indiquant les tailles initiale et finale, puis la fonction de décompression est appelée. En 1991, l'encodage de longueur simple (RLE) et la compression de dictionnaire étaient populaires, comme divers algorithmes Liv-Zempel. Le début du cycle de déballage ressemble à ceci:


Les jetons de décompression sont obtenus à l'aide de la fonction get_next_token, qui lit la partie suivante des données source dans ax: dx avec un décalage de cl. Le registre cl est utilisé comme position du décalage binaire, revenant à zéro après avoir atteint huit. Au début du cycle, le jeton est lu et le bit inférieur est vérifié. Si l'indicateur est défini, le code est simple:


Il enregistre simplement l'octet en cours, reçoit le jeton suivant et continue de fonctionner. Si l'indicateur est effacé, un chemin de code plus long est sélectionné, qui se termine par l'instruction rep movsb. Cela indique qu'une sorte de dictionnaire est utilisé en compression.

L'algorithme de compression est intéressant pour plusieurs raisons. Premièrement, il utilise un codage à longueur de bit variable. La valeur absolue est codée sous la forme d'un indicateur et d'une valeur de données de 8 bits. Curieusement, le train de bits est codé comme un petit endian. Cela complique un peu l'analyse de la décompression en observant le fichier RES dans un éditeur hexadécimal. Par exemple, si les trois premiers octets d'un fragment sont codés en valeurs absolues, les données sont organisées comme suit:

 : AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD  1: 6543210F 7  2: 543210F 76  3: 43210F 765 

De plus, le décompresseur peut sauter l'octet lors de la lecture, si le compteur cl revient à zéro lors de la réception du jeton suivant. Je ne sais pas s'il s'agit d'optimisation, ou d'un bug, ou d'un hack créé par le développeur du jeu pour résoudre le problème avec mes outils.

Si l'indicateur est effacé, le décompresseur effectue une copie à partir de la partie initiale des données décompressées. Dans ce cas, les bits suivants codent la longueur et le décalage à partir desquels copier. Le décalage est codé en 10 ou 13 bits, et l'option souhaitée indique le drapeau. Cela semble être un choix très étrange, car cela complique un peu le code et, au mieux, enregistre seulement 2 bits.

Encoder la longueur de la série semble un peu étrange. Le décompresseur lit les bits jusqu'à ce qu'il atteigne le bit zéro. Ensuite, le nombre de bits utilisés pour coder la longueur est de deux plus le nombre de bits non nuls. Par exemple, lors du codage d'une longueur de 58 (0x3a), le flux binaire ressemble à ceci:

 11110 111010 

Le codage nécessite 11 bits. Les petites longueurs sont mieux codées car la longueur minimale des bits est 2. La copie de longueurs jusqu'à 3 ne nécessite que 3 bits pour coder, jusqu'à 7 nécessite 5 bits, etc. Je ne sais pas avec certitude si ce type de codage est une technique courante.

Le débogueur DOSBox est également très utile pour reconstruire l'algorithme de décompression. Si vous ne savez pas à quoi devraient ressembler les données décompressées, il est difficile de comprendre si le décompresseur fonctionne correctement. À l'aide du débogueur, vous pouvez parcourir l'intégralité de l'algorithme de décompression et enregistrer un vidage de la mémoire non compressée pour comparaison.

Une autre fonctionnalité utile est l'indicateur dans le fichier NDX, indiquant que la ressource est compressée. Étant donné que le jeu original prend en charge les ressources non compressées, nous pouvons reconditionner le fichier RES sans avoir besoin d'un algorithme de compression. La modification et le reconditionnement de fragments avec le lancement ultérieur du jeu est un bon moyen de tester nos hypothèses sur les formats de données.

Niveaux

Fantastic Dizzy est un jeu avec un monde ouvert. Les niveaux sont des zones avec défilement vertical ou horizontal. Le joueur se déplace entre les niveaux, atteignant la fin du niveau ou entrant et sortant des bâtiments. Bien que les références aux fragments dans le fichier RES soient faites via des identifiants (ID) 16 bits, le fichier binaire du jeu contient en fait une table de noms de niveaux correspondants avec des identifiants de fragments. Chaque niveau se compose de plusieurs fragments: un titre, une ou plusieurs couches, un jeu de tuiles et une palette. Il y a peu de redondance ici, car certains niveaux utilisent la même palette et le même jeu de tuiles, mais ne réutilisent pas les mêmes fragments, de sorte que le fichier RES contient de nombreuses ressources en double.

Les couches codent les tuiles pour un niveau. Pour différentes parties du monde ou pour les calques d'arrière-plan, vous pouvez utiliser des calques supplémentaires. Par exemple, au niveau de tree1.stg, il existe huit couches pour différentes parties de la cime des arbres et une couche d'arrière-plan commune. Cependant, les niveaux sous-marins sont divisés en sea1.stg et sea2.stg, chacun ayant une couche de premier plan et une couche d'arrière-plan.

Les couches d'arrière-plan sont des arrière-plans à largeur fixe sans défilement, par exemple, une forêt dans une partie d'un jeu avec des cimes d'arbre. Les tuiles de premier plan et d'arrière-plan, situées devant et derrière le personnage, sont encodées dans le même calque que les tuiles sur lesquelles vous pouvez marcher. Par exemple, la capture d'écran montre le niveau depuis le sommet des arbres depuis le début du jeu:


Niveau de la cime des arbres

Il s'agit de la septième couche de tree1.stg:


Arbre de niveau septième couche1.stg

Il est à noter que le joueur peut passer devant la cabane, mais derrière deux arbres. Toutes les informations sur les tuiles sont contenues dans un tableau de cartes de tuiles situé dans une couche. Les tuiles dans les fragments de la couche sont codées sur deux octets, et les 9 bits inférieurs sont utilisés pour l'index des tuiles. Je n'ai pas bien compris les bits supérieurs, mais au moins ils contiennent des informations sur le décalage de la palette pour la tuile et, probablement, des informations sur les collisions.

En tant que niveaux dans le jeu, des cinématiques, des portraits de personnages et un écran de contrôle d'inventaire sont également stockés. Il semble que cette technique soit standard pour les jeux DOS, probablement parce qu'elle minimise la quantité de code nécessaire.


"Niveau" de gestion des stocks

Sprites

Le format sprite n'est pas particulièrement intéressant. Chaque image-objet est une image bitmap avec un octet par pixel, mais avec seulement 16 couleurs par image-objet. L'utilisation d'un nombre limité de couleurs était une technique courante à l'ère du VGA 256 couleurs, car pour les sprites, il était facile d'effectuer un changement de palette ou de les utiliser à des niveaux avec d'autres palettes; en outre, il a économisé l'espace alloué aux sprites.

Les sprites ont des tailles différentes, donc un fragment séparé contient des informations sur la taille du sprite et leurs déplacements en x et y. Les sprites sont regroupés en ensembles, mais le regroupement semble assez arbitraire. Par exemple, un ensemble de sprites contient des graphiques d'économiseur d'écran, des objets d'inventaire, ainsi que certains personnages non joueurs. Cela rend la visualisation des ensembles de sprites un peu délicate car la palette n'est pas la même pour tous les sprites.


Sprites de personnage de joueur

Que reste-t-il?

Il reste à inverser l'ingénierie de quelques autres choses. La plupart du temps, je m'intéresse aux formats de fichiers de données, mais il y a certains aspects que je ne comprends pas:

• Où sont les emplacements des objets (clés, fruits, etc.). Il semble qu'ils ne soient pas écrits en fragments de niveau. Peut-être qu'ils sont stockés dans le fichier binaire du jeu, car le joueur peut ramasser un objet sur un niveau et le lancer sur un autre.
• Fonctionnement des collisions de niveau. Un joueur peut marcher devant ou derrière certaines tuiles, et les sols peuvent être plats ou en pente.
• Comment les niveaux sont connectés. Ces informations peuvent être stockées dans le binaire du jeu.
• Le décalage de la palette des tuiles aux niveaux n'est pas entièrement correct. Certaines tuiles affichent des couleurs incorrectes.
• Chaque ensemble de sprites a trois fragments: en-tête, table et données. Les fragments avec une table et des données sont clairs pour moi, mais certaines informations sur les sprites sont incluses dans l'en-tête, par exemple, le décalage par x et y. Je n'ai pas complètement compris son format.