nx_webp_huff.nx source

1// nx_webp_huff.nx -- VP8L Huffman code-group reader (WebP lossless). 2// 3// VP8L transmits every Huffman tree in one of two forms: 4// SIMPLE -- 1 or 2 symbols written literally, no code-length layer 5// NORMAL -- a 19-symbol code-length alphabet (3 bits each, sent in a 6// fixed permuted order) which then codes the real symbol 7// lengths, with run-length symbols 16/17/18 8// 9// Both forms resolve to a canonical Huffman table, so both compose onto 10// the existing nx_huffman primitive: VP8L reads bits LSB-first out of the 11// byte stream and sends each code MSB-of-code first, which is exactly what 12// nx_huffman_decode_lsb implements (contract re-verified against 13// nx_bitstream.nx and nx_huffman.nx on 2026-07-31, not assumed from docs). 14// 15// THE ZERO-BIT CASE. A tree carrying exactly one symbol must decode that 16// symbol while consuming NO bits. nx_huffman_decode_lsb always consumes at 17// least one bit, so a bare canonical table is wrong here and would desync 18// the whole stream. NxWlTree carries the single-symbol case explicitly 19// rather than leaving it to the table -- this is the defect that silently 20// corrupts every VP8L image whose alpha or red channel is constant, which 21// is most synthetic images. 22// 23// genealogy_id: webp_lossless_bitstream_spec_2012 24// lineage_id: nx_webp_huff_v1 25// license_tier: ORIGINAL 26 27import "nx_syscalls.nx" 28import "nx_bitstream.nx" 29import "nx_huffman.nx" 30 31// ===== alphabet sizes (spec-fixed, not tunable) =================== 32 33const NX_WL_CODE_LENGTH_CODES: i64 = 19 34const NX_WL_CODE_LEN_LITERALS: i64 = 16 35const NX_WL_DEFAULT_CODE_LEN: i64 = 8 36const NX_WL_TREE_BYTES: i64 = 24 37 38// ===== tree handle ================================================ 39// 40// Fields are i64 by construction -- nx_cc lays struct fields out at 41// i64 stride, so declaring them nx_int mis-offsets every read after 42// the first (see reference-nxcc-nxint-struct-field-offset-bug). 43// `table` holds a *NxHuffmanTable widened to i64. 44 45struct NxWlTree { 46 table: i64, 47 trivial: i64, 48 symbol: i64, 49} 50 51// ===== code-length code order (spec table) ======================== 52// 53// The 19 code-length symbols are transmitted in this permuted order so 54// that a truncated list still carries the most common lengths. 55 56func wl_code_order(out: *i64) -> i64 { 57 out[0] = 17; out[1] = 18; out[2] = 0; out[3] = 1 58 out[4] = 2; out[5] = 3; out[6] = 4; out[7] = 5 59 out[8] = 16; out[9] = 6; out[10] = 7; out[11] = 8 60 out[12] = 9; out[13] = 10; out[14] = 11; out[15] = 12 61 out[16] = 13; out[17] = 14; out[18] = 15 62 return NX_WL_CODE_LENGTH_CODES 63} 64 65// repeat symbols 16/17/18: extra bits read, and the count they add to 66func wl_repeat_extra_bits(slot: i64) -> i64 { 67 if slot == 0 { return 2 } 68 if slot == 1 { return 3 } 69 return 7 70} 71 72func wl_repeat_offset(slot: i64) -> i64 { 73 if slot == 0 { return 3 } 74 if slot == 1 { return 3 } 75 return 11 76} 77 78// ===== tree construction from a length vector ===================== 79// 80// Collapses to the zero-bit form when exactly one symbol is present. 81// Returns 0 when the length vector codes nothing at all -- a caller 82// that needs a mandatory tree must treat 0 as a malformed stream 83// rather than as an empty-but-valid one. 84 85func wl_tree_from_lengths(lengths: *i64, n_symbols: i64) -> *NxWlTree { 86 var nonzero: i64 = 0 87 var last_sym: i64 = 0 88 var i: i64 = 0 89 while i < n_symbols { 90 if lengths[i] != 0 { nonzero = nonzero + 1; last_sym = i } 91 i = i + 1 92 } 93 if nonzero == 0 { return 0 as *NxWlTree } 94 95 let t: *NxWlTree = sys_mmap(NX_WL_TREE_BYTES) as *NxWlTree 96 if nonzero == 1 { 97 t.table = 0 98 t.trivial = 1 99 t.symbol = last_sym 100 return t 101 } 102 let ht: *NxHuffmanTable = nx_huffman_build(lengths as *nx_int, n_symbols as nx_int) 103 if ht == (0 as *NxHuffmanTable) { return 0 as *NxWlTree } 104 t.table = ht as i64 105 t.trivial = 0 106 t.symbol = 0 107 return t 108} 109 110// ===== decode one symbol ========================================== 111// 112// Returns -1 on a malformed code or an exhausted bitstream. A trivial 113// tree consumes no bits, which is the whole point of carrying it. 114 115func wl_decode_symbol(t: *NxWlTree, bs: *NxBitStream) -> i64 { 116 if t == (0 as *NxWlTree) { return 0 - 1 } 117 if t.trivial == 1 { return t.symbol } 118 let ht: *NxHuffmanTable = t.table as *NxHuffmanTable 119 return nx_huffman_decode_lsb(ht, bs) 120} 121 122// ===== SIMPLE form ================================================ 123 124func wl_read_simple(bs: *NxBitStream, lengths: *i64, n_symbols: i64) -> i64 { 125 let num_symbols: i64 = nx_bitstream_read_lsb(bs, 1) + 1 126 let first_len_code: i64 = nx_bitstream_read_lsb(bs, 1) 127 var s0: i64 = 0 128 if first_len_code == 1 { 129 s0 = nx_bitstream_read_lsb(bs, 8) 130 } else { 131 s0 = nx_bitstream_read_lsb(bs, 1) 132 } 133 if s0 < 0 { return 0 } 134 if s0 >= n_symbols { return 0 } 135 lengths[s0] = 1 136 if num_symbols == 2 { 137 let s1: i64 = nx_bitstream_read_lsb(bs, 8) 138 if s1 >= n_symbols { return 0 } 139 if s1 == s0 { return 0 } 140 lengths[s1] = 1 141 } 142 return 1 143} 144 145// ===== NORMAL form ================================================ 146// 147// max_symbol is the spec early-stop: a stream may declare that only the 148// first N symbols carry lengths, leaving the tail implicitly zero. 149// Decrementing it per DECODED SYMBOL (not per written length) is what the 150// spec requires -- a run of 138 zeros costs one decrement, not 138. 151 152func wl_read_normal(bs: *NxBitStream, lengths: *i64, n_symbols: i64) -> i64 { 153 let order: *i64 = sys_mmap(NX_WL_CODE_LENGTH_CODES * 8 + 64) as *i64 154 wl_code_order(order) 155 156 let cl_lengths: *i64 = sys_mmap(NX_WL_CODE_LENGTH_CODES * 8 + 64) as *i64 157 var i: i64 = 0 158 while i < NX_WL_CODE_LENGTH_CODES { cl_lengths[i] = 0; i = i + 1 } 159 160 let num_code_lengths: i64 = nx_bitstream_read_lsb(bs, 4) + 4 161 if num_code_lengths > NX_WL_CODE_LENGTH_CODES { return 0 } 162 i = 0 163 while i < num_code_lengths { 164 cl_lengths[order[i]] = nx_bitstream_read_lsb(bs, 3) 165 i = i + 1 166 } 167 if bs.overflow == 1 { return 0 } 168 169 let cl_tree: *NxWlTree = wl_tree_from_lengths(cl_lengths, NX_WL_CODE_LENGTH_CODES) 170 if cl_tree == (0 as *NxWlTree) { return 0 } 171 172 var max_symbol: i64 = n_symbols 173 if nx_bitstream_read_lsb(bs, 1) == 1 { 174 let length_nbits: i64 = 2 + 2 * nx_bitstream_read_lsb(bs, 3) 175 max_symbol = 2 + nx_bitstream_read_lsb(bs, length_nbits) 176 } 177 // a hostile stream may declare a max_symbol far past the alphabet; the 178 // decode loop is already bounded by n_symbols, but clamping here keeps the 179 // early-stop counter meaningful rather than letting it run as a no-op. 180 if max_symbol > n_symbols { max_symbol = n_symbols } 181 182 var symbol: i64 = 0 183 var prev_len: i64 = NX_WL_DEFAULT_CODE_LEN 184 var ok: i64 = 1 185 var go: i64 = 1 186 while go == 1 { 187 if symbol >= n_symbols { go = 0 } else { 188 if max_symbol <= 0 { go = 0 } else { 189 max_symbol = max_symbol - 1 190 let code_len: i64 = wl_decode_symbol(cl_tree, bs) 191 if code_len < 0 { ok = 0; go = 0 } else { 192 if code_len < NX_WL_CODE_LEN_LITERALS { 193 lengths[symbol] = code_len 194 symbol = symbol + 1 195 if code_len != 0 { prev_len = code_len } 196 } else { 197 let slot: i64 = code_len - NX_WL_CODE_LEN_LITERALS 198 if slot > 2 { ok = 0; go = 0 } else { 199 let extra: i64 = wl_repeat_extra_bits(slot) 200 let offset: i64 = wl_repeat_offset(slot) 201 var repeat: i64 = nx_bitstream_read_lsb(bs, extra) + offset 202 var fill: i64 = 0 203 if slot == 0 { fill = prev_len } 204 if symbol + repeat > n_symbols { ok = 0; go = 0 } else { 205 while repeat > 0 { 206 lengths[symbol] = fill 207 symbol = symbol + 1 208 repeat = repeat - 1 209 } 210 } 211 } 212 } } 213 } } 214 } 215 if bs.overflow == 1 { return 0 } 216 return ok 217} 218 219// ===== the entry point ============================================ 220// 221// Reads one complete Huffman tree of n_symbols from the stream. 222// Returns 0 on any malformed input -- callers MUST check, because a 223// null tree fed to wl_decode_symbol returns -1 forever and would 224// otherwise spin a decode loop rather than failing it. 225 226func wl_read_huffman_code(bs: *NxBitStream, n_symbols: i64) -> *NxWlTree { 227 if n_symbols <= 0 { return 0 as *NxWlTree } 228 let lengths: *i64 = sys_mmap(n_symbols * 8 + 64) as *i64 229 var i: i64 = 0 230 while i < n_symbols { lengths[i] = 0; i = i + 1 } 231 232 let simple: i64 = nx_bitstream_read_lsb(bs, 1) 233 var ok: i64 = 0 234 if simple == 1 { 235 ok = wl_read_simple(bs, lengths, n_symbols) 236 } else { 237 ok = wl_read_normal(bs, lengths, n_symbols) 238 } 239 if ok == 0 { return 0 as *NxWlTree } 240 return wl_tree_from_lengths(lengths, n_symbols) 241}