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 | |
| 20 | use 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)] |
| 24 | pub 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) |
| 34 | type Code = (u16, u8, u16); |
| 35 | |
| 36 | const 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 | |
| 63 | const 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. |
| 93 | const 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 | |
| 101 | const PEEK: u32 = 13; // the longest code, in bits |
| 102 | const 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. |
| 105 | struct Table { |
| 106 | slots: Vec<(u8, u16)>, // length 0 means no code begins with these bits |
| 107 | } |
| 108 | |
| 109 | impl 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. |
| 131 | struct Bits<'a> { |
| 132 | data: &'a [u8], |
| 133 | pos: usize, // in bits |
| 134 | } |
| 135 | |
| 136 | impl<'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. |
| 176 | fn 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. |
| 200 | enum Mode { |
| 201 | Pass, |
| 202 | Horizontal, |
| 203 | Vertical(isize), |
| 204 | } |
| 205 | |
| 206 | fn 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. |
| 237 | fn 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. |
| 251 | fn 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. |
| 300 | fn 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. |
| 321 | pub 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)] |
| 364 | mod 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 | } |