👨🏼‍🎓 🧛🏾 🧑🏾‍🤝‍🧑🏽 Introduction à la rétro-ingénierie: piratage du format de données de jeu 🛌🏾 🚴 🍐

Présentation

L'ingénierie inverse d'un fichier de données inconnu peut être décrite comme un processus de compréhension progressive. À bien des égards, elle ressemble à une méthode scientifique, appliquée uniquement aux objets abstraits créés par l'homme, et non au monde naturel. Nous commençons par collecter des données, puis utilisons ces informations pour avancer une ou plusieurs hypothèses. Nous testons les hypothèses et appliquons les résultats de ces tests pour les clarifier. Si nécessaire, répétez le processus.

Le développement de compétences en ingénierie inverse est essentiellement une question de pratique. En acquérant de l'expérience, vous acquérez une compréhension intuitive de ce que vous devez d'abord explorer, des modèles que vous devez rechercher et des outils les plus pratiques à utiliser.

Dans cet article, je parlerai en détail du processus de rétro-ingénierie des fichiers de données d'un ancien jeu informatique pour montrer comment cela se fait.

Un peu de fond

Tout a commencé lorsque j'ai essayé de recréer le Chip's Challenge sur Linux.

Le Chip's Challenge a été initialement publié en 1989 pour la console portable Atari Lynx, aujourd'hui oubliée. À cette époque, Atari Lynx était une voiture impressionnante, mais elle est sortie en même temps que la Nintendo Game Boy, qui a finalement conquis le marché.

Chip's Challenge est un jeu de puzzle avec une vue de dessus et une carte de tuiles. Comme pour la plupart de ces jeux, l'objectif de chaque niveau est d'arriver à la sortie. Dans la plupart des niveaux, la sortie est protégée par un connecteur pour la puce, qui ne peut être contourné qu'en collectant un certain nombre de puces informatiques.

Vidéo: Atari Lynx en action , procédure pas à pas de niveau un .

Un nouveau jeu démarre à partir du premier niveau sous le nom de "LEÇON 1". En plus des puces et d'un emplacement pour une puce, des clés et des portes y apparaissent. À d'autres niveaux, des obstacles tels que des pièges, des bombes, de l'eau et des créatures se posent qui se déplacent (le plus souvent) le long d'itinéraires prévisibles. Une large gamme d'objets et d'appareils vous permet de créer de nombreux puzzles et limites de temps. Pour terminer le jeu, vous devez passer par plus de 140 niveaux.

Bien que Lynx ait finalement échoué, le Chip's Challenge s'est révélé très populaire et a été porté sur de nombreuses autres plates-formes, apparaissant finalement sur Microsoft Windows, où il s'est généralisé. Autour du jeu, une petite mais dédiée de fans s'est formée et, au fil du temps, un éditeur de niveau a été écrit qui a permis aux joueurs de créer d'innombrables niveaux.

Et c'est là que commence mon histoire. J'ai décidé que je voulais créer une version du moteur de jeu open source de base afin de pouvoir jouer au Chip's Challenge sur Linux et Windows, et faciliter l'exécution de tous les niveaux créés par les fans.

L'existence de l'éditeur de niveau s'est avérée être un miracle pour moi, car j'ai pu explorer les fonctionnalités cachées de la logique du jeu, créer mes propres niveaux et effectuer des tests. Malheureusement, il n'y avait pas d'éditeur de niveau pour le jeu Lynx original; il n'apparaissait que dans le port le plus connu sous Windows.

