¡Hasta aquí llegó el olor!

Al final de este artículo dejé el link para que puedas ver el código fuente del "espiador de cartas".

El Truco Arbiser fue un juego de Truco que estuvo rondando en las computadoras argentinas entre finales de los 80's y los 90's. Se dice, que fue el programa más pirateado después del MS-DOS.

Durante años libré incansables batallas contra la PC y fui insultado y descansado incansablemente cada vez que jugaba alguna partida. Siendo un juego de computadora, aún mi astucia jamás ha logrado ser suficiente para la victoria. Pero ya no más. En este artículo, vamos a ver como hacerle truco al Truco Arbiser y reclamar una victoria más del Humano contra la Máquina.

El Análisis

Para hacerle trucos al Truco Arbiser, primero tenemos que saber antes que nada, en que fue programado.

 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|

Una búsqueda muy rápida y después de unos fabulosos hexdump, nos damos cuenta que el archivo BRUN40.EXE que también está en el directorio donde está el juego, está presente. Este archivo, es la librería (biblioteca para los puristas) runtime de programas compilados con QuickBasic, un compilador del lenguaje de programación BASIC creado por Microsoft. La versión particular de este runtime es la 4.0. A partir de ahora voy a referirme a QuickBasic 4.0 como QB4.

QB4 consiste en dos procesadores de lenguaje. El primero, QB.EXE, mantiene un entorno de programación interactivo. Es un compilador incremental que convierte el código fuente a threaded p-code y después va ejecutando p-code de forma interpretativa. El otro, BC.EXE es un compilador de línea de comando que produce archivos ejecutables nativos.

El threaded p-code es una suerte de Virtual Machine. Como la JVM por ejemplo. El código generado en threaded p-code es un byte code intermedio que es interpretado o bien por el intérprete QB4 o bien por el runtime BRUN40.EXE.

Cada uno de estos compiladores tienen ciertas ventajas, y que pueden ser utilizados dependiendo de diferentes necesidades. El interprete p-code pierde en velocidad de ejecución a cambio de velocidad de compilación. Lo que permitía desarrollar mucho más rápido. Recordemos que el Truco Arbiser fue desarrollado en los 80s; asumo que en una XT o máximo una 286 por el tipo de computadoras que había disponibles en esa época y sus precios. También asumo que la versión que se puede bajar de la página del Truco Arbiser es la versión del año 86 (u 87)1, donde se menciona que fue "recompilada" en la misma página, por la pantalla de presentación, y porque no encontré manera de hacer que la voz funcione aunque esté el archivo VOZ.COM en el zip que ofrece el sitio. Digo esto porque en el sitio del Truco Arbiser se menciona que el módulo de voz fue desarrollado en el año 92 por pedido de una empresa.

Entonces la idea era desarrollar muy rápidamente con p-code y después utilizar el compilador BC para generar el ejecutable final sin la necesidad que el intérprete esté involucrado.

Pero pero pero, la desventaja de este método de desarrollo es que cada compilador produce código diferente. p-code != asm x86. Entonces, un programa que funciona bien en el intérprete QB4 funciona joya, pero cuando se compila a código máquina, algunas diferencias de interpretación podían suceder, y el programa "final" crasheaba.

Cabe recordar que esta optimización entre intérprete y "compilación final" era necesaria debido a lo lento que era el proceso iterativo de desarrollo de software en esta época. Los recursos eran limitados y estas soluciones ayudaban mucho a decrementar el tiempo del ciclo de desarrollo.

Entonces, tenemos como conclusiones parciales que:

  • La versión disponible del Truco Arbiser 5.4, tiene copyright de 1986 y compilada con QB4, es decir, 1987 o posterior1. Datar el ejecutable es importante, nos ayuda a achicar las posibilidades de la versión de compiladores usados en esa época para un futuro análisis.
  • La presencia de BRUN40.EXE achica aún más las posibilidades. Me ayuda a asumir que el programa fue compilado con QB4 y que se compiló no para que sea un ejecutable autocontenido, sino que en el momento de compilación se utilizó la opción EXE Requiring BRUN40.EXE.
  • La presencia de BRUN40.EXE en el ejecutable es consistente con mis observaciones.
  • Un programa compilado de esta manera, no se puede desensamblar fácilmente, ya que hay una "VM" de por medio.

