From 35ad602c26eefb3bc1a68e33ac019578ba6fee98 Mon Sep 17 00:00:00 2001 From: Johannes Rudolph Date: Wed, 14 Sep 2016 19:14:49 +0200 Subject: [PATCH] spec: clarify how bitstream exactly needs to be reversed for reading --- zstd_compression_format.md | 26 +++++++++++++++++--------- 1 file changed, 17 insertions(+), 9 deletions(-) diff --git a/zstd_compression_format.md b/zstd_compression_format.md index f350cdabe..025439f38 100644 --- a/zstd_compression_format.md +++ b/zstd_compression_format.md @@ -1049,15 +1049,23 @@ by reading the required `Number_of_Bits`, and adding the specified `Baseline`. #### Bitstream -All sequences are stored in a single bitstream, read _backward_. -It is therefore necessary to know the bitstream size, -which is deducted from compressed block size. - -The last useful bit of the stream is followed by an end-bit-flag. -Highest bit of last byte is this flag. -It does not belong to the useful part of the bitstream. -Therefore, last byte has 0-7 useful bits. -Note that it also means that last byte cannot be `0`. +FSE bitstreams are read in reverse direction than written. In zstd, +the compressor writes bits forward into a block and the decompressor +must read the bitstream _backwards_. + +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. ##### Starting states -- 2.47.2