nx_zstd_bits.nx

nx_zstd_bits.nx -- Zstandard's BACKWARD bitstream reader + Huffman weights. The piece between nx_zstd_fse.nx (entropy tables) and a working literals section. Both zstd's Huffman streams and its FSE streams are read BACKWARDS from the end of the buffer, which is unlike every other format in this tree -- DEFLATE, VP8L, FLAC, VP8 and AV1 all read forward. THE STREAM ENDS WITH A MARKER BIT, NOT A LENGTH. The final byte's highest SET bit is a sentinel: it and everything above it is padding, and the real data ends immediately below it. So initialisation must find that bit and start there. A reader that begins at the top of the last byte consumes padding as data and every symbol after it is wrong; a reader that assumes a fixed padding width works only when the payload happens to end byte-aligned. A final byte of ZERO has no marker at all and is corrupt by definition -- it is REFUSED here rather than treated as eight padding bits. BITS ARE PACKED LSB-FIRST WITHIN A BYTE, AND READ HIGH-TO-LOW OVERALL. Those two facts together are the whole trick: absolute bit k lives at data[k >> 3] bit (k & 7) counting from the LSB, and reading walks k DOWNWARD with the first bit taken becoming the MOST significant of the result. THE LAST HUFFMAN WEIGHT IS NOT STORED. Weights encode 2^(w-1) each, and the total must reach the next power of two exactly; the final symbol's weight is whatever completes it. A decoder that reads only the stored weights builds a table missing its last symbol, which decodes most literals correctly and then produces one wrong byte wherever that symbol appears. genealogy_id: zstandard_rfc8878_bitstream lineage_id: nx_zstd_bits_v1 license_tier: ORIGINAL