//! QR Code encoder — byte mode, EC level L, versions 1..=40. //! //! `no_std` + heap-free: the module matrix and all work buffers live in //! `.bss` statics, so the encoder is safe to run from the fault/panic //! path. Real hardware has no serial console, so the crash log is drawn //! on the framebuffer as a scannable QR code instead of a frozen text //! band. //! //! Tables follow ISO/IEC 18004 (block structure Table 9 level L, //! alignment positions, version info), cross-verified bit-for-bit //! against segno (`tools/qrcheck` + `tools/qrcheck.py`). /// Largest supported version (177 modules; v40-L byte capacity 2953). pub const MAX_VERSION: usize = 40; /// Modules per side of the largest supported QR. pub const MAX_MODULES: usize = 177; /// v40-L byte-mode capacity — the hard input limit. pub const MAX_BYTES: usize = 2953; const MATRIX_LEN: usize = MAX_MODULES * MAX_MODULES; /// EC-L block structure per version: /// `(ec_codewords_per_block, &[(num_blocks, data_codewords_per_block)])`. const ECC_L: &[(u8, &[(u8, u16)])] = &[ // v1 (7, &[(1, 19)]), // v2 (10, &[(1, 34)]), // v3 (15, &[(1, 55)]), // v4 (20, &[(1, 80)]), // v5 (26, &[(1, 108)]), // v6 (18, &[(2, 68)]), // v7 (20, &[(2, 78)]), // v8 (24, &[(2, 97)]), // v9 (30, &[(2, 116)]), // v10 (18, &[(2, 68), (2, 69)]), // v11 (20, &[(4, 81)]), // v12 (24, &[(2, 92), (2, 93)]), // v13 (26, &[(4, 107)]), // v14 (30, &[(3, 115), (1, 116)]), // v15 (22, &[(5, 87), (1, 88)]), // v16 (24, &[(5, 98), (1, 99)]), // v17 (28, &[(1, 107), (5, 108)]), // v18 (30, &[(5, 120), (1, 121)]), // v19 (28, &[(3, 113), (4, 114)]), // v20 (28, &[(3, 107), (5, 108)]), // v21 (28, &[(4, 116), (4, 117)]), // v22 (28, &[(2, 111), (7, 112)]), // v23 (30, &[(4, 121), (5, 122)]), // v24 (30, &[(6, 117), (4, 118)]), // v25 (26, &[(8, 106), (4, 107)]), // v26 (28, &[(10, 114), (2, 115)]), // v27 (30, &[(8, 122), (4, 123)]), // v28 (30, &[(3, 117), (10, 118)]), // v29 (30, &[(7, 116), (7, 117)]), // v30 (30, &[(5, 115), (10, 116)]), // v31 (30, &[(13, 115), (3, 116)]), // v32 (30, &[(17, 115)]), // v33 (30, &[(17, 115), (1, 116)]), // v34 (30, &[(13, 115), (6, 116)]), // v35 (30, &[(12, 121), (7, 122)]), // v36 (30, &[(6, 121), (14, 122)]), // v37 (30, &[(17, 122), (4, 123)]), // v38 (30, &[(4, 122), (18, 123)]), // v39 (30, &[(20, 117), (4, 118)]), // v40 (30, &[(19, 118), (6, 119)]), ]; /// Alignment-pattern centre coordinate sets per version (index = version-2; /// v1 has none). Patterns sit at every (r, c) pair from the set, minus the /// three corners that overlap the finder patterns. const ALIGNMENT_POS: &[&[u8]] = &[ // v2 &[6, 18], // v3 &[6, 22], // v4 &[6, 26], // v5 &[6, 30], // v6 &[6, 34], // v7 &[6, 22, 38], // v8 &[6, 24, 42], // v9 &[6, 26, 46], // v10 &[6, 28, 50], // v11 &[6, 30, 54], // v12 &[6, 32, 58], // v13 &[6, 34, 62], // v14 &[6, 26, 46, 66], // v15 &[6, 26, 48, 70], // v16 &[6, 26, 50, 74], // v17 &[6, 30, 54, 78], // v18 &[6, 30, 56, 82], // v19 &[6, 30, 58, 86], // v20 &[6, 34, 62, 90], // v21 &[6, 28, 50, 72, 94], // v22 &[6, 26, 50, 74, 98], // v23 &[6, 30, 54, 78, 102], // v24 &[6, 28, 54, 80, 106], // v25 &[6, 32, 58, 84, 110], // v26 &[6, 30, 58, 86, 114], // v27 &[6, 34, 62, 90, 118], // v28 &[6, 26, 50, 74, 98, 122], // v29 &[6, 30, 54, 78, 102, 126], // v30 &[6, 26, 52, 78, 104, 130], // v31 &[6, 30, 56, 82, 108, 134], // v32 &[6, 34, 60, 86, 112, 138], // v33 &[6, 30, 58, 86, 114, 142], // v34 &[6, 34, 62, 90, 118, 146], // v35 &[6, 30, 54, 78, 102, 126, 150], // v36 &[6, 24, 50, 76, 102, 128, 154], // v37 &[6, 28, 54, 80, 106, 132, 158], // v38 &[6, 32, 58, 84, 110, 136, 162], // v39 &[6, 26, 54, 82, 110, 138, 166], // v40 &[6, 30, 58, 86, 114, 142, 170], ]; /// Version info 18-bit BCH values (index = version-7, v7..v40). const VERSION_INFO: &[u32] = &[ 31892, 34236, 39577, 42195, 48118, 51042, 55367, 58893, 63784, 68472, 70749, 76311, 79154, 84390, 87683, 92361, 96236, 102084, 102881, 110507, 110734, 117786, 119615, 126325, 127568, 133589, 136944, 141498, 145311, 150283, 152622, 158308, 161089, 167017, ]; /// Working matrix: 0 = light, 1 = dark. Row-major, top-left origin. static mut MAT: [u8; MATRIX_LEN] = [0; MATRIX_LEN]; /// Function-module map: 1 = fixed pattern cell (never masked, skipped by the /// data zigzag), 0 = data cell. static mut FUNC: [u8; MATRIX_LEN] = [0; MATRIX_LEN]; /// Modules per side of the current matrix. static mut SIZE: usize = 0; /// Mask chosen by the most recent auto-mask encode. static mut LAST_MASK: usize = 0; /// Total codewords of the most recent encode (debug hook). static mut LAST_TOTAL: usize = 0; // GF(256) tables (primitive poly 0x11D), computed once on first encode. static mut GF_EXP: [u8; 512] = [0; 512]; static mut GF_LOG: [u8; 256] = [0; 256]; static mut GF_READY: bool = false; // Data codewords (max v40-L = 2956) and the final interleaved codeword // stream (max v40 total = 3706). static mut CW: [u8; 2956] = [0; 2956]; static mut FINAL_CW: [u8; 3706] = [0; 3706]; fn gf_init() { unsafe { if !GF_READY { let mut x: u8 = 1; for i in 0..255 { GF_EXP[i] = x; GF_LOG[x as usize] = i as u8; x = if x & 0x80 != 0 { (x << 1) ^ 0x1D } else { x << 1 }; } for i in 255..512 { GF_EXP[i] = GF_EXP[i - 255]; } GF_READY = true; } } } #[inline] fn gf_mul(a: u8, b: u8) -> u8 { if a == 0 || b == 0 { return 0; } unsafe { GF_EXP[GF_LOG[a as usize] as usize + GF_LOG[b as usize] as usize] } } /// Build the Reed-Solomon generator polynomial for `ec` EC codewords into /// `out[0..=ec]` (out[0] = leading coefficient, always 1). fn rs_generator(ec: usize, out: &mut [u8; 31]) { unsafe { out[0] = 1; let mut len = 1; for i in 0..ec { for j in (0..len).rev() { out[j + 1] ^= gf_mul(out[j], GF_EXP[i]); } len += 1; } } } /// Reed-Solomon encode: `out` (len `ec`) receives the EC codewords. fn rs_encode(data: &[u8], ec: usize, rs_gen: &[u8; 31], out: &mut [u8]) { for i in 0..ec { out[i] = 0; } for &b in data { let factor = b ^ out[0]; for i in 0..ec - 1 { out[i] = out[i + 1]; } out[ec - 1] = 0; if factor != 0 { for i in 0..ec { out[i] ^= gf_mul(rs_gen[i + 1], factor); } } } } /// Byte-mode data capacity of `version` (EC-L), including the 4-bit mode /// indicator and 8/16-bit character-count field, rounded down to whole bytes. fn byte_capacity(version: usize) -> usize { let (_, blocks) = ECC_L[version - 1]; let data_cw: usize = blocks.iter().map(|(n, d)| *n as usize * *d as usize).sum(); let count_bits = if version <= 9 { 8 } else { 16 }; (data_cw * 8 - 4 - count_bits) / 8 } /// Bit-packed writer over a byte buffer. struct BitWriter<'a> { buf: &'a mut [u8], bitpos: usize, } impl BitWriter<'_> { fn push(&mut self, value: u32, nbits: u8) { for i in (0..nbits).rev() { let bit = ((value >> i) & 1) as u8; let byte = self.bitpos / 8; if bit != 0 { self.buf[byte] |= 1 << (7 - (self.bitpos % 8)); } self.bitpos += 1; } } } /// Build the data codeword stream for `data` (mode 0100, byte count, pad to /// `data_cw` bytes with 0xEC/0x11). fn build_codewords(data: &[u8], data_cw: usize, version: usize) { unsafe { let cw = &mut *core::ptr::addr_of_mut!(CW); for i in 0..data_cw { cw[i] = 0; } let count_bits = if version <= 9 { 8 } else { 16 }; let mut w = BitWriter { buf: &mut cw[..data_cw], bitpos: 0 }; w.push(0b0100, 4); w.push(data.len() as u32, count_bits); for &b in data { w.push(b as u32, 8); } let capacity_bits = data_cw * 8; // Terminator: up to 4 zero bits while capacity allows. let mut term = 0; while w.bitpos < capacity_bits && term < 4 { w.push(0, 1); term += 1; } // Pad to a byte boundary, then 0xEC/0x11 alternating pad bytes. while !w.bitpos.is_multiple_of(8) && w.bitpos < capacity_bits { w.push(0, 1); } let mut pad: u8 = 0xEC; while w.bitpos < capacity_bits { w.push(pad as u32, 8); pad = if pad == 0xEC { 0x11 } else { 0xEC }; } } } fn n_modules(version: usize) -> usize { 17 + 4 * version } /// Mark a module as a function cell with value `val`. fn func_set(x: usize, y: usize, val: u8) { unsafe { let idx = y * SIZE + x; MAT[idx] = val; FUNC[idx] = 1; } } fn finder_cell(x: usize, y: usize, r: usize, c: usize) { let dark = r == 0 || r == 6 || c == 0 || c == 6 || ((2..=4).contains(&r) && (2..=4).contains(&c)); func_set(x + c, y + r, dark as u8); } fn draw_finders(n: usize) { // Top-left (0,0). for r in 0..7 { for c in 0..7 { finder_cell(0, 0, r, c); } } for c in 0..8 { func_set(c, 7, 0); // bottom separator } for r in 0..8 { func_set(7, r, 0); // right separator } // Top-right (n-7, 0). for r in 0..7 { for c in 0..7 { finder_cell(n - 7, 0, r, c); } } for c in 0..8 { func_set(n - 8 + c, 7, 0); // bottom separator } for r in 0..8 { func_set(n - 8, r, 0); // left separator } // Bottom-left (0, n-7). for r in 0..7 { for c in 0..7 { finder_cell(0, n - 7, r, c); } } for c in 0..8 { func_set(c, n - 8, 0); // top separator } for r in 0..8 { func_set(7, n - 8 + r, 0); // right separator } } fn draw_timing(n: usize) { for i in 8..=n - 9 { let dark = (i % 2 == 0) as u8; func_set(i, 6, dark); func_set(6, i, dark); } } fn draw_alignment(version: usize) { if version < 2 { return; } let coords = ALIGNMENT_POS[version - 2]; let last = *coords.last().unwrap() as usize; for &r in coords { for &c in coords { let (r, c) = (r as usize, c as usize); // Skip the three corners that overlap finder patterns. if (r == 6 && c == 6) || (r == 6 && c == last) || (r == last && c == 6) { continue; } for dr in 0..5 { for dc in 0..5 { let dark = dr == 0 || dr == 4 || dc == 0 || dc == 4 || (dr == 2 && dc == 2); func_set(c - 2 + dc, r - 2 + dr, dark as u8); } } } } } /// Mark the two format-info regions as function cells (values set later, /// after mask selection) so the data zigzag skips them. fn reserve_format(n: usize) { for i in 0..6 { func_set(8, i, 0); func_set(5 - i, 8, 0); } func_set(8, 7, 0); func_set(8, 8, 0); func_set(7, 8, 0); // Copy 2: top-right row 8 (bits 0..7), bottom-left col 8 (bits 8..14). for i in 0..8 { func_set(n - 1 - i, 8, 0); } for i in 0..7 { func_set(8, n - 7 + i, 0); } } /// Place the interleaved codewords in the data region (no mask yet). fn place_data(total_cw: usize, n: usize) { let mut bit_idx = 0usize; let mut up = true; let mut right = n - 1; while right >= 1 { if right == 6 { right = 5; } for vert in 0..n { let row = if up { n - 1 - vert } else { vert }; for j in 0..2 { let x = right - j; if unsafe { FUNC[row * SIZE + x] } == 0 && bit_idx < total_cw * 8 { let byte = unsafe { FINAL_CW[bit_idx / 8] }; let bit = (byte >> (7 - bit_idx % 8)) & 1; unsafe { MAT[row * SIZE + x] = bit }; bit_idx += 1; } } } up = !up; if right >= 2 { right -= 2; } else { break; } } debug_assert_eq!(bit_idx, total_cw * 8); } fn mask_bit(mask: usize, x: usize, y: usize) -> bool { match mask { 0 => (x + y).is_multiple_of(2), 1 => y.is_multiple_of(2), 2 => x.is_multiple_of(3), 3 => (x + y).is_multiple_of(3), 4 => (x / 3 + y / 2).is_multiple_of(2), 5 => (x * y) % 2 + (x * y) % 3 == 0, 6 => ((x * y) % 2 + (x * y) % 3).is_multiple_of(2), 7 => ((x + y) % 2 + (x * y) % 3).is_multiple_of(2), _ => false, } } /// Apply (XOR) a mask over the data cells only. fn apply_mask(mask: usize, n: usize) { for y in 0..n { for x in 0..n { if unsafe { FUNC[y * SIZE + x] } == 0 && mask_bit(mask, x, y) { unsafe { MAT[y * SIZE + x] ^= 1 }; } } } } /// BCH remainder over GF(2) (`rs_gen` must have its MSB set). fn bch_remainder(mut v: u32, rs_gen: u32) -> u32 { let gl = 32 - rs_gen.leading_zeros(); let mut vl = 32 - v.leading_zeros(); while vl >= gl { v ^= rs_gen << (vl - gl); vl = 32 - v.leading_zeros(); } v } /// 15-bit format info for EC level L and `mask`. fn format_info(mask: usize) -> u16 { let data = (0b01 << 3) | mask as u32; let rem = bch_remainder(data << 10, 0x537); (((data << 10) | rem) ^ 0x5412) as u16 } fn set_format(format: u16, n: usize) { let b = |i: usize| ((format >> i) & 1) as u8; // Copy 1: around the top-left finder. for i in 0..6 { func_set(8, i, b(i)); } func_set(8, 7, b(6)); func_set(8, 8, b(7)); func_set(7, 8, b(8)); for i in 0..6 { func_set(5 - i, 8, b(9 + i)); } // Copy 2: top-right row 8 (bits 0..7) + bottom-left col 8 (bits 8..14). for i in 0..8 { func_set(n - 1 - i, 8, b(i)); } for i in 0..7 { func_set(8, n - 7 + i, b(8 + i)); } } /// Mark the version-info cells as function (leaving MAT light) so the data /// placement skips them. Called before `place_data`; the actual version bits /// are written later by `write_version_info` (ISO: version info is added /// after data masking is chosen, and must not influence the penalty score). fn reserve_version(n: usize) { if n < 45 { return; // no version-info region below version 7 } for i in 0..18 { func_set(n - 11 + (i % 3), i / 3, 0); // upper right: (row i/3, col n-11+i%3) func_set(i / 3, n - 11 + (i % 3), 0); // lower left: (row n-11+i%3, col i/3) } } /// Write the 18-bit version info (v7..v40) into the reserved cells. fn write_version_info(version: usize, n: usize) { if version < 7 { return; } let v = VERSION_INFO[version - 7]; // Upper right 3x6 block: bit i at (row i/3, col n - 11 + i%3). // Lower left 6x3 block: bit i at (row n - 11 + i%3, col i/3). for i in 0..18 { let bit = ((v >> i) & 1) as u8; func_set(n - 11 + (i % 3), i / 3, bit); func_set(i / 3, n - 11 + (i % 3), bit); } } /// Count N3 penalty occurrences of the finder-like 1:1:3:1:1 core /// (1011101) in `seq`, following segno's `mask_scores` rules: an edge /// position (0 or n-7) always counts; otherwise the 4 modules before and /// after the core must each be entirely light (short windows near the /// edges are allowed). After a counted match the scan resumes at idx+7, /// after a rejected core at idx+4 (identical to segno's find() offsets). fn n3_count(seq: &[u8], n: usize) -> usize { const CORE: [u8; 7] = [1, 0, 1, 1, 1, 0, 1]; let mut count = 0usize; let mut idx = 0usize; while idx + 7 <= n { if seq[idx..idx + 7] != CORE { idx += 1; continue; } let after = idx + 7; let before_light = seq[idx.saturating_sub(4)..idx].iter().all(|&v| v == 0); let after_light = seq[after..(after + 4).min(n)].iter().all(|&v| v == 0); if idx == 0 || idx == n - 7 || before_light || after_light { count += 40; idx += 7; } else { idx += 4; } } count } /// Penalty score (rules N1-N4) of the current matrix, used for mask choice. fn penalty(n: usize) -> usize { let mut score = 0usize; // N1: runs of >= 5 same colour in rows and columns. for y in 0..n { let mut run = 1usize; let mut prev = unsafe { MAT[y * SIZE] }; for x in 1..n { let cur = unsafe { MAT[y * SIZE + x] }; if cur == prev { run += 1; } else { if run >= 5 { score += 3 + run - 5; } run = 1; prev = cur; } } if run >= 5 { score += 3 + run - 5; } } for x in 0..n { let mut run = 1usize; let mut prev = unsafe { MAT[x] }; for y in 1..n { let cur = unsafe { MAT[y * SIZE + x] }; if cur == prev { run += 1; } else { if run >= 5 { score += 3 + run - 5; } run = 1; prev = cur; } } if run >= 5 { score += 3 + run - 5; } } // N2: 2x2 blocks of identical colour. for y in 0..n - 1 { for x in 0..n - 1 { let a = unsafe { MAT[y * SIZE + x] }; if a == unsafe { MAT[y * SIZE + x + 1] } && a == unsafe { MAT[(y + 1) * SIZE + x] } && a == unsafe { MAT[(y + 1) * SIZE + x + 1] } { score += 3; } } } // N3: finder-like 1011101 core (1:1:3:1:1) preceded/followed by light // area. Mirrors segno's `mask_scores` exactly (edge positions count, // after a match the scan resumes 7 cells later, after a rejected core // 4 cells later), so the auto-mask choice matches the reference. let mut buf = [0u8; 177]; for y in 0..n { for x in 0..n { buf[x] = unsafe { MAT[y * SIZE + x] }; } score += n3_count(&buf[..n], n); } for x in 0..n { for y in 0..n { buf[y] = unsafe { MAT[y * SIZE + x] }; } score += n3_count(&buf[..n], n); } // N4: dark-module proportion. let mut dark = 0usize; for y in 0..n { for x in 0..n { dark += unsafe { MAT[y * SIZE + x] } as usize; } } let total = n * n; let percent = dark * 100 / total; let k = (percent as isize - 50).unsigned_abs() / 5; score += 10 * k; score } /// Encode `data` with a fixed version and mask (`None` = auto mask via /// penalty scoring). Reference/test hook; the kernel path uses `encode`. /// Returns 0 if `version` cannot hold `data` or `mask` is invalid. pub fn encode_at(data: &[u8], version: usize, mask: Option) -> usize { if !(1..=MAX_VERSION).contains(&version) || data.len() > byte_capacity(version) { return 0; } if let Some(m) = mask && m > 7 { return 0; } gf_init(); let (ec_per, blocks) = ECC_L[version - 1]; let data_cw: usize = blocks.iter().map(|(n, d)| *n as usize * *d as usize).sum(); let total_cw: usize = blocks .iter() .map(|(n, d)| *n as usize * (*d as usize + ec_per as usize)) .sum(); build_codewords(data, data_cw, version); // Expand the block structure into per-block offsets/lengths. let mut blk_off = [0usize; 32]; let mut blk_len = [0usize; 32]; let mut nblocks = 0usize; let mut off = 0usize; for &(nb, nd) in blocks { for _ in 0..nb { blk_off[nblocks] = off; blk_len[nblocks] = nd as usize; off += nd as usize; nblocks += 1; } } let mut rs_gen = [0u8; 31]; rs_generator(ec_per as usize, &mut rs_gen); unsafe { let cw = &*core::ptr::addr_of_mut!(CW); let final_cw = &mut *core::ptr::addr_of_mut!(FINAL_CW); // Interleave data codewords column-major over blocks. let max_data = *blk_len.iter().max().unwrap(); let mut k = 0usize; for i in 0..max_data { for b in 0..nblocks { if i < blk_len[b] { final_cw[k] = cw[blk_off[b] + i]; k += 1; } } } // Encode EC per block, interleave column-major. let mut ecs = [[0u8; 30]; 32]; for b in 0..nblocks { rs_encode( &cw[blk_off[b]..blk_off[b] + blk_len[b]], ec_per as usize, &rs_gen, &mut ecs[b][..ec_per as usize], ); } for i in 0..ec_per as usize { for b in 0..nblocks { final_cw[k] = ecs[b][i]; k += 1; } } debug_assert_eq!(k, total_cw); } let n = n_modules(version); unsafe { LAST_TOTAL = total_cw }; unsafe { SIZE = n; for i in 0..n * n { MAT[i] = 0; FUNC[i] = 0; } } draw_finders(n); draw_timing(n); draw_alignment(version); func_set(8, n - 8, 1); // dark module (row n-8, col 8) reserve_version(n); reserve_format(n); place_data(total_cw, n); if let Some(m) = mask { apply_mask(m, n); set_format(format_info(m), n); write_version_info(version, n); unsafe { LAST_MASK = m }; } else { // ISO/IEC 18004: format and version info are added *after* mask // selection (they depend on the mask), so the penalty must be // evaluated with those regions still light. let mut best_mask = 0usize; let mut best_score = usize::MAX; for m in 0..8 { apply_mask(m, n); let s = penalty(n); if s < best_score { best_score = s; best_mask = m; } // Un-mask for the next candidate. apply_mask(m, n); } apply_mask(best_mask, n); set_format(format_info(best_mask), n); write_version_info(version, n); unsafe { LAST_MASK = best_mask }; } version } /// Encode `data` (byte mode, EC-L): smallest fitting version, best mask. /// Returns the version used (1..=40) or 0 if `data` is too long. pub fn encode(data: &[u8]) -> usize { if data.is_empty() || data.len() > MAX_BYTES { return 0; } let mut version = 0; for v in 1..=MAX_VERSION { if byte_capacity(v) >= data.len() { version = v; break; } } if version == 0 { return 0; } encode_at(data, version, None) } /// Modules per side of the most recent successful encode (0 = none). pub fn size() -> usize { unsafe { SIZE } } /// Mask chosen by the most recent auto-mask encode (0..7; debug hook for /// the host-side cross-check tool). pub fn last_mask() -> usize { unsafe { LAST_MASK } } /// Final interleaved codeword stream (data + EC) of the most recent /// encode — debug hook for the host-side cross-check tool. pub fn codeword_stream() -> &'static [u8] { unsafe { &FINAL_CW[..LAST_TOTAL] } } /// Whether module `(x, y)` of the current matrix is dark. Valid for /// `x, y < size()`. pub fn module(x: usize, y: usize) -> bool { unsafe { MAT[y * SIZE + x] != 0 } }