path: root/source/codes/Pdf417.mc

// Author:  cirakg & claude ai
// Summary: PDF417 encoder (ISO/IEC 15438): text, byte and numeric compaction as pdf417gen does it, columns fitted to the screen.
//
// Steps:
//   1. Compaction, mirroring pdf417gen (the test reference): the bytes are
//      split into runs of digits, text-compactable characters and other
//      bytes; digit runs under 13 next to text become text; equal neighbours
//      merge. Text uses the four submodes (switch codes, pairs of values,
//      29 as padding), numeric packs 44 digits per base-900 group, byte
//      packs 6 bytes into 5 codewords.
//   2. Error-correction level: the option's fixed level, or automatic
//      (ISO 15438 annex E: 2 up to 40 data codewords, then 3, 4, 5).
//   3. Columns and module size: the largest module size, then the fewest
//      columns, for which the symbol (with a 2-module quiet zone and rows 3
//      modules high) fits the screen (Codes.fits).
//   4. Padding (900), length descriptor, Reed-Solomon mod 929 in steps.
//   5. Rows: start, left row indicator, data, right row indicator, stop,
//      each codeword drawn from its cluster's 17-module pattern.
// The 2,787 patterns, EC factors and text table are JSON resources
// generated from pdf417gen (tools/gen_pdf417_tables.py), loaded only while
// encoding.

import Toybox.Lang;
import Toybox.Math;
import Toybox.WatchUi;

module Pdf417 {

    const START = 0x1fea8;
    const STOP = 0x3fa29;
    const PAD = 900;
    const TEXT_LATCH = 900;
    const BYTE_LATCH = 901;
    const BYTE_LATCH_6 = 924;
    const NUMERIC_LATCH = 902;
    const ROW_HEIGHT = 3;
    const QUIET = 2;
    // Cumulative percent at the end of each phase 0-2 (see Pdf417Job.percent).
    const PHASE_ENDS = [40, 70, 100];
    const MAX_CODEWORDS = 928;

    const KIND_TEXT = 0;
    const KIND_BYTE = 1;
    const KIND_NUMERIC = 2;

    // Text submodes and the switch codes between them [from][to].
    const UPPER = 0;
    const LOWER = 1;
    const MIXED = 2;
    const PUNCT = 3;
    const SWITCHES = [
        [[], [27], [28], [28, 25]],
        [[28, 28], [], [28], [28, 25]],
        [[28], [27], [], [25]],
        [[29], [29, 27], [29, 28], []]
    ];
    const PREFERENCE = [1, 0, 2, 3]; // lower, upper, mixed, punctuation
    // 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 the largest payload its screen takes.
    const COMPACT_PER_STEP = 150;   // bytes (or runs) compacted
    const EC_WORK_PER_STEP = 300;   // data codewords x EC codewords
    const ROWS_PER_STEP = 2;

    // One of the generated table resources ("v" holds the values).
    function table(id as ResourceId) as Array {
        return (WatchUi.loadResource(id) as Dictionary)["v"] as Array;
    }

    // Data codewords (without length descriptor and padding).
    function dataCodewords(data as ByteArray, text as Array<Array<Number>>) as Array<Number> {
        var compactor = new Compactor(data, text);
        while (!compactor.step(data.size() + 1)) {
        }
        return compactor.out;
    }

    // dataCodewords() in steps of about `budget` bytes (or runs): the runs
    // of one kind, then the merged runs (short digit runs next to text
    // become text, equal neighbours join), then the compaction of each run.
    class Compactor {
        var out as Array<Number> = [] as Array<Number>;

        private var _data as ByteArray;
        private var _text as Array<Array<Number>>;
        private var _stage as Number = 0;
        private var _i as Number = 0;
        // [kind, start, end) triples, before and after merging.
        private var _runs as Array<Number> = [] as Array<Number>;
        private var _merged as Array<Number> = [] as Array<Number>;
        // Compaction: the position in the current run (-1 before its latch),
        // the text submode and a text value waiting for its pair.
        private var _pos as Number = -1;
        private var _submode as Number = UPPER;
        private var _half as Number = -1;

        function initialize(data as ByteArray, text as Array<Array<Number>>) {
            _data = data;
            _text = text;
        }

