eui_core/
qr_code.rs

1//! VAPP-162: the QrCode native's MATRIX (catalog/style.json `qrCode`). A
2//! faithful Rust port of Project Nayuki's QR Code generator library
3//! (https://www.nayuki.io/page/qr-code-generator-library, MIT licence,
4//! Copyright (c) Project Nayuki; the notice is in docs/third-party-licences.md
5//! and packages/exponential-ui/vendor/nayuki-qr/LICENSE.txt), mirroring the
6//! TS reference `src/qr-code.ts`: ONE byte-mode segment over the value's
7//! UTF-8 bytes, the smallest version 1–40 that fits, the given error
8//! correction level kept exact (no `boostEcl`), the mask with the lowest
9//! penalty. `fixtures/qr-code.json` locks every matrix bit.
10//!
11//! Copyright (c) Project Nayuki. MIT License: the full notice ships in
12//! packages/exponential-ui/vendor/nayuki-qr/LICENSE.txt and every client's NOTICES.
13
14use std::sync::LazyLock;
15
16use serde::{Deserialize, Serialize};
17
18use crate::generated::catalog as g;
19
20/// style.json `qrCode`: the painted geometry's constants.
21#[derive(Debug, Clone, Deserialize)]
22#[serde(rename_all = "camelCase")]
23pub struct QrCodeSpec {
24    pub quiet_zone: f64,
25    pub label_gap: f64,
26    pub max_value_bytes: usize,
27}
28
29pub static QR_CODE: LazyLock<QrCodeSpec> = LazyLock::new(|| {
30    let style: serde_json::Value = serde_json::from_str(g::STYLE_JSON).expect("style.json");
31    serde_json::from_value(style["qrCode"].clone()).expect("style.json qrCode")
32});
33
34/// The error correction level (catalog enum): anything else is `M`.
35#[derive(Debug, Clone, Copy, PartialEq, Eq, Default, Serialize, Deserialize)]
36#[serde(from = "String")]
37pub enum QrLevel {
38    L,
39    #[default]
40    M,
41    Q,
42    H,
43}
44
45impl From<String> for QrLevel {
46    fn from(s: String) -> Self {
47        Self::parse(&s)
48    }
49}
50
51impl QrLevel {
52    pub fn parse(s: &str) -> Self {
53        match s {
54            "L" => Self::L,
55            "Q" => Self::Q,
56            "H" => Self::H,
57            _ => Self::M,
58        }
59    }
60
61    fn ordinal(self) -> usize {
62        match self {
63            Self::L => 0,
64            Self::M => 1,
65            Self::Q => 2,
66            Self::H => 3,
67        }
68    }
69
70    /// The two format bits the spec gives each level (L 1, M 0, Q 3, H 2).
71    fn format_bits(self) -> u32 {
72        match self {
73            Self::L => 1,
74            Self::M => 0,
75            Self::Q => 3,
76            Self::H => 2,
77        }
78    }
79}
80
81/// `size` rows of `size` characters: '1' = dark, '0' = light; no quiet zone.
82#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
83pub struct QrMatrix {
84    /// Modules per side (21 + 4 × (version − 1)).
85    pub size: usize,
86    pub version: usize,
87    /// The mask pattern chosen (0..7).
88    pub mask: u8,
89    pub rows: Vec<String>,
90}
91
92impl QrMatrix {
93    /// Whether the module at column `x`, row `y` is dark.
94    pub fn dark(&self, x: usize, y: usize) -> bool {
95        self.rows.get(y).and_then(|r| r.as_bytes().get(x)).is_some_and(|b| *b == b'1')
96    }
97}
98
99/// The painted geometry of a QrCode of edge `size` px: (module edge, quiet
100/// zone inset), both px, fractional (painters snap module EDGES).
101pub fn qr_layout(size: f64, modules: usize) -> (f64, f64) {
102    let q = QR_CODE.quiet_zone;
103    let module = size / (modules as f64 + 2.0 * q);
104    (module, module * q)
105}
106
107// Nayuki: ECC_CODEWORDS_PER_BLOCK / NUM_ERROR_CORRECTION_BLOCKS, indexed
108// [level ordinal L M Q H][version]; index 0 is padding.
109const ECC_CODEWORDS_PER_BLOCK: [[i16; 41]; 4] = [
110    [-1, 7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
111    [-1, 10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28],
112    [-1, 13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
113    [-1, 17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
114];
115const NUM_ERROR_CORRECTION_BLOCKS: [[i16; 41]; 4] = [
116    [-1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 9, 9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25],
117    [-1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 8, 9, 9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49],
118    [-1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 8, 8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68],
119    [-1, 1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81],
120];
121
122const PENALTY_N1: i32 = 3;
123const PENALTY_N2: i32 = 3;
124const PENALTY_N3: i32 = 40;
125const PENALTY_N4: i32 = 10;
126
127/// Raw data modules of a version (all modules minus the function patterns).
128fn num_raw_data_modules(ver: usize) -> usize {
129    let mut result = (16 * ver + 128) * ver + 64;
130    if ver >= 2 {
131        let num_align = ver / 7 + 2;
132        result -= (25 * num_align - 10) * num_align - 55;
133        if ver >= 7 {
134            result -= 36;
135        }
136    }
137    result
138}
139
140fn ecc_per_block(ver: usize, level: QrLevel) -> usize {
141    ECC_CODEWORDS_PER_BLOCK[level.ordinal()][ver] as usize
142}
143
144fn num_blocks(ver: usize, level: QrLevel) -> usize {
145    NUM_ERROR_CORRECTION_BLOCKS[level.ordinal()][ver] as usize
146}
147
148fn num_data_codewords(ver: usize, level: QrLevel) -> usize {
149    num_raw_data_modules(ver) / 8 - ecc_per_block(ver, level) * num_blocks(ver, level)
150}
151
152/// Byte mode's character-count field width per version band.
153fn byte_count_bits(ver: usize) -> usize {
154    if ver < 10 { 8 } else { 16 }
155}
156
157// --- Reed–Solomon over GF(2^8 / 0x11D) --------------------------------------
158
159fn rs_multiply(x: u8, y: u8) -> u8 {
160    let mut z: u32 = 0;
161    for i in (0..8).rev() {
162        z = (z << 1) ^ ((z >> 7) * 0x11d);
163        z ^= ((y as u32 >> i) & 1) * x as u32;
164    }
165    (z & 0xff) as u8
166}
167
168fn rs_divisor(degree: usize) -> Vec<u8> {
169    let mut result = vec![0u8; degree - 1];
170    result.push(1);
171    let mut root: u8 = 1;
172    for _ in 0..degree {
173        for j in 0..result.len() {
174            result[j] = rs_multiply(result[j], root);
175            if j + 1 < result.len() {
176                result[j] ^= result[j + 1];
177            }
178        }
179        root = rs_multiply(root, 0x02);
180    }
181    result
182}
183
184fn rs_remainder(data: &[u8], divisor: &[u8]) -> Vec<u8> {
185    let mut result = vec![0u8; divisor.len()];
186    for &b in data {
187        let factor = b ^ result.remove(0);
188        result.push(0);
189        for (r, &coef) in result.iter_mut().zip(divisor) {
190            *r ^= rs_multiply(coef, factor);
191        }
192    }
193    result
194}
195
196// --- The symbol ---------------------------------------------------------------
197
198struct Symbol {
199    version: usize,
200    level: QrLevel,
201    size: usize,
202    modules: Vec<Vec<bool>>,
203    is_function: Vec<Vec<bool>>,
204}
205
206impl Symbol {
207    fn new(version: usize, level: QrLevel) -> Self {
208        let size = version * 4 + 17;
209        Self { version, level, size, modules: vec![vec![false; size]; size], is_function: vec![vec![false; size]; size] }
210    }
211
212    fn set_function(&mut self, x: usize, y: usize, dark: bool) {
213        self.modules[y][x] = dark;
214        self.is_function[y][x] = true;
215    }
216
217    fn draw_function_patterns(&mut self) {
218        for i in 0..self.size {
219            self.set_function(6, i, i % 2 == 0);
220            self.set_function(i, 6, i % 2 == 0);
221        }
222        let s = self.size as i32;
223        self.draw_finder(3, 3);
224        self.draw_finder(s - 4, 3);
225        self.draw_finder(3, s - 4);
226        let align = self.alignment_positions();
227        let n = align.len();
228        for i in 0..n {
229            for j in 0..n {
230                if !((i == 0 && j == 0) || (i == 0 && j == n - 1) || (i == n - 1 && j == 0)) {
231                    self.draw_alignment(align[i], align[j]);
232                }
233            }
234        }
235        self.draw_format_bits(0); // dummy, overwritten after the mask is chosen
236        self.draw_version();
237    }
238
239    fn draw_format_bits(&mut self, mask: u8) {
240        let data = (self.level.format_bits() << 3) | mask as u32;
241        let mut rem = data;
242        for _ in 0..10 {
243            rem = (rem << 1) ^ ((rem >> 9) * 0x537);
244        }
245        let bits = ((data << 10) | rem) ^ 0x5412;
246        let bit = |i: u32| (bits >> i) & 1 != 0;
247        for i in 0..=5 {
248            self.set_function(8, i as usize, bit(i));
249        }
250        self.set_function(8, 7, bit(6));
251        self.set_function(8, 8, bit(7));
252        self.set_function(7, 8, bit(8));
253        for i in 9..15 {
254            self.set_function(14 - i as usize, 8, bit(i));
255        }
256        let size = self.size;
257        for i in 0..8 {
258            self.set_function(size - 1 - i as usize, 8, bit(i));
259        }
260        for i in 8..15 {
261            self.set_function(8, size - 15 + i as usize, bit(i));
262        }
263        self.set_function(8, size - 8, true); // always dark
264    }
265
266    fn draw_version(&mut self) {
267        if self.version < 7 {
268            return;
269        }
270        let mut rem = self.version as u32;
271        for _ in 0..12 {
272            rem = (rem << 1) ^ ((rem >> 11) * 0x1f25);
273        }
274        let bits = ((self.version as u32) << 12) | rem;
275        for i in 0..18usize {
276            let dark = (bits >> i) & 1 != 0;
277            let a = self.size - 11 + i % 3;
278            let b = i / 3;
279            self.set_function(a, b, dark);
280            self.set_function(b, a, dark);
281        }
282    }
283
284    fn draw_finder(&mut self, x: i32, y: i32) {
285        let s = self.size as i32;
286        for dy in -4i32..=4 {
287            for dx in -4i32..=4 {
288                let dist = dx.abs().max(dy.abs());
289                let (xx, yy) = (x + dx, y + dy);
290                if (0..s).contains(&xx) && (0..s).contains(&yy) {
291                    self.set_function(xx as usize, yy as usize, dist != 2 && dist != 4);
292                }
293            }
294        }
295    }
296
297    fn draw_alignment(&mut self, x: usize, y: usize) {
298        for dy in -2i32..=2 {
299            for dx in -2i32..=2 {
300                self.set_function((x as i32 + dx) as usize, (y as i32 + dy) as usize, dx.abs().max(dy.abs()) != 1);
301            }
302        }
303    }
304
305    fn alignment_positions(&self) -> Vec<usize> {
306        if self.version == 1 {
307            return Vec::new();
308        }
309        let num_align = self.version / 7 + 2;
310        let step = (self.version * 8 + num_align * 3 + 5) / (num_align * 4 - 4) * 2;
311        let mut result = vec![6usize];
312        let mut pos = self.size - 7;
313        while result.len() < num_align {
314            result.insert(1, pos);
315            pos -= step;
316        }
317        result
318    }
319
320    fn add_ecc_and_interleave(&self, data: &[u8]) -> Vec<u8> {
321        let n_blocks = num_blocks(self.version, self.level);
322        let block_ecc_len = ecc_per_block(self.version, self.level);
323        let raw_codewords = num_raw_data_modules(self.version) / 8;
324        let num_short_blocks = n_blocks - raw_codewords % n_blocks;
325        let short_block_len = raw_codewords / n_blocks;
326        let divisor = rs_divisor(block_ecc_len);
327        let mut blocks: Vec<Vec<u8>> = Vec::with_capacity(n_blocks);
328        let mut k = 0;
329        for i in 0..n_blocks {
330            let len = short_block_len - block_ecc_len + usize::from(i >= num_short_blocks);
331            let mut dat = data[k..(k + len).min(data.len())].to_vec();
332            k += dat.len();
333            let ecc = rs_remainder(&dat, &divisor);
334            if i < num_short_blocks {
335                dat.push(0);
336            }
337            dat.extend(ecc);
338            blocks.push(dat);
339        }
340        let mut result = Vec::with_capacity(raw_codewords);
341        for i in 0..blocks[0].len() {
342            for (j, block) in blocks.iter().enumerate() {
343                if i != short_block_len - block_ecc_len || j >= num_short_blocks {
344                    result.push(block[i]);
345                }
346            }
347        }
348        result
349    }
350
351    fn draw_codewords(&mut self, data: &[u8]) {
352        let mut i = 0usize;
353        let mut right = self.size as i32 - 1;
354        while right >= 1 {
355            if right == 6 {
356                right = 5;
357            }
358            for vert in 0..self.size {
359                for j in 0..2 {
360                    let x = (right - j) as usize;
361                    let upward = (right + 1) & 2 == 0;
362                    let y = if upward { self.size - 1 - vert } else { vert };
363                    if !self.is_function[y][x] && i < data.len() * 8 {
364                        self.modules[y][x] = (data[i >> 3] >> (7 - (i & 7))) & 1 != 0;
365                        i += 1;
366                    }
367                }
368            }
369            right -= 2;
370        }
371    }
372
373    fn apply_mask(&mut self, mask: u8) {
374        for y in 0..self.size {
375            for x in 0..self.size {
376                let invert = match mask {
377                    0 => (x + y) % 2 == 0,
378                    1 => y % 2 == 0,
379                    2 => x % 3 == 0,
380                    3 => (x + y) % 3 == 0,
381                    4 => (x / 3 + y / 2) % 2 == 0,
382                    5 => (x * y) % 2 + (x * y) % 3 == 0,
383                    6 => ((x * y) % 2 + (x * y) % 3) % 2 == 0,
384                    _ => ((x + y) % 2 + (x * y) % 3) % 2 == 0,
385                };
386                if !self.is_function[y][x] && invert {
387                    self.modules[y][x] = !self.modules[y][x];
388                }
389            }
390        }
391    }
392
393    fn penalty_score(&self) -> i32 {
394        let mut result = 0i32;
395        let size = self.size;
396        for horizontal in [true, false] {
397            for a in 0..size {
398                let mut run_color = false;
399                let mut run = 0i32;
400                let mut history = [0i32; 7];
401                for b in 0..size {
402                    let c = if horizontal { self.modules[a][b] } else { self.modules[b][a] };
403                    if c == run_color {
404                        run += 1;
405                        if run == 5 {
406                            result += PENALTY_N1;
407                        } else if run > 5 {
408                            result += 1;
409                        }
410                    } else {
411                        self.finder_penalty_add_history(run, &mut history);
412                        if !run_color {
413                            result += self.finder_penalty_count_patterns(&history) * PENALTY_N3;
414                        }
415                        run_color = c;
416                        run = 1;
417                    }
418                }
419                result += self.finder_penalty_terminate_and_count(run_color, run, &mut history) * PENALTY_N3;
420            }
421        }
422        for y in 0..size - 1 {
423            for x in 0..size - 1 {
424                let color = self.modules[y][x];
425                if color == self.modules[y][x + 1] && color == self.modules[y + 1][x] && color == self.modules[y + 1][x + 1] {
426                    result += PENALTY_N2;
427                }
428            }
429        }
430        let dark: i32 = self.modules.iter().map(|row| row.iter().filter(|c| **c).count() as i32).sum();
431        let total = (size * size) as i32;
432        // ceil(|dark·20 − total·10| / total) − 1, in integers
433        let num = (dark * 20 - total * 10).abs();
434        let k = (num + total - 1) / total - 1;
435        result += k * PENALTY_N4;
436        result
437    }
438
439    fn finder_penalty_count_patterns(&self, h: &[i32; 7]) -> i32 {
440        let n = h[1];
441        let core = n > 0 && h[2] == n && h[3] == n * 3 && h[4] == n && h[5] == n;
442        i32::from(core && h[0] >= n * 4 && h[6] >= n) + i32::from(core && h[6] >= n * 4 && h[0] >= n)
443    }
444
445    fn finder_penalty_terminate_and_count(&self, current_color: bool, mut current_len: i32, h: &mut [i32; 7]) -> i32 {
446        if current_color {
447            self.finder_penalty_add_history(current_len, h);
448            current_len = 0;
449        }
450        current_len += self.size as i32;
451        self.finder_penalty_add_history(current_len, h);
452        self.finder_penalty_count_patterns(h)
453    }
454
455    fn finder_penalty_add_history(&self, mut current_len: i32, h: &mut [i32; 7]) {
456        if h[0] == 0 {
457            current_len += self.size as i32;
458        }
459        h.copy_within(0..6, 1);
460        h[0] = current_len;
461    }
462}
463
464/// The data codewords of one byte segment at `version` (header, data,
465/// terminator, byte padding, the 0xEC/0x11 pad bytes).
466fn data_codewords(bytes: &[u8], version: usize, level: QrLevel) -> Vec<u8> {
467    let mut bits: Vec<u8> = Vec::new();
468    let append = |bits: &mut Vec<u8>, val: u32, len: usize| {
469        for i in (0..len).rev() {
470            bits.push(((val >> i) & 1) as u8);
471        }
472    };
473    append(&mut bits, 0x4, 4);
474    append(&mut bits, bytes.len() as u32, byte_count_bits(version));
475    for &b in bytes {
476        append(&mut bits, b as u32, 8);
477    }
478    let capacity_bits = num_data_codewords(version, level) * 8;
479    let term = 4.min(capacity_bits - bits.len());
480    append(&mut bits, 0, term);
481    let pad = (8 - bits.len() % 8) % 8;
482    append(&mut bits, 0, pad);
483    let mut pad_byte = 0xecu32;
484    while bits.len() < capacity_bits {
485        append(&mut bits, pad_byte, 8);
486        pad_byte ^= 0xec ^ 0x11;
487    }
488    let mut out = vec![0u8; bits.len() / 8];
489    for (i, b) in bits.iter().enumerate() {
490        out[i >> 3] |= b << (7 - (i & 7));
491    }
492    out
493}
494
495/// The smallest version whose data capacity holds `byte_len` bytes at `level`.
496pub fn qr_version(byte_len: usize, level: QrLevel) -> Option<usize> {
497    (1..=40).find(|&version| {
498        let used = 4 + byte_count_bits(version) + byte_len * 8;
499        byte_len < (1usize << byte_count_bits(version)) && used <= num_data_codewords(version, level) * 8
500    })
501}
502
503/// The QR matrix of `value` (UTF-8, byte mode) at `level`; `None` for an
504/// empty value or one too long for version 40 at that level.
505pub fn qr_matrix(value: &str, level: QrLevel) -> Option<QrMatrix> {
506    if value.is_empty() {
507        return None;
508    }
509    let bytes = value.as_bytes();
510    let version = qr_version(bytes.len(), level)?;
511    let mut sym = Symbol::new(version, level);
512    sym.draw_function_patterns();
513    let codewords = sym.add_ecc_and_interleave(&data_codewords(bytes, version, level));
514    sym.draw_codewords(&codewords);
515    let mut mask = 0u8;
516    let mut min_penalty = i32::MAX;
517    for i in 0..8u8 {
518        sym.apply_mask(i);
519        sym.draw_format_bits(i);
520        let penalty = sym.penalty_score();
521        if penalty < min_penalty {
522            mask = i;
523            min_penalty = penalty;
524        }
525        sym.apply_mask(i); // XOR undoes it
526    }
527    sym.apply_mask(mask);
528    sym.draw_format_bits(mask);
529    let rows = sym.modules.iter().map(|row| row.iter().map(|d| if *d { '1' } else { '0' }).collect()).collect();
530    Some(QrMatrix { size: sym.size, version, mask, rows })
531}
eui_core/qr_code.rs

eui_core/
qr_code.rs
