Spaces:
Running on CPU Upgrade
Running on CPU Upgrade
File size: 10,249 Bytes
367a695 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | // 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 };
}
|