Lo prometido es deuda. Tras un par de semanitas de relax, vuelvo a la carga. Como dije, voy a comentar por encima los cambios que he ido haciendo en estas revisiones (r111 -> r124).

En estos posts siempre me dejo algunas cosas interesantes en el tintero por comentar. Suelo hacer cantidad de refactorizaciones muchas veces haciendo uso de la potencia del CTFE de D. Pero no suelo comentar cuales o por qué las he hecho.

Editor hexadecimal. Búsqueda relativa y de patrón

Por lo pronto he empezado a hacer pruebas para añadir un debugger al emulador. He estado viendo cómo montar un componente de editor hexadecimal que tenga una edición cómoda y posibilidad de buscar directamente sin tener que dumpear. Muchos emuladores tienen visores hexadecimal, pero o bien no dejan editar o bien no dejan buscar con lo que hace falta usar herramientas externas. Yo quiero hacer un componente que tenga todo eso. Incluyendo búsquedas relativas, posibilidad de usar diferentes codificaciones y tablas de codificación personalizadas. Otra cosa que me gustaría añadir es la “búsqueda por patrón”. No conozco ningún editor hexadecimal que tenga este tipo de búsqueda que funciona en los casos en los que falla la búsqueda relativa. Por ejemplo. El Valkyrie Profile tiene una tabla de caracteres no correlativos y no ascii que hace que la búsqueda tradicional, y incluso la búsqueda relativa fallen. Ahí es donde la búsqueda de patrón funciona. Además sirve para hacer búsquedas de tiles.

Si tenemos la frase “Welcome back.” con una búsqueda relativa convendría buscar algo tipo “elcome” para que funcione correctamente (no conviene mezclar mayúsculas y minúsculas en este tipo de búsquedas porque podría no funcionar).

La búsqueda relativa lo que hace es convertir “elcome” en:

php -r"$s = 'elcome'; $list = array(); for ($n = 1, $l = strlen($s); $n < $l; $n++) $list[] = ord($s[$n]) - ord($s[$n - 1]); print_r($list);"  

Array  
(  
[0] => 7  
[1] => -9  
[2] => 12  
[3] => -2  
[4] => -8  
)  

}

Y a la hora de buscar, no se buscan caracteres, sino incrementos. Esto funciona cuando el texto no es ascii, pero la tabla de caracteres tiene las letras en orden alfabético (lo normal).

La búsqueda de patrón lo que hace es buscar repeticiones.

“Welcome back”

“abcdefbghidj”

Por lo pronto a != b != c != d… Cada caracter debe ser único.

Hace tiempo estuve haciendo varias pruebas de implementación. Dejo aquí una en D para los interesados:

import std.string, std.stdio, std.stream, std.file;  

ubyte[] normalize(ubyte[] text) {  
 int[0x100] translate = void; translate[0..0x100] = -1;  

 ubyte[] text2 = new ubyte[text.length];  

 int count_symbols = 0;  

 for (int n = 0, len = text.length; n < len; n++) {  
  int cn = text[n];  
  int* translate_cn = &translate[cn];  
  if (*translate_cn == -1) *translate_cn = count_symbols++;  
  text2[n] = *translate_cn;  
 }  

 return text2;  
}  

void search_pattern(ubyte[] data, ubyte[] search) {  
 auto search_normalized = normalize(search);  

 for (int n = 0; n <= data.length - search.length; n++) {  
  if (normalize(data[n..n + search.length]) == search_normalized) {  
   writefln("%08X find!", n);  

   for (int m = 0; m < search.length; m++) {  
    writefln("%02X: %s", data[n + m], cast(char)search[m]);  
   }  
  }  
 }  
}  

void main() {  
 search_pattern(cast(ubyte[])read("ramdump.bin"), cast(ubyte[])"you're waiting for someone");  
}  

Se podría optimizar haciendo que en vez de normalizar la cadena entera, se hiciese incrementalmente a la vez que se compara con la cadena original normalizada, de esta forma se podría hacer una reducción de proceso por cortocircuito. Pero esta implementación ya era suficientemente rápida para lo que me interesaba, y no quería complicarla.

