🏂🏾 ⛹🏼 ✊🏽 Einführung in das Reverse Engineering: Hacking-Spieldatenformat 🕡 👨‍🚀 🤵🏻

Einführung

Das Reverse Engineering einer unbekannten Datendatei kann als schrittweiser Verständnisprozess beschrieben werden. In vielerlei Hinsicht ähnelt es einer wissenschaftlichen Methode, die nur auf abstrakte Objekte angewendet wird, die vom Menschen geschaffen wurden, und nicht auf die natürliche Welt. Wir beginnen mit der Datenerfassung und verwenden diese Informationen dann, um eine oder mehrere Hypothesen aufzustellen. Wir testen die Hypothesen und wenden die Ergebnisse dieser Tests an, um sie zu klären. Wiederholen Sie gegebenenfalls den Vorgang.

Die Entwicklung von Reverse Engineering-Fähigkeiten ist grundsätzlich eine Frage der Praxis. Indem Sie Erfahrungen sammeln, bauen Sie ein intuitives Verständnis dafür auf, was Sie zuerst erforschen müssen, nach welchen Mustern Sie suchen müssen und welche Tools bequemer zu verwenden sind.

In diesem Artikel werde ich ausführlich über den Prozess des Reverse Engineering von Datendateien aus einem alten Computerspiel sprechen, um zu demonstrieren, wie dies gemacht wird.

Ein kleiner Hintergrund

Alles begann, als ich versuchte, die Chip's Challenge unter Linux neu zu erstellen.

Die Chip's Challenge wurde ursprünglich 1989 für die inzwischen vergessene tragbare Atari Lynx-Konsole veröffentlicht. Für diese Zeit war Atari Lynx ein beeindruckendes Auto, aber es kam zur gleichen Zeit heraus wie der Nintendo Game Boy, der schließlich den Markt eroberte.

Chip's Challenge ist ein Puzzlespiel mit einer Draufsicht und einer Kachelkarte. Wie bei den meisten solchen Spielen besteht das Ziel jedes Levels darin, zum Ausgang zu gelangen. In den meisten Ebenen ist der Ausgang durch einen Anschluss für den Chip geschützt, der nur durch Sammeln einer bestimmten Anzahl von Computerchips umgangen werden kann.

Video: Atari Lynx in Aktion , Komplettlösung der ersten Stufe .

Ein neues Spiel startet ab dem ersten Level unter dem Namen "LEKTION 1". Neben Chips und einem Steckplatz für einen Chip erscheinen Schlüssel und Türen. Auf anderen Ebenen entstehen Hindernisse wie Fallen, Bomben, Wasser und Kreaturen, die sich (meistens) auf vorhersehbaren Wegen bewegen. Mit einer Vielzahl von Objekten und Geräten können Sie viele Rätsel und Zeitlimits erstellen. Um das Spiel zu beenden, musst du mehr als 140 Level durchlaufen.

Obwohl Lynx letztendlich versagte, erwies sich die Chip's Challenge als sehr beliebt und wurde auf viele andere Plattformen portiert, die schließlich unter Microsoft Windows auftauchten und dort weit verbreitet wurden. Rund um das Spiel bildete sich eine kleine, aber engagierte Basis von Fans, und im Laufe der Zeit wurde ein Level-Editor geschrieben, mit dem die Spieler unzählige Level erstellen konnten.

Und hier beginnt meine Geschichte. Ich entschied, dass ich eine Version der grundlegenden Open-Source-Game-Engine erstellen wollte, damit ich die Chip's Challenge unter Linux und Windows spielen und es einfacher machen konnte, alle von Fans erstellten Levels auszuführen.

Die Existenz des Level-Editors stellte sich für mich als Wunder heraus, da ich die verborgenen Funktionen der Spielelogik erkunden, meine eigenen Level erstellen und Tests durchführen konnte. Leider gab es keinen Level-Editor für das ursprüngliche Lynx-Spiel, er erschien nur im bekannteren Port unter Windows.

Der Windows-Port wurde nicht von den ursprünglichen Entwicklern erstellt, daher wurden viele Änderungen an der Spielelogik vorgenommen (und nicht alle waren beabsichtigt). Als ich anfing, meine Engine zu schreiben, wollte ich darin die Logik des ursprünglichen Spiels unter Lynx und die bekanntere Version für Windows neu erstellen. Das Fehlen eines Level-Editors für Lynx hat meine Fähigkeit, das ursprüngliche Spiel im Detail zu studieren, ernsthaft eingeschränkt. Der Windows-Port hatte einen Vorteil: Die Ebenen wurden in einer separaten Datendatei gespeichert, was die Erkennung und das Reverse Engineering vereinfachte. Das Spiel für Lynx wurde auf ROM-Kassetten verteilt, die Sprite-Bilder, Soundeffekte und Maschinencode sowie Level-Daten enthielten, die alle zusammen ausgeführt wurden. Es gibt keine Hinweise darauf, wo sich die Daten in diesem 128-Kilobyte-Speicherauszug des ROM befinden oder wie sie aussehen, und ohne dieses Wissen könnte ich keinen Ebeneneditor für die Lynx-Version erstellen.

Einmal stieß ich in einem gemächlichen Forschungsprozess auf eine Kopie des Chip's Challenge- Ports unter MS-DOS. Wie bei den meisten frühen Ports des Spiels war seine Logik näher am Original als in der Windows-Version. Als ich mir die Programmdaten ansah, um herauszufinden, wie sie gespeichert sind, stellte ich überrascht fest, dass die Ebenendaten in einem separaten Verzeichnis zugewiesen wurden und jede Ebene in einer eigenen Datei gespeichert wurde. Nachdem ich die Level-Daten so bequem getrennt hatte, schlug ich vor, dass es nicht allzu schwierig sein würde, die Level-Datendateien zurückzuentwickeln. Auf diese Weise können Sie einen Level-Editor für die Version des Spiels unter MS-DOS schreiben. Ich entschied, dass dies eine interessante Gelegenheit war.

Aber dann warnte mich ein anderes Mitglied der Chip's Challenge- Community vor einer interessanten Tatsache. Der Inhalt der Level-Dateien für MS-DOS stellte sich als Byte-Dump von ROM Lynx heraus. Dies bedeutete, dass ich, wenn ich die MS-DOS-Dateien dekodieren könnte, dieses Wissen nutzen könnte, um die Ebenen innerhalb des Lynx ROM-Dumps zu lesen und zu ändern. Anschließend können Sie einen Level-Editor direkt für das ursprüngliche Spiel unter Lynx erstellen.

Plötzlich war meine oberste Priorität Reverse Engineering Level-Dateien für MS-DOS.

Datendateien

Hier ist ein Link zum Tarball- Verzeichnis, das alle Datendateien enthält. Ich gebe es für den Fall, dass Sie alle in diesem Artikel beschriebenen Schritte nach mir wiederholen oder versuchen möchten, die Datendateien selbst zu dekodieren.

Ist es legal? Gute Frage. Da diese Dateien nur einen kleinen Teil des Programms für MS-DOS darstellen und für sich genommen unbrauchbar sind und ich sie nur zu Bildungszwecken veröffentliche, glaube ich, dass dies unter die Fair-Use-Anforderungen fällt. Ich hoffe, alle Interessenten stimmen mir zu. (Wenn ich trotzdem einen Drohbrief von Anwälten erhalte, kann ich den Artikel so ändern, dass die Datendateien auf witzige Weise dargestellt werden, und dann erklären, dass es sich um eine Parodie handelt.)

Voraussetzungen

Ich gehe davon aus, dass Sie die Hexadezimalrechnung kennen, auch wenn Sie die Dekodierung von Hexadezimalwerten nicht kennen, und dass Sie mit der Unix-Shell ein wenig vertraut sind. Die in diesem Artikel gezeigte Shell-Sitzung wird auf einem Standard-Linux-System ausgeführt. Die fast verwendeten Befehle sind jedoch gängige Unix-Dienstprogramme und auf anderen Unix-ähnlichen Systemen weit verbreitet.

Erster Blick

Hier ist eine Liste des Verzeichnisses mit den Datendateien vom Port unter MS-DOS:

  $ ls Ebenen
 all_full.pak kuchen_wal.pak eeny_min.pak iceberg.pak Lektion_5.pak mulligan.pak playtime.pak southpol.pak total_.pak
 alphabet.pak schloss_m.pak elementa.pak ice_cube.pak lektion_6.pak nice_day.pak potpourr.pak special.pak verkehr_.pak
 amsterda.pak catacomb.pak fireflie.pak icedeath.pak Lektion_7.pak nightmar.pak problems.pak spirals.pak trinity.pak
 Apartmen.pak cellbloc.pak firetrap.pak icehouse.pak Lektion_8.pak now_you_.pak refracti.pak spooks.pak trust_me.pak
 arcticfl.pak chchchip.pak floorgas.pak invincib.pak lobster_.pak nut_and.pak reverse_.pak steam.pak undergro.pak
 balls_o_.pak chiller.pak gezwungen_e.pak i.pak lock_blo.pak on_the_r.pak rink.pak stripes.pak up_the_b.pak
 Vorsicht_o.pak chipmine.pak force_fi.pak i_slide.pak loop_aro.pak oorto_ge.pak roadsign.pakicide.pak vanishin.pak
 blink.pak citybloc.pak force_sq.pak jailer.pak memory.pak open_que.pak sampler.pak telebloc.pak opfer.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 see_s.pak the_last.pak writer_.pak
 block_ii.pak deceptio.pak glut.pak ladder.pak miss_dir.pak teilweise_.pak short_ci.pak the_mars.pak yorkhous.pak
 block_n_.pak deepfree.pak goldkey.pak lemmings.pak gemischte_nu.pak pentagra.pak shrinkin.pak the_pris.pak
 block_ou.pak digdirt.pak go_with_.pak Lektion_1.pak mix_up.pak perfect_.pak skelzie.pak three_do.pak
 block.pak digger.pak grail.pak Lektion_2.pak monster_.pak pier_sev.pak slide_st.pak time_lap.pak
 bounce_c.pak doublema.pak hidden_d.pak Lektion_3.pak morton.pak ping_pon.pak slo_mo.pak torturec.pak
 pinselfir.pak gezeichnet_an.pak jagd.pak lektion_4.pak mugger_s.pak playhous.pak socialis.pak geworfen_s.pak

