Relative Suche
aus RHWiki, der freien Romhacking-Enzyklopädie
Eine Relative Suche (engl. auch: Relative Search) wird verwendet, um zu Textzeichen im Spiel die zugehörigen Hexcodes zu finden. Anhand dieser Zuordnungen lässt sich dann eine Table erstellen, die man benötigt, um die Texte im Spiel zu hacken.
| Inhaltsverzeichnis |
Grundkonzept
Man nimmt an, dass jeder Buchstabe, der im Spiel auf dem Bildschirm erscheinen kann, eine Nummer hat. Ziel der Relativen Suche ist es, diese Nummern in Erfahrung zu bringen.
Ferner nimmt man an, dass weil z.B. "A", "B" und "C" im Alphabet direkt aufeinander folgen, auch die Nummern von "A", "B" und "C" direkt aufeinander folgen. Also z.B. "A"=1, "B"=2, "C"=3 usw.
Angewendet auf das ganze Alphabet kann man dann z.B. sagen, dass die Nummer von "V" um 9 größer sein muss, als die Nummer von "M", aber nur um 8 größer als die Nummer von "N" usw.
Für Kleinbuchstaben und Zahlen lässt sich dasselbe Prinzip anwenden. Man muss nur beachten, dass man absolut keine Aussage über den Abstand eines Kleinbuchstabens zu einem Großbuchstaben, oder einer Zahl zu einem Buchstaben treffen kann.
Dieses Wissen wendet man nun an, um im Rom nach Sätzen, die im Spiel auftauchen zu suchen.
Suchprozess
Der Suchvorgang lässt sich am besten an einem Beispiel veranschaulichen:
Beispiel: Im Spiel taucht irgendwo der Satz auf: ..."nicht die Erde verlassen"... Die Abstände jeweils zweier benachbarter Zeichen in dieser Folge sind: 'i'-'n'|'c'-'i'|'h'-'c'|'t'-'h'|'d'-'t'|'i'-'d'| usw. => -5 | -6 | 5 | 12 | -16 | 5 | usw. Wichtig: Man kann jedoch keine Aussage zu 'E'-'e' bzw. 'r'-'E' treffen, wie oben erwähnt.
Nun durchsucht man das ganze Rom byteweise:
- man guckt sich zu jedem Byte den Nachfolger an. Ist die Differenz zweier aufeinanderfolgender Bytes gleich dem Abstand von 'n' zu 'i' im Alphabet (also -5), so wird das nächste Byte genommen und geprüft, ob es zum vorherigen den selben Abstand hat, wie 'i' zu 'c' (-6) usw.
- Trifft man im Suchstring auf Leerezeichen, oder andere Zeichen, die für die Suche nicht relevant sind, werden diese sowohl im Suchstring wie auch im Rom einfach übersprungem so als ob sie nicht vorhanden wären.
Ist dieser Vergleich bis zum Ende des gesuchten Textes erfolgreich, so ist vermutlich der Text gefunden.
Ist der Vergleich nicht erfolgreich, wird mit dem nächsten Byte fortgefahren.
Wäre das Rom z.B.: (zur besseren Übersicht in 4er Gruppen unterteilt) 16EBD71A 6797928C 919D498D 928E496E 9B8D8E49 9F8E9B95 8A9C9C8E 979CDBAC (Hexadezimal)
Dann rechnet man:
EB-16 (hex) = 213 (dez) ungleich -5, also weiter D7-EB (hex) = -20 (dez) ungleich -5 => weiter 1A-D7 (hex) = -189 (dez) ungleich -5 => weiter 67-1A (hex) = 77 (dez) ungleich -5 => weiter 97-67 (hex) = 48 (dez) ungleich -5 => weiter 92-97 (hex) = -5 (dez) ist die gesuchte Differenz "ni", Beginn von Restvergleich: 8C-92 (hex) = -6 (dez) stimmt ebenfalls überein "ic" 91-8C (hex) = 5 (dez) stimmt überein "ch" 9D-91 (hex) = 12 (dez) stimmt überein "ht" > Nun folgt im Suchstring ein Leerzeichen. Daher das nächste Zeichen im String (" ") und im Rom (49 hex) ignoriert. 8D-9D (hex) = -16 (dez) stimmt überein "t d" 92-8D (hex) = 5 (dez) stimmt überein "di" usw.
Man findet, dass die Abstände überall übereinstimmen.
Nach dem obigen Beispiel weiß man, dass 'n'=97 ist, 'i'=92 usw. Daraus lassen sich nun die Nummern für das gesamte Alphabet ableiten:
- 'n' liegt im Alphabet 13 Plätz vor 'a'. demnach ist die Nummer von 'a' = 97 (hex) - 13 (dez) = 8A (hex).
Das ganze Alphabet lässt sich dann einfach auffüllen:
a b c d e f g h i j k l m ... 8A 9B 8C 8D 8E 8F 90 91 92 93 94 95 96 ...
Gleichzeitig hat man herausgefunden, dass 49 (hex) ein Leerzeichen darstellt.
Satz- und Sonderzeichen
Mit der Relativen Suche kann man nur Buchstaben und Zahlen finden, da diese eine feste Ordnung haben. Die Nummern zu allen anderen Zeichen kann man aber dennoch herausfinden, indem man mit einem Table-fähigen Hexeditor, z.B. Thingy sich die Sätze anschaut und über Vergleich mit dem Spiel darauf schließt, was an welcher Stelle für ein Zeichen steht.
Auf diese Weise kommt man auch im obigen Beispiel auf das Leerzeichen.
Wichtige Hinweise
Zeilenumbrüche sind in Texten immer etwas problematisch, da man nie weiß, wie viele Bytes ein Zeilenumbruch verbraucht. Deshalb sollte der Text den man sucht, möglichst in nur einer einzigen Zeile auf dem Bildschirm stehen.
Zahlen funktionieren meistens. Allerdings ist darauf zu achten, keine Geld-Anzeigen oder ähnliches für die Suche zu verwenden, da solche Werte im Spiel variabel sind, und anstelle der Zahl ein sog. Platzhalter im Text sein wird.
Grenzen / Komprimierung
Die Relative Suche funktioniert nur, wenn die Texte im Spiel unkomprimiert sind.
Wird eine Komprimierung verwendet, die ganzen Gruppen von Buchstaben auf einmal eine Zahl zuweist, so gestaltet sich die Relative Suche mindestens als schwierig. Mit Glück kann man aber auch hier noch Gruppen einzelner Buchstaben finden, die groß genug sind, sodass man auf die restlichen Teile rückschließen kann.
Wie solche Komprimierungen funktionieren, wird im Artikel Textkomprimierung näher erläutert.
Programme
Die Relative Suche ist sehr kompliziert. Daher tut man sich das meistens nicht per Hand an, sondern verwendet Tools, die in etwa das genauso machen wie oben beschrieben, nur schneller und zuverlässiger.
Folgende Suchtools sind bekannt:
- Search Relative - DOS-Programm, sehr schnell
- Relativeful Search - Windows, langsam
- Relative Searcher - Windows, Zeichenabstand selbst festlegbar
Siehe The ROM Hacking Repository (http://www.romhack.org/old-site/utils/genutils.php).