Recompilación dinámica

Otra de las cosas en las que he estado trabajando más es en la recompilación dinámica. No tenía ninguna experiencia en este campo todavía. Había pensado en el tema en algunas ocasiones y me imaginaba cómo se podría implementar. Pero de la teoría a la práctica va un buen trecho. Por suerte las ideas que tenía en mente parecía que eran bastante acertadas.

Por lo pronto una de las cosas que cambié fue el registro a utilizar para el puntero a la tabla de registros de mips. Comenté que mejor usar un registro que no tuviese que conservarse para evitar tener que hacer PUSH y POP cada vez que se llamaba a un bloque de código nativo generado. Pero resulta que cada vez que se hacía una llamada a una función externa a ese bloque nativo, había que guardarse ese registro con PUSH y POP. Y generalmente habían muchas más llamadas que veces que se salía del código nativo. Así que lo que hice fue hacer el PUSH justo antes de llamar al código nativo en una función intermedia y el POP al volver de la función. De esta forma me ahorraba PUSH y POPs por todo el código generado tanto por una cosa como por la otra. Ahora estoy utilizando el registro EBX para esto.

Otra mejora sustancial que hice fue el mapeado de instrucciones del guest al host. Inicialmente lo hice con un AA (Array Asociativo) que tiene un coste de acceso de una tabla de hashes. En códigos que no tengan muchos saltos dinámicos, no debería suponer “demasiado” problema. Pero el problema viene cuando hay saltos dinámicos por doquier. Ahí no tengo claro que ese coste sea suficientemente satisfactorio. Así que sacrificando mucha más memoria (mas o menos el doble), he hecho un acceso en tiempo constante. Si la RAM de la psp son 32MB, pues la memoria usada sería 64MB. Teniendo en cuenta que cualquier navegador web ya gasta mucho más que eso por el hecho de estar abierto, no creo que sea un problema muy grave ;)

No sé si comenté que en determinados puntos de la ejecución, hay que hacer una parada para ejecutar callbacks, interrupciones, switching de threads, comprobaciones de breakpoints etc. Si lo comenté, imagino que conté también que un buen momento para hacer este tipo de comprobaciones es en los saltos. Son instrucciones que por narices se tienen que ejecutar tarde o temprano y que son menos frecuente que otras.

Otra de las cosas en las que estoy trabajando es en mejorar este proceso. En bucles sencillos con muchas iteraciones puede ser una operación costosa. Y aunque generalmente este tipo de bucles más adelante se convertirán en memsets, memcpy y similares, mejorar este proceso debería suponer un speedup importante en todas las aplicaciones.

VirtualAlloc

Mediante varios VirtualAlloc se puede acelerar sustancialmente todos los accesos (de escritura o lectura) a la memoria del guest. Especialmente si tenemos en cuenta que en la emulación HLE que estoy haciendo, los juegos no van a acceder a DMA, es especialmente sencillo.

De normal, cada vez que se hace un acceso de escritura o lectura a la memoria del guest, tenemos que tener en cuenta que en el caso de la psp hay 3 segmentos de memoria física accesibles. El scratchpad, la memória gráfica y la RAM normal. Esto hace que para acceder a memoria tengamos que determinar en primer lugar el segmento de memoria al que vamos a acceder, ver que no se salga de ahí y calcular la posición que tendrá en la memoria del host. Con diferentes optimizaciones, esto es más o menos rápido, pero el acceso a memoria es una operación muy común, así que cualquier optimización es bienvenida.

Resulta que en windows hay una función VirtualAlloc (tengo entendido que en linux hay una equivalente llamada mmap) que permite reservar una zona de memoria arbitraria al proceso actual. Con lo que podemos reservar la memoria dejando el espacio entre segmentos original en el guest y haciendo que la conversión de dirección de memoria de guest a host y viceversa sea una simple suma.

