Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 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 | 18x 18x 18x 18x 18x 4590x 4590x 4590x 4590x 4626x 1668x 255x 4221971x 4221969x 743x 742x 741x 1411x 1411x 14780x 14780x 14779x 29557x 1411x | /**
* Arithmetic in GF(256), the field QR codes use for Reed–Solomon error
* correction (ISO/IEC 18004 §7.5.2).
*
* The field is generated by the primitive polynomial
* `x^8 + x^4 + x^3 + x^2 + 1` (0x11D). Multiplication is done through
* log/antilog tables so it costs two lookups and an addition instead of a
* carry-less multiply loop.
*/
/** The primitive polynomial that generates GF(256) for QR codes. */
export const PRIMITIVE = 0x11d;
/**
* `EXP[i] = α^i`. Doubled to 512 entries so `EXP[LOG[a] + LOG[b]]` never needs
* a modulo — the sum of two logs is at most 508.
*/
const EXP = new Uint8Array(512);
/** `LOG[α^i] = i`. `LOG[0]` is undefined mathematically and left at 0. */
const LOG = new Uint8Array(256);
{
let x = 1;
for (let i = 0; i < 255; i++) {
EXP[i] = x;
LOG[x] = i;
x <<= 1;
if (x & 0x100) x ^= PRIMITIVE;
}
for (let i = 255; i < 512; i++) EXP[i] = EXP[i - 255]!;
}
/** `α^exponent`, for any non-negative exponent (wraps at 255). */
export function gfExp(exponent: number): number {
return EXP[exponent % 255]!;
}
/** The discrete log of `value` base α. Undefined for 0. */
export function gfLog(value: number): number {
return LOG[value]!;
}
/** Multiplication in GF(256). */
export function gfMul(a: number, b: number): number {
if (a === 0 || b === 0) return 0;
return EXP[LOG[a]! + LOG[b]!]!;
}
/** Division in GF(256). Dividing by zero throws — it is a programming error. */
export function gfDiv(a: number, b: number): number {
if (b === 0) throw new RangeError("Division by zero in GF(256)");
if (a === 0) return 0;
return EXP[(LOG[a]! - LOG[b]! + 255) % 255]!;
}
/**
* Multiply two polynomials over GF(256). Coefficients are stored
* highest-degree-first, matching the convention used by the Reed–Solomon
* generator polynomials.
*/
export function polyMul(a: Readonly<Uint8Array>, b: Readonly<Uint8Array>): Uint8Array {
const result = new Uint8Array(a.length + b.length - 1);
for (let i = 0; i < a.length; i++) {
const ai = a[i]!;
if (ai === 0) continue;
for (let j = 0; j < b.length; j++) {
result[i + j] ^= gfMul(ai, b[j]!);
}
}
return result;
}
|