¡Hasta aquí llegó el olor!

("This is as far as the smell went!" is what the game says when you call "flor" - it rhymes in Spanish: flor / olor.)

At the end of this article I left the link so you can check out the source code of the "card spy".

The Truco Arbiser was a Truco game that made the rounds on Argentine computers between the late 80's and the 90's. They say it was the most pirated program after MS-DOS.

For years I fought endless battles against the PC and I was insulted and mocked relentlessly every time I played a match. Being a computer game, even my cunning has never been enough for victory. But no more. In this article, we are going to see how to play a truco (a trick) on the Truco Arbiser and claim one more victory of Human over Machine.

The Analysis

To pull a trick on the Truco Arbiser, we first have to know what it was programmed in, before anything else.

 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|

After a very quick search and a few fabulous hexdumps, we realize that the file BRUN40.EXE, which is also in the directory where the game lives, is present. This file is the runtime library of programs compiled with QuickBasic, a compiler for the BASIC programming language created by Microsoft. The particular version of this runtime is 4.0. From now on I will refer to QuickBasic 4.0 as QB4.

QB4 consists of two language processors. The first one, QB.EXE, provides an interactive programming environment. It is an incremental compiler that converts the source code to threaded p-code and then goes on executing the p-code in an interpretive fashion. The other one, BC.EXE, is a command line compiler that produces native executable files.

threaded p-code is a sort of Virtual Machine. Like the JVM, for example. The code generated as threaded p-code is an intermediate byte code that is interpreted either by the QB4 interpreter or by the BRUN40.EXE runtime.

Each of these compilers has certain advantages, and they can be used depending on different needs. The p-code interpreter loses in execution speed in exchange for compilation speed. Which allowed for much faster development. Remember that the Truco Arbiser was developed in the 80s; I assume on an XT or at most a 286, given the kind of computers that were available in that era and their prices. I also assume that the version you can download from the Truco Arbiser website is the 86 (or 87)1 version, where it says that it was "recompiled" on the same page, judging by the title screen, and because I couldn’t find a way to make the voice work even though the file VOZ.COM is in the zip that the site offers. I say this because the Truco Arbiser site mentions that the voice module was developed in 1992 at the request of a company.

So the idea was to develop very quickly with p-code and then use the BC compiler to generate the final executable without needing the interpreter involved.

But but but, the downside of this development method is that each compiler produces different code. p-code != asm x86. So a program that works fine in the QB4 interpreter works like a charm, but when compiled to machine code, some differences of interpretation could happen, and the "final" program would crash.

It is worth remembering that this optimization between interpreter and "final compilation" was necessary because of how slow the iterative software development process was at the time. Resources were limited and these solutions helped a lot to shorten the development cycle.

So, as partial conclusions we have that:

  • The available version of the Truco Arbiser 5.4 has a 1986 copyright and was compiled with QB4, that is, in 1987 or later1. Dating the executable is important, it helps us narrow down the possible versions of the compilers used in that era for a future analysis.
  • The presence of BRUN40.EXE narrows the possibilities even further. It helps me assume that the program was compiled with QB4 and that it was compiled not to be a self-contained executable, but rather that the EXE Requiring BRUN40.EXE option was used at compile time.
  • The presence of BRUN40.EXE in the executable is consistent with my observations.
  • A program compiled this way cannot be easily disassembled, since there is a "VM" in between.

The Problem

The problem is not only that the executable needs a runtime to interpret the byte-codes of the compiled program, but also that we know absolutely nothing about the format of the executable, nor how the bytes are interpreted, nor the structure and distribution of the information throughout the executable.

We can assume that at the beginning of the file there is a header that will be picked up by MSDOS, that somewhere the strings will be stored and that somewhere else the p-code will be located, if everything we have been saying turns out to be correct.

I am skipping in this article several attempts to attack the disassembly problem from different angles. All of them failed, of course. I tried to disassemble the Truco Arbiser with IDAPro attached to a debugger linked to a special version of DOSBOX and not only is it unstable, but every other minute a processor interrupt shows up, breaking the main flow of the program’s execution, which makes it unfollowable. What I did learn after debugging for a long time is that there is a table of CALLS pointing to NULL that are patched at runtime while the program is running. Which means that QB4 generates executables that modify themselves; making the debugging task way harder.

I also tried debugging with Turbo Debugger, with better results, but since it consumes a lot of memory (640k ftw!), I didn’t get very far either, because the program would either trap an out of memory or simply crash showing random characters on the screen.