Hice una pequeña demo que iba pintando la pantalla entera de la psp de un color que iba aumentando. Si de la versión interpretada a la de dynarec hubo un cambio de 6 a 50fps, con el VirtualAlloc se ha pasado a 60fps directamente. Todavía quedan muchas cosas que se pueden optimizar, pero poco a poco :)

Clut (Color LookUp Table)

Una cosa que faltaba por implementar era el clut. Mi idea inicial era hacer el unswizzling de texturas y el clut usando shaders, pero por ahora he tirado a la opción típica: hacer un hash para los datos y para la textura y si alguno de los dos cambia, generar una textura estándar de 32 bits con la paleta aplicada y unswizzleado.

HLE/KD

Añadí UIDs con lowid para los identificadores de threads y handles de archivos. Antes se pasaba un puntero a la memoria del host como valor de UID. Las pegas de esto es que se hace más difícil de trackear y que cuando implemente los savestates, daría más problemas que ventajas.

Por otra parte hice diversas correcciones en threads y archivos. Siempre con un conocimiento muy superficial que hace que en ocasiones me de cuenta de un detalle importante después de haber implementado algunas cosas de una forma bastante diferente e incompatible.

Hice muchas correcciones en funciones del kernel y añadí montañas y montañas de nids sin implementar.

Audio

Otra de las cosas con las que he experimentado en estas revisiones ha sido con el audio. Mixing de audio era algo que tampoco había hecho nunca. En lo primero que pensé fue en usar la librería FMOD y hice algunas pruebas con ella. Pero la verdad quería probar como se haría con el Api de windows directamente por una parte, y por otra parte quería evitar a toda costa la dependencia de librerías externas. Y como los datos que llegaban a la librería de audio son datos que están todos con la misma frecuencia y que solo tienen uno o dos canales, era un proceso relativamente sencillo. Lo que me podía preocupar un poco era el resampling, que no he hecho nunca. Pero el mixing de audio a la misma frecuencia, no tiene mucha complicación: basta con sacar la media aritmética de los samples de todos los canales. Aquí había alguna cosilla interesante, pero en “teórica” no tiene mucha complicación. Aún con todo, solo conseguí que saliese un sonido muy chungo; aunque se podía apreciar. Quizá sería por un buffer underrun con el buffer del mixer o por otra cosa, pero tampoco era un tema que me preocupase demasiado, así que con esto medio funcionando pasé a otros temas. Ya haré que se escuche bien más adelante.

Variado

Añadí soporte para tomar pantallazos en png.

Empecé a implementar parcialmente el soporte para sceIoDevctl y parcialmente para callbacks.

Tabla de instrucciones

Una de las cosas más molonas de la implementación del emulador en D, que no tienen otros emuladores es la generación en tiempo de compilación de switch en este caso (o de tablas si hiciese falta) para la decodificación rápida de instrucciones. Y además con una sola tabla, se genera la decodificación del modo intérprete, del dynarec y del desensamblador. Generalmente suele ser mucho más complejo y suele acabar en demasiadas redundancias que dificultan mucho el mantenimiento.

La tabla era algo así:

ID( "mfdr",               VM(0x7000003D, 0xFFE007FF), "%t, %r", ADDR_TYPE_NONE, INSTR_TYPE_PSP ),  
ID( "mfhi",               VM(0x00000010, 0xFFFF07FF), "%d", ADDR_TYPE_NONE, 0 ),  
ID( "mfic",               VM(0x70000024, 0xFFE007FF), "%t, %p", ADDR_TYPE_NONE, INSTR_TYPE_PSP ),  
ID( "mflo",               VM(0x00000012, 0xFFFF07FF), "%d", ADDR_TYPE_NONE, 0 ),  
ID( "movn",               VM(0x0000000B, 0xFC0007FF), "%d, %s, %t", ADDR_TYPE_NONE, INSTR_TYPE_PSP ),  

Bastante centralizado. Dos valores enteros: uno indicando los bits que deben estar seteados o no para que sea la instrucción que toca, y otro con la máscara de los bits que se van a comprar. Es bastante práctico y con esto se puede generar los switch anidados o las tablas que interesan. Pegas: está en hexadecimal y esto tiene lógica en binario. Aunque estuviese en binario la máscara sigue por separado y cuesta de ver qué parte nos interesa.

