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 };
}