eleven / messenger Public

Clone
git clone https://amadan.net/eleven/messenger

Plain git — no account needed to clone.

Download

Download this file

1// Self-contained QR Code (model 2) encoder — byte mode, versions 1-40, all four
2// ECC levels. We render our own QR locally so a join/admin link's secret
3// #fragment never has to leave the browser for some third-party QR service.
4//
5// qrMatrix is pure (no DOM, no globals) so it can be unit-tested in Node; the
6// only browser-only piece is qrCanvas. Tables and the placement/mask algorithm
7// follow ISO/IEC 18004.
8
9const ECL_INDEX = { L: 0, M: 1, Q: 2, H: 3 };
10
11// The 2-bit EC indicator written into the format information is NOT in L/M/Q/H
12// numeric order: L=01, M=00, Q=11, H=10 per the spec.
13const ECL_FORMAT_BITS = { L: 1, M: 0, Q: 3, H: 2 };
14
15// EC codewords per block, indexed [eclIndex][version]. Index 0 of each row is a
16// placeholder so version can index directly. (Nayuki's tables — the part most
17// worth copying verbatim rather than re-deriving.)
18const ECC_CODEWORDS_PER_BLOCK = [
19 [-1, 7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
20 [-1, 10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28],
21 [-1, 13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
22 [-1, 17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30],
23];
24
25// Number of EC blocks, indexed [eclIndex][version].
26const NUM_ERROR_CORRECTION_BLOCKS = [
27 [-1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 8, 8, 9, 9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25],
28 [-1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5, 5, 8, 9, 9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49],
29 [-1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 8, 8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68],
30 [-1, 1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81],
31];
32
33const MIN_VERSION = 1;
34const MAX_VERSION = 40;
35const PENALTY_N1 = 3;
36const PENALTY_N2 = 3;
37const PENALTY_N3 = 40;
38const PENALTY_N4 = 10;
39
40// Number of data+EC modules available in a version, before subtracting function
41// patterns' overhead — i.e. the bits the codeword stream is laid into.
42function numRawDataModules(version) {
43 let result = (16 * version + 128) * version + 64;
44 if (version >= 2) {
45 const numAlign = Math.floor(version / 7) + 2;
46 result -= (25 * numAlign - 10) * numAlign - 55;
47 if (version >= 7) result -= 36; // two version-information blocks
48 }
49 return result;
50}
51
52function numDataCodewords(version, eclIndex) {
53 return (
54 Math.floor(numRawDataModules(version) / 8) -
55 ECC_CODEWORDS_PER_BLOCK[eclIndex][version] *
56 NUM_ERROR_CORRECTION_BLOCKS[eclIndex][version]
57 );
58}
59
60// Byte-mode character-count indicator width grows with version.
61function charCountBits(version) {
62 return version <= 9 ? 8 : 16;
63}
64
65// GF(256) multiply with primitive polynomial 0x11D, via Russian-peasant so we
66// avoid log/antilog tables.
67function gfMul(x, y) {
68 let z = 0;
69 for (let i = 7; i >= 0; i--) {
70 z = (z << 1) ^ ((z >>> 7) * 0x11d);
71 z ^= ((y >>> i) & 1) * x;
72 }
73 return z & 0xff;
74}
75
76// Generator polynomial coefficients (degree `ecLen`) for Reed–Solomon.
77function rsDivisor(ecLen) {
78 const result = new Uint8Array(ecLen);
79 result[ecLen - 1] = 1; // start with the monomial x^0
80 let root = 1;
81 for (let i = 0; i < ecLen; i++) {
82 // multiply the current product by (x - r^i)
83 for (let j = 0; j < result.length; j++) {
84 result[j] = gfMul(result[j], root);
85 if (j + 1 < result.length) result[j] ^= result[j + 1];
86 }
87 root = gfMul(root, 0x02);
88 }
89 return result;
90}
91
92function rsRemainder(data, divisor) {
93 const result = new Uint8Array(divisor.length);
94 for (const b of data) {
95 const factor = b ^ result[0];
96 result.copyWithin(0, 1);
97 result[result.length - 1] = 0;
98 for (let i = 0; i < result.length; i++) {
99 result[i] ^= gfMul(divisor[i], factor);
100 }
101 }
102 return result;
103}
104
105// Build the bit-padded data codeword stream for the chosen version: mode,
106// count, payload, terminator, byte-align, then the alternating EC/11 pad bytes.
107function dataCodewords(bytes, version, eclIndex) {
108 const capacityBits = numDataCodewords(version, eclIndex) * 8;
109 const bits = [];
110 const push = (value, len) => {
111 for (let i = len - 1; i >= 0; i--) bits.push((value >>> i) & 1);
112 };
113
114 push(0b0100, 4); // byte mode
115 push(bytes.length, charCountBits(version));
116 for (const b of bytes) push(b, 8);
117
118 push(0, Math.min(4, capacityBits - bits.length)); // terminator
119 push(0, (8 - (bits.length % 8)) % 8); // align to byte boundary
120 for (let pad = 0xec; bits.length < capacityBits; pad ^= 0xec ^ 0x11) {
121 push(pad, 8);
122 }
123
124 const out = new Uint8Array(bits.length / 8);
125 for (let i = 0; i < bits.length; i++) {
126 out[i >> 3] |= bits[i] << (7 - (i & 7));
127 }
128 return out;
129}
130
131// Split data into blocks, append RS error correction to each, then interleave
132// data-then-EC across blocks as the spec requires.
133function addEccAndInterleave(data, version, eclIndex) {
134 const numBlocks = NUM_ERROR_CORRECTION_BLOCKS[eclIndex][version];
135 const eccLen = ECC_CODEWORDS_PER_BLOCK[eclIndex][version];
136 const rawCodewords = Math.floor(numRawDataModules(version) / 8);
137 const numShort = numBlocks - (rawCodewords % numBlocks);
138 const shortLen = Math.floor(rawCodewords / numBlocks);
139 const divisor = rsDivisor(eccLen);
140
141 const blocks = [];
142 for (let i = 0, k = 0; i < numBlocks; i++) {
143 const datLen = shortLen - eccLen + (i < numShort ? 0 : 1);
144 const dat = data.slice(k, k + datLen);
145 k += datLen;
146 blocks.push({ dat, ecc: rsRemainder(dat, divisor) });
147 }
148
149 const result = new Uint8Array(rawCodewords);
150 let idx = 0;
151 const maxDatLen = shortLen - eccLen + 1;
152 for (let i = 0; i < maxDatLen; i++) {
153 for (const block of blocks) {
154 // short blocks omit their final data codeword from the last column
155 if (i < block.dat.length) result[idx++] = block.dat[i];
156 }
157 }
158 for (let i = 0; i < eccLen; i++) {
159 for (const block of blocks) result[idx++] = block.ecc[i];
160 }
161 return result;
162}
163
164// Alignment-pattern centre coordinates for a version (empty for version 1).
165function alignmentPositions(version) {
166 if (version === 1) return [];
167 const size = version * 4 + 17;
168 const numAlign = Math.floor(version / 7) + 2;
169 const step =
170 version === 32
171 ? 26
172 : Math.ceil((version * 4 + 4) / (numAlign * 2 - 2)) * 2;
173 const result = [6];
174 for (let pos = size - 7; result.length < numAlign; pos -= step) {
175 result.splice(1, 0, pos);
176 }
177 return result;
178}
179
180// A QR symbol under construction: holds the module grid plus a parallel mask of
181// which cells are immutable function patterns.
182class QrSymbol {
183 constructor(version, eclIndex) {
184 this.version = version;
185 this.eclIndex = eclIndex;
186 this.ecl = ["L", "M", "Q", "H"][eclIndex];
187 this.size = version * 4 + 17;
188 this.modules = Array.from({ length: this.size }, () =>
189 new Array(this.size).fill(false)
190 );
191 this.isFunction = Array.from({ length: this.size }, () =>
192 new Array(this.size).fill(false)
193 );
194 }
195
196 set(x, y, dark) {
197 this.modules[y][x] = dark;
198 this.isFunction[y][x] = true;
199 }
200
201 drawFinder(cx, cy) {
202 for (let dy = -4; dy <= 4; dy++) {
203 for (let dx = -4; dx <= 4; dx++) {
204 const x = cx + dx;
205 const y = cy + dy;
206 if (x < 0 || x >= this.size || y < 0 || y >= this.size) continue;
207 const dist = Math.max(Math.abs(dx), Math.abs(dy));
208 this.set(x, y, dist !== 2 && dist !== 4); // ring + centre, with separator
209 }
210 }
211 }
212
213 drawAlignment(cx, cy) {
214 for (let dy = -2; dy <= 2; dy++) {
215 for (let dx = -2; dx <= 2; dx++) {
216 this.set(cx + dx, cy + dy, Math.max(Math.abs(dx), Math.abs(dy)) !== 1);
217 }
218 }
219 }
220
221 drawFunctionPatterns() {
222 for (let i = 0; i < this.size; i++) {
223 this.set(6, i, i % 2 === 0); // vertical timing
224 this.set(i, 6, i % 2 === 0); // horizontal timing
225 }
226
227 this.drawFinder(3, 3);
228 this.drawFinder(this.size - 4, 3);
229 this.drawFinder(3, this.size - 4);
230
231 const pos = alignmentPositions(this.version);
232 const n = pos.length;
233 for (let i = 0; i < n; i++) {
234 for (let j = 0; j < n; j++) {
235 // skip the three that collide with the finder patterns
236 if (
237 (i === 0 && j === 0) ||
238 (i === 0 && j === n - 1) ||
239 (i === n - 1 && j === 0)
240 ) {
241 continue;
242 }
243 this.drawAlignment(pos[i], pos[j]);
244 }
245 }
246
247 // Reserve format/version areas (real bits drawn later); dummy mask is fine.
248 this.drawFormatBits(0);
249 this.drawVersion();
250 }
251
252 drawFormatBits(mask) {
253 const data = (ECL_FORMAT_BITS[this.ecl] << 3) | mask; // 5 bits
254 let rem = data;
255 for (let i = 0; i < 10; i++) rem = (rem << 1) ^ ((rem >> 9) * 0x537);
256 const bits = ((data << 10) | rem) ^ 0x5412; // 15 bits, masked per spec
257 const bit = (i) => ((bits >> i) & 1) !== 0;
258
259 for (let i = 0; i <= 5; i++) this.set(8, i, bit(i));
260 this.set(8, 7, bit(6));
261 this.set(8, 8, bit(7));
262 this.set(7, 8, bit(8));
263 for (let i = 9; i < 15; i++) this.set(14 - i, 8, bit(i));
264
265 for (let i = 0; i < 8; i++) this.set(this.size - 1 - i, 8, bit(i));
266 for (let i = 8; i < 15; i++) this.set(8, this.size - 15 + i, bit(i));
267 this.set(8, this.size - 8, true); // always-dark module
268 }
269
270 drawVersion() {
271 if (this.version < 7) return;
272 let rem = this.version;
273 for (let i = 0; i < 12; i++) rem = (rem << 1) ^ ((rem >> 11) * 0x1f25);
274 const bits = (this.version << 12) | rem; // 18 bits
275
276 for (let i = 0; i < 18; i++) {
277 const dark = ((bits >> i) & 1) !== 0;
278 const a = this.size - 11 + (i % 3);
279 const b = Math.floor(i / 3);
280 this.set(a, b, dark);
281 this.set(b, a, dark);
282 }
283 }
284
285 // Lay the interleaved codeword stream into the data region, zig-zagging up and
286 // down pairs of columns from the right, skipping the vertical timing column.
287 drawCodewords(data) {
288 let i = 0;
289 for (let right = this.size - 1; right >= 1; right -= 2) {
290 if (right === 6) right = 5;
291 for (let vert = 0; vert < this.size; vert++) {
292 for (let j = 0; j < 2; j++) {
293 const x = right - j;
294 const upward = ((right + 1) & 2) === 0;
295 const y = upward ? this.size - 1 - vert : vert;
296 if (!this.isFunction[y][x] && i < data.length * 8) {
297 this.modules[y][x] = ((data[i >> 3] >> (7 - (i & 7))) & 1) !== 0;
298 i++;
299 }
300 }
301 }
302 }
303 }
304
305 maskBit(mask, x, y) {
306 switch (mask) {
307 case 0: return (x + y) % 2 === 0;
308 case 1: return y % 2 === 0;
309 case 2: return x % 3 === 0;
310 case 3: return (x + y) % 3 === 0;
311 case 4: return (Math.floor(x / 3) + Math.floor(y / 2)) % 2 === 0;
312 case 5: return ((x * y) % 2) + ((x * y) % 3) === 0;
313 case 6: return (((x * y) % 2) + ((x * y) % 3)) % 2 === 0;
314 case 7: return (((x + y) % 2) + ((x * y) % 3)) % 2 === 0;
315 default: throw new Error("bad mask");
316 }
317 }
318
319 applyMask(mask) {
320 for (let y = 0; y < this.size; y++) {
321 for (let x = 0; x < this.size; x++) {
322 if (!this.isFunction[y][x] && this.maskBit(mask, x, y)) {
323 this.modules[y][x] = !this.modules[y][x];
324 }
325 }
326 }
327 }
328
329 penaltyScore() {
330 let result = 0;
331 const size = this.size;
332
333 const addHistory = (runLen, history) => {
334 if (history[0] === 0) runLen += size; // light border before a leading run
335 history.pop();
336 history.unshift(runLen);
337 };
338 // A 1:1:3:1:1 dark/light pattern flanked by 4+ light modules (the finder
339 // look-alike) costs N3 each.
340 const countPatterns = (h) => {
341 const n = h[1];
342 const core = n > 0 && h[2] === n && h[3] === n * 3 && h[4] === n && h[5] === n;
343 return (
344 (core && h[0] >= n * 4 && h[6] >= n ? 1 : 0) +
345 (core && h[6] >= n * 4 && h[0] >= n ? 1 : 0)
346 );
347 };
348 const terminateAndCount = (runColor, runLen, history) => {
349 if (runColor) {
350 addHistory(runLen, history);
351 runLen = 0;
352 }
353 runLen += size; // trailing light border
354 addHistory(runLen, history);
355 return countPatterns(history);
356 };
357
358 // Rule 1 + Rule 3, scanned along rows then columns.
359 for (let y = 0; y < size; y++) {
360 let runColor = false;
361 let runLen = 0;
362 const history = [0, 0, 0, 0, 0, 0, 0];
363 for (let x = 0; x < size; x++) {
364 if (this.modules[y][x] === runColor) {
365 runLen++;
366 if (runLen === 5) result += PENALTY_N1;
367 else if (runLen > 5) result++;
368 } else {
369 addHistory(runLen, history);
370 if (!runColor) result += countPatterns(history) * PENALTY_N3;
371 runColor = this.modules[y][x];
372 runLen = 1;
373 }
374 }
375 result += terminateAndCount(runColor, runLen, history) * PENALTY_N3;
376 }
377 for (let x = 0; x < size; x++) {
378 let runColor = false;
379 let runLen = 0;
380 const history = [0, 0, 0, 0, 0, 0, 0];
381 for (let y = 0; y < size; y++) {
382 if (this.modules[y][x] === runColor) {
383 runLen++;
384 if (runLen === 5) result += PENALTY_N1;
385 else if (runLen > 5) result++;
386 } else {
387 addHistory(runLen, history);
388 if (!runColor) result += countPatterns(history) * PENALTY_N3;
389 runColor = this.modules[y][x];
390 runLen = 1;
391 }
392 }
393 result += terminateAndCount(runColor, runLen, history) * PENALTY_N3;
394 }
395
396 // Rule 2: every 2x2 block of one colour costs N2.
397 for (let y = 0; y < size - 1; y++) {
398 for (let x = 0; x < size - 1; x++) {
399 const c = this.modules[y][x];
400 if (
401 c === this.modules[y][x + 1] &&
402 c === this.modules[y + 1][x] &&
403 c === this.modules[y + 1][x + 1]
404 ) {
405 result += PENALTY_N2;
406 }
407 }
408 }
409
410 // Rule 4: deviation of dark-module proportion from 50%.
411 let dark = 0;
412 for (let y = 0; y < size; y++) {
413 for (let x = 0; x < size; x++) if (this.modules[y][x]) dark++;
414 }
415 const total = size * size;
416 const k = Math.ceil(Math.abs(dark * 20 - total * 10) / total) - 1;
417 result += k * PENALTY_N4;
418
419 return result;
420 }
421}
422
423// Pick the smallest version whose data capacity fits the byte payload at the
424// requested ECC level.
425function chooseVersion(byteLen, eclIndex) {
426 for (let version = MIN_VERSION; version <= MAX_VERSION; version++) {
427 const capacityBits = numDataCodewords(version, eclIndex) * 8;
428 const neededBits = 4 + charCountBits(version) + 8 * byteLen;
429 if (neededBits <= capacityBits) return version;
430 }
431 return -1;
432}
433
434// Returns { size, modules } where modules[y][x] is true for a dark module.
435// Throws if the text is too long for version 40 at the given ECC level.
436export function qrMatrix(text, ecl = "M") {
437 const eclIndex = ECL_INDEX[ecl];
438 if (eclIndex === undefined) throw new Error(`unknown ECC level: ${ecl}`);
439
440 const bytes = new TextEncoder().encode(text);
441 const version = chooseVersion(bytes.length, eclIndex);
442 if (version < 0) {
443 throw new Error(`data too long: ${bytes.length} bytes exceeds version 40 at level ${ecl}`);
444 }
445
446 const sym = new QrSymbol(version, eclIndex);
447 sym.drawFunctionPatterns();
448 sym.drawCodewords(
449 addEccAndInterleave(dataCodewords(bytes, version, eclIndex), version, eclIndex)
450 );
451
452 // Try every mask, keep the lowest-penalty one. We apply, score, then undo by
453 // re-applying (XOR masks are self-inverse).
454 let bestMask = 0;
455 let bestPenalty = Infinity;
456 for (let mask = 0; mask < 8; mask++) {
457 sym.applyMask(mask);
458 sym.drawFormatBits(mask);
459 const penalty = sym.penaltyScore();
460 if (penalty < bestPenalty) {
461 bestPenalty = penalty;
462 bestMask = mask;
463 }
464 sym.applyMask(mask);
465 }
466 sym.applyMask(bestMask);
467 sym.drawFormatBits(bestMask);
468
469 return { size: sym.size, modules: sym.modules };
470}
471
472// Browser-only: render the matrix to a fresh <canvas> and return it.
473export function qrCanvas(
474 text,
475 { ecl = "M", scale = 6, margin = 4, dark = "#000", light = "#fff" } = {}
476) {
477 const { size, modules } = qrMatrix(text, ecl);
478 const dim = (size + margin * 2) * scale;
479 const canvas = document.createElement("canvas");
480 canvas.width = dim;
481 canvas.height = dim;
482 const ctx = canvas.getContext("2d");
483 ctx.fillStyle = light;
484 ctx.fillRect(0, 0, dim, dim);
485 ctx.fillStyle = dark;
486 for (let y = 0; y < size; y++) {
487 for (let x = 0; x < size; x++) {
488 if (modules[y][x]) {
489 ctx.fillRect((x + margin) * scale, (y + margin) * scale, scale, scale);
490 }
491 }
492 }
493 return canvas;
494}
495