1// A QR code encoder: byte mode, error correction level M, versions 1 to 202// (up to 666 bytes), no dependencies. Used for the group naddr on the relay3// card and for the remote signer link. Written from the ISO 18004 tables;4// the helpers are exported so the test can read a symbol back and check the5// Reed-Solomon syndromes rather than trust a picture.67// Error correction blocks for level M: [ec codewords per block, group 18// block count, group 1 data codewords, group 2 block count, group 2 data9// codewords], indexed by version. Version 0 is a placeholder.10export const EC_M: [number, number, number, number, number][] = [11 [0, 0, 0, 0, 0],12 [10, 1, 16, 0, 0], [16, 1, 28, 0, 0], [26, 1, 44, 0, 0], [18, 2, 32, 0, 0], [24, 2, 43, 0, 0],13 [16, 4, 27, 0, 0], [18, 4, 31, 0, 0], [22, 2, 38, 2, 39], [22, 3, 36, 2, 37], [26, 4, 43, 1, 44],14 [30, 1, 50, 4, 51], [22, 6, 36, 2, 37], [22, 8, 37, 1, 38], [24, 4, 40, 5, 41], [24, 5, 41, 5, 42],15 [28, 7, 45, 3, 46], [28, 10, 46, 1, 47], [26, 9, 43, 4, 44], [26, 3, 44, 11, 45], [26, 3, 41, 13, 42],16];17const ALIGN: number[][] = [18 [], [], [6, 18], [6, 22], [6, 26], [6, 30], [6, 34], [6, 22, 38], [6, 24, 42], [6, 26, 46], [6, 28, 50],19 [6, 30, 54], [6, 32, 58], [6, 34, 62], [6, 26, 46, 66], [6, 26, 48, 70], [6, 26, 50, 74], [6, 30, 54, 78], [6, 30, 56, 82], [6, 30, 58, 86], [6, 34, 62, 90],20];21export const MAX_VERSION = 20;2223export function dataCodewords(version: number): number {24 const [, g1, d1, g2, d2] = EC_M[version];25 return g1 * d1 + g2 * d2;26}27// capacity is how many bytes a version holds in byte mode at level M.28export function capacity(version: number): number {29 return Math.floor((dataCodewords(version) * 8 - 4 - (version < 10 ? 8 : 16)) / 8);30}3132// ---- GF(256) and Reed-Solomon ----3334const EXP = new Uint8Array(512);35const LOG = new Uint8Array(256);36(() => {37 let x = 1;38 for (let i = 0; i < 255; i++) {39 EXP[i] = x;40 LOG[x] = i;41 x <<= 1;42 if (x & 0x100) x ^= 0x11d;43 }44 for (let i = 255; i < 512; i++) EXP[i] = EXP[i - 255];45})();46export function gfMul(a: number, b: number): number {47 return a === 0 || b === 0 ? 0 : EXP[LOG[a] + LOG[b]];48}49export function gfPow(base: number, e: number): number {50 return EXP[(LOG[base] * e) % 255];51}52function generator(ec: number): number[] {53 let g = [1];54 for (let i = 0; i < ec; i++) {55 const next = new Array<number>(g.length + 1).fill(0);56 for (let j = 0; j < g.length; j++) {57 next[j] ^= g[j];58 next[j + 1] ^= gfMul(g[j], EXP[i]);59 }60 g = next;61 }62 return g;63}64export function rsEncode(data: number[], ec: number): number[] {65 const g = generator(ec);66 const rem = new Array<number>(ec).fill(0);67 for (const d of data) {68 const f = d ^ rem[0];69 rem.shift();70 rem.push(0);71 if (f === 0) continue;72 for (let j = 0; j < ec; j++) rem[j] ^= gfMul(g[j + 1], f);73 }74 return rem;75}7677// ---- layout ----7879export interface Layout {80 size: number;81 isFunction: Uint8Array; // 1 where a module is fixed or reserved82}8384export function layout(version: number): Layout {85 const size = version * 4 + 17;86 const f = new Uint8Array(size * size);87 const mark = (x: number, y: number) => {88 if (x >= 0 && y >= 0 && x < size && y < size) f[y * size + x] = 1;89 };90 // Finders with separators, and the format areas next to them.91 for (const [cx, cy] of [[0, 0], [size - 7, 0], [0, size - 7]]) {92 for (let y = -1; y < 8; y++) for (let x = -1; x < 8; x++) mark(cx + x, cy + y);93 }94 for (let i = 0; i < 9; i++) {95 mark(i, 8);96 mark(8, i);97 }98 for (let i = 0; i < 8; i++) {99 mark(size - 1 - i, 8);100 mark(8, size - 1 - i);101 }102 // Timing.103 for (let i = 8; i < size - 8; i++) {104 mark(i, 6);105 mark(6, i);106 }107 // Alignment.108 const a = ALIGN[version];109 for (const cy of a) {110 for (const cx of a) {111 if ((cx === 6 && cy === 6) || (cx === 6 && cy === size - 7) || (cx === size - 7 && cy === 6)) continue;112 for (let y = -2; y <= 2; y++) for (let x = -2; x <= 2; x++) mark(cx + x, cy + y);113 }114 }115 // Version information.116 if (version >= 7) {117 for (let i = 0; i < 18; i++) {118 mark(Math.floor(i / 3), size - 11 + (i % 3));119 mark(size - 11 + (i % 3), Math.floor(i / 3));120 }121 }122 return { size, isFunction: f };123}124125// dataOrder lists the non-function modules in the zigzag order data bits are placed.126export function dataOrder(l: Layout): [number, number][] {127 const out: [number, number][] = [];128 const { size, isFunction } = l;129 let up = true;130 for (let col = size - 1; col > 0; col -= 2) {131 if (col === 6) col = 5;132 for (let i = 0; i < size; i++) {133 const y = up ? size - 1 - i : i;134 for (const dx of [0, 1]) {135 const x = col - dx;136 if (!isFunction[y * size + x]) out.push([x, y]);137 }138 }139 up = !up;140 }141 return out;142}143144export const MASKS: ((x: number, y: number) => boolean)[] = [145 (x, y) => (x + y) % 2 === 0,146 (_x, y) => y % 2 === 0,147 (x) => x % 3 === 0,148 (x, y) => (x + y) % 3 === 0,149 (x, y) => (Math.floor(y / 2) + Math.floor(x / 3)) % 2 === 0,150 (x, y) => ((x * y) % 2) + ((x * y) % 3) === 0,151 (x, y) => (((x * y) % 2) + ((x * y) % 3)) % 2 === 0,152 (x, y) => (((x + y) % 2) + ((x * y) % 3)) % 2 === 0,153];154155// formatBits is the 15-bit BCH-coded format information for level M and a mask.156export function formatBits(mask: number): number {157 const data = (0 << 3) | mask; // level M is 00158 let bch = data << 10;159 for (let i = 14; i >= 10; i--) if (bch & (1 << i)) bch ^= 0x537 << (i - 10);160 return ((data << 10) | bch) ^ 0x5412;161}162export function versionBits(version: number): number {163 let rem = version << 12;164 for (let i = 17; i >= 12; i--) if (rem & (1 << i)) rem ^= 0x1f25 << (i - 12);165 return (version << 12) | rem;166}167168// ---- encoding ----169170export interface Symbol {171 version: number;172 size: number;173 mask: number;174 modules: Uint8Array; // 1 is dark175}176177// codewords builds the interleaved data and error correction stream.178export function codewords(bytes: Uint8Array, version: number): number[] {179 const bits: number[] = [];180 const push = (v: number, n: number) => {181 for (let i = n - 1; i >= 0; i--) bits.push((v >> i) & 1);182 };183 push(0b0100, 4);184 push(bytes.length, version < 10 ? 8 : 16);185 for (const b of bytes) push(b, 8);186 const total = dataCodewords(version) * 8;187 push(0, Math.min(4, total - bits.length));188 while (bits.length % 8) bits.push(0);189 const data: number[] = [];190 for (let i = 0; i < bits.length; i += 8) data.push(parseInt(bits.slice(i, i + 8).join(""), 2));191 for (let pad = 0xec; data.length < dataCodewords(version); pad ^= 0xec ^ 0x11) data.push(pad);192 // Split into blocks, compute EC, interleave.193 const [ec, g1, d1, g2, d2] = EC_M[version];194 const blocks: number[][] = [];195 let off = 0;196 for (let i = 0; i < g1 + g2; i++) {197 const len = i < g1 ? d1 : d2;198 blocks.push(data.slice(off, off + len));199 off += len;200 }201 const ecs = blocks.map((b) => rsEncode(b, ec));202 const out: number[] = [];203 const longest = Math.max(d1, d2);204 for (let i = 0; i < longest; i++) for (const b of blocks) if (i < b.length) out.push(b[i]);205 for (let i = 0; i < ec; i++) for (const e of ecs) out.push(e[i]);206 return out;207}208209function penalty(m: Uint8Array, size: number): number {210 let score = 0;211 const at = (x: number, y: number) => m[y * size + x];212 // Runs of five or more in a row or column.213 for (let y = 0; y < size; y++) {214 let run = 1;215 for (let x = 1; x < size; x++) {216 if (at(x, y) === at(x - 1, y)) run++;217 else {218 if (run >= 5) score += run - 2;219 run = 1;220 }221 }222 if (run >= 5) score += run - 2;223 }224 for (let x = 0; x < size; x++) {225 let run = 1;226 for (let y = 1; y < size; y++) {227 if (at(x, y) === at(x, y - 1)) run++;228 else {229 if (run >= 5) score += run - 2;230 run = 1;231 }232 }233 if (run >= 5) score += run - 2;234 }235 // Two by two blocks.236 for (let y = 0; y < size - 1; y++) {237 for (let x = 0; x < size - 1; x++) {238 const v = at(x, y);239 if (v === at(x + 1, y) && v === at(x, y + 1) && v === at(x + 1, y + 1)) score += 3;240 }241 }242 // Finder-like patterns with four light modules on a side.243 const pat = [1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0];244 const check = (get: (i: number) => number, len: number) => {245 for (let i = 0; i + 11 <= len; i++) {246 let fwd = true;247 let back = true;248 for (let j = 0; j < 11; j++) {249 const v = get(i + j);250 if (v !== pat[j]) fwd = false;251 if (v !== pat[10 - j]) back = false;252 }253 if (fwd || back) score += 40;254 }255 };256 for (let y = 0; y < size; y++) check((i) => at(i, y), size);257 for (let x = 0; x < size; x++) check((i) => at(x, i), size);258 // Dark proportion.259 let dark = 0;260 for (const v of m) dark += v;261 const pct = (dark * 100) / (size * size);262 score += Math.floor(Math.abs(pct - 50) / 5) * 10;263 return score;264}265266// encode picks the smallest version that fits, tries every mask and keeps267// the one with the lowest penalty.268export function encode(text: string | Uint8Array): Symbol {269 const bytes = typeof text === "string" ? new TextEncoder().encode(text) : text;270 let version = 1;271 while (version <= MAX_VERSION && capacity(version) < bytes.length) version++;272 if (version > MAX_VERSION) throw new Error(`too long for a QR code: ${bytes.length} bytes, at most ${capacity(MAX_VERSION)}`);273 const l = layout(version);274 const { size } = l;275 const cw = codewords(bytes, version);276 const order = dataOrder(l);277 const base = new Uint8Array(size * size);278 const set = (x: number, y: number, v: number) => {279 base[y * size + x] = v;280 };281 // Finders.282 for (const [cx, cy] of [[0, 0], [size - 7, 0], [0, size - 7]]) {283 for (let y = 0; y < 7; y++) {284 for (let x = 0; x < 7; x++) {285 const edge = x === 0 || y === 0 || x === 6 || y === 6;286 const core = x >= 2 && x <= 4 && y >= 2 && y <= 4;287 set(cx + x, cy + y, edge || core ? 1 : 0);288 }289 }290 }291 // Timing.292 for (let i = 8; i < size - 8; i++) {293 set(i, 6, i % 2 === 0 ? 1 : 0);294 set(6, i, i % 2 === 0 ? 1 : 0);295 }296 // Alignment.297 const a = ALIGN[version];298 for (const cy of a) {299 for (const cx of a) {300 if ((cx === 6 && cy === 6) || (cx === 6 && cy === size - 7) || (cx === size - 7 && cy === 6)) continue;301 for (let y = -2; y <= 2; y++) for (let x = -2; x <= 2; x++) set(cx + x, cy + y, Math.max(Math.abs(x), Math.abs(y)) !== 1 ? 1 : 0);302 }303 }304 // Dark module.305 set(8, size - 8, 1);306 // Version information.307 if (version >= 7) {308 const vb = versionBits(version);309 for (let i = 0; i < 18; i++) {310 const bit = (vb >> i) & 1;311 set(Math.floor(i / 3), size - 11 + (i % 3), bit);312 set(size - 11 + (i % 3), Math.floor(i / 3), bit);313 }314 }315 // Data bits, zeros where the stream runs out (the remainder bits).316 const bitAt = (i: number) => (i < cw.length * 8 ? (cw[i >> 3] >> (7 - (i & 7))) & 1 : 0);317 order.forEach(([x, y], i) => set(x, y, bitAt(i)));318319 let best: Uint8Array | null = null;320 let bestMask = 0;321 let bestScore = Infinity;322 for (let mask = 0; mask < 8; mask++) {323 const m = base.slice();324 for (const [x, y] of order) if (MASKS[mask](x, y)) m[y * size + x] ^= 1;325 const fb = formatBits(mask);326 const bit = (i: number) => (fb >> i) & 1;327 // Around the top-left finder: bits 0 to 7 run down column 8, bits 8 to328 // 14 run leftwards along row 8 (ISO 18004 figure 25).329 for (let i = 0; i < 6; i++) m[i * size + 8] = bit(i);330 m[7 * size + 8] = bit(6);331 m[8 * size + 8] = bit(7);332 m[8 * size + 7] = bit(8);333 for (let i = 9; i < 15; i++) m[8 * size + (14 - i)] = bit(i);334 // Split between the other two finders: bits 0 to 7 leftwards along row335 // 8 from the right edge, bits 8 to 14 down column 8 to the bottom.336 for (let i = 0; i < 8; i++) m[8 * size + (size - 1 - i)] = bit(i);337 for (let i = 8; i < 15; i++) m[(size - 15 + i) * size + 8] = bit(i);338 const s = penalty(m, size);339 if (s < bestScore) {340 bestScore = s;341 best = m;342 bestMask = mask;343 }344 }345 return { version, size, mask: bestMask, modules: best as Uint8Array };346}347348// svg renders a symbol with a quiet zone, dark on transparent so it sits on349// any background; pass a fill and a background to change that.350export function svg(text: string | Uint8Array, opts: { margin?: number; fill?: string; background?: string; title?: string } = {}): string {351 const q = encode(text);352 const margin = opts.margin ?? 2;353 const n = q.size + margin * 2;354 let d = "";355 for (let y = 0; y < q.size; y++) {356 for (let x = 0; x < q.size; x++) {357 if (q.modules[y * q.size + x]) d += `M${x + margin} ${y + margin}h1v1h-1z`;358 }359 }360 const bg = opts.background ? `<rect width="${n}" height="${n}" fill="${opts.background}"/>` : "";361 const title = opts.title ? `<title>${opts.title.replace(/[<&>]/g, (c) => ({ "<": "<", "&": "&", ">": ">" })[c] as string)}</title>` : "";362 return `<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 ${n} ${n}" shape-rendering="crispEdges">${title}${bg}<path d="${d}" fill="${opts.fill ?? "#1c1b18"}"/></svg>`;363}