Wie Sie sehen können, enden alle Dateien in .pak . .pak ist die Standardberechtigung für die Anwendungsdatendatei, die uns leider keine Informationen über ihre interne Struktur gibt. Dateinamen sind mit einigen Ausnahmen die ersten acht Zeichen des Ebenennamens. (In den Namen der Level-Dateien "BLOCK BUSTER" und "BLOCK BUSTER II" wird beispielsweise das Wort "Buster" weggelassen, damit sie nicht übereinstimmen.)

  $ ls Ebenen |  wc
      17 148 1974

Es gibt 148 Datendateien im Verzeichnis, und das Spiel hat genau 148 Level, also ist hier alles gleich.

Lassen Sie uns nun untersuchen, was diese Dateien sind. xxd ist ein Standarddienstprogramm zum xxd hexadezimalen Daten (hexdump). Mal sehen, wie es in LEKTION 1 aussieht.

  $ xxd Ebenen / Lektion_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

Was ist ein Hexdump-Dienstprogramm? Ein hexadezimaler Speicherauszug ist eine Standardmethode zum Anzeigen der genauen Bytes einer Binärdatei. Die meisten Bytewerte können nicht mit druckbaren ASCII-Zeichen verknüpft werden oder haben ein unverständliches Erscheinungsbild (z. B. ein Tabulatorzeichen). In einem hexadezimalen Speicherauszug werden einzelne Bytes als numerische Werte ausgegeben. Die Werte werden hexadezimal angezeigt, daher der Name. Im obigen Beispiel werden 16 Bytes in einer Ausgabezeile angezeigt. Die Spalte ganz links zeigt die Position der Zeile in der Datei, ebenfalls hexadezimal, sodass die Anzahl in jeder Zeile um 16 erhöht wird. Bytes werden in acht Spalten und zwei Bytes in jeder Spalte angezeigt. Der Hexdump rechts zeigt, wie die Bytes aussehen würden, wenn sie durch Zeichen angezeigt würden. Nur alle nicht druckbaren ASCII-Werte werden durch Punkte ersetzt. Dies erleichtert das Auffinden von Zeichenfolgen, die in eine Binärdatei eingebettet werden können.

Offensichtlich wird das Reverse Engineering dieser Dateien nicht darauf hinauslaufen, nur den Inhalt zu durchsuchen und zu untersuchen, was dort sichtbar ist. Bisher sagt uns nichts, welche Funktionen die Daten ausführen.

Was erwarten wir zu sehen?

Machen wir einen Schritt zurück und klären die Situation: Welche spezifischen Daten erwarten wir in diesen Datendateien?

Am offensichtlichsten ist eine bestimmte „Karte“ des Levels: Daten, die die Positionen von Wänden und Türen sowie alles andere angeben, was das Level einzigartig macht.

(Zum Glück haben die Fans des Spiels mühsame Arbeit geleistet und vollständige Karten für alle 148 Level gesammelt, damit wir wissen können, was auf jeder Karte stehen soll.)

Zusätzlich zur Karte sollte jede Ebene mehrere andere Attribute haben. Beispielsweise können Sie feststellen, dass jede Ebene einen Namen hat, z. B. "LEKTION 1", "PERFEKTES ZUSAMMENPASSEN", "GEZEICHNET UND QUARTAL" usw. Unterschiedliche Ebenen haben auch unterschiedliche Fristen, sodass wir davon ausgehen können, dass diese Informationen auch in den Daten enthalten sind. Zusätzlich hat jede Ebene ihre eigene Anzahl zusammengesetzter Chips. (Wir könnten annehmen, dass diese Anzahl einfach der Anzahl der Chips auf der Ebene entspricht, aber es stellt sich heraus, dass auf einigen Ebenen mehr Chips vorhanden sind, als zum Öffnen des Chipschlitzes erforderlich sind. Zumindest für diese Ebenen sollte die Mindestanzahl in expliziter Form angegeben werden.)

Ein weiteres Datenelement, das wir in den Level-Daten erwarten, ist der Hinweistext. Auf einigen Ebenen gibt es einen „Hinweisknopf“ - ein großes Fragezeichen, das auf dem Boden liegt. Wenn der Chip darauf steht, wird ein Tooltip-Text angezeigt. Die Hinweisschaltfläche befindet sich auf ungefähr 20 Ebenen.

Schließlich hat jedes Level ein Passwort - eine Folge von vier Buchstaben, mit der der Spieler das Spiel von diesem Level aus fortsetzen kann. (Dieses Kennwort ist erforderlich, da Lynx keinen Datenspeicher hat. Es war unmöglich, Spiele auf der Konsole zu speichern, sodass Sie das Spiel fortsetzen können, nachdem Sie die Konsole mit Kennwörtern aktiviert haben.)

Hier ist unsere Liste der relevanten Daten:

Levelkarte
Levelname
Passwortebene
Zeitlimit
Anzahl der Chips
Tooltip-Text

Lassen Sie uns die Gesamtgröße der Daten grob schätzen. Der einfachste Weg, um das Zeitlimit und die Anzahl der Chips zu bestimmen. Beide Parameter können Werte im Bereich von 0 bis 999 haben, sodass sie höchstwahrscheinlich als ganzzahlige Werte mit einer Gesamtgröße von 4 Byte gespeichert werden. Das Passwort besteht immer aus vier Buchstaben, daher wird es höchstwahrscheinlich als vier weitere Bytes gespeichert, dh nur 8 Bytes. Die Länge der Namen der Ebenen variiert zwischen vier und neunzehn Zeichen. Wenn wir annehmen, dass wir ein weiteres Byte benötigen, um die Zeile zu vervollständigen, sind dies zwanzig Bytes, dh die Zwischensumme beträgt 28 Bytes. Der längste QuickInfo-Text ist über 80 Byte groß. Wenn wir diesen Wert auf 90 runden, erhalten wir insgesamt 118 Byte.

Was ist mit dem Level-Schema? Die meisten Ebenen haben eine Größe von 32 × 32 Kacheln. Größere Ebenen existieren nicht. Einige Ebenen sind niedriger, aber es wäre logisch anzunehmen, dass sie einfach in eine 32 × 32-Karte eingebettet sind. Wenn wir annehmen, dass ein Byte für eine Kachel erforderlich ist, werden 1024 Bytes für die gesamte Schaltung benötigt. Das heißt, wir erhalten im Allgemeinen eine grobe Schätzung von 1142 Bytes pro Ebene. Dies ist natürlich nur eine grobe anfängliche Schätzung. Es ist möglich, dass einige dieser Elemente anders oder gar nicht in Level-Dateien gespeichert werden. Oder sie enthalten andere Daten, die wir nicht bemerkt haben oder die wir nicht kennen. Bisher haben wir aber ein gutes Fundament gelegt.

Nachdem wir uns entschieden haben, was wir in den Datendateien erwarten, wollen wir uns wieder mit dem befassen, was sie tatsächlich enthalten.

Was ist da und was nicht

Obwohl die Datendatei auf den ersten Blick völlig unverständlich erscheint, können Sie dennoch einige Punkte darin erkennen. Erstens sehen wir das nicht . Beispielsweise wird der Name des Levels oder der Text der Tipps nicht angezeigt. Sie können verstehen, dass dies kein Zufall ist, wenn Sie andere Dateien studiert haben:

  $ strings level / * |  weniger
 : !!; #
 &> '' :: 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.
 Zeilen 1-24 / 1544 (mehr)

Hier ist nichts außer beliebigen Fragmenten von ASCII-Müll sichtbar.

Vermutlich gibt es irgendwo in diesen Dateien Ebenennamen und Hinweise, die jedoch entweder nicht in ASCII gespeichert sind oder eine Transformation erfahren haben (z. B. aufgrund von Komprimierung).

Beachten Sie auch Folgendes: Die Datei erreicht kaum eine Größe von 256 Byte. Dies ist ziemlich klein, wenn man bedenkt, dass wir seine Größe anfangs auf mehr als 1140 Bytes geschätzt haben.

Die Option -S sortiert Dateien in absteigender Reihenfolge ihrer Größe.

  $ ls -lS Ebenen |  Kopf
 insgesamt 592
 -rw-r - r-- 1 Brotkasten Brotkasten 680 23. Juni 2015 mulligan.pak
 -rw-r - r-- 1 Breadbox Breadbox 675 Jun 23 2015 shrinkin.pak
 -rw-r - r-- 1 Brotkasten Brotkasten 671 23. Juni 2015 ball_o_.pak
 -rw-r - r-- 1 Brotkasten Brotkasten 648 23. Juni 2015 cake_wal.pak
 -rw-r - r-- 1 Brotkasten Brotkasten 647 23. Juni 2015 citybloc.pak
 -rw-r - r-- 1 Breadbox Breadbox 639 Jun 23 2015 four_ple.pak
 -rw-r - r-- 1 Breadbox Breadbox 636 23. Juni 2015 trust_me.pak
 -rw-r - r-- 1 Breadbox Breadbox 625 23. Juni 2015 block_n_.pak
 -rw-r - r-- 1 Breadbox Breadbox 622 23. Juni 2015 mix_up.pak

Die größte Datei benötigt nur 680 Bytes, und das ist nicht sehr viel. Und was wird das kleinste sein?