El Problema

El problema no solo radica en que el ejecutable necesita de un runtime para interpretar los byte-codes del programa compilado, sino que también no sabemos absolutamente nada ni del formato del ejecutable, ni como se interpretan los bytes, ni la estructura y distribución de la informacion a lo largo del ejecutable.

Podemos asumir que al principio del archivo, hay un header que va a ser levantado por MSDOS, que en algún lugar va a guardarse los strings y que en algún otro lugar se va a alojar el código p-code si todo lo que venimos diciendo fuera correcto.

Estoy obviando en este artículo varios intentos de atacar el problema del desensamblado desde diferentes ópticas. Todos fallidos, por supuesto. Intenté desensamblar el Truco Arbiser con IDAPro attacheado a un debugger linkeado a una version especial del DOSBOX y no solamente es inestable, si no que cada dos por tres una interrupción del procesador se hace presente rompiendo el flujo principal de la ejecución del programa, lo que lo hace inseguible. Lo que si aprendí debuggeando por mucho tiempo, es que hay una tabla de CALLS que apuntan a NULL que son patcheadas en runtime mientras el programa se va ejecutando. Lo que hace que QB4 genere ejecutables que se automodifican; haciendo la tarea de debuggeo muchísimo más difícil.

También intenté debuggear usando el Turbo Debugger, con mejores resultados, pero como se consume mucha memoria (640k ftw!), no logré llegar muy lejos tampoco porque o bien el programa trapeaba un out of memory o bien simplemente crasheaba mostrando caracteres random en la pantalla.

Cuando me refiero a "llegar lejos" hablo de que luego que varias iteraciones de parsear p-code y patchear direcciones de memoria, nunca llegué siquiera a la función que muestra la pantalla de título del juego.

Existe una posibilidad de linkear dos instancias de dosbox por serial, correr el Turbo Debugger y el programa por separado, interrumpir el programa en algun lado remotamente y debuggear desde ahí, pero ya a esta altura estaba frustrado y leyendo artículos sobre este método, me la bajó bastante que se quejaran en los foros que esta forma de debuggear fuera tan lenta.

En definitiva, ir por la opción de debuggear consume tanto tiempo que lo hace impracticable para este caso.2

Desensamblador P-Code

Entonces se me ocurrió: ¿Qué pasa si en vez de debuggear, escribo un desensamblador? 2 Antes de escribirlo e ir por este camino, obviamente busqué en la interwebz si alguien ya lo había hecho. Existen algunas soluciones parciales y un señor que cobra de 350 a 5000 libras esterlinas en Gran Bretania que ofrece el servicio de desensamblado. Claramente pagar no es una opción. Entonces, con este nuevo foco, me puse manos a la obra.

Las cosas obvias

Vamos a tratar en nuestras pruebas, compilar las cosas como pudieran haberlo hecho los Arbiser en su momento. La idea detrás de esto, es ver como se comporta el ejecutable compilado a nivel binario con pequeñas variaciones en el programa BASIC.

Entonces, primero escribimos un programa muy sencillo:

Un 'Hola Mundo' con una variable

Y lo compilamos con lo que aprendimos sobre lo que pudo haber sido la configuración de los Arbiser en su época, con la información que analizamos en las secciones anteriores.

Compilamos para que necesite BRUN

Y compilamos una segunda version con este código fuente

Compilamos para que necesite BRUN

IEEE 754

Notaran que los cambios entre los dos programas en BASIC son muy pocos. Habiendo hecho estos cambios, hacemos un diff binario de los dos ejecutables y comparamos que cambios hubo entre ellos:

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

Ignorando el cambio del nombre del archivo, se puede ver que el string es diferente, y en 0x0a25 hay un word que cambia que asumo que es la variable con valor 127 y 255. Lo interesante es que no es claro a simple vista como se representa 255 con 0x7f43 y 127 con 0xfe42.

