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

What is Byte-Pair Encoding?Qué es Byte-Pair Encoding

Byte-Pair Encoding, usually shortened to BPE, is a dictionary-style compression technique built around repeated pairs of symbols or bytes. A compressor finds a pair that appears often, assigns that pair to another value called a token, and writes the token instead of writing the pair again and again.Byte-Pair Encoding, normalmente abreviado como BPE, es una técnica de compresión basada en diccionario alrededor de pares repetidos de símbolos o bytes. Un compresor encuentra un par que aparece muchas veces, asigna ese par a otro valor llamado token y escribe el token en vez de repetir el par una y otra vez.

The idea is independent of Mega Drive hardware. BPE can be applied to text, graphics, maps, tables, or any other byte stream where repeated adjacent values are common. On a cartridge game, the important reverse-engineering work is discovering how a particular game stores its dictionary and how its decoder expands tokens back into the original data.La idea es independiente del hardware de Mega Drive. BPE puede aplicarse a texto, gráficos, mapas, tablas o cualquier flujo de bytes donde sean comunes los valores adyacentes repetidos. En un juego de cartucho, el trabajo importante de ingeniería inversa es descubrir cómo ese juego guarda su diccionario y cómo su decodificador expande los tokens de vuelta a los datos originales.

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

BPE is a technique, not a file formatBPE es una técnica, no un formato de archivo

This distinction matters in ROM hacking because the decoder expects the exact storage choices made by that game's engine or toolchain: where the dictionary lives, how many entries it has, which bytes are literals, which values are tokens, how blocks are split, and how the output size is known.Esta distincion importa en romhacking porque el decodificador espera las decisiones exactas de almacenamiento tomadas por el motor o la herramienta de ese juego: donde vive el diccionario, cuantas entradas tiene, que bytes son literales, que valores son tokens, como se dividen los bloques y como se conoce el tamaño de salida.

• BPE does not define header structure.BPE no define la estructura de cabecera.
• BPE does not define dictionary location or serialization.BPE no define la ubicacion ni serializacion del diccionario.
• BPE does not define token ranges, literal representation, block sizes, or end markers.BPE no define rangos de tokens, representacion de literales, tamaños de bloque ni marcadores de fin.
• Resource containers belong to the game or publisher pipeline, not to the BPE concept itself.Los contenedores de recursos pertenecen al juego o pipeline del publisher, no al concepto BPE en si.

How BPE compression worksCómo funciona la compresión BPE

A practical BPE encoder usually works by repeatedly choosing substitutions that reduce the final size. The exact scoring rules are implementation-specific, but the broad idea is to trade repeated source bytes for a shorter token stream plus a dictionary that explains those tokens.Un codificador BPE practico suele funcionar eligiendo sustituciones repetidamente mientras reduzcan el tamaño final. Las reglas exactas de puntuacion dependen de cada implementación, pero la idea general es intercambiar bytes fuente repetidos por un flujo de tokens más corto más un diccionario que explica esos tokens.

How BPE decompression worksCómo funciona la descompresión BPE

The decoder reads one value from the compressed stream. If that value is a literal, it writes the byte directly to the output. If that value is a BPE token, it looks up the pair assigned to that token, then emits the left and right values. Either side of that pair may itself be another token.El decodificador lee un valor del flujo comprimido. Si ese valor es un literal, escribe el byte directamente en la salida. Si ese valor es un token BPE, busca el par asignado a ese token y emite el valor izquierdo y el derecho. Cualquiera de los dos lados del par puede ser a su vez otro token.

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)

This is why simply finding compressed-looking bytes is not enough. The pair table, token rules, and stream boundary must all match the game's decoder.Por eso no basta con encontrar bytes que parezcan comprimidos. La tabla de pares, las reglas de tokens y el limite del flujo deben coincidir con el decodificador del juego.

Recursive pair expansionExpansión recursiva de pares

Recursive expansion is what lets a small pair dictionary represent longer repeated sequences. A token can expand into a literal plus another token, or even into two tokens, so one input value can unfold into several output bytes.La expansión recursiva permite que un diccionario pequeño de pares represente secuencias repetidas más largas. Un token puede expandirse en un literal más otro token, o incluso en dos tokens, de modo que un valor de entrada puede desplegarse en varios bytes de salida.

