BPE (Byte-Pair Encoding)BPE (Byte-Pair Encoding)

What BPE isQué es BPE

Byte-Pair Encoding, usually shortened to BPE, is a dictionary-style compression idea based on repeated byte pairs. Instead of storing the same two-byte sequence again and again, a compressor can assign that pair to a spare token value. During decompression, that token expands back into the two original bytes.Byte-Pair Encoding, normalmente abreviado como BPE, es una idea de compresión basada en diccionario que aprovecha pares de bytes repetidos. En vez de guardar una y otra vez la misma secuencia de dos bytes, el compresor puede asignar ese par a un valor de token libre. Durante la descompresión, ese token vuelve a expandirse en los dos bytes originales.

The important detail for ROM hacking is that BPE is not one single file format. It is a technique. A game or toolchain still has to decide how to store the table, where the compressed payload starts, how block sizes are represented, and which byte values count as literal data.El detalle importante para romhacking es que BPE no es un único formato de archivo. Es una técnica. Cada juego o toolchain tiene que decidir cómo guarda la tabla, dónde empieza el payload comprimido, cómo representa los tamaños de bloque y qué valores de byte cuentan como datos literales.

Why games use itPor qué lo usan los juegos

Cartridge games are full of repeated byte patterns: graphics tiles, maps, fonts, menus, animation data, tables, and sometimes code-like command streams. A pair-based dictionary can reduce this repetition without requiring a heavy decoder. That matters on Mega Drive / Genesis because decompression often happens on a 68000 routine with limited RAM and strict timing around when assets can be unpacked.Los juegos de cartucho están llenos de patrones de bytes repetidos: tiles gráficos, mapas, fuentes, menús, datos de animación, tablas y a veces flujos de comandos parecidos a código. Un diccionario basado en pares puede reducir esa repetición sin requerir un decodificador pesado. En Mega Drive / Genesis esto importa porque la descompresión suele hacerse con una rutina 68000, RAM limitada y momentos concretos en los que se pueden desempaquetar recursos.

BPE is especially attractive when the data has many local two-byte repetitions. It is less useful when the data is already noisy, encrypted, heavily packed by another algorithm, or when the replacement table costs more space than it saves.BPE resulta especialmente atractivo cuando los datos tienen muchas repeticiones locales de dos bytes. Es menos útil cuando los datos ya son ruidosos, están cifrados, están muy empaquetados por otro algoritmo o cuando la tabla de sustituciones ocupa más de lo que ahorra.

The classic BPE modelEl modelo BPE clásico

A simple BPE compressor looks for the most frequent adjacent byte pair, replaces that pair with a token, records the token expansion, and repeats the process while it still saves space. Decompression reverses the idea: read a byte, decide whether it is literal or a pair token, and emit the expanded bytes.Un compresor BPE simple busca el par de bytes adyacentes más frecuente, reemplaza ese par por un token, registra la expansión del token y repite el proceso mientras siga ahorrando espacio. La descompresión invierte la idea: lee un byte, decide si es literal o token de par, y emite los bytes expandidos.

Original bytes:
41 42 41 42 43 41 42 43

Pair table:
80 => 41 42
81 => 80 43

Compressed stream:
80 81 81

Expanded output:
41 42 41 42 43 41 42 43

Bytes originales:
41 42 41 42 43 41 42 43

Tabla de pares:
80 => 41 42
81 => 80 43

Flujo comprimido:
80 81 81

Salida expandida:
41 42 41 42 43 41 42 43

In this example, token 80 expands to 41 42. Token 81 expands to 80 43, which means it recursively expands through token 80 before the final byte 43 is emitted.En este ejemplo, el token 80 se expande a 41 42. El token 81 se expande a 80 43, lo que significa que se expande recursivamente a través del token 80 antes de emitir el byte final 43.

Electronic Arts 46FBh

The Electronic Arts 46FBh variation belongs to the Frank Barchard EA compression family. Frank Barchard is credited here as the creator behind the FB-tagged compression algorithms used by Electronic Arts Canada tools and libraries. In this Knowledge Base, this BPE variant is tracked by the method marker 46FBh.La variación 46FBh de Electronic Arts pertenece a la familia de compresión EA de Frank Barchard. Aquí se acredita a Frank Barchard como creador de los algoritmos de compresión etiquetados con FB usados por herramientas y librerías de Electronic Arts Canada. En esta Knowledge Base, esta variante BPE se identifica por el marcador de método 46FBh.

In a Mega Drive ROM or a hex view, that marker appears as the two bytes 46 FB because the 68000-side data is normally read in big-endian order. The byte before FB selects the method, so 46FBh, 30FBh, and 10FBh are related identifiers, but they do not share the same decoder.En una ROM de Mega Drive o en una vista hexadecimal, ese marcador aparece como los dos bytes 46 FB porque los datos leídos por el 68000 suelen interpretarse en orden big-endian. El byte anterior a FB selecciona el método, así que 46FBh, 30FBh y 10FBh son identificadores relacionados, pero no comparten el mismo decodificador.