Después de mirar fijo un rato estos números, es fácil darse cuenta que no solamente no son words sino más bien doublewords y que el formato de estos números es el de la IEEE 754. Comparé varios números generados en un nuevo ejecutable con el siguiente código:

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

Aqui debajo se pueden ver los valores dword generados por esta asignación de variables. Podés comparar por vos mismo estos dword con una calculadora IEEE 754 si querés:

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

Un ejemplo, el valor -5 representado en IEEE 754 en el offset 0xaf3 es 0xc0a00000.

Toda esta explicación que estoy haciendo implica que ya sabemos interpretar un tipo de datos generado por el compilador.

Detectando Headers

Todo muy hermoso ¿Pero de qué sirve saber como interpretar un par de doubles en el binario si no sabemos siquiera en que sección hay que buscarlos?

Acá la cosa se va a poner bastante linda, porque por simple observación, si miramos un ejecutable generado por QB4 podemos apreciar que no hay solamente uno, sino dos headers. El primero es obvio que es el header de un .EXE pero el segundo, no es tan fácil de ver a simple vista, aunque con un ojo entrenado, se nota mirándolo fijo. Muy fijo.

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

Sospecho que en el offset 0x200, el primer word es un identificador de algun tipo, los siguientes (sospechosamente paddeados con espacios) 8 bytes es el nombre del archivo, y luego varios bytes con valores desconocidos hasta que empieza a haber algo que o bien es código o es datos.

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

Yendo por otros lados

BC.EXE que es el QuickBasic Compiler tiene varios flags que pueden pasarse como parámetros a la hora de compilar. Uno de estos parámetros es el /a que además de compilar el programa, también genera un "listado" en un assembler a medio camino de llegar a ser puro código máquina.

Un ejemplo, el siguiente programa en BASIC que llamé FOR.BAS:

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

Genera el siguiente archivo FOR.LST con el flag /a:

                                                                      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)

Y finalmente, la sección relevante del binario 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  |................|

A partir de 0x230 se puede ver que cada opcode correlaciona con el listado FOR.LST! Esto significaría que para poder parsear, al menos esta sección del binario, bastaría (en teoria) con mappear cada uno de los tokens del lenguaje, con su listado y su representación binaria. Hacer una tabla enorme con todas las combinaciones de las declaraciones del lenguaje, identificar tipos, expresiones, y lentamente ir tratando de reconstruir cada secuencia de bytes a algo parecido al código del programa original. Hay cosas que no pueden reconstruirse, como los nombres de variables - que terminan siendo solamente referencias a offsets - o los labels que se usaron para definir nombres de funciones o lugares a donde saltar.

Si esto es razonable, se podría reconstruir parcialmente el código original del Truco Arbiser y luego de tener el código razonablemente desensamblado, podriamos analizarlo para descubrir sus secretos posteriormente.

Escribiendo un parser e interpretando tokens

Encontrando nombres de función

