1

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.

enter image description here

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

enter image description here

* 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.

  • 1
    A nit on the title - these are not 65C816 instructions, but a bytecode that's independent of the CPU, interpreted by program code stored elsewhere in the ROM. – Chromatix Apr 18 at 9:59
  • @Chromatix - Yup, thanks. Now that makes sense to me but at the time of posting I of course couldn't know that :p I'll keep it as is for posterity. – Andrew Cheong Apr 18 at 10:08
2

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.

| improve this answer | |
  • 1
    Thank you, thank you. I was missing the insight that these bytes might be virtual machine "code", i.e. I thought it was pure data that some algorithm (having nothing to do with the data) would unpack. So the table seemed opaque to me and I incorrectly assumed it was old-school magic. Everything is clear now. Wish I could accept both your answers, apologies. – Andrew Cheong Apr 18 at 10:07
  • 2
    @AndrewCheong In the end, all code is as well data and vice versa. Either still needs an algorithm to process it. On a fundamental level it doesn't matter if one sees the first 3 bits as an opcode for a CPU/virtual machine, or a format marker within the data structure. Calling it a virtual machine or a decoder just helps to pick a preferred PoV. I feel that, when thinking about the process of decoding, the VM PoV is more helpful - while when (creating an) encoding (scheme), the data driven approach may lead. After all, this is about squeezing out the last bit (sensible) possible :)) – Raffzahn Apr 18 at 10:28
  • 3
    Yep. Even a decompression program for a format like RLE (run-length encoding) can be thought of as an interpreter. Sure, there is only one kind of instruction, which means "repeat the operand this many times in the output", but we're still fundamentally doing the same thing. – tobiasvl Apr 18 at 10:34
  • 2
    @tobiasvl In fact and for most parts, this is simply a RLE some bells and whistles :) – Raffzahn Apr 18 at 10:39
  • 2
    Huh. I never thought of it that way but now I totally see it. Even a bitmap (image) file, is in some way instructing the interpreter (MSPaint.exe) what to draw. Thanks for that insight. – Andrew Cheong Apr 18 at 10:40
5

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.

| improve this answer | |
  • Doesn't command 2 say "Word Fill" and "Next Word" - so I would interpret the parameter for E9 3Fas 44 80, which is to be taken as word and stored continuous in the next 320 bytes (160 times). – Raffzahn Apr 18 at 9:34
  • Ah indeed. Thanks. – Justme Apr 18 at 10:01
  • Thanks so much. It was just beginning to dawn on me that the "data" might actually be "code" when you posted your answer, and your run-through also helps me validate that I'm doing the math correctly (with @Raffzahn's correction). – Andrew Cheong Apr 18 at 10:04
1

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.

| improve this answer | |
  • Hey, thanks! Yeah, when I said "sequential instructions" I literally thought this table was describing a decompression algorithm, like, do a direct copy, then do a byte fill, then do a ... and I was like, "How can a decompression algorithm possibly be this short?" Now I see the table describes an interpreter as you said. – Andrew Cheong Apr 18 at 10:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.