path: root/source/codes/DataMatrix.mc

// Author:  cirakg & claude ai
// Summary: Data Matrix ECC 200 encoder (ISO/IEC 16022): square sizes 10x10 to 144x144, ASCII and Base256, as a resumable job.
//
// Steps:
//   1. Encode the UTF-8 bytes: ASCII (digit pairs as one codeword) when
//      every byte is below 128, otherwise the cheaper of ASCII with Upper
//      Shift per byte and one Base256 field (randomised, ISO 16022 annex B).
//      C40, Text, X12 and EDIFACT are deferred (README 12.1).
//   2. Pick the smallest square size, pad (129, then randomised pads).
//   3. Reed-Solomon over GF(256) (x^8+x^5+x^3+x^2+1, roots a^1..a^n),
//      per interleaved block, in chunks.
//   4. Place the codewords with the standard "utah" placement, one
//      diagonal pass per step, then add the finder and clock patterns of
//      every data region.
// Verified against ppf.datamatrix (ASCII mode) and by decoding with zxing-cpp.

import Toybox.Lang;

module DataMatrix {

    // Square sizes: [symbol size, data region size, regions per side,
    // data codewords, EC codewords, interleaved blocks] (ISO 16022 table 7).
    const SIZES = [
        [10, 8, 1, 3, 5, 1], [12, 10, 1, 5, 7, 1], [14, 12, 1, 8, 10, 1], [16, 14, 1, 12, 12, 1],
        [18, 16, 1, 18, 14, 1], [20, 18, 1, 22, 18, 1], [22, 20, 1, 30, 20, 1], [24, 22, 1, 36, 24, 1],
        [26, 24, 1, 44, 28, 1], [32, 14, 2, 62, 36, 1], [36, 16, 2, 86, 42, 1], [40, 18, 2, 114, 48, 1],
        [44, 20, 2, 144, 56, 1], [48, 22, 2, 174, 68, 1], [52, 24, 2, 204, 84, 2], [64, 14, 4, 280, 112, 2],
        [72, 16, 4, 368, 144, 4], [80, 18, 4, 456, 192, 4], [88, 20, 4, 576, 224, 4], [96, 22, 4, 696, 272, 4],
        [104, 24, 4, 816, 336, 6], [120, 18, 6, 1050, 408, 6], [132, 20, 6, 1304, 496, 8], [144, 22, 6, 1558, 620, 10]
    ];
    const QUIET = 1;
    const PAD = 129;
    const UPPER_SHIFT = 235;
    const BASE256_LATCH = 231;
    // The placement grid's mark for the fixed dark corner modules.
    const FIXED_DARK = 0xFFFF;
    // 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,500-byte payload (144 x 144 modules).
    const BYTES_PER_STEP = 250;          // codeword encodation
    const ECC_WORK_PER_STEP = 400;       // data symbols x EC symbols
    // Cumulative percent at the end of each phase 0-4 (see DataMatrixJob.percent).
    const PHASE_ENDS = [2, 44, 45, 69, 100];
    const BUILD_MODULES_PER_STEP = 300;  // symbol modules

    var field as ReedSolomon.Field? = null;

    function theField() as ReedSolomon.Field {
        var f = field;
        if (f == null) {
            f = new ReedSolomon.Field(0x12D, 256, 1);
            field = f;
        }
        return f;
    }

    // Codewords for data: ASCII, or Base256 when cheaper (non-ASCII text).
    function codewords(data as ByteArray) as Array<Number> {
        var builder = new CodewordBuilder(data);
        while (!builder.step(data.size() + 1)) {
        }
        return builder.result;
    }

    // codewords() in bounded steps: the ASCII encodation, then (when
    // Base256 is cheaper) the Base256 one, `bytes` input bytes per step.
    class CodewordBuilder {
        var result as Array<Number> = [] as Array<Number>;

        private var _data as ByteArray;
        private var _ascii as Array<Number> = [] as Array<Number>;
        private var _highBytes as Number = 0;
        private var _i as Number = 0;
        private var _base256 as Array<Number>? = null;
        private var _k as Number = 0;

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

