UFTC compression

UFTC ("ultra fast tile compression") is a graphics compression format for Mega Drive homebrew. Its compression ratio isn't that great (about 50% if you use it as intended), but its main appeal is that it can be decompressed on the fly reasonably quickly, making it useful for streaming sprites and the like.

Miniplanets uses this format for Qisha's sprites as well as streaming graphics like the water and moving platforms.

If you just want to use UFTC and don't care about writing it yourself then skip ahead to the tools section and ignore the rest. This page is here to describe how the format works.

Tools and decompression code

You can download the UFTC source code from here. Includes compression tool as well as assembly and C routines for decompressing the data. They're under the zlib license (which means you don't even need to include a credit).

The tool to make UFTC files as well as code to decompress it on the Mega Drive can also be found in the mdtools GitHub repository.

How UFTC compression works

UFTC works by using a "dictionary" approach: every tile is split into 4×4 pixel blocks, and then it makes a list of every unique 4×4 block. Then every tile is stored as a list of four indices (one index for each block). Since indices are smaller, it saves space whenever a block is repeated.

UFTC files have this structure:

  1. Number of blocks
  2. List of every 4×4 block
  3. List of every tile

The first number is just a 16-bit value that says how many blocks are in the block list. This is used to tell where the list of tiles starts. The number may be up to 8192.

Then comes every unique 4×4 block. Each block is 8 bytes, with every 16-bit word representing 4 pixels (with 4-bit per pixel)… think of these as how VDP would store the tiles if they were 4×4 instead of 8×8.

Finally comes the list of every tile. Every tile consists of four words:

  1. Index for top left 4×4 block
  2. Index for top right 4×4 block
  3. Index for bottom left 4×4 block
  4. Index for bottom right 4×4 block

The index is the offset inside the list of each 8×8 block (i.e. measured in bytes).

Since everything takes up a fixed amount of space, it's feasible to decompress arbitrary tiles from the middle of the stream (i.e. random access). You should compress entire spritesheets with UFTC and then decompress the tiles you need out of it to make optimal use of it (the more graphics, the more likely that it'll find common blocks).

UFTC15 and UFTC16

The description above is for the UFTC16 variant.

Early versions of the decompression code using word offsets (which are signed), limiting the amount of unique 8×8 blocks to 4096. These versions are called "UTFC15". Later versions of the decompression code use unsigned offsets (at the same speed) and can address up to 8192 blocks, these are called "UTFC16".

The newer decompressor can safely read data compressed for the older version (it's backwards compatible), so there really isn't any motive to use the older variant unless you can't change the decompression code for whatever reason.