From 9fde94d068f87b34e0bc6bfa48388d89bb54f1e4 Mon Sep 17 00:00:00 2001 From: salmonik Date: Mon, 3 Aug 2026 02:23:35 +0200 Subject: v0.5.8: heap-free QR encoder + crash-dump QR on framebuffer MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Real hardware has no serial console, so a kernel crash only leaves a frozen screen. Every dump_lines() report now also renders the crash text as a scannable QR below the white-on-red band (photograph the screen instead of relaying text). - rsnix/src/qr.rs: from-scratch no_std/no_alloc byte-mode QR encoder (EC-L, v1..v40, .bss statics only — safe on the fault path): RS over GF(256), codeword interleave, zigzag placement, 8 masks with N1-N4 penalty auto-selection, format/version info. - gop.rs: dump_qr() joins dump lines into a static buffer, truncates with '...' at the v40-L capacity, encodes, and renders centered black-on-white with a 4-module quiet zone. - tools/qrcheck: host harness (embedds qr.rs) + qrcheck.py cross-check against segno's placement primitives. Verified bit-exact: 12 versions x 8 masks forced, plus auto-mask choice matches segno's penalty evaluation. Caught 3 encoder bugs (multi-block interleave offsets, transposed version info, mask eval ordering). - QEMU e2e: page-fault dump screendump decodes via zbarimg, content matches the serial log line-for-line. - test-msg.sh and test-fault.sh both PASS; debug+release 0 warnings. --- Cargo.lock | 6 +- Cargo.toml | 2 +- rsnix/src/gop.rs | 83 +++++ rsnix/src/lib.rs | 1 + rsnix/src/qr.rs | 852 ++++++++++++++++++++++++++++++++++++++++++++++ rsnix/src/vt.rs | 6 +- tools/qrcheck.py | 208 +++++++++++ tools/qrcheck/.gitignore | 1 + tools/qrcheck/Cargo.lock | 7 + tools/qrcheck/Cargo.toml | 13 + tools/qrcheck/src/main.rs | 58 ++++ 11 files changed, 1232 insertions(+), 5 deletions(-) create mode 100644 rsnix/src/qr.rs create mode 100644 tools/qrcheck.py create mode 100644 tools/qrcheck/.gitignore create mode 100644 tools/qrcheck/Cargo.lock create mode 100644 tools/qrcheck/Cargo.toml create mode 100644 tools/qrcheck/src/main.rs diff --git a/Cargo.lock b/Cargo.lock index 4cef15c..520111e 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -4,7 +4,7 @@ version = 4 [[package]] name = "rsdos" -version = "0.5.7" +version = "0.5.8" dependencies = [ "rsnix", "shell", @@ -19,11 +19,11 @@ dependencies = [ [[package]] name = "rsnix" -version = "0.5.7" +version = "0.5.8" [[package]] name = "shell" -version = "0.5.7" +version = "0.5.8" dependencies = [ "rsdosedit", "rsnix", diff --git a/Cargo.toml b/Cargo.toml index b55a0aa..7ec8e2e 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -3,7 +3,7 @@ resolver = "2" members = ["rsnix", "shell", "rsdos", "rsdosedit"] [workspace.package] -version = "0.5.7" +version = "0.5.8" edition = "2024" # no_std UEFI kernel: no unwinder available, so panic must abort. diff --git a/rsnix/src/gop.rs b/rsnix/src/gop.rs index 012a9d0..ecf8fa9 100644 --- a/rsnix/src/gop.rs +++ b/rsnix/src/gop.rs @@ -516,6 +516,89 @@ pub fn dump_lines(lines: &[&str]) { } } } + // Scannable QR of the same text below the band (heap-free encoder; + // real hardware has no serial console — photograph the screen). + dump_qr(lines); +} + +/// Render the crash/fault lines as a QR code below the dump band. +/// +/// The joined text is built in a `.bss` buffer (the fault path must not +/// allocate) and encoded byte-mode EC-L by `crate::qr` (also heap-free, +/// static matrix). Over-long text is truncated with a "…" marker. If +/// the text does not fit a QR or there is no framebuffer, this is a no-op +/// and the band text remains the only channel. +static mut QR_TEXT: [u8; crate::qr::MAX_BYTES + 4] = [0; crate::qr::MAX_BYTES + 4]; + +pub fn dump_qr(lines: &[&str]) { + let Some(fb) = fb().as_ref() else { + return; + }; + unsafe { + let text = &mut *core::ptr::addr_of_mut!(QR_TEXT); + let mut n = 0usize; + for line in lines { + let b = line.as_bytes(); + let take = b.len().min(text.len() - n); + text[n..n + take].copy_from_slice(&b[..take]); + n += take; + if n < text.len() { + text[n] = b'\n'; + n += 1; + } + } + while n > 0 && text[n - 1] == b'\n' { + n -= 1; + } + if n == 0 { + return; + } + let cap = crate::qr::MAX_BYTES.saturating_sub(3); + if n > cap { + n = cap; + text[n..n + 3].copy_from_slice(b"..."); + n += 3; + } + if crate::qr::encode(&text[..n]) == 0 { + return; + } + } + render_qr(fb, lines.len() * 16); +} + +/// Draw the current QR matrix (black on white, quiet zone) centred below +/// the band, scaled to the largest square that fits. +fn render_qr(fb: &Framebuffer, band_px: usize) { + let size = crate::qr::size(); + if size == 0 { + return; + } + let total = size + 8; // 4-module quiet zone each side + let avail_w = fb.width.saturating_sub(24); + let avail_h = fb.height.saturating_sub(band_px + 16); + let scale = (avail_w / total).min(avail_h / total); + if scale < 1 { + return; + } + let px = total * scale; + let x0 = (fb.width - px) / 2; + let y0 = band_px + 8 + (avail_h.saturating_sub(px) / 2); + let white = rgb(0xFF, 0xFF, 0xFF); + let black = rgb(0, 0, 0); + fill_rect(x0, y0, px, px, white); + for y in 0..size { + for x in 0..size { + if crate::qr::module(x, y) { + fill_rect( + x0 + (x + 4) * scale, + y0 + (y + 4) * scale, + scale, + scale, + black, + ); + } + } + } } /// Read one pixel back from the shadow (RAM; cheap). Test/demo use only. diff --git a/rsnix/src/lib.rs b/rsnix/src/lib.rs index f4645a5..dbb327c 100644 --- a/rsnix/src/lib.rs +++ b/rsnix/src/lib.rs @@ -14,6 +14,7 @@ pub mod klog; pub mod memory; pub mod paging; pub mod pci; +pub mod qr; pub mod power; pub mod ps2; pub mod rtc; diff --git a/rsnix/src/qr.rs b/rsnix/src/qr.rs new file mode 100644 index 0000000..84151e6 --- /dev/null +++ b/rsnix/src/qr.rs @@ -0,0 +1,852 @@ +//! 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 } +} diff --git a/rsnix/src/vt.rs b/rsnix/src/vt.rs index 6e1f12f..88f8d43 100644 --- a/rsnix/src/vt.rs +++ b/rsnix/src/vt.rs @@ -250,7 +250,11 @@ pub fn debug_verify() { } msg(&alloc::format!( "verify: grids c nz={} blank={} r nz={} blank={} (of {})", - c_nz, c_blank, r_nz, r_blank, total + c_nz, + c_blank, + r_nz, + r_blank, + total )); if c.len() != total || r.len() != total || !heap_ok || !content_ok || !rcontent_ok { msg("verify: FAILED — cells/rendered not sane at shell entry"); diff --git a/tools/qrcheck.py b/tools/qrcheck.py new file mode 100644 index 0000000..305594c --- /dev/null +++ b/tools/qrcheck.py @@ -0,0 +1,208 @@ +#!/usr/bin/env python3 +"""Cross-check the kernel QR encoder (tools/qrcheck) against segno. + +Strategy: segno's own bitstream differs from the kernel's in the pad bits +(segno emits a full extra zero byte when the stream is already byte-aligned), +so instead of comparing against `segno.make()` directly we feed the kernel's +own interleaved codeword stream through segno's placement primitives +(make_matrix / add_finder_patterns / add_alignment_patterns / add_codewords / +apply_mask / add_format_info / add_version_info) and compare matrices +bit-for-bit. For auto-mask cases the chosen mask is validated against +segno's `mask_scores` penalty evaluation on the same (kernel-stream) matrix. +""" +import importlib +import subprocess +import sys + +sys.path.insert(0, "/tmp/segno_pkg") +segno = importlib.import_module("segno") # vendored reference at /tmp/segno_pkg +E = importlib.import_module("segno.encoder") +C = importlib.import_module("segno.consts") + +BIN = "tools/qrcheck/target/debug/qrcheck" +ROOT = "/home/salmon/Documents/rust/rsdos" + + +def run(args): + out = subprocess.run(args, capture_output=True, text=True, cwd=ROOT) + if out.returncode != 0: + print("RUST FAIL:", out.stderr.strip()) + sys.exit(1) + return out.stdout + + +def rust_matrix(text, version, mask): + args = [BIN, text] + if version: + args.append(str(version)) + if mask is not None: + args.append(str(mask)) + lines = run(args).splitlines() + return lines[0], lines[1:] + + +def rust_raw(text, version): + """Kernel interleaved codeword stream (data+EC) as bytes.""" + hexs = run([BIN, "--raw", text, str(version)]).strip() + return bytes.fromhex(hexs) + + +def _to_bits(my_cw): + try: + return [int(b) for byte in my_cw for b in f"{byte:08b}"] + except (ValueError, TypeError) as exc: + print(f"bad codeword stream {my_cw!r}: {exc}") + sys.exit(1) + + +def build_matrix(version, my_cw, mask, with_info): + """Expected matrix from the kernel's codeword stream via segno primitives. + + `with_info=True` also writes format + version info (final symbol); + `with_info=False` leaves them light (as during mask evaluation). + """ + n = E.calc_matrix_size(version) + bits = _to_bits(my_cw) + m = E.make_matrix(n, n) + E.add_finder_patterns(m, n, n) + E.add_alignment_patterns(m, n, n) + E.add_codewords(m, bits, version) + fm = E.make_matrix(n, n) + E.add_finder_patterns(fm, n, n) + E.add_alignment_patterns(fm, n, n) + fm[-8][8] = 0x1 + E.apply_mask(m, E.get_data_mask_functions(False)[mask], n, n, + lambda i, j: fm[i][j] > 0x1) + if with_info: + E.add_format_info(m, version, C.ERROR_LEVEL_L, mask) + E.add_version_info(m, version) + # Normalize leftover (remainder) cells: 0x2/0x3 -> 0/1. + return [[v & 0x1 if v in (2, 3) else v for v in row] for row in m] + + +def render(rows): + return ["".join("#" if c else "." for c in row) for row in rows] + + +def compare_forced(text, version, mask): + hdr, rows = rust_matrix(text, version, mask) + my_cw = rust_raw(text, version) + exp = build_matrix(version, my_cw, mask, with_info=True) + srows = render(exp) + tag = f"v{version} m{mask} {text[:28]!r}" + if len(rows) != len(srows): + print(f"FAIL {tag}: rust {len(rows)}x vs expected {len(srows)}x") + return False + for y, (r, s) in enumerate(zip(rows, srows)): + if r != s: + print(f"FAIL {tag}: row {y} differs (rust v{mask})") + for dy in range(max(0, y - 2), min(len(rows), y + 3)): + print(f" rust row{dy}: {rows[dy]}") + print(f" exp row{dy}: {srows[dy]}") + return False + print(f"OK {tag} ({len(rows)}x{len(rows)}, {hdr})") + return True + + +def segno_best_mask(version, my_cw): + """Mask segno's penalty scoring would choose for the kernel stream.""" + n = E.calc_matrix_size(version) + bits = _to_bits(my_cw) + scores = [] + for mask in range(8): + m = E.make_matrix(n, n) + E.add_finder_patterns(m, n, n) + E.add_alignment_patterns(m, n, n) + E.add_codewords(m, bits, version) + fm = E.make_matrix(n, n) + E.add_finder_patterns(fm, n, n) + E.add_alignment_patterns(fm, n, n) + fm[-8][8] = 0x1 + E.apply_mask(m, E.get_data_mask_functions(False)[mask], n, n, + lambda i, j: fm[i][j] > 0x1) + scores.append((sum(E.mask_scores(m, n, n)), mask)) + return min(scores) # (score, mask); first-lowest wins like segno + + +def _parse_hdr(hdr): + try: + v = int(hdr.split()[0][1:]) + m = int(hdr.split()[1][1:]) + except (ValueError, IndexError) as exc: + print(f"bad header {hdr!r}: {exc}") + sys.exit(1) + return v, m + + +def compare_auto(text, version=None): + args = [BIN, text] + if version: + args.append(str(version)) + lines = run(args).splitlines() + hdr = lines[0] # "v m" + rows = lines[1:] + v, m = _parse_hdr(hdr) + my_cw = rust_raw(text, v) + score, s_mask = segno_best_mask(v, my_cw) + tag = f"v{v} auto-mask {text[:28]!r}" + if m != s_mask: + print(f"FAIL {tag}: rust chose m{m}, segno penalty chose m{s_mask} " + f"(score {score})") + return False + # Full final-matrix check with the chosen mask. + exp = build_matrix(v, my_cw, m, with_info=True) + srows = render(exp) + if len(rows) != len(srows): + print(f"FAIL {tag}: size mismatch") + return False + for y, (r, s) in enumerate(zip(rows, srows)): + if r != s: + print(f"FAIL {tag}: row {y} differs") + for dy in range(max(0, y - 2), min(len(rows), y + 3)): + print(f" rust row{dy}: {rows[dy]}") + print(f" exp row{dy}: {srows[dy]}") + return False + print(f"OK {tag} (m{m} matches segno, {len(rows)}x{len(rows)})") + return True + + +def main(): + ok = True + texts = { + 1: "A", + 2: "hello", + 3: "the quick brown fox", + 4: "0123456789ABCDEF", + 5: "byte mode QR encoder cross-check", + 6: "x" * 100, + 7: "hello world, this is a slightly longer message for v7", + 10: "x" * 250, + 14: "x" * 400, + 20: "x" * 800, + 25: "x" * 1200, + 40: "x" * 2900, + } + for v in (1, 2, 3, 4, 5, 6, 7, 10, 14, 20, 25, 40): + for m in range(8): + ok &= compare_forced(texts[v], v, m) + crash = ( + "!!! heap corruption in dealloc\n" + "ptr=0x404443e0 block=0x1980000 heap=0x1980000 rsp=0x1fffe0\n" + "mem: x=0x41414141 x=0x41414141 x=0x41414141 x=0x41414141\n" + "mem: x=0x41414141 x=0x41414141 x=0x41414141 x=0x41414141\n" + "stk: x=0x0 x=0x0 x=0x0 x=0x0 x=0x0 x=0x0 x=0x0 x=0x0\n" + "hdr: b=0x1980000 s=0x20 f=0 b16=0x1980000 s16=0x20 f16=0\n" + "RSDOS fault: #GP at rip=0x12345678 cr2=0x0 task=main\n" + ) + ok &= compare_auto(crash) + ok &= compare_auto("hello world", 1) + ok &= compare_auto("byte mode QR encoder cross-check", 5) + ok &= compare_auto("hello world, this is a slightly longer message for v7", 7) + ok &= compare_auto("x" * 400, 14) + ok &= compare_auto("x" * 2900, 40) + print("ALL OK" if ok else "FAILURES") + sys.exit(0 if ok else 1) + + +if __name__ == "__main__": + main() diff --git a/tools/qrcheck/.gitignore b/tools/qrcheck/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/tools/qrcheck/.gitignore @@ -0,0 +1 @@ +/target diff --git a/tools/qrcheck/Cargo.lock b/tools/qrcheck/Cargo.lock new file mode 100644 index 0000000..141dd97 --- /dev/null +++ b/tools/qrcheck/Cargo.lock @@ -0,0 +1,7 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 4 + +[[package]] +name = "qrcheck" +version = "0.1.0" diff --git a/tools/qrcheck/Cargo.toml b/tools/qrcheck/Cargo.toml new file mode 100644 index 0000000..4d4487c --- /dev/null +++ b/tools/qrcheck/Cargo.toml @@ -0,0 +1,13 @@ +[package] +name = "qrcheck" +version = "0.1.0" +edition = "2024" + +[[bin]] +name = "qrcheck" +path = "src/main.rs" + +[profile.release] +panic = "abort" + +[workspace] diff --git a/tools/qrcheck/src/main.rs b/tools/qrcheck/src/main.rs new file mode 100644 index 0000000..d294485 --- /dev/null +++ b/tools/qrcheck/src/main.rs @@ -0,0 +1,58 @@ +//! Host-side cross-check tool for the kernel QR encoder. +//! +//! Usage: `qrcheck TEXT [VERSION] [MASK]` +//! - with VERSION+MASK: force both and dump the matrix (compared against +//! segno by `tools/qrcheck.py`); +//! - with neither: auto-pick version and best mask, print `v m`. +//! +//! Output: first line `v m`, then one line per matrix row of +//! `#` (dark) / `.` (light). +#![allow(static_mut_refs)] + +#[path = "../../../rsnix/src/qr.rs"] +mod qr; + +fn main() { + let args: Vec = std::env::args().collect(); + if args.get(1).map(String::as_str) == Some("--raw") { + let text = args.get(2).map(String::as_str).unwrap_or("hello"); + let version: usize = args.get(3).and_then(|s| s.parse().ok()).unwrap_or(0); + let v = if version > 0 { + qr::encode_at(text.as_bytes(), version, Some(0)) + } else { + qr::encode(text.as_bytes()) + }; + if v == 0 { + eprintln!("FAIL"); + std::process::exit(1); + } + for b in qr::codeword_stream() { + print!("{:02x}", b); + } + println!(); + return; + } + let text = args.get(1).map(String::as_str).unwrap_or("hello world"); + let version: usize = args.get(2).and_then(|s| s.parse().ok()).unwrap_or(0); + let mask: Option = args.get(3).and_then(|s| s.parse().ok()); + + let v = if version > 0 { + qr::encode_at(text.as_bytes(), version, mask) + } else { + qr::encode(text.as_bytes()) + }; + if v == 0 { + eprintln!("FAIL: cannot encode {} bytes at v{}", text.len(), version); + std::process::exit(1); + } + let size = qr::size(); + let m = if let Some(m) = mask { m } else { qr::last_mask() }; + println!("v{} m{}", v, m); + for y in 0..size { + let mut row = String::with_capacity(size); + for x in 0..size { + row.push(if qr::module(x, y) { '#' } else { '.' }); + } + println!("{}", row); + } +} -- cgit v1.2.3