Skip to content

armgit / macro

Public Imported from GitHub
0

Macro is a unified workspace for teams: email, chat, docs, tasks, agents, calls, and CRM — @-linked together with shared AI memory.

17.2 KB
Raw Blame
//! `CCITTFaxDecode`: Group 3 one- and two-dimensional and Group 4 fax
//! data (ITU-T T.4 and T.6) to 1-bit rows.
//!
//! Lines are kept as their changing elements (where the color changes,
//! starting white), as the two-dimensional codes are relative to the
//! previous line's.

use crate::error::{AiError, Result};
use std::sync::OnceLock;

/// The decoding parameters.
pub(super) struct Params {
    /// `K`: below zero Group 4, zero Group 3 1-D, above zero mixed.
    pub(super) k: i64,
    pub(super) end_of_line: bool,
    pub(super) byte_align: bool,
    pub(super) columns: usize,
    /// Rows to read (`0`: until the data ends).
    pub(super) rows: usize,
    pub(super) end_of_block: bool,
    pub(super) black_is_1: bool,
}

/// End of line: eleven zeros and a one.
const EOL: u32 = 1;

/// A two-dimensional mode.
#[derive(Clone, Copy, PartialEq, Eq)]
enum Mode {
    Pass,
    Horizontal,
    Vertical(i8),
}

/// Codes: (bits, length, value).
type Code = (u16, u8, u16);

const WHITE: [Code; 104] = [
    (0b00110101, 8, 0),
    (0b000111, 6, 1),
    (0b0111, 4, 2),
    (0b1000, 4, 3),
    (0b1011, 4, 4),
    (0b1100, 4, 5),
    (0b1110, 4, 6),
    (0b1111, 4, 7),
    (0b10011, 5, 8),
    (0b10100, 5, 9),
    (0b00111, 5, 10),
    (0b01000, 5, 11),
    (0b001000, 6, 12),
    (0b000011, 6, 13),
    (0b110100, 6, 14),
    (0b110101, 6, 15),
    (0b101010, 6, 16),
    (0b101011, 6, 17),
    (0b0100111, 7, 18),
    (0b0001100, 7, 19),
    (0b0001000, 7, 20),
    (0b0010111, 7, 21),
    (0b0000011, 7, 22),
    (0b0000100, 7, 23),
    (0b0101000, 7, 24),
    (0b0101011, 7, 25),
    (0b0010011, 7, 26),
    (0b0100100, 7, 27),
    (0b0011000, 7, 28),
    (0b00000010, 8, 29),
    (0b00000011, 8, 30),
    (0b00011010, 8, 31),
    (0b00011011, 8, 32),
    (0b00010010, 8, 33),
    (0b00010011, 8, 34),
    (0b00010100, 8, 35),
    (0b00010101, 8, 36),
    (0b00010110, 8, 37),
    (0b00010111, 8, 38),
    (0b00101000, 8, 39),
    (0b00101001, 8, 40),
    (0b00101010, 8, 41),
    (0b00101011, 8, 42),
    (0b00101100, 8, 43),
    (0b00101101, 8, 44),
    (0b00000100, 8, 45),
    (0b00000101, 8, 46),
    (0b00001010, 8, 47),
    (0b00001011, 8, 48),
    (0b01010010, 8, 49),
    (0b01010011, 8, 50),
    (0b01010100, 8, 51),
    (0b01010101, 8, 52),
    (0b00100100, 8, 53),
    (0b00100101, 8, 54),
    (0b01011000, 8, 55),
    (0b01011001, 8, 56),
    (0b01011010, 8, 57),
    (0b01011011, 8, 58),
    (0b01001010, 8, 59),
    (0b01001011, 8, 60),
    (0b00110010, 8, 61),
    (0b00110011, 8, 62),
    (0b00110100, 8, 63),
    (0b11011, 5, 64),
    (0b10010, 5, 128),
    (0b010111, 6, 192),
    (0b0110111, 7, 256),
    (0b00110110, 8, 320),
    (0b00110111, 8, 384),
    (0b01100100, 8, 448),
    (0b01100101, 8, 512),
    (0b01101000, 8, 576),
    (0b01100111, 8, 640),
    (0b011001100, 9, 704),
    (0b011001101, 9, 768),
    (0b011010010, 9, 832),
    (0b011010011, 9, 896),
    (0b011010100, 9, 960),
    (0b011010101, 9, 1024),
    (0b011010110, 9, 1088),
    (0b011010111, 9, 1152),
    (0b011011000, 9, 1216),
    (0b011011001, 9, 1280),
    (0b011011010, 9, 1344),
    (0b011011011, 9, 1408),
    (0b010011000, 9, 1472),
    (0b010011001, 9, 1536),
    (0b010011010, 9, 1600),
    (0b011000, 6, 1664),
    (0b010011011, 9, 1728),
    (0b00000001000, 11, 1792),
    (0b00000001100, 11, 1856),
    (0b00000001101, 11, 1920),
    (0b000000010010, 12, 1984),
    (0b000000010011, 12, 2048),
    (0b000000010100, 12, 2112),
    (0b000000010101, 12, 2176),
    (0b000000010110, 12, 2240),
    (0b000000010111, 12, 2304),
    (0b000000011100, 12, 2368),
    (0b000000011101, 12, 2432),
    (0b000000011110, 12, 2496),
    (0b000000011111, 12, 2560),
];