When I say "get far" I mean that after several iterations of parsing p-code and patching memory addresses, I never even reached the function that shows the game’s title screen.

There is a possibility of linking two dosbox instances over serial, running Turbo Debugger and the program separately, interrupting the program somewhere remotely and debugging from there, but by this point I was frustrated and reading articles about this method, it kind of bummed me out that people in the forums complained that this way of debugging was so slow.

In short, going for the debugging option takes so much time that it makes it impractical for this case.2

P-Code Disassembler

So it occurred to me: What if instead of debugging, I write a disassembler? 2 Before writing it and going down this path, I obviously searched the interwebz to see if someone had already done it. There are some partial solutions and a gentleman who charges from 350 to 5000 pounds sterling in Great Britain who offers a disassembly service. Clearly paying is not an option. So, with this new focus, I got down to work.

The obvious things

In our tests, we are going to try to compile things the way the Arbisers might have done it back in the day. The idea behind this is to see how the compiled executable behaves at the binary level with small variations in the BASIC program.

So, first we write a very simple program:

A 'Hello World' with a variable

And we compile it with what we learned about what the Arbisers’ configuration might have been back then, with the information we analyzed in the previous sections.

We compile it so it needs BRUN

And we compile a second version with this source code

We compile it so it needs BRUN

IEEE 754

You’ll notice that the changes between the two BASIC programs are very few. Having made these changes, we do a binary diff of the two executables and compare what changed between them:

 $ 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.........

Ignoring the change in the file name, you can see that the string is different, and at 0x0a25 there is a word that changes, which I assume is the variable with the value 127 and 255. The interesting part is that it is not clear at first sight how 255 is represented with 0x7f43 and 127 with 0xfe42.

After staring at these numbers for a while, it is easy to realize that they are not words at all but rather doublewords and that the format of these numbers is IEEE 754. I compared several numbers generated in a new executable with the following code:

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

Below you can see the dword values generated by this variable assignment. You can compare these dwords yourself with an IEEE 754 calculator if you want:

 $ 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...|

An example: the value -5 represented in IEEE 754 at offset 0xaf3 is 0xc0a00000.

All this explanation I’m giving implies that we already know how to interpret a data type generated by the compiler.

Detecting Headers

All very beautiful, but what good is knowing how to interpret a couple of doubles in the binary if we don’t even know which section to look for them in?

Here things are going to get pretty nice, because by simple observation, if we look at an executable generated by QB4 we can see that there is not just one, but two headers. The first one is obviously the header of an .EXE but the second one is not so easy to see at first glance, although with a trained eye, you can spot it by staring. Very hard.

 $ 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.|

I suspect that at offset 0x200, the first word is an identifier of some kind, the next 8 bytes (suspiciously padded with spaces) are the file name, and then several bytes with unknown values until there starts to be something that is either code or data.