Cuando generamos un LST, en cada opcode call el compilador de Microsoft nos da la nomenclatura usada por el runtime de la siguiente manera, por ejemplo:

 [...] (fragmento de 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
 [...]

Cuando parseamos los opcodes, cada vez que encuentro un call, me fijo la dirección a la cual se está llamando y comparo el LWORD descartando el HWORD. Hago esto de manera arbitraria, ya que por ahora funciona bastante bien. No se exactamente que representa HWORD todavía:

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

Y aqui debajo muestro como mi desensamblador detecta los nombres de función, mostrando un poco más de información que es útil a la hora de debuggear mientras lo voy codeando:

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>

Este y otros procesos son bastante tediosos, porque el problema no es mapear una por una las llamadas a cada función del runtime, sino que para poder encontrar cada vez más funciones que llaman a diferentes funciones, tengo que iterativamente, escribir programas en BASIC que sean lo suficientemente distinguibles entre si para triggerear al compilador y que llame a cada una de estas funciones.

Esto significa, que mientras más programas haga, más funciones encuentro gracias al LST generado por el compilador, pero asi también, tengo que ser cada vez más creativo con la "funcionalidad" de los programas para que el compilador me muestre las llamadas de función.

Esto, demanda muchísimo tiempo. Como el objetivo es hacerle truco al Truco Arbiser, no estoy buscando mapear TODO el output del compilador QuickBasic 4.0, sino más bien, programar cosas que - medio adivinando - los Arbiser pudieran haber necesitado hacer al codear el juego.

Emulación de punto flotante

¡Ah! Esto es bastante difícil y me presentó un desafío a la hora de tratar de entender y parsear los opcodes de "punto flotante".

Lo pongo entre comillas, porque en verdad QB4 no estaría usando exactamente opcodes de la FPU sino más bien, usa una especie de emulación, que esta definida de la siguiente forma:

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

Tiene sentido. En esa época, tener una FPU era opcional: podías instalarle una FPU o no a tu computadora y hacer que todas las operaciones de punto flotante vayan a las chapas o podias optar por emular estas operaciones solamente con la CPU haciendo que sus cálculos sean considerablemente más lentos.

Llegar a esta lista, y saber por qué la necesitaba me llevó bastante tiempo. Veamos el siguiente pedazo de desensamblado:


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>

Entonces, existe una relación entre las INTerrupciones, los db, los dw que en el binario eran offsets con los numeros LST del compilador. Claramente los numeros enteros del programa original estaban siendo encodeados de una manera especial, hasta que en un momento caigo y me digo: ¡Claro! ¡IEEE754! 3

Poco a poco las piezas del rompecabezas van empezando a tomar forma y sentido. El problema es que las piezas son muchísimas y es fácil perderse entre tantos bytes y datos sueltos al querer darles sentido.

Offsets y bloques

¿Cómo se organizan las secciones del módulo del ejecutable? ¿Cómo calculo donde están todas las cosas que el binario hace referencia? ¿En que offset exacto se guardan las variables, las constantes, los strings, etc…?

Ni idea todavia :D

B$<funcname>

De pronto me entero que hubo un leak del msdos 6.0 y con él pude completar algunas de las más importantes partes de esta piezas del puzzle. Resulta ser que en el directorio 45/runtime/rt hay muchísimas definiciones de llamadas al runtime donde puedo tomar parte de la documentación, encontrar el offset del runtime e imprimir por cada llamada el nombre de la función y una pequeña descripción de lo que hace:

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

El procedimiento es:

  • Compilar un programa en BASIC
  • Pedirle a BC.EXE que nos genere un .LST
  • Tomar las calls al runtime, y buscar la definición en el source del msdos6.0
  • Leer la doc, y escribir la definicion del offset del call de mi desensamblador (que tagueo con el keyword unknown si no lo tengo parseado)

Estos pasos llevan un montonazo de tiempo, y estando en el mes de junio (2022) a la altura del desarrollo, ya pasaron varios meses solamente haciendo esto en mis tiempos libres. Y empecé a pensar que por acá no es.

Un Giro Inesperado

Esta forma de laburar es bastante purista y a veces cuando programo me divierto mucho y haciendo cosas lo suficientemente dificiles como un desensamblador desde cero con C y los manuales de Intel es fantásticamente divertido, pero el avance del proyecto se vuelve demasiado lento. Durante un tiempo, hasta acá (aproximadamente unos meses) estuve armando mi propio desensamblador y la tarea terminó siendo escribir el desensamblador en vez de tratar de desensamblar el ejecutable con alguna herramienta que lo haga muchísimo mejor que ponermelo a escribir yo mismo.

Llegó un momento en que el trabajo de escribir un desensamblador desde cero se volvió ridículamente tedioso y me estaba consumiendo demasiado tiempo. Por este motivo, decidí cambiar completamente el rumbo del proyecto y usar un engine de desensamblado para automatizar lo mas posible el mapeo de llamadas de función con el runtime de QB.

Decidí apoyarme en Capstone Engine y empezar a automatizar esta comparacion de segment:offset de cada CALL con los listados que escupe el compilador QB4 y matchearlos con mi desensamblador.

Escencialmente:

  • interpretar y comparar offsets con pares lcall/call updateando los strings de llamadas de función.
  • armar una tabla de funciones que ya haya descubierto
  • rinse and repeat ad infinitum

Todo este esfuerzo, dio cierto grado de frutos. Pude de alguna manera desensamblar pedazos de programas compilados con Quick Basic 4.0 usando su runtime y eventualmente iba a llegar a tener un Señor Desensamblador que podía llegar a ser útil en un futuro para desensamblar programas viejos à là HexRays.

De alguna manera, asi es como uno nunca termina nada ¿No? El viaje es lo que entretiene y en este viaje aprendí una barbaridad. El objetivo final era Truquear al Truco y espiralé en hacer toda una suite de desensamblado de P-Code.

Al año siguiente (2023) de tener algo decente, el Arbiser se me estaba escapando nuevamente y seguía sin poder espiarle las cartas a la CPU, que era el objetivo principal. Entendiendo esto, arranqué de nuevo con el IDA y a reversear de nuevo, que era donde había empezado en un principio.

Este camino, era el que me iba a llevar a romperlo finalmente y era por acá.

Análisis de Estructuras en Memoria

El tema de las interrupciones, que me había hecho tirar la toalla tan rápido fue una cuestión de impaciencia nomás. No me acuerdo como lo resolví, pero si no era un setting, le pegaba en el palo. Lo que si empecé a hacer, es solamente breakpoints de lectura y escritura, discriminados. Adicionalmente, mantener una lista de direcciones de memoria interesantes o donde empiecen funciones que parezcan relevantes.

Al año, entonces, me pongo a reversear y llego a una tabla decente para tener ciertos breakpoints que valgan la pena:

segment:offset memoria segment:offset desensamblado longitud descripcion
seg004:fa94 [si+1c72] WORD*6 + 1 jugador words, palo 1 palo 2 palo 3 – nada – carta 1, 2, 3
seg004:f66a [si+1848] WORD*6 + 1 computadora words, palo 1 palo 2 palo 3 – nada - carta 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 ultimo palo procesado (player)
seg005:12d3 ds:2836-ds:283a WORD STACK! BP/SP en seg005, es el numero que recibe AX para muchas operaciones relacionadas con las funciones random
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?

Palos:

Palo EQU
Espada 0x0000
Basto 0x0001
Oro 0x0002
Copa 0x0003

También descubrí algunos detalles importantes que en el código binario y sus estructuras de datos:

  • los valores de las cartas van de 0x0001 a 0x000A (1 a 10, 1234567,10,11,12 son 10 tipos de numero de cartas diferentes)
  • si la carta seleccionada es mayor a 7, entonces le sumamos 2 asi corregimos como se tienen que ver en realidad.
  • hay una region de memoria donde estan las cartas del jugador y del cpu y todo las lecturas tienden a ser para poder dibujarlas en la pantalla y las escrituras son del algoritmo de reparto de cartas

¡Entonces buenísimo saber más o menos que vale cada cosa! La joda ahora es entender como se calculan estos valores y de donde vienen. Sabiendo esto, podriamos replicar el comportamiento con un script en python.

Pseudo Random Number Generator (PRNG)

Resulta ser que estuve horas reverseando esta sección de código, que trataba de obtener el siguiente numero random del Pseudo random Number Generator o 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 ; ---------------------------------------------------------------------------

Como esta sección de código esta en .text asumí que era un algoritmo escrito por los Arbiser y no que era parte del BRUN40.EXE. Bastaba con notar que estábamos en otro segmento mirando el offset de .text y listo, pero noooo. ¿Recuerdan que el source del MSDOS fue leakeado? Bueno, a veces uno al experimentar visión de tunel se puede olvidar que tiene otros ángulos para atacar un mismo problema, en el leak me encuentro esto:

; 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

¡Es la misma sección de código! Y es exactamente el PRNG. No me puse a ver exactamente porque era que parte del runtime estaba en .text porque asumí directamente que lo que estaba pasando es que no estaba saltando dentro del mismo segmento sino que por un lado el módulo del TRUCO.EXE estaba en un segmento y el BRUN40.EXE en otro.

El festejo no duró demasiado. Al identificar entonces donde estaba el PRNG entonces corri un pequeño programa en QB4 y su ejecutable, en ambos, no usando RANDOMIZE para tener el mismo valor del seed en todas las ejecuciones.

print rnd
print rnd
print rnd
print rnd
print rnd

Los resultados del intérprete QB4 y los ejecutables que generaba el compilador eran DISTINTOS. El por que de esto, demandaría otro artículo, asi que cuando vi esta diferencia, me dediqué a trabajar solamente con los ejecutables compilados y no confiar en ningún resultado del intérprete QB.

rnd es el ejecutable - la segunda corrida es desde el interprete

Después de una larga pausa, continué implementando en C una librería para poder acceder con CTypes en Python al LCG de QB4. La idea de tener esta sección separada de QB4 era poder usar otros lenguajes para hacer experimentos y entender bien que propiedades podia llegar a tener este PRNG. La idea era poder usar Python en vez de Quick Basic para sacar ideas y propiedades de este LCG en particular.

RND en RND.EXE y en mi implementaciónEl output en MSDOS y en mi implementación en C

Una nota de color, es que el PRNG lo había reverseado a mano, y la confirmación del screenshot de acá arriba fue anterior al haber accedido al leak del MSDOS 6.0. Resulta ser que la fórmula que usaban para randomizar valores, estaba en la cabecera del archivo como comentario. Yo contento, porque pude confirmar mi implementación de diferentes maneras y saber que estaba perfecto.

Predicción parcial

Más o menos, como que ya tengo el PRNG andando, estuve tratando de encontrar el seed. Mi proceso fue durante un tiempo estar habiendo identificado donde estaba escribiéndose el valor del seed del PRNG y verificar a mano cada mano el valor del seed en memoria, y correr un script en Python para calcular la mano de la CPU.

Lo interesante es que funcionaba bárbaro y yo ya estaba que me publicaba encima, pero después de una o dos manos, como que perdía la "sincronización" con el seed: A veces el programa decidía tocar una canción, escribir un texto o no hacer nada y eso hacía avanzar las llamadas del LCG. Pasé muchísimo tiempo debuggeando, o tratando de debuggear en cada caso cual era el número de veces que se avanzaba al siguiente PRNG generado y, para el que haya tratado de debuggear en Intel 16 bits, sabrá lo difícil que es a veces seguir el código con tanto cambio de segmento. Puaj.

Entonces, ya le podía leer las cartas parcialmente, pero a veces me "desincronizaba" y cada vez que hacía el seguimiento debuggeando, le ponía muchísimas horas para no llegar a ninguna conclusión lo suficientemente fuerte, no podía darme cuenta de cual era la variación de llamadas a la función get_random y lo abandoné por un tiempo, hasta que…

¿Pero para que verga tenés una PC, entonces?

Discutiendo el problema del Truco Arbiser con algunos amigos y contándoles mi frustración con el debugging, les muestro esta sección de código del 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;
}