const BLACK: [Code; 104] = [
    (0b0000110111, 10, 0),
    (0b010, 3, 1),
    (0b11, 2, 2),
    (0b10, 2, 3),
    (0b011, 3, 4),
    (0b0011, 4, 5),
    (0b0010, 4, 6),
    (0b00011, 5, 7),
    (0b000101, 6, 8),
    (0b000100, 6, 9),
    (0b0000100, 7, 10),
    (0b0000101, 7, 11),
    (0b0000111, 7, 12),
    (0b00000100, 8, 13),
    (0b00000111, 8, 14),
    (0b000011000, 9, 15),
    (0b0000010111, 10, 16),
    (0b0000011000, 10, 17),
    (0b0000001000, 10, 18),
    (0b00001100111, 11, 19),
    (0b00001101000, 11, 20),
    (0b00001101100, 11, 21),
    (0b00000110111, 11, 22),
    (0b00000101000, 11, 23),
    (0b00000010111, 11, 24),
    (0b00000011000, 11, 25),
    (0b000011001010, 12, 26),
    (0b000011001011, 12, 27),
    (0b000011001100, 12, 28),
    (0b000011001101, 12, 29),
    (0b000001101000, 12, 30),
    (0b000001101001, 12, 31),
    (0b000001101010, 12, 32),
    (0b000001101011, 12, 33),
    (0b000011010010, 12, 34),
    (0b000011010011, 12, 35),
    (0b000011010100, 12, 36),
    (0b000011010101, 12, 37),
    (0b000011010110, 12, 38),
    (0b000011010111, 12, 39),
    (0b000001101100, 12, 40),
    (0b000001101101, 12, 41),
    (0b000011011010, 12, 42),
    (0b000011011011, 12, 43),
    (0b000001010100, 12, 44),
    (0b000001010101, 12, 45),
    (0b000001010110, 12, 46),
    (0b000001010111, 12, 47),
    (0b000001100100, 12, 48),
    (0b000001100101, 12, 49),
    (0b000001010010, 12, 50),
    (0b000001010011, 12, 51),
    (0b000000100100, 12, 52),
    (0b000000110111, 12, 53),
    (0b000000111000, 12, 54),
    (0b000000100111, 12, 55),
    (0b000000101000, 12, 56),
    (0b000001011000, 12, 57),
    (0b000001011001, 12, 58),
    (0b000000101011, 12, 59),
    (0b000000101100, 12, 60),
    (0b000001011010, 12, 61),
    (0b000001100110, 12, 62),
    (0b000001100111, 12, 63),
    (0b0000001111, 10, 64),
    (0b000011001000, 12, 128),
    (0b000011001001, 12, 192),
    (0b000001011011, 12, 256),
    (0b000000110011, 12, 320),
    (0b000000110100, 12, 384),
    (0b000000110101, 12, 448),
    (0b0000001101100, 13, 512),
    (0b0000001101101, 13, 576),
    (0b0000001001010, 13, 640),
    (0b0000001001011, 13, 704),
    (0b0000001001100, 13, 768),
    (0b0000001001101, 13, 832),
    (0b0000001110010, 13, 896),
    (0b0000001110011, 13, 960),
    (0b0000001110100, 13, 1024),
    (0b0000001110101, 13, 1088),
    (0b0000001110110, 13, 1152),
    (0b0000001110111, 13, 1216),
    (0b0000001010010, 13, 1280),
    (0b0000001010011, 13, 1344),
    (0b0000001010100, 13, 1408),
    (0b0000001010101, 13, 1472),
    (0b0000001011010, 13, 1536),
    (0b0000001011011, 13, 1600),
    (0b0000001100100, 13, 1664),
    (0b0000001100101, 13, 1728),
    (0b00000001000, 11, 1792),
    (0b00000001100, 11, 1856),
    (0b00000001101, 11, 1920),
    (0b000000010010, 12, 1984),
    (0b000000010011, 12, 2048),
    (0b000000010100, 12, 2112),
    (0b000000010101, 12, 2176),
    (0b000000010110, 12, 2240),
    (0b000000010111, 12, 2304),
    (0b000000011100, 12, 2368),
    (0b000000011101, 12, 2432),
    (0b000000011110, 12, 2496),
    (0b000000011111, 12, 2560),
];