        // True when result is ready.
        function step(bytes as Number) as Boolean {
            var data = _data;
            var n = data.size();
            if (_i < n) {
                var stop = _i + bytes < n ? _i + bytes : n;
                var i = _i;
                var ascii = _ascii;
                while (i < stop) {
                    var b = data[i];
                    if (b >= 0x30 && b <= 0x39 && i + 1 < n && data[i + 1] >= 0x30 && data[i + 1] <= 0x39) {
                        ascii.add(130 + (b - 0x30) * 10 + data[i + 1] - 0x30);
                        i += 2;
                        continue;
                    }
                    if (b >= 128) {
                        ascii.add(UPPER_SHIFT);
                        ascii.add(b - 128 + 1);
                        _highBytes++;
                    } else {
                        ascii.add(b + 1);
                    }
                    i++;
                }
                _i = i;
                return false;
            }
            var out = _base256;
            if (out == null) {
                var base256Cost = 1 + (n <= 249 ? 1 : 2) + n;
                if (_highBytes == 0 || _ascii.size() <= base256Cost) {
                    result = _ascii;
                    return true;
                }
                out = [BASE256_LATCH] as Array<Number>;
                if (n <= 249) {
                    out.add(randomise255(n, 2));
                } else {
                    out.add(randomise255(n / 250 + 249, 2));
                    out.add(randomise255(n % 250, 3));
                }
                _base256 = out;
                _ascii = [] as Array<Number>;
            }
            var stop = _k + bytes < n ? _k + bytes : n;
            for (var k = _k; k < stop; k++) {
                out.add(randomise255(data[k], out.size() + 1));
            }
            _k = stop;
            if (_k < n) {
                return false;
            }
            result = out;
            return true;
        }
    }

    // The 255-state randomising of Base256 values at 1-based position pos.
    function randomise255(value as Number, pos as Number) as Number {
        var v = value + ((149 * pos) % 255) + 1;
        return v <= 255 ? v : v - 256;
    }

    // The 253-state randomised pad at 1-based position pos.
    function pad253(pos as Number) as Number {
        var v = PAD + ((149 * pos) % 253) + 1;
        return v <= 254 ? v : v - 254;
    }

    // Encode synchronously (tests); the app uses DataMatrixJob.
    function encode(text as String) as Codes.Matrix or Codes.CodeError {
        var job = new DataMatrixJob(text);
        Jobs.runToCompletion(job, 1);
        var err = job.error;
        return err != null ? new Codes.CodeError(err) : job.matrix() as Codes.Matrix;
    }

    class DataMatrixJob extends Codes.MatrixJob {

        private var _data as ByteArray;
        private var _phase as Number = 0;
        private var _size as Array<Number> = [] as Array<Number>;
        private var _cw as Array<Number> = [] as Array<Number>;
        private var _blocks as Array<Array<Number>> = [] as Array<Array<Number>>;
        private var _builder as CodewordBuilder? = null;
        private var _encoder as ReedSolomon.Encoder? = null;
        private var _block as Number = 0;
        private var _buildRow as Number = 0;
        private var _modules as ByteArray = []b;
        private var _ecTotal as Array<Number> = [] as Array<Number>;
        // Placement state.
        private var _nrow as Number = 0;
        private var _ncol as Number = 0;
        // Placement grid, two bytes per module (big-endian): 10 * codeword +
        // bit, 0 = empty, FIXED_DARK. Bytes, not Numbers: a 132 x 132 grid of
        // Numbers took about 90 KB of the Forerunner 255S's 512 KB.
        private var _place as ByteArray = []b;
        private var _chr as Number = 1;
        private var _downPass as Boolean = false;
        private var _row as Number = 4;
        private var _col as Number = 0;
        private var _result as Codes.Matrix? = null;

        function initialize(text as String) {
            MatrixJob.initialize();
            _data = Bytes.fromUtf8(text);
        }

