¡Hasta aquí llegó el olor!

("Bis hierher ging der Geruch!" sagt das Spiel, wenn man "flor" ansagt - es reimt sich im Spanischen: flor / olor.)

Am Ende dieses Artikels habe ich den Link hinterlassen, damit du dir den Quellcode des "Kartenspions" ansehen kannst.

Das Truco Arbiser war ein Truco-Spiel, das zwischen Ende der 80'er und den 90ern auf argentinischen Computern kursierte. Man sagt, es sei nach MS-DOS das am meisten raubkopierte Programm gewesen.

Jahrelang habe ich unermüdliche Schlachten gegen den PC geschlagen und wurde bei jeder Partie unermüdlich beschimpft und verspottet. Da es sich um ein Computerspiel handelt, hat meine Schlauheit nie ausgereicht, um zu gewinnen. Aber damit ist jetzt Schluss. In diesem Artikel sehen wir, wie man dem Truco Arbiser ein Truco ansagt (bzw. einen Trick anwendet) und einen weiteren Sieg des Menschen über die Maschine einfährt.

Die Analyse

Um dem Truco Arbiser Tricks anzuwenden, müssen wir zuallererst wissen, womit es programmiert wurde.

 arbiser$ ls
BRUN40.EXE  MWYTRUC@.BAS  SIMCGA.COM  TRUCO.EXE      truco.zip
MVYTRUC@    MXYTRUC@      SIMCGA.DOC  truco.hexdump  VOZ.COM
$ hexdump -C TRUCO.EXE |grep -C5 -i BRUN 
0000da00  3f ac cd 3f af cd 3f b0  cd 3f b7 cd 3f b8 cd 3f  |?..?..?..?..?..?|
0000da10  b9 cd 3f ba cd 3f c7 cd  3f c8 cd 3f c9 cd 3f ca  |..?..?..?..?..?.|
0000da20  cd 3f cf cd 3f d0 cd 3f  d4 cd 3f d5 cd 3f fe cd  |.?..?..?..?..?..|
0000da30  3f ff 00 cd 3f ff 01 cd  3f ff 02 cd 3f ff 06 cd  |?...?...?...?...|
0000da40  3f ff 0f cd 3f ff 10 cd  3f ff 11 cd 3f ff 12 cd  |?...?...?...?...|
0000da50  3f ff 13 cd 3f ff 14 00  3c 00 b1 42 52 55 4e 34  |?...?...<..BRUN4|
0000da60  30 2e 45 58 45 00 50 41  54 48 3d 75 11 00 b2 00  |0.EXE.PATH=u....|
0000da70  82 00 b0 bf e2 0d a1 02  00 2e a3 36 00 2b c7 3d  |...........6.+.=|
0000da80  00 10 72 03 b8 00 10 fa  8e d7 81 c4 9e 4d fb 96  |..r..........M..|
0000da90  9f 2e 88 26 38 00 96 83  e4 fe 03 c7 a3 02 00 8c  |...&8...........|
0000daa0  c3 2b d8 f7 db b4 4a cd  21 36 8c 1e 7d 00 a1 2c  |.+....J.!6..}..,|
--
0000de70  f5 1f 89 36 3f 00 c3 1e  06 1f 81 ff 55 00 74 12  |...6?.......U.t.|
0000de80  8a 45 ff 3c 3a 74 0b 3c  5c 74 07 3c 2f 74 03 b0  |.E.<:t.<\t.</t..|
0000de90  5c aa be 43 00 b9 0b 00  f3 a4 1f ba 55 00 b8 00  |\..C........U...|
0000dea0  3d cd 21 c3 b4 3e cd 21  72 01 c3 e9 be fc 00 45  |=.!..>.!r......E|
0000deb0  72 72 6f 72 20 69 6e 20  6c 6f 61 64 69 6e 67 20  |rror in loading |
0000dec0  42 52 55 4e 34 30 2e 45  58 45 20 52 54 4d 20 2d  |BRUN40.EXE RTM -|
0000ded0  20 24 4d 65 6d 6f 72 79  20 61 6c 6c 6f 63 61 74  | $Memory allocat|
0000dee0  69 6f 6e 20 65 72 72 6f  72 24 43 61 6e 6e 6f 74  |ion error$Cannot|
0000def0  20 66 69 6e 64 20 66 69  6c 65 20 69 6e 20 50 41  | find file in PA|
0000df00  54 48 24 44 69 73 6b 20  49 2f 4f 20 65 72 72 6f  |TH$Disk I/O erro|
0000df10  72 24 49 6e 76 61 6c 69  64 20 66 6f 72 6d 61 74  |r$Invalid format|

Nach einer sehr schnellen Suche und ein paar fabelhaften hexdumps stellen wir fest, dass die Datei BRUN40.EXE, die ebenfalls in dem Verzeichnis liegt, in dem sich das Spiel befindet, vorhanden ist. Diese Datei ist die runtime-Bibliothek von Programmen, die mit QuickBasic kompiliert wurden, einem Compiler für die Programmiersprache BASIC, entwickelt von Microsoft. Die genaue Version dieser runtime ist 4.0. Ab jetzt nenne ich QuickBasic 4.0 einfach QB4.

QB4 besteht aus zwei Sprachprozessoren. Der erste, QB.EXE, stellt eine interaktive Entwicklungsumgebung bereit. Es ist ein inkrementeller Compiler, der den Quellcode in threaded p-code umwandelt und dann den p-code interpretiert ausführt. Der andere, BC.EXE, ist ein Kommandozeilen-Compiler, der native ausführbare Dateien erzeugt.

threaded p-code ist eine Art Virtual Machine. Wie zum Beispiel die JVM. Der als threaded p-code erzeugte Code ist ein byte code als Zwischenschritt, der entweder vom QB4-Interpreter oder von der BRUN40.EXE-Runtime interpretiert wird.

Jeder dieser Compiler hat gewisse Vorteile und sie können je nach Bedarf eingesetzt werden. Der p-code-Interpreter verliert an Ausführungsgeschwindigkeit, gewinnt dafür aber an Kompilier-Geschwindigkeit. Das ermöglichte eine viel schnellere Entwicklung. Denken wir daran, dass das Truco Arbiser in den 80ern entwickelt wurde; ich nehme an, auf einem XT oder höchstens einem 286, angesichts der Art von Computern, die es in jener Zeit gab, und ihrer Preise. Außerdem nehme ich an, dass die Version, die man von der Seite des Truco Arbiser herunterladen kann, die Version von 86 (oder 87)1 ist, wo erwähnt wird, dass sie auf derselben Seite "neu kompiliert" wurde, wegen des Titelbildschirms, und weil ich keine Möglichkeit gefunden habe, die Sprachausgabe zum Laufen zu bringen, obwohl die Datei VOZ.COM im Zip der Seite enthalten ist. Ich sage das, weil auf der Seite des Truco Arbiser erwähnt wird, dass das Sprachmodul 1992 im Auftrag einer Firma entwickelt wurde.

Die Idee war also, sehr schnell mit p-code zu entwickeln und danach den BC-Compiler zu benutzen, um die endgültige ausführbare Datei zu erzeugen, ohne dass der Interpreter beteiligt sein muss.

Aber aber aber, der Nachteil dieser Entwicklungsmethode ist, dass jeder Compiler anderen Code erzeugt. p-code != asm x86. Ein Programm, das im QB4-Interpreter einwandfrei läuft, läuft wunderbar, aber beim Kompilieren zu Maschinencode konnten einige Unterschiede in der Interpretation auftreten, und das "fertige" Programm stürzte ab.

Man sollte bedenken, dass diese Optimierung zwischen Interpreter und "Endkompilierung" notwendig war, weil der iterative Softwareentwicklungsprozess in dieser Zeit so langsam war. Die Ressourcen waren begrenzt und diese Lösungen halfen enorm, die Dauer des Entwicklungszyklus zu verkürzen.

