Your Title - truco 2026-11-15T20:05:32+00:00 http://example.com/tag/truco.html Author Here Cantándole truco al Truco Arbiser 2026-11-15T11:37:00+00:00 http://example.com/cantandole-truco-al-arbiser <blockquote> <p>¡Hasta aquí llegó el olor!</p> </blockquote> <p>Al <a href="#código-fuente">final de este artículo</a> dejé el link para que puedas ver el código fuente del "espiador de cartas".</p> <p>El <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> fue un juego de <code class="language-plaintext highlighter-rouge">Truco</code> 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 <code class="language-plaintext highlighter-rouge">MS-DOS</code>.</p> <p>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 <code class="language-plaintext highlighter-rouge">truco</code> al <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> y reclamar una victoria más del Humano contra la Máquina.</p> <h1 id="el-análisis">El Análisis</h1> <p>Para hacerle trucos al <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a>, primero tenemos que saber antes que nada, en que fue programado.</p> <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> arbiser$</span><span class="w"> </span><span class="nb">ls</span> <span class="go">BRUN40.EXE MWYTRUC@.BAS SIMCGA.COM TRUCO.EXE truco.zip MVYTRUC@ MXYTRUC@ SIMCGA.DOC truco.hexdump VOZ.COM </span><span class="gp">$</span><span class="w"> </span>hexdump <span class="nt">-C</span> TRUCO.EXE |grep <span class="nt">-C5</span> <span class="nt">-i</span> BRUN <span class="go">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 |?...?...&lt;..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 |...&amp;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.&lt;:t.&lt;\t.&lt;/t..| 0000de90 5c aa be 43 00 b9 0b 00 f3 a4 1f ba 55 00 b8 00 |\..C........U...| </span><span class="gp">0000dea0 3d cd 21 c3 b4 3e cd 21 72 01 c3 e9 be fc 00 45 |=.!..&gt;</span>.!r......E| <span class="go">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 -| </span><span class="gp">0000ded0 20 24 4d 65 6d 6f 72 79 20 61 6c 6c 6f 63 61 74 | $</span>Memory allocat| <span class="gp">0000dee0 69 6f 6e 20 65 72 72 6f 72 24 43 61 6e 6e 6f 74 |ion error$</span>Cannot| <span class="go">0000def0 20 66 69 6e 64 20 66 69 6c 65 20 69 6e 20 50 41 | find file in PA| </span><span class="gp">0000df00 54 48 24 44 69 73 6b 20 49 2f 4f 20 65 72 72 6f |TH$</span>Disk I/O erro| <span class="gp">0000df10 72 24 49 6e 76 61 6c 69 64 20 66 6f 72 6d 61 74 |r$</span>Invalid format| <span class="go"> </span></code></pre></div></div> <p>Una búsqueda muy rápida y después de unos fabulosos <code class="language-plaintext highlighter-rouge">hexdump</code>, nos damos cuenta que el archivo <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> que también está en el directorio donde está el juego, está presente. Este archivo, es la librería (biblioteca para los puristas) <code class="language-plaintext highlighter-rouge">runtime</code> de programas compilados con <code class="language-plaintext highlighter-rouge">QuickBasic</code>, un compilador del lenguaje de programación <code class="language-plaintext highlighter-rouge">BASIC</code> creado por Microsoft. La versión particular de este <code class="language-plaintext highlighter-rouge">runtime</code> es la <code class="language-plaintext highlighter-rouge">4.0</code>. A partir de ahora voy a referirme a <code class="language-plaintext highlighter-rouge">QuickBasic 4.0</code> como <code class="language-plaintext highlighter-rouge">QB4</code>.</p> <p><code class="language-plaintext highlighter-rouge">QB4</code> consiste en dos procesadores de lenguaje. El primero, <code class="language-plaintext highlighter-rouge">QB.EXE</code>, mantiene un entorno de programación interactivo. Es un compilador incremental que convierte el código fuente a <code class="language-plaintext highlighter-rouge">threaded p-code</code> y después va ejecutando <code class="language-plaintext highlighter-rouge">p-code</code> de forma interpretativa. El otro, <code class="language-plaintext highlighter-rouge">BC.EXE</code> es un compilador de línea de comando que produce archivos ejecutables nativos.</p> <p>El <code class="language-plaintext highlighter-rouge">threaded p-code</code> es una suerte de <code class="language-plaintext highlighter-rouge">Virtual Machine</code>. Como la JVM por ejemplo. El código generado en <code class="language-plaintext highlighter-rouge">threaded p-code</code> es un <code class="language-plaintext highlighter-rouge">byte code</code> intermedio que es interpretado o bien por el intérprete <code class="language-plaintext highlighter-rouge">QB4</code> o bien por el runtime <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code>.</p> <p>Cada uno de estos compiladores tienen ciertas ventajas, y que pueden ser utilizados dependiendo de diferentes necesidades. El interprete <code class="language-plaintext highlighter-rouge">p-code</code> pierde en velocidad de ejecución a cambio de velocidad de <code class="language-plaintext highlighter-rouge">compilación</code>. Lo que permitía desarrollar mucho más rápido. Recordemos que el <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> 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 <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> es la versión del año 86 (u 87)<sup id="fnref:3"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">1</a></sup>, 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 <code class="language-plaintext highlighter-rouge">VOZ.COM</code> en el zip que ofrece el sitio. Digo esto porque en el sitio del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> se menciona que el módulo de voz fue desarrollado en el año 92 por pedido de una empresa.</p> <p>Entonces la idea era desarrollar muy rápidamente con <code class="language-plaintext highlighter-rouge">p-code</code> y después utilizar el compilador <code class="language-plaintext highlighter-rouge">BC</code> para generar el ejecutable final sin la necesidad que el intérprete esté involucrado.</p> <p>Pero pero pero, la desventaja de este método de desarrollo es que cada compilador produce código diferente. <code class="language-plaintext highlighter-rouge">p-code</code> != <code class="language-plaintext highlighter-rouge">asm x86</code>. Entonces, un programa que funciona bien en el intérprete <code class="language-plaintext highlighter-rouge">QB4</code> funciona joya, pero cuando se compila a código máquina, algunas diferencias de interpretación podían suceder, y el programa "final" crasheaba.</p> <blockquote> <p>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.</p> </blockquote> <p>Entonces, tenemos como conclusiones parciales que:</p> <ul> <li>La versión disponible del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> 5.4, tiene copyright de 1986 y compilada con QB4, es decir, 1987 o posterior<sup id="fnref:3:1"><a href="#fn:3" class="footnote" rel="footnote" role="doc-noteref">1</a></sup>. 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.</li> <li>La presencia de <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> achica aún más las posibilidades. Me ayuda a asumir que el programa fue compilado con <code class="language-plaintext highlighter-rouge">QB4</code> y que se compiló no para que sea un ejecutable autocontenido, sino que en el momento de compilación se utilizó la opción <code class="language-plaintext highlighter-rouge">EXE Requiring BRUN40.EXE</code>.</li> <li>La presencia de <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> en el ejecutable es consistente con mis observaciones.</li> <li>Un programa compilado de esta manera, no se puede desensamblar fácilmente, ya que hay una "VM" de por medio.</li> </ul> <h1 id="el-problema">El Problema</h1> <p>El problema no solo radica en que el ejecutable necesita de un <code class="language-plaintext highlighter-rouge">runtime</code> para interpretar los <code class="language-plaintext highlighter-rouge">byte-codes</code> 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.</p> <p>Podemos asumir que al principio del archivo, hay un <code class="language-plaintext highlighter-rouge">header</code> que va a ser levantado por <code class="language-plaintext highlighter-rouge">MSDOS</code>, que en algún lugar va a guardarse los strings y que en algún otro lugar se va a alojar el código <code class="language-plaintext highlighter-rouge">p-code</code> si todo lo que venimos diciendo fuera correcto.</p> <p>Estoy obviando en este artículo varios intentos de atacar el problema del desensamblado desde diferentes ópticas. Todos fallidos, por supuesto. Intenté desensamblar el <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> con <code class="language-plaintext highlighter-rouge">IDAPro</code> attacheado a un debugger linkeado a una version especial del <code class="language-plaintext highlighter-rouge">DOSBOX</code> y no solamente es inestable, si no que cada dos por tres una <code class="language-plaintext highlighter-rouge">interrupción</code> del procesador se hace presente rompiendo el flujo principal de la ejecución del programa, lo que lo hace <em>inseguible</em>. Lo que si aprendí debuggeando por mucho tiempo, es que hay una tabla de <code class="language-plaintext highlighter-rouge">CALLS</code> que apuntan a <code class="language-plaintext highlighter-rouge">NULL</code> que son patcheadas en <code class="language-plaintext highlighter-rouge">runtime</code> mientras el programa se va ejecutando. Lo que hace que <code class="language-plaintext highlighter-rouge">QB4</code> genere ejecutables que se automodifican; haciendo la tarea de debuggeo muchísimo más difícil.</p> <p>También intenté debuggear usando el <code class="language-plaintext highlighter-rouge">Turbo Debugger</code>, con mejores resultados, pero como se consume mucha memoria (640k ftw!), no logré llegar muy lejos tampoco porque o bien el programa trapeaba un <code class="language-plaintext highlighter-rouge">out of memory</code> o bien simplemente crasheaba mostrando caracteres random en la pantalla.</p> <p>Cuando me refiero a "llegar lejos" hablo de que luego que varias iteraciones de parsear <code class="language-plaintext highlighter-rouge">p-code</code> y patchear direcciones de memoria, nunca llegué siquiera a la función que muestra la pantalla de título del juego.</p> <p>Existe una posibilidad de linkear dos instancias de <code class="language-plaintext highlighter-rouge">dosbox</code> por serial, correr el <code class="language-plaintext highlighter-rouge">Turbo Debugger</code> 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.</p> <p>En definitiva, ir por la opción de debuggear consume tanto tiempo que lo hace impracticable para este caso.<sup id="fnref:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">2</a></sup></p> <h1 id="desensamblador-p-code">Desensamblador P-Code</h1> <p>Entonces se me ocurrió: ¿Qué pasa si en vez de debuggear, escribo un desensamblador? <sup id="fnref:1:1"><a href="#fn:1" class="footnote" rel="footnote" role="doc-noteref">2</a></sup> 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.</p> <h2 id="las-cosas-obvias">Las cosas obvias</h2> <p>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 <code class="language-plaintext highlighter-rouge">BASIC</code>.</p> <p>Entonces, primero escribimos un programa muy sencillo:</p> <p><img src="/assets/images/arbiser/qb_000.png" alt="Un 'Hola Mundo' con una variable" class="img-responsive" /></p> <p>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.</p> <p><img src="/assets/images/arbiser/qb_001.png" alt="Compilamos para que necesite BRUN" class="img-responsive" /></p> <p>Y compilamos una segunda version con este código fuente</p> <p><img src="/assets/images/arbiser/qb_002.png" alt="Compilamos para que necesite BRUN" class="img-responsive" /></p> <h3 id="ieee-754">IEEE 754</h3> <p>Notaran que los cambios entre los dos programas en <code class="language-plaintext highlighter-rouge">BASIC</code> son muy pocos. Habiendo hecho estos cambios, hacemos un diff binario de los dos ejecutables y comparamos que cambios hubo entre ellos:</p> <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> $</span><span class="w"> </span>diff &lt;<span class="o">(</span>xxd HOLA1.EXE<span class="o">)</span> &lt;<span class="o">(</span>xxd HOLA2.EXE<span class="o">)</span> <span class="go">33c33 &lt; 00000200: 626d 484f 4c41 3120 2020 0000 6218 3018 bmHOLA1 ..b.0. --- </span><span class="gp">&gt;</span><span class="w"> </span>00000200: 626d 484f 4c41 3220 2020 0000 6218 3018 bmHOLA2 ..b.0. <span class="go">162,163c162,163 &lt; 00000a10: b200 6017 b00a 0044 1848 6f6c 6120 4d75 ..`....D.Hola Mu &lt; 00000a20: 6e64 6f00 007f 4312 00b2 000e 00b0 ffff ndo...C......... --- </span><span class="gp">&gt;</span><span class="w"> </span>00000a10: b200 6017 b00a 0044 1848 4f4c 4120 4d55 ..<span class="sb">`</span>....D.HOLA MU <span class="gp">&gt;</span><span class="w"> </span>00000a20: 4e44 4f00 00fe 4212 00b2 000e 00b0 ffff NDO...B......... </code></pre></div></div> <p>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.</p> <p>Después de mirar fijo un rato estos números, es fácil darse cuenta que no solamente no son <code class="language-plaintext highlighter-rouge">words</code> sino más bien <code class="language-plaintext highlighter-rouge">doublewords</code> y que el formato de estos números es el de la <code class="language-plaintext highlighter-rouge">IEEE 754</code>. Comparé varios números generados en un nuevo ejecutable con el siguiente código:</p> <div class="language-visualbasic highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">2</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">3</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">4</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">5</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">6</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">7</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">8</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">9</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="mi">0</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">2</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">3</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">4</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">5</span> <span class="n">LET</span> <span class="n">variable</span> <span class="o">=</span> <span class="o">-</span><span class="mi">6</span> </code></pre></div></div> <p>Aqui debajo se pueden ver los valores <code class="language-plaintext highlighter-rouge">dword</code> generados por esta asignación de variables. Podés comparar por vos mismo estos <code class="language-plaintext highlighter-rouge">dword</code> con una calculadora <code class="language-plaintext highlighter-rouge">IEEE 754</code> si querés:</p> <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> $</span><span class="w"> </span>hexdump <span class="nt">-C</span> HOLA5.EXE |grep <span class="nt">-A5</span> ab0 <span class="go">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...| </span></code></pre></div></div> <p>Un ejemplo, el valor <code class="language-plaintext highlighter-rouge">-5</code> representado en <code class="language-plaintext highlighter-rouge">IEEE 754</code> en el offset <code class="language-plaintext highlighter-rouge">0xaf3</code> es <code class="language-plaintext highlighter-rouge">0xc0a00000</code>.</p> <p>Toda esta explicación que estoy haciendo implica que ya sabemos interpretar un tipo de datos generado por el compilador.</p> <h3 id="detectando-headers">Detectando Headers</h3> <p>Todo muy hermoso ¿Pero de qué sirve saber como interpretar un par de <code class="language-plaintext highlighter-rouge">doubles</code> en el binario si no sabemos siquiera en que sección hay que buscarlos?</p> <p>Acá la cosa se va a poner bastante linda, porque por simple observación, si miramos un ejecutable generado por <code class="language-plaintext highlighter-rouge">QB4</code> podemos apreciar que no hay solamente uno, sino <em>dos</em> headers. El primero es obvio que es el header de un <code class="language-plaintext highlighter-rouge">.EXE</code> 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.</p> <div class="language-console highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="gp"> $</span><span class="w"> </span>hexdump <span class="nt">-C</span> HOLA5.EXE |grep <span class="nt">-A5</span> HOLA5 <span class="go">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.| </span></code></pre></div></div> <p>Sospecho que en el offset <code class="language-plaintext highlighter-rouge">0x200</code>, 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.</p> <div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cm">/* bm header */</span> <span class="k">typedef</span> <span class="k">struct</span> <span class="p">{</span> <span class="kt">char</span> <span class="n">id</span><span class="p">[</span><span class="mi">2</span><span class="p">];</span> <span class="c1">// bm for BRUN modules</span> <span class="kt">char</span> <span class="n">module_name</span><span class="p">[</span><span class="mi">8</span><span class="p">];</span> <span class="kt">uint16_t</span> <span class="n">sat</span><span class="p">;</span> <span class="c1">// Statament Address Table</span> <span class="kt">uint16_t</span> <span class="n">ds</span><span class="p">;</span> <span class="c1">// </span> <span class="kt">uint16_t</span> <span class="n">data</span><span class="p">;</span> <span class="c1">// BC_DATA</span> <span class="kt">uint16_t</span> <span class="n">ft</span><span class="p">;</span> <span class="kt">uint16_t</span> <span class="n">icn</span><span class="p">;</span> <span class="c1">// base for icn</span> <span class="kt">uint16_t</span> <span class="n">inc</span><span class="p">;</span> <span class="c1">// base for INIT</span> <span class="kt">uint16_t</span> <span class="n">dsg</span><span class="p">;</span> <span class="c1">// base for DATA (runtime DATA)</span> <span class="kt">uint16_t</span> <span class="n">com</span><span class="p">;</span> <span class="c1">// offset for common</span> <span class="kt">uint16_t</span> <span class="n">sz_com</span><span class="p">;</span> <span class="c1">// size for common</span> <span class="kt">uint16_t</span> <span class="n">uconst</span><span class="p">;</span> <span class="c1">// offset for user const</span> <span class="kt">uint16_t</span> <span class="n">udata</span><span class="p">;</span> <span class="c1">// user data</span> <span class="kt">uint16_t</span> <span class="n">cn</span><span class="p">;</span> <span class="kt">uint16_t</span> <span class="n">sz_frame</span><span class="p">;</span> <span class="kt">uint16_t</span> <span class="n">alloc</span><span class="p">;</span> <span class="c1">// offset heap allocation routine for ISAM</span> <span class="kt">uint16_t</span> <span class="n">seg_alloc</span><span class="p">;</span> <span class="c1">// segment heap allocation routine</span> <span class="kt">uint16_t</span> <span class="n">off_dealloc</span><span class="p">;</span> <span class="c1">// offset heap deallocation routine for ISAM</span> <span class="kt">uint16_t</span> <span class="n">seg_dealloc</span><span class="p">;</span> <span class="c1">// segment heap deallocation routine</span> <span class="kt">int16_t</span> <span class="n">c_switch</span><span class="p">;</span> <span class="c1">// value of /C:n switch, -1 if not given</span> <span class="kt">uint16_t</span> <span class="n">u_flag</span><span class="p">;</span> <span class="c1">// switches specified at compile time</span> <span class="p">}</span> <span class="n">bm_hdr</span><span class="p">;</span> </code></pre></div></div> <h3 id="yendo-por-otros-lados">Yendo por otros lados</h3> <p><code class="language-plaintext highlighter-rouge">BC.EXE</code> que es el <code class="language-plaintext highlighter-rouge">QuickBasic Compiler</code> tiene varios flags que pueden pasarse como parámetros a la hora de compilar. Uno de estos parámetros es el <code class="language-plaintext highlighter-rouge">/a</code> 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.</p> <p>Un ejemplo, el siguiente programa en <code class="language-plaintext highlighter-rouge">BASIC</code> que llamé <code class="language-plaintext highlighter-rouge">FOR.BAS</code>:</p> <div class="language-visualbasic highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">n</span> <span class="o">=</span> <span class="mi">0</span> <span class="n">FOR</span> <span class="n">x</span> <span class="o">=</span> <span class="mi">1</span> <span class="n">TO</span> <span class="mi">16</span><span class="p">:</span> <span class="n">n</span> <span class="o">=</span> <span class="p">(</span><span class="n">n</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="n">x</span> <span class="n">PRINT</span> <span class="s">"N ahora es:"</span><span class="p">,</span> <span class="n">n</span> <span class="n">NEXT</span> <span class="n">x</span> </code></pre></div></div> <p>Genera el siguiente archivo <code class="language-plaintext highlighter-rouge">FOR.LST</code> con el flag <code class="language-plaintext highlighter-rouge">/a</code>:</p> <div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nf">PAGE</span> <span class="mi">1</span> <span class="err">24</span> <span class="nf">Feb</span> <span class="mi">22</span> <span class="err">16</span><span class="p">:</span><span class="err">25</span><span class="p">:</span><span class="err">51</span> <span class="nf">Offset</span> <span class="nv">Data</span> <span class="nv">Source</span> <span class="nv">Line</span> <span class="nv">Microsoft</span> <span class="p">(</span><span class="nv">R</span><span class="p">)</span> <span class="nv">QuickBASIC</span> <span class="nv">Compiler</span> <span class="nv">Version</span> <span class="mf">4.00</span> <span class="err">0030</span> <span class="err">0006</span> <span class="nf">n</span> <span class="err">=</span> <span class="mi">0</span> <span class="err">0030</span> <span class="err">0006</span> <span class="nf">FOR</span> <span class="nv">x</span> <span class="err">=</span> <span class="mi">1</span> <span class="nv">TO</span> <span class="mi">16</span><span class="p">:</span> <span class="err">0030</span> <span class="o">**</span> <span class="nl">I00002:</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0032</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0033</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o">&lt;</span><span class="mi">00000000</span><span class="o">&gt;</span> <span class="err">0035</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0037</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">1Eh</span> <span class="err">0038</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">N</span><span class="err">!</span> <span class="err">003</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span> <span class="err">003</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">35h</span> <span class="err">003</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">06h</span> <span class="err">003</span><span class="nf">F</span> <span class="o">**</span> <span class="nv">dw</span> <span class="o">&lt;</span><span class="mi">0000803</span><span class="nv">F</span><span class="o">&gt;</span> <span class="err">0041</span> <span class="o">**</span> <span class="nf">jmp</span> <span class="nv">I00003</span> <span class="err">0044</span> <span class="err">000</span><span class="nf">A</span> <span class="nv">n</span> <span class="err">=</span> <span class="p">(</span><span class="nv">n</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span> <span class="o">*</span> <span class="nv">x</span> <span class="err">0044</span> <span class="err">000</span><span class="nf">A</span> <span class="nv">PRINT</span> <span class="s">"N ahora es:"</span><span class="p">,</span> <span class="nv">n</span> <span class="err">0044</span> <span class="err">000</span><span class="nf">A</span> <span class="nv">NEXT</span> <span class="nv">x</span> <span class="err">0044</span> <span class="o">**</span> <span class="nl">I00004:</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0046</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0047</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">N</span><span class="err">!</span> <span class="err">0049</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">34h</span> <span class="err">004</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">06h</span> <span class="err">004</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">dw</span> <span class="o">&lt;</span><span class="mi">0000803</span><span class="nv">F</span><span class="o">&gt;</span> <span class="err">004</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">34h</span> <span class="err">0050</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">0Eh</span> <span class="err">0051</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">X</span><span class="err">!</span> <span class="err">0053</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0055</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">1Eh</span> <span class="err">0056</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">N</span><span class="err">!</span> <span class="err">0058</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">3Dh</span> <span class="err">005</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span><span class="nv">offset</span> <span class="o">&lt;</span><span class="nv">const</span><span class="o">&gt;</span> <span class="err">005</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">push</span> <span class="nb">ax</span> <span class="err">005</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">call</span> <span class="nv">B$PCSD</span> <span class="err">0063</span> <span class="o">**</span> <span class="nf">push</span> <span class="nv">N</span><span class="err">!</span><span class="o">+</span><span class="mh">0002h</span> <span class="err">0067</span> <span class="o">**</span> <span class="nf">push</span> <span class="nv">N</span><span class="err">!</span> <span class="err">006</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">call</span> <span class="nv">B$PER4</span> <span class="err">0070</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0072</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0073</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">X</span><span class="err">!</span> <span class="err">0075</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">34h</span> <span class="err">0077</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0078</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o">&lt;</span><span class="mi">0000803</span><span class="nv">F</span><span class="o">&gt;</span> <span class="err">007</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">I00003</span><span class="p">:</span> <span class="nv">int</span> <span class="mh">35h</span> <span class="err">007</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">1Eh</span> <span class="err">007</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">dw</span> <span class="nv">X</span><span class="err">!</span> <span class="err">007</span><span class="nf">F</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span> <span class="err">0081</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0083</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0084</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o">&lt;</span><span class="mi">00008041</span><span class="o">&gt;</span> <span class="err">0086</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0088</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0089</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">X</span><span class="err">!</span> <span class="err">008</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span> <span class="err">008</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">call</span> <span class="nv">B$FCMP</span> <span class="err">0092</span> <span class="o">**</span> <span class="nf">jna</span> <span class="kc">$</span><span class="o">-</span><span class="mh">50h</span> <span class="nf">PAGE</span> <span class="mi">2</span> <span class="err">24</span> <span class="nf">Feb</span> <span class="mi">22</span> <span class="err">16</span><span class="p">:</span><span class="err">25</span><span class="p">:</span><span class="err">51</span> <span class="nf">Offset</span> <span class="nv">Data</span> <span class="nv">Source</span> <span class="nv">Line</span> <span class="nv">Microsoft</span> <span class="p">(</span><span class="nv">R</span><span class="p">)</span> <span class="nv">QuickBASIC</span> <span class="nv">Compiler</span> <span class="nv">Version</span> <span class="mf">4.00</span> <span class="err">0094</span> <span class="err">000</span><span class="nf">E</span> <span class="err">0094</span> <span class="err">000</span><span class="nf">E</span> <span class="err">0094</span> <span class="err">000</span><span class="nf">E</span> <span class="err">0094</span> <span class="err">000</span><span class="nf">E</span> <span class="err">0094</span> <span class="o">**</span> <span class="nf">call</span> <span class="nv">B$CENP</span> <span class="err">0099</span> <span class="err">000</span><span class="nf">E</span> <span class="err">44108</span> <span class="kt">Byte</span><span class="nf">s</span> <span class="nv">Available</span> <span class="err">43555</span> <span class="kt">Byte</span><span class="nf">s</span> <span class="nv">Free</span> <span class="err">0</span> <span class="nf">Warning</span> <span class="nv">Error</span><span class="p">(</span><span class="nv">s</span><span class="p">)</span> <span class="err">0</span> <span class="nf">Severe</span> <span class="nv">Error</span><span class="p">(</span><span class="nv">s</span><span class="p">)</span> </code></pre></div></div> <p>Y finalmente, la sección relevante del binario <code class="language-plaintext highlighter-rouge">FOR.EXE</code>:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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 |................| </code></pre></div></div> <p>A partir de <code class="language-plaintext highlighter-rouge">0x230</code> se puede ver que cada opcode correlaciona con el listado <code class="language-plaintext highlighter-rouge">FOR.LST</code>! 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.</p> <p>Si esto es razonable, se podría reconstruir parcialmente el código original del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> y luego de tener el código razonablemente desensamblado, podriamos analizarlo para descubrir sus secretos posteriormente.</p> <h2 id="escribiendo-un-parser-e-interpretando-tokens">Escribiendo un parser e interpretando tokens</h2> <h3 id="encontrando-nombres-de-función">Encontrando nombres de función</h3> <p>Cuando generamos un <code class="language-plaintext highlighter-rouge">LST</code>, en cada opcode <code class="language-plaintext highlighter-rouge">call</code> el compilador de Microsoft nos da la nomenclatura usada por el runtime de la siguiente manera, por ejemplo:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code> [...] (fragmento de FOR.LST) 005A ** mov ax,offset &lt;const&gt; 005D ** push ax 005E ** call B$PCSD 0063 ** push N!+0002h 0067 ** push N! 006B ** call B$PER4 [...] </code></pre></div></div> <p>Cuando parseamos los opcodes, cada vez que encuentro un <code class="language-plaintext highlighter-rouge">call</code>, me fijo la dirección a la cual se está llamando y comparo el <code class="language-plaintext highlighter-rouge">LWORD</code> descartando el <code class="language-plaintext highlighter-rouge">HWORD</code>. Hago esto de manera arbitraria, ya que por ahora funciona bastante bien. No se exactamente que representa <code class="language-plaintext highlighter-rouge">HWORD</code> todavía:</p> <div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="p">[...]</span> <span class="n">fragmento</span> <span class="n">de</span> <span class="nf">bm_get_call_mnemonic</span><span class="p">(</span><span class="kt">char</span><span class="o">*</span><span class="p">)</span> <span class="kt">uint16_t</span> <span class="n">current_lword</span> <span class="o">=</span> <span class="p">(</span><span class="kt">uint16_t</span><span class="p">)(</span><span class="n">current_dword</span> <span class="o">&amp;</span> <span class="mh">0xffff</span><span class="p">);</span> <span class="k">switch</span> <span class="p">(</span><span class="n">current_lword</span><span class="p">)</span> <span class="p">{</span> <span class="p">[...]</span> <span class="k">case</span> <span class="mh">0x0140</span><span class="p">:</span> <span class="n">strcpy</span><span class="p">(</span><span class="o">&amp;</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$PCSD - Print a$,"</span><span class="p">);</span> <span class="k">break</span><span class="p">;</span> <span class="k">case</span> <span class="mh">0x014c</span><span class="p">:</span> <span class="n">strcpy</span><span class="p">(</span><span class="o">&amp;</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$PER4 - Print R4 (Single precision real (sp))"</span><span class="p">);</span> <span class="k">break</span><span class="p">;</span> <span class="p">[...]</span> </code></pre></div></div> <p>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:</p> <div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="err">0</span><span class="nf">x025a</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="nv">offset</span> <span class="mh">0x1858</span> <span class="err">0</span><span class="nf">x025d</span> <span class="nv">push</span> <span class="nb">ax</span> <span class="err">0</span><span class="nf">x025e</span> <span class="nv">call</span> <span class="nv">B$PCSD</span> <span class="o">-</span> <span class="nv">Print</span> <span class="nv">a$</span><span class="p">,</span> <span class="o">&lt;</span><span class="mh">0x000a0140</span><span class="o">&gt;</span> <span class="err">0</span><span class="nf">x0263</span> <span class="nv">push</span> <span class="o">&lt;</span><span class="mh">0x1838</span><span class="o">&gt;</span> <span class="p">(</span><span class="nv">modr</span><span class="p">:</span><span class="mh">0x36</span><span class="p">)</span> <span class="err">0</span><span class="nf">x0267</span> <span class="nv">push</span> <span class="o">&lt;</span><span class="mh">0x1836</span><span class="o">&gt;</span> <span class="p">(</span><span class="nv">modr</span><span class="p">:</span><span class="mh">0x36</span><span class="p">)</span> <span class="err">0</span><span class="nf">x026b</span> <span class="nv">call</span> <span class="nv">B$PER4</span> <span class="o">-</span> <span class="nv">Print</span> <span class="nv">R4</span> <span class="p">(</span><span class="nb">Si</span><span class="nv">ngle</span> <span class="nv">precision</span> <span class="nv">real</span> <span class="p">(</span><span class="nb">sp</span><span class="p">))</span> <span class="o">&lt;</span><span class="mh">0x000a014c</span><span class="o">&gt;</span> </code></pre></div></div> <p>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.</p> <p>Esto significa, que mientras más programas haga, más funciones encuentro gracias al <code class="language-plaintext highlighter-rouge">LST</code> 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.</p> <p>Esto, demanda muchísimo tiempo. Como el objetivo es hacerle truco al <code class="language-plaintext highlighter-rouge">Truco Arbiser</code>, 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.</p> <h3 id="emulación-de-punto-flotante">Emulación de punto flotante</h3> <p>¡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".</p> <p>Lo pongo entre comillas, porque en verdad QB4 no estaría usando exactamente opcodes de la <code class="language-plaintext highlighter-rouge">FPU</code> sino más bien, usa una especie de emulación, que esta definida de la siguiente forma:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>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 </code></pre></div></div> <p>Tiene sentido. En esa época, tener una <code class="language-plaintext highlighter-rouge">FPU</code> 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.</p> <p>Llegar a esta lista, y saber por qué la necesitaba me llevó bastante tiempo. Veamos el siguiente pedazo de desensamblado:</p> <div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nl">BASIC:</span> <span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">2</span> <span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">3</span> <span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">4</span> <span class="nf">LET</span> <span class="nv">variable</span> <span class="err">=</span> <span class="mi">5</span> <span class="nf">QuickBasic</span> <span class="nv">.LST</span><span class="p">:</span> <span class="err">0039</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">003</span><span class="nf">B</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">06h</span> <span class="err">003</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">dw</span> <span class="o">&lt;</span><span class="mi">00000040</span><span class="o">&gt;</span> <span class="err">003</span><span class="nf">E</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">35h</span> <span class="err">0040</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">1Eh</span> <span class="err">0041</span> <span class="o">**</span> <span class="kd">dw</span> <span class="nv">VARIABLE</span><span class="err">!</span> <span class="err">0043</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">3Dh</span> <span class="err">0045</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0047</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0048</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o">&lt;</span><span class="mi">00004040</span><span class="o">&gt;</span> <span class="err">004</span><span class="nf">A</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">35h</span> <span class="err">004</span><span class="nf">C</span> <span class="o">**</span> <span class="nv">db</span> <span class="mh">1Eh</span> <span class="err">004</span><span class="nf">D</span> <span class="o">**</span> <span class="nv">dw</span> <span class="nv">VARIABLE</span><span class="err">!</span> <span class="err">004</span><span class="nf">F</span> <span class="o">**</span> <span class="nv">int</span> <span class="mh">3Dh</span> <span class="err">0051</span> <span class="o">**</span> <span class="nf">int</span> <span class="mh">35h</span> <span class="err">0053</span> <span class="o">**</span> <span class="kd">db</span> <span class="mh">06h</span> <span class="err">0054</span> <span class="o">**</span> <span class="kd">dw</span> <span class="o">&lt;</span><span class="mi">00008040</span><span class="o">&gt;</span> </code></pre></div></div> <p>Entonces, existe una relación entre las <code class="language-plaintext highlighter-rouge">INTerrupciones</code>, los <code class="language-plaintext highlighter-rouge">db</code>, los <code class="language-plaintext highlighter-rouge">dw</code> que en el binario eran offsets con los numeros <code class="language-plaintext highlighter-rouge">LST</code> 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! ¡<code class="language-plaintext highlighter-rouge">IEEE754</code>! <sup id="fnref:2"><a href="#fn:2" class="footnote" rel="footnote" role="doc-noteref">3</a></sup></p> <p>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.</p> <h3 id="offsets-y-bloques">Offsets y bloques</h3> <p>¿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…?</p> <p>Ni idea todavia :D</p> <h3 id="bfuncname">B$&lt;funcname&gt;</h3> <p>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 <code class="language-plaintext highlighter-rouge">45/runtime/rt</code> hay muchísimas definiciones de llamadas al <code class="language-plaintext highlighter-rouge">runtime</code> 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:</p> <div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="p">[...]</span> <span class="k">case</span> <span class="mh">0x0185</span><span class="p">:</span> <span class="n">strcpy</span><span class="p">(</span><span class="o">&amp;</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$SASS - String assignment"</span><span class="p">);</span> <span class="k">break</span><span class="p">;</span> <span class="k">case</span> <span class="mh">0x00f5</span><span class="p">:</span> <span class="n">strcpy</span><span class="p">(</span><span class="o">&amp;</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$INPP -- console input preamble"</span><span class="p">);</span> <span class="k">break</span><span class="p">;</span> <span class="k">case</span> <span class="mh">0x0170</span><span class="p">:</span> <span class="n">strcpy</span><span class="p">(</span><span class="o">&amp;</span><span class="n">func_name</span><span class="p">,</span> <span class="s">"B$RDSD -- console input read String Descriptor"</span><span class="p">);</span> <span class="k">break</span><span class="p">;</span> <span class="p">[...]</span> </code></pre></div></div> <p>El procedimiento es:</p> <ul> <li>Compilar un programa en <code class="language-plaintext highlighter-rouge">BASIC</code></li> <li>Pedirle a <code class="language-plaintext highlighter-rouge">BC.EXE</code> que nos genere un <code class="language-plaintext highlighter-rouge">.LST</code></li> <li>Tomar las <code class="language-plaintext highlighter-rouge">call</code>s al runtime, y buscar la definición en el source del msdos6.0</li> <li>Leer la doc, y escribir la definicion del offset del call de mi desensamblador (que tagueo con el keyword <code class="language-plaintext highlighter-rouge">unknown</code> si no lo tengo parseado)</li> </ul> <p>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 <strong>por acá no es</strong>.</p> <h1 id="un-giro-inesperado">Un Giro Inesperado</h1> <p>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.</p> <p>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.</p> <p>Decidí apoyarme en <a href="https://www.capstone-engine.org/">Capstone Engine</a> y empezar a automatizar esta comparacion de <code class="language-plaintext highlighter-rouge">segment:offset</code> de cada <code class="language-plaintext highlighter-rouge">CALL</code> con los listados que escupe el compilador QB4 y matchearlos con mi desensamblador.</p> <p>Escencialmente:</p> <ul> <li>interpretar y comparar offsets con pares lcall/call updateando los strings de llamadas de función.</li> <li>armar una tabla de funciones que ya haya descubierto</li> <li><strong>rinse and repeat ad infinitum</strong></li> </ul> <p>Todo este esfuerzo, dio cierto grado de frutos. Pude de alguna manera desensamblar pedazos de programas compilados con Quick Basic 4.0 usando su <strong>runtime</strong> y eventualmente iba a llegar a tener un <strong>Señor Desensamblador</strong> que podía llegar a ser útil en un futuro para desensamblar programas viejos <strong>à là HexRays</strong>.</p> <p>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 <strong>Truquear al Truco</strong> y espiralé en hacer toda una suite de desensamblado de P-Code.</p> <p>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.</p> <p>Este camino, era el que me iba a llevar a romperlo finalmente <strong>y era por acá</strong>.</p> <h1 id="análisis-de-estructuras-en-memoria">Análisis de Estructuras en Memoria</h1> <p>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.</p> <p>Al año, entonces, me pongo a reversear y llego a una tabla decente para tener ciertos breakpoints que valgan la pena:</p> <table> <thead> <tr> <th>segment:offset memoria</th> <th>segment:offset desensamblado</th> <th>longitud</th> <th>descripcion</th> </tr> </thead> <tbody> <tr> <td>seg004:fa94</td> <td>[si+1c72]</td> <td>WORD*6 + 1</td> <td>jugador words, palo 1 palo 2 palo 3 – nada – carta 1, 2, 3</td> </tr> <tr> <td>seg004:f66a</td> <td>[si+1848]</td> <td>WORD*6 + 1</td> <td>computadora words, palo 1 palo 2 palo 3 – nada - carta 1, 2, 3</td> </tr> <tr> <td>seg004:f680</td> <td>[si+1860]</td> <td>WORD*3</td> <td>random numbers placeholder/save area</td> </tr> <tr> <td>seg004:fae4</td> <td>ds:1cc4</td> <td>WORD</td> <td>random number</td> </tr> <tr> <td>seg004:fb90</td> <td>ds:1d70</td> <td>WORD</td> <td>current_card being calculated for player</td> </tr> <tr> <td>seg004:fb92</td> <td>ds:1d72</td> <td>WORD</td> <td>current_card being calculated for computer</td> </tr> <tr> <td>seg004:fb02</td> <td>ds:1ce2h</td> <td>WORD</td> <td>last card number processed (player)</td> </tr> <tr> <td>seg004:fb04</td> <td>???</td> <td>DWORD</td> <td>???????????????????????????</td> </tr> <tr> <td>seg004:fb06</td> <td>???</td> <td>DWORD</td> <td>???????????????????????????</td> </tr> <tr> <td>seg004:fb08</td> <td>???</td> <td>DWORD</td> <td>???????????????????????????</td> </tr> <tr> <td>seg004:fb0a</td> <td>???</td> <td>WORD</td> <td>ultimo palo procesado (player)</td> </tr> <tr> <td>seg005:12d3</td> <td>ds:2836-ds:283a</td> <td>WORD</td> <td>STACK! BP/SP en seg005, es el numero que recibe AX para muchas operaciones relacionadas con las funciones random</td> </tr> <tr> <td>021e:e6fb</td> <td>ds:8db</td> <td>WORD</td> <td>Low WORD of previous <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> seed</td> </tr> <tr> <td>021e:e6fd</td> <td>ds:8dd</td> <td>WORD</td> <td>Hi WORD of previous <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> seed</td> </tr> <tr> <td>????</td> <td>021e:e020</td> <td>WORD</td> <td>A Constant QB4.0 <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a></td> </tr> <tr> <td>????</td> <td>021e:e024</td> <td>BYTE</td> <td>C Constant QB4.0 <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a></td> </tr> <tr> <td>????</td> <td>021e:de20</td> <td>DWORD</td> <td>float storage area?</td> </tr> </tbody> </table> <p>Palos:</p> <table> <thead> <tr> <th>Palo</th> <th>EQU</th> </tr> </thead> <tbody> <tr> <td>Espada</td> <td>0x0000</td> </tr> <tr> <td>Basto</td> <td>0x0001</td> </tr> <tr> <td>Oro</td> <td>0x0002</td> </tr> <tr> <td>Copa</td> <td>0x0003</td> </tr> </tbody> </table> <p>También descubrí algunos detalles importantes que en el código binario y sus estructuras de datos:</p> <ul> <li>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)</li> <li>si la carta seleccionada es mayor a 7, entonces le sumamos 2 asi corregimos como se tienen que ver en realidad.</li> <li>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</li> </ul> <p>¡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.</p> <h2 id="pseudo-random-number-generator-prng">Pseudo Random Number Generator (PRNG)</h2> <p>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 <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>:</p> <div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CB7</span> <span class="c1">; ---------------------------------------------------------------------------</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CB7</span> <span class="nv">push</span> <span class="nb">di</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CB8</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CBB</span> <span class="nv">mov</span> <span class="nb">cx</span><span class="p">,</span> <span class="kt">word</span><span class="nv">_200</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CBF</span> <span class="nv">mul</span> <span class="nb">cx</span> <span class="c1">; Unsigned Multiplication of AL or AX</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CC1</span> <span class="nv">xchg</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">di</span> <span class="c1">; Exchange Register/Memory with Register</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CC2</span> <span class="nv">mov</span> <span class="nb">bx</span><span class="p">,</span> <span class="nb">dx</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CC4</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DDh</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CC7</span> <span class="nv">mul</span> <span class="nb">cx</span> <span class="c1">; Unsigned Multiplication of AL or AX</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CC9</span> <span class="nv">add</span> <span class="nb">bx</span><span class="p">,</span> <span class="nb">ax</span> <span class="c1">; Add</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CCB</span> <span class="nv">mov</span> <span class="nb">ax</span><span class="p">,</span> <span class="kt">word</span><span class="nv">_200</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CCE</span> <span class="nv">mul</span> <span class="kt">word</span> <span class="nv">ptr</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span> <span class="c1">; Unsigned Multiplication of AL or AX</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CD2</span> <span class="nv">add</span> <span class="nb">bx</span><span class="p">,</span> <span class="nb">ax</span> <span class="c1">; Add</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CD4</span> <span class="nv">add</span> <span class="nb">di</span><span class="p">,</span> <span class="kt">word</span><span class="nv">_204</span> <span class="c1">; Add</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CD8</span> <span class="nv">adc</span> <span class="nb">bl</span><span class="p">,</span> <span class="kt">byte</span> <span class="nv">ptr</span> <span class="kt">word</span><span class="nv">_204</span> <span class="c1">; Add with Carry</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CDC</span> <span class="nv">xor</span> <span class="nb">bh</span><span class="p">,</span> <span class="nb">bh</span> <span class="c1">; Logical Exclusive OR</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CDE</span> <span class="nv">mov</span> <span class="nb">dx</span><span class="p">,</span> <span class="nb">di</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CE0</span> <span class="nv">mov</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span><span class="p">,</span> <span class="nb">dx</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CE4</span> <span class="nv">mov</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DDh</span><span class="p">,</span> <span class="nb">bx</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CE8</span> <span class="nv">pop</span> <span class="nb">di</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CE9</span> <span class="nv">nop</span> <span class="c1">; No Operation</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CEA</span> <span class="nv">fild</span> <span class="kt">dword</span> <span class="nv">ptr</span> <span class="nb">ds</span><span class="p">:</span><span class="mh">8DBh</span> <span class="c1">; Load Integer</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CEE</span> <span class="nv">nop</span> <span class="c1">; No Operation</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CEF</span> <span class="nv">fdiv</span> <span class="nv">flt_208</span> <span class="c1">; Divide Real</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CF3</span> <span class="nv">mov</span> <span class="nb">bx</span><span class="p">,</span> <span class="mh">0EDh</span> <span class="c1">; 'f'</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CF6</span> <span class="nv">nop</span> <span class="c1">; No Operation</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CF7</span> <span class="nb">fs</span><span class="nv">tp</span> <span class="kt">dword</span> <span class="nv">ptr</span> <span class="p">[</span><span class="nb">bx</span><span class="p">]</span> <span class="c1">; Store Real and Pop</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CF9</span> <span class="nv">xchg</span> <span class="nb">ax</span><span class="p">,</span> <span class="nb">bx</span> <span class="c1">; Exchange Register/Memory with Register</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CFA</span> <span class="nv">nop</span> <span class="c1">; No Operation</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CFB</span> <span class="nv">wait</span> <span class="c1">; Wait until BUSY# Pin is Inactive (HIGH)</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CFC</span> <span class="nv">retn</span> <span class="c1">; Return Near from Procedure</span> <span class="nl">.text:</span><span class="err">98</span><span class="nf">CFC</span> <span class="c1">; ---------------------------------------------------------------------------</span> </code></pre></div></div> <p>Como esta sección de código esta en <code class="language-plaintext highlighter-rouge">.text</code> asumí que era un algoritmo escrito por los Arbiser y no que era parte del <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code>. Bastaba con notar que estábamos en otro segmento mirando el offset de <code class="language-plaintext highlighter-rouge">.text</code> y listo, pero noooo. ¿Recuerdan que el source del MSDOS fue leakeado? Bueno, a veces uno al experimentar <strong>visión de tunel</strong> se puede olvidar que tiene otros ángulos para atacar un mismo problema, en el leak me encuentro esto:</p> <div class="language-nasm highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1">; 45 &gt; runtime &gt; rt &gt; random.asm:240</span> <span class="c1">;***</span> <span class="c1">;GetNextRnd -- get next random number</span> <span class="c1">;MakeFloat -- make the number in [b$RndVar] into a R4</span> <span class="c1">;</span> <span class="c1">;Purpose:</span> <span class="c1">; Get next random number in sequence.</span> <span class="c1">;Entry:</span> <span class="c1">; [b$RndVar] has the seed.</span> <span class="c1">;Exit:</span> <span class="c1">; [AX] = *B$AC which contains the R4 result</span> <span class="c1">;Exceptions:</span> <span class="c1">; none</span> <span class="c1">;*******************************************************************************</span> <span class="nf">cProc</span> <span class="nv">GetNextRnd</span><span class="p">,</span><span class="o">&lt;</span><span class="nv">NEAR</span><span class="o">&gt;</span> <span class="nf">cBegin</span> <span class="nf">PUSH</span> <span class="nb">DI</span> <span class="nf">MOV</span> <span class="nb">AX</span><span class="p">,[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="p">]</span> <span class="c1">;low half of previous number</span> <span class="nf">MOV</span> <span class="nb">CX</span><span class="p">,[</span><span class="nv">RndA</span><span class="p">]</span> <span class="c1">;low half of A</span> <span class="nf">MUL</span> <span class="nb">CX</span> <span class="nf">XCHG</span> <span class="nb">AX</span><span class="p">,</span><span class="nb">DI</span> <span class="c1">;save low half in DI</span> <span class="nf">MOV</span> <span class="nb">BX</span><span class="p">,</span><span class="nb">DX</span> <span class="c1">; high half in BX</span> <span class="nf">MOV</span> <span class="nb">AX</span><span class="p">,[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="o">+</span><span class="mi">2</span><span class="p">]</span> <span class="c1">;high half of previous</span> <span class="nf">MUL</span> <span class="nb">CX</span> <span class="nf">ADD</span> <span class="nb">BX</span><span class="p">,</span><span class="nb">AX</span> <span class="c1">;sum partial products</span> <span class="nf">MOV</span> <span class="nb">AX</span><span class="p">,[</span><span class="nv">RndA</span><span class="p">]</span> <span class="nf">MUL</span> <span class="p">[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="p">]</span> <span class="nf">ADD</span> <span class="nb">BX</span><span class="p">,</span><span class="nb">AX</span> <span class="c1">;last partial product (since we're mod 2^24)</span> <span class="nf">ADD</span> <span class="nb">DI</span><span class="p">,[</span><span class="nv">RndC</span><span class="p">]</span> <span class="c1">;add in constant C</span> <span class="nf">ADC</span> <span class="nb">BL</span><span class="p">,</span><span class="kt">BYTE</span> <span class="nv">PTR</span> <span class="p">[</span><span class="nv">RndC</span><span class="p">]</span> <span class="nf">XOR</span> <span class="nb">BH</span><span class="p">,</span><span class="nb">BH</span> <span class="c1">;extended 24-bit number to 32 bits for NORM</span> <span class="nf">MOV</span> <span class="nb">DX</span><span class="p">,</span><span class="nb">DI</span> <span class="c1">;number in BX:DX</span> <span class="nf">MOV</span> <span class="p">[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="p">],</span><span class="nb">DX</span> <span class="c1">;save for next time</span> <span class="nf">MOV</span> <span class="p">[</span><span class="kt">WORD</span> <span class="nv">PTR</span> <span class="nv">b$RndVar</span><span class="o">+</span><span class="mi">2</span><span class="p">],</span><span class="nb">BX</span> <span class="nf">POP</span> <span class="nb">DI</span> <span class="nl">MakeFloat:</span> <span class="nf">FILD</span> <span class="nv">b$RndVar</span> <span class="c1">; put 24-bit integer on numeric stack</span> <span class="nf">FDIV</span> <span class="nv">FP_2T24</span> <span class="c1">; ST0 = seed/2^24</span> <span class="nf">MOV</span> <span class="nb">BX</span><span class="p">,</span><span class="nv">OFFSET</span> <span class="nv">DGROUP</span><span class="p">:</span><span class="nv">B$AC</span> <span class="nf">FSTP</span> <span class="kt">DWORD</span> <span class="nv">PTR</span> <span class="p">[</span><span class="nb">BX</span><span class="p">]</span> <span class="c1">; put s.p. equivalent into FAC</span> <span class="nf">XCHG</span> <span class="nb">AX</span><span class="p">,</span><span class="nb">BX</span> <span class="c1">; result is *R4 in AX</span> <span class="nf">FWAIT</span> <span class="c1">; ensure result in RAM prior to return</span> <span class="nf">cEnd</span> <span class="c1">; exit to caller</span> </code></pre></div></div> <p>¡Es la misma sección de código! Y es exactamente el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>. No me puse a ver exactamente porque era que parte del runtime estaba en <code class="language-plaintext highlighter-rouge">.text</code> 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 <code class="language-plaintext highlighter-rouge">TRUCO.EXE</code> estaba en un segmento y el <code class="language-plaintext highlighter-rouge">BRUN40.EXE</code> en otro.</p> <p>El festejo no duró demasiado. Al identificar entonces donde estaba el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> entonces corri un pequeño programa en <code class="language-plaintext highlighter-rouge">QB4</code> y su ejecutable, en ambos, no usando <code class="language-plaintext highlighter-rouge">RANDOMIZE</code> para tener el mismo valor del <strong>seed</strong> en todas las ejecuciones.</p> <div class="language-bash highlighter-rouge"><div class="highlight"><pre class="highlight"><code>print rnd print rnd print rnd print rnd print rnd </code></pre></div></div> <p>Los resultados del intérprete <code class="language-plaintext highlighter-rouge">QB4</code> y los ejecutables que generaba el compilador eran <strong>DISTINTOS</strong>. 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.</p> <p><img src="/assets/images/arbiser/qb_003.png" alt="rnd es el ejecutable - la segunda corrida es desde el interprete" title="rnd es el ejecutable - la segunda corrida es desde el interprete" class="img-responsive" /></p> <p>Después de una larga pausa, continué implementando en C una librería para poder acceder con CTypes en Python al <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> de <code class="language-plaintext highlighter-rouge">QB4</code>. La idea de tener esta sección separada de <code class="language-plaintext highlighter-rouge">QB4</code> era poder usar otros lenguajes para hacer experimentos y entender bien que propiedades podia llegar a tener este <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a>. La idea era poder usar <strong>Python</strong> en vez de <strong>Quick Basic</strong> para sacar ideas y propiedades de este <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> en particular.</p> <p><img src="/assets/images/arbiser/prng_poc.png" alt="RND en RND.EXE y en mi implementación" class="img-responsive" /><em>El output en MSDOS y en mi implementación en C</em></p> <p>Una nota de color, es que el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> 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.</p> <p><img src="/assets/images/arbiser/truco_prediccion.png" alt="Predicción parcial" class="img-responsive" /></p> <p>Más o menos, como que ya tengo el <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> andando, estuve tratando de encontrar el seed. Mi proceso fue durante un tiempo estar habiendo identificado donde estaba escribiéndose el valor del <strong>seed</strong> del <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> y verificar a mano cada <code class="language-plaintext highlighter-rouge">mano</code> el valor del <strong>seed</strong> en memoria, y correr un script en Python para calcular la mano de la CPU.</p> <p>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 <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a>. Pasé muchísimo tiempo debuggeando, o tratando de debuggear en cada caso cual era el número de veces que se avanzaba al siguiente <a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a> 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.</p> <p>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 <code class="language-plaintext highlighter-rouge">get_random</code> y lo abandoné por un tiempo, hasta que…</p> <h1 id="pero-para-que-verga-tenés-una-pc-entonces">¿Pero para que verga tenés una PC, entonces?</h1> <p>Discutiendo el problema del <a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a> con algunos amigos y contándoles mi frustración con el debugging, les muestro esta sección de código del <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a>:</p> <div class="language-c highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="cm">/* # 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 */</span> <span class="kt">float</span> <span class="nf">ms_rnd_formula</span><span class="p">(</span><span class="kt">uint32_t</span> <span class="o">*</span><span class="n">prev_rnd</span><span class="p">)</span> <span class="p">{</span> <span class="c1">// a and c constant values are found at 021e:e020 as </span> <span class="c1">// FD 43 03 00 =&gt; A </span> <span class="c1">// C3 9E 26 00 =&gt; C</span> <span class="kt">uint32_t</span> <span class="n">a</span> <span class="o">=</span> <span class="mi">214013</span><span class="p">;</span> <span class="c1">// 0x343fd</span> <span class="kt">uint32_t</span> <span class="n">c</span> <span class="o">=</span> <span class="mi">2531011</span><span class="p">;</span> <span class="c1">// 0x269ec3</span> <span class="kt">float</span> <span class="n">x1</span><span class="p">;</span> <span class="kt">uint32_t</span> <span class="n">p</span><span class="p">;</span> <span class="n">p</span> <span class="o">=</span> <span class="n">pow</span><span class="p">(</span><span class="mi">2</span><span class="p">,</span><span class="mi">24</span><span class="p">);</span> <span class="n">x1</span> <span class="o">=</span> <span class="p">((</span><span class="o">*</span><span class="n">prev_rnd</span> <span class="o">*</span> <span class="n">a</span><span class="p">)</span> <span class="o">+</span> <span class="n">c</span><span class="p">)</span> <span class="o">%</span> <span class="n">p</span><span class="p">;</span> <span class="o">*</span><span class="n">prev_rnd</span> <span class="o">=</span> <span class="n">x1</span><span class="p">;</span> <span class="k">return</span> <span class="n">x1</span> <span class="o">/</span> <span class="n">p</span><span class="p">;</span> <span class="p">}</span> </code></pre></div></div> <p>A lo que uno me pregunta:</p> <p>– ¿Por qué no <strong>precalculás</strong> 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?</p> <p>– 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!</p> <h2 id="mulero">Mulero</h2> <p><img src="/assets/images/arbiser/mulero.png" alt="Mulero TUI" class="img-responsive" /><em>La interfaz de texto de Mulero</em></p> <h3 id="dándole-vueltas-y-vueltas-al-ciclo-del-lcg">Dándole vueltas y vueltas al ciclo del LCG</h3> <p>El <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> de <code class="language-plaintext highlighter-rouge">QB4</code> como venimos diciendo una y otra vez tiene la forma:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>estado = (estado * A + C) mod 2^24 RND = estado / 2^24 </code></pre></div></div> <p>Las constantes efectivas son <code class="language-plaintext highlighter-rouge">A = 0xfd43fd</code> y <code class="language-plaintext highlighter-rouge">C = 0xc39ec3</code>. 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 <a href="https://codeberg.org/toshi/mulero">README</a> del repositorio.</p> <p>Revisando patrones de generadores de números random y sus problemas me topé entre varias cosas más, con el <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0">teorema de Hull-Dobell</a> que dice que un <a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a> con módulo <code class="language-plaintext highlighter-rouge">m</code> recorre <strong>todos</strong> sus <code class="language-plaintext highlighter-rouge">m</code> estados antes de repetirse si y solo si:</p> <ol> <li><code class="language-plaintext highlighter-rouge">C</code> y <code class="language-plaintext highlighter-rouge">m</code> son coprimos.</li> <li><code class="language-plaintext highlighter-rouge">A - 1</code> es divisible por todos los primos que dividen a <code class="language-plaintext highlighter-rouge">m</code>.</li> <li><code class="language-plaintext highlighter-rouge">A - 1</code> es divisible por 4 si <code class="language-plaintext highlighter-rouge">m</code> lo es.</li> </ol> <p>Acá <code class="language-plaintext highlighter-rouge">m = 2^24</code>, así que el único primo es 2 y las condiciones se reducen a <strong><code class="language-plaintext highlighter-rouge">C</code> impar</strong> y <strong><code class="language-plaintext highlighter-rouge">A ≡ 1 (mod 4)</code></strong>. Las constantes cumplen las dos: <code class="language-plaintext highlighter-rouge">0xc3</code> es impar y <code class="language-plaintext highlighter-rouge">0xfd = 253 = 4*63 + 1</code>.</p> <p>Esto significa que los <strong>16.777.216 estados</strong> forman <strong>un solo círculo</strong>. Cada estado ocupa una <em>posición</em> y recorrer el generador es caminar por ese círculo. La "mano siguiente" es la posición actual <strong>más</strong> cierta cantidad de pasos, los que consumió el reparto más los que consumieron poemas, insultos y canciones.</p> <p>En el momento de estar debuggeando, esta <strong>"ventana"</strong> 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 <strong>"cantidad"</strong> de llamadas a RND.</p> <h3 id="tres-manos-na-má-v4r0n">Tres manos na' má' v4r0n!</h3> <p>El estado tiene 24 bits de incertidumbre. Ver tres cartas distintas de 40 te da <code class="language-plaintext highlighter-rouge">log2(40*39*38) ≈ 15,9</code> bits de información, es decir, le saca 15,9 bits de entropía (incertidumbre) al estado<sup id="fnref:4"><a href="#fn:4" class="footnote" rel="footnote" role="doc-noteref">4</a></sup>. Una mano sola no alcanza: hay <code class="language-plaintext highlighter-rouge">2^24 / (40*39*38) ≈ 283</code> posiciones compatibles. Con una mano ganás ~15,9 bits. Las manos siguientes aportan bastante menos, porque la ventana <code class="language-plaintext highlighter-rouge">WINDOW</code> ya nos dice más o menos dónde caen y por esto, con 3 manos nos alcanza.</p> <p>Para unir las manos usamos una ventana. La mano nueva tiene que arrancar a no más de <code class="language-plaintext highlighter-rouge">WINDOW = 1000</code> pasos de donde terminó la anterior. Una candidata falsa tiene una probabilidad de <code class="language-plaintext highlighter-rouge">283 * 1000 / 2^24 ≈ 1,7 %</code> 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 <a href="https://codeberg.org/toshi/mulero">Mulero</a> puede ser que estés jugando y de pronto haya varias manos en esa ventana que cumplan con las condiciones, en ese caso, <a href="https://codeberg.org/toshi/mulero">Mulero</a> se da cuenta y te avisa que no hay un <strong>100%</strong> de certeza en ese momento de la partida y solo basta con jugar una o dos manos más para “re-certerizarse” (?).</p> <h3 id="numpy">numpy</h3> <p>Para esto necesitamos una tabla de <strong>16 millones de entradas y un montón de comparaciones</strong>. En Python puro cada vuelta de un <code class="language-plaintext highlighter-rouge">for</code> cuesta cierto tiempo de intérprete (chequear tipos, crear objetos <code class="language-plaintext highlighter-rouge">int</code> de ~28 bytes) haciendo todo un poco lento. En <a href="https://numpy.org/doc/stable/">NumPy</a> los datos viven en un bloque contiguo de memoria con un tipo fijo (<code class="language-plaintext highlighter-rouge">uint8</code> ocupa 1 byte) y los <code class="language-plaintext highlighter-rouge">for</code> se ejecutan en C en vez de Python. Escribir <code class="language-plaintext highlighter-rouge">a * x + c</code> sobre un array es hacer el <code class="language-plaintext highlighter-rouge">for</code> sin escribirlo. A eso se le llama <strong>vectorizar</strong>.</p> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">valor</span> <span class="o">=</span> <span class="n">ciclos</span><span class="p">[</span><span class="n">a</span> <span class="o">*</span> <span class="n">x</span> <span class="o">+</span> <span class="n">c</span><span class="p">]</span> <span class="c1"># ya está todo precalculado </span></code></pre></div></div> <h4 id="precalcular-el-círculo">Precalcular el círculo</h4> <p>El problema es que cada estado depende del anterior, así que no parecería vectorizable. La salida es el <strong>salto hacia adelante</strong> (<a href="https://mcnp.lanl.gov/pdf_files/Proceedings_1994_TotANS_Brown_202--203.pdf">jump-ahead</a>). Un paso del LCG es una función lineal <code class="language-plaintext highlighter-rouge">f(x) = A*x + C</code>. Componer dos funciones lineales da otra función lineal:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>A*(a*x + c) + C = (A*a)*x + (A*c + C) </code></pre></div></div> <p>Entonces podemos calcular qué hace avanzar 4096 pasos de una sola vez:</p> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">ak</span><span class="p">,</span> <span class="n">ck</span> <span class="o">=</span> <span class="mi">1</span><span class="p">,</span> <span class="mi">0</span> <span class="k">for</span> <span class="n">_</span> <span class="ow">in</span> <span class="nf">range</span><span class="p">(</span><span class="mi">4096</span><span class="p">):</span> <span class="n">ak</span> <span class="o">=</span> <span class="p">(</span><span class="n">ak</span> <span class="o">*</span> <span class="n">A</span><span class="p">)</span> <span class="o">&amp;</span> <span class="n">MASK</span> <span class="n">ck</span> <span class="o">=</span> <span class="p">(</span><span class="n">ck</span> <span class="o">*</span> <span class="n">A</span> <span class="o">+</span> <span class="n">C</span><span class="p">)</span> <span class="o">&amp;</span> <span class="n">MASK</span> <span class="c1"># ahora: estado[n + 4096] = ak * estado[n] + ck </span></code></pre></div></div> <p>Calculamos a mano el primer bloque de 4096 estados. Cada bloque siguiente sale del anterior con <strong>una sola operación sobre un array</strong>:</p> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">state</span><span class="p">[</span><span class="n">b</span><span class="o">*</span><span class="mi">4096</span><span class="p">:(</span><span class="n">b</span><span class="o">+</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="mi">4096</span><span class="p">]</span> <span class="o">=</span> <span class="p">(</span><span class="n">state</span><span class="p">[(</span><span class="n">b</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span><span class="o">*</span><span class="mi">4096</span><span class="p">:</span><span class="n">b</span><span class="o">*</span><span class="mi">4096</span><span class="p">]</span> <span class="o">*</span> <span class="n">ak</span> <span class="o">+</span> <span class="n">ck</span><span class="p">)</span> <span class="o">&amp;</span> <span class="n">MASK</span> </code></pre></div></div> <p>Son 4096 vueltas de Python más 4096 operaciones vectorizadas, en vez de 16 millones de vueltas.</p> <p>Hay varios detalles de NumPy en esas líneas:</p> <ul> <li><code class="language-plaintext highlighter-rouge">&amp; MASK</code> en vez de <code class="language-plaintext highlighter-rouge">% N</code>: como <code class="language-plaintext highlighter-rouge">N</code> es potencia de 2, <code class="language-plaintext highlighter-rouge">x mod 2^24</code> es igual a <code class="language-plaintext highlighter-rouge">x &amp; (2^24 - 1)</code>. Es más rápido y solo funciona con potencias de 2.</li> <li><code class="language-plaintext highlighter-rouge">dtype=np.uint64</code>: <code class="language-plaintext highlighter-rouge">estado * A</code> llega a valer ~2^48 y desbordaría un entero de 32 bits.</li> <li><code class="language-plaintext highlighter-rouge">state[a:b]</code> es una <em>vista</em>, no una copia. Asignarle algo escribe en el array original.</li> <li><code class="language-plaintext highlighter-rouge">np.empty</code> reserva memoria sin inicializarla, porque la vamos a llenar entera.</li> </ul> <h4 id="de-estado-a-carta">De estado a carta</h4> <p>El Truco es un juego de 40 cartas en el mazo. El orden en que escribí y compuse el array para descular como hace <code class="language-plaintext highlighter-rouge">TRUCO.EXE</code> viene de como se calcula la selección de cartas en el programa y el orden en que aparece en memoria.</p> <p><a href="https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L35">https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L35</a>:</p> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="c1"># card stuff # cards goes from 0..39 with suit*10 + index, where suit is 0..3 and index is 0..9 </span><span class="n">SUITS</span> <span class="o">=</span> <span class="sh">"</span><span class="s">eboc</span><span class="sh">"</span> <span class="c1"># suits are: e=espada, b=basto, o=oro, c=copa </span><span class="n">SUITS_NAMES</span> <span class="o">=</span> <span class="p">[</span><span class="sh">"</span><span class="s">espada</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">basto</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">oro</span><span class="sh">"</span><span class="p">,</span> <span class="sh">"</span><span class="s">copa</span><span class="sh">"</span><span class="p">]</span> <span class="n">NUMBERS</span> <span class="o">=</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">10</span><span class="p">,</span> <span class="mi">11</span><span class="p">,</span> <span class="mi">12</span><span class="p">]</span> </code></pre></div></div> <p>Si se fijan en la función <a href="https://codeberg.org/toshi/mulero/src/branch/master/mulero.py#L56">lcg_table()</a> <code class="language-plaintext highlighter-rouge">INT(RND * 40)</code> es <code class="language-plaintext highlighter-rouge">floor(40 * estado / 2^24)</code>. Dividir por <code class="language-plaintext highlighter-rouge">2^24</code> y truncar es correr 24 bits a la derecha, así que queda <code class="language-plaintext highlighter-rouge">(state * 40) &gt;&gt; 24</code>, un valor de 0 a 39. Como <code class="language-plaintext highlighter-rouge">RND</code> primero avanza el estado y después devuelve, la carta de la posición <code class="language-plaintext highlighter-rouge">p</code> sale del estado <code class="language-plaintext highlighter-rouge">p+1</code>. Eso lo resuelve <code class="language-plaintext highlighter-rouge">np.roll(cartas, -1)</code>, que desplaza el array con vuelta circular (el final se conecta con el principio, justo lo que necesita un círculo).</p> <p>El resultado es <code class="language-plaintext highlighter-rouge">CARDS</code>, un array de 16 MB donde <code class="language-plaintext highlighter-rouge">CARDS[p]</code> es la carta que se repartiría en la posición <code class="language-plaintext highlighter-rouge">p</code>.</p> <h4 id="buscar-la-mano">Buscar la mano</h4> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">start</span> <span class="o">=</span> <span class="n">np</span><span class="p">.</span><span class="nf">flatnonzero</span><span class="p">(</span><span class="n">CARDS</span> <span class="o">==</span> <span class="n">mi_primera_carta</span><span class="p">)</span> </code></pre></div></div> <p><code class="language-plaintext highlighter-rouge">CARDS == x</code> genera un array de 16 millones de booleanos y <code class="language-plaintext highlighter-rouge">flatnonzero</code> devuelve los <strong>índices</strong> donde vale <code class="language-plaintext highlighter-rouge">True</code>. Con una sola línea queda el 1/40 de las posiciones, unas 419 mil.</p> <p>Después <code class="language-plaintext highlighter-rouge">deal()</code> simula el reparto de <strong>todas esas candidatas en paralelo</strong>. Como el juego vuelve a tirar cuando sale una carta repetida, cada candidata necesita una cantidad distinta de tiradas. Se resuelve con una lista <code class="language-plaintext highlighter-rouge">pend</code> de las que todavía necesitan carta:</p> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">c</span> <span class="o">=</span> <span class="n">CARDS</span><span class="p">[</span><span class="n">pos</span><span class="p">[</span><span class="n">pend</span><span class="p">]</span> <span class="o">&amp;</span> <span class="n">MASK</span><span class="p">]</span> <span class="c1"># fancy indexing: sacar muchos elementos de una </span><span class="n">repeated</span> <span class="o">=</span> <span class="p">(</span><span class="n">hand</span><span class="p">[</span><span class="n">pend</span><span class="p">,</span> <span class="p">:</span><span class="n">k</span><span class="p">]</span> <span class="o">==</span> <span class="n">c</span><span class="p">[:,</span> <span class="bp">None</span><span class="p">]).</span><span class="nf">any</span><span class="p">(</span><span class="n">axis</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span> </code></pre></div></div> <ul> <li><strong>Fancy indexing</strong>: indexar un array con otro array de índices.</li> <li><strong>Broadcasting</strong>: <code class="language-plaintext highlighter-rouge">hand[pend, :k]</code> tiene forma <code class="language-plaintext highlighter-rouge">(n, k)</code> y <code class="language-plaintext highlighter-rouge">c[:, None]</code> tiene forma <code class="language-plaintext highlighter-rouge">(n, 1)</code>. NumPy "estira" la columna y compara cada carta nueva contra las <code class="language-plaintext highlighter-rouge">k</code> ya repartidas.</li> <li><code class="language-plaintext highlighter-rouge">.any(axis=1)</code> colapsa las columnas y responde "¿repitió alguna?" por cada fila.</li> <li><code class="language-plaintext highlighter-rouge">~repeated</code> es la negación bit a bit. En arrays no se puede usar <code class="language-plaintext highlighter-rouge">not</code>.</li> </ul> <p>Después de cada una de las tres primeras cartas se descartan las candidatas que no coinciden con tu mano (<code class="language-plaintext highlighter-rouge">start = start[ok]</code>, una <strong>máscara booleana</strong>). De 419 mil se pasa a unas ~283, y las cartas de la CPU se simulan solo para esas.</p> <h4 id="encadenar-manos">Encadenar manos</h4> <div class="language-python highlighter-rouge"><div class="highlight"><pre class="highlight"><code><span class="n">gap</span> <span class="o">=</span> <span class="p">(</span><span class="n">start</span><span class="p">[:,</span> <span class="bp">None</span><span class="p">]</span> <span class="o">-</span> <span class="n">prev_end</span><span class="p">[</span><span class="bp">None</span><span class="p">,</span> <span class="p">:])</span> <span class="o">&amp;</span> <span class="n">MASK</span> <span class="n">ok</span> <span class="o">=</span> <span class="p">(</span><span class="n">gap</span> <span class="o">&lt;=</span> <span class="n">WINDOW</span><span class="p">).</span><span class="nf">any</span><span class="p">(</span><span class="n">axis</span><span class="o">=</span><span class="mi">1</span><span class="p">)</span> </code></pre></div></div> <p>Restar un vector columna <code class="language-plaintext highlighter-rouge">(n, 1)</code> y uno fila <code class="language-plaintext highlighter-rouge">(1, m)</code> da una matriz <code class="language-plaintext highlighter-rouge">(n, m)</code> con <strong>todas las diferencias de a pares</strong>, sin ningún <code class="language-plaintext highlighter-rouge">for</code>. El <code class="language-plaintext highlighter-rouge">&amp; MASK</code> sobre números negativos da el módulo correcto (la distancia circular). El <code class="language-plaintext highlighter-rouge">.any(axis=1)</code> pregunta si esta candidata cae a menos de <code class="language-plaintext highlighter-rouge">WINDOW</code> pasos de <em>algún</em> final de la mano anterior.</p> <p>Por último, <code class="language-plaintext highlighter-rouge">np.sort(cpu, axis=1)</code> ordena las cartas de cada mano candidata para que <code class="language-plaintext highlighter-rouge">{3, 7, 9}</code> y <code class="language-plaintext highlighter-rouge">{9, 3, 7}</code> cuenten como la misma, y <code class="language-plaintext highlighter-rouge">np.unique(axis=0, return_counts=True)</code> agrupa las filas iguales y cuenta cuántas veces aparece cada una. <strong>Si queda una sola mano posible, ya sabés qué tiene la CPU</strong>.</p> <p>Ahora, bajate <a href="https://codeberg.org/toshi/mulero">Mulero</a> y ganale de una buena vez!</p> <h1 id="código-fuente">Código fuente</h1> <p><img src="/assets/images/arbiser/mulero-al-arbiser.png" alt="Mulero en acción" class="img-responsive" /><em>El Mulero en acción</em></p> <p>El código fuente de Mulero lo podés descargar en el repositorio de Codeberg: <a href="https://codeberg.org/toshi/mulero">https://codeberg.org/toshi/mulero</a></p> <h1 id="referencias">Referencias</h1> <ul> <li><a href="https://www-2.dc.uba.ar/charlas/lud/truco/">Truco Arbiser</a></li> <li><a href="https://archive.org/stream/PC_Tech_Journal_vol06_n06/PC_Tech_Journal_vol06_n06_djvu.txt">PC Tech Journal Volume 06 Number 06 JUNE 1988</a></li> <li><a href="https://ethanwiner.com/BTU_BOOK.PDF">BASIC Techniques and Utilities</a></li> <li><a href="https://wiki.osdev.org/MZ">MZ File Structure</a></li> <li><a href="http://sparksandflames.com/files/x86InstructionChart.html">x86 Instruction Chart</a></li> <li><a href="https://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf">Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2 (2A, 2B, 2C &amp; 2D): Instruction Set Reference, A-Z</a></li> <li><a href="https://c9x.me/x86/">x86 Instruction Set Reference</a></li> <li><a href="http://ref.x86asm.net/coder32.html">X86 Opcode and Instruction Reference Home</a></li> <li><a href="https://www.h-schmidt.net/FloatConverter/IEEE754.html">IEEE-754 Online Floating Point Converter</a></li> <li><a href="https://www.capstone-engine.org/">Capstone Engine</a></li> <li><a href="https://en.wikipedia.org/wiki/Pseudorandom_number_generator">PRNG</a></li> <li><a href="https://en.wikipedia.org/wiki/Linear_congruential_generator">LCG</a></li> <li><a href="https://codeberg.org/toshi/mulero">README</a></li> <li><a href="https://codeberg.org/toshi/mulero">Mulero</a></li> <li><a href="https://numpy.org/doc/stable/">NumPy</a></li> <li><a href="https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0">teorema de Hull-Dobell</a></li> <li><a href="https://mcnp.lanl.gov/pdf_files/Proceedings_1994_TotANS_Brown_202--203.pdf">jump-ahead</a></li> </ul> <h1 id="notas-al-pie">Notas al pie</h1> <div class="footnotes" role="doc-endnotes"> <ol> <li id="fn:3"> <p>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! <a href="#fnref:3" class="reversefootnote" role="doc-backlink">&#8617;</a> <a href="#fnref:3:1" class="reversefootnote" role="doc-backlink">&#8617;<sup>2</sup></a></p> </li> <li id="fn:1"> <p>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 <code class="language-plaintext highlighter-rouge">reversing</code>, hubiera evitado todo el laburo de hacer un desensamblador para QB4. Estaba mucho más cerca de lo que creía en aquel momento. <a href="#fnref:1" class="reversefootnote" role="doc-backlink">&#8617;</a> <a href="#fnref:1:1" class="reversefootnote" role="doc-backlink">&#8617;<sup>2</sup></a></p> </li> <li id="fn:2"> <p>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. <a href="#fnref:2" class="reversefootnote" role="doc-backlink">&#8617;</a></p> </li> <li id="fn:4"> <p>La <strong>entropía</strong> 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 <a href="https://xkcd.com/936/">xkcd nro 936</a> los bits de entropía se suman solamente cuando las elecciones son independientes. <a href="#fnref:4" class="reversefootnote" role="doc-backlink">&#8617;</a></p> </li> </ol> </div>