aboutsummaryrefslogtreecommitdiff
path: root/source/codes
diff options
context:
space:
mode:
Diffstat (limited to 'source/codes')
-rw-r--r--source/codes/Codes.mc54
-rw-r--r--source/codes/Qr.mc764
-rw-r--r--source/codes/QrTables.mc97
-rw-r--r--source/codes/ReedSolomon.mc110
4 files changed, 1025 insertions, 0 deletions
diff --git a/source/codes/Codes.mc b/source/codes/Codes.mc
index 70c6c2d..2d307ef 100644
--- a/source/codes/Codes.mc
+++ b/source/codes/Codes.mc
@@ -53,6 +53,60 @@ module Codes {
}
}
+ // A 2D code ready to draw: width x height modules, row-major, 1 = dark,
+ // plus the quiet zone its symbology needs (QR 4, Data Matrix 1, ...).
+ class Matrix {
+ var width as Number;
+ var height as Number;
+ var quiet as Number;
+ var modules as ByteArray;
+
+ function initialize(w as Number, h as Number, quietModules as Number, bits as ByteArray) {
+ width = w;
+ height = h;
+ quiet = quietModules;
+ modules = bits;
+ }
+
+ // Compact form for the encrypted cache: width, height, quiet (one byte
+ // each), then the modules packed 8 per byte.
+ function toBytes() as ByteArray {
+ var out = [width, height, quiet]b;
+ var packed = new [(modules.size() + 7) / 8]b;
+ for (var i = 0; i < modules.size(); i++) {
+ if (modules[i] == 1) {
+ packed[i / 8] = packed[i / 8] | (0x80 >> (i % 8));
+ }
+ }
+ out.addAll(packed);
+ return out;
+ }
+
+ static function fromBytes(data as ByteArray) as Matrix? {
+ if (data.size() < 3) {
+ return null;
+ }
+ var w = data[0];
+ var h = data[1];
+ if (w == 0 || h == 0 || data.size() != 3 + (w * h + 7) / 8) {
+ return null;
+ }
+ var bits = new [w * h]b;
+ for (var i = 0; i < w * h; i++) {
+ bits[i] = (data[3 + i / 8] >> (7 - i % 8)) & 1;
+ }
+ return new Matrix(w, h, data[2], bits);
+ }
+ }
+
+ function isMatrix(symbology as Number) as Boolean {
+ return symbology == QR || symbology == DATAMATRIX || symbology == PDF417 || symbology == AZTEC;
+ }
+
+ function ecLevel(options as Number) as Number {
+ return options & OPT_EC_MASK;
+ }
+
// Why a payload can't be encoded, in words for the user.
class CodeError {
var message as String;
diff --git a/source/codes/Qr.mc b/source/codes/Qr.mc
new file mode 100644
index 0000000..8af0f5a
--- /dev/null
+++ b/source/codes/Qr.mc
@@ -0,0 +1,764 @@
+// Author: cirakg & claude ai
+// Summary: QR Code encoder (ISO/IEC 18004): optimal mode segmentation, versions 1-40, levels L-H, all 8 masks, as a resumable job.
+//
+// Steps (README 12.1):
+// 1. Segment the UTF-8 bytes optimally into numeric, alphanumeric and
+// byte segments (dynamic programming, as in Nayuki's QR library), and
+// pick the smallest version whose capacity at the chosen level fits.
+// 2. Build the bit stream (mode, character count, data, terminator, pad
+// 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.
+// 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.
+// Verified against segno with forced version and mask, and by decoding.
+
+import Toybox.Lang;
+
+module Qr {
+
+ const MODE_NUMERIC = 1;
+ const MODE_ALPHANUMERIC = 2;
+ const MODE_BYTE = 4;
+ 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;
+
+ // The GF(256) field of QR (x^8 + x^4 + x^3 + x^2 + 1), shared.
+ var field as ReedSolomon.Field? = null;
+
+ function theField() as ReedSolomon.Field {
+ var f = field;
+ if (f == null) {
+ f = new ReedSolomon.Field(0x11D, 256, 0);
+ field = f;
+ }
+ return f;
+ }
+
+ // Data codewords of version v at level ec (0 L .. 3 H).
+ function dataCodewords(v as Number, ec as Number) as Number {
+ var i = ((v - 1) * 4 + ec) * 5;
+ var b = QrTables.BLOCKS;
+ return (b[i + 1] as Number) * (b[i + 2] as Number) + (b[i + 3] as Number) * (b[i + 4] as Number);
+ }
+
+ function charCountBits(mode as Number, v as Number) as Number {
+ var c = v <= 9 ? 0 : (v <= 26 ? 1 : 2);
+ if (mode == MODE_NUMERIC) {
+ return [10, 12, 14][c] as Number;
+ }
+ if (mode == MODE_ALPHANUMERIC) {
+ return [9, 11, 13][c] as Number;
+ }
+ return [8, 16, 16][c] as Number;
+ }
+
+ function isDigit(b as Number) as Boolean {
+ return b >= 0x30 && b <= 0x39;
+ }
+
+ function alnumValue(b as Number) as Number {
+ if (b >= 0x80) {
+ return -1;
+ }
+ var at = ALPHANUMERIC.find(b.toChar().toString());
+ return at == null ? -1 : at;
+ }
+
+ // Optimal segmentation for a version class: [mode, start, end) triples
+ // flattened, by dynamic programming over the bytes (Nayuki's
+ // makeSegmentsOptimally). Costs are in sixths of a bit (numeric 10/3,
+ // 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;
+ }
+ // 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;
+ }
+ }
+ }
+ 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;
+ }
+ }
+ // 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;
+ }
+ }
+ return segments;
+ }
+
+ // Bits needed for segments at version v.
+ function segmentBits(segments as Array<Number>, v as Number) as Number {
+ var total = 0;
+ for (var s = 0; s < segments.size(); s += 3) {
+ var mode = segments[s];
+ var count = segments[s + 2] - segments[s + 1];
+ total += 4 + charCountBits(mode, v);
+ if (mode == MODE_NUMERIC) {
+ total += count / 3 * 10 + [0, 4, 7][count % 3];
+ } else if (mode == MODE_ALPHANUMERIC) {
+ total += count / 2 * 11 + (count % 2) * 6;
+ } else {
+ total += count * 8;
+ }
+ }
+ return total;
+ }
+
+ // A growing bit stream packed into codewords.
+ class BitWriter {
+ var bytes as ByteArray = []b;
+ var bitCount as Number = 0;
+
+ function initialize() {
+ }
+
+ 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++;
+ }
+ }
+ }
+
+ // The QR result: a size x size matrix, row-major, 1 = dark.
+ class MatrixCode {
+ var size as Number;
+ var modules as ByteArray;
+ var version as Number;
+ var mask as Number;
+
+ function initialize(n as Number, bits as ByteArray, v as Number, m as Number) {
+ size = n;
+ modules = bits;
+ version = v;
+ mask = m;
+ }
+ }
+
+ // Encode synchronously (tests and small codes); the app uses QrJob.
+ function encode(text as String, ec as Number, forceVersion as Number, forceMask as Number) as MatrixCode or Codes.CodeError {
+ var job = new QrJob(text, ec, forceVersion, forceMask);
+ Jobs.runToCompletion(job, 1);
+ var err = job.error;
+ return err != null ? new Codes.CodeError(err) : job.result as MatrixCode;
+ }
+
+ class QrJob extends Jobs.Job {
+
+ var error as String? = null;
+ var result as MatrixCode? = null;
+
+ private var _data as ByteArray;
+ private var _ec as Number;
+ private var _version as Number = 0;
+ private var _forceMask as Number;
+ private var _phase as Number = 0;
+ private var _size as Number = 0;
+ private var _m as ByteArray = []b; // modules, row-major
+ private var _function as ByteArray = []b; // 1 = function module
+ private var _blocks as Array<Array<Number>> = [] as Array<Array<Number>>;
+ private var _ecBlocks as Array<Array<Number>> = [] as Array<Array<Number>>;
+ private var _codewords as ByteArray = []b;
+ private var _cursor as Number = 0;
+ private var _bitIndex as Number = 0;
+ private var _maskIndex as Number = 0;
+ private var _bestMask as Number = 0;
+ private var _bestScore as Number = 0x7FFFFFFF;
+ 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;
+
+ // ec: 0 L, 1 M, 2 Q, 3 H. forceVersion 0 = smallest that fits;
+ // forceMask -1 = best by penalty.
+ function initialize(text as String, ec as Number, forceVersion as Number, forceMask as Number) {
+ Job.initialize();
+ _data = Bytes.fromUtf8(text);
+ _ec = ec;
+ _forceMask = forceMask;
+ _version = forceVersion;
+ }
+
+ // Progress 0-100 for the UI.
+ function percent() as Number {
+ return _phase * 100 / 6;
+ }
+
+ function step(budget as Number) as Boolean {
+ if (_phase == 0) {
+ buildCodewords();
+ } else if (_phase == 1) {
+ eccStep();
+ } else if (_phase == 2) {
+ interleaveAndDrawFunctions();
+ } else if (_phase == 3) {
+ placeStep();
+ } else if (_phase == 4) {
+ maskStep();
+ } else if (_phase == 5) {
+ finish();
+ }
+ return _phase >= 6 || error != null;
+ }
+
+ // Phase 0: segments, version, bit stream, blocks.
+ private function buildCodewords() 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;
+ 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;
+ }
+ }
+ }
+ 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)";
+ 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]);
+ }
+ // Terminator, byte alignment, pad codewords.
+ var terminator = capacity * 8 - w.bitCount;
+ w.put(0, terminator < 4 ? terminator : 4);
+ if (w.bitCount % 8 != 0) {
+ w.put(0, 8 - w.bitCount % 8);
+ }
+ var pad = 0xEC;
+ while (w.bytes.size() < capacity) {
+ w.bytes.add(pad);
+ pad = pad == 0xEC ? 0x11 : 0xEC;
+ }
+ // Split into blocks.
+ var i = ((v - 1) * 4 + _ec) * 5;
+ var t = QrTables.BLOCKS;
+ var at = 0;
+ for (var g = 0; g < 2; g++) {
+ var count = t[i + 1 + 2 * g] as Number;
+ var len = t[i + 2 + 2 * g] as Number;
+ 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];
+ }
+ at += len;
+ _blocks.add(block);
+ }
+ }
+ _cursor = 0;
+ _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, 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));
+ _cursor++;
+ if (_cursor >= _blocks.size()) {
+ _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]);
+ }
+ }
+ }
+ 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]);
+ }
+ }
+ _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;
+ }
+
+ private function drawFunctionPatterns() 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);
+ }
+ // Finder patterns with separators.
+ 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>;
+ 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]);
+ }
+ }
+ // 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).
+ for (var i = 0; i <= 8; i++) {
+ if (i != 6) {
+ setFunction(8, i, 0);
+ setFunction(i, 8, 0);
+ }
+ }
+ for (var i = 0; i < 8; i++) {
+ setFunction(n - 1 - i, 8, 0);
+ setFunction(8, n - 1 - i, 0);
+ }
+ setFunction(8, n - 8, 0);
+ // Version areas (light for now).
+ if (_version >= 7) {
+ for (var i = 0; i < 18; i++) {
+ var a = n - 11 + i % 3;
+ var b = i / 3;
+ setFunction(a, b, 0);
+ setFunction(b, a, 0);
+ }
+ }
+ }
+
+ private function setFunction(x as Number, y as Number, dark as Number) as Void {
+ var at = y * _size + x;
+ _m[at] = dark;
+ _function[at] = 1;
+ }
+
+ private function drawFinder(cx as Number, cy as Number) as Void {
+ for (var dy = -4; dy <= 4; dy++) {
+ for (var dx = -4; dx <= 4; dx++) {
+ var x = cx + dx;
+ var y = cy + dy;
+ if (x < 0 || y < 0 || x >= _size || y >= _size) {
+ continue;
+ }
+ var d = (dx.abs() > dy.abs() ? dx.abs() : dy.abs());
+ setFunction(x, y, d != 2 && d != 4 ? 1 : 0);
+ }
+ }
+ }
+
+ private function drawAlignment(cx as Number, cy as Number) as Void {
+ for (var dy = -2; dy <= 2; dy++) {
+ for (var dx = -2; dx <= 2; dx++) {
+ var d = (dx.abs() > dy.abs() ? dx.abs() : dy.abs());
+ setFunction(cx + dx, cy + dy, d != 1 ? 1 : 0);
+ }
+ }
+ }
+
+ // Phase 3: place the codeword bits in the zigzag, a few column pairs
+ // per step.
+ private function placeStep() as Void {
+ var n = _size;
+ var totalBits = _codewords.size() * 8;
+ var budget = MODULES_PER_STEP;
+ while (_cursor >= 1 && budget > 0) {
+ var right = _cursor == 6 ? 5 : _cursor;
+ var upward = ((right + 1) & 2) == 0;
+ for (var vert = 0; vert < n; vert++) {
+ var y = upward ? n - 1 - vert : vert;
+ for (var j = 0; j < 2; j++) {
+ var x = right - j;
+ var at = y * n + x;
+ if (_function[at] == 0 && _bitIndex < totalBits) {
+ _m[at] = (_codewords[_bitIndex >> 3] >> (7 - (_bitIndex & 7))) & 1;
+ _bitIndex++;
+ }
+ }
+ }
+ budget -= 2 * n;
+ _cursor = right - 2;
+ }
+ if (_cursor < 1) {
+ _codewords = []b;
+ _maskIndex = _forceMask >= 0 ? _forceMask : 0;
+ _cursor = 0;
+ _score = 0;
+ _dark = 0;
+ _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.
+ private function maskStep() as Void {
+ if (_forceMask >= 0) {
+ _bestMask = _forceMask;
+ _phase = 5;
+ return;
+ }
+ var n = _size;
+ var lines = (_maskPass == 0 ? ROW_MODULES_PER_STEP : COLUMN_MODULES_PER_STEP) / n;
+ if (lines < 1) {
+ lines = 1;
+ }
+ for (var l = 0; l < lines && _cursor < n; l++) {
+ if (_maskPass == 0) {
+ applyMaskRow(_cursor);
+ scoreRow(_cursor);
+ } else {
+ scoreColumn(_cursor);
+ }
+ _cursor++;
+ }
+ if (_cursor < n) {
+ return;
+ }
+ _cursor = 0;
+ _maskPass++;
+ if (_maskPass < 2) {
+ return;
+ }
+ // N4: 10 points per 5 % away from half dark (integer form of segno's).
+ var total = n * n;
+ var deviation = (_dark * 100 - 50 * total).abs();
+ _score += 10 * (deviation / (5 * total));
+ if (_score < _bestScore) {
+ _bestScore = _score;
+ _bestMask = _maskIndex;
+ }
+ _maskIndex++;
+ _maskPass = 0;
+ _score = 0;
+ _dark = 0;
+ if (_maskIndex >= 8) {
+ _masked = []b;
+ _prevRow = []b;
+ _phase = 5;
+ }
+ }
+
+ 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;
+ }
+ }
+
+ 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 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;
+ }
+ }
+ _dark += dark;
+ _prevRow = row;
+ }
+
+ 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);
+ }
+
+ // 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();
+ var score = 0;
+ var run = 1;
+ var window = line[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;
+ }
+ 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;
+ }
+ }
+ }
+ }
+ 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;
+ }
+ }
+ 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++) {
+ 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;
+ }
+ }
+ }
+ drawFormat(m);
+ if (_version >= 7) {
+ drawVersion();
+ }
+ result = new MatrixCode(n, _m, _version, m);
+ _function = []b;
+ _phase = 6;
+ }
+
+ private function drawFormat(mask as Number) as Void {
+ var data = ((LEVEL_BITS[_ec] as Number) << 3) | mask;
+ var rem = data;
+ for (var i = 0; i < 10; i++) {
+ rem = (rem << 1) ^ ((rem >> 9) * 0x537);
+ }
+ var bits = ((data << 10) | rem) ^ 0x5412;
+ var n = _size;
+ for (var i = 0; i <= 5; i++) {
+ setFunction(8, i, (bits >> i) & 1);
+ }
+ setFunction(8, 7, (bits >> 6) & 1);
+ setFunction(8, 8, (bits >> 7) & 1);
+ setFunction(7, 8, (bits >> 8) & 1);
+ for (var i = 9; i < 15; i++) {
+ setFunction(14 - i, 8, (bits >> i) & 1);
+ }
+ for (var i = 0; i < 8; i++) {
+ setFunction(n - 1 - i, 8, (bits >> i) & 1);
+ }
+ for (var i = 8; i < 15; i++) {
+ setFunction(8, n - 15 + i, (bits >> i) & 1);
+ }
+ setFunction(8, n - 8, 1);
+ }
+
+ private function drawVersion() as Void {
+ var rem = _version;
+ for (var i = 0; i < 12; i++) {
+ rem = (rem << 1) ^ ((rem >> 11) * 0x1F25);
+ }
+ var bits = (_version << 12) | rem;
+ var n = _size;
+ for (var i = 0; i < 18; i++) {
+ var bit = (bits >> i) & 1;
+ var a = n - 11 + i % 3;
+ var b = i / 3;
+ setFunction(a, b, bit);
+ setFunction(b, a, bit);
+ }
+ }
+ }
+
+ // Mask pattern m at column x, row y: true flips a data module.
+ function maskBit(m as Number, x as Number, y as Number) as Boolean {
+ if (m == 0) {
+ return (x + y) % 2 == 0;
+ }
+ if (m == 1) {
+ return y % 2 == 0;
+ }
+ if (m == 2) {
+ return x % 3 == 0;
+ }
+ if (m == 3) {
+ return (x + y) % 3 == 0;
+ }
+ if (m == 4) {
+ return (x / 3 + y / 2) % 2 == 0;
+ }
+ if (m == 5) {
+ return x * y % 2 + x * y % 3 == 0;
+ }
+ if (m == 6) {
+ return (x * y % 2 + x * y % 3) % 2 == 0;
+ }
+ return ((x + y) % 2 + x * y % 3) % 2 == 0;
+ }
+}
diff --git a/source/codes/QrTables.mc b/source/codes/QrTables.mc
new file mode 100644
index 0000000..d88f7b0
--- /dev/null
+++ b/source/codes/QrTables.mc
@@ -0,0 +1,97 @@
+// Author: cirakg & claude ai
+// Summary: QR error-correction block structure per version and level (generated from segno; do not edit).
+//
+// Generated by tools/gen_qr_tables.py. For version v (1-40) and level e (0 L, 1 M, 2 Q, 3 H), the five
+// numbers at index ((v - 1) * 4 + e) * 5 are: EC codewords per block, group-1 blocks, data codewords
+// per group-1 block, group-2 blocks, data codewords per group-2 block (ISO/IEC 18004 table 9).
+
+import Toybox.Lang;
+
+module QrTables {
+ const BLOCKS = [
+ 7, 1, 19, 0, 0, 10, 1, 16, 0, 0, 13, 1, 13, 0, 0, 17, 1, 9, 0, 0, // version 1: L, M, Q, H
+ 10, 1, 34, 0, 0, 16, 1, 28, 0, 0, 22, 1, 22, 0, 0, 28, 1, 16, 0, 0, // version 2: L, M, Q, H
+ 15, 1, 55, 0, 0, 26, 1, 44, 0, 0, 18, 2, 17, 0, 0, 22, 2, 13, 0, 0, // version 3: L, M, Q, H
+ 20, 1, 80, 0, 0, 18, 2, 32, 0, 0, 26, 2, 24, 0, 0, 16, 4, 9, 0, 0, // version 4: L, M, Q, H
+ 26, 1, 108, 0, 0, 24, 2, 43, 0, 0, 18, 2, 15, 2, 16, 22, 2, 11, 2, 12, // version 5: L, M, Q, H
+ 18, 2, 68, 0, 0, 16, 4, 27, 0, 0, 24, 4, 19, 0, 0, 28, 4, 15, 0, 0, // version 6: L, M, Q, H
+ 20, 2, 78, 0, 0, 18, 4, 31, 0, 0, 18, 2, 14, 4, 15, 26, 4, 13, 1, 14, // version 7: L, M, Q, H
+ 24, 2, 97, 0, 0, 22, 2, 38, 2, 39, 22, 4, 18, 2, 19, 26, 4, 14, 2, 15, // version 8: L, M, Q, H
+ 30, 2, 116, 0, 0, 22, 3, 36, 2, 37, 20, 4, 16, 4, 17, 24, 4, 12, 4, 13, // version 9: L, M, Q, H
+ 18, 2, 68, 2, 69, 26, 4, 43, 1, 44, 24, 6, 19, 2, 20, 28, 6, 15, 2, 16, // version 10: L, M, Q, H
+ 20, 4, 81, 0, 0, 30, 1, 50, 4, 51, 28, 4, 22, 4, 23, 24, 3, 12, 8, 13, // version 11: L, M, Q, H
+ 24, 2, 92, 2, 93, 22, 6, 36, 2, 37, 26, 4, 20, 6, 21, 28, 7, 14, 4, 15, // version 12: L, M, Q, H
+ 26, 4, 107, 0, 0, 22, 8, 37, 1, 38, 24, 8, 20, 4, 21, 22, 12, 11, 4, 12, // version 13: L, M, Q, H
+ 30, 3, 115, 1, 116, 24, 4, 40, 5, 41, 20, 11, 16, 5, 17, 24, 11, 12, 5, 13, // version 14: L, M, Q, H
+ 22, 5, 87, 1, 88, 24, 5, 41, 5, 42, 30, 5, 24, 7, 25, 24, 11, 12, 7, 13, // version 15: L, M, Q, H
+ 24, 5, 98, 1, 99, 28, 7, 45, 3, 46, 24, 15, 19, 2, 20, 30, 3, 15, 13, 16, // version 16: L, M, Q, H
+ 28, 1, 107, 5, 108, 28, 10, 46, 1, 47, 28, 1, 22, 15, 23, 28, 2, 14, 17, 15, // version 17: L, M, Q, H
+ 30, 5, 120, 1, 121, 26, 9, 43, 4, 44, 28, 17, 22, 1, 23, 28, 2, 14, 19, 15, // version 18: L, M, Q, H
+ 28, 3, 113, 4, 114, 26, 3, 44, 11, 45, 26, 17, 21, 4, 22, 26, 9, 13, 16, 14, // version 19: L, M, Q, H
+ 28, 3, 107, 5, 108, 26, 3, 41, 13, 42, 30, 15, 24, 5, 25, 28, 15, 15, 10, 16, // version 20: L, M, Q, H
+ 28, 4, 116, 4, 117, 26, 17, 42, 0, 0, 28, 17, 22, 6, 23, 30, 19, 16, 6, 17, // version 21: L, M, Q, H
+ 28, 2, 111, 7, 112, 28, 17, 46, 0, 0, 30, 7, 24, 16, 25, 24, 34, 13, 0, 0, // version 22: L, M, Q, H
+ 30, 4, 121, 5, 122, 28, 4, 47, 14, 48, 30, 11, 24, 14, 25, 30, 16, 15, 14, 16, // version 23: L, M, Q, H
+ 30, 6, 117, 4, 118, 28, 6, 45, 14, 46, 30, 11, 24, 16, 25, 30, 30, 16, 2, 17, // version 24: L, M, Q, H
+ 26, 8, 106, 4, 107, 28, 8, 47, 13, 48, 30, 7, 24, 22, 25, 30, 22, 15, 13, 16, // version 25: L, M, Q, H
+ 28, 10, 114, 2, 115, 28, 19, 46, 4, 47, 28, 28, 22, 6, 23, 30, 33, 16, 4, 17, // version 26: L, M, Q, H
+ 30, 8, 122, 4, 123, 28, 22, 45, 3, 46, 30, 8, 23, 26, 24, 30, 12, 15, 28, 16, // version 27: L, M, Q, H
+ 30, 3, 117, 10, 118, 28, 3, 45, 23, 46, 30, 4, 24, 31, 25, 30, 11, 15, 31, 16, // version 28: L, M, Q, H
+ 30, 7, 116, 7, 117, 28, 21, 45, 7, 46, 30, 1, 23, 37, 24, 30, 19, 15, 26, 16, // version 29: L, M, Q, H
+ 30, 5, 115, 10, 116, 28, 19, 47, 10, 48, 30, 15, 24, 25, 25, 30, 23, 15, 25, 16, // version 30: L, M, Q, H
+ 30, 13, 115, 3, 116, 28, 2, 46, 29, 47, 30, 42, 24, 1, 25, 30, 23, 15, 28, 16, // version 31: L, M, Q, H
+ 30, 17, 115, 0, 0, 28, 10, 46, 23, 47, 30, 10, 24, 35, 25, 30, 19, 15, 35, 16, // version 32: L, M, Q, H
+ 30, 17, 115, 1, 116, 28, 14, 46, 21, 47, 30, 29, 24, 19, 25, 30, 11, 15, 46, 16, // version 33: L, M, Q, H
+ 30, 13, 115, 6, 116, 28, 14, 46, 23, 47, 30, 44, 24, 7, 25, 30, 59, 16, 1, 17, // version 34: L, M, Q, H
+ 30, 12, 121, 7, 122, 28, 12, 47, 26, 48, 30, 39, 24, 14, 25, 30, 22, 15, 41, 16, // version 35: L, M, Q, H
+ 30, 6, 121, 14, 122, 28, 6, 47, 34, 48, 30, 46, 24, 10, 25, 30, 2, 15, 64, 16, // version 36: L, M, Q, H
+ 30, 17, 122, 4, 123, 28, 29, 46, 14, 47, 30, 49, 24, 10, 25, 30, 24, 15, 46, 16, // version 37: L, M, Q, H
+ 30, 4, 122, 18, 123, 28, 13, 46, 32, 47, 30, 48, 24, 14, 25, 30, 42, 15, 32, 16, // version 38: L, M, Q, H
+ 30, 20, 117, 4, 118, 28, 40, 47, 7, 48, 30, 43, 24, 22, 25, 30, 10, 15, 67, 16, // version 39: L, M, Q, H
+ 30, 19, 118, 6, 119, 28, 18, 47, 31, 48, 30, 34, 24, 34, 25, 30, 20, 15, 61, 16 // version 40: L, M, Q, H
+ ];
+
+ // Alignment pattern centres (row and column coordinates) per version, from version 1.
+ const ALIGNMENT = [
+ [],
+ [6, 18],
+ [6, 22],
+ [6, 26],
+ [6, 30],
+ [6, 34],
+ [6, 22, 38],
+ [6, 24, 42],
+ [6, 26, 46],
+ [6, 28, 50],
+ [6, 30, 54],
+ [6, 32, 58],
+ [6, 34, 62],
+ [6, 26, 46, 66],
+ [6, 26, 48, 70],
+ [6, 26, 50, 74],
+ [6, 30, 54, 78],
+ [6, 30, 56, 82],
+ [6, 30, 58, 86],
+ [6, 34, 62, 90],
+ [6, 28, 50, 72, 94],
+ [6, 26, 50, 74, 98],
+ [6, 30, 54, 78, 102],
+ [6, 28, 54, 80, 106],
+ [6, 32, 58, 84, 110],
+ [6, 30, 58, 86, 114],
+ [6, 34, 62, 90, 118],
+ [6, 26, 50, 74, 98, 122],
+ [6, 30, 54, 78, 102, 126],
+ [6, 26, 52, 78, 104, 130],
+ [6, 30, 56, 82, 108, 134],
+ [6, 34, 60, 86, 112, 138],
+ [6, 30, 58, 86, 114, 142],
+ [6, 34, 62, 90, 118, 146],
+ [6, 30, 54, 78, 102, 126, 150],
+ [6, 24, 50, 76, 102, 128, 154],
+ [6, 28, 54, 80, 106, 132, 158],
+ [6, 32, 58, 84, 110, 136, 162],
+ [6, 26, 54, 82, 110, 138, 166],
+ [6, 30, 58, 86, 114, 142, 170]
+ ];
+}
diff --git a/source/codes/ReedSolomon.mc b/source/codes/ReedSolomon.mc
new file mode 100644
index 0000000..a69fb1a
--- /dev/null
+++ b/source/codes/ReedSolomon.mc
@@ -0,0 +1,110 @@
+// Author: cirakg & claude ai
+// Summary: Reed-Solomon error-correction codewords over GF(2^m) for QR (and later Data Matrix and Aztec).
+//
+// A Field is GF(2^m) with a primitive polynomial and the exponent the
+// generator's roots start at (QR: 0x11D, base 0; Data Matrix: 0x12D,
+// base 1). Generator polynomials are cached per field and length. ecc()
+// is the remainder of data * x^n divided by the generator: the standard
+// systematic encoding, one multiply-accumulate per data symbol and EC
+// symbol, so a caller budgets blocks per job step.
+
+import Toybox.Lang;
+
+module ReedSolomon {
+
+ class Field {
+ var size as Number;
+ var exp as Array<Number>;
+ var log as Array<Number>;
+ var base as Number;
+ private var _generators as Dictionary<Number, Array<Number>> = {} as Dictionary<Number, Array<Number>>;
+
+ // primitive: the field polynomial including x^m (0x11D for GF(256)).
+ function initialize(primitive as Number, fieldSize as Number, generatorBase as Number) {
+ size = fieldSize;
+ base = generatorBase;
+ exp = new [2 * fieldSize] as Array<Number>;
+ log = new [fieldSize] as Array<Number>;
+ var x = 1;
+ for (var i = 0; i < fieldSize - 1; i++) {
+ exp[i] = x;
+ log[x] = i;
+ x <<= 1;
+ if (x >= fieldSize) {
+ x ^= primitive;
+ }
+ }
+ // Doubled table: exp[a + b] needs no modulo.
+ for (var i = fieldSize - 1; i < 2 * fieldSize; i++) {
+ exp[i] = exp[i - (fieldSize - 1)];
+ }
+ log[0] = 0;
+ }
+
+ function multiply(a as Number, b as Number) as Number {
+ if (a == 0 || b == 0) {
+ return 0;
+ }
+ return exp[log[a] + log[b]];
+ }
+
+ // Coefficients of the generator with n roots, highest degree first,
+ // without the leading 1.
+ function generator(n as Number) as Array<Number> {
+ var cached = _generators[n];
+ if (cached != null) {
+ return cached;
+ }
+ var g = [1] as Array<Number>;
+ for (var i = 0; i < n; i++) {
+ // Multiply by (x - a^(base + i)); in GF(2^m) minus is plus.
+ var root = exp[(base + i) % (size - 1)];
+ var next = new [g.size() + 1] as Array<Number>;
+ for (var k = 0; k < next.size(); k++) {
+ next[k] = 0;
+ }
+ for (var k = 0; k < g.size(); k++) {
+ next[k] = next[k] ^ g[k];
+ next[k + 1] = next[k + 1] ^ multiply(g[k], root);
+ }
+ g = next;
+ }
+ var coefficients = g.slice(1, null) as Array<Number>;
+ _generators[n] = coefficients;
+ return coefficients;
+ }
+ }
+
+ // The n error-correction symbols of data (both as symbol values).
+ function ecc(field as Field, data as Array<Number>, n as Number) as Array<Number> {
+ var g = field.generator(n);
+ var rem = new [n] as Array<Number>;
+ for (var k = 0; k < n; k++) {
+ rem[k] = 0;
+ }
+ var exp = field.exp;
+ var log = field.log;
+ var logG = new [n] as Array<Number>;
+ for (var k = 0; k < n; k++) {
+ logG[k] = g[k] == 0 ? -1 : log[g[k]];
+ }
+ for (var i = 0; i < data.size(); i++) {
+ var factor = data[i] ^ rem[0];
+ // Shift the remainder left by one symbol.
+ for (var k = 0; k < n - 1; k++) {
+ rem[k] = rem[k + 1];
+ }
+ rem[n - 1] = 0;
+ if (factor != 0) {
+ var lf = log[factor];
+ for (var k = 0; k < n; k++) {
+ var lg = logG[k];
+ if (lg >= 0) {
+ rem[k] = rem[k] ^ exp[lf + lg];
+ }
+ }
+ }
+ }
+ return rem;
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-29 03:49:07 +0000