This is a functional algorithm for the compression process.
http://5thhorseman.pastebin.com/14cVLejD
There's two things I'm somewhat unclear on, though: how the original format handles repeat sequences spaced more than 127 pixels apart, and palette indexes above the 127th. If those situations never happen, we're good. Otherwise I'll be going back to the drawing board as soon as we find an example in the original data.
The interleaving is next on my list.