LZ bench for ZSTD

[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]

No, I have not used lzbench. If you tell me which numbers you are referring to, I can tell you how they are made.

[vishnucheerakoda]

Yes correct. I was thinking of the window size.
One question is , let's say i have a data to be compressed, and i got same sequence or same symbols(LL,ML,OFF codes) , so we have to use RLE mode for sure, so how the sequence encoded stream looks like ? do we have to only represent extra bits in the stream ? in what order ?

[klauspost]

The RLE only applies to the actual code, not to the bits.

So if all literal lengths are between length 40 and 47, then llCode = 23 (giving RLE), but for each you will have to read 3 bits.

For match offset that can be avoided with repeat codes, but for ll and ml you cannot "compact" similar remaining bits.

[vishnucheerakoda]

Yes I agree for Offset codes can be avoided with repeat codes, but my doubt is : let's say I have only 1 sequence to encode eg : (LL,ML,OFF) is (45,61,1)
LL code = 'd23 with 3 extra bits (101)
ML code = 'd39 with 3 extra bits (010)
OFF Code = 'd2 with 2 extra bits (00)

so the seq section would be like
0x01(no of seq) + 'h54(01010100)(comp mode) + 'h17(LL code) + 'h02(OFF code) + 'h25(ML code) +101-00-010 , is that correct ?
so the extra bits to read from the stream would follow LL,OFF,ML always ??

[klauspost]

That seems correct and valid to me.

Of course in this particular case using a predefined table will be smaller, since all symbols are less than 8 bits. For longer RLE runs that is not always the case.

[vishnucheerakoda]

Thanks for the Quick response. Let me modify and try this !!

[vishnucheerakoda]

Hi, I have done the modification to pass single sequence condition, but soft decompressor is failing. Here is the hexdump of the compressed file

0000000: 28b5 2ffd 2012 2d01 0060 6162 6364 6566 (./. .-..`abcdef
0000010: 6768 696a 6b0a 0154 0b03 0306 ghijk..T....

actual text is abcdefghijkabcdef

Could you please try this hexdump to decompress ?

[klauspost]

@vishnucheerakoda Please gzip the file and attach it here.

[vishnucheerakoda]

single_seq_file.txt.gz

[vishnucheerakoda]

Stream_0_ActDataFile_0.zst.gz is the compressed file.
Stream_0_ActDataFile_0.zst.gz
single_seq_raw_input.txt.gz is the raw input file
single_seq_raw_input.txt.gz

[klauspost]

=== RUN   Test_seqdec_decode_regression/Stream_0_ActDataFile_0.zst
2023/05/19 16:32:18 current already flushed
2023/05/19 16:32:18 Not skippable 28b52ffd 2a4d18
2023/05/19 16:32:18 Read FCS: 18
2023/05/19 16:32:18 Frame: Dict: 0 FrameContentSize: 18 singleseg: true window: 1024 crc: false
2023/05/19 16:32:18 decoding new block
2023/05/19 16:32:18 Data size on stream: 37
2023/05/19 16:32:18 Reading block: unexpected EOF ( 37 ) 19
2023/05/19 16:32:18 *zstd.readerWrapper
2023/05/19 16:32:18 block error: unexpected EOF
2023/05/19 16:32:18 re-adding current decoder 0xc00010a0f0

Seems like the block is truncated.

[vishnucheerakoda]

Hi, There was an issue in the block size calculation for this case, now i am able to decode the compressed file, but some how the distance is wrong , the sequence has to be (LL,ML,OFF) = (11,6,11), but it looks like (11,6,9). when we see the sequence section
0154 0b03 0306 (lsb-msb)
01 - seq number
54 - RLE mode
0b- LL code(no extra bits)
03- OFF code(3 extra bits)
03- ML code(no extra bits)
06- 3'b110 is the extra bits for offset , so ((1<<3) + 6 - 3 = 11.

Could you please check at your end if possible ?
I think uncompressed literals would be decoded without any issue,
When it comes to sequence section, I would like to know how it is being proceeded. is it picking same as i mentioned at top ?

Stream_0_ActDataFile_0.zst.gz

[klauspost]

2023/05/22 11:58:24 literals type: literalsBlockRaw litRegenSize: 12 litCompSize: 0 sizeFormat: 0 4X: false
2023/05/22 11:58:24 prepareSequences: 6 byte(s) input
2023/05/22 11:58:24 Compression modes: 0b1010100
2023/05/22 11:58:24 Table tableLiteralLengths is compModeRLE
2023/05/22 11:58:24 RLE set to 47244640256, code: 11
2023/05/22 11:58:24 Table tableOffsets is compModeRLE
2023/05/22 11:58:24 RLE set to 21474837248, code: 3
2023/05/22 11:58:24 Table tableMatchLengths is compModeRLE
2023/05/22 11:58:24 RLE set to 25769803776, code: 3
2023/05/22 11:58:24 Literals: 12 hash: 421587422911080547 and 1 sequences.
2023/05/22 11:58:24 decodeSync: decoding 1 sequences 2 bits remain on stream
2023/05/22 11:58:24 Seq 0 Litlen: 11 mo: 9 (abs) ml: 6
2023/05/22 11:58:24 Decompressed to total 0 bytes, hash: 17241709254077376921 error: unexpected EOF

There is only 2 bits on the stream, so trying to read 3 gives "unexpected EOF".

My guess is you are missing the final bit to signify that decoding starts there.

[klauspost]

From https://github.com/facebook/zstd/blob/dev/doc/zstd_compression_format.md#decoding-sequences

To find the start of the bitstream it is therefore necessary to know the offset of the last byte of the block which can be found by counting Block_Size bytes after the block header.

After writing the last bit containing information, the compressor writes a single 1-bit and then fills the byte with 0-7 0 bits of padding. The last byte of the compressed bitstream cannot be 0 for that reason.

When decompressing, the last byte containing the padding is the first byte to read. The decompressor needs to skip 0-7 initial 0-bits and the first 1-bit it occurs. Afterwards, the useful part of the bitstream begins.

[vishnucheerakoda]

I have implemented this for normal sequence encoding(FSE) , here i thought that it is from lsb to msb , but it wasn't the case. .as you mentioned this is also has to be read backward. I modified that, now it started working.