nx_jpeg_dht.nx source
↩ module page · 237 lines · 9491 B
1// nx_jpeg_dht.nx -- JPEG Huffman-table (DHT) parser per ITU-T Rec.
2// T.81 sec B.2.4.2 + canonical decode-table builder per Annex C.
3//
4// DHT payload layout (one or more tables packed):
5// Tc (4 bits) Th (4 bits) -- class (0=DC, 1=AC) + table-id (0..3)
6// L1..L16 (16 bytes) -- BITS: count of codes of each length
7// V1..Vn (sum-of-BITS) -- HUFFVAL: symbol assignments in
8// increasing-code-value order
9//
10// Canonical decode table (T.81 Annex C, Fig C.1-C.3) consists of three
11// 17-entry arrays (lengths 1..16, index 0 unused):
12// MINCODE[L] -- smallest code of length L
13// MAXCODE[L] -- largest code of length L (-1 if no codes of len L)
14// VALPTR[L] -- index into HUFFVAL where codes of length L begin
15//
16// Decode algorithm (T.81 Fig F.16) -- DECODE:
17// read 1 bit -> CODE
18// for L = 1 to 16:
19// if CODE <= MAXCODE[L]:
20// return HUFFVAL[VALPTR[L] + CODE - MINCODE[L]]
21// read 1 more bit; CODE = (CODE << 1) | bit
22// error
23//
24// nx_safety_envelope:
25// intended_use: "Huffman-table parsing + canonical decode-table
26// construction for JPEG entropy decode."
27// sil_target: SIL1
28// evidence: [t81_section_b_2_4_2_canonical_basis,
29// t81_annex_c_canonical_table_algorithm,
30// bounded_iteration]
31// hazard_register: [bug-tape-dht-huffsize-table-overflow,
32// bug-tape-dht-malformed-bits-length-sum,
33// bug-tape-dht-tc-th-out-of-range]
34// residual_risk: "Decode-table users must bound L<=16 per spec;
35// substrate emits BAD_LENGTH if BITS sum >256."
36// verdict: NOT_YET_EVALUATED
37
38import "nx_syscalls.nx"
39
40// Sealed-enum result codes.
41const NX_JPEG_DHT_OK: i64 = 0
42const NX_JPEG_DHT_TRUNC: i64 = 1
43const NX_JPEG_DHT_BAD_TC: i64 = 2 // Tc > 1
44const NX_JPEG_DHT_BAD_TH: i64 = 3 // Th > 3
45const NX_JPEG_DHT_TOO_MANY_SYM: i64 = 4 // sum-of-BITS > 256
46const NX_JPEG_DHT_OVERFLOW: i64 = 5 // more than 4 tables in payload
47const NX_JPEG_DHT_RESULT_N: i64 = 6
48
49func nx_jpeg_dht_result_is_valid(v: i64) -> i64 {
50 if v < 0 { return 0 }
51 if v >= NX_JPEG_DHT_RESULT_N { return 0 }
52 return 1
53}
54
55// One parsed Huffman table -- canonical decode form ready for use by
56// the entropy decoder.
57struct NxJpegHTable {
58 tc: i64, // table class 0=DC, 1=AC
59 th: i64, // table-id 0..3
60 n_symbols: i64, // sum of BITS[1..16]
61 bits: *i64, // 17 entries (idx 0 unused; idx 1..16 = BITS counts)
62 huffval: *i64, // n_symbols entries (the symbol assignments)
63 mincode: *i64, // 17 entries (T.81 Fig C.3 derivation)
64 maxcode: *i64, // 17 entries (-1 if no codes of length L)
65 valptr: *i64 // 17 entries (start index into huffval)
66}
67
68const NX_JPEG_HTABLE_BYTES: i64 = 64
69
70// Build canonical decode tables (MINCODE/MAXCODE/VALPTR) per T.81
71// Fig C.1-C.3. Caller has already populated `bits` (17 entries) and
72// allocated the three output arrays (17 entries each).
73func nx_jpeg_dht_build_decode_tables(bits: *i64,
74 mincode: *i64,
75 maxcode: *i64,
76 valptr: *i64) -> i64 {
77 // First derive HUFFSIZE table (T.81 Fig C.1): list of code lengths
78 // for each symbol in increasing-code-value order. We don't actually
79 // need to store HUFFSIZE for decode -- MINCODE/MAXCODE/VALPTR
80 // suffice -- but we need to walk over it conceptually.
81 //
82 // Fig C.2 generates HUFFCODE: code[k] for k = 0..n_symbols-1.
83 // Then Fig C.3 derives MINCODE/MAXCODE/VALPTR from HUFFSIZE+HUFFCODE.
84 //
85 // We perform Fig C.3 directly without materialising HUFFSIZE/HUFFCODE
86 // because we only need the per-length boundaries.
87
88 var L: i64 = 0
89 while L <= 16 {
90 mincode[L] = 0
91 maxcode[L] = 0 - 1 // -1 = "no codes of this length"
92 valptr[L] = 0
93 L = L + 1
94 }
95
96 var code: i64 = 0
97 var symbol_idx: i64 = 0
98 L = 1
99 while L <= 16 {
100 let n_codes_of_len: i64 = bits[L]
101 if n_codes_of_len > 0 {
102 mincode[L] = code
103 valptr[L] = symbol_idx
104 maxcode[L] = code + n_codes_of_len - 1
105 code = code + n_codes_of_len
106 symbol_idx = symbol_idx + n_codes_of_len
107 }
108 code = code << 1 // shift left at end of each length per Fig C.2
109 L = L + 1
110 }
111 return 0
112}
113
114// Parse a DHT payload into 1..4 tables. Caller pre-allocates:
115// tables[4] -- NxJpegHTable structs
116// bits_pool[4*17] -- shared i64 storage for BITS arrays
117// huffval_pool[4*256] -- shared i64 storage for HUFFVAL arrays
118// mincode_pool[4*17]
119// maxcode_pool[4*17]
120// valptr_pool[4*17]
121// count_p receives parsed-table count.
122func nx_jpeg_dht_parse(payload: *u8, payload_len: i64,
123 tables: *NxJpegHTable,
124 bits_pool: *i64, huffval_pool: *i64,
125 mincode_pool: *i64, maxcode_pool: *i64,
126 valptr_pool: *i64,
127 count_p: *i64) -> i64 {
128 var p: i64 = 0
129 var n_tables: i64 = 0
130 count_p[0] = 0
131
132 while p < payload_len {
133 if n_tables >= 4 { return NX_JPEG_DHT_OVERFLOW }
134 if p >= payload_len { return NX_JPEG_DHT_TRUNC }
135 let tc_th: i64 = payload[p] as i64
136 p = p + 1
137 let tc: i64 = tc_th >> 4
138 let th: i64 = tc_th & 0x0F
139 if tc > 1 { return NX_JPEG_DHT_BAD_TC }
140 if th > 3 { return NX_JPEG_DHT_BAD_TH }
141
142 if p + 16 > payload_len { return NX_JPEG_DHT_TRUNC }
143
144 let bits_slice: *i64 = (bits_pool as i64 + n_tables * 17 * 8) as *i64
145 bits_slice[0] = 0
146 var n_symbols: i64 = 0
147 var i: i64 = 1
148 while i <= 16 {
149 let v: i64 = payload[p + i - 1] as i64
150 bits_slice[i] = v
151 n_symbols = n_symbols + v
152 i = i + 1
153 }
154 p = p + 16
155 if n_symbols > 256 { return NX_JPEG_DHT_TOO_MANY_SYM }
156 if p + n_symbols > payload_len { return NX_JPEG_DHT_TRUNC }
157
158 let huffval_slice: *i64 = (huffval_pool as i64 + n_tables * 256 * 8) as *i64
159 var k: i64 = 0
160 while k < n_symbols {
161 huffval_slice[k] = payload[p + k] as i64
162 k = k + 1
163 }
164 p = p + n_symbols
165
166 let mincode_slice: *i64 = (mincode_pool as i64 + n_tables * 17 * 8) as *i64
167 let maxcode_slice: *i64 = (maxcode_pool as i64 + n_tables * 17 * 8) as *i64
168 let valptr_slice: *i64 = (valptr_pool as i64 + n_tables * 17 * 8) as *i64
169 nx_jpeg_dht_build_decode_tables(bits_slice, mincode_slice, maxcode_slice, valptr_slice)
170
171 let entry: *NxJpegHTable = (tables as i64 + n_tables * NX_JPEG_HTABLE_BYTES) as *NxJpegHTable
172 entry.tc = tc
173 entry.th = th
174 entry.n_symbols = n_symbols
175 entry.bits = bits_slice
176 entry.huffval = huffval_slice
177 entry.mincode = mincode_slice
178 entry.maxcode = maxcode_slice
179 entry.valptr = valptr_slice
180
181 n_tables = n_tables + 1
182 }
183
184 count_p[0] = n_tables
185 return NX_JPEG_DHT_OK
186}
187
188// Decode one Huffman-coded symbol from a bit-source. Returns the
189// 8-bit symbol value or -1 on EOF / invalid code.
190//
191// `bit_src` is a *u8 pointing at the next byte to consume. `bit_off_p`
192// holds the bit offset within `*bit_src` (0..7, MSB first per JPEG
193// convention). Both are advanced past consumed bits.
194//
195// `src_end` is the byte AFTER the last legal byte (bound check).
196//
197// Per T.81 sec F.1.2.3, the entropy stream uses 0xFF 0x00 stuffing:
198// a literal 0xFF in the bitstream is followed by 0x00. This decoder
199// transparently skips the 0x00 when it follows a 0xFF byte.
200func nx_jpeg_huff_decode_symbol(table: *NxJpegHTable,
201 bit_src: *u8, bit_off_p: *i64,
202 byte_idx_p: *i64, src_end: i64) -> i64 {
203 var code: i64 = 0
204 var L: i64 = 1
205 while L <= 16 {
206 // Pull one bit (MSB-first). Past the entropy end -> feed 0-bits (JPEG pads the tail); a real marker
207 // (0xFF + non-0x00, e.g. EOI 0xFFD9) ENDS the entropy stream -> jump to end so we pad, not read it.
208 var byte_idx: i64 = byte_idx_p[0]
209 var bit_off: i64 = bit_off_p[0]
210 var bit_val: i64 = 0
211 if byte_idx < src_end {
212 let b: i64 = bit_src[byte_idx] as i64
213 bit_val = (b >> (7 - bit_off)) & 1
214 bit_off = bit_off + 1
215 if bit_off == 8 {
216 bit_off = 0
217 byte_idx = byte_idx + 1
218 if byte_idx < src_end {
219 if b == 0xFF {
220 let nb: i64 = bit_src[byte_idx] as i64
221 if nb == 0x00 { byte_idx = byte_idx + 1 } // byte-stuffing: skip the 0x00
222 else { byte_idx = src_end } // MARKER -> entropy ended, pad from here
223 }
224 }
225 }
226 bit_off_p[0] = bit_off
227 byte_idx_p[0] = byte_idx
228 }
229
230 code = (code << 1) | bit_val
231 if code <= table.maxcode[L] {
232 return table.huffval[table.valptr[L] + code - table.mincode[L]]
233 }
234 L = L + 1
235 }
236 return 0 - 1 // no code found within 16 bits
237}