Die Option -r weist ls an, die Reihenfolge umzukehren.

  $ ls -lSr Ebenen |  Kopf
 insgesamt 592
 -rw-r - r-- 1 Brotkasten Brotkasten 206 23. Juni 2015 kablam.pak
 -rw-r - r-- 1 Brotkasten Brotkasten 214 23. Juni 2015 Fortune_.pak
 -rw-r - r-- 1 Breadbox Breadbox 219 Jun 23 2015 digdirt.pak
 -rw-r - r-- 1 Breadbox Breadbox 226 23. Juni 2015 Lektion_2.pak
 -rw-r - r-- 1 Brotkasten Brotkasten 229 23. Juni 2015 Lektion_8.pak
 -rw-r - r-- 1 Breadbox Breadbox 237 Jun 23 2015 teilweise_.pak
 -rw-r - r-- 1 Breadbox Breadbox 239 Jun 23 2015 knot.pak
 -rw-r - r-- 1 Breadbox Breadbox 247 Jun 23 2015 cellbloc.pak
 -rw-r - r-- 1 Brotkasten Brotkasten 248 23. Juni 2015 torturec.pak

Die kleinste Datei benötigt nur 206 Bytes, was mehr als dreimal kleiner als die größte ist. Dies ist ein ziemlich breiter Bereich, wenn man bedenkt, dass wir ungefähr die gleichen Levelgrößen erwartet haben.

Bei unserer ersten Bewertung gingen wir davon aus, dass die Karte ein Byte pro Kachel und nur 1024 Byte benötigt. Wenn wir diese Schätzung halbieren, dh jede Kachel benötigt nur 4 Bits (oder zwei Kacheln pro Byte), belegt die Karte immer noch 512 Byte. 512 ist kleiner als 680, aber immer noch größer als die meisten Ebenen. Und auf jeden Fall - 4 Bits liefern nur 16 verschiedene Werte, und im Spiel gibt es viel mehr verschiedene Objekte.

Das heißt, es ist offensichtlich, dass die Karten nicht in offener Form in diesen Dateien gespeichert sind. Sie verwenden entweder eine komplexere Codierung, die eine effizientere Beschreibung liefert, und / oder sie sind irgendwie komprimiert. Auf der Ebene „LEKTION 1“ können wir beispielsweise sehen, wie fehlende Einträge für „leere“ Kacheln die Gesamtgröße der Kartendaten erheblich reduzieren.

Wir können uns Karten der größten Dateien ansehen:

Level 57 Karte: Seltsames Labyrinth

Level 98 Karte: SCHRINKEN

und vergleichen Sie sie dann mit Karten der kleinsten Dateien:

Level 106 Karte: KABLAM

Level 112 Karte: FORTUNE FAVORS THE

Dieser Vergleich unterstützt unsere Idee, dass kleine Datendateien einfacheren Ebenen entsprechen oder mehr Redundanz enthalten. Wenn die Daten beispielsweise durch eine Art Lauflängencodierung komprimiert werden, kann dies die Größenintervalle verschiedener Dateien leicht erklären.

Wenn die Dateien tatsächlich verschlüsselt sind, müssen wir höchstwahrscheinlich die Komprimierung entschlüsseln, bevor wir mit dem Entschlüsseln der Kartendaten fortfahren.

Wir untersuchen mehrere Dateien gleichzeitig

Unsere kurze Untersuchung der ersten Datendatei erlaubte es uns, einige Annahmen zu treffen, fand aber nichts Konkretes. Als nächsten Schritt werden wir beginnen, die Muster mehrerer Datendateien zu untersuchen. Im Moment gehen wir davon aus, dass alle 148 Dateien dasselbe Ordnungsschema zum Codieren von Daten verwenden. Wenn Sie also nach doppelten Mustern in diesen Dateien suchen, können Sie sofort loslegen.

Beginnen wir am Anfang der Kacheln. Der obere Rand der Datei wird höchstwahrscheinlich zum Speichern von „Metadaten“ verwendet, die uns über den Inhalt der Datei informieren. Wenn wir nur die erste Zeile des hexadezimalen Speicherauszugs betrachten, können wir einen einfachen und schnellen Vergleich der ersten 16 Bytes durchführen und nach markanten Mustern suchen:

  $ für f in Ebenen / *;  mache xxd $ f |  sed-n 1p;  erledigt |  weniger
 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 ...
 Zeilen 1-24 / 148 (mehr)

Wenn Sie sich diesen Speicherauszug ansehen, sehen Sie, dass in jeder Spalte einige ähnliche Werte vorhanden sind.

Beginnend mit dem ersten Byte stellen wir schnell fest, dass sein Wert in einem sehr begrenzten Wertebereich liegt, im Bereich von hexadezimal 40 (oder ungefähr 20–60 in Dezimal). Dies ist eine ziemlich spezielle Funktion.

Noch interessanter ist, dass das zweite Byte jeder Datei ohne Ausnahmen immer Null ist. Das zweite Byte wird wahrscheinlich nicht verwendet oder ist ein Platzhalter. Es gibt jedoch eine andere Möglichkeit: Diese ersten beiden Bytes stellen zusammen einen 16-Bit-Wert dar, der in Little-Endian-Reihenfolge gespeichert ist.

Was ist Little-Endian? Wenn Sie einen numerischen Wert speichern, der mehr als ein Byte umfasst, müssen Sie zuerst die Reihenfolge auswählen, in der die Bytes gespeichert werden. Wenn Sie zuerst ein Byte speichern, das den kleineren Teil der Zahl darstellt, wird dies als direkte Ordnung ( Little-Endian ) bezeichnet. Wenn Sie zuerst Bytes speichern, die den größten Teil der Zahl bezeichnen, ist dies die umgekehrte Reihenfolge ( Big-Endian ). Zum Beispiel schreiben wir die Dezimalwerte in umgekehrter Reihenfolge (Big-Endian): Die Zeile „42“ bedeutet „zweiundvierzig“, nicht „vier und zwanzig“. Little-Endian ist eine natürliche Ordnung für viele Familien von Mikroprozessoren, daher ist es normalerweise beliebter, mit Ausnahme von Netzwerkprotokollen, für die normalerweise Big-Endian erforderlich ist.

Wenn wir die Analyse fortsetzen, werden wir bald feststellen, dass das dritte Byte in der Datei den beiden vorherigen nicht ähnlich ist: Sein Wert variiert über einen weiten Bereich. Das vierte Byte ist jedoch immer 00 , 01 oder 02 , und 01 ist am häufigsten. Dies deutet auch darauf hin, dass diese beiden Bytes einen weiteren 16-Bit-Wert darstellen, der ungefähr im Bereich der Dezimalwerte 0-700 liegt. Diese Hypothese kann auch durch die Tatsache bestätigt werden, dass der Wert des dritten Bytes normalerweise niedrig ist, wenn der Wert des vierten Bytes 02 , und normalerweise groß, wenn das vierte Byte 00 .

Übrigens ist es erwähnenswert, dass dies teilweise der Grund dafür ist, dass das hexadezimale Dump-Format standardmäßig paarweise Bytes anzeigt - dies erleichtert das Lesen einer Folge von 16-Bit-Ganzzahlen. Das Hex-Dump-Format wurde standardisiert, wenn 16-Bit-Computer verwendet wurden. xxd Sie versuchen, xxd durch xxd -g1 zu xxd -g1 , um die Gruppierung vollständig zu deaktivieren, werden Sie feststellen, dass das Erkennen von Bytepaaren in der Mitte einer Zeile viel Arbeit bedeutet. Dies ist ein einfaches Beispiel dafür, wie die Tools, mit denen unbekannte Daten untersucht werden, dazu führen, dass wir bestimmte Arten von Mustern bemerken. Es ist gut, dass xxd dieses Muster standardmäßig hervorhebt, da es sehr häufig vorkommt (auch heute noch, wenn 64-Bit-Computer überall verwendet werden). Es ist jedoch hilfreich zu wissen, wie diese Parameter geändert werden, wenn sie nicht helfen.

Lassen Sie uns die visuelle Untersuchung fortsetzen und prüfen, ob dieses Muster aus 16-Bit-Ganzzahlwerten erhalten bleibt. Das fünfte Byte hat normalerweise sehr niedrige Werte: 02 und 03 werden am häufigsten angetroffen, und der Maximalwert scheint 05 . Das sechste Byte einer Datei ist sehr oft gleich Null - aber manchmal enthält es viel größere Werte, zum Beispiel 32 oder 2C . In diesem Paar wird unsere Annahme über die im Intervall verteilten Werte nicht besonders bestätigt.

Wir untersuchen die Anfangswerte sorgfältig

Wir können unsere Vermutung testen, indem wir od , um einen Hex-Dump zu generieren. Das Dienstprogramm od ähnelt xxd , bietet jedoch eine viel größere Auswahl an Ausgabeformaten. Wir können es verwenden, um die Ausgabe als 16-Bit-Dezimalzahlen auszugeben:

Die Option -t für das Dienstprogramm od gibt das Ausgabeformat an. In diesem Fall steht u für vorzeichenlose Dezimalzahlen und 2 für zwei Bytes pro Datensatz. (Sie können dieses Format auch mit der Option -d angeben.)

  $ für f in Ebenen / *;  do od -tu2 $ f |  sed-n 1p;  erledigt |  weniger
 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 29 156 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
 Zeilen 1-24 / 148 (mehr)

Diese Ausgabe zeigt, dass unsere Vermutungen über die ersten paar Bytes korrekt waren. Wir sehen, dass der erste 16-Bit-Wert im Dezimalbereich von 20 bis 70 liegt und der zweite 16-Bit-Wert im Dezimalbereich von 100 bis 600. Nachfolgende Werte verhalten sich jedoch nicht so gut. Bestimmte Muster erscheinen in ihnen (zum Beispiel an der vierten Position, überraschend oft 1024), aber sie haben nicht die Wiederholbarkeit, die den ersten Werten der Datei innewohnt.

Nehmen wir daher zunächst an, dass die ersten vier Bytes der Datei speziell sind und aus zwei 16-Bit-Werten bestehen. Da sie sich ganz am Anfang der Datei befinden, handelt es sich höchstwahrscheinlich um Metadaten, die bestimmen, wie der Rest der Datei gelesen werden soll.

