j2k_codec_math/
jpeg.rs

1//! JPEG constants and helpers shared by CPU and device backends.
2
3use core::fmt;
4
5/// Lossless (SOF3) prediction and difference coding.
6pub mod lossless;
7
8/// T.81 zigzag order from stream coefficient index to natural 8x8 index.
9#[rustfmt::skip]
10pub const ZIGZAG: [u8; 64] = [
11     0,  1,  8, 16,  9,  2,  3, 10,
12    17, 24, 32, 25, 18, 11,  4,  5,
13    12, 19, 26, 33, 40, 48, 41, 34,
14    27, 20, 13,  6,  7, 14, 21, 28,
15    35, 42, 49, 56, 57, 50, 43, 36,
16    29, 22, 15, 23, 30, 37, 44, 51,
17    58, 59, 52, 45, 38, 31, 39, 46,
18    53, 60, 61, 54, 47, 55, 62, 63,
19];
20
21/// Canonical JPEG Huffman table derivation.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub struct CanonicalHuffmanDerivation {
24    /// Smallest code for each code length; `i32::MAX` when absent.
25    pub min_code: [i32; 17],
26    /// Largest code for each code length; `-1` when absent.
27    pub max_code: [i32; 17],
28    /// Value-index offset for each code length.
29    pub val_offset: [i32; 17],
30    /// Canonical Huffman code for each value index.
31    pub huffcode: [u16; 256],
32    /// Canonical Huffman code length for each value index.
33    pub huffsize: [u8; 256],
34    /// Number of valid entries in `huffcode` and `huffsize`.
35    pub huffsize_len: usize,
36}
37
38/// Error returned by [`derive_canonical_huffman`].
39#[derive(Debug, Clone, Copy, PartialEq, Eq)]
40pub enum CanonicalHuffmanError {
41    /// BITS entries describe more than 256 symbols.
42    BitsExceedTableCapacity,
43    /// BITS counts do not match the supplied HUFFVAL length.
44    BitsValuesLenMismatch,
45    /// Canonical code assignment overflowed the JPEG 16-bit code space.
46    CodeOverflow,
47}
48
49impl fmt::Display for CanonicalHuffmanError {
50    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
51        match self {
52            Self::BitsExceedTableCapacity => f.write_str("BITS exceed table capacity"),
53            Self::BitsValuesLenMismatch => f.write_str("BITS do not match HUFFVAL length"),
54            Self::CodeOverflow => f.write_str("canonical code overflow"),
55        }
56    }
57}
58
59/// Derive canonical JPEG Huffman codes and slow-path decode bounds from the
60/// T.81 DHT `BITS` vector and HUFFVAL length.
61///
62/// The caller owns the HUFFVAL bytes; this helper derives only the canonical
63/// code metadata shared by CPU and device backends.
64#[expect(
65    clippy::cast_possible_truncation,
66    clippy::cast_possible_wrap,
67    reason = "JPEG Huffman lengths and value counts are bounded to 16 and 256, which fit every converted integer type"
68)]
69pub const fn derive_canonical_huffman(
70    bits: &[u8; 16],
71    values_len: usize,
72) -> Result<CanonicalHuffmanDerivation, CanonicalHuffmanError> {
73    if values_len > 256 {
74        return Err(CanonicalHuffmanError::BitsExceedTableCapacity);
75    }
76
77    let mut huffsize = [0u8; 256];
78    let mut huffsize_len = 0usize;
79    let mut len_minus_1 = 0usize;
80    while len_minus_1 < bits.len() {
81        let len = (len_minus_1 + 1) as u8;
82        let mut remaining = bits[len_minus_1];
83        while remaining != 0 {
84            if huffsize_len >= values_len || huffsize_len >= huffsize.len() {
85                return Err(CanonicalHuffmanError::BitsExceedTableCapacity);
86            }
87            huffsize[huffsize_len] = len;
88            huffsize_len += 1;
89            remaining -= 1;
90        }
91        len_minus_1 += 1;
92    }
93    if huffsize_len != values_len {
94        return Err(CanonicalHuffmanError::BitsValuesLenMismatch);
95    }
96
97    let mut huffcode = [0u16; 256];
98    let mut code = 0u32;
99    let mut si = if huffsize_len == 0 { 0 } else { huffsize[0] };
100    let mut idx = 0usize;
101    while idx < huffsize_len {
102        let size = huffsize[idx];
103        while size != si {
104            code <<= 1;
105            si = si.saturating_add(1);
106        }
107        if si > 16 || code >= (1u32 << si) {
108            return Err(CanonicalHuffmanError::CodeOverflow);
109        }
110        huffcode[idx] = code as u16;
111        code = match code.checked_add(1) {
112            Some(next) => next,
113            None => return Err(CanonicalHuffmanError::CodeOverflow),
114        };
115        idx += 1;
116    }
117
118    let mut min_code = [i32::MAX; 17];
119    let mut max_code = [-1i32; 17];
120    let mut val_offset = [0i32; 17];
121    let mut cursor = 0usize;
122    let mut len_minus_1 = 0usize;
123    while len_minus_1 < bits.len() {
124        let len = len_minus_1 + 1;
125        let count = bits[len_minus_1] as usize;
126        if count == 0 {
127            len_minus_1 += 1;
128            continue;
129        }
130        min_code[len] = huffcode[cursor] as i32;
131        max_code[len] = huffcode[cursor + count - 1] as i32;
132        val_offset[len] = cursor as i32 - min_code[len];
133        cursor += count;
134        len_minus_1 += 1;
135    }
136
137    Ok(CanonicalHuffmanDerivation {
138        min_code,
139        max_code,
140        val_offset,
141        huffcode,
142        huffsize,
143        huffsize_len,
144    })
145}
146
147/// Fixed-point constants used by the baseline JPEG integer IDCT.
148pub mod idct {
149    /// Number of fractional bits in the integer IDCT constants.
150    pub const CONST_BITS: usize = 13;
151    /// First-pass post-IDCT scaling bits.
152    pub const PASS1_BITS: usize = 2;
153
154    /// Fixed-point integer approximation of 0.298631336.
155    pub const FIX_0_298631336: i32 = 2_446;
156    /// Fixed-point integer approximation of 0.390180644.
157    pub const FIX_0_390180644: i32 = 3_196;
158    /// Fixed-point integer approximation of 0.541196100.
159    pub const FIX_0_541196100: i32 = 4_433;
160    /// Fixed-point integer approximation of 0.765366865.
161    pub const FIX_0_765366865: i32 = 6_270;
162    /// Fixed-point integer approximation of 0.899976223.
163    pub const FIX_0_899976223: i32 = 7_373;
164    /// Fixed-point integer approximation of 1.175875602.
165    pub const FIX_1_175875602: i32 = 9_633;
166    /// Fixed-point integer approximation of 1.501321110.
167    pub const FIX_1_501321110: i32 = 12_299;
168    /// Fixed-point integer approximation of 1.847759065.
169    pub const FIX_1_847759065: i32 = 15_137;
170    /// Fixed-point integer approximation of 1.961570560.
171    pub const FIX_1_961570560: i32 = 16_069;
172    /// Fixed-point integer approximation of 2.053119869.
173    pub const FIX_2_053119869: i32 = 16_819;
174    /// Fixed-point integer approximation of 2.562915447.
175    pub const FIX_2_562915447: i32 = 20_995;
176    /// Fixed-point integer approximation of 3.072711026.
177    pub const FIX_3_072711026: i32 = 25_172;
178}
179
180/// Fixed-point constants used by JPEG YCbCr to RGB conversion.
181pub mod ycbcr {
182    /// Fixed-point integer approximation of 1.40200 * 2^16.
183    pub const FIX_1_40200: i32 = 91_881;
184    /// Fixed-point integer approximation of 0.34414 * 2^16.
185    pub const FIX_0_34414: i32 = 22_554;
186    /// Fixed-point integer approximation of 0.71414 * 2^16.
187    pub const FIX_0_71414: i32 = 46_802;
188    /// Fixed-point integer approximation of 1.77200 * 2^16.
189    pub const FIX_1_77200: i32 = 116_130;
190    /// Rounding addend for 16-bit fixed-point color conversion.
191    pub const ROUND: i32 = 1 << 15;
192}
193
194#[cfg(test)]
195mod tests {
196    extern crate alloc;
197
198    use super::*;
199    use alloc::string::ToString;
200
201    #[test]
202    fn zigzag_is_a_permutation_of_one_block() {
203        let mut seen = [false; 64];
204        for &idx in &ZIGZAG {
205            assert!(idx < 64);
206            assert!(!seen[idx as usize], "duplicate zigzag index {idx}");
207            seen[idx as usize] = true;
208        }
209        assert!(seen.into_iter().all(|entry| entry));
210    }
211
212    #[test]
213    fn canonical_huffman_derivation_matches_t81_luma_dc_table() {
214        let bits = [0, 1, 5, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0];
215        let Ok(canonical) = derive_canonical_huffman(&bits, 12) else {
216            panic!("canonical table should derive");
217        };
218
219        assert_eq!(canonical.huffsize_len, 12);
220        assert_eq!(
221            &canonical.huffsize[..12],
222            &[2, 3, 3, 3, 3, 3, 4, 5, 6, 7, 8, 9]
223        );
224        assert_eq!(
225            &canonical.huffcode[..12],
226            &[0, 2, 3, 4, 5, 6, 14, 30, 62, 126, 254, 510]
227        );
228        assert_eq!(canonical.min_code[2], 0);
229        assert_eq!(canonical.max_code[3], 6);
230        assert_eq!(canonical.val_offset[3], -1);
231    }
232
233    #[test]
234    fn canonical_huffman_derivation_rejects_mismatched_value_count() {
235        let bits = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
236
237        assert_eq!(
238            derive_canonical_huffman(&bits, 0),
239            Err(CanonicalHuffmanError::BitsExceedTableCapacity)
240        );
241        assert_eq!(
242            derive_canonical_huffman(&bits, 2),
243            Err(CanonicalHuffmanError::BitsValuesLenMismatch)
244        );
245    }
246
247    #[test]
248    fn canonical_huffman_error_display_is_stable() {
249        let errors = [
250            CanonicalHuffmanError::BitsExceedTableCapacity,
251            CanonicalHuffmanError::BitsValuesLenMismatch,
252            CanonicalHuffmanError::CodeOverflow,
253        ];
254        assert_eq!(
255            errors.map(|error| error.to_string()),
256            [
257                "BITS exceed table capacity",
258                "BITS do not match HUFFVAL length",
259                "canonical code overflow",
260            ]
261        );
262    }
263
264    #[test]
265    fn canonical_huffman_derivation_accepts_complete_decoder_table() {
266        let bits = [2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
267
268        let derived = derive_canonical_huffman(&bits, 2).expect("complete prefix table derives");
269        assert_eq!(&derived.huffcode[..2], &[0, 1]);
270    }
271
272    #[test]
273    fn idct_constants_match_existing_integer_backend() {
274        assert_eq!(idct::CONST_BITS, 13);
275        assert_eq!(idct::PASS1_BITS, 2);
276        assert_eq!(idct::FIX_0_298631336, 2_446);
277        assert_eq!(idct::FIX_0_390180644, 3_196);
278        assert_eq!(idct::FIX_0_541196100, 4_433);
279        assert_eq!(idct::FIX_0_765366865, 6_270);
280        assert_eq!(idct::FIX_0_899976223, 7_373);
281        assert_eq!(idct::FIX_1_175875602, 9_633);
282        assert_eq!(idct::FIX_1_501321110, 12_299);
283        assert_eq!(idct::FIX_1_847759065, 15_137);
284        assert_eq!(idct::FIX_1_961570560, 16_069);
285        assert_eq!(idct::FIX_2_053119869, 16_819);
286        assert_eq!(idct::FIX_2_562915447, 20_995);
287        assert_eq!(idct::FIX_3_072711026, 25_172);
288    }
289}
j2k_codec_math/jpeg.rs

j2k_codec_math/
jpeg.rs
