UFTC, as I understand Sik's description at sonicretro #25105 and the compressor source code, breaks each tile into four 4x4-pixel quadrants, stores all quadrants in a dictionary, and stores each as a list of dictionary indices of the four quadrants that make it up. It decompresses well on a system with 4-bit packed pixels and 16-bit memory, such as the Sega Genesis or Game Boy Advance.In [url=http://forums.nesdev.com/viewtopic.php?p=167589#p167589]this post[/url], Sik wrote:Also pixelart doesn't really compress that well in the first place since there isn't much redundancy at all within a sprite (UFTC exploits the fact that among different sprites from the same animation there may be some repeated portions as well as a good chunk of blank pixels, but even then it barely makes it to about half the size in the best cases).
But decompressing UFTC on a planar system, such as ColecoVision/SG-1000, NES, SMS, TG16, Game Boy, or Super NES, would require a fast shift by 4 to pack and unpack the nibbles that represent 4x1-pixel slivers. A lot of these 8-bit-era CPUs take time to shift proportional to the shift distance. Exceptions include the SWAP instruction of the Game Boy's Z80-like CPU and the S-CPU's multiplier (write $4202=$10, write $4203=data byte, read $4216 and $4217).
I'm curious as to what sort of ratio is possible for 2bpp graphics (NES, Game Boy, Super NES BG3), where each 4x4 pixel quadrant fits into 4 bytes and you need 2 bytes to address a quadrant in the dictionary. This would end up inflating each unique quadrant by 50 percent. So I'm further curious as to how many quadrants other than the all-blank tile are actually repeated often. Because if few are, it'd be cheaper to just encode which quadrants are blank in a header byte, which I'll call "null UFTC":
Code: Select all
76543210
|||||||+- 0: top left is all 0's; 1: contains nonzero pixels
||||||+-- 0: top right is all 0's; 1: contains nonzero pixels
|||||+--- 0: bottom left is all 0's; 1: contains nonzero pixels
||||+---- 0: bottom right is all 0's; 1: contains nonzero pixels
++++----- Compression type for this tile, where one value indicates null UFTC
Code: Select all
76543210
||||||++- 0: top half transparent; 1: left halves; 2: right halves; 3: literal bytes
||||++--- 0: bottom half transparent; 1: left halves; 2: right halves; 3: literal bytes
++++----- Compression type for this tile, where one value indicates null UFTC
Another option is to encode left-half and right-half quadrants as two separate dictionaries that overlap in memory, so that the quadrants can be combined by ANDing without shifting. This might work as well for 4bpp planar tiles on Super NES and TG16 as UFTC works on the Genesis and GBA. How much does it cost in compression ratio to never reuse quadrants from one side to the other?
I could answer all these questions myself by testing these hypotheses against a tile corpus. What corpus is commonly used to evaluate 2bpp and 4bpp tile codecs, if any?