Hace tiempo vi el Allegrex.isa, que mejora este aspecto. A cada instrucción se le asocia una cadena de este tipo:

000001:rs:00001:imm16  

Con esto se ve visualmente los bits que se consideran y las diferentes partes de la instrucción. Me gustó mucho.

Así que haciendo uso del maravilloso poder del CTFE en D, estoy convirtiendo las instrucciones a algo así:

ID( "xor",    VM("000000:rs:rt:rd:00000:100110"), "%d, %s, %t", ADDR_TYPE_NONE, 0 ),  
ID( "xori",   VM("001110:rs:rt:imm16"          ), "%t, %s, %I", ADDR_TYPE_NONE, 0 ),  

// Shift Left/Right Logical/Arithmethic (Variable).  
ID( "sll",    VM("000000:00000:rt:rd:sa:000000"), "%d, %t, %a", ADDR_TYPE_NONE, 0 ),  
ID( "sllv",   VM("000000:rs:rt:rd:00000:000100"), "%d, %t, %s", ADDR_TYPE_NONE, 0 ),  
ID( "sra",    VM("000000:00000:rt:rd:sa:000011"), "%d, %t, %a", ADDR_TYPE_NONE, 0 ),  

Que mejora sustancialmente lo que había. Lo hace visualmente más claro y mantenible.

VM es una estructura con dos static opCall, uno para la definición antigua y otro para la nueva. Como es una función pura, se puede ejecutar en tiempo de compilación sin mayor complicación y generar el value, mask originales utilizando como entrada la cadena :) :

struct ValueMask {  
 string format;  
 uint value, mask;  

 static ValueMask opCall(uint value, uint mask) {  
  ValueMask ret;  
  ret.format = "";  
  ret.value = value;  
  ret.mask  = mask;  
  return ret;  
 }  

 bool opCmp(ValueMask that) {  
  return (this.value == that.value) && (this.mask == that.mask);  
 }  

 static ValueMask opCall(string format) {  
  ValueMask ret;  
  string[] parts;  
  ret.format = format;  
  int start, total;  

  for (int n = 0; n <= format.length; n++) {  
   if ((n == format.length) || (format[n] == ':')) {  
    parts ~= format[start..n];  
    start = n + 1;  
   }  
  }  

  void alloc(uint count) {  
   ret.value <<= count;  
   ret.mask  <<= count;  
   total += count;  
  }  

  void set(uint value, uint mask) {  
   ret.value |= value;  
   ret.mask  |= mask;  
  }  

  foreach (part; parts) {  
   switch (part) {  
    case "rs", "rd", "rt", "sa", "lsb", "msb", "fs", "fd", "ft": alloc(5); break;  
    case "fcond": alloc(4 ); break;  
    case "imm16": alloc(16); break;  
    case "imm26": alloc(26); break;  
    default:  
     if ((part[0] != '0') && (part[0] != '1')) {  
      assert(0, "Unknown identifier");  
     } else {  
      for (int n = 0; n < part.length; n++) {  
       alloc(1);  

       if (part[n] == '0') {  
        set(0, 1);  
       } else if (part[n] == '1') {  
        set(1, 1);  
       } else {  
        //pragma(msg, part);  
        assert(0);  
        set(0, 0);  
       }  
      }  
     }  

    break;  
   }  
  }  

  assert(total == 32);  

  return ret;  
 }  
}  

struct InstructionDefinition {  
 string  name;  
 ValueMask opcode;  
 string  fmt;  
 uint    addrtype;  
 uint    type;  

 string toString() {  
  return format("InstructionDefinition('%s', %08X, %08X, '%s', %s, %s)", name, opcode.value, opcode.mask, fmt, addrtype, type);  
 }  
}  

¡Magia!

BTW: Soy el contribuidor de D más activo del año en ohloh :D http://www.ohloh.net/languages/32