Tatsächlich liegt das zweite Werteintervall (100–600) ziemlich nahe an dem zuvor festgestellten Dateigrößenintervall (208–680). Vielleicht ist das kein Zufall? Stellen wir eine Hypothese auf: Der im dritten und vierten Byte der Datei gespeicherte 16-Bit-Wert korreliert mit der Gesamtgröße der Datei. Nachdem wir eine Hypothese haben, können wir sie testen. Mal sehen, ob große Dateien an diesem Ort wirklich immer große Werte haben und kleine kleine Werte.

Um die Dateigröße in Bytes ohne weitere Informationen anzuzeigen, können Sie wc mit der Option -c . Ebenso können Sie od Optionen hinzufügen, mit denen Sie nur die für uns interessanten Werte anzeigen können. Dann können wir die Befehlssubstitution verwenden, um diese Werte in Shell-Variablen zu schreiben und sie zusammen anzuzeigen:

Die Option -An des Dienstprogramms od deaktiviert die Spalte ganz links, in der der Versatz in der Datei -N4 wird, und -N4 weist od , nach den ersten 4 Bytes der Datei anzuhalten.

  $ für f in Ebenen / *;  do size = $ (wc -c <$ f);  Daten = $ (od -tuS -An -N4 $ f);  echo "$ size: $ data";  erledigt |  weniger
 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

Wenn Sie sich diese Ausgabe ansehen, sehen Sie, dass die Werte ungefähr korreliert sind. Kleinere Dateien haben normalerweise niedrigere Werte an der zweiten Position und große Dateien haben größere Werte. Die Korrelation ist jedoch nicht genau, und es ist anzumerken, dass die Dateigröße immer erheblich größer ist als der darin gespeicherte Wert.

Darüber hinaus ist der erste 16-Bit-Wert bei großen Dateien normalerweise auch größer, aber die Übereinstimmung ist auch nicht ganz vollständig, und Sie können leicht Beispiele für mittelgroße Dateien mit relativ großen Werten an der ersten Position finden. Aber wenn wir diese beiden Werte addieren, korreliert ihre Summe möglicherweise besser mit der Dateigröße?

Wir können readzwei Zahlen aus der Ausgabe odin separate Variablen extrahieren und dann die Shell-Arithmetik verwenden, um ihre Summe zu finden:

Shell-Befehlreadkann nicht auf der rechten Seite der vertikalen Leiste verwendet werden, da die an die Pipeline übertragenen Befehle in einem untergeordneten Befehlsprozessor (Subshell) ausgeführt werden, der beim Beenden seine Umgebungsvariablen zum Bitempfänger bringt. Daher müssen wir stattdessen die Prozessersetzungsfunktion verwenden bashund die Ausgabe odin eine temporäre Datei leiten, die dann an den Befehl umgeleitet werden kann read.

$ für f in Ebenen / *; do size = $ (wc -c <$ f); lies v1 v2 << (od -tuS -An -N4 $ f); sum = $ (($ v1 + $ v2));
    echo "$ size: $ v1 + $ v2 = $ sum"; erledigt | weniger
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
Zeilen 1-24 / 148 (mehr)

Die Summe der beiden Zahlen korreliert ebenfalls ungefähr mit der Dateigröße, stimmt aber immer noch nicht ganz überein. Wie unterschiedlich sind sie? Lassen Sie uns ihren Unterschied demonstrieren:

$ für f in Ebenen / *; do size = $ (wc -c <$ f); lies v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ size - $ v1 - $ v2));
    Echo "$ size = $ v1 + $ v2 + $ diff"; erledigt | weniger
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)

Die Differenz oder der Restwert wird ganz rechts in der Ausgabe angezeigt. Dieser Wert fällt nicht ganz in das konstante Muster, scheint aber ungefähr in einem begrenzten Bereich von 40–120 zu bleiben. Und je größer die Dateien sind, desto größer ist normalerweise ihr Restwert. Aber manchmal haben kleine Dateien auch große Restwerte, so dass dies nicht so konstant ist, wie wir es gerne hätten.

Es ist jedoch anzumerken, dass die Werte von Rückständen niemals negativ sind. Daher bleibt die Idee, dass diese beiden Metadatenwerte Unterabschnitte einer Datei anzeigen, attraktiv.

(Wenn Sie vorsichtig genug sind, haben Sie bereits etwas gesehen, das einen Hinweis auf eine Verbindung gibt, die noch nicht bemerkt wurde. Wenn Sie dies nicht getan haben, lesen Sie weiter. Das Geheimnis wird bald gelüftet.)

Größere dateiübergreifende Vergleiche

An dieser Stelle wäre es schön, mehr als 16 Bytes gleichzeitig vergleichen zu können. Dafür benötigen wir eine andere Art der Visualisierung. Ein guter Ansatz besteht darin, ein Bild zu erstellen, in dem jedes Pixel ein separates Byte einer der Dateien bezeichnet und die Farbe den Wert dieses Bytes angibt. Ein Bild kann einen Ausschnitt aller 148 Dateien gleichzeitig anzeigen, wenn jede Datendatei durch eine einzelne Reihe von Bildpixeln angezeigt wird. Da alle Dateien unterschiedliche Größen haben, verwenden wir jeweils die ersten 200 Bytes, um ein rechteckiges Bild zu erstellen.

Am einfachsten ist es, ein Bild in Graustufen zu erstellen, in dem der Wert jedes Bytes unterschiedlichen Graustufen entspricht. Es ist sehr einfach, eine PGM-Datei mit unseren Daten zu erstellen, da der PGM-Header nur aus ASCII-Text besteht:

 $ echo P5 200 148 255 >hdr.pgm

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

P5Ist die erste Signatur für das PGM-Dateiformat. Die nächsten beiden Zahlen 200und 148geben die Breite und Höhe des Bildes an, und die letzte 255,, gibt den Maximalwert pro Pixel an. Der PGM-Header endet mit einer neuen Zeile, gefolgt von Pixeldaten. (Es ist erwähnenswert, dass der PGM-Header meistens in drei separate Textzeilen unterteilt ist. Der PGM-Standard verlangt jedoch nur, dass die Elemente durch ein Leerzeichen getrennt werden.)

Mit dem Dienstprogramm können Sie headdie ersten 200 Bytes aus jeder Datei extrahieren:

$ für f in Ebenen / *; mach den Kopf -c200 $ f; erledigt> out.pgm

Dann können wir sie mit einer Überschrift verketten und ein angezeigtes Bild erstellen:

xview- Dies ist ein altes X-Programm zum Anzeigen von Bildern in einem Fenster. Sie können es durch Ihren bevorzugten Bildbetrachter ersetzen, z. B. ein Dienstprogramm displayvon ImageMagick. Beachten Sie jedoch, dass es überraschend viele Bildbetrachter gibt, die keine Bilddatei akzeptieren, die zur Standardeingabe umgeleitet wird.

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

Wenn es für Sie schwierig ist, die Details in einem dunklen Bild zu berücksichtigen, können Sie ein anderes Farbschema auswählen. Verwenden Sie das Dienstprogramm pgmtoppmvon ImageMagick, um Pixel in einen anderen Farbbereich zu konvertieren. Diese Version erstellt ein "negatives" Bild:

$ cat hdr.pgm out.pgm | pgmtoppm weiß-schwarz | xview / dev / stdin

Und diese Version macht niedrige Werte gelb und hohe Werte blau:

$ cat hdr.pgm out.pgm | pgmtoppm gelb-blau | xview / dev / stdin

Die Sichtbarkeit von Farben ist eine sehr subjektive Frage, sodass Sie experimentieren und auswählen können, welche für Sie am besten geeignet ist. Wie dem auch sei, das 200 × 148-Bild ist recht klein. Daher ist es am besten, die Sichtbarkeit zu erhöhen, indem Sie es vergrößern:

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

Das Bild ist dunkel und dies bedeutet, dass die meisten Bytes kleine Werte enthalten. Ein auffälliger Streifen mit meist hellen Pixeln, der näher am linken Rand liegt, steht im Kontrast dazu. Dieser Streifen befindet sich im dritten Byte der Datei, das, wie oben erwähnt, im gesamten Wertebereich variiert.

Und obwohl es außerhalb des dritten Bytes nicht viele hohe Werte gibt, bestehen sie beim Erscheinen häufig aus Reihen, wodurch kurze helle Streifen im Bild entstehen. Einige dieser Serien werden regelmäßig unterbrochen, wodurch ein gestrichelter Linieneffekt entsteht. (Vielleicht ist es mit der richtigen Farbauswahl möglich, solche Sequenzen in dunkleren Farben zu bemerken.)

Bei sorgfältiger Betrachtung des Bildes kann verstanden werden, dass hauptsächlich im linken Teil kleine vertikale Streifen dominieren. Diese Bands erzählen von einer gewissen Wiederholbarkeit in den meisten Dateien. Aber nicht in allen Dateien - von Zeit zu Zeit gibt es Pixelzeilen, in denen die Bänder unterbrochen sind - ist dies mehr als genug, um das Vorhandensein eines echten Musters festzustellen. Dieses Muster verschwindet auf der rechten Seite des Bildes, der dunkle Hintergrund der Streifen weicht etwas verrauschtem und unbestimmtem. (Es scheint, dass die Streifen auch im linken Teil des Bildes fehlen, aber es ist auch möglich, dass Sie bei Verwendung eines anderen Farbschemas sehen können, dass sie näher am linken Rand beginnen als hier.)

Die Streifen bestehen aus dünnen Linien mit etwas helleren Pixeln vor einem Hintergrund mit etwas dunkleren Pixeln. Daher sollte dieses grafische Muster mit dem Muster von Datendateien korrelieren, in denen geringfügig größere Werte gleichmäßig auf geringfügig kleinere Bytewerte verteilt sind. Es scheint, dass die Streifen ungefähr in der Mitte des Bildes erschöpft sind. Da die ersten 200 Bytes von Dateien angezeigt werden, sollten Sie erwarten, dass das Bytemuster nach etwa 100 Bytes endet.