        // True when out is complete.
        function step(budget as Number) as Boolean {
            if (_stage == 0) {
                findRuns(budget);
            } else if (_stage == 1) {
                mergeRuns(budget);
            } else {
                compact(budget);
            }
            return _stage == 3;
        }

        private function findRuns(budget as Number) as Void {
            var data = _data;
            var runs = _runs;
            var stop = _i + budget < data.size() ? _i + budget : data.size();
            for (var i = _i; i < stop; i++) {
                var kind = kindOf(data[i], _text);
                var n = runs.size();
                if (n > 0 && runs[n - 3] == kind) {
                    runs[n - 1] = i + 1;
                } else {
                    runs.add(kind);
                    runs.add(i);
                    runs.add(i + 1);
                }
            }
            _i = stop;
            if (_i >= data.size()) {
                _i = 0;
                _stage = 1;
            }
        }

        // Short digit runs next to text become text (judged by the original
        // neighbours), and equal neighbours merge, in one pass.
        private function mergeRuns(budget as Number) as Void {
            var runs = _runs;
            var merged = _merged;
            var stop = _i + 3 * budget < runs.size() ? _i + 3 * budget : runs.size();
            for (var r = _i; r < stop; r += 3) {
                var kind = runs[r];
                if (kind == KIND_NUMERIC && runs[r + 2] - runs[r + 1] < 13
                        && ((r > 0 && runs[r - 3] == KIND_TEXT) || (r + 3 < runs.size() && runs[r + 3] == KIND_TEXT))) {
                    kind = KIND_TEXT;
                }
                var n = merged.size();
                if (n > 0 && merged[n - 3] == kind) {
                    merged[n - 1] = runs[r + 2];
                } else {
                    merged.add(kind);
                    merged.add(runs[r + 1]);
                    merged.add(runs[r + 2]);
                }
            }
            _i = stop;
            if (_i >= runs.size()) {
                _runs = [] as Array<Number>;
                _i = 0;
                _stage = 2;
            }
        }

        private function compact(budget as Number) as Void {
            var left = budget;
            var merged = _merged;
            while (left > 0 && _i < merged.size()) {
                var kind = merged[_i];
                var start = merged[_i + 1];
                var end = merged[_i + 2];
                if (_pos < 0) {
                    if (_i > 0 || kind != KIND_TEXT) {
                        out.add(kind == KIND_TEXT ? TEXT_LATCH : (kind == KIND_NUMERIC ? NUMERIC_LATCH
                            : ((end - start) % 6 == 0 ? BYTE_LATCH_6 : BYTE_LATCH)));
                    }
                    _pos = start;
                    _submode = UPPER;
                    _half = -1;
                }
                var stop = 0;
                if (kind == KIND_TEXT) {
                    stop = _pos + left < end ? _pos + left : end;
                    compactText(_pos, stop);
                    left -= stop - _pos;
                } else if (kind == KIND_NUMERIC) {
                    stop = _pos + 44 < end ? _pos + 44 : end;
                    compactNumeric(_data, _pos, stop, out);
                    left -= 4 * (stop - _pos); // long division: costly per digit
                } else {
                    var groups = left / 6 > 0 ? left / 6 : 1;
                    stop = _pos + 6 * groups < end ? _pos + 6 * groups : end;
                    compactBytes(_data, _pos, stop, out);
                    left -= stop - _pos;
                }
                _pos = stop;
                if (_pos >= end) {
                    if (kind == KIND_TEXT && _half >= 0) {
                        out.add(30 * _half + 29);
                    }
                    _pos = -1;
                    _i += 3;
                }
            }
            if (_i >= merged.size()) {
                _merged = [] as Array<Number>;
                _stage = 3;
            }
        }

        // Text values of data[from, to) in the current submode, with switch
        // codes; values are paired into codewords as they come.
        private function compactText(from as Number, to as Number) as Void {
            var text = _text;
            var data = _data;
            for (var i = from; i < to; i++) {
                var c = data[i];
                if ((text[_submode][c] as Number) < 0) {
                    var next = _submode;
                    for (var p = 0; p < 4; p++) {
                        var m = PREFERENCE[p] as Number;
                        if ((text[m][c] as Number) >= 0) {
                            next = m;
                            break;
                        }
                    }
                    var codes = (SWITCHES[_submode] as Array)[next] as Array<Number>;
                    for (var k = 0; k < codes.size(); k++) {
                        textValue(codes[k]);
                    }
                    _submode = next;
                }
                textValue(text[_submode][c] as Number);
            }
        }

