j2k_codec_math/
jpeg.rs

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

j2k_codec_math/
jpeg.rs