Die Tatsache, dass sich diese Muster in verschiedenen Datendateien ändern, sollte uns zu der Frage führen: Wie werden die Dateien nach den ersten 200 Bytes aussehen? Nun, wir können das Dienstprogramm leicht durch ein headDienstprogramm ersetzen tailund sehen, wie die letzten 200 Bytes aussehen:

$ für f in Ebenen / *; do tail -c200 $ f; erledigt> out.pgm; cat hdr.pgm out.pgm | xview -zoom 300 / dev / stdin

Wir sehen sofort, dass dieser Bereich von Datendateien sehr unterschiedlich ist. Hier sind Bytes viel häufiger, insbesondere gegen Ende der Datei. (Nach wie vor ziehen sie es jedoch vor, sich zu gruppieren und das Bild mit hellen horizontalen Streifen zu bedecken.) Es scheint, dass die Häufigkeit von hohen Bytewerten fast bis zum Ende zunimmt, wo sie abrupt brechen und in etwa zehn bis zwölf Bytes durch niedrige Werte ersetzt werden. Und das Muster hier ist auch nicht universell, aber es ist zu normal, um ein Zufall zu sein.

Vielleicht gibt es in der Mitte der Dateien andere Bereiche, die wir noch nicht berücksichtigt haben. Als nächstes wollen wir die gesamten Dateien auf diese Weise untersuchen. Da jedoch alle Dateien unterschiedliche Größen haben, können sie nicht in einer schönen rechteckigen Anordnung von Pixeln platziert werden. Wir können das Ende jeder Zeile mit schwarzen Pixeln füllen, aber es wäre besser, wenn Sie die Größe so ändern, dass alle Zeilen die gleiche Breite haben und die proportionalen Bereiche verschiedener Dateien mehr oder weniger übereinstimmen.

Und das können wir tatsächlich mit etwas mehr Aufwand tun. Sie können Python und seine Bibliothek zum Arbeiten mit Bildern verwenden PIL(„Kissen“):

Datei 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()

Wenn wir dieses Skript aufrufen und die vollständige Liste der Datendateien als Argumente verwenden, wird ein vollständiges Bild erstellt und in einem separaten Fenster angezeigt:

 $ python showbytes.py Ebenen / *

Obwohl dieses Bild vollständig ist, zeigt es uns leider nichts Neues. (Aber tatsächlich zeigt es noch weniger, weil die Größenänderung das Muster von den Streifen zerstört hat.) Um den gesamten Datensatz zu untersuchen, benötigen wir wahrscheinlich einen besseren Visualisierungsprozess.

Charakterisieren Sie die Daten

Lassen Sie uns in diesem Sinne einen Moment innehalten und eine vollständige Datenzählung durchführen. Wir müssen wissen, ob Datendateien bestimmte Bytewerte bevorzugen. Wenn beispielsweise jeder Wert normalerweise gleich doppelt vorhanden ist, ist dies ein starker Beweis dafür, dass die Dateien tatsächlich komprimiert sind.

Um die Werte vollständig

neu zu schreiben , reichen nur wenige Zeilen in Python aus: Die Datei census.py:

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

Nachdem wir alle Daten in eine Variable geschrieben haben, können wir die Häufigkeit des Auftretens jedes Bytewerts berechnen.

$ cat Levels / * | Python ./census.py | weniger
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
Zeilen 1-24 / 256 (mehr)

Wir sehen, dass es am häufigsten Bytewerte 0 und 1 gibt, die nächsten in der Frequenz sind 2 und 3, wonach die Anzahl weiter abnimmt (obwohl mit weniger Konstanz). Um diese Daten besser zu visualisieren, können wir die Ausgabe an gnuplotdiese Volkszählung übertragen und in ein Histogramm umwandeln:

Die -pDienstprogrammoption gnuplotbefiehlt, das Fenster mit dem Diagramm nach Abschluss der Arbeit nicht zu schließen gnuplot.

$ cat Levels / * | Python ./census.py | gnuplot -p -e 'plot "-" mit boxen'

Es ist sehr auffällig, dass die ersten paar Byte-Werte viel häufiger sind als alle anderen. Einige der folgenden Werte sind ebenfalls recht häufig, und dann beginnen die Häufigkeiten von Werten ab etwa 50 entlang einer glatten Wahrscheinlichkeitskurve abzunehmen. Es gibt jedoch eine Teilmenge hoher Werte, die gleichmäßig voneinander getrennt sind und deren Häufigkeit ziemlich stabil zu sein scheint. Durch Betrachten der ursprünglichen Ausgabe können wir sicherstellen, dass diese Teilmenge aus Werten besteht, die durch acht teilbar sind.

Diese Unterschiede in der Anzahl der Werte deuten darauf hin, dass es mehrere verschiedene „Klassen“ von Bytewerten gibt. Daher ist es logisch zu sehen, wie diese Klassen verteilt sind. Die erste Gruppe von Bytewerten sind die niedrigsten Werte: 0, 1, 2 und 3. Dann kann die zweite Gruppe Werte von 4 bis 64 sein. Und die dritte Gruppe sind Werte über 64, die durch 8 teilbar sind. Ohne den Rest alles andere, einschließlich Nicht teilbar durch 8 Werte größer als 64 ist die vierte und letzte Gruppe.

Vor diesem Hintergrund können wir das zuletzt geschriebene Skript zur Bilderzeugung ändern. Anstatt die tatsächlichen Werte jedes Bytes in einer separaten Farbe anzuzeigen, zeigen wir einfach, zu welcher Gruppe jedes Byte gehört. Sie können jeder der vier Gruppen eine eindeutige Farbe zuweisen. Auf diese Weise können wir feststellen, ob bestimmte Werte tatsächlich an bestimmten Stellen angezeigt werden.

Showbytes2.py-Datei:

 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()

Wir haben vier Gruppen rot, grün, blau und weiß zugeordnet. (Auch hier können Sie versuchen, andere Farben auszuwählen, die Ihren Vorlieben entsprechen.)

 $ python showbytes2.py Ebenen / *

Dank dieses Bildes können wir die Richtigkeit der Trennung von Datendateien in fünf Teile vorab bestätigen:

Der 4-Byte-Header, den wir zuvor gefunden haben.
, , (.. ).
, (. 64).
, .
, .

Dank dieser Farben ist klar, dass im vierten Teil, wo hohe Bytewerte vorherrschen, wie im Bild in Graustufen zu sehen ist, hohe Bytewerte, die durch 8 geteilt werden, besonders vorherrschen.

Aus dem vorherigen Bild wissen wir, dass der zweite Teil, dh der Teil mit Streifen erstreckt sich über einen fast vollständig roten Bereich. Tatsächlich haben wir in einem der ersten Bilder gesehen, dass der Teil mit den Streifen von links nach rechts im Durchschnitt langsam heller wird.

Wir sehen wieder, dass die grünen Pixel aus dem dritten Hauptteil von Zeit zu Zeit gepunktete Muster aus intermittierenden grünen und roten Pixeln (entweder blau oder weiß) bilden. Dieses Muster ist jedoch nicht besonders regelmäßig und kann imaginär sein.

Natürlich ist diese Aufteilung der Datei in fünf Teile sehr willkürlich. Ein vierter Teil mit hohen Bytewerten, die durch acht teilbar sind, kann sich als das Ende des dritten Teils herausstellen. Oder es stellt sich heraus, dass es am besten ist, einen großen dritten Teil in mehrere Teile zu unterteilen, die wir noch nicht festgelegt haben. In dieser Phase hilft uns die Entdeckung von Teilen mehr, Orte für weitere Forschung zu finden. Im Moment reicht es aus zu wissen, dass es Teile gibt, in denen sich die allgemeine Zusammensetzung der Bytewerte ändert, und eine ungefähre Vorstellung von ihrer Größe wird uns helfen, unsere Forschung fortzusetzen.

Struktursuche

Worauf sollten wir als nächstes achten? Nun, nach wie vor ist der einfachste Weg, um zu beginnen, am Anfang der Datei. Oder besser gesagt, ganz oben. Da wir den ersten Teil bereits ziemlich sicher als Vier-Byte-Header identifiziert haben, schauen wir uns genauer an, was als nächstes kommt - den Bereich, den wir den zweiten Teil oder einen Teil der Bands nennen. Diese Bänder sind der stärkste Hinweis auf die Existenz der Struktur, daher ist es besser, hier nach neuen Beweisen für das Vorhandensein des Musters zu suchen.

(Derzeit gehen wir davon aus, dass das Streifenmuster unmittelbar nach den ersten vier Bytes beginnt. Visuell ist dies nicht offensichtlich, aber es scheint wahrscheinlich, und die Untersuchung der Bytewerte sollte uns schnell die Wahrheit zeigen.)

Kehren wir zum Hex-Dump zurück und konzentrieren uns diesmal auf den zweiten Teil. Denken Sie daran, dass wir ein sich wiederholendes Muster von etwas höheren Werten erwarten, das gleichmäßig auf etwas niedrigere Werte verteilt ist.

Die Option -s4befiehlt, xxddie ersten 4 Bytes der Datei zu überspringen.

$ für f in Ebenen / *; mache xxd -s4 $ f | sed-n 1p; erledigt | weniger
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)

Wenn wir uns die Reihenfolge der Bytes in der Zeichenfolge genau ansehen, können wir ein Muster erkennen, bei dem das erste, vierte, siebte und zehnte Byte größer sind als die nächsten Nachbarn. Dieses Muster ist unvollkommen, es gibt Ausnahmen, aber es ist definitiv stabil genug, um die visuelle Wiederholbarkeit der auf allen Bildern sichtbaren Bänder zu erzeugen. (Und es reicht aus, um unsere Annahme zu bestätigen, dass das Streifenmuster unmittelbar nach dem Vier-Byte-Header beginnt.) Die