        private function textValue(v as Number) as Void {
            if (_half < 0) {
                _half = v;
            } else {
                out.add(30 * _half + v);
                _half = -1;
            }
        }
    }

    function kindOf(b as Number, text as Array<Array<Number>>) as Number {
        if (b >= 0x30 && b <= 0x39) {
            return KIND_NUMERIC;
        }
        if (b < 127) {
            for (var m = 0; m < 4; m++) {
                if ((text[m][b] as Number) >= 0) {
                    return KIND_TEXT;
                }
            }
        }
        return KIND_BYTE;
    }

    // 44 digits per group: the value of "1" followed by the digits, in base 900.
    function compactNumeric(data as ByteArray, start as Number, end as Number, out as Array<Number>) as Void {
        for (var g = start; g < end; g += 44) {
            var stop = g + 44 < end ? g + 44 : end;
            var decimal = [1] as Array<Number>;
            for (var i = g; i < stop; i++) {
                decimal.add(data[i] - 0x30);
            }
            var base900 = [] as Array<Number>;
            while (decimal.size() > 0) {
                // Divide the decimal number by 900, keeping the quotient.
                var quotient = [] as Array<Number>;
                var rem = 0;
                for (var k = 0; k < decimal.size(); k++) {
                    var cur = rem * 10 + decimal[k];
                    var q = cur / 900;
                    rem = cur % 900;
                    if (quotient.size() > 0 || q > 0) {
                        quotient.add(q);
                    }
                }
                base900.add(rem);
                decimal = quotient;
            }
            for (var k = base900.size() - 1; k >= 0; k--) {
                out.add(base900[k]);
            }
        }
    }

    // 6 bytes per group as 5 base-900 codewords; a shorter last group as is.
    function compactBytes(data as ByteArray, start as Number, end as Number, out as Array<Number>) as Void {
        for (var g = start; g < end; g += 6) {
            if (g + 6 > end) {
                for (var i = g; i < end; i++) {
                    out.add(data[i]);
                }
                return;
            }
            var value = 0l;
            for (var i = g; i < g + 6; i++) {
                value = value * 256 + data[i];
            }
            var digits = new [5] as Array<Number>;
            for (var k = 4; k >= 0; k--) {
                digits[k] = (value % 900).toNumber();
                value = value / 900;
            }
            out.addAll(digits);
        }
    }

    // ISO 15438 annex E recommended level for the data codewords.
    function autoLevel(dataCount as Number) as Number {
        if (dataCount <= 40) {
            return 2;
        }
        if (dataCount <= 160) {
            return 3;
        }
        return dataCount <= 320 ? 4 : 5;
    }

    // The option's level: Low 2, Medium automatic, Quartile 5, High 6.
    function levelFor(option as Number, dataCount as Number) as Number {
        return [2, autoLevel(dataCount), 5, 6][option] as Number;
    }

    function leftIndicator(row as Number, rows as Number, cols as Number, level as Number) as Number {
        var t = row % 3;
        var x = t == 0 ? (rows - 1) / 3 : (t == 1 ? level * 3 + (rows - 1) % 3 : cols - 1);
        return 30 * (row / 3) + x;
    }

    function rightIndicator(row as Number, rows as Number, cols as Number, level as Number) as Number {
        var t = row % 3;
        var x = t == 0 ? cols - 1 : (t == 1 ? (rows - 1) / 3 : level * 3 + (rows - 1) % 3);
        return 30 * (row / 3) + x;
    }

    // Encode synchronously with given columns and level (tests).
    function encode(text as String, cols as Number, level as Number) as Codes.Matrix or Codes.CodeError {
        var job = new Pdf417Job(text, 0, 0, 0, false);
        job.force(cols, level);
        Jobs.runToCompletion(job, 1);
        var err = job.error;
        return err != null ? new Codes.CodeError(err) : job.matrix() as Codes.Matrix;
    }