        // Progress 0-100: the share of each phase (simulator timings; the
        // Reed-Solomon blocks, the placement and the symbol take the most).
        function percent() as Number {
            var done = 0;
            var total = 0;
            if (_phase == 1 && _size.size() > 0) { // blocks done, and the current one
                var e = _encoder;
                done = _block * 100 + (e != null ? e.percent() : 0);
                total = _size[5] * 100;
            } else if (_phase == 3 && _size.size() > 0) { // codewords placed
                done = _chr - 1;
                total = _size[3] + _size[4];
            } else if (_phase == 4 && _size.size() > 0) { // rows built
                done = _buildRow;
                total = _size[0];
            }
            return Codes.phased(PHASE_ENDS, _phase, done, total);
        }

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

        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) {
                startPlacement();
            } else if (_phase == 3) {
                placeStep();
            } else if (_phase == 4) {
                build();
            }
            return _phase >= 5 || error != null;
        }

        // Codewords (BYTES_PER_STEP per step), then size, padding, blocks.
        private function prepare() as Void {
            if (_data.size() == 0) {
                error = "Data Matrix needs some text";
                return;
            }
            var builder = _builder;
            if (builder == null) {
                builder = new CodewordBuilder(_data);
                _builder = builder;
            }
            if (!builder.step(BYTES_PER_STEP)) {
                return;
            }
            _builder = null;
            var cw = builder.result;
            for (var i = 0; i < SIZES.size() && _size.size() == 0; i++) {
                var s = SIZES[i] as Array<Number>;
                if (cw.size() <= s[3]) {
                    _size = s;
                }
            }
            if (_size.size() == 0) {
                error = "too long for Data Matrix (" + cw.size() + " codewords, at most 1558)";
                return;
            }
            var capacity = _size[3];
            if (cw.size() < capacity) {
                cw.add(PAD);
                while (cw.size() < capacity) {
                    cw.add(pad253(cw.size() + 1));
                }
            }
            _cw = cw;
            var blocks = _size[5];
            for (var b = 0; b < blocks; b++) {
                var block = [] as Array<Number>;
                for (var k = b; k < capacity; k += blocks) {
                    block.add(cw[k]);
                }
                _blocks.add(block);
            }
            _ecTotal = new [_size[4]] as Array<Number>;
            _phase = 1;
        }

        // Reed-Solomon (the shared encoder: the same remainder as ISO 16022
        // annex E), ECC_WORK_PER_STEP data symbols times EC symbols per step.
        private function eccStep() as Void {
            var blocks = _size[5];
            var n = _size[4] / blocks;
            var encoder = _encoder;
            if (encoder == null) {
                var fresh = !theField().hasGenerator(n);
                encoder = new ReedSolomon.Encoder(theField(), _blocks[_block], n);
                _encoder = encoder;
                if (fresh) {
                    return; // the generator took this step
                }
            }
            if (!encoder.step(ECC_WORK_PER_STEP / n > 0 ? ECC_WORK_PER_STEP / n : 1)) {
                return;
            }
            _encoder = null;
            // Interleave this block's EC codewords.
            for (var k = 0; k < n; k++) {
                _ecTotal[_block + k * blocks] = encoder.remainder[k];
            }
            _block++;
            if (_block < blocks) {
                return;
            }
            _cw.addAll(_ecTotal);
            _blocks = [] as Array<Array<Number>>;
            _phase = 2;
        }

        // The empty placement grid (a new ByteArray is zeroed natively).
        private function startPlacement() as Void {
            _nrow = _size[1] * _size[2];
            _ncol = _nrow;
            _place = new [2 * _nrow * _ncol]b;
            _phase = 3;
        }

        private function placeAt(i as Number) as Number {
            return (_place[2 * i] << 8) | _place[2 * i + 1];
        }

        private function setPlace(i as Number, v as Number) as Void {
            _place[2 * i] = (v >> 8) & 0xFF;
            _place[2 * i + 1] = v & 0xFF;
        }

        // ISO 16022 annex F placement, one diagonal pass per step: each
        // sweep is a pass up and to the right (after the corner cases), then
        // one down and to the left (_downPass).
        private function placeStep() as Void {
            var nrow = _nrow;
            var ncol = _ncol;
            if (!_downPass) {
                if (_row >= nrow && _col >= ncol) {
                    finishPlacement();
                    return;
                }
                if (_row == nrow && _col == 0) {
                    corner1();
                }
                if (_row == nrow - 2 && _col == 0 && ncol % 4 != 0) {
                    corner2();
                }
                if (_row == nrow - 2 && _col == 0 && ncol % 8 == 4) {
                    corner3();
                }
                if (_row == nrow + 4 && _col == 2 && ncol % 8 == 0) {
                    corner4();
                }
                do {
                    var at = 2 * (_row * ncol + _col);
                    if (_row < nrow && _col >= 0 && _place[at] == 0 && _place[at + 1] == 0) {
                        utah(_row, _col);
                    }
                    _row -= 2;
                    _col += 2;
                } while (_row >= 0 && _col < ncol);
                _row += 1;
                _col += 3;
                _downPass = true;
                return;
            }
            do {
                var at = 2 * (_row * ncol + _col);
                if (_row >= 0 && _col < ncol && _place[at] == 0 && _place[at + 1] == 0) {
                    utah(_row, _col);
                }
                _row += 2;
                _col -= 2;
            } while (_row < nrow && _col >= 0);
            _row += 3;
            _col += 1;
            _downPass = false;
            if (_row >= nrow && _col >= ncol) {
                finishPlacement();
            }
        }

        // The fixed corner modules when the grid leaves them empty.
        private function finishPlacement() as Void {
            var n = _nrow * _ncol;
            if (placeAt(n - 1) == 0) {
                setPlace(n - 1, FIXED_DARK);
                setPlace(n - _ncol - 2, FIXED_DARK);
            }
            _phase = 4;
        }

        private function setModule(row as Number, col as Number, bit as Number) as Void {
            var r = row;
            var c = col;
            if (r < 0) {
                r += _nrow;
                c += 4 - ((_nrow + 4) % 8);
            }
            if (c < 0) {
                c += _ncol;
                r += 4 - ((_ncol + 4) % 8);
            }
            var v = 10 * _chr + bit;
            var at = 2 * (r * _ncol + c);
            _place[at] = v >> 8;
            _place[at + 1] = v & 0xFF;
        }

        private function utah(row as Number, col as Number) as Void {
            setModule(row - 2, col - 2, 1);
            setModule(row - 2, col - 1, 2);
            setModule(row - 1, col - 2, 3);
            setModule(row - 1, col - 1, 4);
            setModule(row - 1, col, 5);
            setModule(row, col - 2, 6);
            setModule(row, col - 1, 7);
            setModule(row, col, 8);
            _chr++;
        }

        private function corner1() as Void {
            setModule(_nrow - 1, 0, 1);
            setModule(_nrow - 1, 1, 2);
            setModule(_nrow - 1, 2, 3);
            setModule(0, _ncol - 2, 4);
            setModule(0, _ncol - 1, 5);
            setModule(1, _ncol - 1, 6);
            setModule(2, _ncol - 1, 7);
            setModule(3, _ncol - 1, 8);
            _chr++;
        }

        private function corner2() as Void {
            setModule(_nrow - 3, 0, 1);
            setModule(_nrow - 2, 0, 2);
            setModule(_nrow - 1, 0, 3);
            setModule(0, _ncol - 4, 4);
            setModule(0, _ncol - 3, 5);
            setModule(0, _ncol - 2, 6);
            setModule(0, _ncol - 1, 7);
            setModule(1, _ncol - 1, 8);
            _chr++;
        }

        private function corner3() as Void {
            setModule(_nrow - 3, 0, 1);
            setModule(_nrow - 2, 0, 2);
            setModule(_nrow - 1, 0, 3);
            setModule(0, _ncol - 2, 4);
            setModule(0, _ncol - 1, 5);
            setModule(1, _ncol - 1, 6);
            setModule(2, _ncol - 1, 7);
            setModule(3, _ncol - 1, 8);
            _chr++;
        }

        private function corner4() as Void {
            setModule(_nrow - 1, 0, 1);
            setModule(_nrow - 1, _ncol - 1, 2);
            setModule(0, _ncol - 3, 3);
            setModule(0, _ncol - 2, 4);
            setModule(0, _ncol - 1, 5);
            setModule(1, _ncol - 3, 6);
            setModule(1, _ncol - 2, 7);
            setModule(1, _ncol - 1, 8);
            _chr++;
        }

        // The symbol: data modules mapped into the regions, plus each
        // region's finder (solid left and bottom) and clock (top, right);
        // BUILD_MODULES_PER_STEP modules (whole rows) per step.
        private function build() as Void {
            var size = _size[0];
            var region = _size[1];
            var box = region + 2;
            if (_modules.size() == 0) {
                _modules = new [size * size]b;
            }
            var m = _modules;
            var rows = BUILD_MODULES_PER_STEP / size > 0 ? BUILD_MODULES_PER_STEP / size : 1;
            var last = _buildRow + rows < size ? _buildRow + rows : size;
            for (var y = _buildRow; y < last; y++) {
                var ry = y % box;
                for (var x = 0; x < size; x++) {
                    var rx = x % box;
                    var dark = 0;
                    if (rx == 0 || ry == box - 1) {
                        dark = 1;
                    } else if (ry == 0) {
                        dark = rx % 2 == 0 ? 1 : 0;
                    } else if (rx == box - 1) {
                        dark = ry % 2 == 1 ? 1 : 0;
                    } else {
                        var mr = (y / box) * region + ry - 1;
                        var mc = (x / box) * region + rx - 1;
                        var at = 2 * (mr * _ncol + mc);
                        var v = (_place[at] << 8) | _place[at + 1];
                        if (v == FIXED_DARK) {
                            dark = 1;
                        } else if (v > 0) {
                            var cw = _cw[v / 10 - 1];
                            dark = (cw >> (8 - v % 10)) & 1;
                        }
                    }
                    m[y * size + x] = dark;
                }
            }
            _buildRow = last;
            if (_buildRow < size) {
                return;
            }
            _place = []b;
            _modules = []b;
            _result = new Codes.Matrix(size, size, QUIET, m);
            _phase = 5;
        }
    }
}