/// Bits a run table is indexed by (the longest code).
const RUN_BITS: u32 = 13;

/// A lookup by the next 13 bits: (code length, run); length 0 is no code.
fn table(codes: &[Code]) -> Vec<(u8, u16)> {
    let mut t = vec![(0u8, 0u16); 1 << RUN_BITS];
    for &(bits, len, run) in codes {
        let shift = RUN_BITS - u32::from(len);
        let start = usize::from(bits) << shift;
        t[start..start + (1 << shift)].fill((len, run));
    }
    t
}

fn white_table() -> &'static [(u8, u16)] {
    static T: OnceLock<Vec<(u8, u16)>> = OnceLock::new();
    T.get_or_init(|| table(&WHITE))
}

fn black_table() -> &'static [(u8, u16)] {
    static T: OnceLock<Vec<(u8, u16)>> = OnceLock::new();
    T.get_or_init(|| table(&BLACK))
}

/// Reads bits, most significant first; zeros past the end.
struct Reader<'a> {
    data: &'a [u8],
    at: usize,
}

impl Reader<'_> {
    fn peek(&self, n: u32) -> u32 {
        let mut v = 0u32;
        for i in 0..n as usize {
            let bit = self
                .data
                .get((self.at + i) / 8)
                .map_or(0, |b| (b >> (7 - (self.at + i) % 8)) & 1);
            v = (v << 1) | u32::from(bit);
        }
        v
    }

    fn skip(&mut self, n: u32) {
        self.at += n as usize;
    }

    fn done(&self) -> bool {
        self.at >= self.data.len() * 8
    }

    fn align(&mut self) {
        self.at = self.at.div_ceil(8) * 8;
    }

    /// Skips an end of line if one is next (after fill zeros when
    /// `fill`); whether one was.
    fn eol(&mut self, fill: bool) -> bool {
        let start = self.at;
        if fill {
            while self.peek(12) == 0 && !self.done() {
                self.skip(1);
            }
        }
        if self.peek(12) == EOL {
            self.skip(12);
            true
        } else {
            self.at = start;
            false
        }
    }

    /// Moves to the next end of line; whether there is one.
    fn resync(&mut self) -> bool {
        while !self.done() {
            if self.peek(12) == EOL {
                return true;
            }
            self.skip(1);
        }
        false
    }

    /// A run's length: makeup codes then a terminating code.
    fn run(&mut self, black: bool, columns: usize) -> Option<usize> {
        let table = if black { black_table() } else { white_table() };
        let mut total = 0usize;
        loop {
            if self.done() {
                return None;
            }
            let (len, run) = table[self.peek(RUN_BITS) as usize];
            if len == 0 {
                return None;
            }
            self.skip(u32::from(len));
            total += usize::from(run);
            if run < 64 {
                return Some(total);
            }
            if total > columns + 2560 {
                return None;
            }
        }
    }

    fn mode(&mut self) -> Option<Mode> {
        let bits = self.peek(7);
        let (len, mode) = if bits >> 6 == 1 {
            (1, Mode::Vertical(0))
        } else if bits >> 4 == 0b011 {
            (3, Mode::Vertical(1))
        } else if bits >> 4 == 0b010 {
            (3, Mode::Vertical(-1))
        } else if bits >> 4 == 0b001 {
            (3, Mode::Horizontal)
        } else if bits >> 3 == 0b0001 {
            (4, Mode::Pass)
        } else if bits >> 1 == 0b000011 {
            (6, Mode::Vertical(2))
        } else if bits >> 1 == 0b000010 {
            (6, Mode::Vertical(-2))
        } else if bits == 0b0000011 {
            (7, Mode::Vertical(3))
        } else if bits == 0b0000010 {
            (7, Mode::Vertical(-3))
        } else {
            // An extension, an end of line, or damage.
            return None;
        };
        self.skip(len);
        Some(mode)
    }
}

