Open source Kraken/Mermaid/Selkie/LZNA/BitKnit decompression

[powzix]

Here's my open source Kraken / Mermaid / Selkie / LZNA / Bitknit decompressor:

http://www89.zippyshare.com/v/w9ng4xIg/file.html

http://s000.tinyupload.com/?file_id=...41619321065487

http://www.filehosting.org/file/deta...ompressors.zip

http://www.megafileupload.com/k2eg/o...ompressors.zip

https://www.datafilehost.com/d/I8W2VVXZYu

http://oceanhost.eu/j25gcho79d0u/ood...essors.zip.htm


(Only for Windows and is not safe for invalid input)

[Sportman]

0.08 sec. 121.90 MB/s dickens
0.28 sec. 183.14 MB/s mozilla
0.08 sec. 121.44 MB/s mr
0.08 sec. 439.43 MB/s nci
0.06 sec. 110.52 MB/s ooffice
0.06 sec. 176.43 MB/s osdb
0.04 sec. 164.67 MB/s reymont
0.09 sec. 230.04 MB/s samba
0.06 sec. 131.85 MB/s sao
0.30 sec. 137.73 MB/s webster
0.12 sec. 69.01 MB/s x-ray
0.02 sec. 353.22 MB/s xml

[Shelwien]

1. Seems compatible with dll 2.20 only, files created with 2.13 and 2.30 produce "size error"
2. Writes 4-byte filesize at start of the stream, while oodle_api writes 8 bytes; either remove bytes 4-7 or modify lzenc.cpp
3. Had to modify the source to make it compatible with IntelC/older VS

[powzix]

1. Seems compatible with dll 2.20 only, files created with 2.13 and 2.30 produce "size error"
2. Writes 4-byte filesize at start of the stream, while oodle_api writes 8 bytes; either remove bytes 4-7 or modify lzenc.cpp
3. Had to modify the source to make it compatible with IntelC/older VS

I added a pre-built unkraken.exe to the github repo. I get the following performance with it:
dickens.kraken : 2906822 => 10192446 (0.05 seconds, 199.19 MB/s)
mozilla.kraken : 14236921 => 51220480 (0.15 seconds, 334.50 MB/s)
mr.kraken : 2910974 => 9970564 (0.04 seconds, 261.88 MB/s)
nci.kraken : 1894091 => 33553445 (0.04 seconds, 857.14 MB/s)
ooffice.kraken : 2559090 => 6152192 (0.02 seconds, 258.22 MB/s)
osdb.kraken : 3080743 => 10085684 (0.03 seconds, 351.99 MB/s)
reymont.kraken : 1385574 => 6627202 (0.02 seconds, 367.62 MB/s)
samba.kraken : 4001067 => 21606400 (0.05 seconds, 430.64 MB/s)
sao.kraken : 4666289 => 7251944 (0.03 seconds, 285.11 MB/s)
webster.kraken : 8748984 => 41458703 (0.14 seconds, 295.86 MB/s)
xml.kraken : 484282 => 5345280 (0.01 seconds, 783.98 MB/s)
x-ray.kraken : 4842659 => 8474240 (0.05 seconds, 163.43 MB/s)

Note that threaded decoding is not implemented and it doesn't do as much bounds checking as regular kraken.

[powzix]

I added support for Kraken 2.30 files to the github repo.

[powzix]

Performance with latest version built in x64 mode:

