| 1 | // GF(256) and Reed–Solomon, for the QR encoder. |
| 2 | // |
| 3 | // Split from qr.js only because of the 300-line cap, but the split is honest: |
| 4 | // this half is pure finite-field arithmetic with no knowledge of QR at all, |
| 5 | // and it is the half that is easiest to check against a textbook. |
| 6 | // |
| 7 | // The field is GF(2^8) with the QR primitive polynomial 0x11D, generator 2. |
| 8 | |
| 9 | const EXP = new Uint8Array(512); |
| 10 | const LOG = new Uint8Array(256); |
| 11 | |
| 12 | (function buildTables() { |
| 13 | let x = 1; |
| 14 | for (let i = 0; i < 255; i++) { |
| 15 | EXP[i] = x; |
| 16 | LOG[x] = i; |
| 17 | x <<= 1; |
| 18 | if (x & 0x100) x ^= 0x11d; |
| 19 | } |
| 20 | // The second half repeats the first, so a product's exponent never needs a |
| 21 | // modulo in the hot path. |
| 22 | for (let i = 255; i < 512; i++) EXP[i] = EXP[i - 255]; |
| 23 | })(); |
| 24 | |
| 25 | export function mul(a, b) { |
| 26 | if (a === 0 || b === 0) return 0; |
| 27 | return EXP[LOG[a] + LOG[b]]; |
| 28 | } |
| 29 | |
| 30 | // generatorPoly returns the degree-n generator, (x - 2^0)(x - 2^1)…, whose |
| 31 | // roots are what the decoder checks against. |
| 32 | export function generatorPoly(n) { |
| 33 | let g = [1]; |
| 34 | for (let i = 0; i < n; i++) { |
| 35 | const next = new Array(g.length + 1).fill(0); |
| 36 | for (let j = 0; j < g.length; j++) { |
| 37 | next[j] ^= g[j]; |
| 38 | next[j + 1] ^= mul(g[j], EXP[i]); |
| 39 | } |
| 40 | g = next; |
| 41 | } |
| 42 | return g; |
| 43 | } |
| 44 | |
| 45 | // remainder is the error-correction codewords for one block: polynomial |
| 46 | // division of the data by the generator, keeping the remainder. |
| 47 | export function remainder(data, ecLen) { |
| 48 | const gen = generatorPoly(ecLen); |
| 49 | const out = new Uint8Array(ecLen); |
| 50 | for (const byte of data) { |
| 51 | const factor = byte ^ out[0]; |
| 52 | out.copyWithin(0, 1); |
| 53 | out[ecLen - 1] = 0; |
| 54 | if (factor !== 0) { |
| 55 | for (let i = 0; i < ecLen; i++) out[i] ^= mul(gen[i + 1], factor); |
| 56 | } |
| 57 | } |
| 58 | return out; |
| 59 | } |
| 60 | |
amadan