This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Tile compression formats

Tile compression formats
by on (#130347)
After having read a topic about making a graphics hack for Blades of Steel, I decided to write a long-awaited wiki article about tile compression. Currently it covers a few byte-level RLE formats and the pixel-level RLE/Markov thing that Codemasters used and tokumaru reverse engineered. What other tile compression formats are used for 2-bit tiles in commercial NES, Super NES, GB, and GBC releases?
Re: Tile compression formats
by on (#130355)
Now I have to pull out my old Oracle of Ages editor...
Oracle of Ages used one of 4 possible formats: Uncompressed, LZ (short words), LZ (long words), and a bitmask indicating which of the next 16 bytes uses a common byte.

LZ:
mask = read a byte
This determines whether the next 8 things processed are LZ runs or raw bytes, starting with the most significant bit of 'mask'. After processing 8 things, if there are still bytes remaining to decompress, read a new byte for 'mask'.
LZ run (bit is 1):
short word mode:
read a byte
LLLDDDDD
L = length (add 1)
D = distance
If value of L is zero, read a byte and use that for length instead.

long word mode:
read two bytes
DDDDDDDD low byte of LZ distance
LLLLLDDD high byte of LZ distance, length (add 1)
If value of L is zero, read a byte and use that for length instead.

Add ~Distance (bitwise complement) to Destination pointer, copy Length bytes.

16 byte with common:
Read two bytes
MMMMMMMM Mask indicating which bytes use the common byte
MMMMMMMM
If M is zero, just copy 16 bytes.
Otherwise
Read a byte, this is the Common byte.
look at each bit of M (starting with most significant bit of first byte)
If it's 1, output the Common byte
otherwise, copy a byte.


Code I used to decompress it: (BP and CBP are classes that act like byte pointers but do bounds checking)
Code:
void lzdecompress(BP dest, CBP src,int length, bool LWM)
{
   int bitsleft=1;
   u8 mask=0;
   while (length>0)
   {
      bitsleft--;
      mask<<=1;
      if (bitsleft==0)
      {
         bitsleft=8;
         mask=*src++;
      }
      if (mask & 0x80)
      {
         int lzdist1=0,lzdist2=0;
         int lzlength=0;
         if (LWM)
         {
            lzdist1=*src++;
            int a=*src++;
            lzdist2=a & 7;
            a=a>>3;
            if (a!=0)
            {
               lzlength=a+2;
            }
            else
            {
               lzlength=*src++;
               if (lzlength==0) lzlength=256;
            }
         }
         else
         {
            int a=*src++;
            lzdist1=a & 0x1F;
            lzdist2=0;
            a>>=5;
            if (a==0)
            {
               lzlength=*src++;
               if (lzlength==0) lzlength=256;
            }
            else
            {
               lzlength=a+1;
            }
         }
         int i;
         s16 lzdist16= (lzdist1^0xFF) | ((lzdist2^0xFF)<<8);
         BP src2=dest+ lzdist16;
         for (i=0;i<lzlength;i++)
         {
            *dest++=*src2++;
            length--;
            if (length==0) return;
         }
      }
      else
      {
         *dest++=*src++;
         length--;
      }
   }
}

void unpack_16_common(BP*dest_p, CBP*src_p)
{
   BP &dest = *dest_p;
   CBP &src = *src_p;
   int length=16;
   u16 mask=src.getu16be();
   if (mask==0)
   {
      memcpy(&dest[0],&src[0],16);
      dest+=16;
      src+=16;
      return;
   }
   else
   {
      u8 common=*src++;
      int i;
      for (i=0;i<16;i++)
      {
         if (mask & 0x8000)
         {
            *dest++=common;
         }
         else
         {
            *dest++=*src++;
         }
         mask<<=1;
      }
   }
}
Re: Tile compression formats
by on (#130359)
Thanks for the info; I'll summarize to the wiki.

Of these, long word mode is least likely to work well on an NES due to the required 2 KiB state, which exceeds the NES's built-in work RAM. (The GBC has 4K of work RAM, 28K of switchable work RAM, and memory-mapped VRAM.) Is the limit of 32-byte back references a big handicap in short word mode? And how does common byte compare in ratio to RLE methods? (Yeah, I know plain RLE doesn't work well on Game Boy tiles without deinterleaving the tiles into NES format first; assume that.)
Re: Tile compression formats
by on (#149357)
Final Fantasy Legend 3 uses a similar scheme to the Zelda/Oracle "common byte" scheme. Oddly, only the title screen and the monster graphics seem to be compressed; the field sprites and BG tiles, battle animation sprites, and the text font are all uncompressed.

The first byte of a compressed stream indicates the granularity of the common/predicted bytes for the entire stream: 0 means one predicted byte per 8 output bytes, 1 means one per 16 output bytes, 2 means one per 32 output bytes, 3 means one per 64 output bytes. Then each block of compressed data consists of a predicted byte, followed by 1/2/4/8 bytes of mask (depending on the granularity), followed by however many unpredicted bytes are needed. The mask bytes are used in order, MSB first within each byte (same as the Zelda scheme), however a 0 bit indicates a predicted byte and a 1 bit indicates an unpredicted byte (the opposite of Zelda)

The two bitplanes of an entire image are compressed as two separate streams (each with its own granularity selector byte); they get interleaved while being uploaded to VRAM.
Re: Tile compression formats
by on (#149735)
My old company used Pucrunch for our Gameboy, GBC, and GBA games (I even ported it to Nintendo DS at one point). Pucrunch started as a C-64 codec. A couple example games that used it, the two GBC Harry Potter games. If I remember right, it was a form of RLE.
Re: Tile compression formats
by on (#149763)
Most of HAL's NES/SNES/GB games used a sort of RLE/LZ77 derivative (NES games only used it for other things than graphics, due to using CHR-ROM, but I know it was used for planar graphics in SNES and possibly GB games as well).

I wrote about it back when I was documenting Kirby's Dream Course. It'd also been previously documented as used in either Kirby's Adventure or Dream Land (by Parasyte?) and in Earthbound (though the only specific documentation I found for it on PKHack has some pretty glaring mistakes...)

Here's my own decompression/compression implementation that I use in my Kirby's Adventure / Dream Course level editors.

The format itself is pretty simple; the only tricky thing about it is that it can essentially do reversal of bits or bytes in a sequence (which seems to work well for graphics in some cases). It's extremely similar to the compression format used by Pokémon G/S/C, but that one has a few different individual compression methods that I don't actually remember the behavior of.
Re: Tile compression formats
by on (#149784)
Seems everyone and their dog had their own LZ77/RLE hybrid. Konami used yet another variant in Tokimeki Memorial (and probably other SNES games) for everything from graphic tiles to tilemaps to the SPC700 driver program. Rather than try to describe it I'll just paste the decompressor I wrote some years ago in rather nasty Python:

Code:
#!/usr/bin/python

import sys, struct

try:
   inputfile = sys.argv[1]
   offset = int(sys.argv[2],0)
   outputfile = sys.argv[3]

except (IndexError, ValueError):
   sys.exit("Usage: decompress inputfile offset outputfile\n")

# convert LoROM address to file offset
if (offset >= 0x800000) and (offset & 0xffff >= 0x8000):
   offset = ((offset & 0x7f0000) >> 1) | (offset & 0x7fff)

f = open(inputfile, "rb")
f.seek(offset)
length = struct.unpack("<H", f.read(2))

interleave = (length[0] & 0x8000)
length = (length[0] & 0x7fff) - 2
data = bytearray(f.read(length))
print "Length: %04X (%06X - %06X)" % (length + 2, offset, f.tell())
if interleave: print "Interleaved"
f.close()

i = 0

output = bytearray()

while i < length:
   x = data[i]
   if x < 0x80:   # 00-7F: reference
      count = (x >> 2) + 2
      offset = (x << 8) + data[i + 1] + 0x21
      i += 2
      offset = (offset & 0x3ff) | (len(output) & ~0x3ff)
      if offset >= len(output): offset -= 0x400
      for j in range(count):
         output.append(output[offset + j])
   elif x < 0xa0:   # 80-9F: literal
      count = (x & 0x1f)
      i += 1
      output.extend(data[i:i + count])
      i += count
   elif x < 0xc0:   # A0-BF: expand bytes to words
      count = (x & 0x1f) + 2
      i += 1
      for j in range(count):
         output.extend((0, data[i]))
         i += 1
   elif x < 0xe0:   # C0-DF: repeat byte
      count = (x & 0x1f) + 2
      repeat = data[i + 1]
      output.extend((repeat,) * count)
      i += 2
   elif x < 0xff:   # E0-FE: repeat zero
      count = (x & 0x1f) + 2
      output.extend((0,) * count)
      i += 1
   else:         # FF: repeat zero more
      count = (data[i + 1]) + 2
      output.extend((0,) * count)
      i += 2

if interleave:
   if len(output) & 0xf:
      print "Interleave bit set but length not divisible by 16, wtf?"
   temp = bytearray((0,) * 16)
   for i in range(len(output) / 16):
      x = output[i * 16:(i + 1) * 16]
      for j in range(8):
         temp[2 * j    ] = x[j]
         temp[2 * j + 1] = x[j + 8]
      output[i * 16:(i + 1) * 16] = temp

f = open(outputfile, "wb")
f.write(output)
f.close()


An interesting quirk of this one is the optional "interleave" step, which essentially converts NES format tile data to SNES format. Evidently separated bitplanes compress better than interleaved ones.