Konstanz dieses Musters impliziert eindeutig, dass dieser Teil der Datei ein Array oder eine Tabelle ist und jeder Datensatz im Array eine Länge von drei Bytes hat.

Sie können das Hex-Dump-Format so konfigurieren, dass die Ausgabe einfacher als eine Reihe von Triplets angezeigt wird:

Mit dieser Option wird -g3die Gruppierung nach drei Bytes anstelle von zwei festgelegt. Option-c18 Setzt 18 Bytes (ein Vielfaches von 3) pro Zeile anstelle von 16.

$ für f in Ebenen / *; mache xxd -s4 -g3 -c18 $ f | sed-n 1p; erledigt | weniger
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)

In einem auf diese Weise formatierten Speicherauszug werden einige andere Merkmale dieses Musters angezeigt. Nach wie vor ist das erste Byte jedes Tripletts normalerweise größer als die es umgebenden Bytes. Sie können auch feststellen, dass das zweite und dritte Byte jedes Tripletts häufig dupliziert werden. Wenn wir die erste Spalte durchgehen, werden wir sehen, dass die meisten Werte des zweiten und dritten Bytes gleich sind 0000. Werte ungleich Null werden aber auch häufig paarweise gefunden, zum Beispiel 0101oder 2323. Dieses Muster ist ebenfalls unvollkommen, aber es hat zu viel gemeinsam, um ein Zufall zu sein. Wenn wir uns die ASCII-Spalte rechts ansehen, werden wir sehen, dass Bytewerte, die dem druckbaren ASCII-Zeichen entsprechen, häufig paarweise gefunden werden.

Ein weiteres erwähnenswertes Muster, das nicht sofort erkennbar ist: Das erste Byte jedes Tripels erhöht sich von links nach rechts. Obwohl dieses Muster weniger auffällt, ist seine Stabilität hoch; Wir müssen uns viele Zeilen ansehen, bevor wir die erste Nichtübereinstimmung finden. Und Bytes erhöhen sich normalerweise um kleine Werte, aber sie repräsentieren kein reguläres Muster.

Beim Studium des Originalbildes haben wir festgestellt, dass der Teil mit den Streifen in jeder Datei nicht an derselben Stelle endet. Es gibt einen Übergang vom Erstellen eines Musterstreifens links zum zufälligen Rauschen rechts, aber dieser Übergang erfolgt für jede Pixelreihe an verschiedenen Punkten. Dies bedeutet, dass eine Markierung vorhanden sein muss, damit das Programm, das die Datendatei liest, verstehen kann, wo das Array endet und ein anderer Datensatz beginnt.

Kehren wir zum Dump zurück, nur zur ersten Ebene, um die gesamte Datei zu untersuchen:

 $ xxd -s4 -g3 -c18 Ebenen / Lektion_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

Wenn wir die Folge von Tripletts untersuchen, können wir vorläufig annehmen, dass der Teil mit den Bändern in diesen Daten nach 17 Tripletts durch Versatz endet 00000036. Dies ist nicht genau, aber das erste Byte jedes Tripletts erhöht ständig seinen Wert und nimmt dann um das achtzehnte Triplett ab. Noch ein Beweis: Im achtzehnten Triplett hat das zweite Byte die gleiche Bedeutung wie das erste. Wir haben dies noch nicht bemerkt, aber wenn wir zurückgehen und nachsehen, werden wir sehen, dass das erste Byte niemals gleich dem zweiten oder dritten Byte ist.

Wenn unsere Markertheorie korrekt ist, gibt es zwei Möglichkeiten. Erstens ist es möglich, dass nach dem Strip-Teil ein spezieller Byte-Wert steht (direkt nach dem siebzehnten Triplett). Zweitens ist wahrscheinlich irgendwo ein Wert gespeichert, der der Größe des Teils mit Streifen entspricht. Diese Größe kann gleich 17 sein (dh es gibt die Anzahl der Triplets an) oder 51 (es gibt die Gesamtzahl der Bytes in einem Teil an) oder 55 (51 plus 4, dh der Versatz der Datei, in der dieser Teil endet).

Bei der ersten Option kann ein Doppelbytewert eine Markierung für das Ende des Teils sein (vorausgesetzt, eine solche Sequenz tritt im zweiten Teil niemals auf). Eine sorgfältige Untersuchung mehrerer anderer Datendateien widerspricht dieser Idee, da ein solches Muster nirgendwo anders auftritt.

Bei der zweiten Option wird offensichtlich nach dem Größenindikator im ersten Teil gesucht. Siehe - der erste 16-Bit-Wert im 4-Byte-Dateikopf ist 17:

 $ od -An -tuS -N4 Ebenen / Lektion_1.pak
    17 203

Wenn unsere Theorie richtig ist, bestimmt dieser Wert nicht die Größe des Teils mit Streifen, sondern die Anzahl der Drei-Byte-Datensätze. Um diese Idee zu testen, kehren wir zum Rechnen zurück, wo wir die Summe von zwei 16-Bit-Ganzzahlwerten mit der Dateigröße verglichen haben. Dieses Mal multiplizieren wir die erste Zahl mit drei, um die tatsächliche Größe in Bytes zu erhalten:

$ für f in Ebenen / *; do size = $ (wc -c <$ f); lies v1 v2 << (od -tuS -An -N4 $ f); diff = $ (($ size - 3 * $ v1 - $ v2));
    Echo "$ size = 3 * $ v1 + $ v2 + $ diff"; erledigt | weniger
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)

Ja!Nach dieser Änderung ist der Gesamtbetrag aus dem Header immer genau vier weniger als die Größe der gesamten Datendatei. Und da vier auch die Anzahl der Bytes im Header ist, ist es offensichtlich, dass dies kein Zufall ist. Die erste Zahl gibt uns die Anzahl der Drei-Byte-Einträge in der Tabelle an, und die zweite Zahl gibt uns die Anzahl der Bytes an, aus denen der Rest der Datendatei besteht.

Wir haben eine konstante Formel gefunden, was bedeutet, dass wir jetzt vollständig verstehen, was die Zahlen im ersten Teil bedeuten.

(Übrigens, hier ist das sehr geheime Muster, das aufmerksame Leser bemerken könnten. Eine sorgfältige Untersuchung der Gleichungen macht deutlich, dass die Dateien, wenn sie dieselbe erste Nummer haben, dieselbe Restdifferenz erhalten. Dies geschieht, weil die Differenz immer das Zweifache des Wertes beträgt Dies ist ein nicht offensichtliches Muster, aber ein sorgfältiger oder erfolgreicher Beobachter könnte es bemerken.)

Wir können also sagen, dass die Datei drei Hauptteile hat:

Vier-Byte-Header;
Tabelle mit drei Byte-Datensätzen; und
der Rest der Datei, die angeblich die meisten Daten enthält.

(Folglich sollten die anderen Teile, die wir ungefähr früher bestimmt haben, Unterabschnitte des dritten Teils sein.)

Metadaten interpretieren

Angesichts dieses Schemas wäre es logisch anzunehmen, dass die Einträge in der Tabelle des zweiten Teils einige Metadaten sind, die für die Interpretation der Daten des dritten Teils erforderlich sind.

Aber welche Art von Metadaten enthält diese Tabelle?

Wir haben oben festgestellt, dass es einige Anzeichen dafür gibt, dass die Datendatei möglicherweise komprimiert ist. (Dies erscheint jetzt noch plausibler, da wir wissen, dass der dritte Teil jeder Datei, der angeblich Daten jeder Ebene enthält, nur 100 bis 600 Byte groß ist.) Wenn ja, ist es durchaus möglich, dass die Tabelle vor den Hauptdaten Komprimierungsmetadaten enthält - ein Wörterbuch, das beim Auspacken verwendet wird. Beispielsweise gibt es vor Daten, die vom Huffman-Algorithmus codiert werden, normalerweise ein Wörterbuch, das die ursprünglichen Bytewerte Bitsequenzen zuordnet. Obwohl wir nicht erwarten, dass diese Dateien vom Huffman-Algorithmus codiert werden (da die Daten auf Byte-Ebene klare Muster zeigen, dh kaum einen Bitstream darstellen), ist es ratsam, diese Tabelle als Dekomprimierungswörterbuch zu interpretieren.

(Natürlich verwendet nicht jeder Komprimierungstyp ein gespeichertes Wörterbuch. Beispielsweise verwendet der Deflate-Algorithmus das Wörterbuch gzipund zlibermöglicht es Ihnen, es direkt aus dem Datenstrom neu zu erstellen. Solche Fälle sind jedoch eher die Ausnahme als die Regel.)

Normalerweise besteht der Wörterbucheintrag aus zwei Teilen: dem Schlüssel und Werte. Natürlich wird manchmal ein Schlüssel impliziert, beispielsweise wenn er nicht in eine Nachschlagetabelle, sondern in ein Array geordnet wird. Wir haben jedoch bereits festgestellt, dass Drei-Byte-Datensätze aus zwei Teilen zu bestehen scheinen - insbesondere folgt das erste Byte jedes Datensatzes einem Muster, das sich deutlich vom Muster des zweiten und dritten Bytes unterscheidet. Vor diesem Hintergrund wäre eine vernünftige erste Hypothese, das erste Byte als Schlüssel und die verbleibenden zwei Bytes als Wert zu betrachten.

Wenn dies der Fall ist, besteht eine der einfachsten Möglichkeiten zur Interpretation des Streifenteils darin, dass das erste Byte der Bytewert ist, der in den komprimierten Daten ersetzt werden muss, und das zweite und dritte Byte der Wert sind, der ersetzt werden muss. Das mit diesem Schema erzielte Ergebnis wird definitiv größer sein, obwohl nicht klar ist, wie viel. Wie dem auch sei, dies ist eine logische Hypothese und leicht zu überprüfen. Wir können ein kurzes Programm in Python schreiben, das dieses Dekomprimierungsschema implementiert:

