Simple index compression surprisingly effective

[cero]

For an upcoming game, I tried some different compression approaches for sprite tiles, since lz4w was too slow. The amount of data being great enough that even plain memcpy is close to limits, I wondered what approaches would then be fast, even if not as good in compression. About 160 tiles per frame is the goal.

Simple indexing turned out extremely effective: compression ratios almost as good as lz4w, decompressing 40% faster and in constant time. I tried a couple unit sizes, but 4 bytes was the best for my spritesheets. The project does not use the sprite engine; sprites are manually packed using my metatile tool.

Format:
Divide the spritesheet tiles into 4 byte units. Make a list of unique u32 units. Replace each instance with the u16 index to it.

[Stef]

Wow, if LZ4W is too slow for you then you're looking for something really really fast ! On my tests LZ4W was about 9KB/frame at min up to 14-15KB/frame. That represent about 280 up to 450 tiles / frame but you obviously need some extra free CPU time for other tasks so realistically you can spent about 50% of CPU in decompression which give here between 140 to 220 tiles/frame.
I don't understand how you can get good compression ratio with simple indexing ? Are you using kind of sliver dictionary (8 pixels) indexed on 2 words ?
To be honest i would be really interested by something faster than LZ4W

Edit:
Ok just discovered you gave the format, so that is what i was thinking about but at the end you need to store both the slivers (8 pixels block) and the data compressed using indexes. You probably obtain a fast decompression but the compression ratio itself cannot be any better than 50% at max and should be in almost case as big (if not bigger) than uncompressed data... maybe i'm missing something ?? In some aspects it make me think of Sik's UFTC format (which use kind of dictionary as well)

[Sik]

Yeah, and UFTC is not great either (often being around 75% of the original size, though in some cases with large enough spritesheets it does have a tendency to compress somewhat better, e.g. in something I'm working with a large amount of large sprites per character it's shaving off about 1/3 of memory usage, which is not insignificant at that scale).

UFTC normally uses 4×4 pixel blocks. I tried using 8×2 blocks at some point since it'd be faster to decompress, but turned out to give significantly worse compression ratios. I think the issue is that while UFTC is so unsmart that it probably doesn't help remove much redundancy on opaque parts, most of the compression likely comes from blank areas in sprites (since sprites are rarely box-ish). With 4×4 blocks you're more likely to fit the sprite's silhouette better than with 8×2 blocks.

One thing UFTC can do that the compression tool doesn't take advantage of is being able to point in the middle of two 4×4 blocks. This probably can give some more redundancy that can give a bit more of compression (even if just because a computer will notice redundancy in the least expected places). I should try looking into that some day >_>

[cero]

Yeah, the sprites are big and have a lot of frames, but still it was surprising how well they packed with this. One sheet got to 58% (includes both the index and the stream), while zlib got it to 30% and lz4w 51% (numbers from memory).

[cero]

Data from some other spritesheets. Worst of these was 91% and average 79%.

Packed with IDX, original size = 40512 compressed to 35904 (88.6256 %)
Packed with IDX, original size = 56608 compressed to 48912 (86.4047 %)
Packed with IDX, original size = 57728 compressed to 43492 (75.3395 %)
Packed with IDX, original size = 8352 compressed to 6892 (82.5192 %)
Packed with IDX, original size = 38880 compressed to 33456 (86.0494 %)
Packed with IDX, original size = 51456 compressed to 41764 (81.1645 %)
Packed with IDX, original size = 20064 compressed to 15348 (76.4952 %)
Packed with IDX, original size = 39328 compressed to 29304 (74.5118 %)
Packed with IDX, original size = 52608 compressed to 40520 (77.0225 %)
Packed with IDX, original size = 45728 compressed to 38056 (83.2225 %)
Packed with IDX, original size = 37984 compressed to 32812 (86.3837 %)
Packed with IDX, original size = 78240 compressed to 59032 (75.4499 %)
Packed with IDX, original size = 33376 compressed to 25664 (76.8936 %)
Packed with IDX, original size = 21536 compressed to 15304 (71.0624 %)
Packed with IDX, original size = 15360 compressed to 14108 (91.849 %)
Packed with IDX, original size = 12832 compressed to 11140 (86.8142 %)
Packed with IDX, original size = 22016 compressed to 19576 (88.9172 %)
Packed with IDX, original size = 12448 compressed to 10664 (85.6684 %)
Packed with IDX, original size = 36384 compressed to 25912 (71.2181 %)
Packed with IDX, original size = 36384 compressed to 28952 (79.5734 %)
Packed with IDX, original size = 69600 compressed to 57132 (82.0862 %)
Packed with IDX, original size = 108992 compressed to 81032 (74.3467 %)
Packed with IDX, original size = 204928 compressed to 143264 (69.9094 %)
Packed with IDX, original size = 20992 compressed to 18020 (85.8422 %)
Packed with IDX, original size = 66912 compressed to 51708 (77.2776 %)
Packed with IDX, original size = 49440 compressed to 37292 (75.4288 %)
Packed with IDX, original size = 122528 compressed to 86628 (70.7006 %)
Packed with IDX, original size = 39552 compressed to 34464 (87.1359 %)
Packed with IDX, original size = 59552 compressed to 41848 (70.2714 %)
Packed with IDX, original size = 30720 compressed to 25392 (82.6562 %)
Packed with IDX, original size = 97664 compressed to 69736 (71.404 %)
Packed with IDX, original size = 166272 compressed to 117072 (70.4099 %)

[Stef]

Ok, these ratios are close to what Sik's UFTC tend to do (even worse i think) and worse than LZ4W too, but there is always a trade-off to choose between speed and compression ratio