A lo que uno me pregunta:

– ¿Por qué no precalculás todos los números random de un saque en vez de posicionarte con el seed en alguna parte y te vas fijando varios pasos adelante si las cartas de tu propia mano están o no en la siguiente mano?

– Porque son 2^24 elementos que tengo que estar calculando, son ~16 Millones de posibilidades y es un montón de cálculo y memoria… ¡para una máquina de los 80's!

Mulero

Mulero TUILa interfaz de texto de Mulero

Dándole vueltas y vueltas al ciclo del LCG

El LCG de QB4 como venimos diciendo una y otra vez tiene la forma:

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

Las constantes efectivas son A = 0xfd43fd y C = 0xc39ec3. Los comentarios de Microsoft dicen otra cosa porque el runtime carga la mitad baja de cada constante donde debería cargar la alta. El detalle está en el README del repositorio.

Revisando patrones de generadores de números random y sus problemas me topé entre varias cosas más, con el teorema de Hull-Dobell que dice que un LCG con módulo m recorre todos sus m estados antes de repetirse si y solo si:

  1. C y m son coprimos.
  2. A - 1 es divisible por todos los primos que dividen a m.
  3. A - 1 es divisible por 4 si m lo es.

Acá m = 2^24, así que el único primo es 2 y las condiciones se reducen a C impar y A ≡ 1 (mod 4). Las constantes cumplen las dos: 0xc3 es impar y 0xfd = 253 = 4*63 + 1.

