nx_jpeg_entropy.nx source
↩ module page · 174 lines · 6712 B
1// nx_jpeg_entropy.nx -- baseline-JPEG entropy-coded segment decoder.
2// Per ITU-T Rec. T.81 sec F.2. Heaviest brick of JPEG decode.
3//
4// Per-MCU decode shape (baseline sequential, T.81 sec F.2.1.2):
5//
6// for each color component in the scan:
7// -- DC coefficient (T.81 sec F.2.2.1)
8// T = HUFF_DECODE(DC_table) // 0..15 = "category"
9// DIFF = if T == 0 then 0
10// else RECEIVE(T) extended via EXTEND(...)
11// DC[0] = prev_dc + DIFF
12// prev_dc = DC[0]
13//
14// -- 63 AC coefficients (T.81 sec F.2.2.2)
15// k = 1
16// while k < 64:
17// RS = HUFF_DECODE(AC_table) // 8-bit: high4=run, low4=size
18// R = RS >> 4
19// S = RS & 0x0F
20// if S == 0:
21// if R == 15: k = k + 16 // ZRL (zero-run-length=16)
22// else: k = 64 // EOB (end of block)
23// else:
24// k = k + R // skip R zeros
25// AC[k] = RECEIVE(S) extended via EXTEND(...)
26// k = k + 1
27//
28// EXTEND(v, T) per T.81 sec F.2.2.1:
29// if v < 2^(T-1) then v - (2^T - 1)
30// else v
31//
32// RECEIVE(T) reads T bits MSB-first from the bitstream.
33//
34// Output: zig-zag-ordered 64-entry coefficient block. Consumer
35// dequantizes + un-zigzags + IDCTs.
36//
37// nx_safety_envelope:
38// intended_use: "Entropy decode for baseline JPEG MCUs."
39// sil_target: SIL1
40// evidence: [t81_section_f_2_canonical_basis,
41// composes_dht_decode_primitive,
42// bounded_64_coefficient_block]
43// hazard_register: [bug-tape-jpeg-zrl-run-overflow,
44// bug-tape-jpeg-extend-sign-error,
45// bug-tape-jpeg-eof-mid-block]
46// verdict: NOT_YET_EVALUATED
47
48import "nx_syscalls.nx"
49import "nx_jpeg_dht.nx"
50
51const NX_JPEG_ENT_OK: i64 = 0
52const NX_JPEG_ENT_EOF: i64 = 1 // ran out of bytes mid-block
53const NX_JPEG_ENT_BAD_HUFF: i64 = 2 // Huffman decode failed
54const NX_JPEG_ENT_BAD_RUN: i64 = 3 // AC run would push k >= 64
55const NX_JPEG_ENT_RESULT_N: i64 = 4
56
57func nx_jpeg_ent_result_is_valid(v: i64) -> i64 {
58 if v < 0 { return 0 }
59 if v >= NX_JPEG_ENT_RESULT_N { return 0 }
60 return 1
61}
62
63// RECEIVE(T) per T.81 sec F.2.2.4: read T bits MSB-first from the
64// bitstream. Bit-source semantics match nx_jpeg_huff_decode_symbol:
65// byte_idx_p[0]/bit_off_p[0] advance, 0xFF 0x00 stuffing is honoured.
66// Returns the unsigned T-bit value or -1 on EOF.
67func nx_jpeg_ent_receive(t_bits: i64,
68 bit_src: *u8, bit_off_p: *i64,
69 byte_idx_p: *i64, src_end: i64) -> i64 {
70 if t_bits <= 0 { return 0 }
71 if t_bits > 16 { return 0 - 1 } // baseline categories cap at 15 actually
72 var result: i64 = 0
73 var i: i64 = 0
74 while i < t_bits {
75 var byte_idx: i64 = byte_idx_p[0]
76 var bit_off: i64 = bit_off_p[0]
77 var bit_val: i64 = 0 // past the entropy end -> pad with 0-bits (JPEG tail)
78 if byte_idx < src_end {
79 let b: i64 = bit_src[byte_idx] as i64
80 bit_val = (b >> (7 - bit_off)) & 1
81 bit_off = bit_off + 1
82 if bit_off == 8 {
83 bit_off = 0
84 byte_idx = byte_idx + 1
85 if byte_idx < src_end {
86 if b == 0xFF {
87 let nb: i64 = bit_src[byte_idx] as i64
88 if nb == 0x00 { byte_idx = byte_idx + 1 } // stuffing: skip 0x00
89 else { byte_idx = src_end } // MARKER -> entropy ended, pad from here
90 }
91 }
92 }
93 bit_off_p[0] = bit_off
94 byte_idx_p[0] = byte_idx
95 }
96 result = (result << 1) | bit_val
97 i = i + 1
98 }
99 return result
100}
101
102// EXTEND(v, T) per T.81 sec F.2.2.1 / Fig F.12:
103// if v < 2^(T-1) then v + (-(2^T) + 1) i.e. v - (2^T - 1)
104// else v
105func nx_jpeg_ent_extend(v: i64, t_bits: i64) -> i64 {
106 if t_bits == 0 { return 0 }
107 let half: i64 = 1 << (t_bits - 1)
108 if v < half {
109 let full: i64 = 1 << t_bits
110 return v - (full - 1)
111 }
112 return v
113}
114
115// Decode one MCU coefficient block per T.81 sec F.2.1.2 / Fig F.13.
116//
117// dc_table -- Huffman table for DC differential category
118// ac_table -- Huffman table for AC RS bytes
119// prev_dc_p -- *i64 holding running prev_dc; updated in place
120// block_zigzag -- output 64-entry i64 array (in zig-zag order)
121// bit_src, bit_off_p, byte_idx_p, src_end -- bitstream cursor
122//
123// Returns NX_JPEG_ENT_OK on success.
124func nx_jpeg_ent_decode_block(dc_table: *NxJpegHTable,
125 ac_table: *NxJpegHTable,
126 prev_dc_p: *i64,
127 block_zigzag: *i64,
128 bit_src: *u8,
129 bit_off_p: *i64, byte_idx_p: *i64,
130 src_end: i64) -> i64 {
131 // Zero-init the block.
132 var i: i64 = 0
133 while i < 64 { block_zigzag[i] = 0; i = i + 1 }
134
135 // ---- DC coefficient ----
136 let dc_t: i64 = nx_jpeg_huff_decode_symbol(dc_table, bit_src, bit_off_p, byte_idx_p, src_end)
137 if dc_t < 0 { return NX_JPEG_ENT_BAD_HUFF }
138 var dc_diff: i64 = 0
139 if dc_t > 0 {
140 let raw: i64 = nx_jpeg_ent_receive(dc_t, bit_src, bit_off_p, byte_idx_p, src_end)
141 if raw < 0 { return NX_JPEG_ENT_EOF }
142 dc_diff = nx_jpeg_ent_extend(raw, dc_t)
143 }
144 prev_dc_p[0] = prev_dc_p[0] + dc_diff
145 block_zigzag[0] = prev_dc_p[0]
146
147 // ---- AC coefficients ----
148 var k: i64 = 1
149 while k < 64 {
150 let rs: i64 = nx_jpeg_huff_decode_symbol(ac_table, bit_src, bit_off_p, byte_idx_p, src_end)
151 if rs < 0 { return NX_JPEG_ENT_BAD_HUFF }
152 let r: i64 = rs >> 4
153 let s: i64 = rs & 0x0F
154 if s == 0 {
155 if r == 15 {
156 // ZRL: 16 zeros. Block was zero-initialised already so
157 // we just advance k.
158 k = k + 16
159 if k > 64 { return NX_JPEG_ENT_BAD_RUN }
160 } else {
161 // EOB: remaining coefficients are zero. Done.
162 k = 64
163 }
164 } else {
165 k = k + r
166 if k >= 64 { return NX_JPEG_ENT_BAD_RUN }
167 let raw_ac: i64 = nx_jpeg_ent_receive(s, bit_src, bit_off_p, byte_idx_p, src_end)
168 if raw_ac < 0 { return NX_JPEG_ENT_EOF }
169 block_zigzag[k] = nx_jpeg_ent_extend(raw_ac, s)
170 k = k + 1
171 }
172 }
173 return NX_JPEG_ENT_OK
174}