    class Pdf417Job extends Codes.MatrixJob {

        var columns as Number = 0;
        var level as Number = -1;
        var rows as Number = 0;

        private var _data as ByteArray;
        private var _option as Number;
        private var _screenW as Number;
        private var _screenH as Number;
        private var _round as Boolean;
        private var _phase as Number = 0;
        private var _words as Array<Number> = [] as Array<Number>;
        private var _ec as Array<Number> = [] as Array<Number>;
        private var _factors as Array<Number> = [] as Array<Number>;
        private var _compactor as Compactor? = null;
        private var _dataWords as Array<Number>? = null;
        private var _codes as Array<Array<Number>> = [] as Array<Array<Number>>;
        private var _at as Number = 0;
        private var _modules as ByteArray = []b;
        private var _result as Codes.Matrix? = null;

        // option: the EC option (0-3). The screen size decides the columns.
        function initialize(text as String, option as Number, screenW as Number, screenH as Number, round as Boolean) {
            MatrixJob.initialize();
            _data = Bytes.fromUtf8(text);
            _option = option;
            _screenW = screenW;
            _screenH = screenH;
            _round = round;
        }

        // Tests: fixed columns and level instead of the screen and option.
        function force(cols as Number, ecLevel as Number) as Void {
            columns = cols;
            level = ecLevel;
        }

        // Progress 0-100: the share of each phase (simulator timings), and
        // inside the Reed-Solomon and row phases how far they have got.
        function percent() as Number {
            var done = 0;
            var total = 0;
            if (_phase == 1) { // data codewords done
                done = _at;
                total = _words.size();
            } else if (_phase == 2) { // rows built
                done = _at;
                total = rows;
            }
            return Codes.phased(PHASE_ENDS, _phase, done, total);
        }

        // Packing and runs: about 62 / 7 / 31 % of a whole display job (the
        // wide matrices make the runs a third).
        function stageEnds() as Array<Number> {
            return [62, 69];
        }

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

        function step(budget as Number) as Boolean {
            if (_phase == 0) {
                prepare();
            } else if (_phase == 1) {
                ecStep();
            } else if (_phase == 2) {
                rowsStep();
            }
            return _phase >= 3 || error != null;
        }

        // Compaction in steps (after a quick check that the text could fit
        // the screen at all), then level, layout and padding, and the
        // tables in a step of their own.
        private function prepare() as Void {
            if (_data.size() == 0) {
                error = "PDF417 needs some text";
                return;
            }
            var data = _dataWords;
            if (data == null) {
                var compactor = _compactor;
                if (compactor == null) {
                    // At best 44 digits take 15 codewords.
                    var least = _data.size() * 15 / 44;
                    if (least > MAX_CODEWORDS || (columns == 0 && least > screenCapacity())) {
                        error = "too large for this screen as PDF417 (at least " + least + " codewords)";
                        return;
                    }
                    compactor = new Compactor(_data, table(Rez.JsonData.Pdf417Text) as Array<Array<Number>>);
                    _compactor = compactor;
                }
                if (!compactor.step(COMPACT_PER_STEP)) {
                    return;
                }
                _compactor = null;
                _dataWords = compactor.out;
                return;
            }
            if (level < 0) {
                level = levelFor(_option, data.size());
            }
            var ecCount = 1 << (level + 1);
            if (columns == 0 && !chooseLayout(data.size() + ecCount + 1)) {
                error = "too large for this screen as PDF417 (" + data.size() + " codewords)";
                return;
            }
            var total = data.size() + ecCount + 1;
            var padding = total % columns == 0 ? 0 : columns - total % columns;
            var length = data.size() + padding + 1;
            rows = (total + padding) / columns;
            if (length > MAX_CODEWORDS || rows > 90) {
                error = "too long for PDF417 (" + data.size() + " codewords)";
                return;
            }
            if (rows < 3) {
                error = "PDF417 needs at least 3 rows; use fewer columns";
                return;
            }
            _words = [length] as Array<Number>;
            _words.addAll(data);
            _dataWords = null;
            for (var i = 0; i < padding; i++) {
                _words.add(PAD);
            }
            _factors = (table(Rez.JsonData.Pdf417Ec) as Array<Array<Number>>)[level];
            _codes = [table(Rez.JsonData.Pdf417Codes0) as Array<Number>, table(Rez.JsonData.Pdf417Codes1) as Array<Number>,
                table(Rez.JsonData.Pdf417Codes2) as Array<Number>];
            _ec = new [ecCount] as Array<Number>;
            for (var i = 0; i < ecCount; i++) {
                _ec[i] = 0;
            }
            _at = 0;
            _phase = 1;
        }