dickens.kraken : 2901312 => 10192446 (0.03 seconds, 328.03 MB/s)
mozilla.kraken : 14199727 => 51220480 (0.11 seconds, 458.47 MB/s)
mr.kraken : 2923528 => 9970564 (0.03 seconds, 359.33 MB/s)
nci.kraken : 1764475 => 33553445 (0.04 seconds, 855.54 MB/s)
ooffice.kraken : 2561349 => 6152192 (0.02 seconds, 324.22 MB/s)
osdb.kraken : 3007629 => 10085684 (0.02 seconds, 429.78 MB/s)
reymont.kraken : 1387086 => 6627202 (0.01 seconds, 461.50 MB/s)
samba.kraken : 3994454 => 21606400 (0.04 seconds, 606.30 MB/s)
sao.kraken : 4677118 => 7251944 (0.02 seconds, 357.47 MB/s)
webster.kraken : 8658979 => 41458703 (0.13 seconds, 328.90 MB/s)
xml.kraken : 474924 => 5345280 (0.01 seconds, 875.90 MB/s)
x-ray.kraken : 4887079 => 8474240 (0.04 seconds, 207.59 MB/s)

[JamesB]

How do those numbers compare with zstd, brotli, etc on your same machine? I'm also wondering how they compare to the real Kraken implementation. It seems pretty fast for some data sets, but they're all so small it's hard to get a judge on the reliability of that timing. I tried webster with zstd on a local machine (3.2GHz i5) with ZStd and it got around 440MB/s.

I'm curious how you did this too. Was it simply feeding data in and investigating how the output format changes, or actual reverse engineering of the dll? The latter may have implications to the usability of your code in some countries. Regardless knowing the techniques used means the opensource community can use similar techniques in their own tools, avoiding actual code implementations. Eg the idea of having a quantum of 2 blocks using shared history buffers is presumably a method for interleaving two decoders together and thus making memory fetch delays less severe.

[fgiesen]

It's clearly reverse engineered from Oodle 2.2.0 32-bit x86, most likely the Windows DLL. Let's just say I recognize a lot of the code fragments, and they replicate a bunch of random implementation details exactly, in one case appearing to mention instruction selection choices made by VC++ that are different from what GCC does for the same source on Linux.

[powzix]

It's clearly reverse engineered from Oodle 2.2.0 32-bit x86, most likely the Windows DLL. Let's just say I recognize a lot of the code fragments, and they replicate a bunch of random implementation details exactly, in one case appearing to mention instruction selection choices made by VC++ that are different from what GCC does for the same source on Linux.

Yes you are right that I analyzed the Oodle 2.2.0 DLL. I have not looked at GCC output on Linux, but if you're referring to the two CMOVs I spent some time getting VC++ to actually use a CMOV.

[powzix]

The decompressor is on the below link. It uses the same code base as the kraken decompressor because a lot of the code is shared.

http://github.com/powzix/kraken

Also not fuzz safe and might crash on invalid input (unlike the real Selkie / Mermaid decompressor).

[SolidComp]

Here's my open source kraken / mermaid / selkie decompressor:

http://github.com/powzix/kraken

(Only for Windows and is not safe for invalid input)

I've been confused by the third-party benchmarks, and now codecs – I thought these were secret, proprietary codecs. Did RAD release the specs for K/M/S? Where is it? Did they release source code for decompression too?

[Shelwien]

No, somebody else just made a good decompiler.

As to benchmarks, there're now PC games using oodle.

[powzix]

I added LZNA support too.

[powzix]

Added Bitknit support too!

[algorithm]

powzix your work is awesome!

[Jarek]

I see BitKnit adapts probabilities for rANS every 1024 symbols, but there is some strange weight choice.
E.g. for literals it uses weight 31 for symbols in the stream ... but then weight 725 for the last symbol - I understand it is to simulate exponential forgetting, but still it could be a bit smoother, e.g. using a table like weight[(model->adapt_interval) >> 3].

LZNA has very nice symbol-by-symbol rANS adaptation for 8 (3 bit) or 16 (4 bit) size alphabet - with beautiful SIMD for both searching of the symbol and adapting probabilities using CDF only.
This is exactly what they need in VP10/AV1 (alphabet is limited by 16) ...

[powzix]

LZNA has very nice symbol-by-symbol rANS adaptation for 8 (3 bit) or 16 (4 bit) size alphabet - with beautiful SIMD for both searching of the symbol and adapting probabilities using CDF only.