46 FB  ....  dictionary / pair data  ....  compressed payload
^^^^^
method marker seen in the stream as bytes 46 FB

46 FB  ....  diccionario / datos de pares  ....  payload comprimido
^^^^^
marcador de método visto en el flujo como bytes 46 FB

The marker is the start of the investigation, not the end of it. After finding 46 FB, the next job is to identify the block's own structure: whether sizes are stored nearby, whether the table comes before or after the payload, how many pair entries exist, and how the surrounding ROM points to the compressed asset.El marcador es el inicio de la investigación, no el final. Después de encontrar 46 FB, el siguiente trabajo es identificar la estructura propia del bloque: si los tamaños están guardados cerca, si la tabla viene antes o después del payload, cuántas entradas de pares existen y cómo la ROM apunta al recurso comprimido.

Integrated game decoderEl decodificador integrado en el juego

Many Electronic Arts Mega Drive / Genesis games include a generic 68000 decompression routine. It acts as a dispatcher: it reads the compressed block signature, normalizes the method byte, and jumps to the proper decoder instead of assuming one single format.Muchos juegos de Electronic Arts para Mega Drive / Genesis incluyen una rutina genérica de descompresión en 68000. Actúa como despachador: lee la firma del bloque comprimido, normaliza el byte de método y salta al decodificador adecuado en vez de asumir un único formato.

move.b  (a0)+,d3
cmpi.b  #$FB,(a0)+
bne     error_or_exit

btst    #0,d3
beq     continue_decode
addq.w  #3,a0

continue_decode:
andi.b  #$FE,d3

move.b  (a0)+,d3
cmpi.b  #$FB,(a0)+
bne     error_o_salida

btst    #0,d3
beq     continuar
addq.w  #3,a0

continuar:
andi.b  #$FE,d3

The ANDI.B #$FE,D3 instruction shows that the low bit of the identifier is used as a flag. A signature such as 47 FB is interpreted as 46 FB with three additional header bytes, and the same idea applies to 11 FB or 31 FB.La instrucción ANDI.B #$FE,D3 indica que el bit bajo del identificador se usa como flag. Una firma como 47 FB se interpreta como 46 FB con tres bytes adicionales de cabecera, y la misma idea se aplica a 11 FB o 31 FB.

10 FB  -> RefPack
30 FB  -> EA Huffman
32 FB  -> EA Huffman
34 FB  -> EA Huffman
46 FB  -> EA BPE
6E FB  -> uncompressed data, ASCII 'n'
72 FB  -> differential coding, ASCII 'r'
7A FB  -> RLE, ASCII 'z'

10 FB  -> RefPack
30 FB  -> EA Huffman
32 FB  -> EA Huffman
34 FB  -> EA Huffman
46 FB  -> EA BPE
6E FB  -> datos sin comprimir, ASCII 'n'
72 FB  -> codificación diferencial, ASCII 'r'
7A FB  -> RLE, ASCII 'z'

0C 03 00 10  -> cmpi.b #$10,d3  -> RefPack
0C 03 00 46  -> cmpi.b #$46,d3  -> EA BPE
0C 03 00 30  -> cmpi.b #$30,d3  -> EA Huffman
0C 03 00 32  -> cmpi.b #$32,d3  -> EA Huffman
0C 03 00 34  -> cmpi.b #$34,d3  -> EA Huffman

Compressed file structureEstructura del archivo comprimido

In the EA-style packed resources tracked here, the compressed stream is normally part of a larger resource record. The loader can use the total entry size and the high-bit-marked file name to locate the resource before the decompression dispatcher sees the XX FB header.En los recursos empaquetados de estilo EA documentados aquí, el flujo comprimido normalmente forma parte de un registro de recurso más grande. El loader puede usar el tamaño total de la entrada y el nombre de archivo marcado con bit alto para localizar el recurso antes de que el despachador de descompresión lea la cabecera XX FB.

Resource container entry

- Total entry size
  Covers the complete packed file record, including loader metadata,
  the name field, the compression header, and the compressed payload.

- Resource name
  Stored with its high bit set so the game loader can find this entry
  in the resource table or package.

- Packed file data
  The byte range handed to the decompression dispatcher.

  Compression header
  - Method signature: XX FB
  - Decompressed size: expected output length
  - Method payload: data interpreted by the selected decoder

Entrada del contenedor de recursos

- Tamaño total de la entrada
  Cubre el registro empaquetado completo, incluyendo metadatos del loader,
  el campo de nombre, la cabecera de compresión y el payload comprimido.

- Nombre del recurso
  Guardado con el bit alto activado para que el loader pueda encontrar esta
  entrada en la tabla o paquete de recursos.