        // The most codewords any layout can hold on this screen (1 px per
        // module, up to 90 rows).
        private function screenCapacity() as Number {
            var best = 0;
            for (var cols = 1; cols <= 30; cols++) {
                var w = 17 * (cols + 4) + 1 + 2 * QUIET;
                for (var r = 90; r >= 3; r -= 3) {
                    if (Codes.fits(w, r * ROW_HEIGHT + 2 * QUIET, 1, _screenW, _screenH, _round)) {
                        best = cols * r > best ? cols * r : best;
                        break;
                    }
                }
            }
            return best;
        }

        // The largest module size, then the fewest columns, that fit.
        private function chooseLayout(codewords as Number) as Boolean {
            for (var px = 6; px >= 1; px--) {
                for (var cols = 1; cols <= 30; cols++) {
                    var r = (codewords + cols - 1) / cols;
                    if (r < 3 || r > 90) {
                        continue;
                    }
                    var w = 17 * (cols + 4) + 1 + 2 * QUIET;
                    var h = r * ROW_HEIGHT + 2 * QUIET;
                    if (Codes.fits(w, h, px, _screenW, _screenH, _round)) {
                        columns = cols;
                        return true;
                    }
                }
            }
            return false;
        }

        // Reed-Solomon mod 929 (pdf417gen's form), EC_WORK_PER_STEP data
        // codewords times EC codewords per step.
        private function ecStep() as Void {
            var n = _ec.size();
            var f = _factors;
            var words = EC_WORK_PER_STEP / n > 0 ? EC_WORK_PER_STEP / n : 1;
            var end = _at + words < _words.size() ? _at + words : _words.size();
            for (var i = _at; i < end; i++) {
                var temp = (_words[i] + _ec[n - 1]) % 929;
                for (var x = n - 1; x >= 0; x--) {
                    var word = x > 0 ? _ec[x - 1] : 0;
                    _ec[x] = (word + 929 - (temp * f[x]) % 929) % 929;
                }
            }
            _at = end;
            if (_at < _words.size()) {
                return;
            }
            for (var x = n - 1; x >= 0; x--) {
                var v = _ec[x];
                _words.add(v > 0 ? 929 - v : 0);
            }
            _ec = [] as Array<Number>;
            var width = 17 * (columns + 4) + 1;
            _modules = new [width * rows]b;
            _at = 0;
            _phase = 2;
        }

        // A few rows per step: start, indicators, data, stop.
        private function rowsStep() as Void {
            var width = 17 * (columns + 4) + 1;
            for (var k = 0; k < ROWS_PER_STEP && _at < rows; k++) {
                var row = _at;
                var cluster = _codes[row % 3];
                var x = put(row, 0, START, 17, width);
                x = put(row, x, cluster[leftIndicator(row, rows, columns, level)] as Number, 17, width);
                for (var c = 0; c < columns; c++) {
                    x = put(row, x, cluster[_words[row * columns + c]] as Number, 17, width);
                }
                x = put(row, x, cluster[rightIndicator(row, rows, columns, level)] as Number, 17, width);
                put(row, x, STOP, 18, width);
                _at++;
            }
            if (_at < rows) {
                return;
            }
            _codes = [] as Array<Array<Number>>;
            _words = [] as Array<Number>;
            var result = new Codes.Matrix(width, rows, QUIET, _modules);
            result.rowHeight = ROW_HEIGHT;
            _result = result;
            _phase = 3;
        }

        // Draw count bits of pattern (most significant first) at column x of
        // row `row`; returns the next column.
        private function put(row as Number, x as Number, pattern as Number, count as Number, width as Number) as Number {
            var at = row * width + x;
            for (var i = 0; i < count; i++) {
                _modules[at + i] = (pattern >> (count - 1 - i)) & 1;
            }
            return x + count;
        }
    }
}