In the Go Figure Under the hood for OPL4/O4S there was an "open question":
Now that the MSXdev deadline has passed, I could not leave that one, un-investigated. I immediately thought of a way that could be a low hanging fruit. Could I make compression without sacrificing performance at all? Or at least keep the same requirement, make all tunes from Go Figure below 5000 cycles per frame?
It would be a simple trick and likely not a huge gain, but how big would it be? Turns out, not too big: 21% reduction, 160kB immediate reductions or 240kB if some more effort were put into it. —Still worthwhile when you get it for free, performance-wise.
Furthermore, the approach can be extended to give better results. But then it's not so low-hanging anymore.
The idea and how I did it
The idea is to see if there are any recurring patterns in the data. And if there are, store it once, and reference it. The low-hanging fruit is to look at the regwrites only. This data cater for ~75% of the final size. If you followed the explanantion in O4S - The encoder, the part I target is this
I just calculate a hash for each regpair-chunk for each channel in each frame. And when building the final stream, it is easy to check if a frame's data has occured earlier. If so, I replace any already used chunk with a reference to it using a reuse-jump. The stream will look like this:
Such a reuse-jump needs to hold information about both the segment and the location within the segment, so a reuse-jump costs 4 bytes. This means that only chunks of at least 5 bytes will be assessed.
Results
v1.0 would be the version in Go Figure, and v1.5 is this "compression light". The game uses 16kB segments.
We can see that compression results varies from -12% to -32%, with an average of -21% amongst the game scores, while keeping the cycle amount around the same levels, there is a tiny overhead with the reuse-jumps. A few small modifications was done to the overall algorithm as well, that's why we see that some performance numbers even go down.
If implemented in Go Figure now, we would save 10 16kB segments. Tunes always start at the beginning of a segment, so different tunes never share any segment. If we make sure we use the space after a tune too by starting a tune mid-segment, we would save 15 segments (the "no-gap" above).
Next steps
To improve this further, I foresee a lot more work. However, a very interesting topic!
I'd like to look into implementing a gammar based compression technique similar to what Grauw is already using in his
replayer. I have implemented it before with great results. At that time I used it in a per-tune manner. This time, I imagine working on a full playlist at the time, benefitting from any repeatable pattern across all tunes.
Comments
Post a Comment