Yes I agree, it's amazingly beautiful. Very good job by fgiesen or cbloom or whoever it was that came up with it..

BitKnit looks terrible in comparison. Also BitKnit's recent match distance table is weird, it doesn't really keep track of the 8 most recent distances, but only the 2 most recent, and then 6 more... Maybe it remembers only the ones that are actually referenced again at least once. I didn't quite figure out how it works in detail.

[JamesB]

LZNA has very nice symbol-by-symbol rANS adaptation for 8 (3 bit) or 16 (4 bit) size alphabet - with beautiful SIMD for both searching of the symbol and adapting probabilities using CDF only.
This is exactly what they need in VP10/AV1 (alphabet is limited by 16) ...

The toggling between two states is intriguing. I'm assuming this is an alternative method to get interleaving as flip-flopping between two rans states the throughput vs latency differences in cpu instructions can be avoided. That's if I understand the intention correctly. It makes more sense than my approach of having multiple states with multiple start coordinates in the buffer. That does the same job, but doesn't lend itself well to adapting the probabiltiies.

The proper renormalisation rather than using static lookup tables makes it easier to exploit SIMD too. I tried with SIMD but it's largely crippled due to the matrix lookups needing slow and expensive gather operations. However it's only viable with small alphabet sizes (hence lznib I guess). A nice algorithm design.

[Shelwien]

Maybe fgiesen.wordpress.com/2016/03/07/repeated-match-offsets-in-bitknit/ ?
Anyway, they optimize codecs for compression of game resources, so results can be a bit weird.

[fgiesen]

I see BitKnit adapts probabilities for rANS every 1024 symbols, but there is some strange weight choice.

That's just an oversight, not an intentional feature of the model. Quoting the actual code:

        kIncrement = kAvailable / kRenormEvery,
        kFinalBoost = kAvailable % kRenormEvery,

It's just trying to redistribute kAvailable slots of the probability space between renormalization intervals. To be honest I didn't notice how huge the final boost was relative to the normal increments until months after the bitstream had been frozen!

A much more uniform way is to just boost the last "kFinalBoost" symbols before a renormalization takes place by a single increment:

  symfreq[sym] += kIncrement + (renorm_counter >= kFinalBoost ? 1 : 0);
  if (--renorm_counter == 0) renorm();

Alas, not the kind of change you make post-bitstream-freeze.

LZNA has very nice symbol-by-symbol rANS adaptation for 8 (3 bit) or 16 (4 bit) size alphabet - with beautiful SIMD for both searching of the symbol and adapting probabilities using CDF only.
This is exactly what they need in VP10/AV1 (alphabet is limited by 16) ...

This is why I've been insisting that this approach is really quite SIMD-friendly and you might wanna have a look at that for more than a year.

[fgiesen]

BitKnit looks terrible in comparison. Also BitKnit's recent match distance table is weird, it doesn't really keep track of the 8 most recent distances, but only the 2 most recent, and then 6 more... Maybe it remembers only the ones that are actually referenced again at least once. I didn't quite figure out how it works in detail.

I talked about it in depth here: https://fgiesen.wordpress.com/2016/0...ts-in-bitknit/

New distances are inserted into the second-to-last slot and only get "promoted" to one of the first 6 if they occur as a repeat offset. BitKnit was designed for a very specific application (mesh and animation data in RAD Granny), not for Oodle. That data is full of structs and the repeats are extremely frequent. Hence the 8 repeat offsets. Inserting the new distances further down is to avoid contaminating the distance set with transient match offsets that only get used once. The match distance coder is intentionally dumb and cheap, optimized for speed more than compression ratio. Was a better trade-off for the data types and decoding speeds it's targeting.

BitKnit has a few other wrinkles that stem from its origins as special-purpose compressor for one type of file. It turned out to be unexpectedly (and unintendedly!) good for general-purpose compression as well, and it was at a point on the space-speed trade-off curve that nothing else shipping in Oodle at the time was close to, which is how it ended up in there. Post-Kraken, it's back to its original intended role: high compression ratios for specific struct-heavy data (and substantially faster than LZMA/LZNA in that application), OK but not great for anything else.

