How do I interpret these instructions for decompressing game data? [closed]

Question

I'm trying to write a tool for the 1994 SNES game Super Metroid that creates "out of bound" maps for each the game's rooms. To do so, first I need to extract the tile-by-tile data of each room. For example, the screen below shows 16 x 16 tiles, though of course the room itself is much bigger.

There's this incredible guide that details the ROM. Using it, I've found some example room data:

^{* Actually, it goes beyond the highlighted area. I just don't know yet how many bytes are room data.}

This room data is compressed though. The guide doesn't go into the details of decompression, and the only resource I can find about how to decompress that data is a .txt file uploaded in 2011 to romhacking.net. Here are its contents:

  +--------------------------------------------------------------------------------------------------------------+
  |=Decompression=Routine=[$80:B0FF-$80:B270]====================================================================|
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |=Command=Name=|=Hex=|=Binary====|=Syntax==================|=Range======|=Notes================================|
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $00 | %00000000 |                         |            | Copies the next (# + 1) bytes from   |
  | Direct Copy  |  .. |  CMD..... | [%000xxxxx : xxxxx = #] | 1-32 bytes | Compressed Data (CD) to RAM.         |
  |              | $1F | %00011111 |                         |            |                                      |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $20 | %00100000 |                         |            | Writes the next byte (# + 1) bytes   |
  | Byte Fill    |  .. |  CMD..... | [%001xxxxx : xxxxx = #] | 1-32 bytes | deep to RAM.                         |
  |              | $3F | %00111111 |                         |            |                                      |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $40 | %01000000 |                         |            | Writes the next word (# + 1) bytes   |
  | Word Fill    |  .. |  CMD..... | [%010xxxxx : xxxxx = #] | 1-32 bytes | deep to RAM.                         |
  |              | $5F | %01011111 |                         |            |                                      |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $60 | %01100000 |                         |            | Writes the next byte to RAM. Then    |
  | Sigma Fill   |  .. |  CMD..... | [%011xxxxx : xxxxx = #] | 1-32 bytes | adds 1 to that byte and writes it    |
  |              | $7F | %01100000 |                         |            | again...etc.  Writes (# + 1) times.  |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $80 | %10000000 |                         |            | Copies (# + 1) bytes from the RAM    |
  | Library Copy |  .. |  CMD..... | [%100xxxxx : xxxxx = #] | 1-32 bytes | address provided in the next two     |
  |              | $9F | %10011111 |                         |            | bytes.                               |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $A0 | %10100000 |                         | 1-32 bytes | Much like the Library Copy. The only |
  | EORed Copy   |  .. |  CMD..... | [%101xxxxx : xxxxx = #] | $7F:0000 - | difference is that all data copied   |
  |              | $BF | %10111111 |                         | $7F:FFFF   | is EORed with %11111111.             |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $C0 | %11000000 |                         | 1-32 bytes | Subtracts next byte from Y, the RAM  |
  | Minus Copy   |  .. |  CMD..... | [%110xxxxx : xxxxx = #] | 0-255 from | offset, and copies (# + 1) bytes to  |
  |              | $DF | %11011111 |                         | current Y  | current Y. Can copy last tile.       |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              | $E0 | %111 000 00-->Bits 8 9 of X (aka #) | 1-1024     | Extends the range of previous CMDs   |
  |              |     |      |||      --------------------- |      bytes | from 1-32, to 1-1024 bytes deep.     |
  |              |     |      CMD----->Command Code. Any one |            |                                      |
  | Extended CMD |  .. |               of the previous 7 CMD | $7F:0000 - | Specifically, Bits 7-5 flag the ECMD,|
  |              |     |               patterns can go here. | $7F:FFFF   | & Bits 4-2 are interpreted as a CMD. |
  |              |     |               --------------------- |     RAM    | Bits 1-0 & the next byte are treated |
  |              | $FE | %111 111 11                         |            | as a 10-bit value for X, aka #.      |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+
  |              |     |           |                         |            |                                      |
  | Terminate SR | $FF | %11111111 |       [%11111111]       |    ----    | Terminates Sub Routine               |
  |              |     |           |                         |            |                                      |
  +--------------+-----+-----------+-------------------------+------------+--------------------------------------+

^{** Full credit to um... UnicornPoop.}

I understand each of these rows to be sequential instructions. What am I missing though to translate this into pseudocode that a non-"old school" programmer like myself can understand? For example, take this:

Copies the next (# + 1) bytes from Compressed Data (CD) to RAM.

What is #? What exactly am I supposed to do to the room data, 01 00 0a e9 ...? Or what knowledge am I missing to understand what's going on here.

Thanks in advance.

Answer 1

I understand each of these rows to be sequential instructions.

Exactly, they are description (opcodes and data structure) for the virtual machine which is the decoder.

What am I missing though to translate this into pseudocode that a non-"old school" programmer like myself can understand?

There is nothing 'old school' in there. Virtual machines are still made all around today.

For example, take this:

Copies the next (# + 1) bytes from Compressed Data (CD) to RAM.

What is #?

The parameter (# == Number Symbol). In this case the number of bytes that get (should be) copied from input stream (compressed data or program, as you like it) to output (image in RAM).

It's described quite in detail when reading the each entry.

• Command Name
  • Direct Copy
• Encoding Range in Hex
  • $00..$1F
• Encoding Range in Binary
  • %0000 0000 - %0001 1111
• Syntax
  • [%000x xxxx : x xxxx = #] meaning a byte (% -> in Binary) containing 000 as (its) opcode portion, while x xxxxis to be taken as a (parameter) value further called # (here the length)
• Range of the Command (Parameters)
  • 1..32
• Notes/Description
  • Copies the next (# + 1) bytes from Compressed Data (CD) to RAM.

I wouldn't know what to describe better here

What exactly am I supposed to do to the room data, 01 00 0a e9 ...?

Let the virtual machine, described in the table, run it, to transform input (it's program) into output (image in RAM).

• 01 -> Opcode 0 (Copy Data) with data length 2 (%00.0001 + 1)
  • 00 0A -> Two bytes of data to be copied to output
• E9 3F -> Extended (length) Opcode 7 Sub-Opcode 2 (Write Word) with length 320 (%01.0011.1111 + 1)
  • 44 80 -> Two bytes of word data for to be written as 64 bytes to output (32 times)
• 48 -> Opcode 2 (Write Word) with length 9 (%00.1000 + 1)
  • 11 89 -> Two bytes of word data for to be written as 9(!) bytes to output (4 1/2 times)
• ... and so on ...

Or what knowledge am I missing to understand what's going on here.

Not sure, as all is in the table, so it would be good if you point out what parts are unclear.

---

Postscript: I haven't really peeked into that encoding before, but looking close it's a really nifty way of RLE, adapted for the special need of repetitive tile data. Especially the library copy (arbitrary template), minus copy (tile repetition) and EOR copy (background inversion). I like that.

Answer 2

Those codes have nothing to do with the CPU instructions. You write the program that interprets the compressed data according to the given rules to decompress it.

The # is the bits marked with x in the commands. # represents a parameter how much data to operate on.

The first command byte is 01h, it is a direct copy command with # value 1, so copy next 2 bytes of data to destination (00h 0Ah).

After that, the next command byte is E9h. It is an extended command. Command 010 is 2, word fill. The command byte gives two extra bits for the byte count in next byte (3Fh), so parameter is 13Fh. The fill count is 140h, and the data to fill with is the next word (44h 80h).

Next command is 48h.

Answer 3

What am I missing though to translate this into pseudocode that a non-"old school" programmer like myself can understand?

It's hard to say what you're missing. It certainly doesn't seem to require any prior knowledge of 6502 machine code.

I understand each of these rows to be sequential instructions.

Yes. The compressed map is a mini-"program". Each row in the table describes one instruction for the decoder. The decoder is a routine that acts like an interpreter for the compressed map.

The first 3 bits of the byte act as an "opcode" of sorts, which tells the decoder what operation to perform. The operation is explained in the rightmost column.

What is #?

It's the final 5 bits of the byte. They act like an operand or argument to the opcode. What it does with this argument depends on the instruction and is again listed in the rightmost column.

What exactly am I supposed to do to the room data, 01 00 0a e9 ...?

You need to make an interpreter that runs the compressed data as a program. Something like this:

Keep a "program counter" that points at the first byte. Make a loop that runs until the program counter has completed the program. Read the byte at the program counter's current location, check that byte's first 3 bits (logical AND with $E0) and look up the correct instruction based on the table above, and call a function that represents that instruction with the final 5 bits as an argument. Do what the table tells you to do, and increment the program counter accordingly so it's ready to read the next command byte.