Als Zwischenfazit haben wir also:

  • Die verfügbare Version des Truco Arbiser 5.4 hat ein Copyright von 1986 und wurde mit QB4 kompiliert, also 1987 oder später1. Die ausführbare Datei zeitlich einzuordnen ist wichtig, es hilft uns, die möglichen Versionen der damals verwendeten Compiler für eine spätere Analyse einzugrenzen.
  • Das Vorhandensein von BRUN40.EXE grenzt die Möglichkeiten noch weiter ein. Es hilft mir anzunehmen, dass das Programm mit QB4 kompiliert wurde und zwar nicht als eigenständige ausführbare Datei, sondern dass beim Kompilieren die Option EXE Requiring BRUN40.EXE verwendet wurde.
  • Das Vorhandensein von BRUN40.EXE in der ausführbaren Datei deckt sich mit meinen Beobachtungen.
  • Ein auf diese Weise kompiliertes Programm lässt sich nicht einfach disassemblieren, da eine "VM" dazwischen liegt.

Das Problem

Das Problem besteht nicht nur darin, dass die ausführbare Datei eine runtime braucht, um die byte-codes des kompilierten Programms zu interpretieren, sondern auch darin, dass wir absolut nichts über das Format der ausführbaren Datei wissen, weder wie die Bytes interpretiert werden, noch wie die Informationen in der Datei strukturiert und verteilt sind.

Wir können annehmen, dass am Anfang der Datei ein header steht, der von MSDOS eingelesen wird, dass irgendwo die Strings abgelegt sind und dass irgendwo anders der p-code liegt, falls alles was wir bisher gesagt haben stimmt.

In diesem Artikel übergehe ich mehrere Versuche, das Disassemblierungsproblem aus verschiedenen Blickwinkeln anzugehen. Alle gescheitert, natürlich. Ich habe versucht, das Truco Arbiser mit IDAPro zu disassemblieren, angehängt an einen Debugger, der mit einer speziellen Version von DOSBOX verlinkt war, und das ist nicht nur instabil, sondern alle naslang taucht ein Interrupt des Prozessors auf und unterbricht den Hauptfluss der Programmausführung, was es unverfolgbar macht. Was ich nach langem Debuggen gelernt habe, ist, dass es eine Tabelle von CALLS gibt, die auf NULL zeigen und zur runtime gepatcht werden, während das Programm läuft. Das bedeutet, dass QB4 ausführbare Dateien erzeugt, die sich selbst modifizieren; was das Debuggen enorm viel schwieriger macht.

Ich habe auch versucht, mit dem Turbo Debugger zu debuggen, mit besseren Ergebnissen, aber da er viel Speicher verbraucht (640k ftw!), bin ich auch damit nicht sehr weit gekommen, weil das Programm entweder mit einem out of memory abbrach oder einfach abstürzte und zufällige Zeichen auf dem Bildschirm zeigte.

Wenn ich von "weit kommen" spreche, meine ich, dass ich nach mehreren Iterationen des Parsens von p-code und Patchens von Speicheradressen nie auch nur die Funktion erreicht habe, die den Titelbildschirm des Spiels anzeigt.

Es gibt die Möglichkeit, zwei dosbox-Instanzen über seriell zu verbinden, den Turbo Debugger und das Programm getrennt laufen zu lassen, das Programm irgendwo aus der Ferne zu unterbrechen und von dort aus zu debuggen, aber an diesem Punkt war ich frustriert und als ich Artikel über diese Methode las, hat es mir ziemlich die Laune verdorben, dass sich in den Foren alle beschwerten, diese Art zu debuggen sei so langsam.

Kurzum, der Weg über das Debuggen kostet so viel Zeit, dass er in diesem Fall unpraktikabel ist.2

P-Code-Disassembler

Da kam mir die Idee: Was ist, wenn ich statt zu debuggen einen Disassembler schreibe? 2 Bevor ich ihn schrieb und diesen Weg einschlug, habe ich natürlich im Interwebz gesucht, ob das schon jemand gemacht hatte. Es gibt einige Teillösungen und einen Herrn, der in Großbritannien zwischen 350 und 5000 Pfund Sterling verlangt und einen Disassemblierungsservice anbietet. Zahlen kommt offensichtlich nicht in Frage. Mit diesem neuen Fokus machte ich mich also an die Arbeit.

Die offensichtlichen Dinge

Wir werden in unseren Tests versuchen, Dinge so zu kompilieren, wie die Arbisers es damals vielleicht getan haben. Die Idee dahinter ist zu sehen, wie sich die kompilierte ausführbare Datei auf Binärebene bei kleinen Variationen im BASIC-Programm verhält.

Zuerst schreiben wir also ein ganz einfaches Programm:

Ein 'Hallo Welt' mit einer Variable

Und wir kompilieren es mit dem, was wir darüber gelernt haben, wie die Konfiguration der Arbisers damals gewesen sein könnte, anhand der Informationen, die wir in den vorherigen Abschnitten analysiert haben.

Wir kompilieren so, dass BRUN benötigt wird

Und wir kompilieren eine zweite Version mit diesem Quellcode

Wir kompilieren so, dass BRUN benötigt wird

IEEE 754

Ihr werdet merken, dass die Unterschiede zwischen den beiden BASIC-Programmen sehr klein sind. Nach diesen Änderungen machen wir einen binären Diff der beiden ausführbaren Dateien und vergleichen, was sich zwischen ihnen geändert hat:

 $ diff  <(xxd HOLA1.EXE) <(xxd HOLA2.EXE) 
33c33
< 00000200: 626d 484f 4c41 3120 2020 0000 6218 3018  bmHOLA1   ..b.0.
---
> 00000200: 626d 484f 4c41 3220 2020 0000 6218 3018  bmHOLA2   ..b.0.
162,163c162,163
< 00000a10: b200 6017 b00a 0044 1848 6f6c 6120 4d75  ..`....D.Hola Mu
< 00000a20: 6e64 6f00 007f 4312 00b2 000e 00b0 ffff  ndo...C.........
---
> 00000a10: b200 6017 b00a 0044 1848 4f4c 4120 4d55  ..`....D.HOLA MU
> 00000a20: 4e44 4f00 00fe 4212 00b2 000e 00b0 ffff  NDO...B.........

Abgesehen von der Änderung des Dateinamens sieht man, dass der String anders ist, und bei 0x0a25 ändert sich ein Word, bei dem ich annehme, dass es die Variable mit dem Wert 127 bzw. 255 ist. Das Interessante ist, dass auf den ersten Blick nicht klar ist, wie 255 mit 0x7f43 und 127 mit 0xfe42 dargestellt wird.

Nachdem man diese Zahlen eine Weile angestarrt hat, merkt man leicht, dass es gar keine words sind, sondern doublewords, und dass das Format dieser Zahlen IEEE 754 ist. Ich habe mehrere Zahlen verglichen, die in einer neuen ausführbaren Datei mit folgendem Code erzeugt wurden:

LET variable = 2
LET variable = 3
LET variable = 4
LET variable = 5
LET variable = 6
LET variable = 7
LET variable = 8
LET variable = 9
LET variable = 0
LET variable = -2
LET variable = -3
LET variable = -4
LET variable = -5
LET variable = -6

Unten kannst du die dword-Werte sehen, die durch diese Variablenzuweisungen erzeugt wurden. Du kannst diese dwords selbst mit einem IEEE 754-Rechner vergleichen, wenn du magst:

 $ hexdump -C HOLA5.EXE  |grep -A5 ab0