[fgiesen]

The toggling between two states is intriguing. I'm assuming this is an alternative method to get interleaving as flip-flopping between two rans states the throughput vs latency differences in cpu instructions can be avoided.

That is yet another topic I've written about publicly before: https://fgiesen.wordpress.com/2015/1...s-in-practice/

Covers lots of implementation details for the LZNA and BitKnit rANS coders, including rationale. Published last year, something like 4 months after BitKnit was first released (in Granny), and just after it got included in Oodle.

I have to admit that this whole thing is starting to seriously get on my nerves. Charles and me really do write a lot about this stuff, and usually within months of the release of our implementations; sometimes even before the stuff we're talking about is released. It's not exactly encouraging that detailed write-ups like that will get ignored (with some accusations of "you're keeping everything to yourself and giving nothing back to the community!" on the side), but as soon as someone has reverse-engineered the code it's suddenly interesting. I don't think we need to apologize for actually trying to make back the development costs of software that we've spent several full-time months on before we spill the beans on everything completely. Come on!

[powzix]

Fgiesen, in kraken 2.2, you decode 3 huffman streams simultaneously (and in 2.3 it's 6..).

Two going forwards and one going backwards from the end:
|--> ......................|-->.............................<--|

Is there a reason why you chose not to go backwards also from the middle position?

[fgiesen]

The reverse streams need an extra byte swap on LE platforms, and we care more about LE than BE right now.The original idea with the reverse streams was that forward/reverse pairs provide safety padding for each other, and each cursor can act as "end pointer" for the other. The second turned out to be really useful, the first, not as much as expected.

[Jarek]

To be honest I didn't notice how huge the final boost was relative to the normal increments until months after the bitstream had been frozen!

From the perspective of compressors for games, freezing bitstream doesn't seem to be an issue (?) - you don't need forward or backward compatibility, just within a given game?

A much more uniform way is to just boost the last "kFinalBoost" symbols before a renormalization takes place by a single increment(...)

The problem of optimal probability adaptation is a tough one, I've tried to find something better like trend-seeking predicting e.g. linear trend of evolution, but it was more complex and not really better - the exponential forgetting seems just the best way.
Increasing by one until some kFinalBoost is reasonable, but you could getter better behavior at similar cost by just tabling the weighs, e.g. weight[(model->adapt_interval) >> 3].

This is why I've been insisting that this approach is really quite SIMD-friendly and you might wanna have a look at that for more than a year.

So personally I am alone at my University with information theory, I have really tried to find a scientific collaboration on a related topics, but it seems hopeless here. Sure I could spend a year to write a great compressor and make it open source ... but so what? I am evaluated by the number of papers and teaching. Nobody is interested in ANS here, I didn't get a dime from it.

A few months ago I had many discussions with VP10 and Daala team, e.g. here: http://lists.xiph.org/pipermail/daal...il/thread.html
I haven't followed it later, but originally Daala was advocating their implementation of Moffat's approximation of range coding:
https://people.xiph.org/~tterribe/tm...c%20Coding.pdf
there is no multiplication, but the inaccuracy means 1-3% ratio loss.
They emphasize advantage as working on non-power-of-two-denominator (impractical for rANS), because they use adaptation of type: Pr(s) ~ #s / total.
But this adaptation has poor forgetting (far symbols have the same impact as close ones) - tests show that exponential forgetting is essentially better ... and use power-of-two-denominator as you describe.
As their alphabets are limited to 16 (for each of hundreds of contexts), indeed I was advocating exactly what you have in LZNA: using SIMD for both search and symbol update (but I haven't found motivation to learn programming with SIMD).
Currently both rANS and Daala entropy coders are being developed for AV1: https://aomedia.googlesource.com/aom/+/master/aom_dsp/
It would be great if RAD Game Tools would joint the AOM ...

[fgiesen]

From the perspective of compressors for games, freezing bitstream doesn't seem to be an issue (?) - you don't need forward or backward compatibility, just within a given game?

Backwards compatibility is non-negotiable. Otherwise every single format change would create what is effectively a new fork of the project that needs to be maintained for, at the very least, several years. So if we were to say at some point discover a buffer overrun that's been in the code base for a year, we would now need to issue separate patches for every format variant we've supported in that time, and we'd have a lot of support issues with customers accidentally getting the wrong version etc.

The case for forwards compatibility is things like DLC (downloadable content) - new content for an existing game that's released several months after the original game came out. If we can get encoder improvements without changing the format, that's good. Any breaking changes are really bad, and anything that is exclusive (you can either use the old library version _or_ the new one) is a show-stopper if the new library version also happens to add something that the DLC parts depend on.

Currently both rANS and Daala entropy coders are being developed for AV1: https://aomedia.googlesource.com/aom/+/master/aom_dsp/
It would be great if RAD Game Tools would joint the AOM ...

We're not a big enough company to be able to work on that kind of project "on the side"! We have a total of 9 devs working on currently 8 different products.

[Kennon Conrad]

We're not a big enough company to be able to work on that kind of project "on the side"! We have a total of 9 devs working on currently 8 different products.

Sometimes the world is much smaller than it seems. I looked up Rad Game Tools and found it's only five miles from my house.

[Zyzzyva]

fgiesen and cbloom, I am wondering if you've considered other options for opening up these compression formats, given the high level of interest in the formats and the benefit to the community in making them more open? I feel that if your work remains locked up, it will not gain the level of appreciation and recognition that it deserves.

One idea is to release the code as GPL but also sell commercial licenses. Then it could be used in GPL-ed open source projects, but commercial games would still have to pay RAD for a commercial license.

Another idea is to release a format specification, but no code. Then people could, over time, write their own compressors and decompressors. The idea is that this would indirectly protect RAD's particular implementation, since then it wouldn't be as worthwhile for anyone to bother reverse engineering it.

Actions like these might actually *increase* revenue for RAD by virtue of generating more free advertising for their work. RAD should retain an advantage anyway: I understand that their offering includes excellent compressors *and* decompressors, is professionally tested, is professionally supported, has been optimized and tested for gaming platforms, comes with the rest of Oodle, and presumably is easy to license together with other RAD products that games developers may want.

Anyway, I'm just throwing some ideas out there for ways everyone might come out ahead. I'm not really interested in getting into arguments about any specific idea.

[JamesB]

That is yet another topic I've written about publicly before: https://fgiesen.wordpress.com/2015/1...s-in-practice/

Covers lots of implementation details for the LZNA and BitKnit rANS coders, including rationale. Published last year, something like 4 months after BitKnit was first released (in Granny), and just after it got included in Oodle.

I have to admit that this whole thing is starting to seriously get on my nerves. Charles and me really do write a lot about this stuff, and usually within months of the release of our implementations; sometimes even before the stuff we're talking about is released. It's not exactly encouraging that detailed write-ups like that will get ignored (with some accusations of "you're keeping everything to yourself and giving nothing back to the community!" on the side), but as soon as someone has reverse-engineered the code it's suddenly interesting. I don't think we need to apologize for actually trying to make back the development costs of software that we've spent several full-time months on before we spill the beans on everything completely. Come on!

I did read that article, but managed to forget it apparently! One day I'll get around to exploring adaptive rANS and I'm certain your blog posts will come in handy for that, but like many others I spend most of my days doing other work so it's hard to fit it all in.

So I for one though are really happy to see your posts. They're definitely informative and I think you and Charles have been surprisingly open given you're a commercial outfit. Keep up the great work!

[m^3]

The situation reminds me of Chris Martelock.
Hope it ends differently.