Esto significa que los 16.777.216 estados forman un solo círculo. Cada estado ocupa una posición y recorrer el generador es caminar por ese círculo. La "mano siguiente" es la posición actual más cierta cantidad de pasos, los que consumió el reparto más los que consumieron poemas, insultos y canciones.

En el momento de estar debuggeando, esta "ventana" de acciones (la seleccion de poemas, canciones del beeper e insultos) era lo que, creo yo, me desincronizaba la posición en donde me encontraba y debuggear todos los casos dependiendo de un número random que triggerea una cantidad arbitraria de llamadas a las funciones para obtener más números random se me tornó muy tediosa. Esta otra solución que estoy planteando, me salva directamente de calcular la "cantidad" de llamadas a RND.

Tres manos na' má' v4r0n!

El estado tiene 24 bits de incertidumbre. Ver tres cartas distintas de 40 te da log2(40*39*38) ≈ 15,9 bits de información, es decir, le saca 15,9 bits de entropía (incertidumbre) al estado4. Una mano sola no alcanza: hay 2^24 / (40*39*38) ≈ 283 posiciones compatibles. Con una mano ganás ~15,9 bits. Las manos siguientes aportan bastante menos, porque la ventana WINDOW ya nos dice más o menos dónde caen y por esto, con 3 manos nos alcanza.

