summaryrefslogtreecommitdiff
path: root/source/codes/Qr.mc
diff options
context:
space:
mode:
Diffstat (limited to 'source/codes/Qr.mc')
-rw-r--r--source/codes/Qr.mc971
1 files changed, 680 insertions, 291 deletions
diff --git a/source/codes/Qr.mc b/source/codes/Qr.mc
index 1fa69da..1fac051 100644
--- a/source/codes/Qr.mc
+++ b/source/codes/Qr.mc
@@ -9,11 +9,14 @@
// codewords 0xEC 0x11), split it into blocks, add Reed-Solomon
// codewords (QrTables.BLOCKS), interleave.
// 3. Draw the function patterns, place the codewords in the zigzag.
-// 4. Score all 8 masks with the ISO 18004:2015 penalty rules exactly as
-// segno computes them (format and version areas still light), keep
-// the lowest, then draw the format and version information.
+// 4. Pack the rows and columns 16 modules per word, then score all 8
+// masks with the ISO 18004:2015 penalty rules exactly as segno
+// computes them (format and version areas still light), with bit
+// operations on the packed lines; keep the lowest.
+// 5. Apply that mask, then draw the format and version information.
// Each step does a bounded amount of work (one RS block, a few columns or
-// rows), because version 40 is far beyond one event's watchdog budget.
+// rows, a few hundred packed words), because version 40 is far beyond one
+// event's watchdog budget.
// Verified against segno with forced version and mask, and by decoding.
import Toybox.Lang;
@@ -26,15 +29,31 @@ module Qr {
const ALPHANUMERIC = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"; // lint: allow-literal (QR alphanumeric set)
// Format bits per level L, M, Q, H.
const LEVEL_BITS = [1, 0, 3, 2];
- // Modules looked at per job step: well below the 120,000-bytecode
- // watchdog limit of the smallest targets.
- const MODULES_PER_STEP = 2500;
- // Mask scoring costs more per module: the row pass applies the mask and
- // scores N1-N3, the column pass N1 and N3. Sized for the Forerunner
- // 255S's 120,000 bytecodes per event, where 1,200 row modules tripped
- // the watchdog in the UI flow.
- const ROW_MODULES_PER_STEP = 500;
- const COLUMN_MODULES_PER_STEP = 1000;
+ // Modules placed, packed or unmasked per job step. Every step size here
+ // was checked in the simulator by running two steps per event on the
+ // Forerunner 255S (120,000 bytecodes per event): each step stays below
+ // half the watchdog limit.
+ const PLACE_MODULES_PER_STEP = 300;
+ const PACK_MODULES_PER_STEP = 400;
+ const APPLY_MODULES_PER_STEP = 600;
+ // Mask scoring works on packed lines (16 modules per word, see
+ // startPacking); words scored per step. The row pass masks the line and
+ // scores N1, N2, N3 and the dark count, the column pass N1 and N3.
+ const ROW_WORDS_PER_STEP = 100;
+ const COLUMN_WORDS_PER_STEP = 150;
+ // Light bits before each packed line.
+ const PAD = 4;
+ // Phase 0: characters segmented or written per step (the segmentation
+ // costs about 150 bytecodes per character).
+ const SEGMENT_CHARS_PER_STEP = 80;
+ const WRITE_CHARS_PER_STEP = 300;
+ // Phase 1: data symbols times EC symbols per step (about 35 bytecodes each).
+ const ECC_WORK_PER_STEP = 400;
+ // Phase 2: codewords interleaved per step.
+ const INTERLEAVE_PER_STEP = 600;
+ const PREP_SEGMENT = 0;
+ const PREP_WRITE = 1;
+ const PREP_SPLIT = 2;
// The GF(256) field of QR (x^8 + x^4 + x^3 + x^2 + 1), shared.
var field as ReedSolomon.Field? = null;
@@ -70,12 +89,20 @@ module Qr {
return b >= 0x30 && b <= 0x39;
}
+ // The alphanumeric value of byte b, or -1 (table built on first use).
+ var alnumTable as ByteArray? = null;
+
function alnumValue(b as Number) as Number {
- if (b >= 0x80) {
- return -1;
+ var t = alnumTable;
+ if (t == null) {
+ t = new [128]b;
+ var chars = ALPHANUMERIC.toUtf8Array();
+ for (var k = 0; k < chars.size(); k++) {
+ t[chars[k]] = k + 1;
+ }
+ alnumTable = t;
}
- var at = ALPHANUMERIC.find(b.toChar().toString());
- return at == null ? -1 : at;
+ return b < 0x80 ? t[b] - 1 : -1;
}
// Optimal segmentation for a version class: [mode, start, end) triples
@@ -84,64 +111,133 @@ module Qr {
// alphanumeric 11/2, byte 8 bits per character). State j after
// character i: the cheapest encoding so far that continues in mode j;
// choice[i * 3 + j] is the mode character i itself was encoded in.
- function segment(data as ByteArray, v as Number) as Array<Number> {
- var n = data.size();
- var modes = [MODE_BYTE, MODE_ALPHANUMERIC, MODE_NUMERIC];
- var head = [(4 + charCountBits(MODE_BYTE, v)) * 6, (4 + charCountBits(MODE_ALPHANUMERIC, v)) * 6,
- (4 + charCountBits(MODE_NUMERIC, v)) * 6];
- var unit = [48, 33, 20];
- var inf = 0x3FFFFFFF;
- var prev = [head[0], head[1], head[2]];
- // choice[i * 3 + j] = the mode index the segment ending at i in mode j came from.
- var choice = new [n * 3]b;
- for (var i = 0; i < n; i++) {
- var b = data[i];
- var cur = [prev[0] + unit[0], alnumValue(b) >= 0 ? prev[1] + unit[1] : inf, isDigit(b) ? prev[2] + unit[2] : inf];
- choice[i * 3] = 0;
- choice[i * 3 + 1] = 1;
- choice[i * 3 + 2] = 2;
- for (var j = 0; j < 3; j++) {
- for (var k = 0; k < 3; k++) {
- if (k == j || (cur[k] as Number) >= inf) {
- continue;
+ // Resumable: step() handles a bounded number of characters (the
+ // programme, then the walk back and the collection of segments, which
+ // cost far less per character), so a 2,900-byte payload never runs in
+ // one event.
+ class Segmenter {
+ static const MODES = [MODE_BYTE, MODE_ALPHANUMERIC, MODE_NUMERIC];
+ static const INF = 0x3FFFFFFF;
+
+ var segments as Array<Number> = [] as Array<Number>;
+
+ private var _data as ByteArray;
+ private var _head as Array<Number>;
+ private var _prev as Array<Number>;
+ private var _cur as Array<Number> = [0, 0, 0];
+ private var _choice as ByteArray;
+ private var _charModes as ByteArray = []b;
+ private var _i as Number = 0;
+ private var _walk as Number = 0;
+ private var _state as Number = 0;
+ private var _start as Number = 0;
+ private var _collected as Number = 0;
+ private var _done as Boolean = false;
+
+ function initialize(data as ByteArray, v as Number) {
+ _data = data;
+ _head = [(4 + charCountBits(MODE_BYTE, v)) * 6, (4 + charCountBits(MODE_ALPHANUMERIC, v)) * 6,
+ (4 + charCountBits(MODE_NUMERIC, v)) * 6];
+ _prev = [_head[0], _head[1], _head[2]];
+ _choice = new [data.size() * 3]b;
+ }
+
+ // Up to `chars` more characters (of the programme, then of each walk
+ // back); true when segments is ready.
+ function step(chars as Number) as Boolean {
+ var n = _data.size();
+ if (_i < n) {
+ program(chars);
+ } else if (_walk > 0) {
+ walkBack(chars * 4);
+ } else {
+ collect(chars * 4);
+ }
+ return _done;
+ }
+
+ private function program(chars as Number) as Void {
+ var n = _data.size();
+ var head = _head;
+ var prev = _prev;
+ var cur = _cur;
+ var choice = _choice;
+ var stop = _i + chars < n ? _i + chars : n;
+ for (var i = _i; i < stop; i++) {
+ var b = _data[i];
+ cur[0] = prev[0] + 48;
+ cur[1] = alnumValue(b) >= 0 ? prev[1] + 33 : INF;
+ cur[2] = isDigit(b) ? prev[2] + 20 : INF;
+ choice[i * 3] = 0;
+ choice[i * 3 + 1] = 1;
+ choice[i * 3 + 2] = 2;
+ for (var j = 0; j < 3; j++) {
+ for (var k = 0; k < 3; k++) {
+ if (k == j || cur[k] >= INF) {
+ continue;
+ }
+ // State j may follow a character in mode k: a new
+ // segment in mode j starts after it (its header paid now).
+ var switched = (cur[k] + 5) / 6 * 6 + head[j];
+ if (switched < cur[j]) {
+ cur[j] = switched;
+ choice[i * 3 + j] = k;
+ }
}
- // State j may follow a character in mode k: a new segment
- // in mode j starts after it (its header paid now).
- var switched = ((cur[k] as Number) + 5) / 6 * 6 + (head[j] as Number);
- if (switched < (cur[j] as Number)) {
- cur[j] = switched;
- choice[i * 3 + j] = k;
+ }
+ var swap = prev;
+ prev = cur;
+ cur = swap;
+ }
+ _prev = prev;
+ _cur = cur;
+ _i = stop;
+ if (_i >= n) {
+ // The cheapest final mode starts the walk back.
+ var best = 0;
+ for (var j = 1; j < 3; j++) {
+ if (_prev[j] < _prev[best]) {
+ best = j;
}
}
+ _state = best;
+ _charModes = new [n]b;
+ _walk = n;
}
- prev = cur;
}
- // The cheapest final mode, then walk back.
- var best = 0;
- for (var j = 1; j < 3; j++) {
- if ((prev[j] as Number) < (prev[best] as Number)) {
- best = j;
+
+ // From the end: the state after character i says which mode i was in.
+ private function walkBack(chars as Number) as Void {
+ var stop = _walk - chars > 0 ? _walk - chars : 0;
+ for (var i = _walk - 1; i >= stop; i--) {
+ var charMode = _choice[i * 3 + _state];
+ _charModes[i] = charMode;
+ _state = charMode;
+ }
+ _walk = stop;
+ if (_walk == 0) {
+ _choice = []b;
}
}
- // Walk back: the state after character i says which mode i was in.
- var charModes = new [n]b;
- var state = best;
- for (var i = n - 1; i >= 0; i--) {
- var charMode = choice[i * 3 + state];
- charModes[i] = charMode;
- state = charMode;
- }
- var segments = [] as Array<Number>;
- var start = 0;
- for (var i = 1; i <= n; i++) {
- if (i == n || charModes[i] != charModes[start]) {
- segments.add(modes[charModes[start]] as Number);
- segments.add(start);
- segments.add(i);
- start = i;
+
+ // From the start: runs of one mode become segments.
+ private function collect(chars as Number) as Void {
+ var n = _data.size();
+ var stop = _collected + chars < n ? _collected + chars : n;
+ for (var i = _collected + 1; i <= stop; i++) {
+ if (i == n || _charModes[i] != _charModes[_start]) {
+ segments.add(MODES[_charModes[_start]] as Number);
+ segments.add(_start);
+ segments.add(i);
+ _start = i;
+ }
+ }
+ _collected = stop;
+ if (_collected >= n) {
+ _charModes = []b;
+ _done = true;
}
}
- return segments;
}
// Bits needed for segments at version v.
@@ -162,25 +258,28 @@ module Qr {
return total;
}
- // A growing bit stream packed into codewords.
+ // A growing bit stream packed into codewords. Bits wait in `_acc`
+ // until a whole byte is ready.
class BitWriter {
var bytes as ByteArray = []b;
var bitCount as Number = 0;
+ private var _acc as Number = 0;
+ private var _accBits as Number = 0;
+
function initialize() {
}
+ // The low `count` bits of value (count <= 16), most significant first.
function put(value as Number, count as Number) as Void {
- for (var i = count - 1; i >= 0; i--) {
- if (bitCount % 8 == 0) {
- bytes.add(0);
- }
- if (((value >> i) & 1) == 1) {
- var at = bitCount / 8;
- bytes[at] = bytes[at] | (0x80 >> (bitCount % 8));
- }
- bitCount++;
+ _acc = (_acc << count) | (value & ((1 << count) - 1));
+ _accBits += count;
+ bitCount += count;
+ while (_accBits >= 8) {
+ _accBits -= 8;
+ bytes.add((_acc >> _accBits) & 0xFF);
}
+ _acc = _acc & ((1 << _accBits) - 1);
}
}
@@ -230,8 +329,32 @@ module Qr {
private var _score as Number = 0;
private var _dark as Number = 0;
private var _maskPass as Number = 0;
- private var _masked as ByteArray = []b;
- private var _prevRow as ByteArray = []b;
+ // Phase 0 (buildCodewords).
+ private var _prep as Number = PREP_SEGMENT;
+ private var _class as Number = 0;
+ private var _segmenter as Segmenter? = null;
+ private var _segments as Array<Number> = [] as Array<Number>;
+ private var _writer as BitWriter? = null;
+ private var _charAt as Number = -1;
+ private var _encoder as ReedSolomon.Encoder? = null;
+ // Packed lines (startPacking): rows and columns, their non-function
+ // modules, the current mask's patterns, scratch lines.
+ private var _words as Number = 0;
+ private var _rows as Array<Number> = [] as Array<Number>;
+ private var _rowFree as Array<Number> = [] as Array<Number>;
+ private var _cols as Array<Number> = [] as Array<Number>;
+ private var _colFree as Array<Number> = [] as Array<Number>;
+ private var _lineMask as Array<Number> = [] as Array<Number>;
+ private var _n1Valid as Array<Number> = [] as Array<Number>;
+ private var _n2Valid as Array<Number> = [] as Array<Number>;
+ private var _rowPattern as Array<Array<Number>> = [] as Array<Array<Number>>;
+ private var _columnPattern as Array<Array<Number>> = [] as Array<Array<Number>>;
+ private var _patternMask as Number = -1;
+ private var _cur as Array<Number> = [] as Array<Number>;
+ private var _prev as Array<Number> = [] as Array<Number>;
+
+ // The penalty of each mask, in order (empty with a forced mask).
+ var scores as Array<Number> = [] as Array<Number>;
// ec: 0 L, 1 M, 2 Q, 3 H. forceVersion 0 = smallest that fits;
// forceMask -1 = best by penalty.
@@ -245,7 +368,7 @@ module Qr {
// Progress 0-100 for the UI.
function percent() as Number {
- return _phase * 100 / 6;
+ return _phase * 100 / 7;
}
// The code as a generic matrix with QR's 4-module quiet zone.
@@ -264,55 +387,146 @@ module Qr {
} else if (_phase == 3) {
placeStep();
} else if (_phase == 4) {
- maskStep();
+ packStep();
} else if (_phase == 5) {
- finish();
+ maskStep();
+ } else if (_phase == 6) {
+ applyStep();
}
- return _phase >= 6 || error != null;
+ return _phase >= 7 || error != null;
}
- // Phase 0: segments, version, bit stream, blocks.
+ // Phase 0: segments and version, then the bit stream, then blocks,
+ // each in bounded steps:
+ // segment the dynamic programme for one version class (versions
+ // 1-9, 10-26, 27-40 count characters with different
+ // widths), SEGMENT_CHARS_PER_STEP characters per step,
+ // until a class fits the payload;
+ // write the segments into the bit stream, WRITE_CHARS_PER_STEP
+ // characters per step, then terminator and padding;
+ // split the codewords into the Reed-Solomon blocks.
private function buildCodewords() as Void {
+ if (_prep == PREP_SEGMENT) {
+ segmentStep();
+ } else if (_prep == PREP_WRITE) {
+ writeStep();
+ } else {
+ splitBlocks();
+ }
+ }
+
+ private function segmentStep() as Void {
if (_data.size() == 0) {
error = "QR needs some text";
return;
}
- var segments = null;
- var v = _version;
- if (v > 0) {
- segments = segment(_data, v);
- if (segmentBits(segments, v) > dataCodewords(v, _ec) * 8) {
- error = "too long for QR version " + v;
+ var lowest = [1, 10, 27] as Array<Number>;
+ var highest = [9, 26, 40] as Array<Number>;
+ var forced = _version;
+ var segmenter = _segmenter;
+ if (segmenter == null) {
+ if (forced > 0) {
+ _class = forced <= 9 ? 0 : (forced <= 26 ? 1 : 2);
+ }
+ // Skip a class the payload can't fit even as digits (10
+ // bits per 3 characters), without segmenting for it.
+ while (forced == 0 && _class < 2 && _data.size() * 10 / 3 > dataCodewords(highest[_class], _ec) * 8) {
+ _class++;
+ }
+ segmenter = new Segmenter(_data, lowest[_class]);
+ _segmenter = segmenter;
+ }
+ if (!segmenter.step(SEGMENT_CHARS_PER_STEP)) {
+ return;
+ }
+ _segmenter = null;
+ var segments = segmenter.segments;
+ var bits = segmentBits(segments, lowest[_class]);
+ if (forced > 0) {
+ if (bits > dataCodewords(forced, _ec) * 8) {
+ error = "too long for QR version " + forced;
return;
}
} else {
- for (var c = 0; c < 3 && v == 0; c++) {
- var lo = [1, 10, 27][c] as Number;
- var hi = [9, 26, 40][c] as Number;
- var s = segment(_data, lo);
- var bits = segmentBits(s, lo);
- for (var tryV = lo; tryV <= hi; tryV++) {
- if (bits <= dataCodewords(tryV, _ec) * 8) {
- v = tryV;
- segments = s;
- break;
- }
+ for (var v = lowest[_class]; v <= highest[_class] && _version == 0; v++) {
+ if (bits <= dataCodewords(v, _ec) * 8) {
+ _version = v;
}
}
- if (v == 0) {
- error = "too long for a QR code at this error correction level (" + _data.size() + " bytes, at most "
- + dataCodewords(40, _ec) + " in byte mode)";
+ if (_version == 0) {
+ _class++;
+ if (_class > 2) {
+ error = "too long for a QR code at this error correction level (" + _data.size() + " bytes, at most "
+ + dataCodewords(40, _ec) + " in byte mode)";
+ }
return;
}
}
- _version = v;
- var capacity = dataCodewords(v, _ec);
- var w = new BitWriter();
- var segs = segments as Array<Number>;
- for (var s = 0; s < segs.size(); s += 3) {
- writeSegment(w, segs[s], segs[s + 1], segs[s + 2]);
+ _segments = segments;
+ _writer = new BitWriter();
+ _cursor = 0;
+ _charAt = -1;
+ _prep = PREP_WRITE;
+ }
+
+ // Write segment characters; _cursor is the segment (index into the
+ // triples), _charAt the next character, -1 before its header.
+ private function writeStep() as Void {
+ var w = _writer as BitWriter;
+ var segs = _segments;
+ var d = _data;
+ var budget = WRITE_CHARS_PER_STEP;
+ while (budget > 0 && _cursor < segs.size()) {
+ var mode = segs[_cursor];
+ var end = segs[_cursor + 2];
+ if (_charAt < 0) {
+ _charAt = segs[_cursor + 1];
+ w.put(mode, 4);
+ w.put(end - _charAt, charCountBits(mode, _version));
+ }
+ var i = _charAt;
+ // Whole groups (3 digits, 2 alphanumerics) per step.
+ var group = mode == MODE_NUMERIC ? 3 : (mode == MODE_ALPHANUMERIC ? 2 : 1);
+ var take = budget / group * group;
+ var stop = i + (take > group ? take : group);
+ stop = stop < end ? stop : end;
+ budget -= stop - i;
+ if (mode == MODE_NUMERIC) {
+ while (i < stop) {
+ var count = stop - i >= 3 ? 3 : stop - i;
+ var value = 0;
+ for (var k = 0; k < count; k++) {
+ value = value * 10 + d[i + k] - 0x30;
+ }
+ w.put(value, [0, 4, 7, 10][count] as Number);
+ i += count;
+ }
+ } else if (mode == MODE_ALPHANUMERIC) {
+ while (i < stop) {
+ if (stop - i >= 2) {
+ w.put(alnumValue(d[i]) * 45 + alnumValue(d[i + 1]), 11);
+ i += 2;
+ } else {
+ w.put(alnumValue(d[i]), 6);
+ i += 1;
+ }
+ }
+ } else {
+ for (; i < stop; i++) {
+ w.put(d[i], 8);
+ }
+ }
+ _charAt = stop;
+ if (stop >= end) {
+ _cursor += 3;
+ _charAt = -1;
+ }
+ }
+ if (_cursor < segs.size()) {
+ return;
}
// Terminator, byte alignment, pad codewords.
+ var capacity = dataCodewords(_version, _ec);
var terminator = capacity * 8 - w.bitCount;
w.put(0, terminator < 4 ? terminator : 4);
if (w.bitCount % 8 != 0) {
@@ -323,8 +537,14 @@ module Qr {
w.bytes.add(pad);
pad = pad == 0xEC ? 0x11 : 0xEC;
}
- // Split into blocks.
- var i = ((v - 1) * 4 + _ec) * 5;
+ _segments = [] as Array<Number>;
+ _prep = PREP_SPLIT;
+ }
+
+ private function splitBlocks() as Void {
+ var bytes = (_writer as BitWriter).bytes;
+ _writer = null;
+ var i = ((_version - 1) * 4 + _ec) * 5;
var t = QrTables.BLOCKS;
var at = 0;
for (var g = 0; g < 2; g++) {
@@ -333,7 +553,7 @@ module Qr {
for (var b = 0; b < count; b++) {
var block = new [len] as Array<Number>;
for (var k = 0; k < len; k++) {
- block[k] = w.bytes[at + k];
+ block[k] = bytes[at + k];
}
at += len;
_blocks.add(block);
@@ -343,88 +563,89 @@ module Qr {
_phase = 1;
}
- private function writeSegment(w as BitWriter, mode as Number, start as Number, end as Number) as Void {
- var count = end - start;
- w.put(mode, 4);
- w.put(count, charCountBits(mode, _version));
- var d = _data;
- if (mode == MODE_NUMERIC) {
- var i = start;
- while (i < end) {
- var take = end - i >= 3 ? 3 : end - i;
- var value = 0;
- for (var k = 0; k < take; k++) {
- value = value * 10 + d[i + k] - 0x30;
- }
- w.put(value, [0, 4, 7, 10][take] as Number);
- i += take;
- }
- } else if (mode == MODE_ALPHANUMERIC) {
- var i = start;
- while (i < end) {
- if (end - i >= 2) {
- w.put(alnumValue(d[i]) * 45 + alnumValue(d[i + 1]), 11);
- i += 2;
- } else {
- w.put(alnumValue(d[i]), 6);
- i += 1;
- }
- }
- } else {
- for (var i = start; i < end; i++) {
- w.put(d[i], 8);
+ // Phase 1: Reed-Solomon codewords, ECC_WORK_PER_STEP data symbols
+ // times EC symbols per step (a version 40 block is 30 x 118).
+ private function eccStep() as Void {
+ var encoder = _encoder;
+ if (encoder == null) {
+ var i = ((_version - 1) * 4 + _ec) * 5;
+ var n = QrTables.BLOCKS[i] as Number;
+ var fresh = !theField().hasGenerator(n);
+ encoder = new ReedSolomon.Encoder(theField(), _blocks[_cursor], n);
+ _encoder = encoder;
+ if (fresh) {
+ return; // the generator took this step
}
}
- }
-
- // Phase 1: Reed-Solomon codewords, one block per step.
- private function eccStep() as Void {
- var i = ((_version - 1) * 4 + _ec) * 5;
- var n = QrTables.BLOCKS[i] as Number;
- _ecBlocks.add(ReedSolomon.ecc(theField(), _blocks[_cursor], n));
+ if (!encoder.step(ECC_WORK_PER_STEP / encoder.remainder.size())) {
+ return;
+ }
+ _encoder = null;
+ _ecBlocks.add(encoder.remainder);
_cursor++;
if (_cursor >= _blocks.size()) {
+ _cursor = 0;
+ _codewords = []b;
_phase = 2;
}
}
- // Phase 2: interleave codewords; draw the function patterns.
- private function interleaveAndDrawFunctions() as Void {
- var out = []b;
- var longest = 0;
- for (var b = 0; b < _blocks.size(); b++) {
- if (_blocks[b].size() > longest) {
- longest = _blocks[b].size();
- }
- }
- for (var k = 0; k < longest; k++) {
- for (var b = 0; b < _blocks.size(); b++) {
- if (k < _blocks[b].size()) {
- out.add(_blocks[b][k]);
+ // Phase 2: interleave the codewords, INTERLEAVE_PER_STEP per step
+ // (_cursor is the position within the blocks, data then EC), then
+ // draw the function patterns in a step of their own.
+ private function interleaveStep() as Void {
+ var longest = _blocks[_blocks.size() - 1].size(); // group-2 blocks are the longer ones
+ var ecLen = _ecBlocks[0].size();
+ var out = _codewords;
+ var budget = INTERLEAVE_PER_STEP;
+ while (_cursor < longest + ecLen && budget > 0) {
+ var k = _cursor;
+ var blocks = k < longest ? _blocks : _ecBlocks;
+ var at = k < longest ? k : k - longest;
+ for (var b = 0; b < blocks.size(); b++) {
+ if (at < blocks[b].size()) {
+ out.add(blocks[b][at]);
}
}
+ budget -= blocks.size();
+ _cursor++;
}
- var ecLen = _ecBlocks[0].size();
- for (var k = 0; k < ecLen; k++) {
- for (var b = 0; b < _ecBlocks.size(); b++) {
- out.add(_ecBlocks[b][k]);
- }
+ if (_cursor < longest + ecLen) {
+ return;
}
- _codewords = out;
_blocks = [] as Array<Array<Number>>;
_ecBlocks = [] as Array<Array<Number>>;
- drawFunctionPatterns();
- _cursor = _size - 1; // right column of the current column pair
- _bitIndex = 0;
- _phase = 3;
+ _cursor = -1;
}
- private function drawFunctionPatterns() as Void {
+ // After interleaving, _cursor counts down through the drawing:
+ // -1 timing and finder patterns, -2 - a alignment row a, then the
+ // format and version areas.
+ private function interleaveAndDrawFunctions() as Void {
+ if (_cursor >= 0) {
+ interleaveStep();
+ return;
+ }
+ var pos = QrTables.ALIGNMENT[_version - 1] as Array<Number>;
+ if (_cursor == -1) {
+ drawTimingAndFinders();
+ } else if (-2 - _cursor < pos.size()) {
+ drawAlignmentRow(pos, -2 - _cursor);
+ } else {
+ reserveFormatAndVersion();
+ _cursor = _size - 1; // right column of the current column pair
+ _bitIndex = 0;
+ _phase = 3;
+ return;
+ }
+ _cursor--;
+ }
+
+ private function drawTimingAndFinders() as Void {
var n = 17 + 4 * _version;
_size = n;
_m = new [n * n]b;
_function = new [n * n]b;
- // Timing patterns.
for (var i = 0; i < n; i++) {
setFunction(6, i, i % 2 == 0 ? 1 : 0);
setFunction(i, 6, i % 2 == 0 ? 1 : 0);
@@ -433,17 +654,21 @@ module Qr {
drawFinder(3, 3);
drawFinder(n - 4, 3);
drawFinder(3, n - 4);
- // Alignment patterns, except where they'd overlap the finders.
- var pos = QrTables.ALIGNMENT[_version - 1] as Array<Number>;
+ }
+
+ // Alignment patterns in row a, except where they'd overlap the finders.
+ private function drawAlignmentRow(pos as Array<Number>, a as Number) as Void {
var count = pos.size();
- for (var a = 0; a < count; a++) {
- for (var b = 0; b < count; b++) {
- if ((a == 0 && b == 0) || (a == 0 && b == count - 1) || (a == count - 1 && b == 0)) {
- continue;
- }
- drawAlignment(pos[a], pos[b]);
+ for (var b = 0; b < count; b++) {
+ if ((a == 0 && b == 0) || (a == 0 && b == count - 1) || (a == count - 1 && b == 0)) {
+ continue;
}
+ drawAlignment(pos[a], pos[b]);
}
+ }
+
+ private function reserveFormatAndVersion() as Void {
+ var n = _size;
// Format areas and the dark module's place stay light until the
// mask is chosen (segno evaluates masks that way; ISO 18004:2015
// 7.8 leaves format information out of the evaluation).
@@ -503,7 +728,7 @@ module Qr {
private function placeStep() as Void {
var n = _size;
var totalBits = _codewords.size() * 8;
- var budget = MODULES_PER_STEP;
+ var budget = PLACE_MODULES_PER_STEP;
while (_cursor >= 1 && budget > 0) {
var right = _cursor == 6 ? 5 : _cursor;
var upward = ((right + 1) & 2) == 0;
@@ -523,32 +748,167 @@ module Qr {
}
if (_cursor < 1) {
_codewords = []b;
- _maskIndex = _forceMask >= 0 ? _forceMask : 0;
_cursor = 0;
- _score = 0;
- _dark = 0;
+ startPacking();
_phase = 4;
}
}
- // Phase 4: score masks (or apply the forced one). Per mask, two
- // passes: the rows (apply the mask into a copy, then N1, N2, N3 and
- // the dark count), then the columns (N1, N3), each in steps sized to
- // its cost per module.
+ // ---- Packed lines (M8) ----------------------------------------
+ // Mask scoring works on lines packed 16 modules per Number, so the
+ // penalty rules run as a few bit operations per 16 modules instead
+ // of a loop per module. Line layout: module i of a row or column is
+ // bit (i + PAD) of the line, counted from bit 0 of word 0; PAD light
+ // bits before the line and at least 16 after it let the N3 test look
+ // 4 modules back and 10 ahead without special cases (outside the
+ // symbol counts as light, which is what segno's clipped checks do).
+ // Rows and columns are packed once; each mask is then
+ // data XOR (pattern AND not-function), word by word.
+
+ private function startPacking() as Void {
+ var n = _size;
+ var w = (n + PAD) / 16 + 2;
+ _words = w;
+ // Zeroed line by line with addAll (native), not word by word.
+ var zeros = new [w] as Array<Number>;
+ for (var k = 0; k < w; k++) {
+ zeros[k] = 0;
+ }
+ _rows = [] as Array<Number>;
+ _rowFree = [] as Array<Number>;
+ _cols = [] as Array<Number>;
+ _colFree = [] as Array<Number>;
+ for (var line = 0; line < n; line++) {
+ _rows.addAll(zeros);
+ _rowFree.addAll(zeros);
+ _cols.addAll(zeros);
+ _colFree.addAll(zeros);
+ }
+ _lineMask = bitRange(PAD, n + PAD - 1);
+ _n1Valid = bitRange(PAD, n + PAD - 5);
+ _n2Valid = bitRange(PAD, n + PAD - 2);
+ _cur = new [w] as Array<Number>;
+ _prev = new [w] as Array<Number>;
+ }
+
+ // Words with bits first..last set.
+ private function bitRange(first as Number, last as Number) as Array<Number> {
+ var out = new [_words] as Array<Number>;
+ for (var k = 0; k < _words; k++) {
+ var word = 0;
+ for (var b = 0; b < 16; b++) {
+ var p = k * 16 + b;
+ if (p >= first && p <= last) {
+ word |= 1 << b;
+ }
+ }
+ out[k] = word;
+ }
+ return out;
+ }
+
+ // Phase 4: pack rows and columns (modules and the non-function
+ // mask), a few rows per step.
+ private function packStep() as Void {
+ var n = _size;
+ var w = _words;
+ var rows = PACK_MODULES_PER_STEP / n;
+ for (var r = 0; r < rows && _cursor < n; r++) {
+ var y = _cursor;
+ var py = y + PAD;
+ var colWord = py >> 4;
+ var colBit = 1 << (py & 15);
+ for (var x = 0; x < n; x++) {
+ var at = y * n + x;
+ var px = x + PAD;
+ var rowAt = y * w + (px >> 4);
+ var rowBit = 1 << (px & 15);
+ var colAt = x * w + colWord;
+ if (_m[at] != 0) {
+ _rows[rowAt] = _rows[rowAt] | rowBit;
+ _cols[colAt] = _cols[colAt] | colBit;
+ }
+ if (_function[at] == 0) {
+ _rowFree[rowAt] = _rowFree[rowAt] | rowBit;
+ _colFree[colAt] = _colFree[colAt] | colBit;
+ }
+ }
+ _cursor++;
+ }
+ if (_cursor < n) {
+ return;
+ }
+ _function = []b;
+ _cursor = 0;
+ _maskIndex = _forceMask >= 0 ? _forceMask : 0;
+ _patternMask = -1;
+ _score = 0;
+ _dark = 0;
+ _maskPass = 0;
+ _phase = 5;
+ }
+
+ // Mask m as packed lines: rowPattern[r] is row r (mod 12), across
+ // the columns; columnPattern[c] is column c (mod 12), down the
+ // rows. Every mask repeats every 12 modules along a row or a
+ // column (mask 4 every 6 across and 4 down, the others every 2, 3
+ // or 6), and every 12 lines; so twelve values are computed and
+ // repeated over 48 bits (three words, a multiple of 12), then over
+ // the line. maskBit gets coordinates shifted by 12 (the same mask
+ // value) so they are never negative.
+ private function buildPatterns(m as Number) as Void {
+ _rowPattern = [] as Array<Array<Number>>;
+ _columnPattern = [] as Array<Array<Number>>;
+ for (var r = 0; r < 12; r++) {
+ _rowPattern.add(repeated(m, r, true));
+ _columnPattern.add(repeated(m, r, false));
+ }
+ _patternMask = m;
+ }
+
+ private function repeated(m as Number, fixed as Number, alongRow as Boolean) as Array<Number> {
+ // Twelve mask values, starting at line position -PAD (+12).
+ var twelve = new [12]b;
+ for (var i = 0; i < 12; i++) {
+ if (alongRow ? maskBit(m, 12 - PAD + i, fixed) : maskBit(m, fixed, 12 - PAD + i)) {
+ twelve[i] = 1;
+ }
+ }
+ var period = [0, 0, 0];
+ var at = 0;
+ for (var p = 0; p < 48; p++) {
+ if (twelve[at] != 0) {
+ period[p >> 4] = (period[p >> 4] as Number) | (1 << (p & 15));
+ }
+ at = at == 11 ? 0 : at + 1;
+ }
+ var out = new [_words] as Array<Number>;
+ for (var k = 0; k < _words; k++) {
+ out[k] = (period[k % 3] as Number) & (_lineMask[k] as Number);
+ }
+ return out;
+ }
+
+ // Phase 5: score masks (or take the forced one). Per mask: build its
+ // patterns (one step), then the rows (N1, N2, N3 and the dark count)
+ // and the columns (N1, N3), a bounded number of words per step.
private function maskStep() as Void {
if (_forceMask >= 0) {
_bestMask = _forceMask;
- _phase = 5;
+ _phase = 6;
+ return;
+ }
+ if (_patternMask != _maskIndex) {
+ buildPatterns(_maskIndex);
return;
}
var n = _size;
- var lines = (_maskPass == 0 ? ROW_MODULES_PER_STEP : COLUMN_MODULES_PER_STEP) / n;
+ var lines = (_maskPass == 0 ? ROW_WORDS_PER_STEP : COLUMN_WORDS_PER_STEP) / _words;
if (lines < 1) {
lines = 1;
}
for (var l = 0; l < lines && _cursor < n; l++) {
if (_maskPass == 0) {
- applyMaskRow(_cursor);
scoreRow(_cursor);
} else {
scoreColumn(_cursor);
@@ -567,6 +927,7 @@ module Qr {
var total = n * n;
var deviation = (_dark * 100 - 50 * total).abs();
_score += 10 * (deviation / (5 * total));
+ scores.add(_score);
if (_score < _bestScore) {
_bestScore = _score;
_bestMask = _maskIndex;
@@ -576,126 +937,135 @@ module Qr {
_score = 0;
_dark = 0;
if (_maskIndex >= 8) {
- _masked = []b;
- _prevRow = []b;
- _phase = 5;
+ _phase = 6;
}
}
- private function applyMaskRow(y as Number) as Void {
- var n = _size;
- if (_masked.size() != n * n) {
- _masked = new [n * n]b;
- }
- var m = _maskIndex;
- var row = y * n;
- for (var x = 0; x < n; x++) {
- var at = row + x;
- var bit = _m[at];
- if (_function[at] == 0 && maskBit(m, x, y)) {
- bit = bit ^ 1;
- }
- _masked[at] = bit;
+ // Masked line into `into`: data XOR (pattern AND free).
+ private function maskLine(data as Array<Number>, free as Array<Number>, pattern as Array<Number>, line as Number,
+ into as Array<Number>) as Void {
+ var base = line * _words;
+ for (var k = 0; k < _words; k++) {
+ into[k] = (data[base + k] as Number) ^ ((pattern[k] as Number) & (free[base + k] as Number));
}
}
private function scoreRow(y as Number) as Void {
- var n = _size;
- var row = _masked.slice(y * n, y * n + n);
- _score += lineScore(row);
- var prev = _prevRow;
+ var swap = _prev;
+ _prev = _cur;
+ _cur = swap;
+ var cur = _cur;
+ maskLine(_rows, _rowFree, _rowPattern[y % 12], y, cur);
+ _score += lineScore(cur);
+ var pop = popTable();
var dark = 0;
- for (var x = 0; x < n; x++) {
- var c = row[x];
- dark += c;
- // N2: a 2x2 block of one colour with the row above.
- if (y > 0 && x > 0 && c == row[x - 1] && c == prev[x] && c == prev[x - 1]) {
- _score += 3;
- }
+ for (var k = 0; k < _words; k++) {
+ var c = cur[k] as Number;
+ dark += pop[c & 0xFF] + pop[c >> 8];
}
_dark += dark;
- _prevRow = row;
+ if (y == 0) {
+ return;
+ }
+ // N2: 3 for every 2x2 block of one colour (with the row above).
+ var prev = _prev;
+ var blocks = 0;
+ for (var k = 0; k < _words - 1; k++) {
+ var c = (cur[k] as Number) | ((cur[k + 1] as Number) << 16);
+ var q = (prev[k] as Number) | ((prev[k + 1] as Number) << 16);
+ var same = ~((c ^ (c >> 1)) | (q ^ (q >> 1)) | (c ^ q)) & (_n2Valid[k] as Number);
+ if (same != 0) {
+ blocks += pop[same & 0xFF] + pop[same >> 8];
+ }
+ }
+ _score += 3 * blocks;
}
private function scoreColumn(x as Number) as Void {
- var n = _size;
- var column = new [n]b;
- for (var y = 0; y < n; y++) {
- column[y] = _masked[y * n + x];
- }
- _score += lineScore(column);
+ maskLine(_cols, _colFree, _columnPattern[x % 12], x, _cur);
+ _score += lineScore(_cur);
}
- // N1 and N3 of one row or column, in one pass. N1: 3 + (run - 5)
- // for every run of 5 or more equal modules. N3 as segno counts it:
- // 40 for each 1011101 with light modules (up to 4, fewer at the edge)
- // before or after it; after a counted match the search continues
- // behind it, otherwise 4 modules on (found with a rolling 7-bit window).
- private function lineScore(line as ByteArray) as Number {
- var n = line.size();
+ // N1 and N3 of one packed row or column.
+ // N1: 3 + (run - 5) for every run of 5 or more equal modules. A
+ // run of length L has L - 4 windows of 5 equal modules, so N1
+ // is (windows) + 2 * (groups of windows).
+ // N3, as segno counts it: 40 for each 1011101 with 4 light
+ // modules before or after it (fewer at the edge); after a
+ // counted match the search continues behind it, otherwise 4
+ // modules on. Matches are rare, so they are walked one by one.
+ // Positions s below are bit positions 4 before a match's first
+ // module, so every look stays within the two words combined in e.
+ private function lineScore(line as Array<Number>) as Number {
+ var pop = popTable();
var score = 0;
- var run = 1;
- var window = line[0];
+ var carry = 0;
var nextAllowed = 0;
- for (var k = 1; k < n; k++) {
- var c = line[k];
- if (c == line[k - 1]) {
- run++;
- } else {
- if (run >= 5) {
- score += run - 2;
- }
- run = 1;
+ for (var k = 0; k < _words - 1; k++) {
+ var e = (line[k] as Number) | ((line[k + 1] as Number) << 16);
+ var same = ~(e ^ (e >> 1));
+ var windows = same & (same >> 1) & (same >> 2) & (same >> 3) & (_n1Valid[k] as Number);
+ if (windows != 0) {
+ var starts = windows & ~((windows << 1) | carry) & 0xFFFF;
+ score += pop[windows & 0xFF] + pop[windows >> 8] + 2 * (pop[starts & 0xFF] + pop[starts >> 8]);
}
- window = ((window << 1) | c) & 0x7F;
- if (window == 0x5D && k >= 6) {
- var idx = k - 6;
- if (idx >= nextAllowed) {
- var after = idx + 7;
- if (idx == 0 || idx == n - 7 || allLight(line, idx - 4 < 0 ? 0 : idx - 4, idx)
- || allLight(line, after, after + 4 > n ? n : after + 4)) {
- score += 40;
- nextAllowed = idx + 7;
- } else {
- nextAllowed = idx + 4;
- }
+ carry = (windows >> 15) & 1;
+ var match = (e >> 4) & ~(e >> 5) & (e >> 6) & (e >> 7) & (e >> 8) & ~(e >> 9) & (e >> 10) & 0xFFFF;
+ if (match == 0) {
+ continue;
+ }
+ var light = ~(e | (e >> 1) | (e >> 2) | (e >> 3)) | ~((e >> 11) | (e >> 12) | (e >> 13) | (e >> 14));
+ for (var b = 0; b < 16; b++) {
+ var s = k * 16 + b;
+ if (((match >> b) & 1) == 0 || s < nextAllowed) {
+ continue;
+ }
+ if (((light >> b) & 1) != 0) {
+ score += 40;
+ nextAllowed = s + 7;
+ } else {
+ nextAllowed = s + 4;
}
}
}
- if (run >= 5) {
- score += run - 2;
- }
return score;
}
- private function allLight(line as ByteArray, from as Number, to as Number) as Boolean {
- for (var i = from; i < to; i++) {
- if (line[i] != 0) {
- return false;
- }
+ // Phase 6: apply the chosen mask to the module matrix, a few rows
+ // per step (version 40 has 31,329 modules: far too many for one
+ // event).
+ private function applyStep() as Void {
+ if (_patternMask != _bestMask) {
+ buildPatterns(_bestMask);
+ return;
}
- return true;
- }
-
- // Phase 5: apply the chosen mask, draw format and version info.
- private function finish() as Void {
var n = _size;
- var m = _bestMask;
- for (var y = 0; y < n; y++) {
+ var rows = APPLY_MODULES_PER_STEP / n;
+ for (var r = 0; r < rows && _cursor < n; r++) {
+ var y = _cursor;
+ maskLine(_rows, _rowFree, _rowPattern[y % 12], y, _cur);
+ var row = y * n;
for (var x = 0; x < n; x++) {
- var at = y * n + x;
- if (_function[at] == 0 && maskBit(m, x, y)) {
- _m[at] = _m[at] ^ 1;
- }
+ var p = x + PAD;
+ _m[row + x] = ((_cur[p >> 4] as Number) >> (p & 15)) & 1;
}
+ _cursor++;
}
- drawFormat(m);
+ if (_cursor < n) {
+ return;
+ }
+ _rows = [] as Array<Number>;
+ _rowFree = [] as Array<Number>;
+ _cols = [] as Array<Number>;
+ _colFree = [] as Array<Number>;
+ _rowPattern = [] as Array<Array<Number>>;
+ _columnPattern = [] as Array<Array<Number>>;
+ drawFormat(_bestMask);
if (_version >= 7) {
drawVersion();
}
- result = new MatrixCode(n, _m, _version, m);
- _function = []b;
- _phase = 6;
+ result = new MatrixCode(n, _m, _version, _bestMask);
+ _phase = 7;
}
private function drawFormat(mask as Number) as Void {
@@ -707,21 +1077,21 @@ module Qr {
var bits = ((data << 10) | rem) ^ 0x5412;
var n = _size;
for (var i = 0; i <= 5; i++) {
- setFunction(8, i, (bits >> i) & 1);
+ setModule(8, i, (bits >> i) & 1);
}
- setFunction(8, 7, (bits >> 6) & 1);
- setFunction(8, 8, (bits >> 7) & 1);
- setFunction(7, 8, (bits >> 8) & 1);
+ setModule(8, 7, (bits >> 6) & 1);
+ setModule(8, 8, (bits >> 7) & 1);
+ setModule(7, 8, (bits >> 8) & 1);
for (var i = 9; i < 15; i++) {
- setFunction(14 - i, 8, (bits >> i) & 1);
+ setModule(14 - i, 8, (bits >> i) & 1);
}
for (var i = 0; i < 8; i++) {
- setFunction(n - 1 - i, 8, (bits >> i) & 1);
+ setModule(n - 1 - i, 8, (bits >> i) & 1);
}
for (var i = 8; i < 15; i++) {
- setFunction(8, n - 15 + i, (bits >> i) & 1);
+ setModule(8, n - 15 + i, (bits >> i) & 1);
}
- setFunction(8, n - 8, 1);
+ setModule(8, n - 8, 1);
}
private function drawVersion() as Void {
@@ -735,10 +1105,29 @@ module Qr {
var bit = (bits >> i) & 1;
var a = n - 11 + i % 3;
var b = i / 3;
- setFunction(a, b, bit);
- setFunction(b, a, bit);
+ setModule(a, b, bit);
+ setModule(b, a, bit);
+ }
+ }
+
+ private function setModule(x as Number, y as Number, dark as Number) as Void {
+ _m[y * _size + x] = dark;
+ }
+ }
+
+ // A 256-entry table of set-bit counts, built on first use.
+ var popCounts as ByteArray? = null;
+
+ function popTable() as ByteArray {
+ var t = popCounts;
+ if (t == null) {
+ t = new [256]b;
+ for (var i = 1; i < 256; i++) {
+ t[i] = t[i >> 1] + (i & 1);
}
+ popCounts = t;
}
+ return t;
}
// Mask pattern m at column x, row y: true flips a data module.
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-29 10:58:57 +0000