Estructura Yaz0

1. Introducción
2. Funcionamiento
3. Definiciones
4. Estructura
5. Ejemplo
6. Notas
7. Referencias

Las letras Yaz0 se encuentran muy frecuentemente entre los juegos de Nintendo. En el caso de Super Mario Galaxy estas letras se encuentran, en su mayoria, en la cabecera de los archivos ARC en las diferentes carpetas del juego. Yaz0 hace referencia a un algoritmo de compresión. Afortunadamente, es un algoritmo sencillo (es fácil de decodificar) y existen múltiples implementaciones del mismo dado su uso extendido en múltiples juegos. Esta página almacena información acerca de lo que he aprendido de Yaz0 viendo los archivos de Super Mario Galaxy.

Archivo ObjectData/CubeBubbleExPlanetA.arc visto en ImHex

Yaz0 es un algoritmo de compresión que usa los datos ya codificados/leídos para reconstruir el archivo original hacia adelante. Es decir, es un algoritmo que se basa en la repetición de patrones de bytes ya procesados para comprimir/reducir el tamaño de un archivo binario.

Esto lo hace guardando bloques de datos que "apuntan" hacia secuencias de bytes pasadas (cuando sea posible guardarlas). Estos bloques también guardan la información de cuantos bytes copiar de esa dirección. En el proceso de descompresión, los bytes especificados por la instrucción de copiado se colocan al frente de los bytes ya recuperados del archivo (en un contenedor aparte). El resultado es que poco a poco se va escribiendo el archivo de nuevamente.

Ejemplo visual y simplificado de la forma de compresión Yaz0

Se puede ver a través de la imagen que Yaz0 es sólo un conjunto de instrucciones en secuencia (que se leen de izquierda a derecha) que indican como reconstruir los datos de un archivo.

El formato binario de Yaz0 es un poco más complejo que lo que se muestra en la figura, pero ésta debería ayudar a dar una idea general de como funciona. En la siguiente sección se explicaran los detalles.

Yaz0 define 2 instrucciones de copiado:

• 0 o Copia [número] de bytes localizados [número] de bytes atrás: Esta instrucción leída del archivo comprimido dice que "se copien [número] de bytes que se encuentran un [número] de posiciones atrás respecto a la última posición de escritura del archivo en reconstrucción". De otra forma, "desde la última posición escrita en el contenedor en el que se recuperan los bytes originales del archivo comprimido, desplázate hacia atrás unas posiciones y copia cierto número de bytes". Este desplazamiento tiene que ser mayor o igual a 1.
• 1 o Copia directamente el próximo byte: Esta instrucción dice que el próximo byte que se lea del archivo comprimido se coloque directamente en la última posición escrita del archivo en reconstrucción. Esta instrucción es la que naturalmente se dá cuando no hay ninguna repetición de bytes a la que se pueda hacer referencia hacia atrás.

Yaz0 almacena el identificador de estas instrucciones en paquetes de 8. En un byte se almacenan 8 instrucciones y el orden de ellas (de izquierda a derecha) especifica cómo se interpretan los siguientes bytes del archivo comprimido. A este byte lo denomino byte de instrucciones.

Paquete de 8 instrucciones, byte de instrucciones

Los datos que manejan las instrucciones 0 y 1 que vienen después de un byte de instrucciones se almacenan binariamente de la siguiente forma:

• Instrucción 0

  • Si el número de bytes a copiar o n se encuentra entre 0x3 y 0x11 (inclusivo):

    1. A n se le resta 0x2 y se almacena en los 4 bits más significativos de un entero sin signo de 16 bits.
    2. Al desplazamiento hacia atrás de los bytes a copiar o seekback se le resta 1 y se almacena en los 12 bits restantes del entero sin signo de 16 bits.
    3. El entero sin signo de 16 bits se escribe en Big Endian en el archivo comprimido.
    4. La información de copiado queda almacenada en 2 bytes.

  • Si el número de bytes a copiar o n es mayor o igual a 0x12:

    1. A seekback se le resta 1 y se almacena en los 12 bits menos significativos de un entero sin signo de 16 bits. Los 4 bits más significativos quedan en 0.
    2. El entero sin signo de 16 bits se escribe en Big Endian en el archivo comprimido.
    3. A n se le resta 0x12 y se guarda en el siguiente byte del archivo comprimido, después del entero sin signo de 16 bits.
    4. La información de copiado queda almacenada en 3 bytes.

• Instrucción 1

  El siguiente byte del archivo a comprimir se añade directamente al archivo comprimido.

Ejemplo visual simple de un byte de instrucciones y sus bytes siguientes

De aquí puede verse que seekback puede tener valores entre 0x1 y 0xFFF + 0x1, y, n puede tener valores entre 0x3 y 0xFF + 0x12 (IMPORTANTE!).

La estructura del archivo descrita aquí es la estructura que se ha conseguido en los archivos originales de SMG. Esta información no significa que la estructura tenga que ser exactamente como se describe en la página.

Encabezado

Conjunto de tamaño no determinado de bytes de instrucciones

Estructura coloreada de ObjectData/CubeBubbleExPlanetA.arc

En la imagen se muestran los bytes de instrucción en rojo, los bytes directamente copiados en azul y los copiados de bytes en verde. El resto de las variables estan en otros colores.

• Un archivo comprimido Yaz0 no tiene una forma sencilla de chequearse:

  • Si el tamaño del archivo original es mayor de lo que debería entonces va a ocurrir un error al leer al archivo comprimido ya que no van a haber suficientes intrucciones. Se va a intentar leer más allá de los límites del archivo.
  • Si un seekback leído se va más allá del inicio del archivo va a ocurrir un error de lectura.

  Al descomprimir un archivo uno está confiando en que no existen esos errores.

• 2 implementaciones de Yaz0 que generan archivos comprimidos Yaz0 equivalentes a los que se consiguen en Super Mario Galaxy:

  • https://gist.github.com/Mr-Wiseguy/6cca110d74b32b5bb19b76cfa2d7ab4f
  • https://codeberg.org/Humming-Owl/Yaz0
• No importa si el sistema es Big/Little Endian, la información siempre se guardará en Big Endian.
• La implementación original del algoritmo de compresión Yaz0 se mantuvo igual por muchos años. Desde Ocarina of Time (N64) hasta Super Mario Galaxy (Wii). En Super Mario Galaxy 3D All-Stars cambió a otro tipo de implementación (ver las implementaciones de Yaz0 arriba).

• https://wiki.cloudmodding.com/oot/Yaz_(File_Compression)
• https://gbatemp.net/threads/libyaz0-a-library-for-compressing-and-decompressing-yaz0-1-compression-formats.490054/