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;
    // Work per step: each was checked in the simulator by running two
    // steps per event on the Forerunner 255S (120,000 bytecodes per event)
    // with a 1,400-byte payload (32 layers, GF(4096), 830 EC codewords).
    const BYTES_PER_STEP = 200;              // high-level encoding
    const STUFF_BITS_PER_STEP = 1000;        // bit stuffing
    const FIELD_ENTRIES_PER_STEP = 500;      // GF(1024) / GF(4096) tables
    const GENERATOR_WORK_PER_STEP = 500;     // generator coefficient updates
    const ECC_WORK_PER_STEP = 400;           // data symbols x EC symbols
    // Cumulative percent at the end of each phase 0-5 (see AztecJob.percent).
    const PHASE_ENDS = [8, 14, 20, 64, 72, 100];
    const GRID_LINES_PER_STEP = 4;           // reference grid
    const WORDS_PER_STEP = 50;               // codewords into bits
    const PAIRS_PER_STEP = 250;              // spiral bit pairs

    // 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 encoder = new BitEncoder(data);
        while (!encoder.step(data.size() + 1)) {
        }
        return encoder.out.bits;
    }

    // encodeBits() in steps of about `bytes` input bytes. A Binary Shift
    // run's length is written first, then its bytes, across steps.
    class BitEncoder {
        var out as Bits = new Bits();

        private var _data as ByteArray;
        private var _i as Number = 0;
        private var _mode as Number = UPPER;
        private var _runEnd as Number = -1;

        function initialize(data as ByteArray) {
            _data = data;
        }

        // True when every byte is encoded.
        function step(bytes as Number) as Boolean {
            var data = _data;
            var n = data.size();
            var budget = bytes;
            while (budget > 0 && _i < n) {
                if (_runEnd >= 0) {
                    var stop = _i + budget < _runEnd ? _i + budget : _runEnd;
                    budget -= stop - _i;
                    for (var k = _i; k < stop; k++) {
                        out.put(data[k], 8);
                    }
                    _i = stop;
                    if (_i >= _runEnd) {
                        _runEnd = -1;
                    }
                    continue;
                }
                budget--;
                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;
                    budget -= length / 4; // the scan
                    out.put(31, 5);
                    if (length <= 31) {
                        out.put(length, 5);
                    } else {
                        out.put(0, 5);
                        out.put(length - 31, 11);
                    }
                    _runEnd = 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 _i >= n && _runEnd < 0;
        }
    }

    // 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 stuffer = new Stuffer(bits, size);
        stuffer.step(bits.size());
        return stuffer.out;
    }

    // stuff() in steps of `count` input bits.
    class Stuffer {
        var out as Array<Number> = [] as Array<Number>;
        var size as Number;

        private var _bits as ByteArray;
        private var _value as Number = 0;
        private var _count as Number = 0;
        private var _i as Number = 0;

        function initialize(bits as ByteArray, codewordBits as Number) {
            _bits = bits;
            size = codewordBits;
        }

        // True when every bit is in (and the last codeword padded).
        function step(count as Number) as Boolean {
            var bits = _bits;
            var stop = _i + count < bits.size() ? _i + count : bits.size();
            var value = _value;
            var have = _count;
            var i = _i;
            while (i < stop) {
                if (have == 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;
                        have = 0;
                        continue;
                    }
                }
                value = (value << 1) | bits[i];
                have++;
                i++;
                if (have == size) {
                    out.add(value);
                    value = 0;
                    have = 0;
                }
            }
            _value = value;
            _count = have;
            _i = i;
            if (i < bits.size()) {
                return false;
            }
            if (have > 0) {
                for (var k = have; k < size; k++) {
                    value = (value << 1) | 1;
                }
                if (value == (1 << size) - 1) {
                    value = value - 1;
                }
                out.add(value);
                _count = 0;
            }
            return true;
        }
    }

    // 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 _field as ReedSolomon.Field? = null;
        private var _encoder as ReedSolomon.Encoder? = null;
        private var _bitEncoder as BitEncoder? = null;
        private var _stuffer as Stuffer? = null;
        private var _stuffed as Dictionary<Number, Array<Number>> = {} as Dictionary<Number, Array<Number>>;
        private var _configIndex as Number = 0;
        private var _gridAt as Number = 0;
        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;
        }

        // Progress 0-100: the share of each phase (simulator timings; the
        // Reed-Solomon codewords and the spiral take the most).
        function percent() as Number {
            var done = 0;
            var total = 0;
            var e = _encoder;
            if (_phase == 3 && e != null) { // data symbols done
                done = e.percent();
                total = 100;
            } else if (_phase == 5) { // bits placed
                done = _at;
                total = _bits.size();
            }
            return Codes.phased(PHASE_ENDS, _phase, done, total);
        }

        // Packing and runs: about 86 / 3 / 11 % of a whole display job.
        function stageEnds() as Array<Number> {
            return [86, 89];
        }

        function matrix() as Codes.Matrix? {
            return _result;
        }

        function step(budget as Number) as Boolean {
            if (_phase == 0) {
                encodeStep();
            } else if (_phase == 1) {
                chooseStep();
            } else if (_phase == 2) {
                fieldStep();
            } else if (_phase == 3) {
                eccStep();
            } else if (_phase == 4) {
                matrixStep();
            } else if (_phase == 5) {
                placeStep();
            }
            return _phase >= 6 || error != null;
        }

        // Phase 0: the data bits, BYTES_PER_STEP bytes per step.
        private function encodeStep() as Void {
            if (_data.size() == 0) {
                error = "Aztec needs some text";
                return;
            }
            var encoder = _bitEncoder;
            if (encoder == null) {
                encoder = new BitEncoder(_data);
                _bitEncoder = encoder;
            }
            if (!encoder.step(BYTES_PER_STEP)) {
                return;
            }
            _bits = encoder.out.bits;
            _bitEncoder = null;
            _phase = 1;
        }

        // Phase 1: the first configuration that holds the data. A size the
        // bits can't fit even unstuffed is skipped without stuffing; the
        // stuffed codewords are computed once per codeword size, in steps.
        private function chooseStep() as Void {
            while (_configIndex < CONFIGS.size()) {
                var c = CONFIGS[_configIndex] as Array<Number>;
                var lowerBound = (_bits.size() + c[4] - 1) / c[4];
                if ((lowerBound + 3) * 100 >= c[3] * (100 - _ec)) {
                    _configIndex++;
                    continue;
                }
                var words = _stuffed[c[4]];
                if (words == null) {
                    var stuffer = _stuffer;
                    if (stuffer == null || stuffer.size != c[4]) {
                        stuffer = new Stuffer(_bits, c[4]);
                        _stuffer = stuffer;
                    }
                    if (!stuffer.step(STUFF_BITS_PER_STEP)) {
                        return;
                    }
                    words = stuffer.out;
                    _stuffed[c[4]] = words;
                    _stuffer = null;
                }
                if ((words.size() + 3) * 100 < c[3] * (100 - _ec)) {
                    config = c;
                    _words = words;
                    break;
                }
                _configIndex++;
            }
            _stuffed = {} as Dictionary<Number, Array<Number>>;
            if (config.size() == 0) {
                error = "too long for an Aztec code";
                return;
            }
            _dataCount = _words.size();
            _field = new ReedSolomon.Field(polynomial(config[4]), 1 << config[4], 1);
            _phase = 2;
        }

        // Phase 2: GF(1024) and GF(4096) tables and the generator, in steps.
        private function fieldStep() as Void {
            var f = _field as ReedSolomon.Field;
            if (!f.grow(FIELD_ENTRIES_PER_STEP)) {
                return;
            }
            var n = config[3] - _dataCount;
            if (!f.buildGenerator(n, GENERATOR_WORK_PER_STEP)) {
                return;
            }
            _encoder = new ReedSolomon.Encoder(f, _words, n);
            _phase = 3;
        }

        // Phase 3: Reed-Solomon, ECC_WORK_PER_STEP data symbols times EC
        // symbols per step (at least one data symbol).
        private function eccStep() as Void {
            var encoder = _encoder as ReedSolomon.Encoder;
            var n = encoder.remainder.size();
            if (!encoder.step(ECC_WORK_PER_STEP / n > 0 ? ECC_WORK_PER_STEP / n : 1)) {
                return;
            }
            _words.addAll(encoder.remainder);
            _encoder = null;
            _field = null;
            _at = -1;
            _phase = 4;
        }

        private function setDark(x as Number, y as Number, dark as Number) as Void {
            var size = config[0];
            _m[y * size + x] = dark;
        }

        // Phase 4: finder and orientation marks (one step), the reference
        // grid of full-range symbols (GRID_LINES_PER_STEP lines per step),
        // the codeword bits (WORDS_PER_STEP codewords per step); then the
        // spiral state.
        private function matrixStep() as Void {
            var size = config[0];
            var compact = config[1] == 1;
            var c = size / 2;
            var r = compact ? 5 : 7;
            if (_at == -1) {
                drawFinder(size, compact, c, r);
                _gridAt = 0;
                _at = compact ? -3 : -2;
                return;
            }
            if (_at == -2) {
                // Lines at multiples of 16 from the centre, across and down.
                var half = c / 16;
                var lines = 2 * half + 1;
                for (var n = 0; n < GRID_LINES_PER_STEP && _gridAt < 2 * lines; n++) {
                    var v = (_gridAt % lines - half) * 16;
                    var across = _gridAt < lines;
                    for (var t = -c; t <= c; t++) {
                        var x = across ? t : v;
                        var y = across ? v : t;
                        if (x >= -r && x <= r && y >= -r && y <= r) {
                            continue;
                        }
                        setDark(c + x, c + y, ((x + y + 1) % 2 + 2) % 2);
                    }
                    _gridAt++;
                }
                if (_gridAt >= 2 * lines) {
                    _at = -3;
                }
                return;
            }
            // All codeword bits, most significant first, then reversed: the
            // spiral starts from the last bit (as the reference does).
            var bits = config[4];
            if (_bits.size() != _words.size() * bits) {
                _bits = new [_words.size() * bits]b;
                _gridAt = 0;
            }
            var all = _bits;
            var stop = _gridAt + WORDS_PER_STEP < _words.size() ? _gridAt + WORDS_PER_STEP : _words.size();
            for (var i = _gridAt; i < stop; i++) {
                var at = all.size() - 1 - i * bits;
                for (var k = bits - 1; k >= 0; k--) {
                    all[at] = (_words[i] >> k) & 1;
                    at--;
                }
            }
            _gridAt = stop;
            if (_gridAt < _words.size()) {
                return;
            }
            _at = 0;
            _num = 2;
            _side = 0;
            _layer = 0;
            _x = c - r;
            _y = c - r - 1;
            _phase = 5;
        }

        private function drawFinder(size as Number, compact as Boolean, c as Number, r as Number) as Void {
            _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);
        }

        // 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 = 6;
        }

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