- Datos del archivo empaquetado
  Rango de bytes entregado al despachador de descompresión.

  Cabecera de compresión
  - Firma de método: XX FB
  - Tamaño descomprimido: longitud de salida esperada
  - Payload del método: datos interpretados por el decodificador seleccionado

For EA BPE, the method payload is the 46FBh pair table or dictionary data plus the compressed token payload. The decompressed size is the length the loader expects after all pair tokens have expanded into literal bytes.En EA BPE, el payload del método contiene la tabla de pares o datos de diccionario 46FBh más el payload de tokens comprimidos. El tamaño descomprimido es la longitud que espera el loader después de que todos los tokens de pares se hayan expandido a bytes literales.

Decoding modelModelo de decodificación

The safest mental model is recursive token expansion. A token can be a literal byte, or it can name a pair in the dictionary. If the pair contains another token, the decoder expands that token before continuing. The output is complete only when every token has resolved to literal bytes.El modelo mental más seguro es la expansión recursiva de tokens. Un token puede ser un byte literal o puede nombrar un par dentro del diccionario. Si el par contiene otro token, el decodificador expande ese token antes de continuar. La salida solo está completa cuando todos los tokens se han resuelto en bytes literales.

function emitToken(token):
  if token is a literal byte:
    output token
    return

  left, right = pairTable[token]
  emitToken(left)
  emitToken(right)

for each token in the compressed payload:
  emitToken(token)

función emitirToken(token):
  si token es un byte literal:
    emitir token
    volver

  izquierda, derecha = tablaDePares[token]
  emitirToken(izquierda)
  emitirToken(derecha)

por cada token del payload comprimido:
  emitirToken(token)

Real game code may implement this with a stack, a small temporary buffer, repeated table lookups, or a hand-optimized 68000 loop. The observable result is the same: compressed tokens become the exact byte sequence expected by the graphics, map, text, or data loader that uses the decompressed asset.El código real del juego puede implementarlo con una pila, un pequeño buffer temporal, búsquedas repetidas en tabla o un bucle 68000 optimizado a mano. El resultado observable es el mismo: los tokens comprimidos se convierten en la secuencia exacta de bytes que espera el loader de gráficos, mapas, texto o datos que consume el recurso descomprimido.

Reverse engineering workflowFlujo de ingeniería inversa

1. Search the ROM for 46 FB and record every offset where it appears.Busca 46 FB en la ROM y registra todos los offsets donde aparezca.
2. Check whether those offsets are referenced by pointer tables, loading routines, asset indexes, or decompression dispatcher code.Comprueba si esos offsets están referenciados por tablas de punteros, rutinas de carga, índices de recursos o código del despachador de descompresión.
3. Identify the block boundary before decoding. A wrong end offset can make a correct algorithm look broken.Identifica el límite del bloque antes de decodificar. Un offset final incorrecto puede hacer que un algoritmo correcto parezca roto.
4. Separate dictionary data from compressed payload data, then test a small decoder against one known asset.Separa los datos de diccionario del payload comprimido y prueba un decodificador pequeño contra un recurso conocido.
5. Compare the decoded bytes with the expected target format: tiles, tilemaps, text, table data, or another intermediate structure.Compara los bytes decodificados con el formato esperado: tiles, tilemaps, texto, datos de tabla u otra estructura intermedia.
6. When recompressing, check whether the new compressed block still fits in place. If it does not, repoint or relocate the asset instead of overwriting adjacent data.Al recomprimir, comprueba si el nuevo bloque comprimido sigue cabiendo en su sitio. Si no cabe, repuntea o reubica el recurso en vez de sobrescribir datos adyacentes.

Related EA formatsFormatos EA relacionados

Electronic Arts titles can contain several compression methods in the same broader family of tools and asset pipelines. The method ID matters because BPE, Huffman, filtered Huffman, and RefPack-style compression need different decoders.Los juegos de Electronic Arts pueden contener varios métodos de compresión dentro de una misma familia amplia de herramientas y pipelines de recursos. El ID de método importa porque BPE, Huffman, Huffman con filtro y RefPack necesitan decodificadores distintos.

Common pitfallsErrores habituales

• Reading 46 FB in the wrong byte order and then searching for the wrong method ID.Leer 46 FB con el orden de bytes equivocado y acabar buscando el ID de método incorrecto.
• Expanding a pair token only once when the stream actually expects recursive expansion.Expandir un token de par solo una vez cuando el flujo espera expansión recursiva.
• Assuming the compressed size and decompressed size are stored in the same place across every EA title.Asumir que el tamaño comprimido y el tamaño descomprimido se guardan en el mismo sitio en todos los juegos de EA.
• Recompressing data that decodes correctly but no longer fits the original block allocation.Recomprimir datos que decodifican bien pero ya no caben en la asignación original del bloque.
• Mistaking valid compressed bytes for graphics corruption before the final decompressed asset has been checked.Confundir bytes comprimidos válidos con gráficos corruptos antes de comprobar el recurso final descomprimido.