Le port Windows n'a pas été créé par les développeurs d'origine, donc de nombreux changements dans la logique du jeu y sont apparus (et tous n'étaient pas intentionnels). Quand j'ai commencé à écrire mon moteur, je voulais recréer la logique du jeu original sur Lynx et la version la plus connue pour Windows. Mais l'absence d'un éditeur de niveau sur Lynx a sérieusement limité ma capacité à étudier le jeu original en détail. Le port Windows avait un avantage: les niveaux étaient stockés dans un fichier de données séparé, ce qui simplifiait sa détection et son reverse engineering. Le jeu pour Lynx a été distribué sur des cartouches ROM contenant des images de sprite, des effets sonores et du code machine, ainsi que des données de niveau qui ont été exécutées ensemble. Il n'y a aucune indication sur l'emplacement des données dans ce vidage de 128 kilo-octets de la ROM, ni à quoi elles ressemblent, et sans cette connaissance, je ne pourrais pas créer un éditeur de niveau pour la version Lynx.

Une fois, dans un processus de recherche tranquille, je suis tombé sur une copie du port Chip's Challenge sous MS-DOS. Comme pour la plupart des premiers ports du jeu, sa logique était plus proche de l'original que dans la version Windows. Quand j'ai regardé les données du programme pour savoir comment elles sont stockées, j'ai été surpris de constater que les données de niveau étaient allouées dans un répertoire séparé, et chaque niveau était stocké dans son propre fichier. Ayant des données de niveau si commodément séparées, j'ai suggéré qu'il ne serait pas trop difficile de procéder à une rétro-ingénierie des fichiers de données de niveau. Et cela vous permettra d'écrire un éditeur de niveau pour la version du jeu sous MS-DOS. J'ai décidé que c'était une opportunité intéressante.

Mais un autre membre de la communauté Chip's Challenge m'a averti d'un fait intéressant. Le contenu des fichiers de niveau pour MS-DOS s'est avéré être un vidage d'octets de ROM Lynx. Cela signifiait que si je pouvais décoder les fichiers MS-DOS, je pourrais alors utiliser ces connaissances pour lire et modifier les niveaux à l'intérieur du vidage de la mémoire ROM Lynx. Ensuite, vous pouvez créer un éditeur de niveau directement pour le jeu original sur Lynx.

Du coup, ma priorité absolue était les fichiers de niveau de rétro-ingénierie pour MS-DOS.

Fichiers de données

Voici un lien vers le répertoire tarball contenant tous les fichiers de données. Je le donne au cas où vous voudriez répéter après moi toutes les étapes décrites dans cet article, ou essayer de décoder vous-même les fichiers de données.

Est-ce légal? Bonne question. Étant donné que ces fichiers ne sont qu'une petite partie du programme pour MS-DOS, et en eux-mêmes, ils sont inutiles, et puisque je les publie uniquement à des fins éducatives, je pense que cela relève des exigences d'utilisation équitable. J'espère que toutes les parties intéressées seront d'accord avec moi. (Si je reçois néanmoins une lettre de menaces de la part d'avocats, je peux modifier l'article de manière à présenter les fichiers de données de manière amusante, puis déclarer qu'il s'agit d'une parodie.)

Prérequis

Je suppose que vous connaissez le calcul hexadécimal, même si vous ne connaissez pas le décodage des valeurs hexadécimales, et aussi que vous connaissez un peu le shell Unix. La session shell présentée dans cet article s'exécute sur un système Linux standard, mais les commandes presque utilisées sont des utilitaires Unix courants et sont largement distribuées sur d'autres systèmes de type Unix.

Premier coup d'oeil

Voici une liste du répertoire contenant les fichiers de données du port sous MS-DOS:

  Niveaux $ ls
 all_full.pak cake_wal.pak eeny_min.pak iceberg.pak lesson_5.pak mulligan.pak playtime.pak southpol.pak totally_.pak
 alphabet.pak castle_m.pak elementa.pak ice_cube.pak lesson_6.pak nice_day.pak potpourr.pak special.pak traffic_.pak
 amsterda.pak catacomb.pak fireflie.pak icedeath.pak lesson_7.pak nightmar.pak problems.pak spirals.pak trinity.pak
 apartmen.pak cellbloc.pak firetrap.pak icehouse.pak lesson_8.pak now_you_.pak refracti.pak spooks.pak trust_me.pak
 arcticfl.pak chchchip.pak floorgas.pak invincib.pak lobster_.pak nuts_and.pak reverse_.pak steam.pak undergro.pak
 balls_o_.pak chiller.pak forcé_e.pak i.pak lock_blo.pak on_the_r.pak rink.pak stripes.pak up_the_b.pak
 beware_o.pak chipmine.pak force_fi.pak i_slide.pak loop_aro.pak oorto_ge.pak roadsign.pak suicide.pak vanishin.pak
 blink.pak citybloc.pak force_sq.pak jailer.pak memory.pak open_que.pak sampler.pak telebloc.pak victim.pak
 blobdanc.pak colony.pak fortune_.pak jumping_.pak metastab.pak oversea_.pak scavenge.pak telenet.pak vortex.pak
 blobnet.pak corridor.pak four_ple.pak kablam.pak mind_blo.pak pain.pak scoundre.pak t_fair.pak wars.pak
 block_fa.pak cypher.pak four_squ.pak knot.pak mishmesh.pak paranoia.pak voyant_s.pak the_last.pak écrivains_.pak
 block_ii.pak deceptio.pak glut.pak ladder.pak miss_dir.pak partial_.pak short_ci.pak the_mars.pak yorkhous.pak
 block_n_.pak deepfree.pak goldkey.pak lemmings.pak mixed_nu.pak pentagra.pak shrinkin.pak the_pris.pak
 block_ou.pak digdirt.pak go_with_.pak lesson_1.pak mix_up.pak perfect_.pak skelzie.pak three_do.pak
 block.pak digger.pak grail.pak lesson_2.pak monster_.pak pier_sev.pak slide_st.pak time_lap.pak
 bounce_c.pak doublema.pak hidden_d.pak lesson_3.pak morton.pak ping_pon.pak slo_mo.pak torturec.pak
 brushfir.pak drawn_an.pak hunt.pak lesson_4.pak mugger_s.pak playhous.pak socialis.pak tossed_s.pak

Comme vous pouvez le voir, tous les fichiers se terminent par .pak . .pak est l'autorisation standard pour le fichier de données d'application, et cela, malheureusement, ne nous donne aucune information sur sa structure interne. Les noms de fichiers sont les huit premiers caractères du nom de niveau, à quelques exceptions près. (Par exemple, dans les noms des fichiers de niveau «BLOCK BUSTER» et «BLOCK BUSTER II», le mot «buster» est omis afin qu'ils ne correspondent pas.)

  Niveaux $ ls |  wc
      17 148 1974

Il y a 148 fichiers de données dans le répertoire, et le jeu a en fait exactement 148 niveaux, donc tout est pareil ici.

Examinons maintenant ce que sont ces fichiers. xxd est un utilitaire standard pour vider des données hexadécimales (hexdump). Voyons à quoi cela ressemble à l'intérieur de la LEÇON 1.

  $ xxd niveaux / leçon_1.pak
 00000000: 1100 cb00 0200 0004 0202 0504 0407 0505 ................
 00000010: 0807 0709 0001 0a01 010b 0808 0d0a 0a11 ................
 00000020: 0023 1509 0718 0200 2209 0d26 0911 270b. # ...... ".. & ..".
 00000030: 0b28 0705 291e 0127 2705 020d 0122 0704. (..) ..''.... "..
 00000040: 0902 090a 0215 0426 0925 0111 1502 221d ....... &.% .... ".
 00000050: 0124 011d 0d01 0709 0020 001b 0400 1a00. $ ....... ......
 00000060: 2015 2609 1f00 3300 2911 1522 2302 110d. & ... 3.) .. "# ...
 00000070: 0107 2609 1f18 2911 1509 181a 0223 021b .. & ...) ...... # ..
 00000080: 0215 2201 1c01 1c0d 0a07 0409 0201 0201 .. ".............
 00000090: 2826 0123 1505 0902 0121 1505 220a 2727 (&. # .....! .. ". ''
 000000a0: 0b05 0400 060b 0828 0418 780b 0828 0418 ....... (.. x .. (..
 000000b0: 700b 0828 0418 6400 1710 1e1e 1a19 0103 p .. (.. d .........
 000000c0: 000e 1a17 1710 0e1f 010e 1314 1b29 1f1a .............) ..
 000000d0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................
 000000e0: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-.  ....
 000000f0: 1024 291f 1a01 1a1b 1019 000f 1a1a 1d1e. $) .............
 00000100: 2d02

Qu'est-ce qu'un utilitaire hexdump? Un vidage hexadécimal est un moyen standard d'afficher les octets exacts d'un fichier binaire. La plupart des valeurs d'octets ne peuvent pas être associées à des caractères ASCII imprimables, ou elles ont une apparence incompréhensible (comme un caractère de tabulation). Dans un vidage hexadécimal, les octets individuels sont sortis sous forme de valeurs numériques. Les valeurs sont affichées en hexadécimal, d'où le nom. Dans l'exemple ci-dessus, 16 octets sont affichés sur une ligne de sortie. La colonne la plus à gauche indique la position de la ligne dans le fichier, également en hexadécimal, de sorte que le nombre dans chaque ligne est augmenté de 16. Les octets sont affichés sur huit colonnes et deux octets sont affichés dans chaque colonne. Le vidage hexadécimal à droite montre à quoi ressembleraient les octets lorsqu'ils sont affichés par des caractères, seules toutes les valeurs ASCII non imprimables sont remplacées par des points. Cela facilite la recherche de chaînes pouvant être incorporées dans un fichier binaire.

Évidemment, la rétro-ingénierie de ces fichiers ne se résumera pas à parcourir simplement le contenu et à explorer ce qui y est visible. Jusqu'à présent, rien ne nous dit quelles fonctions remplissent les données.

Qu'attendons-nous de voir?

Prenons un peu de recul et clarifions la situation: quelles données spécifiques attendons-nous à trouver dans ces fichiers de données?

Le plus évident est une certaine «carte» du niveau: des données indiquant la position des murs et des portes, ainsi que tout le reste, ce qui rend le niveau unique.

(Heureusement pour nous, les fans du jeu ont fait un travail minutieux et ont collecté des cartes complètes pour les 148 niveaux, afin que nous puissions les utiliser pour savoir ce qui devrait être sur chaque carte.)

En plus de la carte, chaque niveau doit avoir plusieurs autres attributs. Par exemple, vous remarquerez peut-être que chaque niveau a un nom, par exemple, «LEÇON 1», «PARFAIT MATCH», «DESSINÉ ET QUARTIER», etc. Différents niveaux ont également des délais différents, nous pouvons donc supposer que ces informations sont également contenues dans les données. De plus, chaque niveau a son propre nombre de puces assemblées. (Nous pourrions supposer que ce nombre correspond simplement au nombre de puces au niveau, mais il s'avère qu'à certains niveaux, il y a plus de puces que nécessaire pour ouvrir le slot de puce. Au moins pour ces niveaux, le nombre minimum doit être indiqué de manière explicite.)

Un autre élément de données que nous nous attendons à trouver dans les données de niveau est le texte de conseil. À certains niveaux, il y a un «bouton d'indication» - un grand point d'interrogation gisant sur le sol. Lorsque la puce se lève dessus, un texte d'info-bulle s'affiche. Le bouton d'indication est à environ 20 niveaux.

Enfin, chaque niveau a un mot de passe - une séquence de quatre lettres qui permet au joueur de continuer le jeu à partir de ce niveau. (Ce mot de passe est requis car Lynx n'a pas de magasin de données. Il était impossible d'enregistrer des jeux sur la console, vous pouvez donc continuer à jouer après avoir allumé la console à l'aide de mots de passe.)

Voici donc notre liste de données pertinentes:

Carte des niveaux
Nom du niveau
Niveau de mot de passe
Limite de temps
Nombre de jetons
Texte de l'info-bulle

Estimons approximativement la taille totale des données. Le moyen le plus simple de déterminer la limite de temps et le nombre de jetons. Ces deux paramètres peuvent avoir des valeurs comprises entre 0 et 999, ils sont donc très probablement stockés sous forme de valeurs entières avec une taille totale de 4 octets. Le mot de passe se compose toujours de quatre lettres, il est donc très probablement stocké sur quatre octets supplémentaires, c'est-à-dire seulement 8 octets. La longueur des noms des niveaux varie de quatre à dix-neuf caractères. Si nous supposons que nous avons besoin d'un autre octet pour terminer la ligne, alors cela fait vingt octets, c'est-à-dire que le sous-total est de 28 octets. Le texte de l'infobulle le plus long fait plus de 80 octets; si nous arrondissons cette valeur à 90, nous obtiendrons 118 octets au total.

Qu'en est-il du schéma de niveaux? La plupart des niveaux ont une taille de 32 × 32 tuiles. Des niveaux plus importants n'existent pas. Certains niveaux sont inférieurs, mais il serait logique de supposer qu'ils sont simplement intégrés dans une carte 32 × 32. Si nous supposons qu'un octet est requis pour une tuile, alors 1024 octets sont nécessaires pour le circuit complet. Autrement dit, nous obtenons une estimation approximative de 1142 octets par niveau. Bien sûr, ce n'est qu'une estimation initiale approximative. Il est possible que certains de ces éléments soient stockés différemment, ou pas du tout stockés dans des fichiers de niveau. Ou ils peuvent contenir d'autres données que nous n'avons pas remarquées ou que nous ne connaissons pas à leur sujet. Mais jusqu'à présent, nous avons jeté de bonnes bases.

Après avoir décidé de ce que nous nous attendons à voir dans les fichiers de données, revenons à l'étude de ce qu'ils contiennent réellement.

Qu'est-ce qui est là et ce qui ne l'est pas

Bien qu'à première vue, le fichier de données semble complètement incompréhensible, vous pouvez toujours y remarquer quelques points. D'abord, c'est ce que nous ne voyons pas . Par exemple, nous ne voyons ni le nom du niveau ni le texte des conseils. Vous pouvez comprendre que ce n'est pas un hasard, après avoir étudié d'autres fichiers:

  $ strings niveaux / * |  moins
 : !!; #
 &> '' :: 4 #
 . ,,!
 -54 ";
 / & 67
 !) 60
 <171
 * (0 *
 82> '= /
 8> <171 &&
 9> # 2 ') (
 ,) 9
  0hX
 `@PX
 ) "" *
 24 ** 5
 ;)) <
 B777: .. 22C1
 E ,, F
 -GDED
 EGFF16G ;; H <
 IECJ
 9K444
 = MBBB >> N9 "O" 9P3? Q
 lignes 1-24 / 1544 (plus)

Rien n'est visible ici, sauf des fragments arbitraires de déchets ASCII.

Vraisemblablement, quelque part dans ces fichiers, il y a des noms et des indices de niveau, mais ils ne sont pas stockés en ASCII ou ont subi une transformation (par exemple, en raison de la compression).

Il convient également de noter ce qui suit: le fichier atteint à peine 256 octets. C'est assez petit, étant donné qu'au départ, nous estimions sa taille à plus de 1140 octets.

L'option -S trie les fichiers par ordre décroissant de taille.

  Niveaux $ ls -lS |  tête
 592 au total
 -rw-r - r-- 1 boîte à pain boîte à pain 680 23 juin 2015 mulligan.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 675 23 juin 2015 shrinkin.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 671 23 juin 2015 balls_o_.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 648 23 juin 2015 cake_wal.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 647 23 juin 2015 citybloc.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 639 23 juin 2015 four_ple.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 636 23 juin 2015 trust_me.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 625 23 juin 2015 block_n_.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 622 23 juin 2015 mix_up.pak

Le plus gros fichier ne prend que 680 octets, et ce n'est pas beaucoup. Et quelle sera la plus petite?

L'option -r indique à ls d'inverser l'ordre.

  Niveaux $ ls -lSr |  tête
 592 au total
 -rw-r - r-- 1 boîte à pain boîte à pain 206 23 juin 2015 kablam.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 214 23 juin 2015 fortune_.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 219 23 juin 2015 digdirt.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 226 23 juin 2015 leçon_2.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 229 23 juin 2015 leçon_8.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 237 23 juin 2015 partial_.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 239 23 juin 2015 knot.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 247 23 juin 2015 cellbloc.pak
 -rw-r - r-- 1 boîte à pain boîte à pain 248 23 juin 2015 torturec.pak

Le plus petit fichier ne prend que 206 octets, ce qui est plus de trois fois plus petit que le plus grand. Il s'agit d'une gamme assez large, compte tenu du fait que nous nous attendions à peu près aux mêmes tailles de niveau.

Dans notre évaluation initiale, nous avons supposé que la carte aurait besoin d'un octet par tuile, et seulement 1024 octets. Si nous réduisons cette estimation de moitié, c'est-à-dire que chaque tuile ne nécessitera que 4 bits (ou deux tuiles par octet), alors la carte occupera toujours 512 octets. 512 est plus petit que 680, mais toujours plus grand que la plupart des niveaux. Et en tout cas - 4 bits ne fourniront que 16 valeurs différentes, et dans le jeu il y a beaucoup plus d'objets différents.

Autrement dit, il est évident que les cartes ne sont pas stockées dans ces fichiers sous forme ouverte. Ils utilisent soit un codage plus complexe, fournissant une description plus efficace, et / ou ils sont en quelque sorte compressés. Par exemple, au niveau «LEÇON 1», nous pouvons voir comment les entrées manquantes pour les tuiles «vides» réduiront considérablement la taille globale des données cartographiques.

Nous pouvons regarder les cartes des plus gros fichiers:

Carte du niveau 57: STRANGE MAZE

Carte Niveau 98: RÉTRACTATION

puis comparez-les avec les cartes des plus petits fichiers:

Carte Niveau 106: KABLAM

Carte Niveau 112: FORTUNE FAVORISE LE

Cette comparaison soutient notre idée que les petits fichiers de données correspondent à des niveaux plus simples ou contiennent plus de redondance. Par exemple, si les données sont compressées par une sorte de codage de longueur d'exécution, cela peut facilement expliquer les intervalles de taille des différents fichiers.

Si les fichiers sont réellement cryptés, nous devrons très probablement décrypter la compression avant de décrypter les données de la carte.

Nous étudions plusieurs fichiers en même temps

Notre brève étude du premier fichier de données nous a permis de faire quelques hypothèses, mais n'a rien trouvé de concret. Dans une prochaine étape, nous commencerons à explorer les modèles de plusieurs fichiers de données. Pour l'instant, nous supposons que tous les 148 fichiers utilisent le même schéma de classement pour coder les données, donc la recherche de modèles en double dans ces fichiers nous aidera à démarrer.

Commençons par le tout début des tuiles. Le haut du fichier est probablement utilisé pour stocker des «métadonnées» qui nous renseignent sur le contenu du fichier. En ne regardant que la première ligne du vidage hexadécimal, nous pouvons effectuer une comparaison simple et rapide des 16 premiers octets et y rechercher des modèles importants:

  $ pour f dans les niveaux / *;  faire xxd $ f |  sed -n 1p;  fait |  moins
 00000000: 2300 dc01 0300 0004 0101 0a03 030b 2323 # ............. ##
 00000000: 2d00 bf01 0300 0015 0101 2203 0329 2222 -... "..)"
 00000000: 2b00 a101 0301 0105 0000 0601 0207 0505 + ...............
 00000000: 1d00 d300 0200 0003 0101 0402 0205 0102 ................
 00000000: 2d00 7a01 0300 0006 1414 0701 0109 0303 -.z .............
 00000000: 3100 0802 0200 0003 0101 0502 0206 1313 1 ...............
 00000000: 1a00 b700 0200 0003 0100 0502 0206 0101 ................
 00000000: 1a00 0601 0300 0005 0001 0601 0107 0303 ................
 00000000: 2000 7a01 0200 0003 0202 0401 0105 0028 .z ............ (
 00000000: 3a00 a400 0200 0003 2828 0428 0205 0303: ....... ((. (....
 00000000: 2600 da00 0300 0004 0507 0901 010a 0303 & ...............
 00000000: 2400 f000 0300 0004 0303 0504 0407 0101 $ ...............
 00000000: 2a00 ef01 0300 0005 0101 0614 0007 0303 * ...............
 00000000: 2c00 8c01 0300 0004 0303 0500 0107 0101, ...............
 00000000: 2a00 0001 0300 0004 0303 0501 0107 0404 * ...............
 00000000: 1b00 6d01 0200 0003 0101 0502 0206 0003 ..m .............
 00000000: 1e00 1701 0200 0003 0202 0401 0105 0013 ................
 00000000: 3200 ee01 0f00 0015 0101 270f 0f29 1414 2 ......... '..) ..
 00000000: 2a00 5b01 0300 0005 0303 0601 0107 1414 *. [.............
 00000000: 2c00 8a01 0200 0003 0202 0401 0105 0303, ...............
 00000000: 1d00 9c00 0216 1604 0000 0516 0107 0205 ................
 00000000: 2000 e100 0200 0003 0101 0402 0205 0303 ...............
 00000000: 2000 2601 0300 0004 0303 0502 0207 0101. & .............
 00000000: 1f00 f600 0132 0403 0000 0532 3206 0404 ..... 2 ..... 22 ...
 lignes 1-24 / 148 (plus)

En regardant ce vidage, vous pouvez voir que dans chaque colonne il y a des valeurs similaires.

En commençant par le premier octet, nous nous rendons vite compte que sa valeur est dans une plage de valeurs très limitée, dans la plage hexadécimale de 40 (ou environ 20–60 à 20–60 en décimal). Il s'agit d'une fonctionnalité assez spécifique.

Encore plus intéressant, le deuxième octet de chaque fichier est toujours nul, sans exception. Le deuxième octet n'est probablement pas utilisé ou est un espace réservé. Cependant, il existe une autre possibilité - ces deux premiers octets représentent ensemble une valeur de 16 bits stockée dans un ordre petit-boutien.

Qu'est-ce que le petit-endian? Lors du stockage d'une valeur numérique supérieure à un octet, vous devez d'abord sélectionner l'ordre dans lequel les octets seront stockés. Si vous stockez d'abord un octet représentant la plus petite partie du nombre, cela s'appelle ordre direct ( little-endian ); si vous stockez d'abord des octets indiquant la majeure partie du nombre, alors c'est l'ordre inverse ( big-endian ). Par exemple, nous écrivons les valeurs décimales dans l'ordre inverse (big-endian): la ligne «42» signifie «quarante-deux», pas «quatre et vingt». Le petit-endian est un ordre naturel pour de nombreuses familles de microprocesseurs, il est donc généralement plus populaire, à l'exception des protocoles réseau, qui nécessitent généralement le big-endian.

Si nous continuons l'analyse, nous verrons bientôt que le troisième octet du fichier n'est pas similaire aux deux précédents: sa valeur varie sur une large plage. Cependant, le quatrième octet est toujours 00 , 01 ou 02 , et 01 est le plus courant. Cela nous indique également que ces deux octets constituent une autre valeur de 16 bits, qui se situe approximativement dans la plage de valeurs décimales 0-700. Cette hypothèse peut également être confirmée par le fait que la valeur du troisième octet est généralement faible si la valeur du quatrième octet est 02 , et généralement grande si le quatrième octet est 00 .

Soit dit en passant, il convient de noter que c'est en partie la raison pour laquelle le format de vidage hexadécimal affiche les octets par paires par défaut - cela facilite la lecture d'une séquence de nombres entiers de 16 bits. Le format de vidage hexadécimal a été normalisé lorsque des ordinateurs 16 bits étaient utilisés. Essayez de remplacer xxd par xxd -g1 pour désactiver complètement le regroupement, et vous remarquerez que la reconnaissance des paires d'octets au milieu d'une ligne représente beaucoup de travail. Ceci est un exemple simple de la façon dont les outils utilisés pour étudier les données inconnues ont tendance à nous faire remarquer certains types de modèles. Il est bon que xxd souligne ce modèle par défaut car il est très courant (même aujourd'hui, lorsque des ordinateurs 64 bits sont utilisés partout). Mais il est utile de savoir comment modifier ces paramètres s’ils n’aident pas.

Continuons l'exploration visuelle et voyons si ce modèle est préservé des valeurs entières 16 bits. Le cinquième octet a généralement des valeurs très faibles: 02 et 03 sont le plus souvent rencontrés, et la valeur maximale semble être 05 . Le sixième octet d'un fichier est très souvent nul - mais il contient parfois des valeurs beaucoup plus grandes, telles que 32 ou 2C . Dans cette paire, notre hypothèse sur les valeurs distribuées dans l'intervalle n'est pas particulièrement confirmée.

Nous étudions soigneusement les valeurs initiales

Nous pouvons tester notre supposition en utilisant od pour générer un vidage hexadécimal. L'utilitaire od est similaire à xxd , mais offre une sélection beaucoup plus large de formats de sortie. Nous pouvons l'utiliser pour vider la sortie sous forme d'entiers décimaux 16 bits:

L'option -t de l'utilitaire od spécifie le format de sortie. Dans ce cas, u représente les nombres décimaux non signés et 2 représente deux octets par enregistrement. (Vous pouvez également spécifier ce format à l'aide de l'option -d .)

  $ pour f dans les niveaux / *;  faire od -tu2 $ f |  sed -n 1p;  fait |  moins
 0000000 35 476 3 1024 257 778 2819 8995
 0000000 45 447 3 5376 257 802 10499 8738
 0000000 43 417 259 1281 0 262 1794 1285
 0000000 29 211 2 768 257 516 1282 513
 0000000 45 378 3 1536 5140 263 2305 771
 0000000 49 520 2 768 257 517 1538 4883
 0000000 26 183 2 768 1 517 1538 257
 0000000 26 262 3 1280 256 262 1793 771
 0000000 32 378 2 768 514 260 1281 10240
 0000000 58 164 2 768 10280 10244 1282 771
 0000000 38 218 3 1024 1797 265 2561 771
 0000000 36 240 3 1024 771 1029 1796 257
 0000000 42 495 3 1280 257 5126 1792 771
 0000000 44 396 3 1024 771 5 1793 257
 0000000 42 256 3 1024 771 261 1793 1028
 0000000 27 365 2 768 257 517 1538 768
 0000000 30 279 2 768 514 260 1281 4864
 0000000 50 494 15 5376 257 3879 10511 5140
 0000000 42 347 3 1280 771 262 1793 5140
 0000000 44 394 2 768 514 260 1281 771
 0000000 29156 5634 1046 0 5637 1793 1282
 0000000 32 225 2 768 257 516 1282 771
 0000000 32 294 3 1024 771 517 1794 257
 0000000 31 246 12801 772 0 12805 1586 1028
 lignes 1-24 / 148 (plus)

Cette sortie montre que nos suppositions sur les premiers octets étaient correctes. Nous voyons que la première valeur de 16 bits est dans la plage décimale de 20 à 70, et la deuxième valeur de 16 bits est dans la plage décimale de 100 à 600. Cependant, les valeurs suivantes ne se comportent pas si bien. Certains motifs y apparaissent (par exemple, en quatrième position, étonnamment souvent 1024), mais ils n'ont pas la répétabilité inhérente aux premières valeurs du fichier.

Par conséquent, supposons d'abord que les quatre premiers octets du fichier sont spéciaux et se composent de deux valeurs 16 bits. Puisqu'elles se trouvent au tout début du fichier, il s'agit probablement de métadonnées et elles aident à déterminer comment lire le reste du fichier.

En fait, le deuxième intervalle de valeurs (100–600) est assez proche de l'intervalle de taille de fichier que nous avons remarqué plus tôt (208–680). Ce n'est peut-être pas une coïncidence? Prenons une hypothèse: la valeur 16 bits stockée dans les troisième et quatrième octets du fichier est en corrélation avec la taille totale du fichier. Maintenant que nous avons une hypothèse, nous pouvons la tester. Voyons si les gros fichiers à cet endroit ont vraiment de grandes valeurs à tout moment, et les petits ont de petites valeurs.

Pour afficher la taille du fichier en octets sans aucune autre information, vous pouvez utiliser wc avec l'option -c . De même, vous pouvez ajouter des options à od qui vous permettent d'afficher uniquement les valeurs qui nous intéressent. Ensuite, nous pouvons utiliser la substitution de commandes pour écrire ces valeurs dans des variables de shell et les afficher ensemble:

L'option -An de l'utilitaire od désactive la colonne la plus à gauche, qui affiche le décalage dans le fichier, et -N4 indique à od s'arrêter après les 4 premiers octets du fichier.

  $ pour f dans les niveaux / *;  faire taille = $ (wc -c <$ f);  données = $ (od -tuS -An -N4 $ f);  echo "$ size: $ data";  fait |  moins
 585: 35 476
 586: 45 447
 550: 43,417
 302: 29,211
 517: 45 378
 671: 49 520
 265: 26 183
 344: 26,262
 478: 32 378
 342: 58 164
 336: 38 218
 352: 36 240
 625: 42 495
 532: 44,396
 386: 42 256
 450: 27 365
 373: 30 279
 648: 50 494
 477: 42 347
 530: 44,394
 247: 29 156
 325: 32,225
 394: 32,294
 343: 31 246

En regardant cette sortie, vous pouvez voir que les valeurs sont approximativement corrélées. Les fichiers plus petits ont généralement des valeurs inférieures en deuxième position, et les fichiers volumineux ont des valeurs plus grandes. Cependant, la corrélation n'est pas précise et il convient de noter que la taille du fichier est toujours nettement supérieure à la valeur qui y est stockée.

En outre, la première valeur 16 bits est généralement plus grande avec des fichiers de grande taille, mais la correspondance n'est pas non plus complète, et vous pouvez facilement trouver des exemples de fichiers de taille moyenne avec des valeurs relativement grandes en première position. Mais peut-être que si nous additionnons ces deux valeurs ensemble, leur somme sera mieux corrélée avec la taille du fichier?

Nous pouvons utiliser readpour extraire deux nombres de la sortie oddans des variables distinctes, puis utiliser l'arithmétique du shell pour trouver leur somme:

commande Shellreadne peut pas être utilisé sur le côté droit de la barre verticale, car les commandes transférées au pipeline sont exécutées dans un processeur de commandes enfant (sous-shell), qui, une fois quitté, prend ses variables d'environnement dans le récepteur de bits. Par conséquent, à la place, nous devons utiliser la fonction de substitution de processus bashet diriger la sortie odvers un fichier temporaire, qui peut ensuite être redirigé vers la commande read.

$ pour f dans les niveaux / *; faire taille = $ (wc -c <$ f); lire v1 v2 << (od -tuS -An -N4 $ f); sum = $ (($ v1 + $ v2));
    echo "$ taille: $ v1 + $ v2 = $ sum"; fait | moins
585: 35 + 476 = 511
586: 45 + 447 = 492
550: 43 + 417 = 460
302: 29 + 211 = 240
517: 45 + 378 = 423
671: 49 + 520 = 569
265: 26 + 183 = 209
344: 26 + 262 = 288
478: 32 + 378 = 410
342: 58 + 164 = 222
336: 38 + 218 = 256
352: 36 + 240 = 276
625: 42 + 495 = 537
532: 44 + 396 = 440
386: 42 + 256 = 298
450: 27 + 365 = 392
373: 30 + 279 = 309
648: 50 + 494 = 544
477: 42 + 347 = 389
530: 44 + 394 = 438
247: 29 + 156 = 185
325: 32 + 225 = 257
394: 32 + 294 = 326
343: 31 + 246 = 277
lignes 1-24 / 148 (plus)

La somme des deux nombres correspond également approximativement à la taille du fichier, mais ils ne correspondent toujours pas tout à fait. En quoi sont-ils différents? Montrons leur différence:

$ pour f dans les niveaux / *; faire taille = $ (wc -c <$ f); lire v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ taille - $ v1 - $ v2));
    echo "$ size = $ v1 + $ v2 + $ diff"; fait | moins
585 = 35 + 476 + 74
586 = 45 + 447 + 94
550 = 43 + 417 + 90
302 = 29 + 211 + 62
517 = 45 + 378 + 94
671 = 49 + 520 + 102
265 = 26 + 183 + 56
344 = 26 + 262 + 56
478 = 32 + 378 + 68
342 = 58 + 164 + 120
336 = 38 + 218 + 80
352 = 36 + 240 + 76
625 = 42 + 495 + 88
532 = 44 + 396 + 92
386 = 42 + 256 + 88
450 = 27 + 365 + 58
373 = 30 + 279 + 64
648 = 50 + 494 + 104
477 = 42 + 347 + 88
530 = 44 + 394 + 92
247 = 29 + 156 + 62
325 = 32 + 225 + 68
394 = 32 + 294 + 68
343 = 31 + 246 + 66
lines 1-24/148 (more)

La différence, ou valeur «résiduelle», est affichée à l'extrême droite de la sortie. Cette valeur ne tombe pas tout à fait dans le schéma constant, mais elle semble rester approximativement dans une plage limitée de 40 à 120. Et encore une fois, plus les fichiers sont volumineux, plus leur valeur résiduelle est généralement élevée. Mais parfois, les petits fichiers ont également de grandes valeurs résiduelles, ce n'est donc pas aussi constant que nous le souhaiterions.

Cependant, il convient de noter que les valeurs des résidus ne sont jamais négatives. Par conséquent, l'idée que ces deux valeurs de métadonnées indiquent des sous-sections d'un fichier reste intéressante.

(Si vous êtes assez prudent, vous avez déjà vu quelque chose donnant un indice sur une connexion qui n'a pas encore été remarquée. Si ce n'est pas le cas, continuez à lire; le secret sera bientôt révélé.)

Comparaisons croisées de fichiers plus importantes

À ce stade, ce serait bien de pouvoir comparer plus de 16 octets à la fois. Pour cela, nous avons besoin d'un type de visualisation différent. L'une des bonnes approches consiste à créer une image dans laquelle chaque pixel dénote un octet distinct de l'un des fichiers, et la couleur dénote la valeur de cet octet. Une image peut afficher une tranche des 148 fichiers à la fois si chaque fichier de données est indiqué par une seule rangée de pixels d'image. Étant donné que tous les fichiers sont de tailles différentes, nous prenons les 200 premiers octets de chacun pour créer une image rectangulaire.

Le moyen le plus simple consiste à créer une image en niveaux de gris, dans laquelle la valeur de chaque octet correspond à différents niveaux de gris. Il est très simple de créer un fichier PGM avec nos données, car l'en-tête PGM se compose uniquement de texte ASCII:

 $ echo P5 200 148 255 >hdr.pgm

PGM? PGM, «portable graymap» (« ») — , : ASCII, . — PBM («portable bitmap», « »), 8 , PPM («portable pixmap», « »), 3 .

P5Correspond à la signature initiale du format de fichier PGM. Les deux nombres suivants 200et 148, spécifiez la largeur et la hauteur de l'image, et le dernier 255,, indique la valeur maximale par pixel. L'en-tête PGM se termine par une nouvelle ligne suivie de données de pixels. (Il convient de noter que l'en-tête PGM est le plus souvent divisé en trois lignes de texte distinctes, mais la norme PGM nécessite uniquement que les éléments soient séparés par un caractère d'espacement.)

Nous pouvons utiliser l'utilitaire headpour extraire les 200 premiers octets de chaque fichier:

$ pour f dans les niveaux / *; faire tête -c200 $ f; fait> out.pgm

Ensuite, nous pouvons les concaténer avec un en-tête et créer une image affichée:

xview- il s'agit d'un ancien programme X pour afficher des images dans une fenêtre. Vous pouvez le remplacer par votre visionneuse d'images préférée, par exemple, un utilitaire displayd'ImageMagick, mais gardez à l'esprit qu'il existe étonnamment de nombreuses visionneuses d'images qui n'acceptent pas un fichier image redirigé vers l'entrée standard.

$ cat hdr.pgm out.pgm | xview / dev / stdin

S'il vous est difficile de prendre en compte les détails d'une image sombre, vous pouvez choisir un schéma de couleurs différent. Utilisez l'utilitaire pgmtoppmd'ImageMagick pour convertir les pixels en une gamme de couleurs différente. Cette version va créer une image «négative»:

$ cat hdr.pgm out.pgm | pgmtoppm blanc-noir | xview / dev / stdin

Et cette version rend les faibles valeurs jaunes et les hautes valeurs bleues:

$ cat hdr.pgm out.pgm | pgmtoppm jaune-bleu | xview / dev / stdin

La visibilité des couleurs est une question très subjective, vous pouvez donc expérimenter et choisir celle qui vous convient le mieux. Quoi qu'il en soit, l'image 200 × 148 est assez petite, il est donc préférable d'augmenter la visibilité en augmentant sa taille:

$ cat hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

L'image est sombre, ce qui signifie que la plupart des octets contiennent de petites valeurs. Une bande visible de pixels principalement lumineux plus près du bord gauche contraste avec elle. Cette bande est située dans le troisième octet du fichier qui, comme nous l'avons dit plus haut, varie dans toute la plage de valeurs.

Et bien qu'il n'y ait pas beaucoup de valeurs élevées en dehors du troisième octet, lorsqu'elles apparaissent, elles sont souvent constituées de séries, créant de courtes bandes lumineuses dans l'image. Certaines de ces séries sont interrompues périodiquement, créant un effet de ligne pointillée. (Peut-être qu'avec la bonne sélection de couleurs, il sera possible de remarquer de telles séquences dans des couleurs plus sombres.)

Une étude attentive de l'image permet de comprendre que la bande gauche domine principalement dans la partie gauche. Ces bandes nous parlent d'une certaine répétabilité dans la plupart des fichiers. Mais pas dans tous les fichiers - de temps en temps, il y a des lignes de pixels où les bandes sont interrompues - mais c'est plus que suffisant pour déterminer la présence d'un motif réel. Ce motif disparaît sur le côté droit de l'image, le fond sombre des rayures laisse place à quelque chose de plus bruyant et indéfini. (Il semble que les rayures manquent également dans la partie tout à gauche de l'image, mais, je le répète, il est possible que lorsque vous utilisez un jeu de couleurs différent, vous pouvez voir qu'elles commencent plus près du bord gauche qu'il n'y paraît ici.)

Les rayures sont constituées de fines lignes de pixels légèrement plus lumineux sur un fond de pixels légèrement plus sombres. Par conséquent, ce modèle graphique doit être en corrélation avec le modèle des fichiers de données dans lesquels des valeurs légèrement plus grandes sont également réparties entre des valeurs d'octets légèrement plus petites. Il semble que les rayures soient épuisées approximativement au milieu de l'image. Puisqu'il affiche les 200 premiers octets de fichiers, vous devez vous attendre à ce que le modèle d'octets se termine après environ 100 octets.

Le fait que ces modèles changent dans différents fichiers de données devrait nous conduire à la question: à quoi ressembleront les fichiers après les 200 premiers octets. Eh bien, nous pouvons facilement remplacer l'utilitaire par un headutilitaire tailet voir à quoi ressemblent les 200 derniers octets:

$ pour f dans les niveaux / *; do tail -c200 $ f; done> out.pgm; cat hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

On voit immédiatement que ce domaine des fichiers de données est très différent. Ici, les octets sont beaucoup plus courants, surtout vers la fin du fichier. (Cependant, comme auparavant, ils préfèrent se regrouper en couvrant l'image avec des bandes horizontales lumineuses.) Il semble que la fréquence des valeurs d'octets élevées augmente presque jusqu'à la fin, où elle se casse brusquement et est remplacée par des valeurs faibles dans les dix à douze derniers octets environ. Et le modèle ici n'est pas non plus universel, mais il est trop standard pour être une coïncidence.

Peut-être au milieu des dossiers, il peut y avoir d'autres domaines que nous n'avons pas encore pris en considération. La prochaine chose que nous voulons faire est d'examiner les fichiers entiers de cette façon. Mais comme tous les fichiers ont des tailles différentes, ils ne peuvent pas être placés dans un magnifique tableau rectangulaire de pixels. Nous pouvons remplir la fin de chaque ligne avec des pixels noirs, mais il serait préférable de les redimensionner afin que toutes les lignes aient la même largeur et que les zones proportionnelles des différents fichiers correspondent plus ou moins.

Et nous pouvons réellement le faire avec un peu plus d'efforts. Vous pouvez utiliser Python et sa bibliothèque pour travailler avec des images PIL(«Pillow»):

Fichier showbytes.py:

 import sys from PIL import Image # Retrieve the full list of data files. filenames = sys.argv[1:] # Create a grayscale image, its height equal to the number of data files. width = 750 height = len(filenames) image = Image.new('L', (width, height)) # Fill in the image, one row at a time. for y in range(height): # Retrieve the contents of one data file. data = open(filenames[y]).read() linewidth = len(data) # Turn the data into a pixel-high image, each byte becoming one pixel. line = Image.new(image.mode, (linewidth, 1)) linepixels = line.load() for x in range(linewidth): linepixels[x,0] = ord(data[x]) # Stretch the line out to fit the final image, and paste it into place. line = line.resize((width, 1)) image.paste(line, (0, y)) # Magnify the final image and display it. image = image.resize((width, 3 * height)) image.show()

Lorsque nous appelons ce script, en utilisant la liste complète des fichiers de données comme arguments, il crée une image complète et l'affiche dans une fenêtre distincte:

 $ python showbytes.py niveaux / *

Malheureusement, bien que cette image soit complète, elle ne nous montre rien de nouveau. (Mais en réalité, cela montre encore moins, car le redimensionnement a détruit le motif des rayures.) Probablement, pour étudier l'ensemble des données, nous avons besoin d'un meilleur processus de visualisation.

Caractérisez les données

Dans cet esprit, arrêtons-nous un instant et terminons un recensement complet des données. Nous devons savoir si les fichiers de données donnent la préférence à certaines valeurs d'octets. Par exemple, si chaque valeur est généralement également dupliquée, cela constituera une preuve solide que les fichiers sont réellement compressés.

Pour

réécrire complètement les valeurs, quelques lignes en Python suffisent: Le fichier Census.py:

 import sys data = sys.stdin.read() for c in range(256): print c, data.count(chr(c))

Après avoir poussé toutes les données dans une variable, nous pouvons calculer la fréquence d'occurrence de chaque valeur d'octet.

$ niveaux de chat / * | python ./census.py | moins
0 2458
1 2525
2 1626
3 1768
4 1042
5 1491
6 1081
7 1445
8 958
9 1541
10 1279
11 1224
12 845
13 908
14 859
15 1022
16 679
17 1087
18 881
19 1116
20 1007
21 1189
22 1029
23 733
lignes 1-24 / 256 (plus)

Nous voyons que le plus souvent, il y a des valeurs d'octets 0 et 1, les fréquences suivantes sont 2 et 3, après quoi le nombre continue de diminuer (bien qu'avec moins de constance). Afin de mieux visualiser ces données, nous pouvons transférer la sortie vers gnuplotet transformer ce recensement en un histogramme:

L'option -putilitaire gnuplotordonne de ne pas fermer la fenêtre avec le graphique après la fin des travaux gnuplot.

$ niveaux de chat / * | python ./census.py | gnuplot -p -e 'plot "-" with boxes'

Il est très visible que les premières valeurs d'octets sont beaucoup plus courantes que toutes les autres. Plusieurs des valeurs suivantes sont également assez courantes, puis les fréquences de valeurs d'environ 50 commencent à diminuer le long d'une courbe de probabilité lisse. Cependant, il existe un sous-ensemble de valeurs élevées qui sont régulièrement séparées les unes des autres, dont la fréquence semble plutôt stable. En regardant la sortie d'origine, nous pouvons nous assurer que ce sous-ensemble se compose de valeurs qui peuvent être divisibles par huit.

Ces différences dans le nombre de valeurs suggèrent qu'il existe plusieurs «classes» différentes de valeurs d'octets, il sera donc logique de voir comment ces classes sont distribuées. Le premier groupe de valeurs d'octets sera les valeurs les plus basses: 0, 1, 2 et 3. Ensuite, le deuxième groupe peut être des valeurs de 4 à 64. Et le troisième groupe sera des valeurs supérieures à 64, qui sont divisibles par 8. Tout le reste, y compris non divisible par 8 valeurs supérieures à 64 sera le quatrième et dernier groupe.

Avec tout cela à l'esprit, nous pouvons changer le dernier script de génération d'image écrit. Au lieu d'afficher les valeurs réelles de chaque octet dans une couleur distincte, montrons simplement à quel groupe appartient chaque octet. Vous pouvez attribuer une couleur unique à chacun des quatre groupes, ce qui nous aidera à voir si certaines valeurs apparaissent réellement à certains endroits.

Fichier Showbytes2.py:

 import sys from PIL import Image # Retrieve the full list of data files. filenames = sys.argv[1:] # Create a color image, its height equal to the number of data files. width = 750 height = len(filenames) image = Image.new('RGB', (width, height)) # Fill in the image, one row at a time. for y in range(height): # Retrieve the contents of one data file. data = open(filenames[y]).read() linewidth = len(data) # Turn the data into a pixel-high image, each byte becoming one pixel. line = Image.new(image.mode, (linewidth, 1)) linepixels = line.load() # Determine which group each byte belongs to and assign it a color. for x in range(linewidth): byte = ord(data[x]) if byte < 0x04: linepixels[x,0] = (255, 0, 0) elif byte < 0x40: linepixels[x,0] = (0, 255, 0) elif byte % 8 == 0: linepixels[x,0] = (0, 0, 255) else: linepixels[x,0] = (255, 255, 255) # Paste the line of pixels into the final image, stretching to fit. line = line.resize((width, 1)) image.paste(line, (0, y)) # Magnify the final image and display it. image = image.resize((width, 3 * height)) image.show()

Nous avons attribué quatre groupes rouge, vert, bleu et blanc. (Encore une fois, vous pouvez essayer de choisir d'autres couleurs selon vos préférences.)

 $ python showbytes2.py niveaux / *

Grâce à cette image, nous pouvons pré-confirmer l'exactitude de la séparation des fichiers de données en cinq parties:

L'en-tête de quatre octets que nous avons trouvé plus tôt.
, , (.. ).
, (. 64).
, .
, .

, , , , , 8.

, , , . , , , , .

, ( , ). , .

Bien entendu, cette division du dossier en cinq parties est très arbitraire. Une quatrième partie avec des valeurs d'octets élevées divisibles par huit peut s'avérer être juste la fin de la troisième partie. Ou il peut s'avérer qu'il est préférable de diviser une grande troisième partie en plusieurs parties que nous n'avons pas encore déterminées. A ce stade, la découverte de pièces nous aide davantage à trouver des lieux de recherches complémentaires. Pour l'instant, il nous suffit de savoir qu'il existe des parties dans lesquelles la composition générale des valeurs d'octets change, et une idée approximative de leur taille nous aidera à poursuivre nos recherches.

Recherche de structure

Que devons-nous chercher ensuite? Eh bien, comme auparavant, la façon la plus simple de commencer est à partir du haut du fichier. Ou plutôt près du sommet. Étant donné que nous avons déjà identifié avec confiance la première partie comme un en-tête de quatre octets, examinons de plus près ce qui vient ensuite - la zone que nous appelons la deuxième partie, ou une partie des bandes. Ces bandes sont le signe le plus fort de l'existence de la structure, il est donc préférable de chercher de nouvelles preuves de la présence du motif ici.

(Pour le moment, nous supposons que le modèle de bande commence immédiatement après les quatre premiers octets. Visuellement, ce n'est pas évident, mais cela semble probable, et l'examen des valeurs d'octets devrait rapidement nous montrer la vérité.)

Revenons au vidage hexadécimal, cette fois en nous concentrant sur la deuxième partie. N'oubliez pas que nous nous attendons à trouver un motif répétitif de valeurs légèrement plus élevées uniformément réparties entre des valeurs légèrement inférieures.

L'option -s4ordonne de xxdsauter les 4 premiers octets du fichier.

$ pour f dans les niveaux / *; faire xxd -s4 $ f | sed -n 1p; fait | moins
00000004: 0200 0003 0202 0401 0105 0303 0700 0108 ................
00000004: 0201 0104 0000 0504 0407 0202 0902 010a ................
00000004: 0300 0004 0303 0504 0407 0505 0801 0109 ................
00000004: 0300 0009 0202 1203 0313 0909 1401 0115 ................
00000004: 0203 0305 0000 0602 0207 0505 0901 010a ................
00000004: 0203 0304 0000 0502 0206 0404 0901 010a ................
00000004: 0300 0005 022a 0602 2907 0303 0902 000a ..... * ..) .......
00000004: 0203 0305 0000 0605 0507 0101 0802 0209 ................
00000004: 0300 0007 0303 0901 010a 0707 0b09 090c ................
00000004: 0300 0004 0101 0903 030e 0404 1609 0920 ...............
00000004: 0200 0003 1313 0402 0205 0013 0701 0109 ................
00000004: 0500 0006 0505 0701 0109 0606 0e07 070f ................
00000004: 0100 0003 0101 0a03 030b 0a0a 0e32 3216 .............22.
00000004: 0300 0004 0705 0903 030a 0606 0b08 080c ................
00000004: 0200 0003 0701 0402 0209 0501 0a08 080b ................
00000004: 0200 0003 0202 0901 010a 0303 0b05 010d ................
00000004: 0200 0003 0202 0403 0305 0101 0904 040a ................
00000004: 0300 0007 0303 0f01 0115 0707 2114 1422 ............!.."
00000004: 0200 0003 0202 0403 0309 0101 0a04 040b ................
00000004: 0231 3103 0202 0500 0006 0303 0701 0109 .11.............
00000004: 0200 0003 0202 0b32 320c 0303 0e08 0811 .......22.......
00000004: 0201 0103 0000 0902 020a 0303 0b09 090c ................
00000004: 0200 0003 0202 0a01 010b 0303 0d0b 0b0f ................
00000004: 0300 0005 0303 0701 0109 0001 0b05 051b ................
lines 27-50/148 (more)

, , , , , . , , , , . ( , .)

, , .

, :

-g3 . -c18 définit 18 octets (un multiple de 3) par ligne au lieu de 16.

$ pour f dans les niveaux / *; faire xxd -s4 -g3 -c18 $ f | sed -n 1p; fait | moins
00000004: 050000 060505 070101 090606 0e0707 0f0001 ..................
00000004: 010000 030101 0a0303 0b0a0a 0e3232 161414 ............. 22 ...
00000004: 030000 040705 090303 0a0606 0b0808 0c0101 ..................
00000004: 020000 030701 040202 090501 0a0808 0b0101 ..................
00000004: 020000 030202 090101 0a0303 0b0501 0d0302 ..................
00000004: 020000 030202 040303 050101 090404 0a0302 ..................
00000004: 030000 070303 0f0101 150707 211414 221313 ............! .. "..
00000004: 020000 030202 040303 090101 0a0404 0b0001 ..................
00000004: 023131 030202 050000 060303 070101 090505 .11 ...............
00000004: 020000 030202 0b3232 0c0303 0e0808 110b0b ....... 22 .........
00000004: 020101 030000 090202 0a0303 0b0909 0c0a0a ..................
00000004: 020000 030202 0a0101 0b0303 0d0b0b 0f2323 ................##
00000004: 030000 050303 070101 090001 0b0505 1b0707 ..................
00000004: 022323 030000 040202 050303 030101 070505 .##...............
00000004: 031414 050000 060303 070505 080101 090707 ..................
00000004: 030000 050202 060303 070505 080101 090606 ..................
00000004: 030202 040000 050303 070404 080005 090101 ..................
00000004: 030202 040000 050303 090404 1d0101 1f0909 ..................
00000004: 020000 050303 060101 070202 0f0300 110505 ..................
00000004: 050000 070101 0c0505 0d0007 110c0c 120707 ..................
00000004: 030202 050000 060303 070505 080101 090606 ..................
00000004: 020000 030101 050202 060505 070100 080303 ..................
00000004: 020000 030202 050303 090101 0a0505 0b0302 ..................
00000004: 022c2c 030000 040202 020303 050101 060202 .,,...............
lines 38-61/148 (more)

Dans un vidage formaté de cette manière, d'autres fonctionnalités de ce modèle commencent à apparaître. Comme précédemment, le premier octet de chaque triplet est généralement plus grand que les octets qui l'entourent. Vous pouvez également remarquer que les deuxième et troisième octets de chaque triplet sont souvent dupliqués. En descendant la première colonne, nous verrons que la plupart des valeurs des deuxième et troisième octets sont égales 0000. Mais les valeurs non nulles sont également souvent trouvées par paires, par exemple, 0101ou 2323. Ce schéma est également imparfait, mais il a trop en commun pour être une coïncidence. Et en regardant la colonne ASCII à droite, nous verrons que lorsque nous avons des valeurs d'octets qui correspondent au caractère ASCII imprimable, elles sont souvent trouvées par paires.

Un autre motif à noter qui n'est pas immédiatement perceptible: le premier octet de chaque triple augmente de gauche à droite. Bien que ce modèle soit moins perceptible, sa stabilité est élevée; nous devons examiner beaucoup de lignes avant de trouver le premier décalage. Et les octets augmentent généralement de petites valeurs, mais ils ne représentent aucun modèle régulier.

En étudiant l'image d'origine, nous avons remarqué que la partie avec les rayures se termine dans chaque fichier pas au même endroit. Il y a une transition entre la création d'une bande de motifs à gauche et un bruit aléatoire à droite, mais cette transition se produit pour chaque ligne de pixels à différents points. Cela implique qu'il doit y avoir un marqueur pour que le programme qui lit le fichier de données puisse comprendre où se termine le tableau et où commence un autre ensemble de données.

Revenons au vidage uniquement au premier niveau pour examiner l'ensemble du fichier:

 $ xxd -s4 -g3 -c18 niveaux / leçon_1.pak
00000004: 020000 040202 050404 070505 080707 090001 ..................
00000016: 0a0101 0b0808 0d0a0a 110023 150907 180200 ........... # ......
00000028: 22090d 260911 270b0b 280705 291e01 272705 ".. & .. '.. (..) ..' '.
0000003a: 020d01 220704 090209 0a0215 042609 250111 ... "......... &.% ..
0000004c: 150222 1d0124 011d0d 010709 002000 1b0400 .. ".. $ ....... ....
0000005e: 1a0020 152609 1f0033 002911 152223 02110d ... & ... 3.) .. "# ...
00000070: 010726 091f18 291115 09181a 022302 1b0215 .. & ...) ...... # ....
00000082: 22011c 011c0d 0a0704 090201 020128 260123 "............. (&. #
00000094: 150509 020121 150522 0a2727 0b0504 00060b .....! .. ".''......
000000a6: 082804 18780b 082804 18700b 082804 186400 .(..x..(..p..(..d.
000000b8: 17101e 1e1a19 010300 0e1a17 17100e 1f010e ..................
000000ca: 13141b 291f1a 001210 1f011b 0c1e1f 011f13 ...)..............
000000dc: 10010e 13141b 001e1a 0e1610 1f2d00 201e10 .............-. ..
000000ee: 011610 24291f 1a011a 1b1019 000f1a 1a1d1e ...$).............
00000100: 2d02

En étudiant la séquence des triplets, nous pouvons supposer que la partie avec des bandes dans ces données se termine après 17 triplets, par décalage 00000036. Ce n'est pas exact, mais le premier octet de chaque triplet augmente constamment sa valeur, puis diminue du dix-huitième triplet. Encore une preuve: dans le dix-huitième triplet, le deuxième octet a la même signification que le premier. Nous ne l'avons pas encore remarqué, mais si nous regardons en arrière, nous verrons que le premier octet n'est jamais égal au deuxième ou au troisième octet.

Si notre théorie des marqueurs est correcte, il y a deux possibilités. Premièrement, il est possible qu'après la partie de bande il y ait une valeur d'octet spéciale (juste après le dix-septième triplet). Deuxièmement, il existe probablement une valeur stockée quelque part qui est égale à la taille de la pièce avec des rayures. Cette taille peut être égale à 17 (c'est-à-dire qu'elle indique le nombre de triplets), ou 51 (elle indique le nombre total d'octets dans une partie), ou 55 (51 plus 4, c'est-à-dire le décalage du fichier dans lequel se termine cette partie).

Pour la première option, une valeur à deux octets peut être un marqueur pour la fin de la partie (étant donné qu'une telle séquence ne se produit jamais dans la deuxième partie). Cependant, une étude attentive de plusieurs autres fichiers de données contredit cette idée, car un tel modèle n'apparaît nulle part ailleurs.

Pour la deuxième option, il cherchera évidemment l'indicateur de taille dans la première partie. Voici - la première valeur de 16 bits dans l'en-tête de fichier de quatre octets est 17:

 $ od -An -tuS -N4 niveaux / leçon_1.pak
    17 203

Si notre théorie est correcte, cette valeur ne détermine pas la taille de la partie avec des rayures, mais le nombre d'enregistrements sur trois octets. Pour tester cette idée, revenons à l'informatique, où nous avons comparé la somme de deux valeurs entières de 16 bits avec la taille du fichier. Cette fois, nous multiplions le premier nombre par trois pour obtenir la taille réelle en octets:

$ pour f dans les niveaux / *; faire taille = $ (wc -c <$ f); lire v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ taille - 3 * $ v1 - $ v2));
    echo "$ size = 3 * $ v1 + $ v2 + $ diff"; fait | moins
585 = 3 * 35 + 476 + 4
586 = 3 * 45 + 447 + 4
550 = 3 * 43 + 417 + 4
302 = 3 * 29 + 211 + 4
517 = 3 * 45 + 378 + 4
671 = 3 * 49 + 520 + 4
265 = 3 * 26 + 183 + 4
344 = 3 * 26 + 262 + 4
478 = 3 * 32 + 378 + 4
342 = 3 * 58 + 164 + 4
336 = 3 * 38 + 218 + 4
352 = 3 * 36 + 240 + 4
625 = 3 * 42 + 495 + 4
532 = 3 * 44 + 396 + 4
386 = 3 * 42 + 256 + 4
450 = 3 * 27 + 365 + 4
373 = 3 * 30 + 279 + 4
648 = 3 * 50 + 494 + 4
477 = 3 * 42 + 347 + 4
530 = 3 * 44 + 394 + 4
247 = 3 * 29 + 156 + 4
325 = 3 * 32 + 225 + 4
394 = 3 * 32 + 294 + 4
343 = 3 * 31 + 246 + 4
lines 1-24/148 (more)

Ouais! Après cette modification, le montant total de l'en-tête est toujours exactement quatre fois inférieur à la taille de l'ensemble du fichier de données. Et puisque quatre est également le nombre d'octets dans l'en-tête, il est évident que ce n'est pas une coïncidence. Le premier nombre nous donne le nombre d'entrées de trois octets dans la table, et le deuxième nombre nous donne le nombre d'octets qui composent le reste du fichier de données.

Nous avons trouvé une formule constante, ce qui signifie que nous comprenons maintenant parfaitement ce que signifient les chiffres dans la première partie.

(Au fait, voici le schéma très secret que les lecteurs attentifs peuvent remarquer. Une étude attentive des équations montre clairement que lorsque les fichiers ont le même premier nombre, ils obtiennent la même différence résiduelle. Cela se produit car la différence est toujours le double de la valeur C'est un modèle peu évident, mais un observateur minutieux ou réussi pourrait le remarquer.)

Ainsi, nous pouvons dire que le fichier comprend trois parties principales:

en-tête de quatre octets;
tableau de trois enregistrements d'octets; et
le reste du fichier, qui contient soi-disant la plupart des données.

(Par conséquent, les autres parties que nous avons approximativement déterminées précédemment devraient être des sous-sections de la troisième partie.)

Interprétation des métadonnées

Compte tenu de ce schéma, il serait logique de supposer que les entrées du tableau de la deuxième partie sont des métadonnées nécessaires à l'interprétation des données de la troisième partie.

Mais quel type de métadonnées ce tableau contient-il?

Nous avons remarqué ci-dessus qu'il y a quelques signes que le fichier de données peut être compressé. (Maintenant, cela semble encore plus plausible, car nous savons que la troisième partie de chaque fichier, censée contenir des données de chaque niveau, ne fait que 100 à 600 octets.) Si c'est le cas, il est fort possible que la table qui précède les données principales contienne des métadonnées de compression - un dictionnaire utilisé lors du déballage. Par exemple, avant les données codées par l'algorithme Huffman, il existe généralement un dictionnaire qui mappe les valeurs d'octets d'origine aux séquences de bits. Bien que nous ne nous attendions pas à ce que ces fichiers soient codés par l'algorithme de Huffman (puisque les données montrent des modèles clairs au niveau des octets, c'est-à-dire qu'ils ne sont guère un flux binaire), il serait sage d'essayer d'interpréter ce tableau comme un dictionnaire de décompression.

(, . , deflate, gzip zlib , . , .)

: . , , , , . , — , , . , , — .

Si tel est le cas, alors l'un des moyens les plus simples d'interpréter la partie de bande est que le premier octet est la valeur d'octet qui doit être remplacée dans les données compressées, et les deuxième et troisième octets sont la valeur qui doit être remplacée. Le résultat créé par ce schéma sera certainement plus grand, bien qu'il ne soit pas clair combien. Quoi qu'il en soit, c'est une hypothèse logique, et elle est assez facile à vérifier. Nous pouvons écrire un petit programme en Python qui implémente ce schéma de décompression:

File decompress.py:

 import struct import sys # Read the compressed data file. data = sys.stdin.read() # Extract the two integers of the four-byte header. tablesize, datasize = struct.unpack('HH', data[0:4]) data = data[4:] # Separate the dictionary table and the compressed data. tablesize *= 3 table = data[0:tablesize] data = data[tablesize:datasize] # Apply the dictionary entries to the data section. for n in range(0, len(table), 3): key = table[n] val = table[n+1:n+3] data = data.replace(key, val) # Output the expanded result. sys.stdout.write(data)

Maintenant, nous pouvons vérifier ce script en utilisant un exemple de fichier de données:

$ python ./decompress.py <levels/lesson_1.pak | xxd 00000000: 0b0b 0b0b 0404 0000 0a0a 0109 0d05 0502 ................ 00000010: 0200 0100 0000 0101 0100 0009 0702 0209 ................ 00000020: 1100 0125 0100 2309 0700 0009 0d1d 0124 ...%..#........$ 00000030: 011d 0a0a 0105 0500 0100 2000 1b02 0200 .......... ..... 00000040: 1a00 2009 0709 1100 011f 0033 001e 0100 .. ........3.... 00000050: 2309 0709 0d23 0000 0023 0a0a 0105 0509 #....#...#...... 00000060: 1100 011f 0200 1e01 0023 0907 0001 0200 .........#...... 00000070: 1a00 0023 0000 1b00 0009 0709 0d01 1c01 ...#............ 00000080: 1c0a 0a01 0105 0502 0200 0100 0001 0000 ................ 00000090: 0107 0509 1101 2309 0704 0400 0100 0001 ......#......... 000000a0: 2109 0704 0409 0d01 010b 0b0b 0b08 0804 !............... 000000b0: 0402 0200 0608 0807 0707 0502 0202 0078 ...............x 000000c0: 0808 0707 0705 0202 0200 7008 0807 0707 ..........p..... 000000d0: 0502 0202 0064 0017 101e 1e1a 1901 0300 .....d.......... 000000e0: 0e1a 1717 100e 1f01 0e13 141b 1e01 1f1a ................ 000000f0: 0012 101f 011b 0c1e 1f01 1f13 1001 0e13 ................ 00000100: 141b 001e 1a0e 1610 1f2d 0020 1e10 0116 .........-. .... 00000110: 1024 1e01 1f1a 011a 1b10 1900 0f1a 1a1d .$.............. 00000120: 1e2d 0000

Cependant, les résultats ne sont pas remarquables. Bien sûr, le flux de données résultant est devenu plus déployé que l'original, mais pas beaucoup. Certainement pas assez pour contenir toutes les données que nous espérons trouver. De toute évidence, ce schéma de déballage est un peu plus simple que nécessaire.

Si nous examinons attentivement la sortie résultante, nous verrons bientôt qu'elle commence par de nombreux octets répétés. 0b, 04, 00, 0a- ils se produisent tous les deux par deux. En regardant l'original compressé, nous verrons que toutes ces paires sont apparues en raison d'un remplacement de dictionnaire. Mais dans le processus, nous remarquons immédiatement que toutes ces significations en double correspondent également à des entrées dans le dictionnaire. Autrement dit, si nous appliquons à nouveau le dictionnaire, les données se développeront à nouveau. Peut-être que nous ne déballons pas assez?

Notre première supposition peut être d'effectuer une deuxième passe, en appliquant chaque entrée de dictionnaire une deuxième fois pour étendre encore plus les données. La deuxième supposition peut être d'effectuer plusieurs passes avec le dictionnaire, en répétant le processus jusqu'à ce que tous les octets similaires aux clés du dictionnaire soient remplacés. Cependant, si nous examinons de plus près la structure du dictionnaire, nous réalisons que nous appliquons simplement les entrées du dictionnaire de droite à gauche , et non de gauche à droite, lorsque toutes nos valeurs sont développées en une seule passe.

En prenant cette hypothèse, nous pouvons voir la structure d'un algorithme de compression plus plausible. Le programme prend les données sources et les analyse, à la recherche des séquences à deux octets les plus courantes. Il remplace ensuite la séquence de deux octets par une valeur d'octet qui ne se trouve pas dans les données. Il répète ensuite le processus en le poursuivant jusqu'à ce que les données contiennent plus de deux répétitions de séquences à deux octets. En fait, un tel algorithme de compression a un nom: il est connu sous le nom de compression «re-pair», qui est l'abréviation de «paires récursives».

(Et cela peut expliquer certains modèles que nous voyons dans le dictionnaire. Pendant la compression, le dictionnaire est construit de gauche à droite, donc lors du déballage, il doit être appliqué de droite à gauche. Comme les entrées du dictionnaire font souvent référence aux entrées précédentes, il est logique que les deuxième et troisième octets soient souvent plus petit que le premier.)

Bien que la recompression ne produise pas de résultats très impressionnants, elle présente un avantage: le décompresseur peut être implémenté avec un minimum de code. J'ai moi-même utilisé le recouplage dans certaines situations lorsque j'avais besoin de minimiser la taille totale des données compressées et du code de décompression.

Ainsi, nous pouvons effectuer une modification sur une ligne du programme Python pour appliquer le dictionnaire de droite à gauche:

Fichier decompress2.py:

 import struct import sys # Read the compressed data file. data = sys.stdin.read() # Extract the two integers of the four-byte header. tablesize, datasize = struct.unpack('HH', data[0:4]) data = data[4:] # Separate the dictionary table and the compressed data. tablesize *= 3 table = data[0:tablesize] data = data[tablesize:datasize] # Apply the dictionary entries to the data section in reverse order. for n in range(len(table) - 3, -3, -3): key = table[n] val = table[n+1:n+3] data = data.replace(key, val) # Output the expanded result. sys.stdout.write(data)

Si nous essayons cette version, la sortie sera beaucoup plus grande:

 $ python ./decompress2.py <levels/lesson_1.pak | xxd | less
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000010: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000030: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000050: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000070: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000090: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000000f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000100: 0000 0000 0000 0000 0000 0101 0101 0100 ................
00000110: 0101 0101 0100 0000 0000 0000 0000 0000 ................
00000120: 0000 0000 0000 0000 0000 0100 0000 0101 ................
00000130: 0100 0000 0100 0000 0000 0000 0000 0000 ................
00000140: 0000 0000 0000 0000 0000 0100 2300 0125 ............#..%
00000150: 0100 2300 0100 0000 0000 0000 0000 0000 ..#.............
00000160: 0000 0000 0000 0000 0101 0101 011d 0124 ...............$
00000170: 011d 0101 0101 0100 0000 0000 0000 0000 ................
lignes 1-24 / 93 (plus)

Nous voyons beaucoup d'octets nuls dans cette sortie, mais cela peut bien correspondre à une carte presque vide. Les octets différents de zéro semblent être regroupés les uns à côté des autres. Puisque nous espérons trouver une carte 32 × 32, reformatons la sortie à 32 octets par ligne:

$ python ./decompress2.py <niveaux / leçon_1.pak | xxd -c32 | moins
00000000: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000020: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000040: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000060: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000080: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000a0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000c0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000000e0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
00000100: 0000 0000 0000 0000 0000 0101 0101 0100 0101 0101 0100 0000 0000 0000 0000 0000 ................................
00000120: 0000 0000 0000 0000 0000 0100 0000 0101 0100 0000 0100 0000 0000 0000 0000 0000 ................................
00000140: 0000 0000 0000 0000 0000 0100 2300 0125 0100 2300 0100 0000 0000 0000 0000 0000 ............#..%..#.............
00000160: 0000 0000 0000 0000 0101 0101 011d 0124 011d 0101 0101 0100 0000 0000 0000 0000 ...............$................
00000180: 0000 0000 0000 0000 0100 2000 1b00 0000 0000 1a00 2000 0100 0000 0000 0000 0000 .......... ......... ...........
000001a0: 0000 0000 0000 0000 0100 2300 011f 0033 001e 0100 2300 0100 0000 0000 0000 0000 ..........#....3....#...........
000001c0: 0000 0000 0000 0000 0101 0101 0123 0000 0023 0101 0101 0100 0000 0000 0000 0000 .............#...#..............
000001e0: 0000 0000 0000 0000 0100 2300 011f 0000 001e 0100 2300 0100 0000 0000 0000 0000 ..........#.........#...........
00000200: 0000 0000 0000 0000 0100 0000 1a00 0023 0000 1b00 0000 0100 0000 0000 0000 0000 ...............#................
00000220: 0000 0000 0000 0000 0101 0101 0101 1c01 1c01 0101 0101 0100 0000 0000 0000 0000 ................................
00000240: 0000 0000 0000 0000 0000 0000 0100 0001 0000 0100 0000 0000 0000 0000 0000 0000 ................................
00000260: 0000 0000 0000 0000 0000 0000 0100 2301 2300 0100 0000 0000 0000 0000 0000 0000 ..............#.#...............
00000280: 0000 0000 0000 0000 0000 0000 0100 0001 2100 0100 0000 0000 0000 0000 0000 0000 ................!...............
000002a0: 0000 0000 0000 0000 0000 0000 0101 0101 0101 0100 0000 0000 0000 0000 0000 0000 ................................
000002c0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
000002e0: 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 ................................
lines 1-24/47 (more)

Après avoir soigneusement examiné les modèles de valeurs non nulles, nous verrons que la carte est clairement visible dans la sortie. En fait, nous pouvons rendre ce motif plus visible à l'aide de l'outil de vidage «coloré», qui attribue une couleur à chaque valeur d'octet, simplifiant la recherche de motifs de valeurs en double:

xcdil s'agit d'un outil non standard, mais vous pouvez le télécharger à partir d'ici . Notez l'option -rutilitaire less, qui vous indique d'effacer les séquences de contrôle.

Comparez cela à une carte de premier niveau dessinée par des fans:

Sans aucun doute, nous voyons les données de la carte de niveau. Vous pouvez être sûr que nous avons correctement déterminé l'algorithme de déballage.

Interprétation des données

En comparant les valeurs d'octets avec l'image de la carte, nous pouvons déterminer ce qui 00code une tuile vide, 01code un mur et 23désigne une puce. 1Adésigne une porte rouge, 1B- une porte bleue, etc. Nous pouvons attribuer des valeurs exactes aux puces, clés, portes et toutes les autres tuiles qui composent la carte de niveau entière.

Maintenant, nous pouvons passer au niveau suivant et trouver les valeurs d'octets pour les objets qui y apparaissent. Et continuez avec les niveaux suivants jusqu'à ce que nous obtenions une liste complète des valeurs d'octets et des objets de jeu qu'ils encodent.

Comme nous l'avons initialement suggéré, la carte se termine exactement après 1024 octets (au décalage 000003FF).

Cette fois, pour supprimer les 32 premières lignes du vidage, nous utilisonssed. Comme nous avons 32 octets par ligne, nous ignorerons les 1024 premiers octets.

Immédiatement après les données de la carte se trouve une séquence de 384 octets (dont les valeurs sont dans l'intervalle 00000400- 0000057F), presque toutes égales à zéro, mais des valeurs non nulles se situent également entre elles. Après cela vient un modèle d'octets complètement différent, il serait donc logique de supposer que cette séquence de 384 octets est une partie distincte.

Si nous regardons quelques niveaux supplémentaires, nous remarquons rapidement le modèle. La partie de 384 octets se compose en fait de trois sous-sections de 128 octets chacune. Chaque sous-section commence par quelques octets non nuls suivis de zéros qui remplissent le reste de la sous-section.

; ( ) . , , «» . «» , ( , ) (). , .

, , , , .

128- — , . , :

 $ python ./decompress2.py <levels/lesson_2.pak | xxd | less
00000400: 0608 1c1c 0808 0000 0000 0000 0000 0000 ................
00000410: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000420: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000430: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000440: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000450: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000460: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000470: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000480: a870 98a0 6868 0000 0000 0000 0000 0000 .p..hh..........
00000490: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004a0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004b0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004c0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004d0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004e0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
000004f0: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000500: 6060 6060 5868 0000 0000 0000 0000 0000 ````Xh..........
00000510: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000520: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000530: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000540: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000550: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000560: 0000 0000 0000 0000 0000 0000 0000 0000 ................
00000570: 0000 0000 0000 0000 0000 0000 0000 0000 ................
lines 64-87/93 (more)

: , . 128- 06 , 08 1C . , 06 , 08 — , 1C — .

( , : , 04 , 05 , 06 07. Cet ensemble de notations contient en fait tous les monstres. Lorsque nous étudierons attentivement les différentes valeurs, nous comprendrons finalement que la valeur 0, 1, 2 ou 3 est ajoutée à la valeur d'octet indiquant le type, indiquant la direction initiale de la foule: nord, est, sud ou ouest. C'est-à-dire, par exemple, qu'une valeur d'octet 06indique une puce orientée vers le sud.)

. , , X , — Y . , , , 3 , .. 8. «» , . (, , , , .)

, , :

, xxdaccepte une -svaleur hexadécimale pour l'option .

$ pour f dans les niveaux / *; faire python ./decompress2.py <$ f | xxd -s 0x580 | sed -n 1p; fait | moins
00000580: 9001 0c17 1701 1120 1717 00 ....... ...
00000580: 0000 0c17 1b13 0c0d 101f 011e 1a20 1b00 ............. ..
00000580: f401 0c18 1e1f 101d 0f0c 1800 ............
00000580: 2c01 0c1b 0c1d 1f18 1019 1f00, ...........
00000580: 9001 0c1d 0e1f 140e 1117 1a22 00 ............ "
00000580: 2c01 0d0c 1717 1e01 1a01 1114 1d10 00, ..............
00000580: 2c01 0d10 220c 1d10 011a 1101 0d20 1200, ... "........ ..
00000580: 5802 0d17 1419 1600 X .......
00000580: 0000 0d17 1a0d 0f0c 190e 1000 ............
00000580: f401 0d17 1a0d 1910 1f00 ..........
00000580: f401 0d17 1a0e 1601 110c 0e1f 1a1d 2400 .............. $.
00000580: ee02 0d17 1a0e 1601 0d20 1e1f 101d 0114 ......... ......
00000580: 5802 0d17 1a0e 1601 1901 1d1a 1717 00 X..............
00000580: 5e01 0d17 1a0e 1601 1a20 1f00 ^........ ..
00000580: c201 0d17 1a0e 1601 0d20 1e1f 101d 00 ......... .....
00000580: 2c01 0d1a 2019 0e10 010e 141f 2400 ,... .......$.
00000580: 5000 0d1d 201e 1311 141d 1000 P... .......
00000580: e703 0e0c 1610 0122 0c17 1600 ......."....
00000580: 5802 0e0c 1e1f 1710 0118 1a0c 1f00 X.............
00000580: 8f01 0e0c 1f0c 0e1a 180d 1e00 ............
00000580: 0000 0e10 1717 0d17 1a0e 1610 0f00 1b1d ................
00000580: 2c01 0e13 0e13 0e13 141b 1e00 ,...........
00000580: 8f01 0e13 1417 1710 1d00 ..........
00000580: bc02 0e13 141b 1814 1910 00 ...........
lines 1-24/148 (more)

L'examen de la première paire d'octets dans le reste nous indique rapidement qu'ils contiennent une autre valeur entière de 16 bits. Si nous les considérons comme ceci, alors la majorité des valeurs apparaissent en notation décimale sous forme de nombres ronds:

La commande odutilise à la -jplace pour passer au décalage d'origine -s. Il convient également de noter la commande printf: en plus de fournir une mise en forme, c'est un moyen pratique d'afficher du texte sans un retour à la ligne à la fin.

$ pour f dans les niveaux / *; faire printf "% -20s" $ f; python ./decompress2.py <$ f | od -An -j 0x580 -tuS -N2; fait | moins
levels / all_full.pak 400
niveaux / alphabet.pak 0
niveaux / amsterda.pak 500
levels / apartmen.pak 300
niveaux / arcticfl.pak 400
niveaux / boules_o_.pak 300
niveaux / beware_o.pak 300
niveaux / blink.pak 600
niveaux / blobdanc.pak 0
niveaux / blobnet.pak 500
niveaux / block_fa.pak 500
levels / block_ii.pak 750
niveaux / block_n_.pak 600
levels / block_ou.pak 350
levels / block.pak 450
niveaux / bounce_c.pak 300
niveaux / brushfir.pak 80
niveaux / cake_wal.pak 999
levels / castle_m.pak 600
niveaux / catacomb.pak 399
niveaux / cellbloc.pak 0
niveaux / chchchip.pak 300
niveaux / chiller.pak 399
niveaux / chipmine.pak 700
lignes 1-24 / 148 (plus)

Si nous nous tournons à nouveau vers la liste, créée à l'origine à partir des données que nous nous attendions à trouver dans les fichiers, nous nous rendons compte que ce nombre est le temps de passer le niveau (si la valeur est zéro, il n'y a pas de limite de temps sur le niveau).

Après ces deux octets, les données deviennent plus volatiles. Le fait que pour la plupart des niveaux il reste une dizaine d'octets dans le fichier limite sérieusement leur contenu:

$ python ./decompress2.py <levels / all_full.pak | xxd -s 0x0582
00000582: 0c17 1701 1120 1717 00 ..... ...

Par exemple, il ne reste que neuf octets à ce niveau. Nous prenons en compte cette taille limitée, ainsi que le fait que ces neuf octets contiennent quatre occurrences de la valeur 17, collectées en deux paires. On remarquera immédiatement que le motif des chiffres 17correspond au motif des lettres Lau nom du niveau «TOUT COMPLÈTE». Le nom comporte huit caractères, donc l'octet nul à la fin est très probablement le caractère de fin de ligne. Après avoir découvert cela, vous pouvez regarder trivialement tous les autres niveaux et utiliser leurs noms pour construire une liste complète de personnages:

`00`	fin de ligne
`01`	barre d'espace
`02` - `0B`	chiffres 0-9
`0C` - `25`	lettres AZ
`26` - `30`	signes de ponctuation

Pour la plupart des niveaux, le fichier de données se termine ici. Cependant, quelques dizaines de noms contiennent encore des données. Si nous jetons un coup d'œil à la liste, nous verrons qu'il existe des niveaux avec des boutons de conseil, et ces données restantes contiennent le texte de la ligne de conseil de niveau codé avec le même jeu de caractères que les noms de niveau.

Après cela, nous avons atteint la fin de tous les fichiers. Nous avons maintenant une description complète du schéma de ces niveaux. Notre tâche est terminée.

Affaires inachevées

Un lecteur attentif peut remarquer qu'au départ, nous nous attendions à trouver dans ces fichiers deux autres éléments que nous n'avons jamais rencontrés. Nous expliquerons l'absence des deux:

le premier élément est le nombre de jetons, c'est-à-dire Le nombre total de jetons qu'un joueur doit collecter pour passer à travers le connecteur de jetons. Comme nous l'avons dit initialement, il est souvent égal au nombre total de puces à un niveau, mais cela ne se produit pas toujours. Par conséquent, ces données doivent être obtenues d'une manière ou d'une autre. La réponse peut être trouvée en étudiant les cartes des niveaux auxquels il y a des jetons supplémentaires. Il s'avère que deux valeurs différentes sont utilisées pour indiquer les puces. La valeur que 23nous avons trouvée initialement, mais la valeur est également utilisée.31désignant une puce qui n'affecte pas le montant total requis pour ouvrir le connecteur de puce. (Cependant, du point de vue du gameplay, les deux types de jetons sont identiques. S'il y a un type de jeton 31au niveau, alors au niveau vous ne pouvez pas collecter autant de jetons que vous le souhaitez.)

Le deuxième élément est le mot de passe de niveau à quatre lettres. Il n'est masqué nulle part dans les données de niveau. Malheureusement, ce problème ne peut pas être résolu par une enquête plus approfondie du fichier de données. Nous sommes obligés de conclure que les mots de passe sont simplement stockés ailleurs. L'explication la plus probable: ils sont codés en dur quelque part dans le programme lui-même. Cependant, il est devenu plus tard clair que les mots de passe ne sont pas stockés directement. Des gens familiers avec le code lui-même, j'ai appris que les mots de passe sont générés dynamiquement à l'aide d'un générateur de nombres pseudo-aléatoires initialisé avec une séquence spécifique. Par conséquent, les mots de passe des niveaux ne peuvent pas être modifiés directement, cela ne peut être fait qu'en changeant le code assembleur.

Postface

En effectuant une ingénierie inverse complète des données dans les fichiers de niveau, j'ai pu commencer à écrire un programme qui peut coder et décoder les données de niveau. Grâce à elle, j'ai pu créer l'éditeur de niveau tant attendu pour la version de Chip's Challenge pour Lynx, et la présence de cet outil a considérablement accru ma capacité à étudier la logique du jeu, et également amélioré la qualité de son émulation.

Mais ... je dois admettre que j'ai personnellement fait le développement inverse des fichiers de données d'une manière non décrite ci-dessus. J'ai commencé à l'autre bout - avec la définition des données de chaîne. J'ai commencé à étudier les fichiers des huit premiers niveaux. Puisqu'ils sont appelés de "LEÇON 1" à "LEÇON 8", j'ai recherché des données de sous-chaînes identiques en eux. Et j'ai eu de la chance: aucun des noms de ces niveaux n'a été compressé, donc les huit noms sont stockés dans les fichiers de données dans leur forme d'origine. Bien sûr, j'étais gêné que ces lignes ne soient pas stockées en caractères ASCII, mais le double S du nom m'a aidé à détecter un motif qui se répétait dans les huit fichiers de données. Et ayant trouvé le nom, j'ai reconnu l'encodage des lettres, des chiffres et du caractère espace. Ensuite, j'ai appliqué cet encodage au reste du fichier, et juste après le nom, j'ai vu des lignes d'invite et j'ai commencé à observer les anomalies:

Un grand utilitaire trfacilite la conversion de votre propre jeu de caractères de fichiers de données en ASCII.

$ tr '\ 001- \ 045' '0-9A-Z' <niveaux / leçon_1.pak | xxd
00000000: 4600 cb00 3000 0032 3030 3332 3235 3333 F ... 0..200322533
00000010: 3635 3537 0020 3820 2039 3636 4238 3846 6557. 8 966B88F
00000020: 0058 4a37 354d 3000 5737 4226 3746 2739 .XJ75M0.W7B & 7F'9
00000030: 3928 3533 2953 2027 2733 3042 2057 3532 9 (53) S '' 30B W52
00000040: 3730 3738 304a 3226 375a 2046 4a30 5752 70780J2 & 7Z FJ0WR
00000050: 2059 2052 4220 3537 0055 0050 3200 4f00 Y RB 57.U.P2.O.
00000060: 554a 2637 5400 3300 2946 4a57 5830 4642 UJ & 7T.3.) FJWX0FB
00000070: 2035 2637 544d 2946 4a37 4d4f 3058 3050 5 & 7TM) FJ7MO0X0P
00000080: 304a 5720 5120 5142 3835 3237 3020 3020 0JW Q QB85270 0
00000090: 2826 2058 4a33 3730 2056 4a33 5738 2727 (& XJ370 VJ3W8''
000000a0: 3933 3200 3439 3628 324d 7839 3628 324d 932.496(2Mx96(2M
000000b0: 7039 3628 324d 6400 4c45 5353 4f4e 2031 p96(2Md.LESSON 1
000000c0: 0043 4f4c 4c45 4354 2043 4849 5029 544f .COLLECT CHIP)TO
000000d0: 0047 4554 2050 4153 5420 5448 4520 4348 .GET PAST THE CH
000000e0: 4950 0053 4f43 4b45 542d 0055 5345 204b IP.SOCKET-.USE K
000000f0: 4559 2954 4f20 4f50 454e 0044 4f4f 5253 EY)TO OPEN.DOORS
00000100: 2d30 -0

Par exemple, dans le texte d'aide, il y a deux endroits où la séquence de S et l'espace sont remplacés par le crochet droit. Ces anomalies m'ont donné suffisamment de preuves pour calculer déductivement la présence de compression et obtenir des informations sur sa nature. Plus tard, j'ai associé des valeurs d'octets anormales à leurs occurrences plus près du début du fichier de données. (Par exemple, dans le vidage de décalage hexadécimal illustré ci-dessus, 00000035il y a un crochet droit, suivi d'un S majuscule et d'un espace.) À partir de cela, j'ai calculé le schéma de compression de manière similaire au processus décrit dans l'article. Tout le reste était assez simple.

Il me semble que l'on peut en tirer une leçon: il n'y a pas de moyen unique d'examiner un fichier de données inconnu. Tous les outils qui vous conviennent sont les bons outils pour la rétro-ingénierie.

Introduction à la rétro-ingénierie: piratage du format de données de jeu