Skip to content

Instantly share code, notes, and snippets.

@bellbind

bellbind/bitstream.js

Last active February 20, 2022 05:28
Show Gist options
  • Save bellbind/a057eee7e532f63f71d164fa7c8342a0 to your computer and use it in GitHub Desktop.
Save bellbind/a057eee7e532f63f71d164fa7c8342a0 to your computer and use it in GitHub Desktop.
Download ZIP
[JavaScript] QR code generator from scratch
Raw
bitstream.js
// big endian bit stream
export class BitWriter {
constructor(buf = [], byte = 0, pos = 7) {
this.byte = byte;
this.pos = pos;
this.buf = Array.from(buf);
}
writeBit(b) {
this.byte |= (b & 1) << this.pos;
this.pos--;
if (this.pos < 0) {
this.buf.push(this.byte);
this.byte = 0;
this.pos = 7;
}
}
write(value, n) {
for (let i = n - 1; i >= 0; i--) this.writeBit((value >>> i) & 1);
}
writeBytes(bytes) {
if (this.pos < 7) {
this.buf.push(this.byte);
this.byte = 0;
this.pos = 7;
}
for (const v of bytes) this.buf.push(v);
}
toBuffer() {
const bytes = this.buf.slice();
if (this.pos < 7) bytes.push(this.byte);
return new Uint8Array(bytes);
}
bitLength() {
return this.buf.length * 8 + (7 - this.pos);
}
byteLength() {
return this.buf.length + (this.pos === 7 ? 0 : 1);
}
}
export class BitReader {
constructor(buf, index = 0, pos = 7) {
this.buf = Uint8Array.from(buf);
this.index = index;
this.pos = pos;
}
isEnd() {
return this.index >= this.buf.length;
}
canReadBits(n) {
const finished = this.index * 8 + 7 - this.pos;
return finished + n <= this.buf.length * 8;
}
readBit() {
if (this.isEnd()) throw Error(`no enough bytes`);
const b = (this.buf[this.index] >>> this.pos) & 1;
this.pos--;
if (this.pos < 0) {
this.pos = 7;
this.index++;
}
return b;
}
read(n) {
let r = 0;
for (let i = n - 1; i >= 0; i--) r |= this.readBit() << i;
return r;
}
readBytes(n = 1) {
// drop incomplete reading byte
if (this.pos < 7) {
this.index++;
this.pos = 7;
}
if (this.index + n > this.buf.length) throw Error(`no enough bytes`);
const slice = this.buf.slice(this.index, this.index + n);
this.index += n;
return slice;
}
}
Raw
cp2sjis.js
const t = new Map(), rev = new Map();
export const has = c => t.has(c);
export const get = c => t.get(c);
export const toChar = j => rev.get(j);
try {
const td = new TextDecoder("shift_jis", {fatal: true});
const dv = new DataView(new ArrayBuffer(2));
const putSjis = code => {
dv.setUint16(0, code, false);
try {
const ch = td.decode(dv);
t.set(ch, code);
rev.set(code, ch);
} catch (err) {}
};
for (let code = 0x8140; code <= 0x9ffc; code++) putSjis(code);
for (let code = 0xe040; code <= 0xebbf; code++) putSjis(code);
} catch (error) {
console.info("[INFO] cp2sjis.js depends on SJIS supported TextDecoer, but");
console.info(error);
}
Raw
gen-cp2sjis.js
// $ node gen-cp2sjis.js > cp2sjis.js
try {
const td = new TextDecoder("shift_jis", {fatal: true});
const dv = new DataView(new ArrayBuffer(2));
const t = [];
const putSjis = code => {
dv.setUint16(0, code, false);
try {
const ch = td.decode(dv);
t.push([ch, code]);
} catch (err) {}
};
for (let code = 0x8140; code <= 0x9ffc; code++) putSjis(code);
for (let code = 0xe040; code <= 0xebbf; code++) putSjis(code);
const entries = t.map(
([ch, code]) => `["\\u{${ch.codePointAt(0).toString(16)}}", ${code}]`
//kv => JSON.stringify(kv)
).join(",");
console.log(`
const t = new Map([${entries}]), rev = new Map();
for (const [ch, code] of t) rev.set(code,ch);
export const has = c => t.has(c);
export const get = c => t.get(c);
export const toChar = j => rev.get(j);
`);
} catch (error) {
console.info("[INFO] cp2sjis.js depends on SJIS supported TextDecoer, but");
console.info(error);
}
Raw
package.json
{"type": "module"}
Raw
qr-code-element-example.html
<!doctype html>
<html>
<head>
<script type="module" src="./qr-code.js"></script>
</head>
<body>
<h1><code>qr-code</code> custom element</h1>
<div>
<label>text: <input value="Hello World!" size="80" oninput="
document.querySelector('qr-code').dataset.text = this.value;"></label>
</div>
<qr-code data-text="Hello World!" data-quarity="M" data-scale="4"
data-style="border: solid; width: 50vmin; height: 50vmin;"
></qr-code>
</body>
</html>
Raw
qr-code.js
import * as qrcode from "./qrcode.js";
class QRCode extends HTMLElement {
constructor(opts = {}) {
super();
Object.assign(this.dataset, opts);
this.attachShadow({mode: "open"});
this.observer = new MutationObserver(muts => this.update());
}
connectedCallback() {
this.update();
this.observer.observe(this, {attributes: true});
}
disconnectedCallback() {
this.observer.disconnect();
}
update() {
const {text = "", quarity = "Q", scale = 8, style = ""} = this.dataset;
const {frame, width} = qrcode.qrcode(text, quarity);
this.shadowRoot.innerHTML = qrcode.svg(frame, width, scale >>> 0);
this.shadowRoot.firstElementChild.setAttribute("style", style);
}
}
customElements.define("qr-code", QRCode);
Raw
qrauto.js
import * as cp2sjis from "./cp2sjis.js";
import {BitWriter} from "./bitstream.js";
import {
lengthBit, alphaNumTable, bitNumbers, bitAlphaNums, bitBytes, bitKanjis,
terminateData, addNumbers, addAlphaNums, addBytes, addKanjis,
} from "./qrdata.js";
import {dataBytes} from "./qrmessage.js";
// find version to fit bytes
export const minVersion = (qi, bytes) => {
for (let v = 1; v <= 40; v++) if (dataBytes(v, qi) >= bytes) return v;
return -1; // overflow data
};
// heqp queue
export const heapPush = (queue, less, elem) => {
queue.push(elem);
let idx = queue.length - 1;
while (idx > 0) {
const parent = (idx - 1) >>> 1;
if (less(elem, queue[parent])) {
[queue[idx], queue[parent], idx] = [queue[parent], elem, parent];
} else break;
}
};
export const heapPop = (queue, less) => {
const ret = queue[0], elem = queue.pop();
if (queue.length === 0) return ret;
queue[0] = elem;
let idx = 0;
for (let l = idx * 2 + 1; l < queue.length; l = idx * 2 + 1) {
const r = l + 1;
const child = (r < queue.length && less(queue[r], queue[l])) ? r : l;
if (less(queue[child], elem)) {
[queue[idx], queue[child], idx] = [queue[child], elem, child];
} else break;
}
return ret;
};
// split runs of same type char in bytes
const nums = new Set(alphaNumTable.slice(0, 10));
const alphas = new Set(alphaNumTable.slice(10));
export const toRuns = (text, useKanji = true) => {
const te = new TextEncoder();
const r = [];
let mode = -1, s = 0, i = 0, ts = 0, ti = 0;
for (const ch of text) { // for surrogate pair
const cmode = nums.has(ch) ? 0 : alphas.has(ch) ? 1 :
useKanji && cp2sjis.has(ch) ? 3 : 2;
if (cmode !== mode) {
if (mode >= 0) r.push({mode, s, e: i, ts, te: ti});
[mode, s, ts] = [cmode, i, ti];
}
ti += ch.length; // for surrogate pair
i += te.encode(ch).length;
}
if (mode >= 0) r.push({mode, s, e: i, ts, te: ti});
return r;
};
// bit size as score of chunks
export const bits = (mode, version, len, tlen) => {
if (mode === 0) return bitNumbers(version, len);
if (mode === 1) return bitAlphaNums(version, len);
if (mode === 2) return bitBytes(version, len);
if (mode === 3) return bitKanjis(version, tlen);
return bitBytes(version, len);
};
export const guessChunks = (qi, runs, v) => {
//const maxlen = bytes.length;
const maxlen = runs[runs.length - 1].e;
// A*/Dijkstra-algorithm (heuristic distance: bytelen * 3)
const chunk = (mode, s, e, ts, te, prev) => ({
mode, s, e, ts, te, bits: prev.bits + bits(mode, v, e - s, te - ts)});
const node = (head, mode, run, last) => {
const prevs = mode !== last.mode ? head.chunks : head.chunks.slice(0, -1);
const tail = mode !== last.mode ?
chunk(mode, run.s, run.e, run.ts, run.te, last) :
chunk(mode, last.s, run.e, last.ts, run.te,
head.chunks[head.chunks.length - 2]);
const score = tail.bits + (maxlen - run.e) * 3;
return {cur: head.cur + 1, score, chunks: [...prevs, tail]};
};
const queue = [], less = (a, b) => a.score < b.score;
const root = {mode: -1, s: 0, e: 0, bits: 0};
queue.push({cur: 0, score: (maxlen - runs[0].s) * 3, chunks: [root]});
while (queue.length > 0) {
const head = heapPop(queue, less);
if (head.cur === runs.length) return head.chunks.slice(1);
const run = runs[head.cur];
const last = head.chunks[head.chunks.length - 1];
if (run.mode === 0) {
heapPush(queue, less, node(head, 0, run, last));
heapPush(queue, less, node(head, 1, run, last));
if (last.mode === 2) heapPush(queue, less, node(head, 2, run, last));
} else if (run.mode === 1) {
heapPush(queue, less, node(head, 1, run, last));
heapPush(queue, less, node(head, 2, run, last));
} else if (run.mode === 3) {
heapPush(queue, less, node(head, 3, run, last));
heapPush(queue, less, node(head, 2, run, last));
} else {
heapPush(queue, less, node(head, 2, run, last));
}
}
throw Error("never reached");
};
export const byteSize = (chunks, version) => chunks.reduce(
(r, ch) => r + bits(ch.mode, version, ch.e - ch.s, ch.te - ch.ts), 0) / 8;
export const guessChunksRec = (qi, runs, v0, runSize = 19) => {
const chunks = [];
for (let i = 0; i < runs.length; i += runSize) {
// guessChunks is O(run.length^2). Split shorter runs with runSize param
const part = guessChunks(qi, runs.slice(i, i + runSize), v0);
if (chunks.length > 0 && chunks[chunks.length - 1].mode === part[0].mode) {
chunks[chunks.length - 1].e = part[0].e;
chunks[chunks.length - 1].te = part[0].te;
chunks.push(...part.slice(1));
} else {
chunks.push(...part);
}
}
if (chunks.length === runs.length) return chunks;
return guessChunksRec(qi, chunks, v0, runSize >= 11 ? runSize - 2 : 11);
};
export const guess = (qi, text, useKanji = true) => {
if (text.length === 0) {
const v = 1;
const bw = new BitWriter();
const datalen = dataBytes(v, qi);
terminateData(bw, datalen);
return [bw, v];
}
const max = dataBytes(40, qi);
if (Math.ceil(bitNumbers(40, text.length) / 8) > max) throw Error(
`text is too long: ${text.length}`);
const runs = toRuns(text, useKanji);
const bytelen = runs[runs.length - 1].e;
const v0 = bytelen + 3 > max ? 40 : minVersion(qi, bytelen + 3);
const chunks = guessChunksRec(qi, runs, v0);
const size = byteSize(chunks, v0);
if (size > max) throw Error(`Too large text: ${size}-byte (max: ${max})`);
const v = minVersion(qi, size);
const datalen = dataBytes(v, qi);
const bw = new BitWriter();
for (const {mode, s, e, ts, te} of chunks) {
const str = text.slice(ts, te);
if (mode === 0) addNumbers(bw, v, str);
if (mode === 1) addAlphaNums(bw, v, str);
if (mode === 3) addKanjis(bw, v, str);
if (mode === 2) addBytes(bw, v, str);
}
terminateData(bw, datalen);
return [bw, v];
};
Raw
qrcapture-example.html
<!doctype html>
<html>
<head>
<script type="module">
import {binarize, captureFinders, toFrame} from "./qrcapture.js";
import {svg} from "./qrimagedata.js";
import {qrdecode} from "./qrdecode.js";
const plot = (c2d, x, y, r, color) => {
c2d.save();
c2d.fillStyle = color;
c2d.beginPath();
c2d.arc(x, y, r, 0, 2 * Math.PI);
c2d.closePath();
c2d.fill();
c2d.restore();
};
const mask = (c2d, x, y, w, h, color) => {
c2d.save();
c2d.fillStyle = color;
c2d.fillRect(x, y, w, h);
c2d.restore();
};
document.getElementById("capture").addEventListener("click", ev => {
(async () => {
const video = document.createElement("video");
const camera = document.getElementById("camera");
const cellsView = document.getElementById("cells");
const c2d = camera.getContext("2d");
const finderColors = ["red", "green", "blue"]; // tl, tr, bl
const alignmentColor = "magenta";
video.addEventListener("play", ev => {
console.log("video:play");
camera.width = video.videoWidth;
camera.height = video.videoHeight;
document.getElementById("size").textContent =
`camera ${video.videoWidth}x${video.videoHeight}`;
const w = Math.min(video.videoWidth, video.videoHeight);
const offsx = (camera.width - w) >>> 1;
const offsy = (camera.height - w) >>> 1;
requestAnimationFrame(function capture() {
c2d.drawImage(video, 0, 0, c2d.canvas.width, c2d.canvas.height);
const image = c2d.getImageData(offsx, offsy, w, w);
mask(c2d, offsx, offsy, w, w, "rgba(0, 0, 0, 0.25)");
const [bin, colors] = binarize(image);
const finders = captureFinders(bin, w);
if (finders.length === 3) {
try {
const [frame, width, cellH, cellV, alignment] =
toFrame(finders, bin, w);
if (frame) {
const scale = 4;
const cw = (cellH + cellV) / 2;
for (let i = 0; i < 3; i++) {
const {x, y} = finders[i];
plot(c2d, offsx + x, offsy + y, cw * 3, finderColors[i]);
}
if (alignment) {
const {x, y} = alignment;
plot(c2d, offsx + x, offsy + y, cw, alignmentColor);
}
try {
const text = qrdecode(frame, width);
document.getElementById("text").textContent = text;
cellsView.innerHTML =
`size: ${width}<br>${svg(frame, width, scale)}`;
} catch (error) {}
}
} catch (error) {
console.error(error);
}
}
requestAnimationFrame(capture);
});
});
//console.log(video);
try {
// Screen captire
//const media = await navigator.mediaDevices.getDisplayMedia(
// {auido: false, video: {cursor: "never"}});
// Rear camera
//const h = screen.orientation.type.startsWith("portrait");
const media = await navigator.mediaDevices.getUserMedia(
{auido: false, video: {
//NOTE: crash on android chrome when specified the size
//width: {ideal: 800}, height: {ideal: 800},
facingMode: "environment"}});
//console.log(media);
video.srcObject = media;
video.autoplay = true;
} catch (error) {
document.getElementById("log").prepend(error.toString());
}
})().catch(console.error);
}, {once: true});
</script>
</head>
<body>
<label>QR code capturing <button id="capture">start</button></label>
<spam id="size"></spam>
<hr />
<div><canvas id="camera" style="border: solid"></canvas></div>
<hr />
<div>result: <span id="text"></span></div>
<div id="cells"></div>
<hr />
<div id="log"></div>
</body>
</html>
Raw
qrcapture.js
// low quality image scanner for QR codes
const range = n => [...Array(n).keys()];
// Binarize width * height sized array of black as true
export const binarize = ({data, width, height}) => {
const len = width * height, w = width, h = height;
const colors = range(len).map(
i => 0.299 * data[i * 4] + 0.587 * data[i * 4 + 1] +
0.114 * data[i * 4 + 2]); //Y of YUV;
const diffs = range(len).map(i => {
const x = i % w, y = (i - x) / w;
if (x < 1 || w - 1 <= x || y < 1 || h - 1 <= y) return colors[i];
const dxx = colors[i - 1] - 2 * colors[i] + colors[i + 1];
const dyy = colors[i - w] - 2 * colors[i] + colors[i + w];
const dxy = (colors[i - 1 - w] + colors[i + 1 - w] +
colors[i - 1 + w] + colors[i + 1 + w]) / 4;
const md1 = Math.abs(dxx) > Math.abs(dyy) ? dxx : dyy;
return Math.abs(md1) > Math.abs(dxy) ? md1 : dxy;
});
const ave = diffs.reduce((r, c) => r + c, 0) / len;
const bin = diffs.map(c => c < ave);
return [bin, diffs];
};
// split binarized image as black or white runs for each rows
const binToHRuns = (bin, width) => range(width).map(y => {
const runs = [];
let cur = {j: y, b: false, s: 0, e: 0};
for (let x = 0; x < width; x++) {
const b = bin[y * width + x];
if (cur.b === b) cur.e = x + 1;
else if (cur.e !== 0) {
runs.push(cur);
cur = {j: y, b, s: x, e: x + 1};
}
}
runs.push(cur);
return runs;
});
// split binarized image as black or white runs for each columns
const binToVRuns = (bin, width) => range(width).map(x => {
const runs = [];
let cur = {j: x, b: false, s: 0, e: 0};
for (let y = 0; y < width; y++) {
const b = bin[y * width + x];
if (cur.b === b) cur.e = y + 1;
else if (cur.e !== 0) {
runs.push(cur);
cur = {j: x, b, s: y, e: y + 1};
}
}
runs.push(cur);
return runs;
});
// get finder candidates from black or white runs
const getFinders = (runs, width) => {
const finders = [];
for (let j = 0; j < width; j++) {
const lruns = runs[j];
if (lruns.length < 5) continue;
for (let i = 0; i < lruns.length - 4; i++) {
const cellW = (lruns[i + 4].e - lruns[i].s) / 7; //as finder width
if (cellW < 2) continue;
const lb = lruns[i], lw = lruns[i + 1], center = lruns[i + 2],
rw = lruns[i + 3], rb = lruns[i + 4];
const isFinder = Math.abs(lb.e - lb.s - cellW) < cellW &&
Math.abs(lw.e - lw.s - cellW) < cellW &&
Math.abs(center.e - center.s - 3 * cellW) < cellW &&
Math.abs(rw.e - rw.s - cellW) < cellW &&
Math.abs(rb.e - rb.s - cellW) < cellW ;
if (!isFinder) continue;
const connected = finders.find(f => {
const last = f[f.length - 1];
if (last.j !== j - 1) return false;
if (last.b !== center.b) return false;
if (last.s <= center.s && center.s < last.e) return true;
if (last.s < center.e && center.e <= last.e) return true;
if (last.e <= center.s || center.e <= last.s) return false;
const r = (center.e - center.s) / (last.e - last.s);
return 0.5 < r && r < 1.5;
});
if (connected) connected.push(center);
else finders.push([center]);
}
}
return finders.filter(f => f.length > 1).map(f => {
const i = f.reduce((r, l) => r + l.e + l.s, 0) / (2 * f.length);
const j = (f[0].j + f[f.length - 1].j) / 2;
const w = f.reduce((r, l) => r + l.e - l.s, 0) / (3 * f.length);
return {i, j, w};
});
};
// sort finder candidates
const sortFinders = (hfinders, vfinders, bin, width) => {
const {abs, round} = Math;
const filtered = hfinders.filter(
hf => vfinders.findIndex(
vf => Math.hypot(vf.j - hf.i, vf.i - hf.j) <= hf.w) >= 0);
if (filtered.length === 0) return [];
const ordered = filtered.map(({i, j, w}) => {
const b = bin[round(j) * width + round(i)];
const score = range(7 * 7).reduce((s, k) => {
const rem = k % 7, dx = rem - 3, dy = (k - rem) / 7 - 3;
const m = abs(dy) <= 1 && abs(dx) <= 1 ? b :
abs(dy) <= 2 && abs(dx) <= 2 ? !b : b;
return s + (bin[round(j + dy * w) * width + round(i + dx * w)] === m);
}, 0);
return {x: i, y: j, b, w, score};
}).sort((a, b) => b.score - a.score);
return ordered.filter(f => f.b === ordered[0].b);
};
// resolve location of 3 finders: [tl, tr, bl]
const resolveFinders = (finders) => {
const [a, b, c] = finders;
const ab = Math.hypot(b.x - a.x, b.y - a.y);
const bc = Math.hypot(c.x - b.x, c.y - b.y);
const ca = Math.hypot(a.x - c.x, a.y - c.y);
const toLR = (o, e1, e2) =>
(e1.x - o.x) * (e2.y - o.y) - (e1.y - o.y) * (e2.x - o.x) > 0 ?
[o, e1, e2] : [o, e2, e1];
return (bc > ab && bc > ca) ? toLR(a, b, c) :
(ca > ab && ca > bc) ? toLR(b, c, a) : toLR(c, a, b);
};
// get 3 finders from binarized image
export const captureFinders = (bin, width) => {
const vruns = binToVRuns(bin, width);
const hruns = binToHRuns(bin, width);
const hfinders = getFinders(hruns, width);
const vfinders = getFinders(vruns, width);
const finders = sortFinders(hfinders, vfinders, bin, width).slice(0, 3);
return finders.length === 3 ? resolveFinders(finders) : [];
};
// compute cell width/height and cell size
const toAngledRuns = (o, p, bin, width) => {
const {sign, abs, floor, ceil, max, min} = Math;
const op = [p.x - o.x, p.y - o.y];
const s = [o.x - op[0], o.y - op[1]];
const e = [p.x + op[0], p.y + op[1]];
const [m, n] = abs(op[0]) > abs(op[1]) ? [0, 1] : [1, 0];
const idx = abs(op[0]) > abs(op[1]) ? (i, j) => j * width + i :
(i, j) => i * width + j;
const angle = op[n] / op[m], di = sign(e[m] - s[m]);
const runs = [];
const is = max(floor(s[m]), 0), js = floor(s[n] + angle * (is - s[m]));
const last = min(ceil(e[m]), width);
let cur = {b: false, m, sm: is, sn: js, em: is, en: js};
for (let i = is; di * (last - i) > 0; i += di) {
if (i < 0 || i >= width) continue;
const j = floor(s[n] + angle * (i - s[m]));
const b = bin[idx(i, j)];
if (cur.b === b) {
cur.em = i;
cur.en = j;
} else if (cur.sm !== cur.em || cur.sn !== cur.en) {
runs.push(cur);
cur = {
b, m, i, j, sm: i, sn: j,
em: i + 1, en: floor(s[n] + angle * (i + 1 - s[m]))};
}
}
if (cur.sm !== cur.em || cur.sn !== cur.en) runs.push(cur);
return runs;
};
const indexOfAngledRun = (runs, p) => runs.findIndex(run => {
const v = run.m === 0 ? p.x : p.y;
return Math.min(run.sm, run.em) <= v && v < Math.max(run.sm, run.em);
});
const runsWidth = (runS, runE) =>
Math.hypot(runE.em - runS.sm, runE.en - runS.sn);
const resolveCellSize = ([tl, tr, bl], bin, width) => {
const hruns = toAngledRuns(tl, tr, bin, width);
const vruns = toAngledRuns(tl, bl, bin, width);
const htl = indexOfAngledRun(hruns, tl);
const htr = indexOfAngledRun(hruns, tr);
const vtl = indexOfAngledRun(vruns, tl);
const vbl = indexOfAngledRun(vruns, bl);
if (htl - 2 < 0 || htr - 2 < 0 || vtl - 2 < 0 || vbl - 2 < 0) {
return {size: 0};
}
if (htl + 2 >= hruns.length || htr + 2 >= hruns.length ||
vtl + 2 >= vruns.length || vbl + 2 >= vruns.length) return {size: 0};
const htlw = runsWidth(hruns[htl - 2], hruns[htl + 2]);
const htrw = runsWidth(hruns[htr - 2], hruns[htr + 2]);
const vtlw = runsWidth(vruns[vtl - 2], vruns[vtl + 2]);
const vblw = runsWidth(vruns[vbl - 2], vruns[vbl + 2]);
const cellH = (htlw + htrw) / 14;
const cellV = (vtlw + vblw) / 14;
const hsize = Math.hypot(tr.x - tl.x, tr.y - tl.y) / cellH + 6;
const vsize = Math.hypot(bl.x - tl.x, bl.y - tl.y) / cellV + 6;
const size = Math.round((hsize + vsize) / 8) * 4 + 1;
return {size, cellH, cellV};
};
// TBD: Alignment pattern
const findAlignment = ([tl, tr, bl], cellSize, cellH, cellV, bin, width) => {
const b = tl.b;
const br = {x: tr.x + (bl.x - tl.x), y: tr.y + (bl.y - tl.y)};
const prov = {
x: tl.x + (cellSize - 10) / (cellSize - 7) * (br.x - tl.x),
y: tl.y + (cellSize - 10) / (cellSize - 7) * (br.y - tl.y)};
if (cellSize < 25) return prov;
const hAsX = Math.abs(tr.x - tl.x) > Math.abs(tr.y - tl.y);
const dx = hAsX ? cellH : cellV, dy = hAsX ? cellV : cellH;
const hruns = binToHRuns(bin, width);
const align = findAlignmentAt(hruns, bin, width, b, prov, dx, dy);
return align ? align : prov;
};
const findAlignmentAt = (hruns, bin, width, b, prov, dx, dy) => {
const {abs, hypot, floor} = Math;
const w = (dx + dy) / 2;
const shruns = hruns.map(runs => runs.filter(run => {
if (run.b !== b) return false;
if (abs(run.e - run.s) > dx * 2) return false;
const x = (run.e + run.s) / 2, y = run.j + 0.5;
const dist = hypot(x - prov.x, y - prov.y);
if (dist > w * 8) return false;
if (bin[floor(y) * width + floor(x)] !== b) return false;
if (bin[floor(y - dy / 3) * width + floor(x)] !== b) return false;
if (bin[floor(y + dy / 3) * width + floor(x)] !== b) return false;
for (let i = 0; i < 25; i++) {
const rem = i % 5, s = rem - 2, t = (i - rem) / 5 - 2;
if (s === 0 && t === 0) continue;
if (abs(s) <= 1 && abs(t) <= 1) {
if (bin[floor(y + dy * t) * width + floor(x + dx * s)] === b) {
return false;
}
continue;
}
if (bin[floor(y + dy * t) * width + floor(x + dx * s)] !== b) {
return false;
}
}
return true;
})).flat();
if (shruns.length > 0) {
const s = shruns[0], e = shruns[shruns.length - 1];
return {x: (s.e + s.s + e.e + e.s) / 4 + 0.5, y: (s.j + e.j) / 2 + 0.5};
} else return null;
};
// matrix math
const mat3mul = (ma, mb) => {
const r = [[0, 0, 0], [0, 0, 0], [0, 0, 0]];
for (let i = 0; i < 3; i++) for (let k = 0; k < 3; k++) {
for (let j = 0; j < 3; j++) r[i][j] += ma[i][k] * mb[k][j];
}
return r;
};
//console.log(mat3mul(
// [[3.5, 25 - 3.5, 3.5], [3.5, 3.5, 25 - 3.5], [1, 1, 1]],
// [[1, 2, 3],[1, 2, 3],[1,2,3]]));
const mat3tr = m => range(3).map(i => range(3).map(j => m[j][i]));
const mat3scale = (m, c) => m.map(l => l.map(v => v * c));
const mat3submat = (m, i, j) => m.filter(
(l, mi) => mi !== i).map(l => l.filter((_, lj) => lj !== j));
const mat2det = m => m[0][0] * m[1][1] - m[0][1] * m[1][0];
const mat3adj = m => mat3tr(m.map(
(l, i) => l.map((_, j) => (-1) ** (i + j) * mat2det(mat3submat(m, i, j)))));
const mat3det = m => m[0].reduce(
(r, c, i) => r + (-1) ** i * c * mat2det(mat3submat(m, 0, i)), 0);
const mat3inv = m => mat3scale(mat3adj(m), 1 / mat3det(m));
//console.log(mat3det([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]]));
//console.log(mat3adj([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]]));
//console.log(mat3inv([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]]));
//console.log(mat3inv(mat3inv([[3.5,25-3.5,3.5], [3.5,3.5,25-3.5], [1,1,1]])));
const transform = (m, x, y) => {
const z = m[2][0] * x + m[2][1] * y + m[2][2];
return {
x: (m[0][0] * x + m[0][1] * y + m[0][2]) / z,
y: (m[1][0] * x + m[1][1] * y + m[1][2]) / z,
};
};
// image to cells
// P = [[3.5, w-3.5, 3.5], [3.5, 3.5, w-3.5], [1, 1, 1]]
// R = [[tl.x, tr.x, bl.x], [tl.y. tr.y, bl.y], [1, 1, 1]]
// M*P = R => M = R*P^-1
export const toFrame = (alignedFinders, bin, width) => {
const [tl, tr, bl] = alignedFinders;
const {size, cellH, cellV} = resolveCellSize(alignedFinders, bin, width);
if (size <= 0) return [[], size, cellH, cellV];
const br = findAlignment(alignedFinders, size, cellH, cellV, bin, width);
const P0 = [[3.5, size - 3.5, 3.5], [3.5, 3.5, size - 3.5], [1, 1, 1]];
const R0 = [[tl.x, tr.x, bl.x], [tl.y, tr.y, bl.y], [1, 1, 1]];
const M0 = mat3mul(R0, mat3inv(P0));
const P1 = [
[3.5, size - 3.5, size - 6.5], [3.5, 3.5, size - 6.5], [1, 1, 1]];
const R1 = [[tl.x, tr.x, br.x], [tl.y, tr.y, br.y], [1, 1, 1]];
const M1 = mat3mul(R1, mat3inv(P1));
const P2 = [
[3.5, size - 6.5, 3.5], [3.5, size - 6.5, size - 3.5], [1, 1, 1]];
const R2 = [[tl.x, br.x, bl.x], [tl.y, br.y, bl.y], [1, 1, 1]];
const M2 = mat3mul(R2, mat3inv(P2));
const P3 = [
[size - 3.5, 3.5, size - 6.5], [3.5, size - 3.5, size - 6.5], [1, 1, 1]];
const R3 = [[tr.x, bl.x, br.x], [tr.y, bl.y, br.y], [1, 1, 1]];
const M3 = mat3mul(R3, mat3inv(P3));
return [range(size * size).map(i => {
const x = i % size, y = (i - x) / size;
const M = (x > size * 2 / 4) && (y > size * 2 / 4) ? M3 :
(x < size * 2 / 4) && (y > size * 2 / 4) ? M2 :
(x > size * 2 / 4) && (y < size * 2 / 4) ? M1 : M0;
const p = transform(M, x + 0.5, y + 0.5);
const b = bin[Math.floor(p.y) * width + Math.floor(p.x)];
return +(tr.b === b);
}), size, cellH, cellV, br];
};
Raw
qrcode-example.html
<!doctype html>
<html>
<head>
<script type="module">
import * as QRCode from "./qrcode.js";
const scale = 8;
const h2 = document.createElement("h2");
const {frame, width, version, quarity, maskId} = QRCode.qrcode("12345 <=> HELLO WORLD");
h2.textContent = `Version-Quarity (maskId): ${version}-${quarity} (${maskId})`;
const canvas = document.createElement("canvas");
canvas.style.border = "solid";
const w = scale * QRCode.renderWidth(width);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
QRCode.render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
document.body.append(h2, canvas);
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrcode-example2.html
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<script type="module">
import * as QRCode from "./qrcode.js";
const {frame, width, version, quarity, maskId} = QRCode.qrcode("こんにちは👌");
const scale = 8;
const h2 = document.createElement("h2");
const div = document.createElement("div");
h2.textContent = `Version-Quarity (maskId): ${version}-${quarity} (${maskId})`;
div.innerHTML = QRCode.svg(frame, width, scale);
document.body.append(h2, div);
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrcode-generator.html
<!doctype html>
<html>
<head>
<link rel="icon" herf="data:," />
<meta charset="utf-8" />
<title>QR Code generator</title>
<script type="module">
import * as QRCode from "./qrcode.js";
const generate = () => {
const scale = +document.getElementById("scale").value;
const quarity0 = document.getElementById("quarity").value;
const text = document.getElementById("text").value;
const useKanji = document.getElementById("useKanji").checked;
const result = document.getElementById("result");
try {
const {frame, width, version, quarity, maskId} =
QRCode.qrcode(text, quarity0, useKanji);
// 2d canvas with ImageData
const canvas = document.createElement("canvas");
const w = scale * QRCode.renderWidth(width);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
QRCode.render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
const svg = document.createElement("a");
svg.setAttribute("download", "qrcode.png");
svg.href = canvas.toDataURL("image/png");
//svg text
svg.innerHTML = QRCode.svg(frame, width, scale);
const h3 = document.createElement("h3");
h3.append(`Version-Quarity (maskId): ${version}-${quarity} (${maskId})`);
const p = document.createElement("p");
const span = document.createElement("span");
span.style.backgroundColor = "white";
span.innerHTML = text.replace(/ /g, "&nbsp;");
p.append("Text: ", span);
const div = document.createElement("div");
div.append(h3, p, svg);
result.prepend(div);
} catch (error) {
const pre = document.createElement("pre");
pre.style.display = "block";
pre.textContent = `${error}\n`;
console.error(error);
result.prepend(pre);
}
};
document.getElementById("generate").addEventListener("click", generate);
document.getElementById("scale").addEventListener("input", ev => {
document.getElementById("scaleVal").textContent = ev.target.value;
});
</script>
</head>
<body style="background-color: gray;">
<h1>QR Code generator</h1>
<div>
<label>text: <input id="text" size="50"/></label>
<button id="generate">generate</button>
</div>
<div>
<label>quarity: <select id="quarity">
<option value="L">L</option>
<option value="M">M</option>
<option value="Q" selected>Q</option>
<option value="H">H</option>
</label>
</select>
<label>
scale <span id="scaleVal">8</span>:
<input id="scale" type="range" min="4" max="32" value="8" />
</label>
<label>
<input id="useKanji" type="checkbox" checked="checked" />
use Kanji mode
</label>
</div>
<h2>Result (click to download)</h2>
<div id="result"></div>
</body>
</html>
Raw
qrcode-generator2.html
<!doctype html>
<html>
<head>
<link rel="icon" herf="data:," />
<meta charset="utf-8" />
<title>QR Code generator</title>
<script type="module">
import * as QRCode from "./qrcode.js";
const generate = () => {
const scale = +document.getElementById("scale").value;
const quarity0 = document.getElementById("quarity").value;
const text = document.getElementById("text").value;
const useKanji = document.getElementById("useKanji").checked;
const result = document.getElementById("result");
try {
const {frame, width, version, quarity, maskId} =
QRCode.qrcode(text, quarity0, useKanji);
// 2d canvas with ImageData
const canvas = document.createElement("canvas");
const w = scale * QRCode.renderWidth(width);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
QRCode.render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
const svg = document.createElement("a");
svg.setAttribute("download", "qrcode.png");
svg.href = canvas.toDataURL("image/png");
//svg text
svg.innerHTML = QRCode.svg(frame, width, scale);
const h3 = document.createElement("h3");
h3.append(`Version-Quarity (maskId): ${version}-${quarity} (${maskId})`);
const div = document.createElement("div");
div.append(svg, h3);
result.innerHTML = "";
result.prepend(div);
} catch (error) {
const pre = document.createElement("pre");
pre.style.display = "block";
pre.textContent = `${error}\n`;
console.error(error);
result.innerHTML = "";
result.prepend(pre);
}
};
generate();
document.getElementById("text").addEventListener("input", generate);
document.getElementById("quarity").addEventListener("input", generate);
document.getElementById("scale").addEventListener("input", generate);
document.getElementById("useKanji").addEventListener("input", generate);
document.getElementById("scale").addEventListener("input", ev => {
document.getElementById("scaleVal").textContent = ev.target.value;;
});
try {screen.orientation.lock("portrait");} catch (error) {}
</script>
<style>
body {
background-color: gray;
display: flex; flex-direction: column; align-items: center;
}
textarea#text {width: 50vmin; height: 20vmin;}
span#scaleVal {display: inline-block; width: 2ch; text-align: right;}
#result svg {width: 50vmin; height: 50vmin;}
</style>
</head>
<body>
<h1>QR Code generator</h1>
<div>
<textarea id="text" placeholder="Text for QR code"></textarea>
</div>
<div>
<label>quarity: <select id="quarity">
<option value="L">L</option>
<option value="M">M</option>
<option value="Q" selected>Q</option>
<option value="H">H</option>
</label>
</select>
<label>
scale <span id="scaleVal">8</span>:
<input id="scale" type="range" min="4" max="32" value="8" />
</label>
<label>
<input id="useKanji" type="checkbox" checked="checked" />
use Kanji mode
</label>
</div>
<h2>Result (click to download)</h2>
<div id="result"></div>
</body>
</html>
Raw
qrcode.js
import {BitWriter} from "./bitstream.js";
import * as QRData from "./qrdata.js";
import {
quarities, quarityIndex, dataBytes, encodeMessage,
} from "./qrmessage.js";
import {qrwidth} from "./qrframe.js";
import {buildFrame} from "./qrencode.js";
import {evaluate} from "./qrevaluation.js";
import {guess} from "./qrauto.js";
export {render, renderWidth, svg} from "./qrimagedata.js";
const range = n => [...Array(n).keys()];
export const quarityList = Object.freeze([...quarities]);
export const versionList = Object.freeze(range(40).map(k => k + 1));
export const maskIdList = Object.freeze(range(8));
// QR-Code builder auto data packing with minimum version
// - returns {frame, width, version, quarity, maskId}
export const qrcode = (text, quarity = "Q", useKanji = true) => {
if (!quarityList.includes(quarity)) throw TypeError(
`invalid quarity: ${quarity}`);
const qi = quarityIndex(quarity);
const [bw, version] = guess(qi, text, useKanji);
if (bw.byteLength() > dataBytes(version, qi)) throw Error(
`Overflow text in version-${version}`);
const coded = encodeMessage(bw.toBuffer(), version, qi);
const width = qrwidth(version);
const {frame, maskId} = buildBestFrame(coded, version, qi, width);
return {frame, width, version, quarity, maskId};
};
export const buildBestFrame = (coded, version, qi, width) => {
return maskIdList.map(maskId => {
const frame = buildFrame(coded, version, qi, maskId);
const penalty = evaluate(frame, width);
return {penalty, frame, maskId};
}).sort((a, b) => a.penalty - b.penalty)[0];
};
// QR-Code builder with specified version and quarity (and mask)
// 1. add each text with data type
// 2. then build a frame
export const qrbuilder = (version, quarity) => {
if (!quarityList.includes(quarity)) throw TypeError(
`invalid quarity: ${quarity}`);
if (!versionList.includes(version)) throw TypeError(
`invalid version: ${version}`);
const bw = new BitWriter();
const qi = quarityIndex(quarity);
const dataLength = dataBytes(version, qi);
// builder object
let result = null;
const self = {dataLength};
return Object.freeze(Object.assign(self, {
addNumbers: (text) => {
QRData.addNumbers(bw, version, text);
return self;
},
addAlphaNums: (text) => {
QRData.addAlphaNums(bw, version, text);
return self;
},
addBytes: (text) => {
QRData.addBytes(bw, version, text);
return self;
},
addKanjis: (text) => {
QRData.addKanjis(bw, version, text);
return self;
},
build: (maskId = null) => {
if (result) return result;
QRData.terminateData(bw, dataLength);
if (bw.byteLength() > dataBytes(version)) throw Error(
`Overflow text in version-${version}`);
const coded = encodeMessage(bw.toBuffer(), version, qi);
const width = qrwidth(version);
const fm = maskId === null ? buildBestFrame(coded, version, qi, width) :
{frame: buildFrame(coded, version, qi, maskId), maskId};
return {frame: fm.frame, width, version, quarity, maskId: fm.maskId};
},
}));
};
Raw
qrdata-example.js
import {BitWriter} from "./bitstream.js";
import * as QRData from "./qrdata.js";
{
const bw = new BitWriter();
const v = 1;
QRData.addNumbers(bw, v, "8675309");
QRData.terminateData(bw, 9); // 1-H
console.log([...bw.toBuffer()].map(n => n.toString(2).padStart(8, "0")));
}
{
const bw = new BitWriter();
const v = 1;
QRData.addAlphaNums(bw, v, "HELLO WORLD");
QRData.terminateData(bw, 13); // 1-Q
console.log([...bw.toBuffer()].map(n => n.toString(2).padStart(8, "0")));
}
{
const bw = new BitWriter();
const v = 1;
QRData.addBytes(bw, v, "Hello World!");
QRData.terminateData(bw, 16); // 1-M
console.log([...bw.toBuffer()].map(n => n.toString(2).padStart(8, "0")));
}
{
//https://www.thonky.com/qr-code-tutorial/kanji-mode-encoding
const bw = new BitWriter();
const v = 1;
const td = new TextDecoder("shift_jis");
const kanjis = td.decode(new Uint8Array([0xe4, 0xaa, 0x89, 0xd7]));
QRData.addKanjis(bw, v, kanjis);
QRData.terminateData(bw, 16); // 1-M
console.log([...bw.toBuffer()].map(n => n.toString(2).padStart(8, "0")));
// 1000 0000-0010 1101-0101_0101-0 001_1010-0101_11 00-00 0...
// 1110_1100 0001_0001 1110_1100 0001_0001 ...
}
Raw
qrdata.js
import * as cp2sjis from "./cp2sjis.js";
// utilities
export const range = n => [...Array(n).keys()];
export const chunking = (a, n) => range(Math.ceil(a.length / n)).map(
i => a.slice(i * n, (i + 1) * n));
// data length varied by version
const lengthBitTable = [
// version: 1<=>9, 10<=>26, 27<=>40
[10, 12, 14], // Numbers
[ 9, 11, 13], // AlphaNums
[ 8, 16, 16], // Bytes
[ 8, 10, 12], // Kanjis
];
const maxLengthTable = lengthBitTable.map(l => l.map(b => 2 ** b));
export const lengthBit = (mode, version) => {
console.assert(1 <= version && version <= 40, "invalid version", version);
return lengthBitTable[mode][version <= 9 ? 0 : version <= 26 ? 1 : 2];
};
export const maxLength = (mode, version) => {
console.assert(1 <= version && version <= 40, "invalid version", version);
return maxLengthTable[mode][version <= 9 ? 0 : version <= 26 ? 1 : 2];
};
// 0. terminateor
export const addTerminator = (bitwriter) => {
bitwriter.write(0, 4);
return bitwriter;
};
export const bitTerminator = () => 4;
// last padding
export const addPads = (bitwriter, totalLength) => {
const pad = totalLength - bitwriter.byteLength();
bitwriter.writeBytes(range(pad).map(k => (k & 1) ? 0b00010001 : 0b11101100));
return bitwriter;
};
export const terminateData = (bitwriter, totalLength) => {
if (totalLength - bitwriter.byteLength()) addTerminator(bitwriter);
return addPads(bitwriter, totalLength);
};
// 1. numbers
export const regExpNumbers = (version, least = 1) =>
RegExp(`^\\d{${least},${maxLength(0, version)}}$`);
export const addNumbers = (bitwriter, version, text) => {
console.assert(regExpNumbers(version).test(text), "invalid numbers", text);
bitwriter.write(1 << 0, 4);
bitwriter.write(text.length, lengthBit(0, version));
const chunks = chunking(text, 3);
const last = chunks[chunks.length - 1].length !== 3 ? chunks.pop() : "";
for (const chunk of chunks) bitwriter.write(+chunk, 10);
if (last.length === 2) bitwriter.write(+last, 7);
else if (last.length === 1) bitwriter.write(+last, 4);
return bitwriter;
};
export const bitNumbers = (version, len) => {
if (maxLength(0, version) < len) return -1;
const rem = len % 3, c3 = (len - rem) / 3;
return 4 + lengthBit(0, version) + 10 * c3 +
(rem === 2 ? 7 : rem === 1 ? 4 : 0);
};
// 2. alphanums
export const alphaNumTable = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:";
//console.assert(alphaNumTable.length === 45);
export const regExpAlphaNums = (version, least = 1) =>
RegExp(`^[${alphaNumTable}]{${least},${maxLength(1, version)}}$`);
export const addAlphaNums = (bitwriter, version, text) => {
console.assert(regExpAlphaNums(version).test(text), "invalid alphanums", text);
bitwriter.write(1 << 1, 4);
bitwriter.write(text.length, lengthBit(1, version));
const chunks = chunking(text, 2);
const last = chunks[chunks.length - 1].length !== 2 ? chunks.pop() : "";
for (const chunk of chunks) bitwriter.write(
45 * alphaNumTable.indexOf(chunk[0]) + alphaNumTable.indexOf(chunk[1]), 11);
if (last.length === 1) bitwriter.write(alphaNumTable.indexOf(last), 6);
return bitwriter;
};
export const bitAlphaNums = (version, len) => {
if (maxLength(1, version) < len) return -1;
const rem = len % 2, c2 = (len - rem) / 2;
return 4 + lengthBit(1, version) + 11 * c2 + (rem === 1 ? 6 : 0);
};
// 3. bytes
export const addBytes = (bitwriter, version, text) => {
const chunks = new TextEncoder().encode(text);
console.assert(chunks.length <= maxLength(2, version), "invalid length bytes", text);
bitwriter.write(1 << 2, 4);
bitwriter.write(chunks.length, lengthBit(2, version));
for (const chunk of chunks) bitwriter.write(chunk, 8);
return bitwriter;
};
export const bitBytes = (version, len) => {
// NOTE: `len` as byte count (not character count)
if (maxLength(2, version) < len) return -1;
return 4 + lengthBit(2, version) + 8 * len;
};
// 4. Kanjis: SJIS 2-byte code numbers except for ASCII, half-width KATAKANA
export const addKanjis = (bitwriter, version, text) => {
const kanjiArray = [...text].map(ch => cp2sjis.get(ch));
console.assert(kanjiArray.every(
c => 0x8140 <= c && c <= 0x9ffc || 0xe040 <= c && c <= 0xebbf) &&
kanjiArray.length <= maxLength(3, version));
bitwriter.write(1 << 3, 4);
bitwriter.write(kanjiArray.length, lengthBit(3, version));
for (const c of kanjiArray) {
const o = c - (c <= 0x9ffc ? 0x8140 : 0xc140);
bitwriter.write((o >> 8) * 0xc0 + (o & 0xff), 13);
}
return bitwriter;
};
export const bitKanjis = (version, len) => {
// NOTE: `len` as character counts (not byte count)
if (maxLength(3, version) < len) return -1;
return 4 + lengthBit(3, version) + 13 * len;
};
Raw
qrdecode-example.js
import {qrcode} from "./qrcode.js";
import {qrdecode} from "./qrdecode.js";
{
const text = "12345 HELLO WORLD!! \u{8317}\u{8377}";
const {frame, width, version, quarity, maskId} = qrcode(text, "H");
const result = qrdecode(frame, width);
console.assert(text === result);
}
{
const text = "12345 HELLO WORLD!! \u{8317}\u{8377}";
console.log("original", text);
const {frame, width, version, quarity, maskId} = qrcode(text, "H");
console.log("V-Q-M", version, quarity, maskId);
// NOTE: QR code is weak for random position noise
// because bytes of single block is spread on frame
const errored = frame.slice();
for (let i = 0; i < width >>> 1; i++) {
errored[errored.length - 1 - i] ^= 1;
errored[width * (width >>> 1) + width - 1 - i] ^= 1;
errored[width * (width - 1 - i) + (width >>> 1)] ^= 1;
}
console.assert(frame.length === errored.length);
const errorCount = errored.filter((b, i) => b !== frame[i]).length;
console.log("errors", errorCount);
console.log("error rate", errorCount / errored.length);
const result = qrdecode(errored, width);
console.log("decoded", result);
}
Raw
qrdecode.js
import {BitWriter, BitReader} from "./bitstream.js";
import * as cp2sjis from "./cp2sjis.js";
import {lengthBit, alphaNumTable} from "./qrdata.js";
import {
formatMask, formatValue, blockInfo, transpose, poly,
} from "./qrmessage.js";
import {range, get, set} from "./qrframe.js";
import {buildEmptyFrame, makeScanner, qrmask} from "./qrencode.js";
import {RSCode} from "./qrrscode.js";
export const qrversion = width => (width - 17) / 4;
export const qrdecode = (frame, width) => {
if (frame.length !== width * width) throw Error(`invalid frame size`);
if (!frame.every(v => v === 0 || v === 1)) {
throw Error(`invalid frame values: should be 0 or 1`);
}
const version = qrversion(width);
if (!(Number.isInteger(version) && 1 <= version && version <= 40)) {
throw Error(`any version does not match width: ${width}`);
}
const {qi, maskId} = scanFormat(frame, width);
const coded = scanCode(frame, width, version, qi, maskId);
const bytes = decodePlain(coded, version, qi);
return unpackText(bytes, version);
};
// unpack string from bitstream
export const unpackText = (bytes, version) => {
const br = new BitReader(bytes);
const chunks = [];
while (br.canReadBits(4)) {
const mode = br.read(4);
if (mode === 0) break;
else if (mode === 1) unpackNumbers(br, version, chunks);
else if (mode === 2) unpackAlphaNums(br, version, chunks);
else if (mode === 4) unpackBytes(br, version, chunks);
else if (mode === 8) unpackKanjis(br, version, chunks);
// TBD: other modes
else throw Error(`invalid packing mode: ${mode}`);
}
return chunks.join("");
};
export const unpackNumbers = (br, version, chunks) => {
const len = br.read(lengthBit(0, version));
const rem = len % 3, d = (len - rem) / 3;
for (let i = 0; i < d; i++) {
chunks.push(br.read(10).toString().padStart(3, "0"));
}
if (rem === 2) chunks.push(br.read(7).toString().padStart(2, "0"));
if (rem === 1) chunks.push(br.read(4).toString().padStart(1, "0"));
};
export const unpackAlphaNums = (br, version, chunks) => {
const len = br.read(lengthBit(1, version));
const rem = len % 2, d = (len - rem) / 2;
for (let i = 0; i < d; i++) {
const v = br.read(11);
const c2 = v % 45, c1 = (v - c2) / 45;
chunks.push(alphaNumTable[c1], alphaNumTable[c2]);
}
if (rem === 1) chunks.push(alphaNumTable[br.read(6)]);
};
export const unpackBytes = (br, version, chunks) => {
const len = br.read(lengthBit(2, version));
const buf = new Uint8Array(len);
for (let i = 0; i < len; i++) buf[i] = br.read(8);
chunks.push(new TextDecoder().decode(buf));
};
export const unpackKanjis = (br, version, chunks) => {
const len = br.read(lengthBit(3, version));
for (let i = 0; i < len; i++) {
const v = br.read(13);
const low = v % 0xc0, high = (v - low) / 0xc0;
const sjis = ((high << 8) | low) + (high >= 0x1f ? 0xc140 : 0x8140);
chunks.push(cp2sjis.toChar(sjis));
}
};
// decode to plain bytes
export const decodePlain = (coded, version, qi) => {
const [paritySize, b1Size, b1count, b2count] = blockInfo(version, qi);
const blockCount = b1count + b2count;
const dataSize = b1Size * blockCount + b2count;
const dataList = transpose(
range(b1Size).map(i => coded.slice(i * blockCount, (i + 1) * blockCount)));
const b1dataList = dataList.slice(0, b1count);
const b2dataList = dataList.slice(b1count).map(
(block, i) => [...block, coded[dataSize - b2count + i]]);
const parityList = transpose(range(paritySize).map(i => coded.slice(
dataSize + i * blockCount, dataSize + (i + 1) * blockCount)));
const messageList = [...b1dataList, ...b2dataList].map(
(data, i) => [...data, ...parityList[i]]);
const rscode = RSCode(poly, paritySize);
return messageList.map(
msg => rscode.decode(msg).slice(0, -paritySize)).flat();
};
// scan format
const formats = range(4).flatMap(qi => range(8).map(
maskId => ({qi, maskId, format: formatValue(qi, maskId)})));
const popcnt32 = n => {
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
return (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
};
export const scanFormat = (frame, width) => {
const f1a = [];
for (let i = 0; i < 6; i++) f1a.push(get(frame, width, i, 8));
f1a.push(get(frame, width, 7, 8));
f1a.push(get(frame, width, 8, 8));
f1a.push(get(frame, width, 8, 7));
for (let i = 9; i < 15; i++) f1a.push(get(frame, width, 8, 14 - i));
const f1v = f1a.reduce((r, b) => (r << 1) | b, 0) ^ formatMask;
const f1r = formats.map(f => [popcnt32(f.format ^ f1v), f]);
const f2a = [];
for (let i = 0; i < 7; i++) {
f2a.push(get(frame, width, 8, width - 1 - i));
}
for (let i = 7; i < 15; i++) {
f2a.push(get(frame, width, width - 15 + i, 8));
}
const f2v = f2a.reduce((r, b) => (r << 1) | b, 0) ^ formatMask;
const f2r = formats.map(f => [popcnt32(f.format ^ f2v), f]);
// NOTE: choose the nearest format code, instead of computing BCH syndromes
// because too many erros easily match invalid format codes
const ordered = [...f1r, ...f2r].sort(([a], [b]) => a - b);
const min = ordered[0][0];
if (min > 4) throw Error(`cannot scan version`); // over BCH error collect
return ordered[0][1];
};
// scan code
export const scanCode = (frame, width, version, qi, maskId) => {
const [empty, w] = buildEmptyFrame(version, qi, maskId);
console.assert(w === width, "invalid width");
const bw = new BitWriter();
for (const [x, y] of makeScanner(width)) {
if (get(empty, width, x, y) !== null) continue;
const m = qrmask(maskId, x, y);
const b = get(frame, width, x, y) ^ m;
bw.writeBit(b);
}
return bw.buf; // ignore bits in incomplete byte
};
Raw
qrencode-example.html
<!doctype html>
<html>
<head>
<script type="module">
import {BitWriter} from "./bitstream.js";
import {addNumbers, terminateData} from "./qrdata.js";
import {dataBytes, encodeMessage} from "./qrmessage.js";
import {qrwidth} from "./qrframe.js";
import {buildFrame} from "./qrencode.js";
import {render} from "./qrimagedata.js";
const scale = 4;
for (let v = 1; v <= 40; v++) {
const qi = 3;
for (let maskId = 0; maskId < 8; maskId++) {
const h2 = document.createElement("h2");
h2.textContent = `Version-Quarity (Mask): ${v}-${"LMQH"[qi]} (${maskId})`;
const bw = new BitWriter();
addNumbers(bw, v, "0123456789");
terminateData(bw, dataBytes(v, qi));
const coded = encodeMessage(bw.toBuffer(), v, qi);
const frame = buildFrame(coded, v, qi, maskId);
const width = qrwidth(v);
const canvas = document.createElement("canvas");
canvas.style.border = "solid";
const w = scale * (width + 8);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
document.body.append(h2, canvas);
}
}
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrencode-example2.html
<!doctype html>
<html>
<head>
<script type="module">
import {BitWriter} from "./bitstream.js";
import {addNumbers, addAlphaNums, terminateData} from "./qrdata.js";
import {dataBytes, encodeMessage} from "./qrmessage.js";
import {qrwidth} from "./qrframe.js";
import {buildFrame} from "./qrencode.js";
import {render} from "./qrimagedata.js";
const scale = 8;
const v = 1;
const qi = 2;
for (let maskId = 0; maskId < 8; maskId++) {
const h2 = document.createElement("h2");
h2.textContent = `Version-Quarity (Mask): ${v}-${"LMQH"[qi]} (${maskId})`;
const bw = new BitWriter();
//addNumbers(bw, v, "0123456789");
addAlphaNums(bw, v, "HELLO WORLD");
terminateData(bw, dataBytes(v, qi));
const coded = encodeMessage(bw.toBuffer(), v, qi);
const frame = buildFrame(coded, v, qi, maskId);
const width = qrwidth(v);
const canvas = document.createElement("canvas");
canvas.style.border = "solid";
const w = scale * (width + 8);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
document.body.append(h2, canvas);
}
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrencode-example3.html
<!doctype html>
<html>
<head>
<script type="module">
import {BitWriter} from "./bitstream.js";
import {addNumbers, addAlphaNums, terminateData} from "./qrdata.js";
import {dataBytes, encodeMessage} from "./qrmessage.js";
import {qrwidth} from "./qrframe.js";
import {buildFrame} from "./qrencode.js";
import {render} from "./qrimagedata.js";
const scale = 8;
const v = 7;
//const v = 8;
const qi = 2;
//const qi = 1;
for (let maskId = 0; maskId < 8; maskId++) {
const h2 = document.createElement("h2");
h2.textContent = `Version-Quarity (Mask): ${v}-${"LMQH"[qi]} (${maskId})`;
const bw = new BitWriter();
//addNumbers(bw, v, "0123456789");
addAlphaNums(bw, v, "HELLO WORLD");
terminateData(bw, dataBytes(v, qi));
const coded = encodeMessage(bw.toBuffer(), v, qi);
const frame = buildFrame(coded, v, qi, maskId);
const width = qrwidth(v);
const canvas = document.createElement("canvas");
canvas.style.border = "solid";
const w = scale * (width + 8);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
document.body.append(h2, canvas);
}
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrencode-example4.html
<!doctype html>
<html>
<head>
<script type="module">
import {BitWriter} from "./bitstream.js";
import {addNumbers, addAlphaNums, terminateData} from "./qrdata.js";
import {dataBytes, encodeMessage} from "./qrmessage.js";
import {qrwidth} from "./qrframe.js";
import {buildFrame} from "./qrencode.js";
import {render} from "./qrimagedata.js";
const scale = 8;
const v = 7;
//const v = 8;
const qi = 2;
//const qi = 1;
const maskId = 0;
const h2 = document.createElement("h2");
h2.textContent = `Version-Quarity (Mask): ${v}-${"LMQH"[qi]} (${maskId})`;
const bw = new BitWriter();
//addNumbers(bw, v, "0123456789");
addAlphaNums(bw, v, "HELLO WORLD");
terminateData(bw, dataBytes(v, qi));
const coded = encodeMessage(bw.toBuffer(), v, qi);
const frame = buildFrame(coded, v, qi, maskId);
const width = qrwidth(v);
const canvas = document.createElement("canvas");
canvas.style.border = "solid";
const w = scale * (width + 8);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
document.body.append(h2, canvas);
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrencode.js
import {BitReader} from "./bitstream.js";
import * as QRMessage from "./qrmessage.js";
import {qrwidth, get, set, makeFrame} from "./qrframe.js";
export const buildEmptyFrame = (version, qi, maskId) => {
const width = qrwidth(version);
const frame = makeFrame(version);
const formatBits = QRMessage.formatBits(qi, maskId);
embedFormat(frame, width, formatBits);
if (version >= 7) {
const versionBits = QRMessage.versionBits(version);
embedVersion(frame, width, versionBits);
}
return [frame, width];
};
export const buildFrame = (coded, version, qi, maskId) => {
console.assert(coded.length === QRMessage.codeBytes(version, qi),
"Invalid data length");
const [frame, width] = buildEmptyFrame(version, qi, maskId);
embedCode(frame, width, coded, maskId);
return frame;
};
// embedding code info
export const embedFormat = (frame, width, formatBits) => {
// top left: go left then go up
for (let i = 0; i < 6; i++) set(frame, width, i, 8, formatBits[i]);
set(frame, width, 7, 8, formatBits[6]);
set(frame, width, 8, 8, formatBits[7]);
set(frame, width, 8, 7, formatBits[8]);
for (let i = 9; i < 15; i++) set(frame, width, 8, 14 - i, formatBits[i]);
// bottom-left: go left
for (let i = 0; i < 7; i++) {
set(frame, width, 8, width - 1 - i, formatBits[i]);
}
// top-right: go up
for (let i = 7; i < 15; i++) {
set(frame, width, width - 15 + i, 8, formatBits[i]);
}
};
export const embedVersion = (frame, width, versionBits) => {
for (let i = 0; i < 18; i++) {
const rem = i % 3, u = (i - rem) / 3, v = (width - 11) + rem;
set(frame, width, u, v, versionBits[i]); // bottom-left
set(frame, width, v, u, versionBits[i]); // top-right
}
};
// generator of zigzag scan [x, y] to set bit
export const makeScanner = function* (width) {
let x = width - 1, y = width - 1, dy = -1;
while (x >= 0) {
yield [x, y];
x--;
yield [x, y];
y += dy;
if (0 <= y & y < width) {
x++;
} else {
y -= dy;
dy *= -1;
x--;
if (x === 6) x--;
}
}
};
// mask pattern
// - https://www.thonky.com/qr-code-tutorial/mask-patterns
const qrmaskTable = [
(x, y) => (x + y) % 2 === 0,
(x, y) => y % 2 === 0,
(x, y) => x % 3 === 0,
(x, y) => (x + y) % 3 === 0,
(x, y) => ((x - x % 3) / 3 + (y - y % 2) / 2) % 2 === 0,
(x, y) => (x * y) % 2 + (x * y) % 3 === 0,
(x, y) => ((x * y) % 2 + (x * y) % 3) % 2 === 0,
(x, y) => ((x + y) % 2 + (x * y) % 3) % 2 === 0,
];
export const qrmask = (maskId, x, y) => +qrmaskTable[maskId](x, y);
export const embedCode = (frame, width, coded, maskId) => {
const br = new BitReader(coded);
for (const [x, y] of makeScanner(width)) {
if (get(frame, width, x, y) !== null) continue;
const b = br.isEnd() ? 0 : br.readBit();
const m = qrmask(maskId, x, y);
set(frame, width, x, y, m ^ b);
}
console.assert(br.isEnd(), "incomplete read");
};
Raw
qrevaluation.js
import {get} from "./qrframe.js";
// mask evaluation
// - https://www.thonky.com/qr-code-tutorial/data-masking
export const evaluate1 = (frame, width) => {
// longer line (len >= 5) as penalty len-2
let score = 0;
for (let y = 0; y < width; y++) {
let len = 1, cur = get(frame, width, 0, y);
for (let x = 1; x < width; x++) {
const c = get(frame, width, x, y);
if (c === cur) {
len++;
if (len === 5) score += 3;
else if (len > 5) score++;
} else {
cur = c, len = 1;
}
}
}
for (let x = 0; x < width; x++) {
let len = 1, cur = get(frame, width, x, 0);
for (let y = 1; y < width; y++) {
const c = get(frame, width, x, y);
if (c === cur) {
len++;
if (len === 5) score += 3;
else if (len > 5) score++;
} else {
cur = c, len = 1;
}
}
}
return score;
};
export const evaluate2 = (frame, width) => {
// 2x2 square as penalty 3
let score = 0;
for (let y = 1; y < width; y++) {
for (let x = 1; x < width; x++) {
const c = get(frame, width, x, y);
const up = get(frame, width, x, y - 1);
if (c !== up) {
x++;
continue;
}
if (get(frame, width, x - 1, y - 1) === c &&
get(frame, width, x - 1, y) === c) score += 3;
}
}
return score;
};
export const evaluate3 = (frame, width) => {
// 11-bit line pattern 10111010000 or 00001011101 as penalty 40
const p1 = 0b10111010000, p2 = 0b00001011101, m = 0b11111111111;
let score = 0;
for (let y = 0; y < width; y++) {
let scan = 0;
for (let x = 0; x < 10; x++) scan = (scan << 1) | get(frame, width, x, y);
for (let x = 10; x < width; x++) {
scan = ((scan << 1) | get(frame, width, x, y)) & m;
if (scan === p1 || scan === p2) score += 40;
}
}
for (let x = 0; x < width; x++) {
let scan = 0;
for (let y = 0; y < 10; y++) scan = (scan << 1) | get(frame, width, x, y);
for (let y = 10; y < width; y++) {
scan = ((scan << 1) | get(frame, width, x, y)) & m;
if (scan === p1 || scan === p2) score += 40;
}
}
return score;
};
export const evaluate4 = (frame, width) => {
// dark/light rate as penalty as 10 each 5% difeerence
const total = frame.length, dark = frame.filter(b => b === 1).length;
return Math.floor(Math.abs(dark * 100 / total - 50) / 5) * 10;
};
export const evaluate = (frame, width) =>
evaluate1(frame, width) + evaluate2(frame, width) + evaluate3(frame, width) +
evaluate4(frame, width);
Raw
qrframe-example.html
<!doctype html>
<html>
<head>
<script type="module">
import {qrwidth, makeFrame} from "./qrframe.js";
import {render} from "./qrimagedata.js";
const scale = 4;
for (let v = 1; v <= 40; v++) {
const h2 = document.createElement("h2");
h2.textContent = `Version ${v}`;
const width = qrwidth(v);
const frame = makeFrame(v);
const canvas = document.createElement("canvas");
canvas.style.border = "solid";
const w = scale * (width + 8);
canvas.width = canvas.height = w;
const c2d = canvas.getContext("2d");
const image = c2d.createImageData(w, w);
render(image, frame, width, scale);
c2d.putImageData(image, 0, 0);
document.body.append(h2, canvas);
}
</script>
</head>
<body style="background-color: gray;"></body>
</html>
Raw
qrframe.js
export const range = n => [...Array(n).keys()];
export const qrwidth = version => 17 + version * 4;
export const blankFrame = width => Array(width ** 2).fill(null);
export const get = (frame, width, x, y) => frame[y * width + x];
export const set = (frame, width, x, y, value) => frame[y * width + x] = value;
// finder patterns
export const markFinder = (frame, width, cx, cy) => {
for (let x = 0; x < 7; x++) for (let y = 0; y < 7; y++) {
const b = x === 0 || x === 6 || y === 0 || y === 6 ||
(2 <= x && x <= 4 && 2 <= y && y <= 4);
set(frame, width, cx - 3 + x, cy - 3 + y, +b);
}
};
export const markSeparator = (frame, width) => {
for (let i = 0; i < 8; i++) {
// top left
set(frame, width, 7, i, 0); // v
set(frame, width, i, 7, 0); // h
// top right
set(frame, width, width - 8, i, 0); // v
set(frame, width, width - 1 - i, 7, 0); // h
// bottom left
set(frame, width, 7, width - 1 - i, 0); // v
set(frame, width, i, width - 8, 0); // h
}
};
export const markFinders = (frame, width) => {
markFinder(frame, width, 3, 3);
markFinder(frame, width, width - 4, 3);
markFinder(frame, width, 3, width - 4);
markSeparator(frame, width);
};
// alignment patterns
// - https://www.thonky.com/qr-code-tutorial/alignment-pattern-locations
const alignmentSpans = [
0, 0, 0, 0, 0, 0, 0, // 1 <=> 6
16, 18, 20, 22, 24, 26, 28, // 7 <=> 13
20, 22, 24, 24, 26, 28, 28, //14 <=> 20
22, 24, 24, 26, 26, 28, 28, //21 <=> 27
24, 24, 26, 26, 26, 28, 28, //28 <=> 34
24, 26, 26, 26, 28, 28, //35 <=> 40
];
export const alignmentIndexes = version => {
if (version < 2) return [];
const last = qrwidth(version) - 7;
const count = Math.floor(version / 7) + 1;
const span = alignmentSpans[version];
return range(count).map(k => last - k * span).reverse();
};
export const markAlignment = (frame, width, cx, cy) => {
for (let x = 0; x < 5; x++) for (let y = 0; y < 5; y++) {
const b = x === 0 || x === 4 || y === 0 || y === 4 || (x === 2 && y === 2);
set(frame, width, cx - 2 + x, cy - 2 + y, +b);
}
};
export const markAlignments = (frame, width, indexes) => {
for (const cx of indexes) for (const cy of indexes) {
markAlignment(frame, width, cx, cy);
}
for (const cx of indexes.slice(0, -1)) markAlignment(frame, width, cx, 6);
for (const cy of indexes.slice(0, -1)) markAlignment(frame, width, 6, cy);
};
export const markTimings = (frame, width) => {
for (let i = 8; i < width - 8; i++) {
set(frame, width, 6, i, 1 - (i & 1)); // v-line
set(frame, width, i, 6, 1 - (i & 1)); // h-line
}
};
// non data frame
export const makeFrame = version => {
const width = qrwidth(version);
const frame = blankFrame(width);
markFinders(frame, width);
const indexes = alignmentIndexes(version);
markAlignments(frame, width, indexes);
markTimings(frame, width);
set(frame, width, 8, width - 8, 1);
return frame;
};
Raw
qrgf-example.js
import {range, PF2Poly, GF2n, Polynomial} from "./qrgf.js";
//*
{
const gf = GF2n(8, 0b100011101);
const poly = Polynomial(gf);
const msg = [
0b10000000, 0b01000100, 0b10000101, 0b10100111, 0b01001001, 0b10100111,
0b10001011, 0b01101100, 0b00000000, 0b11101100, 0b00010001, 0b11101100,
0b00010001, 0b11101100, 0b00010001, 0b11101100, 0b00010001, 0b11101100,
0b00010001,
];
const gen = poly.prod(range(7).map(k => [gf.one, gf.alpha(k)]));
console.log("gen", gen);
const m = poly.carry(msg, 7);
//console.log(m);
const r = poly.mod(m, gen);
console.log("parity", r);
const coded = poly.sub(m, r);
console.log("coded", coded);
}
//*/
{
const gf = GF2n(8, 0b100011101);
const poly = Polynomial(gf);
const d = 18;
const gen = poly.prod(range(d).map(k => [gf.one, gf.alpha(k)]));
console.log(gen);
console.log(gen.map(c => gf.exponent(c)));
//const msg0 = range(7).flatMap(_ => [236, 17]);
//const msg = [...msg0, 236];
const msg0 = range(7).flatMap(_ => [17, 236]);
const msg = [...msg0, 17];
const m = poly.carry(msg, d);
const r = poly.mod(m, gen);
console.log(r);
}
Raw
qrgf.js
// Tiny GF2n and Polynomial
export const range = n => [...Array(n).keys()];
export const PF2Poly = () => {
const order = e => Math.max(0, 31 - Math.clz32(e));
const neg = e => e;
const add = (a, b) => a ^ b;
const sub = (a, b) => a ^ b;
const carry = (e, k) => e << k;
const mul = (a, b) => {
let r = 0;
for (; b > 0; b >>>= 1, a <<= 1) if (b & 1) r ^= a;
return r;
};
const mod = (a, b) => {
const ma = order(a), mb = order(b);
for (let i = ma - mb, m = 1 << ma; i >= 0; i--, m >>>= 1) {
if (a & m) a ^= b << i;
}
return a;
};
const times = (e, k) => k % 2 === 0 ? 0 : e;
return {order, neg, add, sub, carry, mul, mod, times};
};
export const GF2n = (n, f) => {
const poly = Object.freeze(PF2Poly());
const pn = 2 ** n, pn1 = pn - 1;
const modpn1 = k => (pn1 + k % pn1) % pn1;
const zero = 0, one = 1, a = 2, isZero = e => e === 0;
const {add, sub, neg, times} = poly;
const sum = es => es.reduce((r, e) => add(r, e), zero);
const mul0 = (a, b) => poly.mod(poly.mul(a, b), f);
const powList = [one];
for (let i = 1; i < pn1; i++) {
powList.push(mul0(powList[powList.length - 1], a));
}
const expoList = range(pn).map(e => e === 0 ? NaN : powList.indexOf(e));
const exponent = e => expoList[e];
const mul = (a, b) => a === 0 || b === 0 ? 0 :
powList[modpn1(exponent(a) + exponent(b))];
const pow = (e, k) => e === 0 ? 0 : k === 1 ? e :
powList[modpn1(exponent(e) * k)];
const inv = e => e === 0 ? NaN : powList[modpn1(-exponent(e))];
const div = (a, b) => b === 0 ? NaN : a === 0 ? 0 :
powList[modpn1(exponent(a) - exponent(b))];
const alpha = (k = 1) => pow(a, k);
return {
n, f, pn, neg, zero, one, a, isZero,
add, sub, times, sum, mul, pow, inv, div, exponent, alpha,
};
};
// Polynomial as reversed array
export const Polynomial = K => {
// convert index and order
const deg = (e, i) => i < 0 ? 0 : e.length - 1 - i;
const zero = Object.freeze([K.zero]), one = Object.freeze([K.one]);
const add = (a, b) => {
const [A, B] = a.length >= b.length ? [a, b] : [b, a];
const offs = A.length - B.length;
return A.map((c, i) => i < offs ? c : K.add(c, B[i - offs]));
};
const neg = e => e.map(c => K.neg(c));
const scale = (e, c) => e.map(ci => K.mul(ci, c));
const sub = (a, b) => add(a, neg(b));
const sum = es => es.reduce((r, e) => add(r, e), zero);
const carry = (e, k) => e.concat(Array(k).fill(K.zero));
const mul = (a, b) => sum(b.map(
(bi, i) => carry(scale(a, bi), deg(b, i))));
const prod = es => es.reduce((r, e) => mul(r, e), one);
const order = e => deg(e, e.findIndex(ek => !K.isZero(ek)));
const mod = (a, b) => {
const ma = order(a), mb = order(b);
if (ma < mb) return a.slice(-mb);
const f = K.div(a[0], b[0]);
return mod(sub(a, carry(scale(b, f), ma - mb)).slice(1), b);
};
const coef = (e, k) => e[deg(e, k)] || K.zero;
const monomial = (c, k) => carry([c], k);
const diff = e => e.map((c, i) => K.times(c, deg(e, i))).slice(0, -1);
const apply = (e, v) => K.sum(
e.map((c, i) => K.mul(c, K.pow(v, deg(e, i)))));
return {
K, zero, one, neg, scale, add, sub, sum, carry, mul, order, mod, prod,
coef, monomial, diff, apply,
};
};
Raw
qrimagedata.js
const get = (frame, width, x, y) => frame[y * width + x];
const set = (image, x, y, p) => {
if (p === null) return;
const i = 4 * (y * image.width + x);
image.data[i + 0] = image.data[i + 1] = image.data[i + 2] = p ? 0 : 255;
image.data[i + 3] = 255;
};
// HTML 2D Canvas ImageData
export const renderWidth = width => width + 8;
export const render = (image, frame, width, scale) => {
const pxwidth = (width + 8) * scale;
console.assert(image.width >= pxwidth && image.height >= pxwidth);
for (let x = 0; x < width + 8; x++) for (let y = 0; y < width + 8; y++) {
const margin = x < 4 || width + 4 <= x || y < 4 || width + 4 <= y;
const p = margin ? 0 : get(frame, width, x - 4, y - 4);
for (let u = 0; u < scale; u++) for (let v = 0; v < scale; v++) {
set(image, x * scale + u, y * scale + v, p);
}
}
return image;
};
// SVG string
export const svg = (frame, width, scale) => {
const darks = frame.map((b, i) => {
if (b === 0) return "";
const x = i % width, y = (i - x) / width;
return `<rect x="${x + 4}" y="${y + 4}" width="1" height="1" />`;
});
const w = width + 8, size = w * scale;
return `<svg xmlns="http://www.w3.org/2000/svg" version="1.1"
viewBox="0 0 ${w} ${w}" width="${size}px" height="${size}px">\
<rect x="0" y="0" width="${w}" height="${w}" fill="white" />\
${darks.join("")}</svg>`;
};
Raw
qrmessage-example.js
import {BitWriter} from "./bitstream.js";
import * as QRData from "./qrdata.js";
import * as QRMessage from "./qrmessage.js";
//*
{
const bw = new BitWriter();
const v = 1, q = "H";
const qi = QRMessage.quarityIndex(q);
const len = QRMessage.dataBytes(v, qi);
QRData.addNumbers(bw, v, "8675309");
QRData.terminateData(bw, len);
const buf = bw.toBuffer();
//console.log([...buf].map(n => n.toString(2).padStart(8, "0")));
const result = QRMessage.encodeMessage(buf, v, qi);
console.log(result);
console.assert(result.length === QRMessage.codeBytes(v, qi));
}
{
const bw = new BitWriter();
const v = 1, q = "Q";
const qi = QRMessage.quarityIndex(q);
const len = QRMessage.dataBytes(v, qi);
QRData.addAlphaNums(bw, v, "HELLO WORLD");
QRData.terminateData(bw, len); // 1-Q
const buf = bw.toBuffer();
//console.log([...buf].map(n => n.toString(2).padStart(8, "0")));
const result = QRMessage.encodeMessage(buf, v, qi);
console.log(result);
console.assert(result.length === QRMessage.codeBytes(v, qi));
}
{
const bw = new BitWriter();
const v = 1, q = "M";
const qi = QRMessage.quarityIndex(q);
const len = QRMessage.dataBytes(v, qi);
QRData.addBytes(bw, v, "Hello World!");
QRData.terminateData(bw, len); // 1-M
const buf = bw.toBuffer();
//console.log([...buf].map(n => n.toString(2).padStart(8, "0")));
const result = QRMessage.encodeMessage(buf, v, qi);
console.log(result);
console.assert(result.length === QRMessage.codeBytes(v, qi));
}
//*/
{
const v = 5, q = "Q";
const buf = [
0b01000011, 0b01010101, 0b01000110, 0b10000110, 0b01010111, 0b00100110, 0b01010101, 0b11000010,
0b01110111, 0b00110010, 0b00000110, 0b00010010, 0b00000110, 0b01100111, 0b00100110, 0b11110110,
0b11110110, 0b01000010, 0b00000111, 0b01110110, 0b10000110, 0b11110010, 0b00000111, 0b00100110,
0b01010110, 0b00010110, 0b11000110, 0b11000111, 0b10010010, 0b00000110, 0b10110110, 0b11100110,
0b11110111, 0b01110111, 0b00110010, 0b00000111, 0b01110110, 0b10000110, 0b01010111, 0b00100110,
0b01010010, 0b00000110, 0b10000110, 0b10010111, 0b00110010, 0b00000111, 0b01000110, 0b11110111,
0b01110110, 0b01010110, 0b11000010, 0b00000110, 0b10010111, 0b00110010, 0b11100000, 0b11101100,
0b00010001, 0b11101100, 0b00010001, 0b11101100, 0b00010001, 0b11101100,
];
const qi = QRMessage.quarityIndex(q);
const result = QRMessage.encodeMessage(buf, v, qi);
console.log(result);
}
Raw
qrmessage.js
import {range, PF2Poly, GF2n, Polynomial} from "./qrgf.js";
import {RSCode} from "./qrrscode.js";
// Reed-Solomon encode on GF(2^8) with a^8+a^4+a^3+a^2+1=0
// - https://www.thonky.com/qr-code-tutorial/error-correction-coding
export const gf = Object.freeze(GF2n(8, 0b100011101));
export const poly = Object.freeze(Polynomial(gf));
// message encode
// - https://www.thonky.com/qr-code-tutorial/structure-final-message
export const quarities = "LMQH";
const blockTable = [
// each version has at most two block;
// parity byte length is same, data length b2 is b1 + 1
// quarities L/M/Q/H has different parity different block counts
// - https://www.thonky.com/qr-code-tutorial/error-correction-table
[[/*L: parity, b1 bytes, b1 count, b2 count,*/], [/*M*/], [/*Q*/], [/*H*/],],
[[7, 19, 1, 0], [10, 16, 1, 0], [13, 13, 1, 0], [17, 9, 1, 0]], // 1
[[10, 34, 1, 0], [16, 28, 1, 0], [22, 22, 1, 0], [28, 16, 1, 0]], // 2
[[15, 55, 1, 0], [26, 44, 1, 0], [18, 17, 2, 0], [22, 13, 2, 0]], // 3
[[20, 80, 1, 0], [18, 32, 2, 0], [26, 24, 2, 0], [16, 9, 4, 0]], // 4
[[26, 108, 1, 0], [24, 43, 2, 0], [18, 15, 2, 2], [22, 11, 2, 2]], // 5
[[18, 68, 2, 0], [16, 27, 4, 0], [24, 19, 4, 0], [28, 15, 4, 0]], // 6
[[20, 78, 2, 0], [18, 31, 4, 0], [18, 14, 2, 4], [26, 13, 4, 1]], // 7
[[24, 97, 2, 0], [22, 38, 2, 2], [22, 18, 4, 2], [26, 14, 4, 2]], // 8
[[30, 116, 2, 0], [22, 36, 3, 2], [20, 16, 4, 4], [24, 12, 4, 4]], // 9
[[18, 68, 2, 2], [26, 43, 4, 1], [24, 19, 6, 2], [28, 15, 6, 2]], //10
[[20, 81, 4, 0], [30, 50, 1, 4], [28, 22, 4, 4], [24, 12, 3, 8]], //11
[[24, 92, 2, 2], [22, 36, 6, 2], [26, 20, 4, 6], [28, 14, 7, 4]], //12
[[26, 107, 4, 0], [22, 37, 8, 1], [24, 20, 8, 4], [22, 11, 12, 4]], //13
[[30, 115, 3, 1], [24, 40, 4, 5], [20, 16, 11, 5], [24, 12, 11, 5]], //14
[[22, 87, 5, 1], [24, 41, 5, 5], [30, 24, 5, 7], [24, 12, 11, 7]], //15
[[24, 98, 5, 1], [28, 45, 7, 3], [24, 19, 15, 2], [30, 15, 3, 13]], //16
[[28, 107, 1, 5], [28, 46, 10, 1], [28, 22, 1, 15], [28, 14, 2, 17]], //17
[[30, 120, 5, 1], [26, 43, 9, 4], [28, 22, 17, 1], [28, 14, 2, 19]], //18
[[28, 113, 3, 4], [26, 44, 3, 11], [26, 21, 17, 4], [26, 13, 9, 16]], //19
[[28, 107, 3, 5], [26, 41, 3, 13], [30, 24, 15, 5], [28, 15, 15, 10]], //20
[[28, 116, 4, 4], [26, 42, 17, 0], [28, 22, 17, 6], [30, 16, 19, 6]], //21
[[28, 111, 2, 7], [28, 46, 17, 0], [30, 24, 7, 16], [24, 13, 34, 0]], //22
[[30, 121, 4, 5], [28, 47, 4, 14], [30, 24, 11, 14], [30, 15, 16, 14]], //23
[[30, 117, 6, 4], [28, 45, 6, 14], [30, 24, 11, 16], [30, 16, 30, 2]], //24
[[26, 106, 8, 4], [28, 47, 8, 13], [30, 24, 7, 22], [30, 15, 22, 13]], //25
[[28, 114, 10, 2], [28, 46, 19, 4], [28, 22, 28, 6], [30, 16, 33, 4]], //26
[[30, 122, 8, 4], [28, 45, 22, 3], [30, 23, 8, 26], [30, 15, 12, 28]], //27
[[30, 117, 3, 10], [28, 45, 3, 23], [30, 24, 4, 31], [30, 15, 11, 31]], //28
[[30, 116, 7, 7], [28, 45, 21, 7], [30, 23, 1, 37], [30, 15, 19, 26]], //29
[[30, 115, 5, 10], [28, 47, 19, 10], [30, 24, 15, 25], [30, 15, 23, 25]],//30
[[30, 115, 13, 3], [28, 46, 2, 29], [30, 24, 42, 1], [30, 15, 23, 28]], //31
[[30, 115, 17, 0], [28, 46, 10, 23], [30, 24, 10, 35], [30, 15, 19, 35]],//32
[[30, 115, 17, 1], [28, 46, 14, 21], [30, 24, 29, 19], [30, 15, 11, 46]],//33
[[30, 115, 13, 6], [28, 46, 14, 23], [30, 24, 44, 7], [30, 16, 59, 1]], //34
[[30, 121, 12, 7], [28, 47, 12, 26], [30, 24, 39, 14], [30, 15, 22, 41]],//35
[[30, 121, 6, 14], [28, 47, 6, 34], [30, 24, 46, 10], [30, 15, 2, 64]], //36
[[30, 122, 17, 4], [28, 46, 29, 14], [30, 24, 49, 10], [30, 15, 24, 46]],//37
[[30, 122, 4, 18], [28, 46, 13, 32], [30, 24, 48, 14], [30, 15, 42, 32]],//38
[[30, 117, 20, 4], [28, 47, 40, 7], [30, 24, 43, 22], [30, 15, 10, 67]], //39
[[30, 118, 19, 6], [28, 47, 18, 31], [30, 24, 34, 34], [30, 15, 20, 61]],//40
];
export const blockInfo = (version, qi) => blockTable[version][qi].slice();
export const quarityIndex = c => quarities.indexOf(c);
export const codeBytes = (version, qindex) => {
const [parity, b1data, b1count, b2count] = blockTable[version][qindex];
return (parity + b1data) * b1count + (parity + b1data + 1) * b2count;
};
export const dataBytes = (version, qindex) => {
const [parity, b1data, b1count, b2count] = blockTable[version][qindex];
return b1data * b1count + (b1data + 1) * b2count;
};
export const splitBlocks = (bytes, b1data, b1count, b2count) => {
const b2data = b1data + 1, b2offs = b1data * b1count;
const b1blocks = range(b1count).map(
i => bytes.slice(i * b1data, (i + 1) * b1data));
const b2blocks = range(b2count).map(
i => bytes.slice(b2offs + i * b2data, b2offs + (i + 1) * b2data));
return [...b1blocks, ...b2blocks];
};
export const transpose = m => range(m[0].length).map(i => m.map(l => l[i]));
export const interleaveBlocks = (blocks, b1data, b1count) => {
const former = transpose(blocks.map(b => b.slice(0, b1data))).flat();
const latter = blocks.slice(b1count).flatMap(b => b[b.length - 1]);
return [...former, ...latter];
};
export const encodeMessage = (bytes, version, qindex) => {
console.assert(bytes.length === dataBytes(version, qindex));
const [paritySize, b1data, b1count, b2count] = blockTable[version][qindex];
const rscode = RSCode(poly, paritySize);
const blocks = splitBlocks(Array.from(bytes), b1data, b1count, b2count);
const parities = blocks.map(block => rscode.parity(block));
const iblocks = interleaveBlocks(blocks, b1data, b1count);
const iparities = transpose(parities).flat();
return [...iblocks, ...iparities];
};
// BCH encode
// - https://www.thonky.com/qr-code-tutorial/format-version-information
const pf2poly = PF2Poly();
const formatBit = 15, formatCarry = 10, formatGen = 0b10100110111;
const quarityBits = [1, 0, 3, 2];
export const formatMask = 0b101010000010010;
export const formatValue = (qIndex, maskId) => {
const data = pf2poly.carry((quarityBits[qIndex] << 3) | maskId, formatCarry);
return pf2poly.sub(data, pf2poly.mod(data, formatGen));
};
export const formatBits = (qIndex, maskId) => {
const coded = formatValue(qIndex, maskId) ^ formatMask;
return range(formatBit).map(k => (coded >>> k) & 1).reverse();
};
// Version bits uses Extended BCH code (18, 6) such as
// - Use primitive element a an GF2n(11, 0b101011100011)
// - the versionGen is (x-a^0)*...*(x-a^2^11) => 0b11 * 0b101011100011
// - error posistion k is of e^2^k (not e^k as usual BCH code)
const versionBit = 18, versionCarry = 12, versionGen = 0b1111100100101;
export const versionBits = (version) => {
const data = pf2poly.carry(version, versionCarry);
const coded = pf2poly.sub(data, pf2poly.mod(data, versionGen));
return range(formatBit).map(k => (coded >>> k) & 1);
};
Raw
qrrscode-example.js
import {range, GF2n, Polynomial} from "./qrgf.js";
import {RSCode} from "./qrrscode.js";
{
const gf = GF2n(8, 0b100011101);
const poly = Polynomial(gf);
const d = 7;
const rscode = RSCode(poly, d);
const msg = [
0b10000000, 0b01000100, 0b10000101, 0b10100111, 0b01001001, 0b10100111,
0b10001011, 0b01101100, 0b00000000, 0b11101100, 0b00010001, 0b11101100,
0b00010001, 0b11101100, 0b00010001, 0b11101100, 0b00010001, 0b11101100,
0b00010001,
];
console.log("gen", rscode.gen);
const parity = rscode.parity(msg);
//console.log("parity", parity.map(c => c.toString(2).padStart(8, "0")));
console.log("parity", parity);
const coded = [...msg, ...parity];
const rx = [...coded];
rx[0] ^= 0xff;
rx[12] ^= 0xed;
rx[24] ^= 0x10;
try {
const cx = rscode.decode(rx);
console.log("recovered", cx.every((c, i) => coded[i] === c));
} catch (error) {
console.log(error.message);
}
}
{
const gf = GF2n(8, 0b100011101);
const poly = Polynomial(gf);
const d = 18;
const rscode = RSCode(poly, d);
//const msg0 = range(7).flatMap(_ => [236, 17]);
//const msg = [...msg0, 236];
const msg0 = range(7).flatMap(_ => [17, 236]);
const msg = [...msg0, 17];
const parity = rscode.parity(msg);
console.log(parity);
const coded = [...msg, ...parity];
const rx = [...coded];
rx[0] ^= 0xff;
rx[12] ^= 0xed;
rx[24] ^= 0x10;
rx[32] ^= 0x12;
rx[3] ^= 0x12;
rx[9] ^= 0x52;
rx[11] ^= 0x94;
rx[21] ^= 0xfe;
//rx[19] ^= 0x5f;
rx[29] ^= 0xac;
try {
const cx = rscode.decode(rx);
console.log("recovered", cx.every((c, i) => coded[i] === c));
} catch (error) {
console.log(error.message);
}
}
Raw
qrrscode.js
const range = n => [...Array(n).keys()];
export const findLinearRecurrence = (poly, s) => {
// Berlekamp-Massey algorithm
// NOTE: s as [s0, s1, ...]
const {K, one, add, sub, scale, carry, mul, coef} = poly;
let cx = one, cl = 1, bx = one, bl = 1, b = K.one, m = 0;
for (let i = 0; i < s.length; i++) {
const d = K.sum(range(cl).map(k => K.mul(coef(cx, k), s[i - k])));
m++;
if (K.isZero(d)) continue;
const tx = cx, tl = cl;
cx = sub(cx, scale(carry(bx, m), K.div(d, b)));
cl = Math.max(cl, bl + m);
if (cl > tl) [bx, bl, b, m] = [tx, tl, d, 0];
}
return cx;
};
export const RSCode = (poly, d, b = 0) => {
const {
K, add, sub, carry, mul, mod, sum, prod, monomial, apply, diff} = poly;
const gen = prod(range(d).map(
k => add(monomial(K.one, 1), monomial(K.alpha(b + k), 0))));
const parity = msg => mod(carry(msg, d), gen);
const decode = rx => {
const N = rx.length;
// NOTE: synds as [s0, s1, ...]
const synds = range(d).map(k => apply(rx, K.alpha(b + k)));
if (synds.every(si => K.isZero(si))) return rx;
const lx = findLinearRecurrence(poly, synds);
if (lx.length - 1 > (d >>> 1)) throw Error(
"RSCode.decode: too many errors");
// NOTE: positions as power of a: index of cx as cx[N - 1 - k]
const pos = range(N).filter(k => K.isZero(apply(lx, K.alpha(-k))));
const sx = sum(synds.map((sk, k ) => monomial(sk, k)));
const ox = mod(mul(sx, lx), monomial(K.one, d));
const dlx = diff(lx);
// NOTE: errors index is same as positions index (not array index)
const errors = pos.map(k => {
const akinv = K.alpha(-k);
const oAkinv = apply(ox, akinv);
const dlAkinv = apply(dlx, akinv);
const ak1b = K.alpha(k * (1 - b));
return K.neg(K.mul(ak1b, K.div(oAkinv, dlAkinv)));
});
const ex = sum(pos.map((k, i) => monomial(errors[i], k)));
return sub(rx, ex);
};
return {poly, b, d, gen, parity, decode};
};
@bellbind
Copy link
Author

bellbind commented Apr 3, 2020 •
edited
Loading

Browser demo

order to read modules

module for data

  • qrgf.js: GF(2^n) and Polynomial as Array implementation
  • qrrscode.js: Reed-Solomon code implementation
  • bitstream.js: big endian bit reader/writer
  • cp2sjis.js: Unicode char to SJIS code table with TextDecoder
  • qrdata.js: packing text data to bitstream
  • qrmessage.js: format coded data with parities

modules for image

  • qrframe.js: generate QR code frame image with markers
  • qrencode.js: embed masked coded data into frame image
  • qrevaluation.js: compute penalties for each masked frame image
  • qrimagedata.js: render frame image to 2D-canvas ImageData or SVG text

modules for QR code generator application

  • qrauto.js: find fit versions, the best packed data
  • qrcode.js: all-in-one QR code generator and Configurable QR code builder

modules for QR code decoder/capture

  • qrdecode.js: QR code decoder from frame array of qrcode.js
  • qrcapture.js: Capturing frame from ImageData (binarize image, detect 3-finders, convert frame from binarized image)

modules for qr-code Custom Element

  • qr-code.js: qr-code custom element with MutationObserver

console based examples for each module

  • https://gist.githack.com/bellbind/a057eee7e532f63f71d164fa7c8342a0/raw/qrgf-example.js
  • https://gist.githack.com/bellbind/a057eee7e532f63f71d164fa7c8342a0/raw/qrrscode-example.js
  • https://gist.githack.com/bellbind/a057eee7e532f63f71d164fa7c8342a0/raw/qrdata-example.js
  • https://gist.githack.com/bellbind/a057eee7e532f63f71d164fa7c8342a0/raw/qrmessage-example.js
  • https://gist.githack.com/bellbind/a057eee7e532f63f71d164fa7c8342a0/raw/qrdecode-example.js

HTML based examples for each module

@bellbind
Copy link
Author

bellbind commented Jun 1, 2020 •
edited
Loading

Application: WIFI connect URL for QR code

  • WIFI:T:WPA;S:yourssid;P:yourpass
  • WIFI:T:WEP;S:yourssid;P:yourpass
  • WIFI:T:NOPASS;S:yourssid

see: https://github.com/zxing/zxing/wiki/Barcode-Contents#wifi-network-config-android

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment