Third Party Compression compatibility

[vishnucheerakoda]

Hi all,
I am working on ZSTD Compression/Decompression algorithms. I have used Facebook Decompressor as well as their Educational decoder to validate RTL compression algorithm. Found few issues ,those are stated below.

#1 My RTL compressed data is not getting decompressed with latest Facebook ZSTD Decompressor, where as their
Educational decoder is able to do it.
Note: Production is able to decode it but the data is wrong.(something is going wrong when it is a 4 stream encoded,
sequences are found okay)

#2 Educational decoder fails for few blocks of webster and samba due to a corner case:
The case is all the 256 literals are having same weight(let's say 1)
So the Huffman codes would be like 0x1000
It is not able to find the end since there is no overflow on the stream.

Files :
1st_case.txt.zip

[klauspost]

The output produces corruption detected: stream overrun 4.

This indicates that the huff0 stream produces more output than it should.

2023/04/04 09:56:44 Frame: Dict: 0 FrameContentSize: 32768 singleseg: true window: 32768 crc: false
2023/04/04 09:56:44 decoding new block
2023/04/04 09:56:44 Data size on stream: 16294
2023/04/04 09:56:44 History trimmed: 0 decoded already: 0
2023/04/04 09:56:44 literals type: literalsBlockCompressed litRegenSize: 6979 litCompSize: 4473 sizeFormat: 2 4X: true
2023/04/04 09:56:44 huff table input: 4473 CRC: 666845455
2023/04/04 09:56:44 decoding compressed literals: corruption detected: stream overrun 4

Huff0 Stream 0 decodes to at least 1746 bytes.

[vishnucheerakoda]

It won't be independent 128KB . it can slide between blocks till 128KB. hardware compression has lot of limitations to take decisions based on the data , eg : repeat FSE table, use predefined table etc.

[klauspost]

Predefined is actually a bigger deal than I expected. Here is a comparison, using defaults, using 128K window and only predefined tables and using 128K but with dynamic tables on nyc-taxi-data-10M.csv:

Level	Defaults	128K + Predef	128K
1	641,319,332	826,919,668	709,479,324
2	588,976,126	818,387,598	690,662,612
3	517,666,647	753,742,717	650,892,393
4	459,777,201	712,467,733	620,587,433

Gzip reference: 1: 846,471,964 - 5: 767,340,514 - 9: 709,819,738
Zstandard reference: 1: 687,399,637 - 3: 598,514,411 - 9: 517,554,797

[klauspost]

For reference, the hw implementation I tested output 791,xxx,xxx bytes. But it did all entropy coding (huff0+fse) in software.

[vishnucheerakoda]

Hi, I would like to know how did you get the levels of ZSTD compression ? did you use lz bench to get that ? if so, the block size which we mention in the command (lzbench -b128 -v -ezstd file) will restrict the distance <=128KB ?

[klauspost]

@vishnucheerakoda I used my own library for these numbers (it has a switch to force predefined tables). My library only has 4 levels.

Block size was 128K for all. Window size was 128K.

The "Zstandard reference" was using the commandline zstd -1, etc.

[klauspost]

Do you have a sample of the huff0 case? I don't think it is possible.

My encoder will never generate that case since it will reject this as incompressible after doing the histogram.

In fact I cannot encode this, since the table is incompressible as FSE and cannot be stored as raw values.

The first check is maxCount < (len(in)>>7)

This means I will reject trying to compress if no histogram entry is above len(input)/128.

The second check is if the FSE is incompressible and maxSymbolValue > (256 - 128).

Finally, I reject if actual output + table doesn't give a reasonable improvement after compression. This is tweakable, but for zstd it is fixed at wantSize -= wantSize >> 4 for now.

This is to avoid the decompression penalty when improvement is marginal.

[klauspost]

In short, I cannot see how you can generate a valid table for the case you describe since the FSE input is a single value repeated, so if you could provide a sample input I can check that.

[vishnucheerakoda]

Lets say all the literals are having same frequency. so the Huffman code length would be 8 for all the literals(as you say uncompressible, RTL doesn't have that intelligence). so the probability values for a TableLog of 6 would be {0,64}. which indicates symbol 1 is occupying all the states in the fse table. as per spec this is valid. so the huffman code encoded stream would be just 0x1000 . 0001|SOS|000000|even state lit0|000000|odd state lit1| , rest all would be zero. so total stream size would be only 2 bytes. as per educational decoder it will be waiting for overflow , but here it wouldn't happen even if you consume 256 literals.

[klauspost]

which indicates symbol 1 is occupying all the states in the fse table. as per spec this is valid

No. The FSE code explicitly disallow for single value:

Note that there must be two or more symbols with nonzero probability. source

Since all weights have the same value it cannot be represented as FSE.

[vishnucheerakoda]

This makes sense!!! Thank you!!!