anyd/codes/qr/
decode.rs

1//! QR decoding: [`BitMatrix`] → [`Symbol`].
2//!
3//! This is the *structural* decoder: it consumes a clean, already-sampled module
4//! grid (as produced by the encoder or an image-sampling front-end) and recovers the
5//! exact segments and [`QrMeta`], so the result re-encodes identically.
6
7use super::matrix::Canvas;
8use super::tables::{char_count_bits, ec_blocks, mode_from_indicator, remainder_bits};
9use super::{QrMeta, Version};
10use crate::error::{Error, Result};
11use crate::output::{BitMatrix, Encoding};
12use crate::segment::{Mode, Segment};
13use crate::symbol::{Symbol, SymbolMeta};
14use crate::symbology::Symbology;
15use crate::traits::Decode;
16
17/// QR Code structural decoder.
18#[derive(Debug, Default, Clone, Copy)]
19pub struct QrDecoder;
20
21impl QrDecoder {
22    /// A new decoder.
23    pub fn new() -> Self {
24        QrDecoder
25    }
26
27    /// Decode a sampled QR module grid into a [`Symbol`].
28    pub fn decode_matrix(&self, matrix: &BitMatrix) -> Result<Symbol> {
29        let version = version_from_size(matrix.width(), matrix.height())?;
30        let canvas = Canvas::from_matrix(version, matrix);
31        let (level, mask) = canvas
32            .read_format()
33            .ok_or_else(|| Error::undecodable("unreadable format information"))?;
34
35        // Read the masked data modules along the path, unmasking as we go.
36        let path = canvas.data_path();
37        let mut bits: Vec<bool> = Vec::with_capacity(path.len());
38        for &(x, y) in &path {
39            bits.push(canvas.get(x, y) ^ Canvas::mask_bit(mask, x, y));
40        }
41
42        let ecb = ec_blocks(version, level);
43        let total_cw = ecb.total_codewords();
44        // Pack to codewords, dropping trailing remainder bits.
45        if bits.len() < total_cw * 8 {
46            return Err(Error::undecodable("not enough data modules"));
47        }
48        let mut codewords = Vec::with_capacity(total_cw);
49        for i in 0..total_cw {
50            let mut byte = 0u8;
51            for k in 0..8 {
52                byte = (byte << 1) | bits[i * 8 + k] as u8;
53            }
54            codewords.push(byte);
55        }
56        let _ = remainder_bits(version); // remainder bits already excluded above
57
58        let data = deinterleave_and_correct(&codewords, &ecb)?;
59        let segments = parse_segments(&data, version)?;
60
61        let meta = QrMeta {
62            version,
63            ec_level: level,
64            mask,
65        };
66        Ok(Symbol::new(
67            Symbology::QrCode,
68            segments,
69            SymbolMeta::Qr(meta),
70        ))
71    }
72}
73
74impl Decode for QrDecoder {
75    fn decode(&self, encoding: &Encoding) -> Result<Symbol> {
76        match encoding {
77            Encoding::Matrix(m) => self.decode_matrix(m),
78            Encoding::Linear(_) => Err(Error::Unsupported {
79                what: "QR decode of a linear pattern",
80            }),
81        }
82    }
83}
84
85/// Derive the QR version from the grid dimensions.
86fn version_from_size(width: usize, height: usize) -> Result<Version> {
87    if width != height {
88        return Err(Error::undecodable("QR grid is not square"));
89    }
90    if width < 21 || !(width - 21).is_multiple_of(4) {
91        return Err(Error::undecodable("grid size is not a valid QR version"));
92    }
93    let v = ((width - 21) / 4 + 1) as u8;
94    Version::new(v).ok_or_else(|| Error::undecodable("grid size out of QR version range"))
95}
96
97/// De-interleave codewords back into blocks, RS-correct each, and concatenate the
98/// corrected data codewords in original block order.
99fn deinterleave_and_correct(codewords: &[u8], ecb: &super::tables::EcBlocks) -> Result<Vec<u8>> {
100    let total_blocks = ecb.total_blocks();
101    let block_sizes: Vec<usize> = (0..ecb.group1_blocks)
102        .map(|_| ecb.group1_data)
103        .chain((0..ecb.group2_blocks).map(|_| ecb.group2_data))
104        .collect();
105
106    let (interleaved_data, interleaved_ec) = codewords.split_at(ecb.total_data());
107
108    // De-interleave data codewords, column by column.
109    let mut block_data: Vec<Vec<u8>> = vec![Vec::new(); total_blocks];
110    let max_data = ecb.group1_data.max(ecb.group2_data);
111    let mut di = 0;
112    for col in 0..max_data {
113        for (bi, &bsize) in block_sizes.iter().enumerate() {
114            if col < bsize {
115                block_data[bi].push(interleaved_data[di]);
116                di += 1;
117            }
118        }
119    }
120
121    // De-interleave EC codewords.
122    let mut block_ec: Vec<Vec<u8>> = vec![Vec::new(); total_blocks];
123    let mut ei = 0;
124    for _col in 0..ecb.ec_per_block {
125        for ec in block_ec.iter_mut() {
126            ec.push(interleaved_ec[ei]);
127            ei += 1;
128        }
129    }
130
131    // Correct each block and gather corrected data codewords.
132    let mut out = Vec::with_capacity(ecb.total_data());
133    for bi in 0..total_blocks {
134        let mut full = block_data[bi].clone();
135        full.extend_from_slice(&block_ec[bi]);
136        let corrected =
137            super::gf::decode(&full, ecb.ec_per_block).ok_or(Error::ErrorCorrectionFailed)?;
138        out.extend_from_slice(&corrected[..block_sizes[bi]]);
139    }
140    Ok(out)
141}
142
143/// Read bits most-significant-first out of a codeword byte stream.
144struct BitReader<'a> {
145    bits: &'a [u8],
146    pos: usize,
147}
148
149impl<'a> BitReader<'a> {
150    fn new(bits: &'a [u8]) -> Self {
151        BitReader { bits, pos: 0 }
152    }
153
154    fn remaining(&self) -> usize {
155        self.bits.len() * 8 - self.pos
156    }
157
158    fn read(&mut self, n: usize) -> Option<u32> {
159        if self.remaining() < n {
160            return None;
161        }
162        let mut v = 0u32;
163        for _ in 0..n {
164            let byte = self.bits[self.pos / 8];
165            let bit = (byte >> (7 - self.pos % 8)) & 1;
166            v = (v << 1) | bit as u32;
167            self.pos += 1;
168        }
169        Some(v)
170    }
171}
172
173fn alnum_char(v: u32) -> Option<u8> {
174    let c = match v {
175        0..=9 => b'0' + v as u8,
176        10..=35 => b'A' + (v - 10) as u8,
177        36 => b' ',
178        37 => b'$',
179        38 => b'%',
180        39 => b'*',
181        40 => b'+',
182        41 => b'-',
183        42 => b'.',
184        43 => b'/',
185        44 => b':',
186        _ => return None,
187    };
188    Some(c)
189}
190
191fn kanji_bytes(v: u32) -> Option<(u8, u8)> {
192    let base = (v / 0xC0) << 8 | (v % 0xC0);
193    let code = if base < 0x1F00 {
194        base + 0x8140
195    } else {
196        base + 0xC140
197    };
198    Some(((code >> 8) as u8, (code & 0xFF) as u8))
199}
200
201/// Parse the corrected data codewords into segments, stopping at the terminator or
202/// when the remaining bits are all padding.
203fn parse_segments(data: &[u8], version: Version) -> Result<Vec<Segment>> {
204    let mut r = BitReader::new(data);
205    let mut segments = Vec::new();
206
207    while r.remaining() >= 4 {
208        let indicator = r.read(4).unwrap() as u8;
209        if indicator == 0 {
210            break; // terminator (or padding)
211        }
212        let mode = mode_from_indicator(indicator)
213            .ok_or_else(|| Error::undecodable("unknown QR mode indicator"))?;
214        match mode {
215            Mode::Eci(_) => {
216                let assignment = read_eci_assignment(&mut r)?;
217                segments.push(Segment::eci(assignment));
218            }
219            Mode::Numeric => {
220                let count = r.read(char_count_bits(version, &mode)).ok_or_else(trunc)? as usize;
221                let mut out = Vec::with_capacity(count);
222                let mut remaining = count;
223                while remaining >= 3 {
224                    let v = r.read(10).ok_or_else(trunc)?;
225                    out.extend_from_slice(format!("{v:03}").as_bytes());
226                    remaining -= 3;
227                }
228                if remaining == 2 {
229                    let v = r.read(7).ok_or_else(trunc)?;
230                    out.extend_from_slice(format!("{v:02}").as_bytes());
231                } else if remaining == 1 {
232                    let v = r.read(4).ok_or_else(trunc)?;
233                    out.push(b'0' + v as u8);
234                }
235                segments.push(Segment::numeric(out));
236            }
237            Mode::Alphanumeric => {
238                let count = r.read(char_count_bits(version, &mode)).ok_or_else(trunc)? as usize;
239                let mut out = Vec::with_capacity(count);
240                let mut remaining = count;
241                while remaining >= 2 {
242                    let v = r.read(11).ok_or_else(trunc)?;
243                    out.push(
244                        alnum_char(v / 45)
245                            .ok_or_else(|| Error::undecodable("bad alphanumeric value"))?,
246                    );
247                    out.push(
248                        alnum_char(v % 45)
249                            .ok_or_else(|| Error::undecodable("bad alphanumeric value"))?,
250                    );
251                    remaining -= 2;
252                }
253                if remaining == 1 {
254                    let v = r.read(6).ok_or_else(trunc)?;
255                    out.push(
256                        alnum_char(v)
257                            .ok_or_else(|| Error::undecodable("bad alphanumeric value"))?,
258                    );
259                }
260                segments.push(Segment::alphanumeric(out));
261            }
262            Mode::Byte => {
263                let count = r.read(char_count_bits(version, &mode)).ok_or_else(trunc)? as usize;
264                let mut out = Vec::with_capacity(count);
265                for _ in 0..count {
266                    out.push(r.read(8).ok_or_else(trunc)? as u8);
267                }
268                segments.push(Segment::byte(out));
269            }
270            Mode::Kanji => {
271                let count = r.read(char_count_bits(version, &mode)).ok_or_else(trunc)? as usize;
272                let mut out = Vec::with_capacity(count * 2);
273                for _ in 0..count {
274                    let v = r.read(13).ok_or_else(trunc)?;
275                    let (hi, lo) =
276                        kanji_bytes(v).ok_or_else(|| Error::undecodable("bad kanji value"))?;
277                    out.push(hi);
278                    out.push(lo);
279                }
280                segments.push(Segment::kanji(out));
281            }
282        }
283    }
284    Ok(segments)
285}
286
287fn read_eci_assignment(r: &mut BitReader<'_>) -> Result<u32> {
288    let first = r.read(8).ok_or_else(trunc)?;
289    if first & 0x80 == 0 {
290        Ok(first)
291    } else if first & 0xC0 == 0x80 {
292        let rest = r.read(8).ok_or_else(trunc)?;
293        Ok(((first & 0x3F) << 8) | rest)
294    } else if first & 0xE0 == 0xC0 {
295        let rest = r.read(16).ok_or_else(trunc)?;
296        Ok(((first & 0x1F) << 16) | rest)
297    } else {
298        Err(Error::undecodable("invalid ECI assignment"))
299    }
300}
301
302fn trunc() -> Error {
303    Error::undecodable("truncated QR data stream")
304}
anyd/codes/qr/decode.rs

anyd/codes/qr/
decode.rs
