| 1 | // A QR encoder, alphanumeric mode, versions 1–6. |
| 2 | // |
| 3 | // This is here for one artifact: the Emergency Kit. The Account Key card and |
| 4 | // the Recovery sheet each carry their code as a QR so a phone can read it off |
| 5 | // paper years later, and that is the moment nothing may be wrong. |
| 6 | // |
| 7 | // Deliberately narrow. Alphanumeric mode only, because a CONTRA code is |
| 8 | // `A1-`/`C1-` plus Crockford Base32 — uppercase letters, digits and hyphens, |
| 9 | // all inside QR's 45-character alphanumeric set. Versions 1–6 only, because a |
| 10 | // 38-character code needs version 3 and stopping below 7 means no version |
| 11 | // information block. Anything outside that throws rather than guessing. |
| 12 | // |
| 13 | // It is checked two ways in CI, not one: every symbol it produces is decoded |
| 14 | // back by ZXing, and every matrix is compared bit-for-bit against Python's |
| 15 | // `qrcode` at the same version, EC level and mask. Neither of those is ours. |
| 16 | |
| 17 | import { remainder } from "./qrgf.js"; |
| 18 | import { |
| 19 | ALIGNMENT, ALNUM, BLOCKS, dataCapacity, EC_LEVELS, MASKS, size, |
| 20 | } from "./qrtables.js"; |
| 21 | |
| 22 | export { EC_LEVELS }; |
| 23 | |
| 24 | class Bits { |
| 25 | constructor() { this.bits = []; } |
| 26 | push(value, length) { |
| 27 | for (let i = length - 1; i >= 0; i--) this.bits.push((value >> i) & 1); |
| 28 | } |
| 29 | get length() { return this.bits.length; } |
| 30 | } |
| 31 | |
| 32 | // encodeAlphanumeric packs characters in pairs — 11 bits for two, 6 for a |
| 33 | // leftover one — which is the whole reason to use this mode over bytes. |
| 34 | function encodeAlphanumeric(text, version, ec) { |
| 35 | const bits = new Bits(); |
| 36 | bits.push(0b0010, 4); // mode: alphanumeric |
| 37 | bits.push(text.length, 9); // character count, 9 bits for versions 1–9 |
| 38 | for (let i = 0; i < text.length; i += 2) { |
| 39 | const a = ALNUM.indexOf(text[i]); |
| 40 | if (a < 0) throw new Error(`qr: ${JSON.stringify(text[i])} is not alphanumeric`); |
| 41 | if (i + 1 < text.length) { |
| 42 | const b = ALNUM.indexOf(text[i + 1]); |
| 43 | if (b < 0) throw new Error(`qr: ${JSON.stringify(text[i + 1])} is not alphanumeric`); |
| 44 | bits.push(a * 45 + b, 11); |
| 45 | } else { |
| 46 | bits.push(a, 6); |
| 47 | } |
| 48 | } |
| 49 | |
| 50 | const capacity = dataCapacity(version, ec) * 8; |
| 51 | if (bits.length > capacity) { |
| 52 | throw new Error(`qr: ${text.length} characters do not fit in version ${version}${ec}`); |
| 53 | } |
| 54 | // Terminator, then to a byte boundary, then the two alternating pad bytes. |
| 55 | bits.push(0, Math.min(4, capacity - bits.length)); |
| 56 | while (bits.length % 8 !== 0) bits.bits.push(0); |
| 57 | |
| 58 | const bytes = []; |
| 59 | for (let i = 0; i < bits.length; i += 8) { |
| 60 | let b = 0; |
| 61 | for (let j = 0; j < 8; j++) b = (b << 1) | bits.bits[i + j]; |
| 62 | bytes.push(b); |
| 63 | } |
| 64 | for (let i = 0; bytes.length < capacity / 8; i++) bytes.push(i % 2 ? 0x11 : 0xec); |
| 65 | return bytes; |
| 66 | } |
| 67 | |
| 68 | // interleave splits the data into the version's blocks, computes each block's |
| 69 | // error correction, and reads the whole lot back column-wise — which is what |
| 70 | // spreads a coffee stain across every block instead of destroying one. |
| 71 | function interleave(bytes, version, ec) { |
| 72 | const [, ecLen, groups] = BLOCKS[version][ec]; |
| 73 | const data = []; |
| 74 | let at = 0; |
| 75 | for (const [count, words] of groups) { |
| 76 | for (let i = 0; i < count; i++) { |
| 77 | data.push(bytes.slice(at, at + words)); |
| 78 | at += words; |
| 79 | } |
| 80 | } |
| 81 | const ecc = data.map((block) => remainder(block, ecLen)); |
| 82 | |
| 83 | const out = []; |
| 84 | const longest = Math.max(...data.map((b) => b.length)); |
| 85 | for (let i = 0; i < longest; i++) { |
| 86 | for (const block of data) if (i < block.length) out.push(block[i]); |
| 87 | } |
| 88 | for (let i = 0; i < ecLen; i++) for (const block of ecc) out.push(block[i]); |
| 89 | return out; |
| 90 | } |
| 91 | |
| 92 | // The fixed patterns: finders, separators, timing, alignment, and the dark |
| 93 | // module. `reserved` marks every cell data must not be written into. |
| 94 | function skeleton(version) { |
| 95 | const n = size(version); |
| 96 | const m = Array.from({ length: n }, () => new Array(n).fill(0)); |
| 97 | const reserved = Array.from({ length: n }, () => new Array(n).fill(false)); |
| 98 | |
| 99 | const put = (r, c, v) => { |
| 100 | if (r >= 0 && r < n && c >= 0 && c < n) { m[r][c] = v; reserved[r][c] = true; } |
| 101 | }; |
| 102 | |
| 103 | for (const [top, left] of [[0, 0], [0, n - 7], [n - 7, 0]]) { |
| 104 | for (let r = -1; r <= 7; r++) { |
| 105 | for (let c = -1; c <= 7; c++) { |
| 106 | const onRing = r === 0 || r === 6 || c === 0 || c === 6; |
| 107 | const inCore = r >= 2 && r <= 4 && c >= 2 && c <= 4; |
| 108 | const inside = r >= 0 && r <= 6 && c >= 0 && c <= 6; |
| 109 | put(top + r, left + c, inside && (onRing || inCore) ? 1 : 0); |
| 110 | } |
| 111 | } |
| 112 | } |
| 113 | |
| 114 | for (let i = 8; i < n - 8; i++) { |
| 115 | put(6, i, i % 2 === 0 ? 1 : 0); |
| 116 | put(i, 6, i % 2 === 0 ? 1 : 0); |
| 117 | } |
| 118 | |
| 119 | const centres = ALIGNMENT[version]; |
| 120 | for (const r of centres) { |
| 121 | for (const c of centres) { |
| 122 | // Never over a finder. |
| 123 | if ((r <= 8 && c <= 8) || (r <= 8 && c >= n - 9) || (r >= n - 9 && c <= 8)) continue; |
| 124 | for (let dr = -2; dr <= 2; dr++) { |
| 125 | for (let dc = -2; dc <= 2; dc++) { |
| 126 | const edge = Math.abs(dr) === 2 || Math.abs(dc) === 2; |
| 127 | put(r + dr, c + dc, edge || (dr === 0 && dc === 0) ? 1 : 0); |
| 128 | } |
| 129 | } |
| 130 | } |
| 131 | } |
| 132 | |
| 133 | put(n - 8, 8, 1); // the dark module |
| 134 | |
| 135 | // Format information areas, reserved now and written after masking. |
| 136 | for (let i = 0; i < 9; i++) { |
| 137 | if (!reserved[8][i]) put(8, i, 0); |
| 138 | if (!reserved[i][8]) put(i, 8, 0); |
| 139 | } |
| 140 | for (let i = 0; i < 8; i++) { |
| 141 | if (!reserved[8][n - 1 - i]) put(8, n - 1 - i, 0); |
| 142 | if (!reserved[n - 1 - i][8]) put(n - 1 - i, 8, 0); |
| 143 | } |
| 144 | return { m, reserved, n }; |
| 145 | } |
| 146 | |
| 147 | |
| 148 | // Data goes in two-module columns, right to left, snaking up and down, and |
| 149 | // skipping the vertical timing column. |
| 150 | function place(grid, codewords) { |
| 151 | const { m, reserved, n } = grid; |
| 152 | let bit = 0; |
| 153 | const total = codewords.length * 8; |
| 154 | for (let right = n - 1; right > 0; right -= 2) { |
| 155 | if (right === 6) right = 5; // the timing column is not a data column |
| 156 | for (let step = 0; step < n; step++) { |
| 157 | const up = ((n - 1 - right) & 2) === 0; |
| 158 | const row = up ? n - 1 - step : step; |
| 159 | for (const col of [right, right - 1]) { |
| 160 | if (reserved[row][col] || bit >= total) continue; |
| 161 | m[row][col] = (codewords[bit >> 3] >> (7 - (bit & 7))) & 1; |
| 162 | bit++; |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | } |
| 167 | |
| 168 | function penalty(m, n) { |
| 169 | let score = 0; |
| 170 | const run = (get) => { |
| 171 | for (let a = 0; a < n; a++) { |
| 172 | let length = 1; |
| 173 | for (let b = 1; b < n; b++) { |
| 174 | if (get(a, b) === get(a, b - 1)) { |
| 175 | length++; |
| 176 | } else { |
| 177 | if (length >= 5) score += length - 2; |
| 178 | length = 1; |
| 179 | } |
| 180 | } |
| 181 | if (length >= 5) score += length - 2; |
| 182 | } |
| 183 | }; |
| 184 | run((r, c) => m[r][c]); |
| 185 | run((c, r) => m[r][c]); |
| 186 | |
| 187 | for (let r = 0; r < n - 1; r++) { |
| 188 | for (let c = 0; c < n - 1; c++) { |
| 189 | const v = m[r][c]; |
| 190 | if (v === m[r][c + 1] && v === m[r + 1][c] && v === m[r + 1][c + 1]) score += 3; |
| 191 | } |
| 192 | } |
| 193 | |
| 194 | const A = [1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]; |
| 195 | const B = [0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1]; |
| 196 | const matches = (get, a, b) => |
| 197 | A.every((v, i) => get(a, b + i) === v) || B.every((v, i) => get(a, b + i) === v); |
| 198 | for (let a = 0; a < n; a++) { |
| 199 | for (let b = 0; b + 11 <= n; b++) { |
| 200 | if (matches((x, y) => m[x][y], a, b)) score += 40; |
| 201 | if (matches((x, y) => m[y][x], a, b)) score += 40; |
| 202 | } |
| 203 | } |
| 204 | |
| 205 | let dark = 0; |
| 206 | for (let r = 0; r < n; r++) for (let c = 0; c < n; c++) dark += m[r][c]; |
| 207 | score += Math.floor(Math.abs((dark * 100) / (n * n) - 50) / 5) * 10; |
| 208 | return score; |
| 209 | } |
| 210 | |
| 211 | // BCH(15,5) over the 5 format bits, then the specification's fixed XOR. |
| 212 | function formatBits(ec, mask) { |
| 213 | let value = (EC_LEVELS[ec] << 3) | mask; |
| 214 | let rem = value; |
| 215 | for (let i = 0; i < 10; i++) { |
| 216 | rem <<= 1; |
| 217 | if (rem & 0x400) rem ^= 0x537; |
| 218 | } |
| 219 | return ((value << 10) | rem) ^ 0x5412; |
| 220 | } |
| 221 | |
| 222 | // The 15 format bits go in twice, and the two copies run in opposite |
| 223 | // directions — which is the detail worth stating rather than deriving from a |
| 224 | // loop, because getting it backwards produces a symbol that is correct |
| 225 | // everywhere else and scans nowhere. |
| 226 | // |
| 227 | // Bit 14 is the most significant. Copy A starts at the top-left corner and |
| 228 | // reads MSB-first along row 8, then continues MSB-first *up* column 8. Copy B |
| 229 | // starts at the bottom of column 8 and runs MSB-first upward, then continues |
| 230 | // along row 8 towards the right edge. (8,6) and (6,8) are timing and are |
| 231 | // skipped; (n-8,8) is the dark module and is not a format cell. |
| 232 | function writeFormat(m, n, ec, mask) { |
| 233 | const bits = formatBits(ec, mask); |
| 234 | const at = (i) => (bits >> i) & 1; |
| 235 | |
| 236 | // Copy A: bits 14…7 along the top row, then bits 6…0 up the left column. |
| 237 | const rowA = [0, 1, 2, 3, 4, 5, 7, 8]; |
| 238 | rowA.forEach((c, i) => { m[8][c] = at(14 - i); }); |
| 239 | const colA = [7, 5, 4, 3, 2, 1, 0]; |
| 240 | colA.forEach((r, i) => { m[r][8] = at(6 - i); }); |
| 241 | |
| 242 | // Copy B: bits 14…8 up from the bottom, then bits 7…0 to the right edge. |
| 243 | for (let i = 0; i < 7; i++) m[n - 1 - i][8] = at(14 - i); |
| 244 | for (let i = 0; i < 8; i++) m[8][n - 8 + i] = at(7 - i); |
| 245 | |
| 246 | m[n - 8][8] = 1; // the dark module, restated |
| 247 | } |
| 248 | |
| 249 | // smallestVersion is the smallest symbol the text fits at this EC level. |
| 250 | export function smallestVersion(text, ec) { |
| 251 | const bits = 4 + 9 + Math.floor(text.length / 2) * 11 + (text.length % 2) * 6; |
| 252 | for (let v = 1; v <= 6; v++) { |
| 253 | if (bits <= dataCapacity(v, ec) * 8) return v; |
| 254 | } |
| 255 | throw new Error(`qr: ${text.length} characters need a version above 6`); |
| 256 | } |
| 257 | |
| 258 | // encode returns the module matrix: 1 is dark, 0 is light, no quiet zone. |
| 259 | // |
| 260 | // `mask` is normally chosen by penalty score, exactly as the specification |
| 261 | // says; passing one forces it, which is what lets CI compare our matrix |
| 262 | // bit-for-bit against another encoder's. |
| 263 | export function encode(text, { ec = "Q", version = null, mask = null } = {}) { |
| 264 | if (!EC_LEVELS.hasOwnProperty(ec)) throw new Error(`qr: unknown EC level ${ec}`); |
| 265 | const v = version ?? smallestVersion(text, ec); |
| 266 | if (!BLOCKS[v]) throw new Error(`qr: version ${v} is outside 1–6`); |
| 267 | |
| 268 | const codewords = interleave(encodeAlphanumeric(text, v, ec), v, ec); |
| 269 | |
| 270 | const build = (candidate) => { |
| 271 | const grid = skeleton(v); |
| 272 | place(grid, codewords); |
| 273 | for (let r = 0; r < grid.n; r++) { |
| 274 | for (let c = 0; c < grid.n; c++) { |
| 275 | if (!grid.reserved[r][c] && MASKS[candidate](r, c)) grid.m[r][c] ^= 1; |
| 276 | } |
| 277 | } |
| 278 | writeFormat(grid.m, grid.n, ec, candidate); |
| 279 | return grid; |
| 280 | }; |
| 281 | |
| 282 | if (mask !== null) return { modules: build(mask).m, version: v, ec, mask }; |
| 283 | |
| 284 | let best = null; |
| 285 | let bestScore = Infinity; |
| 286 | let bestMask = 0; |
| 287 | for (let candidate = 0; candidate < 8; candidate++) { |
| 288 | const grid = build(candidate); |
| 289 | const score = penalty(grid.m, grid.n); |
| 290 | if (score < bestScore) { |
| 291 | bestScore = score; |
| 292 | best = grid; |
| 293 | bestMask = candidate; |
| 294 | } |
| 295 | } |
| 296 | return { modules: best.m, version: v, ec, mask: bestMask }; |
| 297 | } |
| 298 | |
amadan