path: root/source/codes/Aztec.mc

// 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++;
            }
        }
    }
}