nx_huffman.nx

nx_huffman.nx -- canonical Huffman decoder. Composes against nx_bitstream. Used by: - DEFLATE (RFC 1951) -- literal/length + distance trees - JPEG -- DHT segments (DC + AC coefficient tables) - MP3 / AAC / Vorbis / Opus -- spectral coefficient codes - brotli -- many sub-tables - FLAC -- Rice partitions (not strictly Huffman; close family) Canonical Huffman is the convention where: - codes are assigned ONLY by their length sequence - shortest codes first; within a length, in symbol order - given just an array of (length per symbol), the decoder can reconstruct the tree Build algorithm (RFC 1951 section 3.2.2): 1. count[L] = number of symbols with length L 2. first_code[L] = (first_code[L-1] + count[L-1]) << 1 3. sort symbols by (length, symbol index) -> symbol_table 4. first_symbol[L] = cumulative count of lengths < L Decode algorithm: - read bits MSB-first into accumulator - for L = 1..max_length: if accumulator < first_code[L] + count[L]: idx = accumulator - first_code[L] return symbol_table[first_symbol[L] + idx] else: shift accumulator left by 1, read next bit, OR in - return -1 (invalid bitstream) genealogy_id: rfc1951_canonical_huffman_1996 lineage_id: nx_huffman_v1