Datei 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)

Jetzt können wir dieses Skript anhand einer Beispieldatendatei überprüfen:

$ 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

Die Ergebnisse sind jedoch unauffällig. Natürlich wurde der resultierende Datenstrom mehr bereitgestellt als der ursprüngliche, aber nicht viel. Auf jeden Fall nicht genug, um alle Daten zu enthalten, die wir erwarten zu finden. Offensichtlich ist dieses Auspackschema etwas einfacher als nötig.

Wenn wir die resultierende Ausgabe sorgfältig untersuchen, werden wir bald feststellen, dass sie mit vielen wiederholten Bytes beginnt. 0b, 04, 00, 0a- sie alle treten paarweise auf . Wenn wir uns das komprimierte Original ansehen, werden wir sehen, dass alle diese Paare aufgrund eines Wörterbuchersatzes entstanden sind. Dabei stellen wir jedoch sofort fest, dass all diese doppelten Bedeutungen auch Einträgen im Wörterbuch entsprechen. Das heißt, wenn wir das Wörterbuch erneut anwenden, werden die Daten erneut erweitert. Vielleicht packen wir nicht genug aus?

Unsere erste Vermutung könnte darin bestehen, einen zweiten Durchgang durchzuführen und jeden Wörterbucheintrag ein zweites Mal anzuwenden, um die Daten noch weiter zu erweitern. Die zweite Vermutung kann darin bestehen, mehrere Durchgänge mit dem Wörterbuch durchzuführen und den Vorgang zu wiederholen, bis alle Bytes, die den Schlüsseln des Wörterbuchs ähnlich sind, ersetzt wurden. Wenn wir uns jedoch die Struktur des Wörterbuchs genauer ansehen, stellen wir fest, dass wir die Wörterbucheinträge einfach von rechts nach links und nicht von links nach rechts anwenden , wenn alle unsere Werte in einem Durchgang erweitert werden.

Anhand dieser Hypothese können wir die Struktur eines plausibleren Komprimierungsalgorithmus erkennen. Das Programm nimmt die Quelldaten und durchsucht sie nach den häufigsten Doppelbyte-Sequenzen. Anschließend wird die Zwei-Byte-Sequenz durch einen Byte-Wert ersetzt, der nicht in den Daten enthalten ist. Anschließend wird der Vorgang wiederholt und fortgesetzt, bis die Daten mehr als zwei Wiederholungen von Doppelbyte-Sequenzen enthalten. Tatsächlich hat ein solcher Komprimierungsalgorithmus einen Namen: Er wird als "Re-Pair" -Komprimierung bezeichnet, was für "rekursive Paare" steht.

(Und dies kann einige Muster erklären, die wir im Wörterbuch sehen. Während der Komprimierung wird das Wörterbuch von links nach rechts erstellt. Wenn es entpackt wird, sollte es von rechts nach links angewendet werden. Da Wörterbucheinträge häufig auf vorherige Einträge verweisen, ist es logisch, dass das zweite und dritte Byte häufig verwendet werden kleiner als der erste.)

Die Re-Pair-Komprimierung führt zwar nicht zu sehr beeindruckenden Ergebnissen, hat jedoch einen Vorteil: Der Dekomprimierer kann mit einem Minimum an Code implementiert werden. Ich selbst habe Wieder Paar, in einigen Situationen verwendet, wenn ich zu minimieren hatte die Gesamtgröße der komprimierten Daten und dekomprimieren Code.

Wir können also eine Änderung in einer Zeile des Python-Programms vornehmen, um das Wörterbuch von rechts nach links anzuwenden:

Datei 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)

Wenn wir diese Version ausprobieren, wird die Ausgabe viel größer sein:

 $ 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 ................
Zeilen 1-24 / 93 (mehr)

Wir sehen viele Null-Bytes in dieser Ausgabe, aber dies kann durchaus einer fast leeren Karte entsprechen. Bytes ungleich Null scheinen nebeneinander gruppiert zu sein. Da wir hoffen, eine 32 × 32-Karte zu finden, formatieren wir die Ausgabe auf 32 Byte pro Zeile neu:

$ python ./decompress2.py <Ebenen / Lektion_1.pak | xxd -c32 | weniger
00000000: 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)

Wenn wir uns die Muster von Werten ungleich Null genau angesehen haben, werden wir sehen, dass die Karte in der Ausgabe deutlich sichtbar ist. Tatsächlich können wir dieses Muster mit dem "farbigen" Dump-Tool besser sichtbar machen, das jedem Byte-Wert eine Farbe zuweist, was die Suche nach Mustern mit wiederholten Werten vereinfacht: Es

xcdist ein nicht standardmäßiges Tool, das Sie jedoch von hier herunterladen können . Beachten Sie die -rDienstprogrammoption less, mit der Sie die Steuersequenzen löschen können.

Vergleichen Sie dies mit einer von Fans gezeichneten Karte der ersten Ebene:

Ohne Zweifel sehen wir die Daten der Levelkarte. Sie können ziemlich sicher sein, dass wir den Entpackungsalgorithmus korrekt bestimmt haben.

Dateninterpretation

Durch Vergleichen der Bytewerte mit dem Kartenbild können wir bestimmen, was 00eine leere Kachel 01codiert, eine Wand codiert und 23einen Chip bezeichnet. 1Abezeichnet eine rote Tür, 1B- eine blaue Tür und so weiter. Wir können den Chips, Schlüsseln, Türen und allen anderen Kacheln, aus denen die gesamte Levelkarte besteht, genaue Werte zuweisen.

Jetzt können wir zur nächsten Ebene gehen und die Bytewerte für die dort angezeigten Objekte finden. Fahren Sie mit den nächsten Ebenen fort, bis Sie eine vollständige Liste der Bytewerte und Spielobjekte erhalten, die sie codieren.

Wie ursprünglich vorgeschlagen, endet die Karte genau nach 1024 Byte (im Offset 000003FF).

Dieses Mal verwenden wir, um die ersten 32 Zeilen des Dumps zu entfernensed. Da wir 32 Bytes pro Zeile haben, überspringen wir die ersten 1024 Bytes.

Unmittelbar nach den Kartendaten befindet sich eine Folge von 384 Bytes (deren Werte im Intervall 00000400- liegen 0000057F), von denen fast alle gleich Null sind, aber auch Werte ungleich Null zwischen ihnen liegen. Danach folgt ein völlig anderes Bytemuster, daher wäre es logisch anzunehmen, dass diese 384-Byte-Sequenz ein separater Teil ist.

Wenn wir uns ein paar weitere Ebenen ansehen, bemerken wir schnell das Muster. Der 384-Byte-Teil besteht tatsächlich aus drei Unterabschnitten mit jeweils 128 Byte Länge. Jeder Unterabschnitt beginnt mit einigen Bytes ungleich Null, gefolgt von Nullen, die den Rest des Unterabschnitts ausfüllen.

Einige Ebenen enthalten viele Daten. für andere (zum Beispiel für die erste Stufe) nur das Minimum. Wenn wir die Levels mit ihren Karten vergleichen, werden wir bald feststellen, dass die Datenmenge in diesem Teil der Datei in direktem Zusammenhang mit der Anzahl der „Mobs“ pro Level steht. In diesem Fall umfasst die Anzahl der "Mobs" alle Kreaturen auf dem Level, Landblöcke (die sich nicht unabhängig bewegen, aber geschoben werden können) und den Hauptcharakter Chip (Spieler). Das heißt, Mobs werden nicht auf der Karte selbst angezeigt, sondern in diesen drei Puffern codiert.

Nachdem wir erfahren haben, dass diese drei Unterabschnitte Daten zu den Mobs auf der Ebene enthalten, wird es nicht sehr schwierig sein, herauszufinden, was in jedem der Unterabschnitte enthalten ist.

Der erste 128-Byte-Unterabschnitt ist eine Liste von Bytewerten, die den Mob-Typ bestimmen. Zum Beispiel sehen Puffer der zweiten Ebene folgendermaßen aus:

 $ 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 ................
Zeilen 64-87 / 93 (mehr)

Vergleichen Sie dies mit einer Levelkarte:

Auf dieser Ebene gibt es sechs Mobs: drei Bugs, zwei Blocks und einen Chip. Der erste 128-Byte-Unterschlüssel enthält ein Byte 06, drei Bytes 08und zwei Bytes 1C. Es wäre vernünftig zu schließen, wofür 06Chip steht 08- ein Fehler und 1C- ein Block.

(Fortsetzung auf Datendateien aus den Ebenen der Karten und füllt im Wörterbuch Mobs zu vergleichen, wir schnell einen Fehler in dieser Theorie finden: Der Chip kann auf vier verschiedene Werte bezeichnet werden, nämlich 04, 05, 06oder07. Dieser Satz von Notationen enthält tatsächlich alle Mobs. Wenn wir die verschiedenen Werte sorgfältig untersuchen, werden wir schließlich verstehen, dass der Wert 0, 1, 2 oder 3 zu dem Bytewert addiert wird, der den Typ angibt und die Anfangsrichtung des Mobs angibt: Nord, Ost, Süd oder West. Das heißt, ein Bytewert 06bezeichnet einen Chip, der nach Süden schaut.)

Die Bedeutung der beiden anderen Unterabschnitte ist weniger offensichtlich. Nachdem wir jedoch die sich wiederholenden Werte in diesen Unterabschnitten untersucht und die Karten für diese Mobs verglichen haben, werden wir verstehen, dass die Bytes im zweiten Unterabschnitt die X-Koordinate jedes Mobs und die Bytes im dritten Unterabschnitt die Y-Koordinate jedes Mobs speichern. Das Verständnis dieser Entscheidung wird durch die Tatsache behindert, dass die in diesen Unterabschnitten gespeicherten Koordinaten tatsächlich um 3 Bits nach links verschoben sind, d. H. multipliziert mit 8. Diese kleine Tatsache erklärt die „blaue“ Gruppe, die wir in der Wertezählung gefunden haben. (Die Gründe, warum diese Verschiebung vorgenommen wurde, sind nicht klar, aber höchstwahrscheinlich werden die unteren drei Bits verwendet, um die Animation darzustellen, wenn sich die Mobs bewegen.)

