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, a few
//      diagonal sweeps 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;
    // Work per step, sized for the 120,000-bytecode watchdog.
    const RS_SYMBOLS_PER_STEP = 40;
    const SWEEPS_PER_STEP = 6;

    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 ascii = [] as Array<Number>;
        var highBytes = 0;
        var i = 0;
        while (i < data.size()) {
            var b = data[i];
            if (b >= 0x30 && b <= 0x39 && i + 1 < data.size() && 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++;
        }
        var n = data.size();
        var base256Cost = 1 + (n <= 249 ? 1 : 2) + n;
        if (highBytes == 0 || ascii.size() <= base256Cost) {
            return ascii;
        }
        var 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));
        }
        for (var k = 0; k < n; k++) {
            out.add(randomise255(data[k], out.size() + 1));
        }
        return out;
    }

    // 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 _rem as Array<Number> = [] as Array<Number>;
        private var _block as Number = 0;
        private var _at as Number = 0;
        private var _ecTotal as Array<Number> = [] as Array<Number>;
        // Placement state.
        private var _nrow as Number = 0;
        private var _ncol as Number = 0;
        private var _place as Array<Number> = [] as Array<Number>; // 10 * codeword + bit, 0 = empty, -1 = fixed dark
        private var _chr as Number = 1;
        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);
        }

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

        // Codewords, size, padding, blocks.
        private function prepare() as Void {
            if (_data.size() == 0) {
                error = "Data Matrix needs some text";
                return;
            }
            var cw = codewords(_data);
            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>;
            startBlock();
            _phase = 1;
        }

        private function startBlock() as Void {
            var n = _size[4] / _size[5];
            _rem = new [n] as Array<Number>;
            for (var k = 0; k < n; k++) {
                _rem[k] = 0;
            }
            _at = 0;
        }

        // Reed-Solomon, RS_SYMBOLS_PER_STEP data symbols per step.
        private function eccStep() as Void {
            var f = theField();
            var data = _blocks[_block];
            var n = _rem.size();
            var g = f.generator(n);
            var end = _at + RS_SYMBOLS_PER_STEP < data.size() ? _at + RS_SYMBOLS_PER_STEP : data.size();
            for (var i = _at; i < end; i++) {
                var factor = data[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 < data.size()) {
                return;
            }
            // Interleave this block's EC codewords.
            var blocks = _size[5];
            for (var k = 0; k < n; k++) {
                _ecTotal[_block + k * blocks] = _rem[k];
            }
            _block++;
            if (_block < blocks) {
                startBlock();
                return;
            }
            _cw.addAll(_ecTotal);
            _blocks = [] as Array<Array<Number>>;
            _nrow = _size[1] * _size[2];
            _ncol = _nrow;
            _place = new [_nrow * _ncol] as Array<Number>;
            for (var k = 0; k < _place.size(); k++) {
                _place[k] = 0;
            }
            _phase = 2;
        }

        // ISO 16022 annex F placement, SWEEPS_PER_STEP diagonal sweeps per step.
        private function placeStep() as Void {
            var nrow = _nrow;
            var ncol = _ncol;
            for (var s = 0; s < SWEEPS_PER_STEP && (_row < nrow || _col < ncol); s++) {
                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 {
                    if (_row < nrow && _col >= 0 && _place[_row * ncol + _col] == 0) {
                        utah(_row, _col);
                    }
                    _row -= 2;
                    _col += 2;
                } while (_row >= 0 && _col < ncol);
                _row += 1;
                _col += 3;
                do {
                    if (_row >= 0 && _col < ncol && _place[_row * ncol + _col] == 0) {
                        utah(_row, _col);
                    }
                    _row += 2;
                    _col -= 2;
                } while (_row < nrow && _col >= 0);
                _row += 3;
                _col += 1;
            }
            if (_row < nrow || _col < ncol) {
                return;
            }
            if (_place[nrow * ncol - 1] == 0) {
                _place[nrow * ncol - 1] = -1;
                _place[nrow * ncol - ncol - 2] = -1;
            }
            _phase = 3;
        }

        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);
            }
            _place[r * _ncol + c] = 10 * _chr + bit;
        }

        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).
        private function build() as Void {
            var size = _size[0];
            var region = _size[1];
            var box = region + 2;
            var m = new [size * size]b;
            for (var y = 0; y < size; 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 v = _place[mr * _ncol + mc];
                        if (v == -1) {
                            dark = 1;
                        } else if (v > 0) {
                            var cw = _cw[v / 10 - 1];
                            dark = (cw >> (8 - v % 10)) & 1;
                        }
                    }
                    m[y * size + x] = dark;
                }
            }
            _place = [] as Array<Number>;
            _result = new Codes.Matrix(size, size, QUIET, m);
            _phase = 4;
        }
    }
}