nx_huffman.nx source

1// nx_huffman.nx -- canonical Huffman decoder. 2// 3// Composes against nx_bitstream. Used by: 4// - DEFLATE (RFC 1951) -- literal/length + distance trees 5// - JPEG -- DHT segments (DC + AC coefficient tables) 6// - MP3 / AAC / Vorbis / Opus -- spectral coefficient codes 7// - brotli -- many sub-tables 8// - FLAC -- Rice partitions (not strictly Huffman; close family) 9// 10// Canonical Huffman is the convention where: 11// - codes are assigned ONLY by their length sequence 12// - shortest codes first; within a length, in symbol order 13// - given just an array of (length per symbol), the decoder 14// can reconstruct the tree 15// 16// Build algorithm (RFC 1951 section 3.2.2): 17// 1. count[L] = number of symbols with length L 18// 2. first_code[L] = (first_code[L-1] + count[L-1]) << 1 19// 3. sort symbols by (length, symbol index) -> symbol_table 20// 4. first_symbol[L] = cumulative count of lengths < L 21// 22// Decode algorithm: 23// - read bits MSB-first into accumulator 24// - for L = 1..max_length: 25// if accumulator < first_code[L] + count[L]: 26// idx = accumulator - first_code[L] 27// return symbol_table[first_symbol[L] + idx] 28// else: 29// shift accumulator left by 1, read next bit, OR in 30// - return -1 (invalid bitstream) 31// 32// genealogy_id: rfc1951_canonical_huffman_1996 33// lineage_id: nx_huffman_v1 34 35// nx_safety_envelope: 36// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 37// sil_target: SIL1 38// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail] 39// verdict: NOT_YET_EVALUATED 40 41import "nx_syscalls.nx" 42import "nx_runtime.nx" 43import "nx_tier.nx" 44import "nx_bitstream.nx" 45 46// ===== bounds ===================================================== 47 48const NX_HUFF_MAX_SYMBOLS: nx_int = 65536 // covers DEFLATE 288 + JPEG 256 + most use cases 49const NX_HUFF_MAX_LENGTH: nx_int = 32 50 51// ===== table struct ============================================== 52 53struct NxHuffmanTable { 54 n_symbols: nx_int, 55 max_length: nx_int, 56 count: *nx_int, // count[L] for L in [0, max_length] 57 first_code: *nx_int, // first_code[L] 58 first_symbol: *nx_int, // first_symbol[L] (offset into symbol_table) 59 symbol_table: *nx_int, // n_symbols entries sorted by (length, symbol) 60} 61 62const NX_HUFF_TABLE_BYTES: nx_size = 56 63 64// ===== build ====================================================== 65// 66// code_lengths[s] = length of code for symbol s (0 = absent from 67// table). Returns NULL if input invalid. 68 69func nx_huffman_build(code_lengths: *nx_int, n_symbols: nx_int) -> *NxHuffmanTable { 70 if n_symbols <= 0 { return 0 as *NxHuffmanTable } 71 if n_symbols > NX_HUFF_MAX_SYMBOLS { return 0 as *NxHuffmanTable } 72 73 let p: *u8 = sys_mmap(NX_HUFF_TABLE_BYTES) 74 let t: *NxHuffmanTable = p as *NxHuffmanTable 75 t.n_symbols = n_symbols 76 77 // Step 1: count[L] for L in [0, NX_HUFF_MAX_LENGTH]. 78 let count_bytes: nx_size = ((NX_HUFF_MAX_LENGTH + 1) as nx_size) * 8 79 let count: *nx_int = (sys_mmap(count_bytes)) as *nx_int 80 var i: nx_int = 0 81 while i <= NX_HUFF_MAX_LENGTH { 82 count[i] = 0 83 i = i + 1 84 } 85 var s: nx_int = 0 86 var max_len: nx_int = 0 87 while s < n_symbols { 88 let L: nx_int = code_lengths[s] 89 if L > 0 { 90 if L > NX_HUFF_MAX_LENGTH { return 0 as *NxHuffmanTable } 91 count[L] = count[L] + 1 92 if L > max_len { max_len = L } 93 } 94 s = s + 1 95 } 96 t.count = count 97 t.max_length = max_len 98 99 // Step 2: first_code[L]. 100 let first_code_bytes: nx_size = ((NX_HUFF_MAX_LENGTH + 1) as nx_size) * 8 101 let first_code: *nx_int = (sys_mmap(first_code_bytes)) as *nx_int 102 first_code[0] = 0 103 var fc: nx_int = 0 104 var L: nx_int = 1 105 while L <= NX_HUFF_MAX_LENGTH { 106 fc = (fc + count[L - 1]) * 2 107 first_code[L] = fc 108 L = L + 1 109 } 110 t.first_code = first_code 111 112 // Step 3: first_symbol[L] = cumulative count of (length < L). 113 let first_symbol_bytes: nx_size = ((NX_HUFF_MAX_LENGTH + 1) as nx_size) * 8 114 let first_symbol: *nx_int = (sys_mmap(first_symbol_bytes)) as *nx_int 115 first_symbol[0] = 0 116 var fs: nx_int = 0 117 var FL: nx_int = 1 118 while FL <= NX_HUFF_MAX_LENGTH { 119 first_symbol[FL] = fs 120 fs = fs + count[FL] 121 FL = FL + 1 122 } 123 t.first_symbol = first_symbol 124 125 // Step 4: symbol_table sorted by (length, symbol index). 126 let symtab_bytes: nx_size = (n_symbols as nx_size) * 8 127 let symtab: *nx_int = (sys_mmap(symtab_bytes)) as *nx_int 128 129 // running write-offset per length 130 let next_off_bytes: nx_size = ((NX_HUFF_MAX_LENGTH + 1) as nx_size) * 8 131 let next_off: *nx_int = (sys_mmap(next_off_bytes)) as *nx_int 132 var ni: nx_int = 0 133 while ni <= NX_HUFF_MAX_LENGTH { 134 next_off[ni] = first_symbol[ni] 135 ni = ni + 1 136 } 137 var sym: nx_int = 0 138 while sym < n_symbols { 139 let len: nx_int = code_lengths[sym] 140 if len > 0 { 141 let dst_idx: nx_int = next_off[len] 142 symtab[dst_idx] = sym 143 next_off[len] = dst_idx + 1 144 } 145 sym = sym + 1 146 } 147 t.symbol_table = symtab 148 return t 149} 150 151// ===== decode one symbol (MSB-first bit reading) ================== 152// 153// Reads bits one at a time, accumulating into `code`, until `code` 154// fits within an in-range canonical code. Returns the matching 155// symbol, or -1 on bitstream error / invalid code. 156 157func nx_huffman_decode_msb(t: *NxHuffmanTable, bs: *NxBitStream) -> nx_int { 158 var code: nx_int = 0 159 var L: nx_int = 1 160 while L <= t.max_length { 161 let bit: nx_int = nx_bitstream_read_msb(bs, 1) 162 if bs.overflow == 1 { return -1 } 163 code = (code << 1) | bit 164 let fc: nx_int = t.first_code[L] 165 let cnt: nx_int = t.count[L] 166 if code < (fc + cnt) { 167 if code >= fc { 168 let idx: nx_int = code - fc 169 let st_off: nx_int = t.first_symbol[L] 170 return t.symbol_table[st_off + idx] 171 } 172 } 173 L = L + 1 174 } 175 return -1 176} 177 178// ===== decode (LSB-first variant; DEFLATE convention) ============ 179// 180// DEFLATE reads Huffman codes LSB-first BUT the bits within each 181// code are also bit-reversed. The substrate's nx_deflate wrapper 182// pre-reverses; this primitive provides the bit-reversed read 183// helper. 184 185func _huff_reverse_bits(v: nx_int, n: nx_int) -> nx_int { 186 var src: nx_int = v 187 var dst: nx_int = 0 188 var i: nx_int = 0 189 while i < n { 190 let bit: nx_int = src & 1 191 dst = (dst << 1) | bit 192 src = src >> 1 193 i = i + 1 194 } 195 return dst 196} 197 198func nx_huffman_decode_lsb(t: *NxHuffmanTable, bs: *NxBitStream) -> nx_int { 199 var code: nx_int = 0 200 var L: nx_int = 1 201 while L <= t.max_length { 202 let bit: nx_int = nx_bitstream_read_lsb(bs, 1) 203 if bs.overflow == 1 { return -1 } 204 code = (code << 1) | bit 205 let fc: nx_int = t.first_code[L] 206 let cnt: nx_int = t.count[L] 207 if code < (fc + cnt) { 208 if code >= fc { 209 let idx: nx_int = code - fc 210 let st_off: nx_int = t.first_symbol[L] 211 return t.symbol_table[st_off + idx] 212 } 213 } 214 L = L + 1 215 } 216 return -1 217} 218 219// ===== self-test ================================================== 220 221func main() -> nx_int { 222 // Toy table: 4 symbols with code-lengths [2, 1, 3, 3]. 223 // sym 0: length 2 -> code 10 (binary) 224 // sym 1: length 1 -> code 0 225 // sym 2: length 3 -> code 110 226 // sym 3: length 3 -> code 111 227 let lens: *nx_int = (sys_mmap(32)) as *nx_int 228 lens[0] = 2 229 lens[1] = 1 230 lens[2] = 3 231 lens[3] = 3 232 233 let t: *NxHuffmanTable = nx_huffman_build(lens, 4) 234 if t == (0 as *NxHuffmanTable) { return 1 } 235 if t.n_symbols != 4 { return 2 } 236 if t.max_length != 3 { return 3 } 237 238 // Verify count + first_code. 239 if t.count[1] != 1 { return 4 } 240 if t.count[2] != 1 { return 5 } 241 if t.count[3] != 2 { return 6 } 242 if t.first_code[1] != 0 { return 7 } 243 if t.first_code[2] != 2 { return 8 } // (0 + 1) * 2 244 if t.first_code[3] != 6 { return 9 } // (2 + 1) * 2 245 246 // Verify symbol_table sorted by (length, symbol): 247 // pos 0: symbol 1 (length 1) 248 // pos 1: symbol 0 (length 2) 249 // pos 2: symbol 2 (length 3) 250 // pos 3: symbol 3 (length 3) 251 if t.symbol_table[0] != 1 { return 10 } 252 if t.symbol_table[1] != 0 { return 11 } 253 if t.symbol_table[2] != 2 { return 12 } 254 if t.symbol_table[3] != 3 { return 13 } 255 256 // ---- decode MSB-first ---- 257 // 258 // Encode the stream: sym1 sym0 sym2 sym3 sym1 259 // = 0 10 110 111 0 = 0 1011 0111 0 = "0 10 110 111 0" 260 // Concatenated MSB-first: 0101 1011 1101 0... 261 // 262 // Pack into bytes MSB-first: 263 // bit 0 (MSB of byte 0): 0 264 // bit 1: 1 265 // bit 2: 0 266 // bit 3: 1 267 // bit 4: 1 268 // bit 5: 0 269 // bit 6: 1 270 // bit 7: 1 271 // byte 0 = 0101_1011 = 0x5B 272 // 273 // bit 8: 1 274 // bit 9: 1 275 // bit 10: 1 276 // bit 11: 0 277 // bit 12: ... (4 padding bits) 278 // byte 1 = 1110_0000 = 0xE0 279 let buf: *u8 = (sys_mmap(2)) as *u8 280 buf[0] = 0x5B as u8 281 buf[1] = 0xE0 as u8 282 283 let bs: *NxBitStream = nx_bitstream_alloc(buf, 2) 284 let s1: nx_int = nx_huffman_decode_msb(t, bs) 285 if s1 != 1 { return 20 } 286 let s2: nx_int = nx_huffman_decode_msb(t, bs) 287 if s2 != 0 { return 21 } 288 let s3: nx_int = nx_huffman_decode_msb(t, bs) 289 if s3 != 2 { return 22 } 290 let s4: nx_int = nx_huffman_decode_msb(t, bs) 291 if s4 != 3 { return 23 } 292 let s5: nx_int = nx_huffman_decode_msb(t, bs) 293 if s5 != 1 { return 24 } 294 295 // ---- bit-reverse helper ---- 296 // reverse(0b101, 3) = 0b101 = 5 297 if _huff_reverse_bits(5, 3) != 5 { return 30 } 298 // reverse(0b110, 3) = 0b011 = 3 299 if _huff_reverse_bits(6, 3) != 3 { return 31 } 300 // reverse(0b1010, 4) = 0b0101 = 5 301 if _huff_reverse_bits(10, 4) != 5 { return 32 } 302 303 return 0 304}