Token 81
   |
   +-- Token 80
   |      |
   |      +-- 41
   |      +-- 42
   |
   +-- 43

Output:
41 42 43

Why BPE can compress game resources effectivelyPor que BPE puede comprimir recursos de juego

BPE is useful when the source data contains repeated adjacent values. Cartridge games often have structured data where those patterns appear naturally, but BPE is not inherently tied to graphics, text, or any single asset type. It works only when the actual bytes make pair substitution worthwhile.BPE es util cuando los datos fuente contienen valores adyacentes repetidos. Los juegos de cartucho suelen tener datos estructurados donde esos patrones aparecen de forma natural, pero BPE no está ligado de manera inherente a gráficos, texto ni ningun tipo unico de recurso. Funciona solo cuando los bytes reales hacen que la sustitucion de pares merezca la pena.

Compression ratio vs dictionary costRatio de compresión frente a coste del diccionario

Every substitution saves bytes in the payload, but every substitution also costs space in the dictionary. BPE is worthwhile only when the saved payload bytes exceed the storage required to describe the new token.Cada sustitucion ahorra bytes en el payload, pero cada sustitucion tambien cuesta espacio en el diccionario. BPE merece la pena solo cuando los bytes ahorrados en el payload superan el almacenamiento necesario para describir el nuevo token.

Space saved by substitutions
        vs.
Space required by dictionary

A pair that occurs only a few times can increase the final block size. A sensible encoder stops adding new pairs when additional substitutions no longer produce a useful saving or when the game's dictionary limit has been reached.Un par que aparece solo unas pocas veces puede aumentar el tamaño final del bloque. Un codificador sensato deja de anadir pares cuando las sustituciones adicionales ya no producen ahorro util o cuando se alcanza el limite de diccionario del juego.

BPE on Mega Drive / GenesisBPE en Mega Drive / Genesis

Mega Drive hardware does not understand BPE. Decompression is performed in software, usually by a Motorola 68000 routine that reads compressed data from ROM, expands it into RAM or a temporary buffer, and then hands the result to the game engine or transfers it to VRAM.El hardware de Mega Drive no entiende BPE. La descompresión se realiza por software, normalmente con una rutina Motorola 68000 que lee datos comprimidos desde ROM, los expande en RAM o en un buffer temporal y luego entrega el resultado al motor del juego o lo transfiere a VRAM.

ROM compressed data
        |
        v
Read dictionary
        |
        v
Read compressed tokens
        |
        v
Expand BPE pairs
        |
        v
RAM / output buffer
        |
        v
Game resource / VRAM transfer

How to recognize BPE in a ROMCómo reconocer BPE en una ROM

The strongest evidence for BPE comes from the decoding routine, not from one magic byte sequence. Look for code that repeatedly resolves one input value into two output values, especially when some of those values are then resolved again through the same table.La evidencia más fuerte de BPE viene de la rutina de decodificación, no de una secuencia magica de bytes. Busca codigo que resuelva repetidamente un valor de entrada en dos valores de salida, sobre todo cuando algunos de esos valores vuelven a resolverse mediante la misma tabla.

• A table containing pairs of byte values.Una tabla que contiene pares de valores byte.
• Compressed stream values repeatedly indexing that table.Valores del flujo comprimido indexando repetidamente esa tabla.
• Recursive token expansion rather than one-byte output per input byte.Expansión recursiva de tokens en vez de una salida de un byte por cada byte de entrada.
• An output stream significantly larger than the compressed input.Un flujo de salida significativamente mayor que la entrada comprimida.
• A resource that looks invalid until it passes through the decoder.Un recurso que parece invalido hasta que pasa por el decodificador.

Reverse engineering a BPE decoderIngeniería inversa de un decodificador BPE

Resource pointer
      |
      v
Resource loader
      |
      v
Compressed data
      |
      v
Decoder
      |
      v
Dictionary lookup
      |
      v
Expanded output

After you find the loader and decoder, document the fields the routine actually uses. The goal is not just to decompress one asset once, but to understand the contract a future encoder must satisfy.Despues de encontrar el cargador y el decodificador, documenta los campos que la rutina usa realmente. El objetivo no es solo descomprimir un recurso una vez, sino entender el contrato que un codificador futuro debe cumplir.