00000ab0  b2 00 60 17 b0 0a 00 44  18 48 4f 4c 41 20 4d 55  |..`....D.HOLA MU|
00000ac0  4e 44 4f 00 00 00 40 00  00 40 40 00 00 80 40 00  |NDO...@..@@...@.|
00000ad0  00 a0 40 00 00 c0 40 00  00 e0 40 00 00 00 41 00  |..@...@...@...A.|
00000ae0  00 10 41 00 00 00 00 00  00 00 c0 00 00 40 c0 00  |..A..........@..|
00000af0  00 80 c0 00 00 a0 c0 00  00 c0 c0 46 00 b2 00 0a  |...........F....|
00000b00  00 b0 ff ff 01 03 00 b2  00 25 00 b0 4f 00 0f 00  |.........%..O...|

Ein Beispiel: Der Wert -5 in IEEE 754-Darstellung am Offset 0xaf3 ist 0xc0a00000.

All diese Erklärungen setzen voraus, dass wir bereits einen vom Compiler erzeugten Datentyp interpretieren können.

Header erkennen

Alles sehr schön, aber was nützt es zu wissen, wie man ein paar doubles in der Binärdatei interpretiert, wenn wir nicht einmal wissen, in welchem Abschnitt wir sie suchen müssen?

Hier wird es richtig schön, denn schon bei einfacher Betrachtung einer von QB4 erzeugten ausführbaren Datei sehen wir, dass es nicht nur einen, sondern zwei Header gibt. Der erste ist offensichtlich der Header einer .EXE, aber der zweite ist auf den ersten Blick nicht so leicht zu erkennen, auch wenn man ihn mit geübtem Auge sieht, wenn man ihn anstarrt. Ganz lange.

 $ hexdump -C HOLA5.EXE  |grep -A5 HOLA5
00000200  62 6d 48 4f 4c 41 35 20  20 20 00 00 92 18 30 18  |bmHOLA5   ....0.|
00000210  40 18 00 00 00 00 00 00  30 18 00 00 00 00 00 00  |@.......0.......|
00000220  40 18 0a 00 00 00 00 00  00 00 00 00 ff ff 80 00  |@...............|
00000230  b8 40 18 50 9a 52 01 0f  00 cd 35 06 4e 18 cd 35  |.@.P.R....5.N..5|
00000240  1e 36 18 cd 3d cd 35 06  52 18 cd 35 1e 36 18 cd  |.6..=.5.R..5.6..|
00000250  3d cd 35 06 56 18 cd 35  1e 36 18 cd 3d cd 35 06  |=.5.V..5.6..=.5.|

Ich vermute, dass am Offset 0x200 das erste Word eine Art Kennung ist, die folgenden 8 Bytes (verdächtigerweise mit Leerzeichen aufgefüllt) der Dateiname sind, und danach mehrere Bytes mit unbekannten Werten kommen, bis irgendetwas beginnt, das entweder Code oder Daten ist.

/* bm header */
typedef struct {
    char        id[2];             // bm for BRUN modules
    char        module_name[8];    
    uint16_t    sat;           // Statament Address Table
    uint16_t    ds;            // 
    uint16_t    data;          // BC_DATA
    uint16_t    ft;        
    uint16_t    icn;           // base for icn
    uint16_t    inc;           // base for INIT
    uint16_t    dsg;           // base for DATA (runtime DATA)
    uint16_t    com;           // offset for common
    uint16_t    sz_com;        // size for common
    uint16_t    uconst;        // offset for user const
    uint16_t    udata;         // user data
    uint16_t    cn;            
    uint16_t    sz_frame;
    uint16_t    alloc;         // offset heap allocation routine for ISAM
    uint16_t    seg_alloc;     // segment heap allocation routine
    uint16_t    off_dealloc;   // offset heap deallocation routine for ISAM
    uint16_t    seg_dealloc;   // segment heap deallocation routine
    int16_t     c_switch;      // value of /C:n switch, -1 if not given
    uint16_t    u_flag;        // switches specified at compile time

} bm_hdr;

Andere Wege gehen

BC.EXE, der QuickBasic Compiler, hat mehrere Flags, die man beim Kompilieren als Parameter übergeben kann. Einer dieser Parameter ist /a, der zusätzlich zum Kompilieren des Programms auch eine "Auflistung" in einem Assembler erzeugt, der auf halbem Weg zu reinem Maschinencode ist.

Ein Beispiel, das folgende BASIC-Programm, das ich FOR.BAS genannt habe:

n = 0
FOR x = 1 TO 16:
     n = (n + 1) * x
     PRINT "N ahora es:", n
NEXT x

Erzeugt mit dem Flag /a die folgende Datei FOR.LST:

                                                                      PAGE   1
                                                                      24 Feb 22
                                                                      16:25:51
Offset  Data    Source Line     Microsoft (R) QuickBASIC Compiler  Version 4.00

 0030   0006    n = 0
 0030   0006    FOR x = 1 TO 16:
 0030    **            I00002: int   35h
 0032    **                    db    06h
 0033    **                    dw    <00000000>
 0035    **                    int   35h
 0037    **                    db    1Eh
 0038    **                    dw    N!
 003A    **                    int   3Dh
 003C    **                    int   35h
 003E    **                    db    06h
 003F    **                    dw    <0000803F>
 0041    **                    jmp   I00003
 0044   000A         n = (n + 1) * x
 0044   000A         PRINT "N ahora es:", n
 0044   000A    NEXT x
 0044    **            I00004: int   35h
 0046    **                    db    06h
 0047    **                    dw    N!
 0049    **                    int   34h
 004B    **                    db    06h
 004C    **                    dw    <0000803F>
 004E    **                    int   34h
 0050    **                    db    0Eh
 0051    **                    dw    X!
 0053    **                    int   35h
 0055    **                    db    1Eh
 0056    **                    dw    N!
 0058    **                    int   3Dh
 005A    **                    mov   ax,offset <const>
 005D    **                    push  ax
 005E    **                    call  B$PCSD
 0063    **                    push  N!+0002h
 0067    **                    push  N!
 006B    **                    call  B$PER4
 0070    **                    int   35h
 0072    **                    db    06h
 0073    **                    dw    X!
 0075    **                    int   34h
 0077    **                    db    06h
 0078    **                    dw    <0000803F>
 007A    **            I00003: int   35h
 007C    **                    db    1Eh
 007D    **                    dw    X!
 007F    **                    int   3Dh
 0081    **                    int   35h
 0083    **                    db    06h
 0084    **                    dw    <00008041>
 0086    **                    int   35h
 0088    **                    db    06h
 0089    **                    dw    X!
 008B    **                    int   3Dh
 008D    **                    call  B$FCMP
 0092    **                    jna   $-50h

                                                                      PAGE   2
                                                                      24 Feb 22
                                                                      16:25:51
Offset  Data    Source Line     Microsoft (R) QuickBASIC Compiler  Version 4.00

 0094   000E    
 0094   000E         
 0094   000E    
 0094   000E    
 0094    **                    call  B$CENP
 0099   000E    

44108 Bytes Available
43555 Bytes Free

    0 Warning Error(s)
    0 Severe  Error(s)

Und schließlich der relevante Abschnitt der Binärdatei FOR.EXE:

00000200  62 6d 46 4f 52 20 20 20  20 20 00 00 72 18 30 18  |bmFOR     ..r.0.|
00000210  44 18 00 00 00 00 00 00  30 18 00 00 00 00 00 00  |D.......0.......|
00000220  50 18 0a 00 00 00 00 00  00 00 00 00 ff ff 80 00  |P...............|
00000230  cd 35 06 50 18 cd 35 1e  36 18 cd 3d cd 35 06 54  |.5.P..5.6..=.5.T|
00000240  18 e9 36 00 cd 35 06 36  18 cd 34 06 54 18 cd 34  |..6..5.6..4.T..4|
00000250  0e 3a 18 cd 35 1e 36 18  cd 3d b8 58 18 50 9a 40  |.:..5.6..=.X.P.@|
00000260  01 0a 00 ff 36 38 18 ff  36 36 18 9a 4c 01 0a 00  |....68..66..L...|
00000270  cd 35 06 3a 18 cd 34 06  54 18 cd 35 1e 3a 18 cd  |.5.:..4.T..5.:..|
00000280  3d cd 35 06 68 18 cd 35  06 3a 18 cd 3d 9a 34 02  |=.5.h..5.:..=.4.|
00000290  0a 00 76 b0 9a 13 00 0a  00 00 00 00 00 00 00 00  |..v.............|
000002a0  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  |................|

Ab 0x230 sieht man, dass jeder Opcode mit der Auflistung FOR.LST übereinstimmt! Das würde bedeuten, dass es zum Parsen zumindest dieses Abschnitts der Binärdatei (theoretisch) genügen würde, jedes der Tokens der Sprache mit seiner Auflistung und seiner binären Darstellung zu verknüpfen. Eine riesige Tabelle mit allen Kombinationen der Anweisungen der Sprache anlegen, Typen und Ausdrücke identifizieren und langsam versuchen, jede Bytefolge zu etwas zu rekonstruieren, das dem Code des ursprünglichen Programms ähnelt. Manche Dinge lassen sich nicht rekonstruieren, wie die Namen von Variablen - die am Ende nur Verweise auf Offsets sind - oder die Labels, die benutzt wurden, um Namen von Funktionen oder Sprungziele zu definieren.

Wenn das vernünftig ist, könnte man den ursprünglichen Code des Truco Arbiser teilweise rekonstruieren und, sobald wir den Code einigermaßen disassembliert haben, könnten wir ihn analysieren, um danach seine Geheimnisse zu lüften.

Einen Parser schreiben und Tokens interpretieren

Funktionsnamen finden

Wenn wir ein LST erzeugen, gibt uns der Microsoft-Compiler bei jedem call-Opcode die vom Runtime verwendete Bezeichnung zum Beispiel so an:

 [...] (Ausschnitt aus FOR.LST)
 005A    **                    mov   ax,offset <const>
 005D    **                    push  ax
 005E    **                    call  B$PCSD
 0063    **                    push  N!+0002h
 0067    **                    push  N!
 006B    **                    call  B$PER4
 [...]

Wenn wir die Opcodes parsen, schaue ich bei jedem call auf die Adresse, die aufgerufen wird, und vergleiche das LWORD, wobei ich das HWORD verwerfe. Das mache ich auf willkürliche Weise, da es im Moment ziemlich gut funktioniert. Ich weiß noch nicht genau, was HWORD darstellt:

    [...] Ausschnitt aus bm_get_call_mnemonic(char*)

    uint16_t current_lword = (uint16_t)(current_dword & 0xffff);

    switch (current_lword) {
    [...]
        case 0x0140:
            strcpy(&func_name, "B$PCSD - Print a$,");
        break;

        case 0x014c:
            strcpy(&func_name, "B$PER4 - Print R4 (Single precision real (sp))");
        break;
    [...]

Und hier unten zeige ich, wie mein Disassembler die Funktionsnamen erkennt und dabei ein bisschen mehr Informationen anzeigt, die beim Debuggen nützlich sind, während ich ihn programmiere:

0x025a		mov	ax, offset 0x1858
0x025d		push	ax
0x025e		call	B$PCSD - Print a$,	<0x000a0140>
0x0263		push	<0x1838> (modr:0x36)
0x0267		push	<0x1836> (modr:0x36)
0x026b		call	B$PER4 - Print R4 (Single precision real (sp))	<0x000a014c>

Dieser und andere Prozesse sind ziemlich mühsam, denn das Problem ist nicht, die Aufrufe jeder Funktion der Runtime einzeln zuzuordnen, sondern dass ich, um immer mehr Funktionen zu finden, die andere Funktionen aufrufen, iterativ BASIC-Programme schreiben muss, die sich ausreichend voneinander unterscheiden, damit der Compiler jede dieser Funktionen aufruft.

Das bedeutet: Je mehr Programme ich schreibe, desto mehr Funktionen finde ich dank des vom Compiler erzeugten LST, aber gleichzeitig muss ich immer kreativer mit der "Funktionalität" der Programme sein, damit mir der Compiler die Funktionsaufrufe zeigt.

Das kostet enorm viel Zeit. Da das Ziel ist, dem Truco Arbiser Truco anzusagen, versuche ich nicht, ALLES zu mappen, was der Compiler von QuickBasic 4.0 ausgibt, sondern eher Dinge zu programmieren, die - mit etwas Raten - die Arbisers beim Programmieren des Spiels gebraucht haben könnten.

Gleitkomma-Emulation

Ah! Das ist ziemlich schwierig und stellte mich vor eine Herausforderung, als ich versuchte, die "Gleitkomma"-Opcodes zu verstehen und zu parsen.

Ich setze es in Anführungszeichen, weil QB4 in Wahrheit nicht genau FPU-Opcodes verwendet, sondern eine Art Emulation, die wie folgt definiert ist:

INT 34 - FLOATING POINT EMULATION - OPCODE D8h
INT 35 - FLOATING POINT EMULATION - OPCODE D9h
INT 36 - FLOATING POINT EMULATION - OPCODE DAh
INT 37 - FLOATING POINT EMULATION - OPCODE DBh
INT 38 - FLOATING POINT EMULATION - OPCODE DCh
INT 39 - FLOATING POINT EMULATION - OPCODE DDh
INT 3A - FLOATING POINT EMULATION - OPCODE DEh
INT 3B - FLOATING POINT EMULATION - OPCODE DFh
INT 3C - FLOATING POINT EMULATION - SEGMENT OVERRIDE
INT 3D - FLOATING POINT EMULATION - STANDALONE FWAIT
INT 3E - FLOATING POINT EMULATION - Borland "SHORTCUT" CALL

Ergibt Sinn. Damals war eine FPU optional: Man konnte in seinen Computer eine FPU einbauen oder nicht und alle Gleitkomma-Operationen gingen dann den Bach runter, oder man konnte sich dafür entscheiden, diese Operationen nur mit der CPU zu emulieren, was die Berechnungen erheblich langsamer machte.

Bis ich zu dieser Liste kam und wusste, wofür ich sie brauchte, verging ziemlich viel Zeit. Schauen wir uns das folgende Stück Disassembly an:


BASIC:
LET variable = 2
LET variable = 3
LET variable = 4
LET variable = 5

QuickBasic .LST:
 0039    **                    int   35h
 003B    **                    db    06h
 003C    **                    dw    <00000040>
 003E    **                    int   35h
 0040    **                    db    1Eh
 0041    **                    dw    VARIABLE!
 0043    **                    int   3Dh
 0045    **                    int   35h
 0047    **                    db    06h
 0048    **                    dw    <00004040>
 004A    **                    int   35h
 004C    **                    db    1Eh
 004D    **                    dw    VARIABLE!
 004F    **                    int   3Dh
 0051    **                    int   35h
 0053    **                    db    06h
 0054    **                    dw    <00008040>

Es gibt also eine Beziehung zwischen den INTerrupts, den dbs und den dws, die in der Binärdatei Offsets waren, und den LST-Nummern des Compilers. Offensichtlich wurden die ganzen Zahlen des Originalprogramms auf besondere Weise kodiert, bis es mir irgendwann dämmert und ich sage: Natürlich! IEEE754! 3

Nach und nach beginnen die Teile des Puzzles Form und Sinn anzunehmen. Das Problem ist, dass es unglaublich viele Teile gibt und man sich leicht zwischen so vielen Bytes und losen Daten verliert, wenn man versucht, ihnen einen Sinn zu geben.

Offsets und Blöcke

Wie sind die Abschnitte des Moduls der ausführbaren Datei organisiert? Wie berechne ich, wo all die Dinge liegen, auf die die Binärdatei verweist? An welchem genauen Offset werden die Variablen, die Konstanten, die Strings usw. gespeichert?

Keine Ahnung, noch nicht :D

B$<funcname>

Plötzlich erfahre ich, dass es einen Leak von msdos 6.0 gab, und damit konnte ich einige der wichtigsten Teile dieses Puzzles vervollständigen. Es stellt sich heraus, dass es im Verzeichnis 45/runtime/rt jede Menge Definitionen von runtime-Aufrufen gibt, aus denen ich einen Teil der Dokumentation übernehmen, den Offset der Runtime finden und für jeden Aufruf den Namen der Funktion und eine kurze Beschreibung ihrer Aufgabe ausgeben kann:

    [...]
        case 0x0185: 
            strcpy(&func_name, "B$SASS - String assignment");
        break;

        case 0x00f5: 
            strcpy(&func_name, "B$INPP -- console input preamble");
        break;

        case 0x0170:
            strcpy(&func_name, "B$RDSD -- console input read String Descriptor");
        break; 
    [...]

Das Vorgehen ist:

  • Ein BASIC-Programm kompilieren
  • BC.EXE bitten, uns ein .LST zu erzeugen
  • Die calls zur Runtime nehmen und die Definition im Quellcode von msdos6.0 nachschlagen
  • Die Doku lesen und die Definition des Call-Offsets in meinem Disassembler hinterlegen (den ich mit dem Schlüsselwort unknown markiere, falls ich ihn nicht geparst habe)

Diese Schritte kosten unglaublich viel Zeit, und im Juni (2022) war ich an diesem Punkt der Entwicklung schon seit mehreren Monaten dabei, nur das in meiner Freizeit zu tun. Und ich begann zu denken, dass der Weg nicht hierüber führt.

Eine unerwartete Wendung

Diese Arbeitsweise ist ziemlich puristisch, und manchmal habe ich beim Programmieren viel Spaß, und Dinge zu tun, die schwer genug sind, wie ein Disassembler von Grund auf mit C und den Intel-Handbüchern, macht fantastisch viel Spaß, aber der Fortschritt des Projekts wird viel zu langsam. Eine Zeit lang, bis hierher (ungefähr ein paar Monate), baute ich meinen eigenen Disassembler, und die Aufgabe wurde schließlich, den Disassembler zu schreiben, anstatt zu versuchen, die ausführbare Datei mit einem Werkzeug zu disassemblieren, das das viel besser kann, als wenn ich es selbst schreibe.

Irgendwann wurde die Arbeit, einen Disassembler von Grund auf zu schreiben, lächerlich mühsam und verschlang zu viel Zeit. Deshalb beschloss ich, den Kurs des Projekts komplett zu ändern und eine Disassemblierungs-Engine zu verwenden, um das Mapping der Funktionsaufrufe auf die QB-Runtime so weit wie möglich zu automatisieren.

Ich entschied mich, auf die Capstone Engine zu setzen und den Vergleich von segment:offset jedes CALL mit den Listings, die der QB4-Compiler ausspuckt, zu automatisieren und sie mit meinem Disassembler abzugleichen.

Im Wesentlichen:

  • Offsets mit lcall/call-Paaren interpretieren und vergleichen und dabei die Strings der Funktionsaufrufe aktualisieren.
  • Eine Tabelle der Funktionen aufbauen, die ich bereits entdeckt habe
  • rinse and repeat ad infinitum

All diese Mühe trug gewisse Früchte. Ich konnte irgendwie Teile von Programmen disassemblieren, die mit Quick Basic 4.0 kompiliert wurden, unter Verwendung seiner runtime, und irgendwann würde ich einen Señor Disassembler haben, der in Zukunft nützlich sein könnte, um alte Programme zu disassemblieren, à là HexRays.

Irgendwie ist es so, dass man nie etwas fertigstellt, oder? Die Reise ist es, was unterhält, und auf dieser Reise habe ich unglaublich viel gelernt. Das Endziel war, Truco auf das Truco anzuwenden (Truquear al Truco), und ich bin darin abgeschweift, eine ganze P-Code-Disassemblierungs-Suite zu bauen.

Im Jahr darauf (2023), als ich etwas Brauchbares hatte, entwischte mir das Arbiser wieder und ich konnte der CPU immer noch nicht in die Karten schauen, was das Hauptziel war. Als ich das verstanden hatte, fing ich wieder mit IDA an und mit dem Reversen, dort, wo ich ursprünglich angefangen hatte.

Dieser Weg würde mich schließlich dazu bringen, es zu knacken, und der Weg führte hierüber.

Analyse von Strukturen im Speicher

Das Thema mit den Interrupts, das mich so schnell das Handtuch werfen ließ, war nur eine Frage der Ungeduld. Ich weiß nicht mehr, wie ich es gelöst habe, aber wenn es keine Einstellung war, lag ich verdammt nah dran. Was ich anfing zu tun, waren nur Lese- und Schreib-Breakpoints, getrennt voneinander. Zusätzlich führte ich eine Liste interessanter Speicheradressen oder von Stellen, an denen relevant aussehende Funktionen beginnen.

Ein Jahr später mache ich mich also ans Reversen und komme zu einer ordentlichen Tabelle, um einige lohnenswerte Breakpoints zu setzen:

segment:offset Speicher segment:offset disassembliert Länge Beschreibung
seg004:fa94 [si+1c72] WORD*6 + 1 Spieler-Words, Farbe 1 Farbe 2 Farbe 3 – nichts – Karte 1, 2, 3
seg004:f66a [si+1848] WORD*6 + 1 Computer-Words, Farbe 1 Farbe 2 Farbe 3 – nichts - Karte 1, 2, 3
seg004:f680 [si+1860] WORD*3 Platzhalter/Speicherbereich für Zufallszahlen
seg004:fae4 ds:1cc4 WORD Zufallszahl
seg004:fb90 ds:1d70 WORD current_card, die für den Spieler berechnet wird
seg004:fb92 ds:1d72 WORD current_card, die für den Computer berechnet wird
seg004:fb02 ds:1ce2h WORD zuletzt verarbeitete Kartennummer (Spieler)
seg004:fb04 ??? DWORD ???????????????????????????
seg004:fb06 ??? DWORD ???????????????????????????
seg004:fb08 ??? DWORD ???????????????????????????
seg004:fb0a ??? WORD zuletzt verarbeitete Farbe (Spieler)
seg005:12d3 ds:2836-ds:283a WORD STACK! BP/SP in seg005, ist die Zahl, die AX für viele Operationen im Zusammenhang mit den Zufallsfunktionen erhält
021e:e6fb ds:8db WORD Low WORD des vorherigen PRNG-Seeds
021e:e6fd ds:8dd WORD Hi WORD des vorherigen PRNG-Seeds
???? 021e:e020 WORD A Konstante QB4.0 PRNG
???? 021e:e024 BYTE C Konstante QB4.0 PRNG
???? 021e:de20 DWORD Gleitkomma-Speicherbereich?

Farben (Palos):

Farbe EQU
Espada (Schwerter) 0x0000
Basto (Stäbe) 0x0001
Oro (Münzen) 0x0002
Copa (Kelche) 0x0003

Ich habe außerdem einige wichtige Details im Binärcode und seinen Datenstrukturen entdeckt:

  • die Kartenwerte reichen von 0x0001 bis 0x000A (1 bis 10, 1234567,10,11,12 sind 10 verschiedene Kartennummern)
  • wenn die ausgewählte Karte größer als 7 ist, addieren wir 2, um so zu korrigieren, wie sie tatsächlich aussehen müssen.
  • es gibt einen Speicherbereich, in dem die Karten des Spielers und der CPU liegen, und alle Lesezugriffe dienen tendenziell dazu, sie auf dem Bildschirm zu zeichnen, die Schreibzugriffe stammen vom Algorithmus zum Austeilen der Karten

Super, ungefähr zu wissen, was was bedeutet! Die Knobelei ist jetzt zu verstehen, wie diese Werte berechnet werden und woher sie kommen. Wenn wir das wissen, könnten wir das Verhalten mit einem Python-Skript nachbilden.

Pseudo Random Number Generator (PRNG)

Es stellt sich heraus, dass ich Stunden damit verbracht habe, diesen Codeabschnitt zu reversen, der versuchte, die nächste Zufallszahl des Pseudo Random Number Generators oder PRNG zu erzeugen:


.text:98CB7 ; ---------------------------------------------------------------------------
.text:98CB7 push    di
.text:98CB8 mov     ax, ds:8DBh
.text:98CBB mov     cx, word_200
.text:98CBF mul     cx                              ; Unsigned Multiplication of AL or AX
.text:98CC1 xchg    ax, di                          ; Exchange Register/Memory with Register
.text:98CC2 mov     bx, dx
.text:98CC4 mov     ax, ds:8DDh
.text:98CC7 mul     cx                              ; Unsigned Multiplication of AL or AX
.text:98CC9 add     bx, ax                          ; Add
.text:98CCB mov     ax, word_200
.text:98CCE mul     word ptr ds:8DBh                ; Unsigned Multiplication of AL or AX
.text:98CD2 add     bx, ax                          ; Add
.text:98CD4 add     di, word_204                    ; Add
.text:98CD8 adc     bl, byte ptr word_204           ; Add with Carry
.text:98CDC xor     bh, bh                          ; Logical Exclusive OR
.text:98CDE mov     dx, di
.text:98CE0 mov     ds:8DBh, dx
.text:98CE4 mov     ds:8DDh, bx
.text:98CE8 pop     di
.text:98CE9 nop                                     ; No Operation
.text:98CEA fild    dword ptr ds:8DBh               ; Load Integer
.text:98CEE nop                                     ; No Operation
.text:98CEF fdiv    flt_208                         ; Divide Real
.text:98CF3 mov     bx, 0EDh ; 'f'
.text:98CF6 nop                                     ; No Operation
.text:98CF7 fstp    dword ptr [bx]                  ; Store Real and Pop
.text:98CF9 xchg    ax, bx                          ; Exchange Register/Memory with Register
.text:98CFA nop                                     ; No Operation
.text:98CFB wait                                    ; Wait until BUSY# Pin is Inactive (HIGH)
.text:98CFC retn                                    ; Return Near from Procedure
.text:98CFC ; ---------------------------------------------------------------------------

Da dieser Codeabschnitt in .text liegt, nahm ich an, es sei ein von den Arbisers geschriebener Algorithmus und nicht Teil von BRUN40.EXE. Es hätte gereicht zu bemerken, dass wir in einem anderen Segment waren, wenn man sich den Offset von .text ansah, und fertig, aber neeeein. Erinnert ihr euch, dass der MSDOS-Quellcode geleakt wurde? Nun, manchmal kann man mit Tunnelblick vergessen, dass man andere Blickwinkel hat, um dasselbe Problem anzugehen. Im Leak finde ich Folgendes:

; 45 > runtime > rt > random.asm:240
;***
;GetNextRnd -- get next random number
;MakeFloat -- make the number in [b$RndVar] into a R4
;
;Purpose:
;	Get next random number in sequence.
;Entry:
;	[b$RndVar] has the seed.
;Exit:
;	[AX]	= *B$AC which contains the R4 result
;Exceptions:
;	none
;*******************************************************************************

cProc	GetNextRnd,<NEAR>	

cBegin				
	PUSH	DI		
	MOV	AX,[WORD PTR b$RndVar]	 ;low half of previous number
	MOV	CX,[RndA]	;low half of A
	MUL	CX
	XCHG	AX,DI		;save low half in DI
	MOV	BX,DX		;  high half in BX
	MOV	AX,[WORD PTR b$RndVar+2] ;high half of previous
	MUL	CX
	ADD	BX,AX		;sum partial products
	MOV	AX,[RndA]
	MUL	[WORD PTR b$RndVar]	 
	ADD	BX,AX		;last partial product (since we're mod 2^24)
	ADD	DI,[RndC]	;add in constant C
	ADC	BL,BYTE PTR [RndC]
	XOR	BH,BH		;extended 24-bit number to 32 bits for NORM
	MOV	DX,DI		;number in BX:DX
	MOV	[WORD PTR b$RndVar],DX	 ;save for next time
	MOV	[WORD PTR b$RndVar+2],BX 
	POP	DI		
MakeFloat:			

	FILD	b$RndVar	; put 24-bit integer on numeric stack
	FDIV	FP_2T24 	; ST0 = seed/2^24
	MOV	BX,OFFSET DGROUP:B$AC 
	FSTP	DWORD PTR [BX]	; put s.p. equivalent into FAC
	XCHG	AX,BX		; result is *R4 in AX
	FWAIT			; ensure result in RAM prior to return

cEnd				; exit to caller

Das ist derselbe Codeabschnitt! Und es ist genau der PRNG. Ich habe nicht genau nachgesehen, warum dieser Teil der Runtime in .text lag, denn ich nahm direkt an, dass es nicht innerhalb desselben Segments sprang, sondern dass das Modul von TRUCO.EXE in einem Segment und BRUN40.EXE in einem anderen lag.

Die Feier dauerte nicht lange. Nachdem ich den PRNG lokalisiert hatte, ließ ich ein kleines Programm in QB4 und seine ausführbare Datei laufen, in beiden ohne RANDOMIZE, um in allen Läufen denselben Seed-Wert zu haben.

print rnd
print rnd
print rnd
print rnd
print rnd

Die Ergebnisse des QB4-Interpreters und der vom Compiler erzeugten ausführbaren Dateien waren VERSCHIEDEN. Das Warum würde einen weiteren Artikel erfordern, also habe ich, als ich diesen Unterschied sah, beschlossen, nur mit den kompilierten ausführbaren Dateien zu arbeiten und keinem Ergebnis des QB-Interpreters zu vertrauen.

rnd ist die ausführbare Datei - der zweite Lauf stammt aus dem Interpreter

Nach einer langen Pause habe ich in C eine Bibliothek implementiert, um mit CTypes in Python auf den LCG von QB4 zugreifen zu können. Die Idee, diesen Abschnitt von QB4 getrennt zu haben, war, andere Sprachen für Experimente nutzen zu können und gut zu verstehen, welche Eigenschaften dieser PRNG haben könnte. Die Idee war, Python statt Quick Basic zu benutzen, um Ideen und Eigenschaften dieses speziellen LCG herauszuarbeiten.

RND in RND.EXE und in meiner ImplementierungDie Ausgabe unter MSDOS und in meiner Implementierung in C

Eine Randbemerkung: Den PRNG hatte ich von Hand gereversed, und die Bestätigung durch den Screenshot oben kam, bevor ich Zugang zum MSDOS-6.0-Leak hatte. Es stellt sich heraus, dass die Formel, die sie zum Randomisieren von Werten benutzten, als Kommentar im Header der Datei stand. Ich war glücklich, weil ich meine Implementierung auf verschiedene Weisen bestätigen konnte und wusste, dass sie perfekt war.

Teilweise Vorhersage

Da ich den PRNG nun mehr oder weniger zum Laufen hatte, versuchte ich, den Seed zu finden. Mein Vorgehen war eine Zeit lang, nachdem ich identifiziert hatte, wo der Seed des PRNG geschrieben wurde, bei jeder Hand den Wert des Seeds im Speicher von Hand zu prüfen und ein Python-Skript laufen zu lassen, um die Hand der CPU zu berechnen.

Das Interessante ist, dass es hervorragend funktionierte und ich mir vor lauter Vorfreude fast in die Hose veröffentlicht hätte, aber nach ein oder zwei Händen verlor ich irgendwie die "Synchronisierung" mit dem Seed: Manchmal entschied das Programm, ein Lied zu spielen, einen Text zu schreiben oder gar nichts zu tun, und das ließ die Aufrufe des LCG fortschreiten. Ich verbrachte unglaublich viel Zeit damit, in jedem Fall zu debuggen oder zu versuchen zu debuggen, wie oft zum nächsten PRNG-Wert weitergeschaltet wurde, und wer schon einmal versucht hat, auf Intel 16 Bit zu debuggen, weiß, wie schwierig es manchmal ist, dem Code bei so vielen Segmentwechseln zu folgen. Puh.

Ich konnte ihr also schon teilweise die Karten lesen, aber manchmal "desynchronisierte" ich mich, und jedes Mal, wenn ich es debuggend nachverfolgte, steckte ich unglaublich viele Stunden hinein, ohne zu einem ausreichend starken Schluss zu kommen, ich konnte nicht herausfinden, wie stark die Anzahl der Aufrufe der Funktion get_random variierte, und ich ließ es für eine Weile liegen, bis…

Aber wozu zum Teufel hast du dann einen PC?

Als ich das Problem des Truco Arbiser mit ein paar Freunden diskutierte und ihnen von meiner Frustration mit dem Debugging erzählte, zeigte ich ihnen diesen Codeabschnitt des LCG:

/*
# According to Microsoft, this is the linear congruential method for prng
# x1 = (x0 * a + c ) mod 2 ^ 24
#
# where
#
# x1 = new random number from [0 to 2^24]
# x0 = previous number (or seed, for the first one)
# a = 214013
# c = 2531011
# the random number returns a float 
# x1 / 2^24

*/
float ms_rnd_formula(uint32_t *prev_rnd) {

    // a and c constant values are found at 021e:e020 as 
    // FD 43 03 00 => A 
    // C3 9E 26 00 => C
    uint32_t a = 214013; // 0x343fd
    uint32_t c = 2531011; // 0x269ec3
    float x1;
    uint32_t p;

    p = pow(2,24);
    x1 = ((*prev_rnd * a) + c) % p;

    *prev_rnd = x1;
    return x1 / p;
}

Worauf mich jemand fragt:

– Warum berechnest du nicht vor, alle Zufallszahlen auf einmal, statt dich mit dem Seed irgendwo zu positionieren und mehrere Schritte vorauszuschauen, ob die Karten deiner eigenen Hand in der nächsten Hand sind oder nicht?

– Weil das 2^24 Elemente sind, die ich berechnen müsste, also ~16 Millionen Möglichkeiten, und das ist eine Menge Rechnerei und Speicher… für eine Maschine aus den 80'ern!

Mulero

Mulero TUIDie Textoberfläche von Mulero

Immer wieder im LCG-Zyklus herumdrehen

Der LCG von QB4 hat, wie wir immer wieder sagen, die Form:

estado = (estado * A + C) mod 2^24
RND    = estado / 2^24

Die effektiven Konstanten sind A = 0xfd43fd und C = 0xc39ec3. Die Kommentare von Microsoft sagen etwas anderes, weil die Runtime die untere Hälfte jeder Konstante lädt, wo sie die obere laden sollte. Die Details stehen in der README des Repositorys.

Beim Durchsehen von Mustern von Zufallszahlengeneratoren und ihren Problemen stieß ich unter anderem auf den Satz von Hull-Dobell, der besagt, dass ein LCG mit Modulus m alle seine m Zustände durchläuft, bevor er sich wiederholt, genau dann wenn:

  1. C und m teilerfremd sind.
  2. A - 1 durch alle Primzahlen teilbar ist, die m teilen.
  3. A - 1 durch 4 teilbar ist, wenn m es ist.

Hier ist m = 2^24, also ist die einzige Primzahl die 2 und die Bedingungen reduzieren sich auf C ungerade und A ≡ 1 (mod 4). Die Konstanten erfüllen beide: 0xc3 ist ungerade und 0xfd = 253 = 4*63 + 1.

Das bedeutet, dass die 16.777.216 Zustände einen einzigen Kreis bilden. Jeder Zustand nimmt eine Position ein, und den Generator laufen zu lassen heißt, auf diesem Kreis zu wandern. Die "nächste Hand" ist die aktuelle Position plus eine gewisse Anzahl von Schritten, nämlich die, die das Austeilen verbraucht hat, plus die, die Gedichte, Beschimpfungen und Lieder verbraucht haben.

Zur Zeit des Debuggens war es, glaube ich, dieses "Fenster" von Aktionen (die Auswahl von Gedichten, Beeper-Liedern und Beschimpfungen), das mir die Position, an der ich mich befand, desynchronisierte, und alle Fälle zu debuggen, abhängig von einer Zufallszahl, die eine beliebige Anzahl von Aufrufen der Funktionen auslöst, die weitere Zufallszahlen holen, wurde sehr mühsam. Diese andere Lösung, die ich vorschlage, erspart mir direkt, die "Anzahl" der Aufrufe von RND zu berechnen.

Nur drei Hände, Jung3!

Der Zustand hat 24 Bit Unsicherheit. Drei verschiedene Karten aus 40 zu sehen liefert dir log2(40*39*38) ≈ 15,9 Bit an Information, das heißt, es nimmt dem Zustand 15,9 Bit Entropie (Unsicherheit)4. Eine einzelne Hand reicht nicht: Es gibt 2^24 / (40*39*38) ≈ 283 kompatible Positionen. Mit einer Hand gewinnst du ~15,9 Bit. Die folgenden Hände tragen deutlich weniger bei, weil uns das Fenster WINDOW schon ungefähr sagt, wo sie landen, und deshalb reichen uns 3 Hände.

Um die Hände zu verbinden, benutzen wir ein Fenster. Die neue Hand muss höchstens WINDOW = 1000 Schritte von dem Punkt entfernt beginnen, an dem die vorherige endete. Ein falscher Kandidat hat eine Wahrscheinlichkeit von 283 * 1000 / 2^24 ≈ 1,7 %, das zufällig zu erfüllen. Bei der dritten Hand überlebt fast kein falscher Kandidat mehr. Die Wahrscheinlichkeit ist gering, aber nicht null. Ab und zu kann es beim Benutzen von Mulero passieren, dass du gerade spielst und plötzlich mehrere Hände in diesem Fenster liegen, die die Bedingungen erfüllen; in diesem Fall merkt Mulero das und sagt dir, dass es in diesem Moment der Partie keine 100%ige Gewissheit gibt, und es genügt, ein oder zwei weitere Hände zu spielen, um sich "neu zu zertifizieren" (?).

numpy

Dafür brauchen wir eine Tabelle mit 16 Millionen Einträgen und einer Menge Vergleiche. In reinem Python kostet jeder Durchlauf eines for etwas Interpreter-Zeit (Typen prüfen, int-Objekte von ~28 Bytes erzeugen), was alles etwas langsam macht. In NumPy liegen die Daten in einem zusammenhängenden Speicherblock mit festem Typ (uint8 belegt 1 Byte) und die for-Schleifen laufen in C statt in Python. a * x + c auf ein Array zu schreiben bedeutet, das for auszuführen, ohne es zu schreiben. Das nennt man Vektorisieren.

valor = ciclos[a * x + c]       # alles ist bereits vorberechnet

Den Kreis vorberechnen

Das Problem ist, dass jeder Zustand vom vorherigen abhängt, also scheint er nicht vektorisierbar zu sein. Der Ausweg ist der Sprung nach vorn (jump-ahead). Ein Schritt des LCG ist eine lineare Funktion f(x) = A*x + C. Die Verkettung zweier linearer Funktionen ergibt wieder eine lineare Funktion:

A*(a*x + c) + C = (A*a)*x + (A*c + C)

So können wir berechnen, was 4096 Schritte auf einmal vorrückt:

ak, ck = 1, 0
for _ in range(4096):
    ak = (ak * A) & MASK
    ck = (ck * A + C) & MASK
# jetzt: estado[n + 4096] = ak * estado[n] + ck

Den ersten Block von 4096 Zuständen berechnen wir von Hand. Jeder folgende Block entsteht aus dem vorherigen mit einer einzigen Operation auf einem Array:

state[b*4096:(b+1)*4096] = (state[(b-1)*4096:b*4096] * ak + ck) & MASK

Das sind 4096 Python-Durchläufe plus 4096 vektorisierte Operationen, statt 16 Millionen Durchläufen.

In diesen Zeilen stecken mehrere NumPy-Details:

  • & MASK statt % N: Da N eine Zweierpotenz ist, ist x mod 2^24 gleich x & (2^24 - 1). Das ist schneller und funktioniert nur mit Zweierpotenzen.
  • dtype=np.uint64: estado * A erreicht ~2^48 und würde eine 32-Bit-Ganzzahl überlaufen lassen.
  • state[a:b] ist eine View, keine Kopie. Etwas zuzuweisen schreibt in das ursprüngliche Array.
  • np.empty reserviert Speicher ohne ihn zu initialisieren, weil wir ihn komplett füllen werden.

Vom Zustand zur Karte

Truco ist ein Spiel mit 40 Karten im Stapel. Die Reihenfolge, in der ich das Array geschrieben und zusammengesetzt habe, um herauszufinden, wie TRUCO.EXE es macht, ergibt sich daraus, wie die Kartenauswahl im Programm berechnet wird und in welcher Reihenfolge sie im Speicher erscheint.

https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L35:

# card stuff
# cards goes from 0..39 with suit*10 + index, where suit is 0..3 and index is 0..9
SUITS = "eboc" # suits are: e=espada, b=basto, o=oro, c=copa
SUITS_NAMES = ["espada", "basto", "oro", "copa"]
NUMBERS = [1, 2, 3, 4, 5, 6, 7, 10, 11, 12]

Wenn ihr euch die Funktion lcg_table() anseht: INT(RND * 40) ist floor(40 * estado / 2^24). Durch 2^24 zu teilen und abzuschneiden bedeutet, 24 Bit nach rechts zu schieben, sodass (state * 40) >> 24 übrig bleibt, ein Wert von 0 bis 39. Da RND zuerst den Zustand weiterschaltet und dann zurückgibt, stammt die Karte an Position p aus dem Zustand p+1. Das löst np.roll(cartas, -1), das das Array zyklisch verschiebt (das Ende ist mit dem Anfang verbunden, genau das, was ein Kreis braucht).

Das Ergebnis ist CARDS, ein 16-MB-Array, bei dem CARDS[p] die Karte ist, die an Position p ausgeteilt würde.

Die Hand suchen

start = np.flatnonzero(CARDS == mi_primera_carta)

CARDS == x erzeugt ein Array mit 16 Millionen Booleans und flatnonzero gibt die Indizes zurück, an denen True steht. Mit einer einzigen Zeile bleibt 1/40 der Positionen übrig, etwa 419 Tausend.

Danach simuliert deal() das Austeilen für alle diese Kandidaten parallel. Da das Spiel erneut zieht, wenn eine bereits vorhandene Karte herauskommt, braucht jeder Kandidat eine andere Anzahl von Ziehungen. Das wird mit einer Liste pend derjenigen gelöst, die noch eine Karte brauchen:

c = CARDS[pos[pend] & MASK]                          # fancy indexing: viele Elemente auf einmal herausholen
repeated = (hand[pend, :k] == c[:, None]).any(axis=1)
  • Fancy indexing: ein Array mit einem anderen Array von Indizes indizieren.
  • Broadcasting: hand[pend, :k] hat die Form (n, k) und c[:, None] die Form (n, 1). NumPy "streckt" die Spalte und vergleicht jede neue Karte mit den k bereits ausgeteilten.
  • .any(axis=1) faltet die Spalten zusammen und beantwortet für jede Zeile "Hat sich irgendeine wiederholt?".
  • ~repeated ist die bitweise Negation. Bei Arrays kann man nicht not benutzen.

Nach jeder der ersten drei Karten werden die Kandidaten verworfen, die nicht zu deiner Hand passen (start = start[ok], eine boolesche Maske). Von 419 Tausend kommt man auf etwa ~283, und die Karten der CPU werden nur für diese simuliert.

Hände verketten

gap = (start[:, None] - prev_end[None, :]) & MASK
ok  = (gap <= WINDOW).any(axis=1)

Wenn man einen Spaltenvektor (n, 1) und einen Zeilenvektor (1, m) subtrahiert, erhält man eine (n, m)-Matrix mit allen paarweisen Differenzen, ganz ohne for. Das & MASK auf negativen Zahlen liefert den korrekten Modulo (die zirkuläre Distanz). Das .any(axis=1) fragt, ob dieser Kandidat weniger als WINDOW Schritte von irgendeinem Ende der vorherigen Hand entfernt liegt.

Schließlich sortiert np.sort(cpu, axis=1) die Karten jeder Kandidatenhand, sodass {3, 7, 9} und {9, 3, 7} als dieselbe zählen, und np.unique(axis=0, return_counts=True) gruppiert die gleichen Zeilen und zählt, wie oft jede vorkommt. Wenn nur noch eine mögliche Hand übrig bleibt, weißt du schon, was die CPU hat.

Jetzt lade dir Mulero herunter und schlag es endlich!

Quellcode

Mulero in AktionMulero in Aktion

Den Quellcode von Mulero kannst du aus dem Codeberg-Repository herunterladen: https://codeberg.org/toshi/mulero

Referenzen

Fußnoten

  1. Damals schrieb ich "wurde 1986 kompiliert", weil der Copyright-Vermerk im Spiel ebenfalls 1986 nennt, aber Quick Basic 4.0 wurde 1987 veröffentlicht! ↩ ↩2

  2. Das habe ich allerdings etwa vier Jahre vor der Veröffentlichung dieses Artikels geschrieben, und hätte ich die Reversing-Arbeit noch ein wenig weitergeführt, hätte ich mir die ganze Arbeit sparen können, einen Disassembler für QB4 zu bauen. Ich war viel näher dran, als ich damals dachte. ↩ ↩2

  3. Es war nicht trivial für mich zu erkennen, dass es dieses Format war, der IEEE754-Gleitkommastandard, den ich unter die Lupe nahm. In einem viel früheren Beitrag auf einem Blog, den es nicht mehr gibt, hatte ich ein anderes Format gereversed, nämlich MBF (Microsoft Binary Format), und da ich annahm, dass Microsoft dasselbe Format verwenden würde wie in anderen Programmen, kam ich nicht so leicht auf die Idee, dass sie vielleicht den IEEE-Standard benutzen. ↩

  4. Entropie ist der Logarithmus zur Basis 2 der Anzahl gleich wahrscheinlicher Möglichkeiten (jedes Bit halbiert die Kandidaten). Wie man auch in xkcd Nr. 936 sehen kann, addieren sich die Bits an Entropie nur, wenn die Entscheidungen unabhängig voneinander sind. ↩