/// The line being decoded, as changing elements: `changes[i]` ends run `i`
/// (white runs at even `i`).
struct Line {
    changes: Vec<usize>,
    /// The run being written.
    at: usize,
    columns: usize,
}

impl Line {
    fn start(&mut self) {
        self.changes.clear();
        self.changes.push(0);
        self.at = 0;
    }

    fn end(&self) -> usize {
        self.changes[self.at]
    }

    /// Extends the runs to `a1`, starting a run when the color changes.
    fn add(&mut self, a1: usize, black: bool) {
        if a1 > self.end() {
            let a1 = a1.min(self.columns);
            if (self.at & 1 == 1) != black {
                self.at += 1;
                if self.changes.len() <= self.at {
                    self.changes.push(0);
                }
            }
            self.changes[self.at] = a1;
        }
    }

    /// Like [`Line::add`], also moving back when `a1` is left of the end.
    fn add_back(&mut self, a1: i64, black: bool) {
        let a1 = usize::try_from(a1).unwrap_or(0);
        if a1 > self.end() {
            self.add(a1, black);
        } else if a1 < self.end() {
            while self.at > 0 && a1 < self.changes[self.at - 1] {
                self.at -= 1;
            }
            self.changes[self.at] = a1;
        }
    }

    /// The finished line's changes (through `at`), ending at `columns`.
    fn changes(&self) -> &[usize] {
        &self.changes[..=self.at]
    }
}