/* 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;

Going elsewhere

BC.EXE, the QuickBasic Compiler, has several flags that can be passed as parameters at compile time. One of these parameters is /a, which in addition to compiling the program also generates a "listing" in an assembler halfway to becoming pure machine code.

An example, the following BASIC program that I called FOR.BAS:

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

Generates the following FOR.LST file with the /a flag:

                                                                      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)

And finally, the relevant section of the FOR.EXE binary:

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  |................|

From 0x230 on you can see that each opcode correlates with the FOR.LST listing! This would mean that in order to parse, at least this section of the binary, it would be enough (in theory) to map each of the tokens of the language to its listing and its binary representation. Make a huge table with all the combinations of the language’s statements, identify types, expressions, and slowly try to reconstruct each sequence of bytes into something resembling the original program’s code. There are things that cannot be reconstructed, like the names of variables - which end up being just references to offsets - or the labels that were used to define names of functions or places to jump to.

If this is reasonable, we could partially reconstruct the original code of the Truco Arbiser and, once we have the code reasonably disassembled, we could analyze it to uncover its secrets afterwards.

Writing a parser and interpreting tokens

Finding function names

When we generate an LST, at every call opcode the Microsoft compiler gives us the nomenclature used by the runtime in the following way, for example:

 [...] (excerpt of 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
 [...]

When we parse the opcodes, every time I find a call, I look at the address being called and compare the LWORD discarding the HWORD. I do this in an arbitrary way, since for now it works pretty well. I don’t know exactly what HWORD represents yet:

    [...] excerpt of 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;
    [...]

And here below I show how my disassembler detects function names, showing a bit more information that is useful when debugging while I’m coding it:

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>

This and other processes are quite tedious, because the problem is not mapping the calls to each runtime function one by one, but that in order to find more and more functions that call different functions, I have to iteratively write BASIC programs that are distinguishable enough from each other to trigger the compiler into calling each one of these functions.

This means that the more programs I write, the more functions I find thanks to the LST generated by the compiler, but at the same time, I have to be more and more creative with the "functionality" of the programs so that the compiler shows me the function calls.

This takes a huge amount of time. Since the goal is to pull a trick on the Truco Arbiser, I’m not trying to map ALL of the output of the QuickBasic 4.0 compiler, but rather to program things that - sort of guessing - the Arbisers might have needed to do when coding the game.

Floating point emulation

Ah! This is quite hard and it presented me a challenge when trying to understand and parse the "floating point" opcodes.

I put it in quotes because in truth QB4 would not be using exactly FPU opcodes but rather a kind of emulation, which is defined as follows:

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

Makes sense. Back then, having an FPU was optional: you could install an FPU or not in your computer and have all the floating point operations go to hell, or you could choose to emulate these operations using only the CPU, making the calculations considerably slower.

Getting to this list, and knowing why I needed it, took me quite some time. Let’s look at the following piece of disassembly:


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>

So, there is a relationship between the INTerrupts, the dbs, the dws, which in the binary were offsets, and the compiler’s LST numbers. Clearly the integer numbers of the original program were being encoded in a special way, until at some point it clicks and I tell myself: Of course! IEEE754! 3

Little by little the pieces of the puzzle start taking shape and making sense. The problem is that there are a ton of pieces and it’s easy to get lost among so many bytes and loose data when trying to make sense of them.

Offsets and blocks

How are the sections of the executable’s module organized? How do I calculate where all the things the binary refers to are? At what exact offset are the variables, the constants, the strings, etc. stored?

No idea yet :D

B$<funcname>

Suddenly I find out that there was a leak of msdos 6.0 and with it I was able to complete some of the most important parts of this puzzle. It turns out that in the 45/runtime/rt directory there are tons of definitions of runtime calls from which I can take part of the documentation, find the runtime offset and print for each call the name of the function and a short description of what it does:

    [...]
        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; 
    [...]

The procedure is:

  • Compile a BASIC program
  • Ask BC.EXE to generate an .LST for us
  • Take the calls to the runtime, and look up the definition in the msdos6.0 source
  • Read the doc, and write the definition of the call offset in my disassembler (which I tag with the keyword unknown if I haven’t parsed it)

These steps take a ton of time, and being in the month of June (2022) at this point of development, several months had already gone by doing only this in my free time. And I started to think that this is not the way.

An Unexpected Twist

This way of working is quite purist and sometimes when I program I have a lot of fun, and doing things hard enough like a disassembler from scratch with C and the Intel manuals is fantastically fun, but the progress of the project becomes way too slow. For a while, up to this point (roughly a few months) I was putting together my own disassembler and the task ended up being writing the disassembler instead of trying to disassemble the executable with some tool that does it much better than me writing it myself.

There came a moment when the work of writing a disassembler from scratch became ridiculously tedious and was consuming too much of my time. For that reason, I decided to completely change the course of the project and use a disassembly engine to automate as much as possible the mapping of function calls to the QB runtime.

I decided to lean on Capstone Engine and start automating this comparison of the segment:offset of each CALL with the listings that the QB4 compiler spits out and match them with my disassembler.

Essentially:

  • interpret and compare offsets with lcall/call pairs, updating the function call strings.
  • build a table of the functions I’ve already discovered
  • rinse and repeat ad infinitum

All this effort bore some fruit. I was somehow able to disassemble pieces of programs compiled with Quick Basic 4.0 using its runtime and eventually I was going to end up with a Señor Disassembler that could end up being useful in the future to disassemble old programs à là HexRays.

In a way, this is how one never finishes anything, right? The journey is what entertains and on this journey I learned a ton. The final goal was to Truquear al Truco (to trick the Truco) and I spiraled into making a whole suite for disassembling P-Code.

The year after (2023), having something decent, the Arbiser was slipping away from me again and I still couldn’t peek at the CPU’s cards, which was the main goal. Understanding this, I started again with IDA and reversing again, which is where I had started in the first place.

This path was the one that was finally going to lead me to break it and this was the way.

Analysis of Memory Structures

The interrupts issue, which had made me throw in the towel so quickly, was just a matter of impatience. I don’t remember how I solved it, but if it wasn’t a setting, I was very, very close. What I did start doing was only read and write breakpoints, separately. Additionally, keeping a list of interesting memory addresses or where functions that look relevant begin.

A year later, then, I get down to reversing and I arrive at a decent table to have some breakpoints worth setting:

segment:offset memory segment:offset disassembled length description
seg004:fa94 [si+1c72] WORD*6 + 1 player words, suit 1 suit 2 suit 3 – nothing – card 1, 2, 3
seg004:f66a [si+1848] WORD*6 + 1 computer words, suit 1 suit 2 suit 3 – nothing - card 1, 2, 3
seg004:f680 [si+1860] WORD*3 random numbers placeholder/save area
seg004:fae4 ds:1cc4 WORD random number
seg004:fb90 ds:1d70 WORD current_card being calculated for player
seg004:fb92 ds:1d72 WORD current_card being calculated for computer
seg004:fb02 ds:1ce2h WORD last card number processed (player)
seg004:fb04 ??? DWORD ???????????????????????????
seg004:fb06 ??? DWORD ???????????????????????????
seg004:fb08 ??? DWORD ???????????????????????????
seg004:fb0a ??? WORD last suit processed (player)
seg005:12d3 ds:2836-ds:283a WORD STACK! BP/SP in seg005, it is the number that AX receives for many operations related to the random functions
021e:e6fb ds:8db WORD Low WORD of previous PRNG seed
021e:e6fd ds:8dd WORD Hi WORD of previous PRNG seed
???? 021e:e020 WORD A Constant QB4.0 PRNG
???? 021e:e024 BYTE C Constant QB4.0 PRNG
???? 021e:de20 DWORD float storage area?

Suits (Palos):

Suit EQU
Espada (Swords) 0x0000
Basto (Clubs) 0x0001
Oro (Coins) 0x0002
Copa (Cups) 0x0003

I also discovered some important details about the binary code and its data structures:

  • the card values go from 0x0001 to 0x000A (1 to 10, 1234567,10,11,12 are 10 different card number types)
  • if the selected card is greater than 7, then we add 2 so that we correct how they actually have to look.
  • there is a memory region where the player’s and the CPU’s cards are, and all the reads tend to be for drawing them on the screen and the writes come from the card-dealing algorithm

So awesome to know more or less what each thing is worth! The tough part now is understanding how these values are calculated and where they come from. Knowing this, we could replicate the behavior with a python script.

Pseudo Random Number Generator (PRNG)

It turns out that I spent hours reversing this section of code, which tried to get the next random number from the Pseudo random Number Generator or PRNG:


.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 ; ---------------------------------------------------------------------------

Since this section of code is in .text I assumed it was an algorithm written by the Arbisers and not part of BRUN40.EXE. It would have been enough to notice that we were in another segment by looking at the offset of .text and that’s it, but noooo. Remember that the MSDOS source was leaked? Well, sometimes when one experiences tunnel vision one can forget that there are other angles to attack the same problem, in the leak I find this:

; 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

It’s the same section of code! And it is exactly the PRNG. I didn’t look into exactly why that part of the runtime was in .text because I directly assumed that what was happening was that it wasn’t jumping within the same segment but that the TRUCO.EXE module was in one segment and BRUN40.EXE in another.

The celebration didn’t last long. Having identified where the PRNG was, I ran a small program in QB4 and its executable, in both, not using RANDOMIZE in order to have the same seed value in all the runs.

print rnd
print rnd
print rnd
print rnd
print rnd

The results of the QB4 interpreter and of the executables that the compiler generated were DIFFERENT. The why of this would demand another article, so when I saw this difference, I dedicated myself to working only with the compiled executables and not trusting any result from the QB interpreter.

rnd is the executable - the second run is from the interpreter

After a long pause, I went on to implement in C a library to be able to access with CTypes in Python the QB4 LCG. The idea of having this section separated from QB4 was to be able to use other languages to do experiments and to understand well what properties this PRNG could have. The idea was to be able to use Python instead of Quick Basic to draw ideas and properties from this particular LCG.

RND in RND.EXE and in my implementationThe output in MSDOS and in my implementation in C

A side note: I had reversed the PRNG by hand, and the confirmation in the screenshot above came before I got access to the MSDOS 6.0 leak. It turns out that the formula they used to randomize values was in the header of the file as a comment. I was happy, because I could confirm my implementation in different ways and know that it was perfect.

Partial prediction

More or less, now that I had the PRNG running, I was trying to find the seed. My process for a while was, having identified where the seed of the PRNG was being written, to check by hand the value of the seed in memory at every hand, and run a Python script to calculate the CPU’s hand.

The interesting part is that it worked great and I was so hyped I almost published my pants, but after a hand or two, it kind of lost "synchronization" with the seed: Sometimes the program decided to play a song, write a text or do nothing and that advanced the LCG calls. I spent a huge amount of time debugging, or trying to debug in each case the number of times that the next PRNG value was generated and, for anyone who has tried to debug on 16-bit Intel, you know how hard it sometimes is to follow the code with so many segment changes. Ugh.

So, I could already read the cards partially, but sometimes I got "desynchronized" and every time I did the debugging follow-up, I put in a huge number of hours without reaching any conclusion strong enough, I couldn’t figure out what the variation in the calls to the get_random function was and I abandoned it for a while, until…

But what the hell do you have a PC for, then?

Discussing the Truco Arbiser problem with some friends and telling them about my frustration with debugging, I show them this section of code of the 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;
}

To which someone asks me:

– Why don’t you precompute all the random numbers in one go instead of positioning yourself with the seed somewhere and looking several steps ahead to see whether the cards of your own hand are or aren’t in the next hand?

– Because it’s 2^24 elements that I’d have to be calculating, that’s ~16 million possibilities and it’s a lot of calculation and memory… for an 80's machine!

Mulero

Mulero TUIMulero’s text interface

Going round and round the LCG cycle

The QB4 LCG, as we have been saying over and over, has the form:

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

The effective constants are A = 0xfd43fd and C = 0xc39ec3. Microsoft’s comments say otherwise because the runtime loads the low half of each constant where it should load the high one. The details are in the repository’s README.

Looking through random number generator patterns and their problems I came across, among several other things, the Hull-Dobell theorem, which says that an LCG with modulus m goes through all its m states before repeating if and only if:

  1. C and m are coprime.
  2. A - 1 is divisible by all the primes that divide m.
  3. A - 1 is divisible by 4 if m is.

Here m = 2^24, so the only prime is 2 and the conditions boil down to C odd and A ≡ 1 (mod 4). The constants meet both: 0xc3 is odd and 0xfd = 253 = 4*63 + 1.

This means that the 16,777,216 states form a single circle. Each state occupies a position and running the generator is walking around that circle. The "next hand" is the current position plus a certain number of steps, the ones consumed by the deal plus the ones consumed by poems, insults and songs.

At the time of debugging, this "window" of actions (the selection of poems, beeper songs and insults) was what, I believe, desynchronized the position where I was, and debugging all the cases depending on a random number that triggers an arbitrary amount of calls to the functions that get more random numbers became very tedious. This other solution I’m proposing saves me directly from calculating the "amount" of calls to RND.

Just three hands, m4n!

The state has 24 bits of uncertainty. Seeing three distinct cards out of 40 gives you log2(40*39*38) ≈ 15.9 bits of information, that is, it removes 15.9 bits of entropy (uncertainty) from the state4. A single hand is not enough: there are 2^24 / (40*39*38) ≈ 283 compatible positions. With one hand you gain ~15.9 bits. The following hands contribute quite a bit less, because the WINDOW window already tells us more or less where they land, and for this reason 3 hands are enough for us.

To join the hands together we use a window. The new hand has to start no more than WINDOW = 1000 steps from where the previous one ended. A false candidate has a probability of 283 * 1000 / 2^24 ≈ 1.7 % of meeting this by chance. By the third hand almost no false candidate survives. The probability is low, but it’s not zero. Every now and then while using Mulero it may happen that you are playing and suddenly there are several hands in that window that meet the conditions; in that case, Mulero notices and lets you know that there is not 100% certainty at that point of the game, and it is enough to play one or two more hands to "re-certify" (?).

numpy

For this we need a table of 16 million entries and a ton of comparisons. In pure Python every turn of a for costs some interpreter time (checking types, creating int objects of ~28 bytes) making everything a bit slow. In NumPy the data lives in a contiguous block of memory with a fixed type (uint8 takes up 1 byte) and the fors run in C instead of Python. Writing a * x + c over an array is doing the for without writing it. This is called vectorizing.

valor = ciclos[a * x + c]       # everything is already precomputed

Precomputing the circle

The problem is that each state depends on the previous one, so it would seem not to be vectorizable. The way out is the jump ahead (jump-ahead). One step of the LCG is a linear function f(x) = A*x + C. Composing two linear functions gives another linear function:

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

So we can calculate what advances 4096 steps in one go:

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

We compute by hand the first block of 4096 states. Each following block comes from the previous one with a single operation over an array:

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

That’s 4096 Python turns plus 4096 vectorized operations, instead of 16 million turns.

There are several NumPy details in those lines:

  • & MASK instead of % N: since N is a power of 2, x mod 2^24 is equal to x & (2^24 - 1). It’s faster and only works with powers of 2.
  • dtype=np.uint64: estado * A reaches ~2^48 and would overflow a 32-bit integer.
  • state[a:b] is a view, not a copy. Assigning to it writes to the original array.
  • np.empty reserves memory without initializing it, because we are going to fill it entirely.

From state to card

Truco is a game with 40 cards in the deck. The order in which I wrote and composed the array to figure out how TRUCO.EXE does it comes from how the card selection is calculated in the program and the order in which it appears in memory.

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]

If you look at the function lcg_table(), INT(RND * 40) is floor(40 * estado / 2^24). Dividing by 2^24 and truncating is shifting 24 bits to the right, so what we get is (state * 40) >> 24, a value from 0 to 39. Since RND first advances the state and then returns, the card at position p comes from state p+1. That is solved by np.roll(cartas, -1), which shifts the array with wrap-around (the end connects to the beginning, exactly what a circle needs).

The result is CARDS, a 16 MB array where CARDS[p] is the card that would be dealt at position p.

Finding the hand

start = np.flatnonzero(CARDS == mi_primera_carta)

CARDS == x generates an array of 16 million booleans and flatnonzero returns the indices where it is True. With a single line we are left with 1/40 of the positions, about 419 thousand.

Then deal() simulates the deal for all those candidates in parallel. Since the game draws again when a repeated card comes out, each candidate needs a different number of draws. This is solved with a pend list of those that still need a card:

c = CARDS[pos[pend] & MASK]                          # fancy indexing: grab many elements at once
repeated = (hand[pend, :k] == c[:, None]).any(axis=1)
  • Fancy indexing: indexing an array with another array of indices.
  • Broadcasting: hand[pend, :k] has shape (n, k) and c[:, None] has shape (n, 1). NumPy "stretches" the column and compares each new card against the k already dealt.
  • .any(axis=1) collapses the columns and answers "did any repeat?" for each row.
  • ~repeated is the bitwise negation. With arrays you can’t use not.

After each of the first three cards, the candidates that don’t match your hand are discarded (start = start[ok], a boolean mask). From 419 thousand we go down to about ~283, and the CPU’s cards are simulated only for those.

Chaining hands

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

Subtracting a column vector (n, 1) and a row vector (1, m) gives an (n, m) matrix with all the pairwise differences, without any for. The & MASK over negative numbers gives the correct modulo (the circular distance). The .any(axis=1) asks whether this candidate falls less than WINDOW steps from some end of the previous hand.

Finally, np.sort(cpu, axis=1) sorts the cards of each candidate hand so that {3, 7, 9} and {9, 3, 7} count as the same, and np.unique(axis=0, return_counts=True) groups the equal rows and counts how many times each one appears. If only one possible hand is left, you already know what the CPU has.

Now, download Mulero and beat it once and for all!

Source code

Mulero in actionMulero in action

You can download Mulero’s source code from the Codeberg repository: https://codeberg.org/toshi/mulero

References

Footnotes

  1. At the time I wrote "it was compiled in 1986" because the copyright notice in the game also says 1986, but Quick Basic 4.0 was released in 1987! ↩ ↩2

  2. However, I wrote this around four years before the publication of this article and had I continued a bit longer with the reversing effort, I would have avoided all the work of building a disassembler for QB4. I was much closer than I thought at that moment. ↩ ↩2

  3. It wasn’t trivial for me to realize that this was the format, the IEEE754 floating point standard, that I was looking at under the microscope. In a much earlier post on a blog that no longer exists, I had been reversing another format, MBF (Microsoft Binary Format), and assuming that Microsoft would use the same format it had used in other programs, it didn’t occur to me so easily that they might use the IEEE standard. ↩

  4. Entropy is the base-2 logarithm of the number of equally likely possibilities (each bit halves the candidates). As can also be seen in xkcd no. 936, the bits of entropy add up only when the choices are independent. ↩