• Where the dictionary begins and how many entries it contains.Dónde empieza el diccionario y cuantas entradas contiene.
• Which values are literals and which values represent tokens.Que valores son literales y cuales representan tokens.
• Whether tokens can reference other tokens.Si los tokens pueden referenciar otros tokens.
• How the decoder detects the end of the stream.Cómo detecta el decodificador el final del flujo.
• How output size is determined.Cómo se determina el tamaño de salida.
• Whether resources are divided into blocks.Si los recursos están divididos en bloques.

Recompressing BPE dataRecomprimir datos BPE

Understanding the decoder is only half the work. To modify a BPE-compressed resource, a ROM hacker may need an encoder that creates a new stream accepted by the original game's decoder. The new stream usually does not need to be byte-identical to the original; it only needs to obey the same format rules.Entender el decodificador es solo la mitad del trabajo. Para modificar un recurso comprimido con BPE, un romhacker puede necesitar un codificador que cree un nuevo flujo aceptado por el decodificador original del juego. Normalmente el nuevo flujo no tiene que ser identico byte a byte al original; solo tiene que obedecer las mismás reglas de formato.

Modified asset
      |
      v
Build pair dictionary
      |
      v
Choose replacement tokens
      |
      v
Write dictionary + token stream
      |
      v
Fit in original space or relocate resource

• Avoid token conflicts with literal values.Evita conflictos de tokens con valores literales.
• Preserve recursive dictionary rules accepted by the original decoder.Conserva las reglas de diccionario recursivo aceptadas por el decodificador original.
• Respect dictionary size, payload size, and expected output length.Respeta tamaño de diccionario, tamaño de payload y longitud de salida esperada.
• If the block no longer fits, relocate it and update the pointers instead of truncating it.Si el bloque ya no cabe, reubícalo y actualiza punteros en vez de truncarlo.

Mega Drive / Genesis games using BPEJuegos de Mega Drive / Genesis que usan BPE

This list is intentionally conservative. A game should be added only when the BPE decoder, compressed resource, and decoded asset type have been verified, or when an external report is clearly marked with its evidence level. At the time of this revision, no title-level BPE entry is published here without that verification.Esta lista es deliberadamente conservadora. Un juego debe añadirse solo cuando se hayan verificado el decodificador BPE, el recurso comprimido y el tipo de recurso decodificado, o cuando un reporte externo esté marcado claramente con su nivel de evidencia. En el momento de esta revisión, no se publica aquí ninguna entrada BPE por título sin esa verificacion.

Example: Electronic Arts 46FBh implementationEjemplo: implementación Electronic Arts 46FBh

Some Electronic Arts Mega Drive titles use a BPE implementation identified by the 46FBh method marker. This is a useful case study because the marker can guide an investigation inside EA resource data, but it does not define BPE in general.Algunos títulos de Electronic Arts para Mega Drive usan una implementación BPE identificada por el marcador de método 46FBh. Es un caso de estudio util porque el marcador puede orientar una investigación dentro de datos de recursos EA, pero no define BPE en general.

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

Common pitfallsErrores habituales

• Treating BPE as one fixed file format instead of a technique implemented differently by each game.Tratar BPE como un formato de archivo fijo en vez de una técnica implementada de forma distinta por cada juego.
• Assuming 46 FB is the generic signature for BPE.Asumir que 46 FB es la firma genérica de BPE.
• Expanding a pair token only once when the stream expects recursive expansion.Expandir un token de par solo una vez cuando el flujo espera expansión recursiva.
• Ignoring dictionary cost when recompressing a modified asset.Ignorar el coste del diccionario al recomprimir un recurso modificado.
• Publishing a game as BPE-confirmed without recording the decoder evidence or decoded resource type.Publicar un juego como confirmado con BPE sin documentar la evidencia del decodificador o el tipo de recurso decodificado.

Further reading / related compression articlesLecturas relacionadas sobre compresión

BPE sits beside other compression families rather than replacing them. Compare the core ideas briefly, then move to format-specific articles when the ROM evidence points to another decoder.BPE convive con otras familias de compresión en vez de sustituirlas. Compara brevemente las ideas base y luego pasa a artículos específicos cuando la evidencia de la ROM apunte a otro decodificador.