/// Decodes fax data to rows of `columns` 1-bit pixels padded to whole
/// bytes (0 for black unless `BlackIs1`); the rows read.
pub(super) fn decode(data: &[u8], p: &Params, max_rows: usize) -> Result<(usize, Vec<u8>)> {
    let columns = p.columns;
    if columns == 0 || columns > super::MAX_SIDE as usize {
        return Err(AiError::corrupt("CCITT: bad Columns"));
    }
    let mut out = Vec::new();
    let mut reader = Reader { data, at: 0 };
    let mut line = Line {
        changes: vec![columns],
        at: 0,
        columns,
    };
    let mut reference: Vec<usize> = Vec::new();
    let mut rows = 0;
    // A leading end of line, and the first line's tag.
    reader.eol(true);
    let mut two_d = p.k < 0;
    if p.k > 0 {
        two_d = reader.peek(1) == 0;
        reader.skip(1);
    }
    let limit = if p.rows > 0 {
        p.rows.min(max_rows)
    } else {
        max_rows
    };
    while rows < limit && !reader.done() {
        if p.byte_align && p.k < 0 {
            reader.align();
        }
        let ok = if two_d {
            reference.clear();
            reference.extend_from_slice(line.changes());
            reference.retain(|&c| c < columns);
            reference.extend([columns, columns]);
            decode_2d(&mut reader, &mut line, &reference)
        } else {
            decode_1d(&mut reader, &mut line)
        };
        if !ok {
            // Damage, or the end of the data. With end-of-line codes, the
            // line is finished in white and decoding resumes at the next
            // one; otherwise the rows read are kept.
            if !p.end_of_line || !reader.resync() {
                break;
            }
            line.add(columns, false);
        }
        emit(&line, columns, p.black_is_1, &mut out);
        rows += 1;
        // An end of line (after fill zeros) may follow; an end of block (two
        // or six of them in a row) ends the data. Byte-aligned Group 3 lines
        // pad up to their end of line (which then ends on a byte boundary)
        // or, without one, up to the next byte.
        let mut got_eol = reader.eol(true);
        if !got_eol && p.byte_align && p.k >= 0 {
            reader.align();
            got_eol = reader.eol(true);
        }
        if got_eol && p.end_of_block {
            let save = reader.at;
            if p.k > 0 {
                reader.skip(1);
            }
            if reader.eol(false) {
                break;
            }
            reader.at = save;
        }
        if p.k > 0 {
            two_d = reader.peek(1) == 0;
            reader.skip(1);
        }
    }
    Ok((rows, out))
}

fn decode_1d(reader: &mut Reader<'_>, line: &mut Line) -> bool {
    line.start();
    let mut black = false;
    while line.end() < line.columns {
        let Some(run) = reader.run(black, line.columns) else {
            return false;
        };
        line.add(line.end() + run, black);
        black = !black;
    }
    true
}

fn decode_2d(reader: &mut Reader<'_>, line: &mut Line, reference: &[usize]) -> bool {
    let columns = line.columns;
    let r = |i: usize| reference.get(i).copied().unwrap_or(columns);
    line.start();
    let mut black = false;
    let mut b = 0usize;
    while line.end() < columns {
        let Some(mode) = reader.mode() else {
            return false;
        };
        match mode {
            Mode::Pass => {
                line.add(r(b + 1), black);
                if r(b + 1) < columns {
                    b += 2;
                }
            }
            Mode::Horizontal => {
                let first = reader.run(black, columns);
                let second = reader.run(!black, columns);
                let (Some(first), Some(second)) = (first, second) else {
                    return false;
                };
                line.add(line.end() + first, black);
                if line.end() < columns {
                    line.add(line.end() + second, !black);
                }
                while r(b) <= line.end() && r(b) < columns {
                    b += 2;
                }
            }
            Mode::Vertical(d) => {
                let a1 = r(b) as i64 + i64::from(d);
                if d >= 0 {
                    line.add(usize::try_from(a1).unwrap_or(0), black);
                } else {
                    line.add_back(a1, black);
                }
                black = !black;
                if line.end() < columns {
                    if d < 0 && b > 0 {
                        b -= 1;
                    } else {
                        b += 1;
                    }
                    while r(b) <= line.end() && r(b) < columns {
                        b += 2;
                    }
                }
            }
        }
    }
    true
}

/// Appends a line's pixels: white runs then black, alternating.
fn emit(line: &Line, columns: usize, black_is_1: bool, out: &mut Vec<u8>) {
    let start = out.len();
    let row_bytes = columns.div_ceil(8);
    // White pixels' bit.
    let white = !black_is_1;
    out.resize(start + row_bytes, if white { 0xff } else { 0 });
    let row = &mut out[start..];
    let mut x = 0;
    for (i, &end) in line.changes().iter().enumerate() {
        let end = end.min(columns);
        if i % 2 == 1 {
            for px in x..end {
                let bit = 0x80 >> (px % 8);
                if white {
                    row[px / 8] &= !bit;
                } else {
                    row[px / 8] |= bit;
                }
            }
        }
        x = x.max(end);
    }
    // Padding bits past the last column are left as written.
}