Para unir las manos usamos una ventana. La mano nueva tiene que arrancar a no más de WINDOW = 1000 pasos de donde terminó la anterior. Una candidata falsa tiene una probabilidad de 283 * 1000 / 2^24 ≈ 1,7 % de cumplirlo por casualidad. En la tercera mano casi no sobrevive ninguna falsa. La probabilidad es baja, pero no es igual a cero. Cada tanto usando a Mulero puede ser que estés jugando y de pronto haya varias manos en esa ventana que cumplan con las condiciones, en ese caso, Mulero se da cuenta y te avisa que no hay un 100% de certeza en ese momento de la partida y solo basta con jugar una o dos manos más para “re-certerizarse” (?).

numpy

Para esto necesitamos una tabla de 16 millones de entradas y un montón de comparaciones. En Python puro cada vuelta de un for cuesta cierto tiempo de intérprete (chequear tipos, crear objetos int de ~28 bytes) haciendo todo un poco lento. En NumPy los datos viven en un bloque contiguo de memoria con un tipo fijo (uint8 ocupa 1 byte) y los for se ejecutan en C en vez de Python. Escribir a * x + c sobre un array es hacer el for sin escribirlo. A eso se le llama vectorizar.

valor = ciclos[a * x + c]       # ya está todo precalculado

Precalcular el círculo

El problema es que cada estado depende del anterior, así que no parecería vectorizable. La salida es el salto hacia adelante (jump-ahead). Un paso del LCG es una función lineal f(x) = A*x + C. Componer dos funciones lineales da otra función lineal:

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

Entonces podemos calcular qué hace avanzar 4096 pasos de una sola vez:

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

Calculamos a mano el primer bloque de 4096 estados. Cada bloque siguiente sale del anterior con una sola operación sobre un array:

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

Son 4096 vueltas de Python más 4096 operaciones vectorizadas, en vez de 16 millones de vueltas.

Hay varios detalles de NumPy en esas líneas:

  • & MASK en vez de % N: como N es potencia de 2, x mod 2^24 es igual a x & (2^24 - 1). Es más rápido y solo funciona con potencias de 2.
  • dtype=np.uint64: estado * A llega a valer ~2^48 y desbordaría un entero de 32 bits.
  • state[a:b] es una vista, no una copia. Asignarle algo escribe en el array original.
  • np.empty reserva memoria sin inicializarla, porque la vamos a llenar entera.

De estado a carta

El Truco es un juego de 40 cartas en el mazo. El orden en que escribí y compuse el array para descular como hace TRUCO.EXE viene de como se calcula la selección de cartas en el programa y el orden en que aparece en memoria.

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]

