Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_graphics/src/ccitt.rs

13.6 KiB, 1 run

created by r1870400018:75656, 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 CCITT fax codings TIFF carries: Modified Huffman, T.4 (Group 3) and T.6 (Group 4).
2//!
3//! A black and white scan of a letter is the case this exists for. Scanners and fax software store
4//! a bilevel page in one of these three far more often than in anything else, because a page of
5//! print is mostly long runs of white and the codes were designed around exactly that.
6//!
7//! All three describe a row as runs of alternating colour starting with white. Modified Huffman
8//! codes each row by itself, with the run lengths in two fixed prefix codes, one for white and one
9//! for black. T.4 adds an end-of-line code before each row and, optionally, rows coded against the
10//! row above (two-dimensional coding), where each change of colour is said as an offset from the
11//! nearest matching change above it. T.6 codes every row that way, with no end-of-line codes.
12//!
13//! The output is one bit a pixel, eight to a byte with the leftmost pixel in the high bit, each row
14//! padded to a whole byte, a set bit meaning black -- TIFF's `WhiteIsZero`, the photometric these
15//! files nearly always declare.
16//!
17//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
18//! Anthropic Claude
19
20use oxedyne_fe2o3_core::prelude::*;
21
22/// Which of the three codings a strip is in, with T.4's options.
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub enum Coding {
25 Mh, // TIFF compression 2: rows byte aligned, no end-of-line codes
26 T4 {
27 two_d: bool, // T4Options bit 0: rows may be coded against the row above
28 aligned: bool, // T4Options bit 2: fill bits put each end-of-line on a byte end
29 },
30 T6, // TIFF compression 4
31}
32
33// (code, length in bits, run)
34type Code = (u16, u8, u16);
35
36const WHITE: &[Code] = &[
37 (0b00110101, 8, 0), (0b000111, 6, 1), (0b0111, 4, 2), (0b1000, 4, 3),
38 (0b1011, 4, 4), (0b1100, 4, 5), (0b1110, 4, 6), (0b1111, 4, 7),
39 (0b10011, 5, 8), (0b10100, 5, 9), (0b00111, 5, 10), (0b01000, 5, 11),
40 (0b001000, 6, 12), (0b000011, 6, 13), (0b110100, 6, 14), (0b110101, 6, 15),
41 (0b101010, 6, 16), (0b101011, 6, 17), (0b0100111, 7, 18), (0b0001100, 7, 19),
42 (0b0001000, 7, 20), (0b0010111, 7, 21), (0b0000011, 7, 22), (0b0000100, 7, 23),
43 (0b0101000, 7, 24), (0b0101011, 7, 25), (0b0010011, 7, 26), (0b0100100, 7, 27),
44 (0b0011000, 7, 28), (0b00000010, 8, 29), (0b00000011, 8, 30), (0b00011010, 8, 31),
45 (0b00011011, 8, 32), (0b00010010, 8, 33), (0b00010011, 8, 34), (0b00010100, 8, 35),
46 (0b00010101, 8, 36), (0b00010110, 8, 37), (0b00010111, 8, 38), (0b00101000, 8, 39),
47 (0b00101001, 8, 40), (0b00101010, 8, 41), (0b00101011, 8, 42), (0b00101100, 8, 43),
48 (0b00101101, 8, 44), (0b00000100, 8, 45), (0b00000101, 8, 46), (0b00001010, 8, 47),
49 (0b00001011, 8, 48), (0b01010010, 8, 49), (0b01010011, 8, 50), (0b01010100, 8, 51),
50 (0b01010101, 8, 52), (0b00100100, 8, 53), (0b00100101, 8, 54), (0b01011000, 8, 55),
51 (0b01011001, 8, 56), (0b01011010, 8, 57), (0b01011011, 8, 58), (0b01001010, 8, 59),
52 (0b01001011, 8, 60), (0b00110010, 8, 61), (0b00110011, 8, 62), (0b00110100, 8, 63),
53 // Make-up codes.
54 (0b11011, 5, 64), (0b10010, 5, 128), (0b010111, 6, 192), (0b0110111, 7, 256),
55 (0b00110110, 8, 320), (0b00110111, 8, 384), (0b01100100, 8, 448), (0b01100101, 8, 512),
56 (0b01101000, 8, 576), (0b01100111, 8, 640), (0b011001100, 9, 704), (0b011001101, 9, 768),
57 (0b011010010, 9, 832), (0b011010011, 9, 896), (0b011010100, 9, 960), (0b011010101, 9, 1024),
58 (0b011010110, 9, 1088), (0b011010111, 9, 1152), (0b011011000, 9, 1216), (0b011011001, 9, 1280),
59 (0b011011010, 9, 1344), (0b011011011, 9, 1408), (0b010011000, 9, 1472), (0b010011001, 9, 1536),
60 (0b010011010, 9, 1600), (0b011000, 6, 1664), (0b010011011, 9, 1728),
61];
62
63const BLACK: &[Code] = &[
64 (0b0000110111, 10, 0), (0b010, 3, 1), (0b11, 2, 2), (0b10, 2, 3),
65 (0b011, 3, 4), (0b0011, 4, 5), (0b0010, 4, 6), (0b00011, 5, 7),
66 (0b000101, 6, 8), (0b000100, 6, 9), (0b0000100, 7, 10), (0b0000101, 7, 11),
67 (0b0000111, 7, 12), (0b00000100, 8, 13), (0b00000111, 8, 14), (0b000011000, 9, 15),
68 (0b0000010111, 10, 16), (0b0000011000, 10, 17), (0b0000001000, 10, 18), (0b00001100111, 11, 19),
69 (0b00001101000, 11, 20), (0b00001101100, 11, 21), (0b00000110111, 11, 22), (0b00000101000, 11, 23),
70 (0b00000010111, 11, 24), (0b00000011000, 11, 25), (0b000011001010, 12, 26), (0b000011001011, 12, 27),
71 (0b000011001100, 12, 28), (0b000011001101, 12, 29), (0b000001101000, 12, 30), (0b000001101001, 12, 31),
72 (0b000001101010, 12, 32), (0b000001101011, 12, 33), (0b000011010010, 12, 34), (0b000011010011, 12, 35),
73 (0b000011010100, 12, 36), (0b000011010101, 12, 37), (0b000011010110, 12, 38), (0b000011010111, 12, 39),
74 (0b000001101100, 12, 40), (0b000001101101, 12, 41), (0b000011011010, 12, 42), (0b000011011011, 12, 43),
75 (0b000001010100, 12, 44), (0b000001010101, 12, 45), (0b000001010110, 12, 46), (0b000001010111, 12, 47),
76 (0b000001100100, 12, 48), (0b000001100101, 12, 49), (0b000001010010, 12, 50), (0b000001010011, 12, 51),
77 (0b000000100100, 12, 52), (0b000000110111, 12, 53), (0b000000111000, 12, 54), (0b000000100111, 12, 55),
78 (0b000000101000, 12, 56), (0b000001011000, 12, 57), (0b000001011001, 12, 58), (0b000000101011, 12, 59),
79 (0b000000101100, 12, 60), (0b000001011010, 12, 61), (0b000001100110, 12, 62), (0b000001100111, 12, 63),
80 // Make-up codes.
81 (0b0000001111, 10, 64), (0b000011001000, 12, 128), (0b000011001001, 12, 192),
82 (0b000001011011, 12, 256), (0b000000110011, 12, 320), (0b000000110100, 12, 384),
83 (0b000000110101, 12, 448), (0b0000001101100, 13, 512), (0b0000001101101, 13, 576),
84 (0b0000001001010, 13, 640), (0b0000001001011, 13, 704), (0b0000001001100, 13, 768),
85 (0b0000001001101, 13, 832), (0b0000001110010, 13, 896), (0b0000001110011, 13, 960),
86 (0b0000001110100, 13, 1024), (0b0000001110101, 13, 1088), (0b0000001110110, 13, 1152),
87 (0b0000001110111, 13, 1216), (0b0000001010010, 13, 1280), (0b0000001010011, 13, 1344),
88 (0b0000001010100, 13, 1408), (0b0000001010101, 13, 1472), (0b0000001011010, 13, 1536),
89 (0b0000001011011, 13, 1600), (0b0000001100100, 13, 1664), (0b0000001100101, 13, 1728),
90];
91
92// The make-up codes past 1728, which white and black share.
93const EXTENDED: &[Code] = &[
94 (0b00000001000, 11, 1792), (0b00000001100, 11, 1856), (0b00000001101, 11, 1920),
95 (0b000000010010, 12, 1984), (0b000000010011, 12, 2048), (0b000000010100, 12, 2112),
96 (0b000000010101, 12, 2176), (0b000000010110, 12, 2240), (0b000000010111, 12, 2304),
97 (0b000000011100, 12, 2368), (0b000000011101, 12, 2432), (0b000000011110, 12, 2496),
98 (0b000000011111, 12, 2560),
99];
100
101const PEEK: u32 = 13; // the longest code, in bits
102const EOL: u16 = 0xffff; // a run value marking the end-of-line code in a table
103
104/// A table indexed by the next thirteen bits, giving the code's length and its run.
105struct Table {
106 slots: Vec<(u8, u16)>, // length 0 means no code begins with these bits
107}
108
109impl Table {
110
111 fn build(codes: &[Code]) -> Outcome<Self> {
112 let mut slots = vec![(0u8, 0u16); 1 << PEEK];
113 let all = codes.iter().chain(EXTENDED.iter()).chain(std::iter::once(&(1u16, 12u8, EOL)));
114 for &(code, len, run) in all {
115 let span = 1usize << (PEEK - len as u32);
116 let base = (code as usize) << (PEEK - len as u32);
117 for s in &mut slots[base..base + span] {
118 if s.0 != 0 {
119 return Err(err!(
120 "The fax code for run {} collides with another; the table is wrong.", run;
121 Bug));
122 }
123 *s = (len, run);
124 }
125 }
126 Ok(Self { slots })
127 }
128}
129
130/// Reads bits most significant first, from any position.
131struct Bits<'a> {
132 data: &'a [u8],
133 pos: usize, // in bits
134}
135
136impl<'a> Bits<'a> {
137
138 fn bit(&self, at: usize) -> u32 {
139 match self.data.get(at >> 3) {
140 Some(b) => ((b >> (7 - (at & 7))) & 1) as u32,
141 None => 0,
142 }
143 }
144
145 fn peek(&self, n: u32) -> u32 {
146 let mut v = 0;
147 for i in 0..n as usize {
148 v = (v << 1) | self.bit(self.pos + i);
149 }
150 v
151 }
152
153 fn left(&self) -> usize {
154 (self.data.len() * 8).saturating_sub(self.pos)
155 }
156
157 fn align(&mut self) {
158 self.pos = (self.pos + 7) & !7;
159 }
160
161 /// Steps over an end-of-line code, with any fill zeros before it, if one is next.
162 fn eol(&mut self) -> bool {
163 let mut z = 0;
164 while z < self.left() && self.bit(self.pos + z) == 0 {
165 z += 1;
166 }
167 if z >= 11 && z < self.left() {
168 self.pos += z + 1;
169 return true;
170 }
171 false
172 }
173}
174
175/// Reads one run of the given colour: any make-up codes, then a terminating one.
176fn run(b: &mut Bits, t: &Table, white: bool) -> Outcome<usize> {
177 let mut total = 0usize;
178 loop {
179 if b.left() == 0 {
180 return Err(err!(
181 "A fax strip ends in the middle of a {} run.", if white { "white" } else { "black" };
182 Invalid, Input, Decode));
183 }
184 let (len, v) = t.slots[b.peek(PEEK) as usize];
185 if len == 0 || v == EOL {
186 return Err(err!(
187 "A fax strip holds no valid {} run code at bit {}.",
188 if white { "white" } else { "black" }, b.pos;
189 Invalid, Input, Decode));
190 }
191 b.pos += len as usize;
192 total += v as usize;
193 if v < 64 {
194 return Ok(total);
195 }
196 }
197}
198
199// Two-dimensional modes, with the vertical offset where one applies.
200enum Mode {
201 Pass,
202 Horizontal,
203 Vertical(isize),
204}
205
206fn mode(b: &mut Bits) -> Outcome<Mode> {
207 let v = b.peek(7);
208 let (len, m) = if v >> 6 == 1 {
209 (1, Mode::Vertical(0))
210 } else if v >> 4 == 0b011 {
211 (3, Mode::Vertical(1))
212 } else if v >> 4 == 0b010 {
213 (3, Mode::Vertical(-1))
214 } else if v >> 4 == 0b001 {
215 (3, Mode::Horizontal)
216 } else if v >> 3 == 0b0001 {
217 (4, Mode::Pass)
218 } else if v >> 1 == 0b000011 {
219 (6, Mode::Vertical(2))
220 } else if v >> 1 == 0b000010 {
221 (6, Mode::Vertical(-2))
222 } else if v == 0b0000011 {
223 (7, Mode::Vertical(3))
224 } else if v == 0b0000010 {
225 (7, Mode::Vertical(-3))
226 } else {
227 return Err(err!(
228 "A fax strip holds no two-dimensional mode code at bit {} (uncompressed mode is not \
229 read).", b.pos;
230 Invalid, Input, Decode, Unimplemented));
231 };
232 b.pos += len;
233 Ok(m)
234}
235
236/// Decodes a row coded by itself, as changes of colour.
237fn row_1d(b: &mut Bits, wt: &Table, bt: &Table, w: usize, out: &mut Vec<usize>) -> Outcome<()> {
238 out.clear();
239 let mut x = 0usize;
240 let mut white = true;
241 while x < w {
242 let r = res!(run(b, if white { wt } else { bt }, white));
243 x = (x + r).min(w);
244 out.push(x);
245 white = !white;
246 }
247 Ok(())
248}
249
250/// Decodes a row coded against the one above, `refs`, as changes of colour.
251fn row_2d(b: &mut Bits, wt: &Table, bt: &Table, w: usize, refs: &[usize], out: &mut Vec<usize>)
252 -> Outcome<()>
253{
254 out.clear();
255 let mut a0: isize = -1;
256 let mut white = true;
257 let mut i = 0usize; // where the search for b1 resumes
258 while a0 < w as isize {
259 // b1 is the first change above, right of a0, to the colour opposite a0's; changes at even
260 // indices are to black and at odd ones to white.
261 let want = if white { 0 } else { 1 };
262 while i < refs.len() && (refs[i] as isize <= a0 || i % 2 != want) {
263 i += 1;
264 }
265 let b1 = refs.get(i).copied().unwrap_or(w) as isize;
266 let b2 = refs.get(i + 1).copied().unwrap_or(w) as isize;
267 match res!(mode(b)) {
268 Mode::Pass => {
269 a0 = b2;
270 }
271 Mode::Horizontal => {
272 let start = a0.max(0) as usize;
273 let r1 = res!(run(b, if white { wt } else { bt }, white));
274 let r2 = res!(run(b, if white { bt } else { wt }, !white));
275 let a1 = (start + r1).min(w);
276 let a2 = (a1 + r2).min(w);
277 out.push(a1);
278 out.push(a2);
279 a0 = a2 as isize;
280 }
281 Mode::Vertical(d) => {
282 let a1 = b1 + d;
283 if a1 < 0 || a1 < a0 || a1 > w as isize {
284 return Err(err!(
285 "A fax row's vertical code puts a change at {}, outside the row of {} or \
286 behind {}.", a1, w, a0;
287 Invalid, Input, Decode));
288 }
289 out.push(a1 as usize);
290 a0 = a1;
291 white = !white;
292 }
293 }
294 i = i.saturating_sub(1);
295 }
296 Ok(())
297}
298
299/// Paints a row's changes of colour as packed bits, black set.
300fn paint(changes: &[usize], w: usize, row: &mut [u8]) {
301 let mut x = 0usize;
302 let mut black = false;
303 for &c in changes {
304 let c = c.min(w);
305 if black {
306 for p in x..c {
307 row[p >> 3] |= 0x80 >> (p & 7);
308 }
309 }
310 x = c;
311 black = !black;
312 }
313 if black {
314 for p in x..w {
315 row[p >> 3] |= 0x80 >> (p & 7);
316 }
317 }
318}
319
320/// Decodes a strip of `h` rows of `w` pixels.
321pub fn decode(data: &[u8], w: usize, h: usize, coding: Coding) -> Outcome<Vec<u8>> {
322 let wt = res!(Table::build(WHITE));
323 let bt = res!(Table::build(BLACK));
324 let stride = (w + 7) / 8;
325 let mut out = vec![0u8; stride * h];
326 let mut b = Bits { data, pos: 0 };
327 let mut refs: Vec<usize> = Vec::new(); // an imaginary white row above the first
328 let mut cur: Vec<usize> = Vec::new();
329 for y in 0..h {
330 match coding {
331 Coding::Mh => {
332 res!(row_1d(&mut b, &wt, &bt, w, &mut cur));
333 b.align();
334 }
335 Coding::T4 { two_d, aligned: _ } => {
336 // Fill bits before an end-of-line are zeros, which `eol` steps over whether or
337 // not the option says they are there; a row with no end-of-line before it is
338 // read from where the last one ended.
339 b.eol();
340 let one_d = if two_d {
341 let tag = b.bit(b.pos);
342 b.pos += 1;
343 tag == 1
344 } else {
345 true
346 };
347 if one_d {
348 res!(row_1d(&mut b, &wt, &bt, w, &mut cur));
349 } else {
350 res!(row_2d(&mut b, &wt, &bt, w, &refs, &mut cur));
351 }
352 }
353 Coding::T6 => {
354 res!(row_2d(&mut b, &wt, &bt, w, &refs, &mut cur));
355 }
356 }
357 paint(&cur, w, &mut out[y * stride..(y + 1) * stride]);
358 std::mem::swap(&mut refs, &mut cur);
359 }
360 Ok(out)
361}
362
363#[cfg(test)]
364mod tests {
365 use super::*;
366
367 /// The Kraft sum of a complete prefix code is one; with the EOL and the shared make-up codes
368 /// beside them neither table is complete, but both must be prefix-free, which `build` checks.
369 #[test]
370 fn test_the_code_tables_are_prefix_free_00() -> Outcome<()> {
371 let _ = res!(Table::build(WHITE));
372 let _ = res!(Table::build(BLACK));
373 assert_eq!(WHITE.len(), 64 + 27);
374 assert_eq!(BLACK.len(), 64 + 27);
375 for (i, c) in WHITE.iter().enumerate().take(64) {
376 assert_eq!(c.2 as usize, i);
377 }
378 for (i, c) in BLACK.iter().enumerate().take(64) {
379 assert_eq!(c.2 as usize, i);
380 }
381 Ok(())
382 }
383}