loopable / web /src /shell /qrcode.ts
fsanyoto's picture
Deploy AIOS web (React glide grid + FastAPI slice)
992a41f verified
Raw History Blame
10.2 kB
// 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<number>(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<number>(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<boolean>(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 };
}