oxedyne/daimond/www/js/qrscan.js
39.7 KiB, 1 run
created by r2519314175:1423, which is this file's identity for as long as the history lasts, whatever it is later renamed to
download · who wrote it · its history
| 1 | /* ============================================================ |
| 2 | Daimond — reading a QR code (qrscan.js) |
| 3 | ------------------------------------------------------------ |
| 4 | THE READING HALF ONLY. Daimond has exactly one QR ENCODER and |
| 5 | it is in Rust — `fe2o3_graphics::qr`, exported as `qr_matrix` |
| 6 | and reached from the page as `window.DaimondQR.matrix`. Nothing |
| 7 | here draws a symbol, and nothing here may grow to. A second |
| 8 | encoder is how two devices come to disagree about a code they |
| 9 | both claim to have written. |
| 10 | |
| 11 | Why any of it is here. First contact is two people in a room: |
| 12 | one holds up a card, the other reads it. `BarcodeDetector` does |
| 13 | that job on the browsers that have it, and is used first because |
| 14 | it is the platform's own reader and it is what a phone's camera |
| 15 | app uses. Firefox and desktop Safari have none, so the pixels |
| 16 | have to be decoded in JavaScript or the feature is absent on |
| 17 | two of the four browsers people actually run. |
| 18 | |
| 19 | WHERE THIS CAME FROM, AND WHERE IT SHOULD END UP. The picture |
| 20 | pipeline — luminance, adaptive threshold, finder search, the |
| 21 | homography and the sampler — is ported from the codec in |
| 22 | `oxegen/www/public/js/qr.js`, which was written for the same |
| 23 | ceremony and is exercised by `oxegen/dev/qr.test.mjs`. The |
| 24 | matrix-to-bytes half is written here as the exact inverse of |
| 25 | `fe2o3_graphics::qr`, with the two error-correction tables |
| 26 | transcribed from that crate rather than from the standard, so |
| 27 | the reader and the writer cannot drift apart. A decoder |
| 28 | ultimately belongs in `fe2o3_graphics::qr` beside the encoder; |
| 29 | until it is there, this is the fallback and dev/verify_qrscan.mjs |
| 30 | holds it to the Rust encoder's output at every version. |
| 31 | |
| 32 | THE VERSION RANGE MATTERS AND IS NOT INCIDENTAL. The oxegen |
| 33 | codec stops at version 10, 57 modules across, because an |
| 34 | oxenym pairing code is short. An identity card is not: a signed |
| 35 | `daimond/card/0` artefact measures about 336 bytes, so its |
| 36 | `#c=` URL needs version 17. A reader capped at 10 would have |
| 37 | been a reader that could never once read the thing this app |
| 38 | shows it. So the tables here are computed, not tabulated, and |
| 39 | the range is the standard's whole 1 to 40. |
| 40 | |
| 41 | Loaded ON DEMAND by trust.js, not from index.html: it is only |
| 42 | wanted when somebody opens the scanner, and the boot has enough |
| 43 | to do. |
| 44 | ============================================================ */ |
| 45 | (function () { |
| 46 | 'use strict'; |
| 47 | |
| 48 | // ── GF(256), the QR field ────────────────────────────────── |
| 49 | // x^8 + x^4 + x^3 + x^2 + 1. Two tables and the rest is lookup. |
| 50 | |
| 51 | var EXP = new Uint8Array(512); |
| 52 | var LOG = new Uint8Array(256); |
| 53 | (function field() { |
| 54 | var x = 1; |
| 55 | for (var i = 0; i < 255; i++) { |
| 56 | EXP[i] = x; |
| 57 | LOG[x] = i; |
| 58 | x <<= 1; |
| 59 | if (x & 0x100) x ^= 0x11d; |
| 60 | } |
| 61 | // Doubled, so a sum of two logs never has to be reduced. |
| 62 | for (var j = 255; j < 512; j++) EXP[j] = EXP[j - 255]; |
| 63 | })(); |
| 64 | |
| 65 | /// Multiply in the field. Zero absorbs, as it must. |
| 66 | function mul(a, b) { return a && b ? EXP[LOG[a] + LOG[b]] : 0; } |
| 67 | /// Divide in the field. The divisor may not be zero. |
| 68 | function div(a, b) { return a ? EXP[LOG[a] + 255 - LOG[b]] : 0; } |
| 69 | /// The multiplicative inverse. |
| 70 | function inv(a) { return EXP[255 - LOG[a]]; } |
| 71 | |
| 72 | // Polynomials are coefficient arrays, highest degree first. |
| 73 | |
| 74 | function polyAdd(a, b) { |
| 75 | var out = new Uint8Array(Math.max(a.length, b.length)); |
| 76 | var i; |
| 77 | for (i = 0; i < a.length; i++) out[i + out.length - a.length] = a[i]; |
| 78 | for (i = 0; i < b.length; i++) out[i + out.length - b.length] ^= b[i]; |
| 79 | return out; |
| 80 | } |
| 81 | |
| 82 | function polyMul(a, b) { |
| 83 | var out = new Uint8Array(a.length + b.length - 1); |
| 84 | for (var i = 0; i < a.length; i++) { |
| 85 | for (var j = 0; j < b.length; j++) out[i + j] ^= mul(a[i], b[j]); |
| 86 | } |
| 87 | return out; |
| 88 | } |
| 89 | |
| 90 | function polyScale(a, x) { |
| 91 | var out = new Uint8Array(a.length); |
| 92 | for (var i = 0; i < a.length; i++) out[i] = mul(a[i], x); |
| 93 | return out; |
| 94 | } |
| 95 | |
| 96 | function polyEval(a, x) { |
| 97 | var y = a[0]; |
| 98 | for (var i = 1; i < a.length; i++) y = mul(y, x) ^ a[i]; |
| 99 | return y; |
| 100 | } |
| 101 | |
| 102 | // ── Reed-Solomon, the reading way ────────────────────────── |
| 103 | // Syndromes, Berlekamp-Massey for the locator, Chien for the positions and |
| 104 | // Forney for the magnitudes. A correction is not trusted because the |
| 105 | // arithmetic completed: the corrected block is re-checked, and a block that |
| 106 | // still has a syndrome is a failure rather than a guess. |
| 107 | |
| 108 | /// The syndromes, with the leading zero the locator search expects. |
| 109 | function syndromes(msg, nsym) { |
| 110 | var out = new Uint8Array(nsym + 1); |
| 111 | for (var i = 0; i < nsym; i++) out[i + 1] = polyEval(msg, EXP[i]); |
| 112 | return out; |
| 113 | } |
| 114 | |
| 115 | /// The error locator polynomial, or null when there are too many errors. |
| 116 | function errorLocator(synd, nsym) { |
| 117 | var err = Uint8Array.from([1]); |
| 118 | var old = Uint8Array.from([1]); |
| 119 | var shift = synd.length - nsym; |
| 120 | for (var i = 0; i < nsym; i++) { |
| 121 | var k = i + shift; |
| 122 | var delta = synd[k]; |
| 123 | for (var j = 1; j < err.length; j++) { |
| 124 | delta ^= mul(err[err.length - 1 - j], synd[k - j]); |
| 125 | } |
| 126 | var grown = new Uint8Array(old.length + 1); |
| 127 | grown.set(old, 0); |
| 128 | old = grown; |
| 129 | if (delta !== 0) { |
| 130 | if (old.length > err.length) { |
| 131 | var next = polyScale(old, delta); |
| 132 | old = polyScale(err, inv(delta)); |
| 133 | err = next; |
| 134 | } |
| 135 | err = polyAdd(err, polyScale(old, delta)); |
| 136 | } |
| 137 | } |
| 138 | var lead = 0; |
| 139 | while (lead < err.length && err[lead] === 0) lead++; |
| 140 | err = err.slice(lead); |
| 141 | // More errors than the code can locate is not a code this block holds. |
| 142 | return (err.length - 1) * 2 > nsym ? null : err; |
| 143 | } |
| 144 | |
| 145 | /// Where the errors are, as indices from the head of the block. |
| 146 | /// |
| 147 | /// The locator's roots are the INVERSES of the error positions' field |
| 148 | /// elements, so the search runs over a^-i and not over a^i. |
| 149 | function errorPositions(loc, n) { |
| 150 | var want = loc.length - 1; |
| 151 | var pos = []; |
| 152 | for (var i = 0; i < n; i++) { |
| 153 | if (polyEval(loc, EXP[(255 - i % 255) % 255]) === 0) pos.push(n - 1 - i); |
| 154 | } |
| 155 | return pos.length === want ? pos : null; |
| 156 | } |
| 157 | |
| 158 | /// The error evaluator: the syndromes times the locator, modulo x^(n+1). |
| 159 | function errorEvaluator(synd, loc) { |
| 160 | var p = polyMul(synd, loc); |
| 161 | return p.slice(Math.max(0, p.length - loc.length)); |
| 162 | } |
| 163 | |
| 164 | /// Take the errors out of a block, given where they are. |
| 165 | function applyForney(msg, synd, pos) { |
| 166 | var n = msg.length; |
| 167 | var degrees = pos.map(function (p) { return n - 1 - p; }); |
| 168 | var loc = Uint8Array.from([1]); |
| 169 | var i, j; |
| 170 | for (i = 0; i < degrees.length; i++) { |
| 171 | loc = polyMul(loc, Uint8Array.from([EXP[degrees[i] % 255], 1])); |
| 172 | } |
| 173 | var rev = Uint8Array.from(synd).reverse(); |
| 174 | var om = errorEvaluator(rev, loc); |
| 175 | var roots = degrees.map(function (d) { return EXP[d % 255]; }); |
| 176 | |
| 177 | var fix = new Uint8Array(n); |
| 178 | for (i = 0; i < roots.length; i++) { |
| 179 | var xi = roots[i]; |
| 180 | var xinv = inv(xi); |
| 181 | var prime = 1; |
| 182 | for (j = 0; j < roots.length; j++) { |
| 183 | if (j !== i) prime = mul(prime, 1 ^ mul(xinv, roots[j])); |
| 184 | } |
| 185 | if (prime === 0) return null; |
| 186 | fix[pos[i]] = div(mul(xi, polyEval(om, xinv)), prime); |
| 187 | } |
| 188 | return polyAdd(msg, fix); |
| 189 | } |
| 190 | |
| 191 | /// Correct one block, or null where it cannot be corrected. |
| 192 | function rsDecode(block, nsym) { |
| 193 | var synd = syndromes(block, nsym); |
| 194 | var clean = true; |
| 195 | var i; |
| 196 | for (i = 0; i < synd.length; i++) if (synd[i]) { clean = false; break; } |
| 197 | if (clean) return block; |
| 198 | var loc = errorLocator(synd, nsym); |
| 199 | if (!loc) return null; |
| 200 | var pos = errorPositions(loc, block.length); |
| 201 | if (!pos || !pos.length) return null; |
| 202 | var fixed = applyForney(block, synd, pos); |
| 203 | if (!fixed) return null; |
| 204 | // The proof: a corrected block has no syndrome left. Without this a |
| 205 | // miscorrection returns confident rubbish. |
| 206 | var again = syndromes(fixed, nsym); |
| 207 | for (i = 0; i < again.length; i++) if (again[i]) return null; |
| 208 | return fixed; |
| 209 | } |
| 210 | |
| 211 | // ── The version parameters ───────────────────────────────── |
| 212 | // |
| 213 | // TRANSCRIBED FROM `fe2o3_graphics/src/qr.rs`, which is the encoder this |
| 214 | // reader has to agree with, and not from the standard: two independent |
| 215 | // readings of the same table are two chances to differ on a version nobody |
| 216 | // tested. Everything else a version implies -- total codewords, how the |
| 217 | // blocks divide, where the alignment patterns sit -- is COMPUTED from these, |
| 218 | // exactly as the encoder computes it, because a table that repeats what it |
| 219 | // implies is a table that can disagree with itself. |
| 220 | // |
| 221 | // Indexed [ecc ordinal][version], version 0 unused. Low is 0, High is 3. |
| 222 | |
| 223 | var ECC_PER_BLOCK = [ |
| 224 | [-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], |
| 225 | [-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], |
| 226 | [-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], |
| 227 | [-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], |
| 228 | ]; |
| 229 | |
| 230 | var ECC_BLOCKS = [ |
| 231 | [-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], |
| 232 | [-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], |
| 233 | [-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], |
| 234 | [-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], |
| 235 | ]; |
| 236 | |
| 237 | /// The level's index in the tables above. |
| 238 | var ORDINAL = { L: 0, M: 1, Q: 2, H: 3 }; |
| 239 | /// The two-bit value the format field carries for each level. NOT the same |
| 240 | /// order as the table index: the standard assigns Medium the value 0. |
| 241 | var FORMAT_BITS = { L: 1, M: 0, Q: 3, H: 2 }; |
| 242 | /// The four levels in format-field order, so a read format word names one. |
| 243 | var ECC_OF = ['M', 'L', 'H', 'Q']; |
| 244 | |
| 245 | var MIN_VERSION = 1; |
| 246 | var MAX_VERSION = 40; |
| 247 | |
| 248 | /// The frame's width in modules. |
| 249 | function widthOf(version) { return 17 + 4 * version; } |
| 250 | |
| 251 | /// The version a matrix of this width is drawn at, or 0 when it is not one. |
| 252 | function versionOf(size) { |
| 253 | var v = (size - 17) / 4; |
| 254 | return v >= MIN_VERSION && v <= MAX_VERSION && v === Math.floor(v) ? v : 0; |
| 255 | } |
| 256 | |
| 257 | /// Every module a version holds before function patterns and error |
| 258 | /// correction are taken out, in bits. The encoder's own formula. |
| 259 | function rawDataModules(ver) { |
| 260 | var n = (16 * ver + 128) * ver + 64; |
| 261 | if (ver >= 2) { |
| 262 | var numalign = Math.floor(ver / 7) + 2; |
| 263 | n -= (25 * numalign - 10) * numalign - 55; |
| 264 | if (ver >= 7) n -= 36; // two version blocks of eighteen bits |
| 265 | } |
| 266 | return n; |
| 267 | } |
| 268 | |
| 269 | /// Codewords, data and check together. |
| 270 | function totalCodewords(ver) { return Math.floor(rawDataModules(ver) / 8); } |
| 271 | |
| 272 | /// How a version's blocks divide at a level: the counts and the lengths. |
| 273 | function split(version, ecc) { |
| 274 | var o = ORDINAL[ecc]; |
| 275 | var nsym = ECC_PER_BLOCK[o][version]; |
| 276 | var blocks = ECC_BLOCKS[o][version]; |
| 277 | var total = totalCodewords(version); |
| 278 | var data = total - nsym * blocks; |
| 279 | var short = Math.floor(data / blocks); |
| 280 | var longs = data % blocks; |
| 281 | return { nsym: nsym, blocks: blocks, total: total, data: data, |
| 282 | short: short, shorts: blocks - longs, longs: longs }; |
| 283 | } |
| 284 | |
| 285 | /// How many data codewords a version and level hold. |
| 286 | function capacity(version, ecc) { return split(version, ecc).data; } |
| 287 | |
| 288 | /// The width of the character-count field in byte mode. |
| 289 | function countBits(version) { return version < 10 ? 8 : 16; } |
| 290 | |
| 291 | /// Where the alignment patterns' centres sit, for a version. The encoder's |
| 292 | /// own formula, version 32 included, which the standard makes an exception of. |
| 293 | function alignPositions(ver) { |
| 294 | if (ver === 1) return []; |
| 295 | var num = Math.floor(ver / 7) + 2; |
| 296 | var step = (ver === 32) ? 26 |
| 297 | : Math.floor((ver * 4 + num * 2 + 1) / (num * 2 - 2)) * 2; |
| 298 | var size = ver * 4 + 17; |
| 299 | var out = []; |
| 300 | for (var i = 0; i < num - 1; i++) out.push(size - 7 - i * step); |
| 301 | out.push(6); |
| 302 | out.reverse(); |
| 303 | return out; |
| 304 | } |
| 305 | |
| 306 | // ── The frame ────────────────────────────────────────────── |
| 307 | // Which modules are function patterns, so the data stream knows what to |
| 308 | // skip. Built the same way the encoder builds it. |
| 309 | |
| 310 | /// A version's function-pattern map. `fixed` marks every module the data |
| 311 | /// stream must skip, the format and version areas included. |
| 312 | var FRAMES = {}; |
| 313 | function frameOf(version) { |
| 314 | if (FRAMES[version]) return FRAMES[version]; |
| 315 | var size = widthOf(version); |
| 316 | var fixed = new Uint8Array(size * size); |
| 317 | var mark = function (x, y) { |
| 318 | if (x < 0 || y < 0 || x >= size || y >= size) return; |
| 319 | fixed[y * size + x] = 1; |
| 320 | }; |
| 321 | var corners = [[0, 0], [size - 7, 0], [0, size - 7]]; |
| 322 | var i, dx, dy, c; |
| 323 | // The three finders, each with its separator. |
| 324 | for (c = 0; c < corners.length; c++) { |
| 325 | for (dy = -1; dy <= 7; dy++) { |
| 326 | for (dx = -1; dx <= 7; dx++) mark(corners[c][0] + dx, corners[c][1] + dy); |
| 327 | } |
| 328 | } |
| 329 | // The timing patterns, which are what tell a reader the module pitch. |
| 330 | for (i = 8; i < size - 8; i++) { mark(i, 6); mark(6, i); } |
| 331 | // The alignment patterns, less the three the finders already occupy. |
| 332 | var coords = alignPositions(version); |
| 333 | for (var a = 0; a < coords.length; a++) { |
| 334 | for (var b = 0; b < coords.length; b++) { |
| 335 | var cx = coords[b], cy = coords[a]; |
| 336 | var atCorner = (cx === 6 && cy === 6) |
| 337 | || (cx === 6 && cy === size - 7) |
| 338 | || (cx === size - 7 && cy === 6); |
| 339 | if (atCorner) continue; |
| 340 | for (dy = -2; dy <= 2; dy++) { |
| 341 | for (dx = -2; dx <= 2; dx++) mark(cx + dx, cy + dy); |
| 342 | } |
| 343 | } |
| 344 | } |
| 345 | // The format areas. (8, 6) and (6, 8) belong to the timing patterns and |
| 346 | // not to the format, which is why the loop steps over 6. |
| 347 | for (i = 0; i < 9; i++) { |
| 348 | if (i === 6) continue; |
| 349 | mark(8, i); mark(i, 8); |
| 350 | } |
| 351 | for (i = 0; i < 8; i++) { mark(size - 1 - i, 8); mark(8, size - 1 - i); } |
| 352 | mark(8, size - 8); // the module that is always dark |
| 353 | // And the version areas, on the versions that carry them. |
| 354 | if (version >= 7) { |
| 355 | for (i = 0; i < 18; i++) { |
| 356 | var p = size - 11 + i % 3; |
| 357 | var q = Math.floor(i / 3); |
| 358 | mark(p, q); mark(q, p); |
| 359 | } |
| 360 | } |
| 361 | FRAMES[version] = { version: version, size: size, fixed: fixed }; |
| 362 | return FRAMES[version]; |
| 363 | } |
| 364 | |
| 365 | /// Every data module of a frame, in the order the stream fills them: upward |
| 366 | /// and downward through two-module columns from the right, skipping column 6 |
| 367 | /// because the vertical timing pattern stands in it. |
| 368 | function stream(size, fixed) { |
| 369 | var order = []; |
| 370 | for (var right = size - 1; right >= 1; right -= 2) { |
| 371 | if (right === 6) right = 5; |
| 372 | for (var step = 0; step < size; step++) { |
| 373 | for (var j = 0; j < 2; j++) { |
| 374 | var x = right - j; |
| 375 | var up = ((right + 1) & 2) === 0; |
| 376 | var y = up ? size - 1 - step : step; |
| 377 | var i = y * size + x; |
| 378 | if (!fixed[i]) order.push(i); |
| 379 | } |
| 380 | } |
| 381 | } |
| 382 | return order; |
| 383 | } |
| 384 | |
| 385 | /// Whether mask `m` inverts the module at (x, y). |
| 386 | function masked(m, x, y) { |
| 387 | switch (m) { |
| 388 | case 0: return (x + y) % 2 === 0; |
| 389 | case 1: return y % 2 === 0; |
| 390 | case 2: return x % 3 === 0; |
| 391 | case 3: return (x + y) % 3 === 0; |
| 392 | case 4: return (Math.floor(y / 2) + Math.floor(x / 3)) % 2 === 0; |
| 393 | case 5: return (x * y) % 2 + (x * y) % 3 === 0; |
| 394 | case 6: return ((x * y) % 2 + (x * y) % 3) % 2 === 0; |
| 395 | default: return ((x + y) % 2 + (x * y) % 3) % 2 === 0; |
| 396 | } |
| 397 | } |
| 398 | |
| 399 | // ── Format and version information ───────────────────────── |
| 400 | |
| 401 | /// The fifteen bits that say which level and which mask, already masked. |
| 402 | function formatBits(ecc, mask) { |
| 403 | var data = (FORMAT_BITS[ecc] << 3) | mask; |
| 404 | var rem = data; |
| 405 | for (var i = 0; i < 10; i++) rem = (rem << 1) ^ ((rem >>> 9) * 0x537); |
| 406 | return ((data << 10) | rem) ^ 0x5412; |
| 407 | } |
| 408 | |
| 409 | /// The eighteen bits that say which version, for versions 7 and up. |
| 410 | function versionBits(version) { |
| 411 | var rem = version; |
| 412 | for (var i = 0; i < 12; i++) rem = (rem << 1) ^ ((rem >>> 11) * 0x1f25); |
| 413 | return (version << 12) | rem; |
| 414 | } |
| 415 | |
| 416 | // Every legal word, so a damaged one can be matched to the nearest. |
| 417 | var FORMATS = (function () { |
| 418 | var out = []; |
| 419 | var levels = ['L', 'M', 'Q', 'H']; |
| 420 | for (var i = 0; i < levels.length; i++) { |
| 421 | for (var m = 0; m < 8; m++) { |
| 422 | out.push({ bits: formatBits(levels[i], m), ecc: levels[i], mask: m }); |
| 423 | } |
| 424 | } |
| 425 | return out; |
| 426 | })(); |
| 427 | |
| 428 | var VERSIONS = (function () { |
| 429 | var out = []; |
| 430 | for (var v = 7; v <= MAX_VERSION; v++) out.push({ bits: versionBits(v), version: v }); |
| 431 | return out; |
| 432 | })(); |
| 433 | |
| 434 | /// How many bits two words differ in. |
| 435 | function hamming(a, b) { |
| 436 | var x = a ^ b, n = 0; |
| 437 | while (x) { n += x & 1; x >>>= 1; } |
| 438 | return n; |
| 439 | } |
| 440 | |
| 441 | /// Read the format information, from whichever copy is asked for. |
| 442 | function readFormat(cells, size, copy) { |
| 443 | var at = function (x, y) { return cells[y * size + x]; }; |
| 444 | var bits = 0; |
| 445 | var put = function (i, v) { bits |= (v & 1) << i; }; |
| 446 | var i; |
| 447 | if (copy === 0) { |
| 448 | for (i = 0; i <= 5; i++) put(i, at(8, i)); |
| 449 | put(6, at(8, 7)); |
| 450 | put(7, at(8, 8)); |
| 451 | put(8, at(7, 8)); |
| 452 | for (i = 9; i < 15; i++) put(i, at(14 - i, 8)); |
| 453 | } else { |
| 454 | for (i = 0; i < 8; i++) put(i, at(size - 1 - i, 8)); |
| 455 | for (i = 8; i < 15; i++) put(i, at(8, size - 15 + i)); |
| 456 | } |
| 457 | return bits; |
| 458 | } |
| 459 | |
| 460 | /// The version drawn in the frame, or 0 where there is none to read. |
| 461 | function readVersion(cells, size) { |
| 462 | if (size < 45) return 0; |
| 463 | var bits = 0; |
| 464 | for (var i = 0; i < 18; i++) { |
| 465 | var a = size - 11 + i % 3; |
| 466 | var b = Math.floor(i / 3); |
| 467 | bits |= (cells[b * size + a] & 1) << i; |
| 468 | } |
| 469 | var best = null; |
| 470 | for (var v = 0; v < VERSIONS.length; v++) { |
| 471 | var d = hamming(bits, VERSIONS[v].bits); |
| 472 | if (d <= 3 && (!best || d < best.d)) best = { d: d, version: VERSIONS[v].version }; |
| 473 | } |
| 474 | return best ? best.version : 0; |
| 475 | } |
| 476 | |
| 477 | // ── Decoding a matrix ────────────────────────────────────── |
| 478 | |
| 479 | /// Read a sampled matrix: format, mask, codewords, correction, payload. |
| 480 | /// |
| 481 | /// `cells` is one byte per module, row-major, 1 dark -- the same shape |
| 482 | /// `DaimondQR.matrix` hands out, which is what lets the encoder be the |
| 483 | /// oracle this reader is tested against. |
| 484 | function fromMatrix(cells, size) { |
| 485 | var guess = versionOf(size); |
| 486 | if (!guess) return null; |
| 487 | var format = null; |
| 488 | var copy, i, b; |
| 489 | for (copy = 0; copy < 2; copy++) { |
| 490 | var bits = readFormat(cells, size, copy); |
| 491 | var best = null; |
| 492 | for (i = 0; i < FORMATS.length; i++) { |
| 493 | var d = hamming(bits, FORMATS[i].bits); |
| 494 | if (d <= 3 && (!best || d < best.d)) best = { d: d, f: FORMATS[i] }; |
| 495 | } |
| 496 | if (best && (!format || best.d < format.d)) format = { d: best.d, f: best.f }; |
| 497 | if (format && format.d === 0) break; |
| 498 | } |
| 499 | if (!format) return null; |
| 500 | var drawn = readVersion(cells, size); |
| 501 | if (drawn && drawn !== guess) return null; |
| 502 | |
| 503 | var ecc = format.f.ecc; |
| 504 | var mask = format.f.mask; |
| 505 | var frame = frameOf(guess); |
| 506 | var order = stream(size, frame.fixed); |
| 507 | |
| 508 | // Take the mask off, then read the stream out of the data modules. |
| 509 | var sp = split(guess, ecc); |
| 510 | var words = new Uint8Array(sp.total); |
| 511 | for (i = 0; i < order.length && i < words.length * 8; i++) { |
| 512 | var idx = order[i]; |
| 513 | var x = idx % size; |
| 514 | var y = (idx - x) / size; |
| 515 | var bit = cells[idx] ^ (masked(mask, x, y) ? 1 : 0); |
| 516 | if (bit) words[i >>> 3] |= 0x80 >>> (i & 7); |
| 517 | } |
| 518 | |
| 519 | // Undo the interleave, then correct each block on its own. The short |
| 520 | // blocks hold one data codeword fewer, and the encoder skips that one |
| 521 | // cell as it interleaves, which is why the data pass stops at `short` |
| 522 | // for them and runs one further for the rest. |
| 523 | var dataBlocks = []; |
| 524 | for (b = 0; b < sp.blocks; b++) { |
| 525 | dataBlocks.push(new Uint8Array(sp.short + (b < sp.shorts ? 0 : 1))); |
| 526 | } |
| 527 | var n = 0; |
| 528 | for (i = 0; i <= sp.short; i++) { |
| 529 | for (b = 0; b < sp.blocks; b++) { |
| 530 | if (i < dataBlocks[b].length) dataBlocks[b][i] = words[n++]; |
| 531 | } |
| 532 | } |
| 533 | var checkBlocks = []; |
| 534 | for (b = 0; b < sp.blocks; b++) checkBlocks.push(new Uint8Array(sp.nsym)); |
| 535 | for (i = 0; i < sp.nsym; i++) { |
| 536 | for (b = 0; b < sp.blocks; b++) checkBlocks[b][i] = words[n++]; |
| 537 | } |
| 538 | |
| 539 | var out = []; |
| 540 | for (b = 0; b < sp.blocks; b++) { |
| 541 | var whole = new Uint8Array(dataBlocks[b].length + sp.nsym); |
| 542 | whole.set(dataBlocks[b], 0); |
| 543 | whole.set(checkBlocks[b], dataBlocks[b].length); |
| 544 | var fixed = rsDecode(whole, sp.nsym); |
| 545 | if (!fixed) return null; |
| 546 | for (i = 0; i < dataBlocks[b].length; i++) out.push(fixed[i]); |
| 547 | } |
| 548 | |
| 549 | var text = payload(out, guess); |
| 550 | if (text === null) return null; |
| 551 | return { text: text, version: guess, ecc: ecc, mask: mask, corrections: format.d }; |
| 552 | } |
| 553 | |
| 554 | /// The payload out of the corrected data codewords. Byte mode only, which is |
| 555 | /// what the encoder writes; any other mode is refused rather than guessed at. |
| 556 | function payload(words, version) { |
| 557 | var at = 0; |
| 558 | var total = words.length * 8; |
| 559 | var take = function (n) { |
| 560 | var v = 0; |
| 561 | for (var i = 0; i < n; i++) { |
| 562 | if (at >= total) return null; |
| 563 | v = (v << 1) | ((words[at >>> 3] >>> (7 - (at & 7))) & 1); |
| 564 | at++; |
| 565 | } |
| 566 | return v; |
| 567 | }; |
| 568 | var bytes = []; |
| 569 | for (;;) { |
| 570 | var mode = take(4); |
| 571 | if (mode === null || mode === 0) break; // the terminator, or the end |
| 572 | if (mode !== 4) return null; // any other mode is not ours |
| 573 | var n = take(countBits(version)); |
| 574 | if (n === null) return null; |
| 575 | for (var i = 0; i < n; i++) { |
| 576 | var byte = take(8); |
| 577 | if (byte === null) return null; |
| 578 | bytes.push(byte); |
| 579 | } |
| 580 | } |
| 581 | var buf = Uint8Array.from(bytes); |
| 582 | return new TextDecoder('utf-8', { fatal: false }).decode(buf); |
| 583 | } |
| 584 | |
| 585 | // ── Reading a picture ────────────────────────────────────── |
| 586 | |
| 587 | /// Luminance, on the usual weighting. |
| 588 | function luminance(frame) { |
| 589 | var width = frame.width, height = frame.height, data = frame.data; |
| 590 | var out = new Uint8ClampedArray(width * height); |
| 591 | for (var i = 0, j = 0; j < out.length; i += 4, j++) { |
| 592 | out[j] = (data[i] * 299 + data[i + 1] * 587 + data[i + 2] * 114) / 1000; |
| 593 | } |
| 594 | return out; |
| 595 | } |
| 596 | |
| 597 | // A block the local threshold is taken over, and the smallest spread of |
| 598 | // luminance a block must have before its own average is trusted. |
| 599 | var BLOCK = 8; |
| 600 | var SPREAD = 24; |
| 601 | |
| 602 | /// Binarise adaptively: one threshold per block of the picture, taken from |
| 603 | /// the neighbourhood rather than from the whole frame. |
| 604 | /// |
| 605 | /// A single global threshold works on a screen and fails on every |
| 606 | /// photograph, because a phone holding a card under a lamp has one half of |
| 607 | /// the frame brighter than the other half's paper is dark. |
| 608 | function binarise(lum, width, height) { |
| 609 | var bw = Math.max(1, Math.ceil(width / BLOCK)); |
| 610 | var bh = Math.max(1, Math.ceil(height / BLOCK)); |
| 611 | var mean = new Float32Array(bw * bh); |
| 612 | var bx, by, x, y, x0, y0, x1, y1, sum, n; |
| 613 | for (by = 0; by < bh; by++) { |
| 614 | for (bx = 0; bx < bw; bx++) { |
| 615 | x0 = bx * BLOCK; y0 = by * BLOCK; |
| 616 | x1 = Math.min(width, x0 + BLOCK); y1 = Math.min(height, y0 + BLOCK); |
| 617 | sum = 0; n = 0; |
| 618 | var lo = 255, hi = 0; |
| 619 | for (y = y0; y < y1; y++) { |
| 620 | for (x = x0; x < x1; x++) { |
| 621 | var v = lum[y * width + x]; |
| 622 | sum += v; n++; |
| 623 | if (v < lo) lo = v; |
| 624 | if (v > hi) hi = v; |
| 625 | } |
| 626 | } |
| 627 | var avg = sum / Math.max(1, n); |
| 628 | if (hi - lo <= SPREAD) { |
| 629 | // All one colour: below whatever the darkest module is. |
| 630 | avg = lo / 2; |
| 631 | if (by > 0 && bx > 0) { |
| 632 | var near = (mean[(by - 1) * bw + bx] |
| 633 | + 2 * mean[by * bw + bx - 1] |
| 634 | + mean[(by - 1) * bw + bx - 1]) / 4; |
| 635 | if (lo < near) avg = near; |
| 636 | } |
| 637 | } |
| 638 | mean[by * bw + bx] = avg; |
| 639 | } |
| 640 | } |
| 641 | var bin = new Uint8Array(width * height); |
| 642 | for (by = 0; by < bh; by++) { |
| 643 | for (bx = 0; bx < bw; bx++) { |
| 644 | sum = 0; n = 0; |
| 645 | for (var dy = -2; dy <= 2; dy++) { |
| 646 | var yy = Math.min(bh - 1, Math.max(0, by + dy)); |
| 647 | for (var dx = -2; dx <= 2; dx++) { |
| 648 | var xx = Math.min(bw - 1, Math.max(0, bx + dx)); |
| 649 | sum += mean[yy * bw + xx]; n++; |
| 650 | } |
| 651 | } |
| 652 | var t = sum / n; |
| 653 | x0 = bx * BLOCK; y0 = by * BLOCK; |
| 654 | x1 = Math.min(width, x0 + BLOCK); y1 = Math.min(height, y0 + BLOCK); |
| 655 | for (y = y0; y < y1; y++) { |
| 656 | for (x = x0; x < x1; x++) { |
| 657 | bin[y * width + x] = lum[y * width + x] <= t ? 1 : 0; |
| 658 | } |
| 659 | } |
| 660 | } |
| 661 | } |
| 662 | return bin; |
| 663 | } |
| 664 | |
| 665 | // ── Finding the code in the picture ──────────────────────── |
| 666 | // The three finder patterns are the whole of it: found them, and the code's |
| 667 | // position, size, rotation and skew all follow. |
| 668 | |
| 669 | /// Whether five runs hold the finder's 1:1:3:1:1 proportions. |
| 670 | function isFinderRun(c) { |
| 671 | var total = c[0] + c[1] + c[2] + c[3] + c[4]; |
| 672 | if (total < 7) return false; |
| 673 | var m = total / 7; |
| 674 | var tol = m / 2; |
| 675 | return Math.abs(m - c[0]) < tol && Math.abs(m - c[1]) < tol |
| 676 | && Math.abs(3 * m - c[2]) < 3 * tol |
| 677 | && Math.abs(m - c[3]) < tol && Math.abs(m - c[4]) < tol; |
| 678 | } |
| 679 | |
| 680 | /// One line of the picture as alternating runs. `at` is the first pixel |
| 681 | /// index of the run and `n` its length. |
| 682 | function runs(bin, width, height, along, axis) { |
| 683 | var limit = axis ? height : width; |
| 684 | var out = []; |
| 685 | var at = 0; |
| 686 | var dark = axis ? bin[along] === 1 : bin[along * width] === 1; |
| 687 | for (var i = 1; i <= limit; i++) { |
| 688 | var here = i < limit |
| 689 | && (axis ? bin[i * width + along] === 1 : bin[along * width + i] === 1); |
| 690 | if (i === limit || here !== dark) { |
| 691 | out.push({ dark: dark, at: at, n: i - at }); |
| 692 | at = i; |
| 693 | dark = here; |
| 694 | } |
| 695 | } |
| 696 | return out; |
| 697 | } |
| 698 | |
| 699 | /// The centre of a run, in pixel-index coordinates. |
| 700 | function midRun(r) { return r.at + (r.n - 1) / 2; } |
| 701 | |
| 702 | /// Confirm a candidate along one axis, and say where its centre is. A row of |
| 703 | /// a picture can hold the finder's proportions by accident -- a line of text |
| 704 | /// does -- and only a pattern that holds them both ways is a finder. |
| 705 | function crossCheck(bin, width, height, cx, cy, module, axis) { |
| 706 | var limit = axis ? height : width; |
| 707 | var read = function (i) { return (axis ? bin[i * width + cx] : bin[cy * width + i]) === 1; }; |
| 708 | var from = axis ? cy : cx; |
| 709 | if (from < 0 || from >= limit || !read(from)) return null; |
| 710 | var cap = Math.max(3, module * 4); |
| 711 | |
| 712 | var lo = from, hi = from; |
| 713 | while (lo - 1 >= 0 && read(lo - 1)) lo--; |
| 714 | while (hi + 1 < limit && read(hi + 1)) hi++; |
| 715 | var c = [0, 0, hi - lo + 1, 0, 0]; |
| 716 | |
| 717 | var i = lo - 1; |
| 718 | while (i >= 0 && !read(i) && c[1] <= cap) { c[1]++; i--; } |
| 719 | while (i >= 0 && read(i) && c[0] <= cap) { c[0]++; i--; } |
| 720 | i = hi + 1; |
| 721 | while (i < limit && !read(i) && c[3] <= cap) { c[3]++; i++; } |
| 722 | while (i < limit && read(i) && c[4] <= cap) { c[4]++; i++; } |
| 723 | |
| 724 | if (!isFinderRun(c)) return null; |
| 725 | return (lo + hi) / 2; |
| 726 | } |
| 727 | |
| 728 | /// Every finder-like pattern the picture holds, with its module pitch. |
| 729 | function finders(bin, width, height) { |
| 730 | var found = []; |
| 731 | var add = function (x, y, module) { |
| 732 | for (var i = 0; i < found.length; i++) { |
| 733 | var p = found[i]; |
| 734 | if (Math.abs(p.x - x) <= module && Math.abs(p.y - y) <= module |
| 735 | && Math.abs(p.module - module) <= Math.max(1, module / 2)) { |
| 736 | p.x = (p.x * p.count + x) / (p.count + 1); |
| 737 | p.y = (p.y * p.count + y) / (p.count + 1); |
| 738 | p.module = (p.module * p.count + module) / (p.count + 1); |
| 739 | p.count++; |
| 740 | return; |
| 741 | } |
| 742 | } |
| 743 | found.push({ x: x, y: y, module: module, count: 1 }); |
| 744 | }; |
| 745 | |
| 746 | for (var y = 0; y < height; y++) { |
| 747 | var row = runs(bin, width, height, y, 0); |
| 748 | for (var i = 0; i + 5 <= row.length; i++) { |
| 749 | if (!row[i].dark) continue; |
| 750 | var c = [row[i].n, row[i + 1].n, row[i + 2].n, row[i + 3].n, row[i + 4].n]; |
| 751 | if (!isFinderRun(c)) continue; |
| 752 | var module = (c[0] + c[1] + c[2] + c[3] + c[4]) / 7; |
| 753 | var cx0 = Math.round(midRun(row[i + 2])); |
| 754 | var cy = crossCheck(bin, width, height, cx0, y, module, 1); |
| 755 | if (cy === null) continue; |
| 756 | var cx = crossCheck(bin, width, height, cx0, Math.round(cy), module, 0); |
| 757 | if (cx === null) continue; |
| 758 | add(cx, cy, module); |
| 759 | } |
| 760 | } |
| 761 | return found.filter(function (p) { return p.count >= 2; }); |
| 762 | } |
| 763 | |
| 764 | function dist(a, b) { return Math.hypot(a.x - b.x, a.y - b.y); } |
| 765 | |
| 766 | /// The three of them that form a code, in reading order: a right-angled |
| 767 | /// isosceles triangle with the right angle at the top left. |
| 768 | function triple(all) { |
| 769 | var best = null; |
| 770 | for (var i = 0; i < all.length; i++) { |
| 771 | for (var j = i + 1; j < all.length; j++) { |
| 772 | for (var k = j + 1; k < all.length; k++) { |
| 773 | var fit = fitTriple(all[i], all[j], all[k]); |
| 774 | if (fit && (!best || fit.error < best.error)) best = fit; |
| 775 | } |
| 776 | } |
| 777 | } |
| 778 | return best; |
| 779 | } |
| 780 | |
| 781 | function fitTriple(a, b, c) { |
| 782 | var ab = dist(a, b), bc = dist(b, c), ac = dist(a, c); |
| 783 | // The vertex is opposite the longest side. |
| 784 | var v, p, q; |
| 785 | if (bc >= ab && bc >= ac) { v = a; p = b; q = c; } |
| 786 | else if (ac >= ab && ac >= bc) { v = b; p = a; q = c; } |
| 787 | else { v = c; p = a; q = b; } |
| 788 | var d1 = dist(v, p), d2 = dist(v, q), hyp = dist(p, q); |
| 789 | if (!d1 || !d2) return null; |
| 790 | var legs = Math.abs(d1 - d2) / Math.max(d1, d2); |
| 791 | if (legs > 0.3) return null; |
| 792 | var right = Math.abs(hyp - Math.hypot(d1, d2)) / hyp; |
| 793 | if (right > 0.2) return null; |
| 794 | var sizes = [a.module, b.module, c.module]; |
| 795 | var mean = (sizes[0] + sizes[1] + sizes[2]) / 3; |
| 796 | var spread = Math.max(Math.abs(sizes[0] - mean), Math.abs(sizes[1] - mean), |
| 797 | Math.abs(sizes[2] - mean)) / mean; |
| 798 | if (spread > 0.5) return null; |
| 799 | // Which of the two is the top right is the handedness of the pair about |
| 800 | // the vertex, and handedness survives rotation -- which is what lets a |
| 801 | // code held sideways be read without trying four ways. |
| 802 | var turn = (p.x - v.x) * (q.y - v.y) - (p.y - v.y) * (q.x - v.x); |
| 803 | return { |
| 804 | error: legs + right + spread, |
| 805 | topLeft: v, |
| 806 | topRight: turn > 0 ? p : q, |
| 807 | bottomLeft: turn > 0 ? q : p, |
| 808 | module: mean, |
| 809 | }; |
| 810 | } |
| 811 | |
| 812 | // ── The perspective ──────────────────────────────────────── |
| 813 | // A code photographed off-axis is a projective image of a square, so the map |
| 814 | // from module coordinates to picture coordinates is a homography. |
| 815 | |
| 816 | /// The homography taking the unit square's corners to four points. |
| 817 | function squareTo(p) { |
| 818 | var p0 = p[0], p1 = p[1], p2 = p[2], p3 = p[3]; |
| 819 | var dx3 = p0.x - p1.x + p2.x - p3.x; |
| 820 | var dy3 = p0.y - p1.y + p2.y - p3.y; |
| 821 | if (Math.abs(dx3) < 1e-9 && Math.abs(dy3) < 1e-9) { |
| 822 | return [p1.x - p0.x, p3.x - p0.x, p0.x, |
| 823 | p1.y - p0.y, p3.y - p0.y, p0.y, |
| 824 | 0, 0, 1]; |
| 825 | } |
| 826 | var dx1 = p1.x - p2.x, dx2 = p3.x - p2.x; |
| 827 | var dy1 = p1.y - p2.y, dy2 = p3.y - p2.y; |
| 828 | var den = dx1 * dy2 - dx2 * dy1; |
| 829 | if (!den) return null; |
| 830 | var a = (dx3 * dy2 - dx2 * dy3) / den; |
| 831 | var b = (dx1 * dy3 - dx3 * dy1) / den; |
| 832 | return [p1.x - p0.x + a * p1.x, p3.x - p0.x + b * p3.x, p0.x, |
| 833 | p1.y - p0.y + a * p1.y, p3.y - p0.y + b * p3.y, p0.y, |
| 834 | a, b, 1]; |
| 835 | } |
| 836 | |
| 837 | /// The adjugate, which inverts a homography up to a scale that cancels. |
| 838 | function adjugate(m) { |
| 839 | return [ |
| 840 | m[4] * m[8] - m[5] * m[7], m[2] * m[7] - m[1] * m[8], m[1] * m[5] - m[2] * m[4], |
| 841 | m[5] * m[6] - m[3] * m[8], m[0] * m[8] - m[2] * m[6], m[2] * m[3] - m[0] * m[5], |
| 842 | m[3] * m[7] - m[4] * m[6], m[1] * m[6] - m[0] * m[7], m[0] * m[4] - m[1] * m[3], |
| 843 | ]; |
| 844 | } |
| 845 | |
| 846 | function matMul(a, b) { |
| 847 | var out = new Array(9); |
| 848 | for (var r = 0; r < 3; r++) { |
| 849 | for (var c = 0; c < 3; c++) { |
| 850 | var s = 0; |
| 851 | for (var k = 0; k < 3; k++) s += a[r * 3 + k] * b[k * 3 + c]; |
| 852 | out[r * 3 + c] = s; |
| 853 | } |
| 854 | } |
| 855 | return out; |
| 856 | } |
| 857 | |
| 858 | function applyH(m, x, y) { |
| 859 | var w = m[6] * x + m[7] * y + m[8]; |
| 860 | return { x: (m[0] * x + m[1] * y + m[2]) / w, y: (m[3] * x + m[4] * y + m[5]) / w }; |
| 861 | } |
| 862 | |
| 863 | /// The homography from module space to picture space, from four pairs. |
| 864 | function transform(from, to) { |
| 865 | var a = squareTo(to); |
| 866 | var b = squareTo(from); |
| 867 | if (!a || !b) return null; |
| 868 | return matMul(a, adjugate(b)); |
| 869 | } |
| 870 | |
| 871 | /// Look for an alignment pattern near where one is expected. It is the |
| 872 | /// fourth correspondence, and it is what makes a skewed code read. |
| 873 | function findAlignment(bin, width, height, cx, cy, module) { |
| 874 | var span = Math.max(3, Math.ceil(module * 3)); |
| 875 | var top = Math.max(0, Math.round(cy - span)); |
| 876 | var foot = Math.min(height - 1, Math.round(cy + span)); |
| 877 | var left = Math.max(0, Math.round(cx - span)); |
| 878 | var right = Math.min(width - 1, Math.round(cx + span)); |
| 879 | var best = null; |
| 880 | for (var y = top; y <= foot; y++) { |
| 881 | // The pattern's own middle row is light, dark, light, one module each. |
| 882 | var row = runs(bin, width, height, y, 0); |
| 883 | for (var i = 0; i + 3 <= row.length; i++) { |
| 884 | if (row[i].dark) continue; |
| 885 | if (!isAlignRun([row[i].n, row[i + 1].n, row[i + 2].n], module)) continue; |
| 886 | var px = midRun(row[i + 1]); |
| 887 | if (px < left || px > right) continue; |
| 888 | var py = alignVertical(bin, width, height, Math.round(px), y, module); |
| 889 | if (py === null) continue; |
| 890 | var d = Math.hypot(px - cx, py - cy); |
| 891 | if (!best || d < best.d) best = { d: d, x: px, y: py }; |
| 892 | } |
| 893 | } |
| 894 | return best; |
| 895 | } |
| 896 | |
| 897 | /// Whether three runs are the alignment pattern's 1:1:1 at this pitch. |
| 898 | function isAlignRun(c, module) { |
| 899 | var tol = Math.max(0.8, module * 0.7); |
| 900 | return Math.abs(c[0] - module) <= tol && Math.abs(c[1] - module) <= tol |
| 901 | && Math.abs(c[2] - module) <= tol; |
| 902 | } |
| 903 | |
| 904 | /// The same check down the column, and where the centre module sits. |
| 905 | function alignVertical(bin, width, height, cx, cy, module) { |
| 906 | if (cx < 0 || cx >= width) return null; |
| 907 | var read = function (i) { return bin[i * width + cx] === 1; }; |
| 908 | if (!read(cy)) return null; |
| 909 | var lo = cy, hi = cy; |
| 910 | while (lo - 1 >= 0 && read(lo - 1)) lo--; |
| 911 | while (hi + 1 < height && read(hi + 1)) hi++; |
| 912 | var cap = Math.max(3, module * 3); |
| 913 | var above = 0, i = lo - 1; |
| 914 | while (i >= 0 && !read(i) && above <= cap) { above++; i--; } |
| 915 | var below = 0; |
| 916 | i = hi + 1; |
| 917 | while (i < height && !read(i) && below <= cap) { below++; i++; } |
| 918 | if (!isAlignRun([above, hi - lo + 1, below], module)) return null; |
| 919 | return (lo + hi) / 2; |
| 920 | } |
| 921 | |
| 922 | /// Sample the module at (x, y) of the grid, as the pitch allows. |
| 923 | function sampleAt(bin, width, height, m, x, y, module) { |
| 924 | var step = module >= 3 ? module / 4 : 0; |
| 925 | var offs = step |
| 926 | ? [[0, 0], [-step, 0], [step, 0], [0, -step], [0, step]] |
| 927 | : [[0, 0]]; |
| 928 | var dark = 0, seen = 0; |
| 929 | var p = applyH(m, x + 0.5, y + 0.5); |
| 930 | for (var i = 0; i < offs.length; i++) { |
| 931 | var px = Math.round(p.x + offs[i][0]); |
| 932 | var py = Math.round(p.y + offs[i][1]); |
| 933 | if (px < 0 || py < 0 || px >= width || py >= height) continue; |
| 934 | seen++; |
| 935 | dark += bin[py * width + px]; |
| 936 | } |
| 937 | if (!seen) return 0; |
| 938 | return dark * 2 > seen ? 1 : 0; |
| 939 | } |
| 940 | |
| 941 | /// Read a matrix of `size` modules out of the picture. |
| 942 | function sampleGrid(bin, width, height, spot, size) { |
| 943 | var half = 3.5; |
| 944 | var from = [ |
| 945 | { x: half, y: half }, |
| 946 | { x: size - half, y: half }, |
| 947 | spot.align ? { x: size - 6.5, y: size - 6.5 } : { x: size - half, y: size - half }, |
| 948 | { x: half, y: size - half }, |
| 949 | ]; |
| 950 | var to = [spot.topLeft, spot.topRight, spot.align || spot.bottomRight, spot.bottomLeft]; |
| 951 | var m = transform(from, to); |
| 952 | if (!m) return null; |
| 953 | var cells = new Uint8Array(size * size); |
| 954 | for (var y = 0; y < size; y++) { |
| 955 | for (var x = 0; x < size; x++) { |
| 956 | cells[y * size + x] = sampleAt(bin, width, height, m, x, y, spot.module); |
| 957 | } |
| 958 | } |
| 959 | return cells; |
| 960 | } |
| 961 | |
| 962 | /// Read a code out of a picture. |
| 963 | /// |
| 964 | /// `frame` is an ImageData, or anything with `width`, `height` and RGBA |
| 965 | /// `data`. Answers null when there is nothing there to read -- which is the |
| 966 | /// ordinary answer on most frames of a camera stream, not a failure. |
| 967 | function decode(frame) { |
| 968 | if (!frame || !frame.data || !frame.width) return null; |
| 969 | var width = frame.width, height = frame.height; |
| 970 | var bin = binarise(luminance(frame), width, height); |
| 971 | var all = finders(bin, width, height); |
| 972 | if (all.length < 3) return null; |
| 973 | // The strongest candidates first: a picture of a code on a page holds |
| 974 | // more finder-like runs than a code has finders. |
| 975 | all.sort(function (a, b) { return b.count - a.count; }); |
| 976 | var spot = triple(all.slice(0, 8)); |
| 977 | if (!spot) return null; |
| 978 | |
| 979 | var across = dist(spot.topLeft, spot.topRight) / spot.module; |
| 980 | var down = dist(spot.topLeft, spot.bottomLeft) / spot.module; |
| 981 | var guess = Math.round((across + down) / 2) + 7; |
| 982 | |
| 983 | // The estimate is a division of two measured lengths, so it can land a |
| 984 | // version either side. Every legal width near it is tried, nearest first, |
| 985 | // and the first that reads is the answer -- a wrong width almost never |
| 986 | // survives the format check, let alone the Reed-Solomon. |
| 987 | var near = 17 + 4 * Math.round((guess - 17) / 4); |
| 988 | var widths = [near, near - 4, near + 4, near - 8, near + 8] |
| 989 | .filter(function (s) { return versionOf(s); }); |
| 990 | |
| 991 | for (var w = 0; w < widths.length; w++) { |
| 992 | var size = widths[w]; |
| 993 | // The bottom-right corner from the three finders, and then the |
| 994 | // alignment pattern that sits just inside it where there is one. |
| 995 | var bottomRight = { |
| 996 | x: spot.topRight.x - spot.topLeft.x + spot.bottomLeft.x, |
| 997 | y: spot.topRight.y - spot.topLeft.y + spot.bottomLeft.y, |
| 998 | }; |
| 999 | var align = null; |
| 1000 | if (size > 21) { |
| 1001 | var pull = 1 - 3 / (size - 7); |
| 1002 | var ex = spot.topLeft.x + pull * (bottomRight.x - spot.topLeft.x); |
| 1003 | var ey = spot.topLeft.y + pull * (bottomRight.y - spot.topLeft.y); |
| 1004 | align = findAlignment(bin, width, height, ex, ey, spot.module); |
| 1005 | } |
| 1006 | var tries = align ? [align, null] : [null]; |
| 1007 | for (var a = 0; a < tries.length; a++) { |
| 1008 | var cells = sampleGrid(bin, width, height, { |
| 1009 | topLeft: spot.topLeft, topRight: spot.topRight, |
| 1010 | bottomLeft: spot.bottomLeft, bottomRight: bottomRight, |
| 1011 | align: tries[a], module: spot.module, |
| 1012 | }, size); |
| 1013 | if (!cells) continue; |
| 1014 | var got = fromMatrix(cells, size); |
| 1015 | if (got) return got; |
| 1016 | } |
| 1017 | } |
| 1018 | return null; |
| 1019 | } |
| 1020 | |
| 1021 | /// RGBA pixels out of whatever was handed over. |
| 1022 | function pixels(source) { |
| 1023 | if (!source) return null; |
| 1024 | if (source.data && source.width) return source; |
| 1025 | if (typeof document === 'undefined') return null; |
| 1026 | var w = source.videoWidth || source.naturalWidth || source.width; |
| 1027 | var h = source.videoHeight || source.naturalHeight || source.height; |
| 1028 | if (!w || !h) return null; |
| 1029 | var canvas = document.createElement('canvas'); |
| 1030 | canvas.width = w; |
| 1031 | canvas.height = h; |
| 1032 | var ctx = canvas.getContext('2d', { willReadFrequently: true }); |
| 1033 | if (!ctx) return null; |
| 1034 | try { ctx.drawImage(source, 0, 0, w, h); } catch (e) { return null; } |
| 1035 | try { return ctx.getImageData(0, 0, w, h); } catch (e) { return null; } |
| 1036 | } |
| 1037 | |
| 1038 | /// Read a code from a video element, a canvas, an image or raw pixels. |
| 1039 | /// |
| 1040 | /// THE PLATFORM'S OWN READER FIRST. `BarcodeDetector` is hardware-backed and |
| 1041 | /// is what a phone's camera app uses; the decoder above is what Firefox and |
| 1042 | /// desktop Safari get instead. The answer has the same shape either way, so |
| 1043 | /// nothing above this call has to know which read it -- but `by` says, so a |
| 1044 | /// failure can be attributed to the right half. |
| 1045 | async function detect(source) { |
| 1046 | var Detector = (typeof window !== 'undefined') ? window.BarcodeDetector : null; |
| 1047 | if (Detector) { |
| 1048 | try { |
| 1049 | var kinds = await Detector.getSupportedFormats(); |
| 1050 | if (kinds && kinds.indexOf('qr_code') >= 0) { |
| 1051 | var reader = new Detector({ formats: ['qr_code'] }); |
| 1052 | var hits = await reader.detect(source); |
| 1053 | if (hits && hits.length) { |
| 1054 | return { text: hits[0].rawValue, by: 'BarcodeDetector', |
| 1055 | version: 0, ecc: null, mask: -1 }; |
| 1056 | } |
| 1057 | return null; |
| 1058 | } |
| 1059 | } catch (e) { /* the platform's reader is not usable; ours is */ } |
| 1060 | } |
| 1061 | var frame = pixels(source); |
| 1062 | if (!frame) return null; |
| 1063 | var got = decode(frame); |
| 1064 | if (!got) return null; |
| 1065 | got.by = 'daimond'; |
| 1066 | return got; |
| 1067 | } |
| 1068 | |
| 1069 | // ── Public surface ───────────────────────────────────────── |
| 1070 | // `fromMatrix` is published beside `decode` because it is the half the |
| 1071 | // encoder can be an oracle for: dev/verify_qrscan.mjs hands it the grid |
| 1072 | // `DaimondQR.matrix` produced, with no picture in between, so a failure |
| 1073 | // there is the codec and never the camera. |
| 1074 | window.DaimondQRScan = { |
| 1075 | decode: decode, |
| 1076 | detect: detect, |
| 1077 | fromMatrix: fromMatrix, |
| 1078 | pixels: pixels, |
| 1079 | binarise: binarise, |
| 1080 | luminance: luminance, |
| 1081 | capacity: capacity, |
| 1082 | versionOf: versionOf, |
| 1083 | widthOf: widthOf, |
| 1084 | maxVersion: MAX_VERSION, |
| 1085 | levels: ECC_OF, |
| 1086 | }; |
| 1087 | })(); |