feat(codes): add an Aztec encoder (compact and full range) as a resumable job

Upper/Lower/Digit modes with Binary Shift, bit stuffing, Reed-Solomon over
GF(2^6..2^12) in steps, geometry ported from aztec_code_generator; symbols
match it for single-class text.

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>

1 files changed, 522 insertions, 0 deletions

diff --git a/source/codes/Aztec.mc b/source/codes/Aztec.mc
new file mode 100644
index 0000000..29b6c95
--- /dev/null
+++ b/source/codes/Aztec.mc
@@ -0,0 +1,522 @@
+// Author:  cirakg & claude ai
+// Summary: Aztec Code encoder (ISO/IEC 24778): compact 1-4 and full-range 1-32 layers, error correction by percentage, as a job.
+//
+// Steps:
+//   1. High-level encoding to bits: runs of capitals (and spaces) in Upper
+//      mode, small letters in Lower, digits (with space , .) in Digit, and
+//      every other byte (punctuation, UTF-8) in Binary Shift runs, with the
+//      standard latch and shift codes. Simpler than an optimal mode search,
+//      always valid; verified by decoding with zxing-cpp.
+//   2. The smallest symbol (in the order of aztec_code_generator's table)
+//      whose codewords hold the data plus 3 codewords and the chosen error
+//      correction percentage (10, 23, 36 or 50 %); bit stuffing per
+//      codeword size (no all-zero or all-one codewords).
+//   3. Reed-Solomon over GF(2^6), GF(2^8), GF(2^10) or GF(2^12), in steps.
+//   4. The matrix: bull's-eye finder, orientation marks, reference grid
+//      (full range), the data spiral (two modules per step, outward) and the
+//      mode message with its own GF(16) error correction. This geometry is a
+//      port of aztec_code_generator (MIT), the test reference.
+
+import Toybox.Lang;
+
+module Aztec {
+
+    // [size, compact (1/0), layers, codewords, codeword bits], in the order
+    // the reference tries them.
+    const CONFIGS = [
+        [15, 1, 1, 17, 6], [19, 0, 1, 21, 6], [19, 1, 2, 40, 6], [23, 0, 2, 48, 6], [23, 1, 3, 51, 8],
+        [27, 0, 3, 60, 8], [27, 1, 4, 76, 8], [31, 0, 4, 88, 8], [37, 0, 5, 120, 8], [41, 0, 6, 156, 8],
+        [45, 0, 7, 196, 8], [49, 0, 8, 240, 8], [53, 0, 9, 230, 10], [57, 0, 10, 272, 10], [61, 0, 11, 316, 10],
+        [67, 0, 12, 364, 10], [71, 0, 13, 416, 10], [75, 0, 14, 470, 10], [79, 0, 15, 528, 10], [83, 0, 16, 588, 10],
+        [87, 0, 17, 652, 10], [91, 0, 18, 720, 10], [95, 0, 19, 790, 10], [101, 0, 20, 864, 10], [105, 0, 21, 940, 10],
+        [109, 0, 22, 1020, 10], [113, 0, 23, 920, 12], [117, 0, 24, 992, 12], [121, 0, 25, 1066, 12], [125, 0, 26, 1144, 12],
+        [131, 0, 27, 1224, 12], [135, 0, 28, 1306, 12], [139, 0, 29, 1392, 12], [143, 0, 30, 1480, 12], [147, 0, 31, 1570, 12],
+        [151, 0, 32, 1664, 12]
+    ];
+    // Error-correction percentage per option: Low, Medium (default), Quartile, High.
+    const EC_PERCENT = [10, 23, 36, 50];
+    const QUIET = 2;
+    const RS_SYMBOLS_PER_STEP = 40;
+    const PAIRS_PER_STEP = 600;
+
+    // Text modes.
+    const UPPER = 0;
+    const LOWER = 1;
+    const DIGIT = 2;
+    const BINARY = 3;
+
+    // Field polynomial per codeword size.
+    function polynomial(bits as Number) as Number {
+        if (bits == 4) {
+            return 19;
+        }
+        if (bits == 6) {
+            return 67;
+        }
+        if (bits == 8) {
+            return 301;
+        }
+        return bits == 10 ? 1033 : 4201;
+    }
+
+    function classOf(b as Number) as Number {
+        if ((b >= 0x41 && b <= 0x5A)) {
+            return UPPER;
+        }
+        if (b >= 0x61 && b <= 0x7A) {
+            return LOWER;
+        }
+        if (b >= 0x30 && b <= 0x39) {
+            return DIGIT;
+        }
+        return b == 0x20 ? -1 : BINARY; // -1: space fits Upper, Lower and Digit
+    }
+
+    // A growing bit string.
+    class Bits {
+        var bits as ByteArray = []b;
+
+        function initialize() {
+        }
+
+        function put(value as Number, count as Number) as Void {
+            for (var i = count - 1; i >= 0; i--) {
+                bits.add((value >> i) & 1);
+            }
+        }
+    }
+
+    // The data bits of text (see step 1).
+    function encodeBits(data as ByteArray) as ByteArray {
+        var out = new Bits();
+        var mode = UPPER;
+        var i = 0;
+        var n = data.size();
+        while (i < n) {
+            var c = classOf(data[i]);
+            if (c == -1) {
+                // A space: in the current text mode if it has one.
+                out.put(1, mode == DIGIT ? 4 : 5);
+                i++;
+                continue;
+            }
+            if (c == BINARY) {
+                // Binary Shift needs Upper or Lower; from Digit latch to Upper.
+                if (mode == DIGIT) {
+                    out.put(14, 4);
+                    mode = UPPER;
+                }
+                var end = i;
+                while (end < n && end - i < 2078 && classOf(data[end]) == BINARY) {
+                    end++;
+                }
+                var length = end - i;
+                out.put(31, 5);
+                if (length <= 31) {
+                    out.put(length, 5);
+                } else {
+                    out.put(0, 5);
+                    out.put(length - 31, 11);
+                }
+                for (var k = i; k < end; k++) {
+                    out.put(data[k], 8);
+                }
+                i = end;
+                continue;
+            }
+            if (c != mode) {
+                latch(out, mode, c);
+                mode = c;
+            }
+            var b = data[i];
+            if (mode == UPPER) {
+                out.put(b - 0x41 + 2, 5);
+            } else if (mode == LOWER) {
+                out.put(b - 0x61 + 2, 5);
+            } else {
+                out.put(b - 0x30 + 2, 4);
+            }
+            i++;
+        }
+        return out.bits;
+    }
+
+    // Latch codes between the text modes (ISO 24778 table 2).
+    function latch(out as Bits, from as Number, to as Number) as Void {
+        if (from == UPPER) {
+            out.put(to == LOWER ? 28 : 30, 5);         // L/L or D/L
+        } else if (from == LOWER) {
+            if (to == DIGIT) {
+                out.put(30, 5);                         // D/L
+            } else {
+                out.put(30, 5);                         // D/L, then U/L
+                out.put(14, 4);
+            }
+        } else {
+            out.put(14, 4);                             // U/L
+            if (to == LOWER) {
+                out.put(28, 5);                         // then L/L
+            }
+        }
+    }
+
+    // Codewords of `size` bits with bit stuffing: a codeword whose first
+    // size - 1 bits are all equal gets the opposite last bit; the final
+    // partial codeword is padded with ones (its last bit 0 if all ones).
+    function stuff(bits as ByteArray, size as Number) as Array<Number> {
+        var out = [] as Array<Number>;
+        var value = 0;
+        var count = 0;
+        var i = 0;
+        while (i < bits.size()) {
+            if (count == size - 1) {
+                var allZero = value == 0;
+                var allOne = value == (1 << (size - 1)) - 1;
+                if (allZero || allOne) {
+                    value = (value << 1) | (allZero ? 1 : 0);
+                    out.add(value);
+                    value = 0;
+                    count = 0;
+                    continue;
+                }
+            }
+            value = (value << 1) | bits[i];
+            count++;
+            i++;
+            if (count == size) {
+                out.add(value);
+                value = 0;
+                count = 0;
+            }
+        }
+        if (count > 0) {
+            for (var k = count; k < size; k++) {
+                value = (value << 1) | 1;
+            }
+            if (value == (1 << size) - 1) {
+                value = value - 1;
+            }
+            out.add(value);
+        }
+        return out;
+    }
+
+    // Encode synchronously (tests).
+    function encode(text as String, option as Number) as Codes.Matrix or Codes.CodeError {
+        var job = new AztecJob(text, option);
+        Jobs.runToCompletion(job, 1);
+        var err = job.error;
+        return err != null ? new Codes.CodeError(err) : job.matrix() as Codes.Matrix;
+    }
+
+    class AztecJob extends Codes.MatrixJob {
+
+        var config as Array<Number> = [] as Array<Number>;
+        private var _data as ByteArray;
+        private var _ec as Number;
+        private var _phase as Number = 0;
+        private var _words as Array<Number> = [] as Array<Number>;
+        private var _dataCount as Number = 0;
+        private var _rem as Array<Number> = [] as Array<Number>;
+        private var _field as ReedSolomon.Field? = null;
+        private var _at as Number = 0;
+        private var _m as ByteArray = []b;
+        private var _result as Codes.Matrix? = null;
+        // Spiral state.
+        private var _bits as ByteArray = []b;
+        private var _num as Number = 2;
+        private var _side as Number = 0;
+        private var _layer as Number = 0;
+        private var _x as Number = 0;
+        private var _y as Number = 0;
+
+        function initialize(text as String, option as Number) {
+            MatrixJob.initialize();
+            _data = Bytes.fromUtf8(text);
+            _ec = EC_PERCENT[option] as Number;
+        }
+
+        function percent() as Number {
+            return _phase * 25;
+        }
+
+        function matrix() as Codes.Matrix? {
+            return _result;
+        }
+
+        function step(budget as Number) as Boolean {
+            if (_phase == 0) {
+                prepare();
+            } else if (_phase == 1) {
+                eccStep();
+            } else if (_phase == 2) {
+                placeStep();
+            }
+            return _phase >= 3 || error != null;
+        }
+
+        private function prepare() as Void {
+            if (_data.size() == 0) {
+                error = "Aztec needs some text";
+                return;
+            }
+            var bits = encodeBits(_data);
+            for (var i = 0; i < CONFIGS.size() && config.size() == 0; i++) {
+                var c = CONFIGS[i] as Array<Number>;
+                var words = stuff(bits, c[4]);
+                if ((words.size() + 3) * 100 < c[3] * (100 - _ec)) {
+                    config = c;
+                    _words = words;
+                }
+            }
+            if (config.size() == 0) {
+                error = "too long for an Aztec code";
+                return;
+            }
+            _dataCount = _words.size();
+            var ecCount = config[3] - _dataCount;
+            _field = new ReedSolomon.Field(polynomial(config[4]), 1 << config[4], 1);
+            _rem = new [ecCount] as Array<Number>;
+            for (var k = 0; k < ecCount; k++) {
+                _rem[k] = 0;
+            }
+            _at = 0;
+            _phase = 1;
+        }
+
+        private function eccStep() as Void {
+            var f = _field as ReedSolomon.Field;
+            var n = _rem.size();
+            var g = f.generator(n);
+            var end = _at + RS_SYMBOLS_PER_STEP < _dataCount ? _at + RS_SYMBOLS_PER_STEP : _dataCount;
+            for (var i = _at; i < end; i++) {
+                var factor = _words[i] ^ _rem[0];
+                for (var k = 0; k < n - 1; k++) {
+                    _rem[k] = _rem[k + 1] ^ f.multiply(g[k], factor);
+                }
+                _rem[n - 1] = f.multiply(g[n - 1], factor);
+            }
+            _at = end;
+            if (_at < _dataCount) {
+                return;
+            }
+            _words.addAll(_rem);
+            _rem = [] as Array<Number>;
+            _field = null;
+            startMatrix();
+            _phase = 2;
+        }
+
+        private function setDark(x as Number, y as Number, dark as Number) as Void {
+            var size = config[0];
+            _m[y * size + x] = dark;
+        }
+
+        // Finder, orientation marks and reference grid; then the spiral state.
+        private function startMatrix() as Void {
+            var size = config[0];
+            var compact = config[1] == 1;
+            var c = size / 2;
+            var r = compact ? 5 : 7;
+            _m = new [size * size]b;
+            for (var x = -r; x < r; x++) {
+                for (var y = -r; y < r; y++) {
+                    var d = x.abs() > y.abs() ? x.abs() : y.abs();
+                    setDark(c + x, c + y, (d + 1) % 2);
+                }
+            }
+            setDark(c - r, c - r, 1);
+            setDark(c - r, c - r + 1, 1);
+            setDark(c - r + 1, c - r, 1);
+            setDark(c + r, c - r, 1);
+            setDark(c + r, c - r + 1, 1);
+            setDark(c + r, c + r - 1, 1);
+            if (!compact) {
+                for (var x = -c; x <= c; x++) {
+                    for (var y = -c; y <= c; y++) {
+                        if (x >= -r && x <= r && y >= -r && y <= r) {
+                            continue;
+                        }
+                        if (x % 16 == 0 || y % 16 == 0) {
+                            setDark(c + x, c + y, ((x + y + 1) % 2 + 2) % 2);
+                        }
+                    }
+                }
+            }
+            // All codeword bits, most significant first, then reversed: the
+            // spiral starts from the last bit (as the reference does).
+            var bits = config[4];
+            var all = new [_words.size() * bits]b;
+            var at = all.size() - 1;
+            for (var i = 0; i < _words.size(); i++) {
+                for (var k = bits - 1; k >= 0; k--) {
+                    all[at] = (_words[i] >> k) & 1;
+                    at--;
+                }
+            }
+            _bits = all;
+            _at = 0;
+            _num = 2;
+            _side = 0;
+            _layer = 0;
+            _x = c - r;
+            _y = c - r - 1;
+        }
+
+        // The data spiral, PAIRS_PER_STEP bit pairs per step (a port of
+        // aztec_code_generator's __add_data).
+        private function placeStep() as Void {
+            var size = config[0];
+            var compact = config[1] == 1;
+            var c = size / 2;
+            var r = compact ? 5 : 7;
+            var end = _at + 2 * PAIRS_PER_STEP < _bits.size() ? _at + 2 * PAIRS_PER_STEP : _bits.size();
+            while (_at < end) {
+                var b0 = _bits[_at];
+                var b1 = _bits[_at + 1];
+                _at += 2;
+                _num++;
+                var maxNum = 2 * r + _layer * 4 + (compact ? 4 : 3);
+                if (_side == 0) { // top: move right
+                    var dy0 = !compact && grid(c - _y) ? 1 : 0;
+                    var dy1 = !compact && grid(c - _y + 1) ? 2 : 1;
+                    setDark(_x, _y - dy0, b0);
+                    setDark(_x, _y - dy1, b1);
+                    _x++;
+                    if (_num > maxNum) {
+                        _num = 2;
+                        _side = 1;
+                        _x--;
+                        _y++;
+                    }
+                    if (!compact && grid(c - _x)) {
+                        _x++;
+                    }
+                    if (!compact && grid(c - _y)) {
+                        _y++;
+                    }
+                } else if (_side == 1) { // right: move down
+                    var dx0 = !compact && grid(c - _x) ? 1 : 0;
+                    var dx1 = !compact && grid(c - _x + 1) ? 2 : 1;
+                    setDark(_x - dx0, _y, b1);
+                    setDark(_x - dx1, _y, b0);
+                    _y++;
+                    if (_num > maxNum) {
+                        _num = 2;
+                        _side = 2;
+                        _x -= 2;
+                        if (!compact && grid(c - _x - 1)) {
+                            _x--;
+                        }
+                        _y--;
+                    }
+                    if (!compact && grid(c - _y)) {
+                        _y++;
+                    }
+                    if (!compact && grid(c - _x)) {
+                        _x--;
+                    }
+                } else if (_side == 2) { // bottom: move left
+                    var dy0 = !compact && grid(c - _y) ? 1 : 0;
+                    var dy1 = !compact && grid(c - _y + 1) ? 2 : 1;
+                    setDark(_x, _y - dy0, b1);
+                    setDark(_x, _y - dy1, b0);
+                    _x--;
+                    if (_num > maxNum) {
+                        _num = 2;
+                        _side = 3;
+                        _x++;
+                        _y -= 2;
+                        if (!compact && grid(c - _y - 1)) {
+                            _y--;
+                        }
+                    }
+                    if (!compact && grid(c - _x)) {
+                        _x--;
+                    }
+                    if (!compact && grid(c - _y)) {
+                        _y--;
+                    }
+                } else { // left: move up
+                    var dx0 = !compact && grid(c - _x) ? 1 : 0;
+                    var dx1 = !compact && grid(c - _x - 1) ? 2 : 1;
+                    setDark(_x + dx1, _y, b0);
+                    setDark(_x + dx0, _y, b1);
+                    _y--;
+                    if (_num > maxNum) {
+                        _num = 2;
+                        _side = 0;
+                        _layer++;
+                    }
+                    if (!compact && grid(c - _y)) {
+                        _y--;
+                    }
+                }
+            }
+            if (_at < _bits.size()) {
+                return;
+            }
+            _bits = []b;
+            addModeMessage();
+            _words = [] as Array<Number>;
+            _result = new Codes.Matrix(size, size, QUIET, _m);
+            _phase = 3;
+        }
+
+        // True on a reference-grid line (Python's % 16 == 0 for any sign).
+        private function grid(v as Number) as Boolean {
+            return v % 16 == 0;
+        }
+
+        // The mode message (layers and data codewords) with GF(16) error
+        // correction, around the finder.
+        private function addModeMessage() as Void {
+            var compact = config[1] == 1;
+            var layers = config[2];
+            var nibbles = [] as Array<Number>;
+            var total = 0;
+            if (compact) {
+                var word = ((layers - 1) << 6) | (_dataCount - 1);
+                nibbles = [(word >> 4) & 0xF, word & 0xF];
+                total = 7;
+            } else {
+                var word = ((layers - 1) << 11) | (_dataCount - 1);
+                nibbles = [(word >> 12) & 0xF, (word >> 8) & 0xF, (word >> 4) & 0xF, word & 0xF];
+                total = 10;
+            }
+            var f = new ReedSolomon.Field(19, 16, 1);
+            var check = ReedSolomon.ecc(f, nibbles, total - nibbles.size());
+            for (var k = 0; k < check.size(); k++) {
+                nibbles.add(check[k]);
+            }
+            var size = config[0];
+            var c = size / 2;
+            var r = compact ? 5 : 7;
+            var side = compact ? 7 : 11;
+            var index = 0;
+            for (var i = 0; i < nibbles.size() * 4; i++) {
+                var bit = (nibbles[i / 4] >> (3 - i % 4)) & 1;
+                if (!compact && index % side == 5) {
+                    index++;
+                }
+                var x = 0;
+                var y = 0;
+                if (index < side) {
+                    x = index + 2 - r;
+                    y = -r;
+                } else if (index < side * 2) {
+                    x = r;
+                    y = index % side + 2 - r;
+                } else if (index < side * 3) {
+                    x = r - index % side - 2;
+                    y = r;
+                } else {
+                    x = -r;
+                    y = r - index % side - 2;
+                }
+                setDark(c + x, c + y, bit);
+                index++;
+            }
+        }
+    }
+}