// Byte-mode QR, level M, with no runtime imports or browser state. The matrix // excludes the quiet zone: every renderer must supply four light modules. export type QrMatrix = { size: number; version: number; mask: number; modules: boolean[][] }; // ISO/IEC 18004 level-M block layouts, versions 1..10. Longer blocks follow // shorter ones; the difference is one DATA byte, never an extra parity byte. const BLOCKS = [ { parity: 10, data: [16] }, { parity: 16, data: [28] }, { parity: 26, data: [44] }, { parity: 18, data: [32, 32] }, { parity: 24, data: [43, 43] }, { parity: 16, data: [27, 27, 27, 27] }, { parity: 18, data: [31, 31, 31, 31] }, { parity: 22, data: [38, 38, 39, 39] }, { parity: 22, data: [36, 36, 36, 37, 37] }, { parity: 26, data: [43, 43, 43, 43, 44] }, ]; const ALIGNMENT = [[], [6, 18], [6, 22], [6, 26], [6, 30], [6, 34], [6, 22, 38], [6, 24, 42], [6, 26, 46], [6, 28, 50]]; function multiply(a: number, b: number): number { let product = 0; for (; b > 0; b >>>= 1) { if (b & 1) product ^= a; a <<= 1; if (a & 0x100) a ^= 0x11d; } return product; } function generator(degree: number): number[] { // QR uses roots alpha^0 through alpha^(degree-1) over GF(256), alpha=2. // A wrong polynomial still makes a perfect-looking square that cannot scan. let polynomial = [1]; let root = 1; for (let i = 0; i < degree; i++) { const next = Array(polynomial.length + 1).fill(0); polynomial.forEach((coefficient, j) => { next[j] ^= coefficient; next[j + 1] ^= multiply(coefficient, root); }); polynomial = next; root = multiply(root, 2); } return polynomial; } function interleave(data: number[], lengths: number[], parity: number): number[] { const divisor = generator(parity); let offset = 0; const blocks = lengths.map((length) => { const block = data.slice(offset, offset + length); offset += length; const remainder = Array(parity).fill(0); for (const value of block) { const factor = value ^ remainder.shift()!; remainder.push(0); for (let j = 0; j < parity; j++) remainder[j] ^= multiply(divisor[j + 1], factor); } return { data: block, remainder }; }); // Interleave one column across ALL blocks, then the next. Concatenating // complete blocks is tempting and fails only once a version has >1 block. const result: number[] = []; for (let i = 0; i < Math.max(...lengths); i++) { for (const block of blocks) if (i < block.data.length) result.push(block.data[i]); } for (let i = 0; i < parity; i++) { for (const block of blocks) result.push(block.remainder[i]); } return result; } function maskBit(mask: number, row: number, col: number): boolean { const product = row * col; switch (mask) { case 0: return (row + col) % 2 === 0; case 1: return row % 2 === 0; case 2: return col % 3 === 0; case 3: return (row + col) % 3 === 0; case 4: return (Math.floor(row / 2) + Math.floor(col / 3)) % 2 === 0; case 5: return product % 2 + product % 3 === 0; case 6: return (product % 2 + product % 3) % 2 === 0; case 7: return ((row + col) % 2 + product % 3) % 2 === 0; default: throw new Error("Invalid QR mask"); } } function penalty(modules: boolean[][]): number { const size = modules.length; let score = 0; let dark = 0; const linePenalty = (line: boolean[]): number => { let total = 0; let run = 1; for (let i = 1; i < size; i++) { if (line[i] === line[i - 1]) run++; else { if (run >= 5) total += run - 2; run = 1; } } if (run >= 5) total += run - 2; // N1: 3 for five, then 1 per extra module. for (let i = 0; i <= size - 7; i++) { if (line[i] && !line[i + 1] && line[i + 2] && line[i + 3] && line[i + 4] && !line[i + 5] && line[i + 6]) { // N3: a finder-like 1:1:3:1:1 run with four light modules on // either side. The symbol edge abuts the caller's light quiet zone. const before = line.slice(Math.max(0, i - 4), i).every((bit) => !bit); const after = line.slice(i + 7, i + 11).every((bit) => !bit); if (before || after) total += 40; } } return total; }; for (let row = 0; row < size; row++) { score += linePenalty(modules[row]); score += linePenalty(modules.map((line) => line[row])); for (let col = 0; col < size; col++) { if (modules[row][col]) dark++; // N2: every solid 2x2 square, including overlapping squares. if (row > 0 && col > 0 && modules[row][col] === modules[row - 1][col] && modules[row][col] === modules[row][col - 1] && modules[row][col] === modules[row - 1][col - 1]) score += 3; } } // N4: ten points per full five-percentage-point departure from half dark. return score + Math.floor(Math.abs(dark * 20 - size * size * 10) / (size * size)) * 10; } /** Encode UTF-8 bytes (setup URIs are ASCII/percent-encoded). Never truncate. */ export function encodeQr(text: string): QrMatrix { const bytes = new TextEncoder().encode(text); const index = BLOCKS.findIndex((block, i) => 4 + (i < 9 ? 8 : 16) + bytes.length * 8 <= block.data.reduce((a, b) => a + b, 0) * 8); if (index < 0) throw new RangeError("QR data exceeds version 10-M capacity (213 bytes)"); const version = index + 1; const size = 17 + 4 * version; const layout = BLOCKS[index]; const capacity = layout.data.reduce((a, b) => a + b, 0) * 8; const bits: number[] = []; const append = (value: number, count: number) => { for (let shift = count - 1; shift >= 0; shift--) bits.push((value >>> shift) & 1); }; append(4, 4); // Byte mode; v10 widens the byte COUNT from 8 bits to 16. append(bytes.length, version < 10 ? 8 : 16); bytes.forEach((byte) => append(byte, 8)); append(0, Math.min(4, capacity - bits.length)); // The independent reference keeps a full zero alignment byte after an // already aligned terminator. Preserve that convention when space permits; // a capacity-bound payload must never gain a byte beyond its data blocks. append(0, Math.min(8 - bits.length % 8, capacity - bits.length)); const data: number[] = []; for (let i = 0; i < bits.length; i += 8) { data.push(bits.slice(i, i + 8).reduce((value, bit) => (value << 1) | bit, 0)); } for (let pad = 0; data.length < capacity / 8; pad++) data.push(pad % 2 === 0 ? 0xEC : 0x11); const codewords = interleave(data, layout.data, layout.parity); const modules = Array.from({ length: size }, () => Array(size).fill(false)); const reserved = modules.map((row) => row.slice()); const set = (row: number, col: number, dark: boolean) => { modules[row][col] = dark; reserved[row][col] = true; }; for (let i = 0; i < size; i++) { set(6, i, i % 2 === 0); set(i, 6, i % 2 === 0); } for (const [cy, cx] of [[3, 3], [3, size - 4], [size - 4, 3]]) { for (let dy = -4; dy <= 4; dy++) for (let dx = -4; dx <= 4; dx++) { const row = cy + dy, col = cx + dx; if (row < 0 || col < 0 || row >= size || col >= size) continue; const distance = Math.max(Math.abs(dx), Math.abs(dy)); set(row, col, distance !== 2 && distance !== 4); } } const centers = ALIGNMENT[index]; for (const row of centers) for (const col of centers) { // Alignment can overwrite TIMING, but never any of the three finders. if ((row === 6 && (col === 6 || col === size - 7)) || (col === 6 && row === size - 7)) continue; for (let dy = -2; dy <= 2; dy++) for (let dx = -2; dx <= 2; dx++) { set(row + dy, col + dx, Math.max(Math.abs(dx), Math.abs(dy)) !== 1); } } const format = (value: number) => { const bit = (i: number) => ((value >>> i) & 1) !== 0; for (let i = 0; i <= 5; i++) set(i, 8, bit(i)); set(7, 8, bit(6)); set(8, 8, bit(7)); set(8, 7, bit(8)); for (let i = 9; i < 15; i++) set(8, 14 - i, bit(i)); for (let i = 0; i < 8; i++) set(8, size - 1 - i, bit(i)); for (let i = 8; i < 15; i++) set(size - 15 + i, 8, bit(i)); }; const versionInfo = (value: number) => { if (version < 7) return; for (let i = 0; i < 18; i++) { const a = size - 11 + i % 3, b = Math.floor(i / 3); set(b, a, ((value >>> i) & 1) !== 0); set(a, b, ((value >>> i) & 1) !== 0); } }; format(0); versionInfo(0); set(size - 8, 8, false); let cursor = 0; let upward = true; for (let right = size - 1; right >= 1; right -= 2) { if (right === 6) right--; for (let step = 0; step < size; step++) { const row = upward ? size - 1 - step : step; for (let offset = 0; offset < 2; offset++) { const col = right - offset; if (reserved[row][col]) continue; // Remainder bits past the last codeword are light before masking. modules[row][col] = cursor < codewords.length * 8 && ((codewords[cursor >>> 3] >>> (7 - cursor % 8)) & 1) !== 0; cursor++; } } upward = !upward; } // Choose, never fix, the mask using all four penalty rules. Reserve metadata // as light while scoring; write the chosen format/version bits afterwards. // Strictly-less keeps the lowest mask number when penalties tie. let mask = 0; let bestScore = Infinity; for (let candidate = 0; candidate < 8; candidate++) { const masked = modules.map((row, y) => row.map((dark, x) => reserved[y][x] ? dark : dark !== maskBit(candidate, y, x))); const score = penalty(masked); if (score < bestScore) { bestScore = score; mask = candidate; } } for (let row = 0; row < size; row++) for (let col = 0; col < size; col++) { if (!reserved[row][col]) modules[row][col] = modules[row][col] !== maskBit(mask, row, col); } // M has format indicator 00; the remaining three data bits name the mask. let formatRemainder = mask; for (let i = 0; i < 10; i++) formatRemainder = (formatRemainder << 1) ^ ((formatRemainder >>> 9) * 0x537); format(((mask << 10) | formatRemainder) ^ 0x5412); set(size - 8, 8, true); let versionRemainder = version; for (let i = 0; i < 12; i++) versionRemainder = (versionRemainder << 1) ^ ((versionRemainder >>> 11) * 0x1f25); versionInfo((version << 12) | versionRemainder); return { size, version, mask, modules }; }