Si se fijan en la función lcg_table() INT(RND * 40) es floor(40 * estado / 2^24). Dividir por 2^24 y truncar es correr 24 bits a la derecha, así que queda (state * 40) >> 24, un valor de 0 a 39. Como RND primero avanza el estado y después devuelve, la carta de la posición p sale del estado p+1. Eso lo resuelve np.roll(cartas, -1), que desplaza el array con vuelta circular (el final se conecta con el principio, justo lo que necesita un círculo).

El resultado es CARDS, un array de 16 MB donde CARDS[p] es la carta que se repartiría en la posición p.

Buscar la mano

start = np.flatnonzero(CARDS == mi_primera_carta)

CARDS == x genera un array de 16 millones de booleanos y flatnonzero devuelve los índices donde vale True. Con una sola línea queda el 1/40 de las posiciones, unas 419 mil.

Después deal() simula el reparto de todas esas candidatas en paralelo. Como el juego vuelve a tirar cuando sale una carta repetida, cada candidata necesita una cantidad distinta de tiradas. Se resuelve con una lista pend de las que todavía necesitan carta:

c = CARDS[pos[pend] & MASK]                          # fancy indexing: sacar muchos elementos de una
repeated = (hand[pend, :k] == c[:, None]).any(axis=1)
  • Fancy indexing: indexar un array con otro array de índices.
  • Broadcasting: hand[pend, :k] tiene forma (n, k) y c[:, None] tiene forma (n, 1). NumPy "estira" la columna y compara cada carta nueva contra las k ya repartidas.
  • .any(axis=1) colapsa las columnas y responde "¿repitió alguna?" por cada fila.
  • ~repeated es la negación bit a bit. En arrays no se puede usar not.

Después de cada una de las tres primeras cartas se descartan las candidatas que no coinciden con tu mano (start = start[ok], una máscara booleana). De 419 mil se pasa a unas ~283, y las cartas de la CPU se simulan solo para esas.

Encadenar manos

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

Restar un vector columna (n, 1) y uno fila (1, m) da una matriz (n, m) con todas las diferencias de a pares, sin ningún for. El & MASK sobre números negativos da el módulo correcto (la distancia circular). El .any(axis=1) pregunta si esta candidata cae a menos de WINDOW pasos de algún final de la mano anterior.

Por último, np.sort(cpu, axis=1) ordena las cartas de cada mano candidata para que {3, 7, 9} y {9, 3, 7} cuenten como la misma, y np.unique(axis=0, return_counts=True) agrupa las filas iguales y cuenta cuántas veces aparece cada una. Si queda una sola mano posible, ya sabés qué tiene la CPU.

Ahora, bajate Mulero y ganale de una buena vez!

Código fuente

Mulero en acciónEl Mulero en acción

El código fuente de Mulero lo podés descargar en el repositorio de Codeberg: https://codeberg.org/toshi/mulero

Referencias

Notas al pie

  1. Escribí en ese momento "fue compilada en 1986" porque la nota de copyright en el juego también dice 1986, pero Quick Basic 4.0 fue relizeada en 1987! ↩ ↩2

  2. Sin embargo, esto lo escribí alrededor de cuatro años antes de la publicación de este artículo y si hubiera continuado un poco más en el esfuerzo del reversing, hubiera evitado todo el laburo de hacer un desensamblador para QB4. Estaba mucho más cerca de lo que creía en aquel momento. ↩ ↩2

  3. No me fue trivial darme cuenta que era este formato, el estándar del punto flotante IEEE754 el que estaba mirando bajo la lupa. En una publicación en un blog muy anterior a este que ya no existe más, estuve reverseando otro formato que era el MBF (Microsoft Binary Format) y asumiendo que Microsoft iba a usar el mismo formato que usó en otros programas, no se me había ocurrido tan fácilmente que quizas iban a usar el estándar IEEE. ↩

  4. La entropía es el logaritmo en base 2 de la cantidad de posibilidades igualmente probables (cada bit divide los candidatos a la mitad). Como también se puede ver en xkcd nro 936 los bits de entropía se suman solamente cuando las elecciones son independientes. ↩