Nachdem wir uns mit diesem Teil befasst haben, können wir jetzt sehen, wie viele Datendateien nur noch wenige Bytes hinter sich haben:

Hinweis wasxxdakzeptiert einen -shexadezimalen Wert für die Option .

$ für f in Ebenen / *; Python machen ./decompress2.py <$ f | xxd -s 0x580 | sed-n 1p; erledigt | weniger
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)

Die Untersuchung des ersten Bytepaars im Rest deutet schnell darauf hin, dass sie einen weiteren 16-Bit-Integer-Wert enthalten. Wenn wir sie so betrachten, erscheint der Großteil der Werte in Dezimalschreibweise als runde Zahlen:

Der Befehl odverwendet -jstattdessen die , um zum ursprünglichen Versatz zu wechseln -s. Beachten Sie auch den Befehl printf: Zusätzlich zur Formatierung ist es eine bequeme Möglichkeit, Text anzuzeigen, ohne dass am Ende eine neue Zeile hängt.

$ für f in Ebenen / *; printf "% -20s" $ f; Python ./decompress2.py <$ f | od -An -j 0x580 -tuS -N2; erledigt | weniger
Ebenen / all_full.pak 400
Ebenen / alphabet.pak 0
Ebenen / amsterda.pak 500
Ebenen / Apartmen.pak 300
Ebenen / arcticfl.pak 400
Ebenen / Bälle_o_.pak 300
Ebenen / beware_o.pak 300
Ebenen / blink.pak 600
Ebenen / blobdanc.pak 0
Ebenen / blobnet.pak 500
Ebenen / block_fa.pak 500
Ebenen / block_ii.pak 750
Ebenen / block_n_.pak 600
Ebenen / block_ou.pak 350
Ebenen / block.pak 450
Ebenen / bounce_c.pak 300
Ebenen / pinselfir.pak 80
Ebenen / kuchen_wal.pak 999
Ebenen / schloss_m.pak 600
Ebenen / catacomb.pak 399
Ebenen / cellbloc.pak 0
Ebenen / chchchip.pak 300
Ebenen / chiller.pak 399
Ebenen / chipmine.pak 700
Zeilen 1-24 / 148 (mehr)

Wenn wir uns erneut der Liste zuwenden, die ursprünglich aus den Daten erstellt wurde, die wir in den Dateien erwartet hatten, erkennen wir, dass diese Zahl die Zeit ist, um die Ebene abzuschließen (wenn der Wert Null ist, gibt es keine zeitliche Begrenzung für die Ebene).

Nach diesen zwei Bytes werden die Daten flüchtiger. Die Tatsache, dass für die meisten Ebenen noch etwa zehn Bytes in der Datei vorhanden sind, schränkt deren Inhalt erheblich ein:

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

Beispielsweise verbleiben nur neun Bytes auf dieser Ebene. Wir berücksichtigen diese begrenzte Größe sowie die Tatsache, dass diese neun Bytes vier Vorkommen des Wertes enthalten 17, die in zwei Paaren gesammelt werden. Wir werden sofort feststellen, dass das Zahlenmuster 17dem Buchstabenmuster Lim Namen der Stufe „ALL FULL“ entspricht. Der Name ist acht Zeichen lang, daher ist das Nullbyte am Ende höchstwahrscheinlich das Zeilenendezeichen. Nachdem Sie dies entdeckt haben, können Sie sich alle anderen Ebenen trivial ansehen und ihre Namen verwenden, um eine vollständige Liste der Zeichen zu erstellen:

`00`	Zeilenende
`01`	Leertaste
`02` - - `0B`	Ziffern 0-9
`0C` - - `25`	Buchstaben AZ
`26` - - `30`	Satzzeichen

Für die meisten Ebenen endet die Datendatei hier. Ein paar Dutzend des Namens haben jedoch noch Daten. Wenn wir uns die Liste ansehen, werden wir feststellen, dass es Ebenen mit Hinweisschaltflächen gibt, und diese verbleibenden Daten enthalten den Text der Ebenenhinweiszeile, der mit demselben Zeichensatz wie die Ebenennamen codiert ist.

Danach haben wir das Ende aller Dateien erreicht. Jetzt haben wir eine vollständige Beschreibung des Schemas dieser Ebenen. Unsere Aufgabe ist erledigt.

Unvollendete Geschäfte

Ein aufmerksamer Leser kann feststellen, dass wir anfangs erwartet hatten, zwei weitere Elemente in diesen Dateien zu finden, die wir nie getroffen haben. Wir werden das Fehlen von beiden erklären:

Das erste Element ist die Anzahl der Chips, d.h. Die Gesamtzahl der Chips, die ein Spieler sammeln muss, um den Chip-Anschluss zu passieren. Wie wir anfangs sagten, ist es oft gleich der Gesamtzahl der Chips auf einem Level, aber das passiert nicht immer. Daher müssen diese Daten auf irgendeine Weise erhalten werden. Die Antwort kann gefunden werden, indem Karten der Stufen studiert werden, bei denen es zusätzliche Chips gibt. Es stellt sich heraus, dass zwei verschiedene Werte verwendet werden, um Chips anzuzeigen. Der Wert, den 23wir ursprünglich gefunden haben, aber der Wert wird auch verwendet.31bezeichnet einen Chip, der die zum Öffnen des Chipverbinders erforderliche Gesamtmenge nicht beeinflusst. (Aus Sicht des Gameplays sind jedoch beide Arten von Chips gleich. Wenn sich 31auf dem Level ein Chip-Typ befindet , können Sie auf dem Level keine beliebige Anzahl von Chips sammeln.)

Das zweite Element ist das aus vier Buchstaben bestehende Passwort. Es ist nirgendwo in den Leveldaten versteckt. Leider kann dieses Problem nicht durch weitere Untersuchung der Datendatei gelöst werden. Wir müssen zu dem Schluss kommen, dass Passwörter einfach woanders gespeichert werden. Die wahrscheinlichste Erklärung: Sie sind irgendwo im Programm selbst fest codiert. Später wurde jedoch klar, dass Passwörter nicht direkt gespeichert werden. Von Personen, die mit dem Code selbst vertraut sind, habe ich erfahren, dass Passwörter mithilfe eines Pseudozufallszahlengenerators, der mit einer bestimmten Sequenz initialisiert wurde, dynamisch generiert werden. Daher können Kennwörter für Ebenen nicht direkt geändert werden. Dies kann nur durch Ändern des Assembler-Codes erfolgen.

Nachwort

Durch ein vollständiges Reverse Engineering der Daten in den Level-Dateien könnte ich ein Programm schreiben, das Level-Daten codieren und decodieren kann. Dank ihr konnte ich den lang erwarteten Level-Editor für die Version von Chips Challenge for Lynx erstellen , und das Vorhandensein dieses Tools verbesserte meine Fähigkeit, die Logik des Spiels zu studieren, erheblich und verbesserte auch die Qualität seiner Emulation.

Aber ... ich muss zugeben, dass ich persönlich die umgekehrte Entwicklung der Datendateien auf eine Weise durchgeführt habe, die oben nicht beschrieben wurde. Ich habe am anderen Ende angefangen - mit der Definition von String-Daten. Ich begann die Akten der ersten acht Ebenen zu studieren. Da sie von "LEKTION 1" bis "LEKTION 8" aufgerufen werden, habe ich nach Daten identischer Teilzeichenfolgen gesucht. Und ich hatte Glück: Keiner der Namen dieser Ebenen wurde komprimiert, sodass alle acht Namen in ihrer ursprünglichen Form in den Datendateien gespeichert sind. Natürlich war es mir peinlich, dass diese Zeilen nicht in ASCII-Zeichen gespeichert waren, aber das doppelte S im Namen half mir, ein Muster zu erkennen, das sich in allen acht Datendateien wiederholte. Und nachdem ich den Namen gefunden hatte, erkannte ich die Zeichenkodierung von Buchstaben, Zahlen und dem Leerzeichen. Dann habe ich diese Codierung auf den Rest der Datei angewendet, und direkt nach dem Namen sah ich Eingabeaufforderungszeilen und begann, die Anomalien zu beobachten:

Ein großartiges Dienstprogramm trerleichtert das Konvertieren Ihres eigenen Zeichensatzes von Datendateien in ASCII.

$ tr '\ 001- \ 045' '0-9A-Z' <Ebenen / Lektion_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

Im Hilfetext gibt es beispielsweise zwei Stellen, an denen die Folge von S und das Leerzeichen durch die rechte Klammer ersetzt werden. Diese Anomalien gaben mir genügend Beweise, um das Vorhandensein von Kompression deduktiv zu berechnen und einige Informationen über ihre Natur zu erhalten. Später habe ich abnormale Bytewerte mit ihren Vorkommen verknüpft, die näher am Anfang der Datendatei liegen. (In dem oben gezeigten hexadezimalen Offset-Dump 00000035befindet sich beispielsweise eine rechte Klammer, gefolgt von einem Großbuchstaben S und einem Leerzeichen.) Daraus berechnete ich das Komprimierungsschema ähnlich dem im Artikel beschriebenen Prozess. Alles andere war ziemlich einfach.

Es scheint mir, dass man daraus eine Lehre ziehen kann: Es gibt keine eindeutige Möglichkeit, eine unbekannte Datendatei zu untersuchen. Alle Werkzeuge, die zu Ihnen passen, sind die richtigen Werkzeuge für das Reverse Engineering.

Einführung in das Reverse Engineering: Hacking-Spieldatenformat