Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_graphics/src/lzw.rs

6.3 KiB, 1 run

created by r1870400018:75662, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! The Lempel-Ziv-Welch decoder GIF and TIFF share.
2//!
3//! The two formats agree on the algorithm and disagree on three details, which is why one decoder
4//! takes them as arguments rather than each format owning a copy: GIF packs its codes least
5//! significant bit first and TIFF most significant bit first; GIF starts at any code size from two
6//! to eight bits and TIFF always at eight; and TIFF widens the code one entry early, when the table
7//! is one short of the next power of two, a quirk of the first encoder that the specification then
8//! wrote down as the rule.
9//!
10//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
11//! Anthropic Claude
12
13use oxedyne_fe2o3_core::prelude::*;
14
15const MAX_BITS: u32 = 12;
16const TABLE: usize = 1 << MAX_BITS;
17
18/// Which end of each byte the codes are read from.
19#[derive(Clone, Copy, Debug, PartialEq, Eq)]
20pub enum BitOrder {
21 Lsb, // GIF
22 Msb, // TIFF
23}
24
25/// Decodes an LZW stream into at most `limit` bytes.
26///
27/// A stream that ends without its end-of-information code is taken as ended rather than refused:
28/// GIF writers and TIFF writers alike are known to leave it off, and every byte before it decoded
29/// correctly. A code that names an entry not yet in the table is refused, since nothing after it can
30/// be trusted.
31///
32/// # Arguments
33/// * `min` - The literal code width: GIF's minimum code size, or 8 for TIFF.
34/// * `early` - Whether the code widens one entry early, as TIFF's does.
35pub fn decode(data: &[u8], min: u8, order: BitOrder, early: bool, limit: usize)
36 -> Outcome<Vec<u8>>
37{
38 if min < 1 || min as u32 >= MAX_BITS {
39 return Err(err!(
40 "An LZW literal width of {} bits is outside 1 to {}.", min, MAX_BITS - 1;
41 Invalid, Input, Decode));
42 }
43 let clear = 1usize << min;
44 let eoi = clear + 1;
45 let mut prefix = vec![0u16; TABLE];
46 let mut suffix = vec![0u8; TABLE];
47 let mut first = vec![0u8; TABLE];
48 let mut length = vec![0u16; TABLE];
49 for i in 0..clear {
50 suffix[i] = i as u8;
51 first[i] = i as u8;
52 length[i] = 1;
53 }
54 let mut next = eoi + 1;
55 let mut size = min as u32 + 1;
56 let mut prev: Option<usize> = None;
57 let mut out: Vec<u8> = Vec::with_capacity(limit.min(data.len().saturating_mul(4)));
58
59 let mut acc: u32 = 0; // bits not yet consumed
60 let mut have: u32 = 0; // how many of them there are
61 let mut pos = 0;
62
63 loop {
64 while have < size && pos < data.len() {
65 match order {
66 BitOrder::Lsb => acc |= (data[pos] as u32) << have,
67 BitOrder::Msb => acc = (acc << 8) | data[pos] as u32,
68 }
69 have += 8;
70 pos += 1;
71 }
72 if have < size {
73 break; // the stream ran out without its end code
74 }
75 let mask = (1u32 << size) - 1;
76 let code = match order {
77 BitOrder::Lsb => {
78 let c = acc & mask;
79 acc >>= size;
80 c
81 }
82 BitOrder::Msb => {
83 let c = (acc >> (have - size)) & mask;
84 acc &= (1u32 << (have - size)) - 1;
85 c
86 }
87 } as usize;
88 have -= size;
89
90 if code == clear {
91 next = eoi + 1;
92 size = min as u32 + 1;
93 prev = None;
94 continue;
95 }
96 if code == eoi {
97 break;
98 }
99 let p = match prev {
100 None => {
101 if code >= clear {
102 return Err(err!(
103 "An LZW stream opens with code {}, which is not a literal (below {}).",
104 code, clear;
105 Invalid, Input, Decode));
106 }
107 if out.len() >= limit {
108 break;
109 }
110 out.push(code as u8);
111 prev = Some(code);
112 continue;
113 }
114 Some(p) => p,
115 };
116 // The entry this code adds is the previous string and the first byte of this one, which
117 // for the code not yet in the table is the previous string's own first byte.
118 let head = if code < next {
119 first[code]
120 } else if code == next && next < TABLE {
121 first[p]
122 } else {
123 return Err(err!(
124 "An LZW code of {} arrived when the table held only {} entries.", code, next;
125 Invalid, Input, Decode));
126 };
127 if next < TABLE {
128 prefix[next] = p as u16;
129 suffix[next] = head;
130 first[next] = first[p];
131 length[next] = length[p] + 1;
132 next += 1;
133 }
134 let n = length[code] as usize;
135 let start = out.len();
136 if start + n > limit {
137 return Err(err!(
138 "An LZW stream expands past the {} bytes its image can hold.", limit;
139 Invalid, Input, Decode, Excessive));
140 }
141 out.resize(start + n, 0);
142 let mut c = code;
143 for i in (0..n).rev() {
144 out[start + i] = suffix[c];
145 c = prefix[c] as usize;
146 }
147 let widen = if early { next + 1 } else { next };
148 if widen >= (1usize << size) && size < MAX_BITS {
149 size += 1;
150 }
151 prev = Some(code);
152 }
153 Ok(out)
154}
155
156#[cfg(test)]
157mod tests {
158 use super::*;
159
160 /// Packs codes of the given widths the way the named order reads them.
161 fn pack(codes: &[(u32, u32)], order: BitOrder) -> Vec<u8> {
162 let mut out = Vec::new();
163 let mut acc: u64 = 0;
164 let mut have = 0u32;
165 for &(c, w) in codes {
166 match order {
167 BitOrder::Lsb => acc |= (c as u64) << have,
168 BitOrder::Msb => acc = (acc << w) | c as u64,
169 }
170 have += w;
171 while have >= 8 {
172 match order {
173 BitOrder::Lsb => {
174 out.push((acc & 0xff) as u8);
175 acc >>= 8;
176 }
177 BitOrder::Msb => {
178 out.push(((acc >> (have - 8)) & 0xff) as u8);
179 }
180 }
181 have -= 8;
182 }
183 }
184 if have > 0 {
185 match order {
186 BitOrder::Lsb => out.push(acc as u8),
187 BitOrder::Msb => out.push(((acc << (8 - have)) & 0xff) as u8),
188 }
189 }
190 out
191 }
192
193 #[test]
194 fn test_gif_style_stream_with_the_unknown_code_case_00() -> Outcome<()> {
195 // Literals 0..3, clear 4, eoi 5. "ABABABA" as 0 1 6 8 with A=0, B=1.
196 let codes = [(4, 3), (0, 3), (1, 3), (6, 3), (8, 4), (5, 4)];
197 let out = res!(decode(&pack(&codes, BitOrder::Lsb), 2, BitOrder::Lsb, false, 64));
198 assert_eq!(out, vec![0, 1, 0, 1, 0, 1, 0]);
199 Ok(())
200 }
201
202 #[test]
203 fn test_tiff_style_stream_widens_early_00() -> Outcome<()> {
204 // 8-bit literals, clear 256, eoi 257. Enough literals to fill the table to 511, at which
205 // point TIFF moves to ten bits one entry early.
206 let mut codes = vec![(256u32, 9u32)];
207 let mut want = Vec::new();
208 // Each literal after the first adds one entry: 258 + 253 = 511 after 254 literals, and
209 // with 511 next the code is ten bits wide, where GIF would wait for 512.
210 for i in 0..254u32 {
211 codes.push((i, 9));
212 want.push(i as u8);
213 }
214 codes.push((257, 10));
215 let out = res!(decode(&pack(&codes, BitOrder::Msb), 8, BitOrder::Msb, true, 4096));
216 assert_eq!(out, want);
217 Ok(())
218 }
219
220 #[test]
221 fn test_a_code_beyond_the_table_is_refused_00() {
222 let codes = [(4, 3), (0, 3), (7, 3)];
223 assert!(decode(&pack(&codes, BitOrder::Lsb), 2, BitOrder::Lsb, false, 64).is_err());
224 }
225}