path: root/source/codes/Qr.mc

// Author:  cirakg & claude ai
// Summary: QR Code encoder (ISO/IEC 18004): optimal mode segmentation, versions 1-40, levels L-H, all 8 masks, as a resumable job.
//
// Steps (README 12.1):
//   1. Segment the UTF-8 bytes optimally into numeric, alphanumeric and
//      byte segments (dynamic programming, as in Nayuki's QR library), and
//      pick the smallest version whose capacity at the chosen level fits.
//   2. Build the bit stream (mode, character count, data, terminator, pad
//      codewords 0xEC 0x11), split it into blocks, add Reed-Solomon
//      codewords (QrTables.BLOCKS), interleave.
//   3. Draw the function patterns, place the codewords in the zigzag.
//   4. Pack the rows and columns 16 modules per word, then score all 8
//      masks with the ISO 18004:2015 penalty rules exactly as segno
//      computes them (format and version areas still light), with bit
//      operations on the packed lines; keep the lowest.
//   5. Apply that mask, then draw the format and version information.
// Each step does a bounded amount of work (one RS block, a few columns or
// rows, a few hundred packed words), because version 40 is far beyond one
// event's watchdog budget.
// Verified against segno with forced version and mask, and by decoding.

import Toybox.Lang;

module Qr {

    const MODE_NUMERIC = 1;
    const MODE_ALPHANUMERIC = 2;
    const MODE_BYTE = 4;
    const ALPHANUMERIC = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:"; // lint: allow-literal (QR alphanumeric set)
    // Format bits per level L, M, Q, H.
    const LEVEL_BITS = [1, 0, 3, 2];
    // Modules placed, packed or unmasked per job step. Every step size here
    // was checked in the simulator by running two steps per event on the
    // Forerunner 255S (120,000 bytecodes per event): each step stays below
    // half the watchdog limit.
    const PLACE_MODULES_PER_STEP = 300;
    const PACK_MODULES_PER_STEP = 400;
    const APPLY_MODULES_PER_STEP = 600;
    // Mask scoring works on packed lines (16 modules per word, see
    // startPacking); words scored per step. The row pass masks the line and
    // scores N1, N2, N3 and the dark count, the column pass N1 and N3.
    const ROW_WORDS_PER_STEP = 100;
    const COLUMN_WORDS_PER_STEP = 150;
    // Light bits before each packed line.
    const PAD = 4;
    // Phase 0: characters segmented or written per step (the segmentation
    // costs about 150 bytecodes per character).
    const SEGMENT_CHARS_PER_STEP = 80;
    const WRITE_CHARS_PER_STEP = 300;
    // Phase 1: data symbols times EC symbols per step (about 35 bytecodes each).
    const ECC_WORK_PER_STEP = 400;
    // Cumulative percent at the end of each phase 0-6 (see QrJob.percent).
    const PHASE_ENDS = [8, 16, 18, 27, 39, 93, 100];
    // Phase 2: codewords interleaved per step.
    const INTERLEAVE_PER_STEP = 600;
    const PREP_SEGMENT = 0;
    const PREP_WRITE = 1;
    const PREP_SPLIT = 2;

    // The GF(256) field of QR (x^8 + x^4 + x^3 + x^2 + 1), shared.
    var field as ReedSolomon.Field? = null;

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

    // Data codewords of version v at level ec (0 L .. 3 H).
    function dataCodewords(v as Number, ec as Number) as Number {
        var i = ((v - 1) * 4 + ec) * 5;
        var b = QrTables.BLOCKS;
        return (b[i + 1] as Number) * (b[i + 2] as Number) + (b[i + 3] as Number) * (b[i + 4] as Number);
    }

    function charCountBits(mode as Number, v as Number) as Number {
        var c = v <= 9 ? 0 : (v <= 26 ? 1 : 2);
        if (mode == MODE_NUMERIC) {
            return [10, 12, 14][c] as Number;
        }
        if (mode == MODE_ALPHANUMERIC) {
            return [9, 11, 13][c] as Number;
        }
        return [8, 16, 16][c] as Number;
    }

    function isDigit(b as Number) as Boolean {
        return b >= 0x30 && b <= 0x39;
    }

    // The alphanumeric value of byte b, or -1 (table built on first use).
    var alnumTable as ByteArray? = null;

    function alnumValue(b as Number) as Number {
        var t = alnumTable;
        if (t == null) {
            t = new [128]b;
            var chars = ALPHANUMERIC.toUtf8Array();
            for (var k = 0; k < chars.size(); k++) {
                t[chars[k]] = k + 1;
            }
            alnumTable = t;
        }
        return b < 0x80 ? t[b] - 1 : -1;
    }

    // Optimal segmentation for a version class: [mode, start, end) triples
    // flattened, by dynamic programming over the bytes (Nayuki's
    // makeSegmentsOptimally). Costs are in sixths of a bit (numeric 10/3,
    // alphanumeric 11/2, byte 8 bits per character). State j after
    // character i: the cheapest encoding so far that continues in mode j;
    // choice[i * 3 + j] is the mode character i itself was encoded in.
    // Resumable: step() handles a bounded number of characters (the
    // programme, then the walk back and the collection of segments, which
    // cost far less per character), so a 2,900-byte payload never runs in
    // one event.
    class Segmenter {
        static const MODES = [MODE_BYTE, MODE_ALPHANUMERIC, MODE_NUMERIC];
        static const INF = 0x3FFFFFFF;

        var segments as Array<Number> = [] as Array<Number>;

        private var _data as ByteArray;
        private var _head as Array<Number>;
        private var _prev as Array<Number>;
        private var _cur as Array<Number> = [0, 0, 0];
        private var _choice as ByteArray;
        private var _charModes as ByteArray = []b;
        private var _i as Number = 0;
        private var _walk as Number = 0;
        private var _state as Number = 0;
        private var _start as Number = 0;
        private var _collected as Number = 0;
        private var _done as Boolean = false;

        function initialize(data as ByteArray, v as Number) {
            _data = data;
            _head = [(4 + charCountBits(MODE_BYTE, v)) * 6, (4 + charCountBits(MODE_ALPHANUMERIC, v)) * 6,
                (4 + charCountBits(MODE_NUMERIC, v)) * 6];
            _prev = [_head[0], _head[1], _head[2]];
            _choice = new [data.size() * 3]b;
        }

        // Up to `chars` more characters (of the programme, then of each walk
        // back); true when segments is ready.
        function step(chars as Number) as Boolean {
            var n = _data.size();
            if (_i < n) {
                program(chars);
            } else if (_walk > 0) {
                walkBack(chars * 4);
            } else {
                collect(chars * 4);
            }
            return _done;
        }

        private function program(chars as Number) as Void {
            var n = _data.size();
            var head = _head;
            var prev = _prev;
            var cur = _cur;
            var choice = _choice;
            var stop = _i + chars < n ? _i + chars : n;
            for (var i = _i; i < stop; i++) {
                var b = _data[i];
                cur[0] = prev[0] + 48;
                cur[1] = alnumValue(b) >= 0 ? prev[1] + 33 : INF;
                cur[2] = isDigit(b) ? prev[2] + 20 : INF;
                choice[i * 3] = 0;
                choice[i * 3 + 1] = 1;
                choice[i * 3 + 2] = 2;
                for (var j = 0; j < 3; j++) {
                    for (var k = 0; k < 3; k++) {
                        if (k == j || cur[k] >= INF) {
                            continue;
                        }
                        // State j may follow a character in mode k: a new
                        // segment in mode j starts after it (its header paid now).
                        var switched = (cur[k] + 5) / 6 * 6 + head[j];
                        if (switched < cur[j]) {
                            cur[j] = switched;
                            choice[i * 3 + j] = k;
                        }
                    }
                }
                var swap = prev;
                prev = cur;
                cur = swap;
            }
            _prev = prev;
            _cur = cur;
            _i = stop;
            if (_i >= n) {
                // The cheapest final mode starts the walk back.
                var best = 0;
                for (var j = 1; j < 3; j++) {
                    if (_prev[j] < _prev[best]) {
                        best = j;
                    }
                }
                _state = best;
                _charModes = new [n]b;
                _walk = n;
            }
        }

        // From the end: the state after character i says which mode i was in.
        private function walkBack(chars as Number) as Void {
            var stop = _walk - chars > 0 ? _walk - chars : 0;
            for (var i = _walk - 1; i >= stop; i--) {
                var charMode = _choice[i * 3 + _state];
                _charModes[i] = charMode;
                _state = charMode;
            }
            _walk = stop;
            if (_walk == 0) {
                _choice = []b;
            }
        }

        // From the start: runs of one mode become segments.
        private function collect(chars as Number) as Void {
            var n = _data.size();
            var stop = _collected + chars < n ? _collected + chars : n;
            for (var i = _collected + 1; i <= stop; i++) {
                if (i == n || _charModes[i] != _charModes[_start]) {
                    segments.add(MODES[_charModes[_start]] as Number);
                    segments.add(_start);
                    segments.add(i);
                    _start = i;
                }
            }
            _collected = stop;
            if (_collected >= n) {
                _charModes = []b;
                _done = true;
            }
        }
    }

    // Bits needed for segments at version v.
    function segmentBits(segments as Array<Number>, v as Number) as Number {
        var total = 0;
        for (var s = 0; s < segments.size(); s += 3) {
            var mode = segments[s];
            var count = segments[s + 2] - segments[s + 1];
            total += 4 + charCountBits(mode, v);
            if (mode == MODE_NUMERIC) {
                total += count / 3 * 10 + [0, 4, 7][count % 3];
            } else if (mode == MODE_ALPHANUMERIC) {
                total += count / 2 * 11 + (count % 2) * 6;
            } else {
                total += count * 8;
            }
        }
        return total;
    }

    // A growing bit stream packed into codewords. Bits wait in `_acc`
    // until a whole byte is ready.
    class BitWriter {
        var bytes as ByteArray = []b;
        var bitCount as Number = 0;

        private var _acc as Number = 0;
        private var _accBits as Number = 0;

        function initialize() {
        }

        // The low `count` bits of value (count <= 16), most significant first.
        function put(value as Number, count as Number) as Void {
            _acc = (_acc << count) | (value & ((1 << count) - 1));
            _accBits += count;
            bitCount += count;
            while (_accBits >= 8) {
                _accBits -= 8;
                bytes.add((_acc >> _accBits) & 0xFF);
            }
            _acc = _acc & ((1 << _accBits) - 1);
        }
    }

    // The QR result: a size x size matrix, row-major, 1 = dark.
    class MatrixCode {
        var size as Number;
        var modules as ByteArray;
        var version as Number;
        var mask as Number;

        function initialize(n as Number, bits as ByteArray, v as Number, m as Number) {
            size = n;
            modules = bits;
            version = v;
            mask = m;
        }
    }

    // Encode synchronously (tests and small codes); the app uses QrJob.
    function encode(text as String, ec as Number, forceVersion as Number, forceMask as Number) as MatrixCode or Codes.CodeError {
        var job = new QrJob(text, ec, forceVersion, forceMask);
        Jobs.runToCompletion(job, 1);
        var err = job.error;
        return err != null ? new Codes.CodeError(err) : job.result as MatrixCode;
    }

    class QrJob extends Codes.MatrixJob {

        var result as MatrixCode? = null;

        private var _data as ByteArray;
        private var _ec as Number;
        private var _version as Number = 0;
        private var _forceMask as Number;
        private var _phase as Number = 0;
        private var _size as Number = 0;
        private var _m as ByteArray = []b;          // modules, row-major
        private var _function as ByteArray = []b;   // 1 = function module
        private var _blocks as Array<Array<Number>> = [] as Array<Array<Number>>;
        private var _ecBlocks as Array<Array<Number>> = [] as Array<Array<Number>>;
        private var _codewords as ByteArray = []b;
        private var _cursor as Number = 0;
        private var _bitIndex as Number = 0;
        private var _maskIndex as Number = 0;
        private var _bestMask as Number = 0;
        private var _bestScore as Number = 0x7FFFFFFF;
        private var _score as Number = 0;
        private var _dark as Number = 0;
        private var _maskPass as Number = 0;
        // Phase 0 (buildCodewords).
        private var _prep as Number = PREP_SEGMENT;
        private var _class as Number = 0;
        private var _segmenter as Segmenter? = null;
        private var _segments as Array<Number> = [] as Array<Number>;
        private var _writer as BitWriter? = null;
        private var _charAt as Number = -1;
        private var _encoder as ReedSolomon.Encoder? = null;
        // Packed lines (startPacking): rows and columns, their non-function
        // modules, the current mask's patterns, scratch lines.
        private var _words as Number = 0;
        private var _rows as Array<Number> = [] as Array<Number>;
        private var _rowFree as Array<Number> = [] as Array<Number>;
        private var _cols as Array<Number> = [] as Array<Number>;
        private var _colFree as Array<Number> = [] as Array<Number>;
        private var _lineMask as Array<Number> = [] as Array<Number>;
        private var _n1Valid as Array<Number> = [] as Array<Number>;
        private var _n2Valid as Array<Number> = [] as Array<Number>;
        private var _rowPattern as Array<Array<Number>> = [] as Array<Array<Number>>;
        private var _columnPattern as Array<Array<Number>> = [] as Array<Array<Number>>;
        private var _patternMask as Number = -1;
        private var _cur as Array<Number> = [] as Array<Number>;
        private var _prev as Array<Number> = [] as Array<Number>;

        // The penalty of each mask, in order (empty with a forced mask).
        var scores as Array<Number> = [] as Array<Number>;

        // ec: 0 L, 1 M, 2 Q, 3 H. forceVersion 0 = smallest that fits;
        // forceMask -1 = best by penalty.
        function initialize(text as String, ec as Number, forceVersion as Number, forceMask as Number) {
            MatrixJob.initialize();
            _data = Bytes.fromUtf8(text);
            _ec = ec;
            _forceMask = forceMask;
            _version = forceVersion;
        }

        // Progress 0-100 for the UI: the share of each phase of the work
        // (simulator timings of a version 6, a version 40 and a level H
        // code; mask scoring is about half of it), and inside the long ones
        // how far they have got.
        function percent() as Number {
            var done = 0;
            var total = 0;
            if (_phase == 1 && _blocks.size() > 0) { // blocks done, and the current one
                var e = _encoder;
                done = _cursor * 100 + (e != null ? e.percent() : 0);
                total = _blocks.size() * 100;
            } else if (_phase == 3) { // column pairs, right to left
                done = _size - 1 - _cursor;
                total = _size - 1;
            } else if (_phase == 5) { // lines of the masks scored so far
                done = (_maskIndex * 2 + _maskPass) * _size + _cursor;
                total = 16 * _size;
            } else if (_phase == 6) { // rows masked
                done = _cursor;
                total = _size;
            }
            return Codes.phased(PHASE_ENDS, _phase, done, total);
        }

        // Packing and runs: about 92 / 2 / 6 % of a whole display job.
        function stageEnds() as Array<Number> {
            return [92, 94];
        }

        // The code as a generic matrix with QR's 4-module quiet zone.
        function matrix() as Codes.Matrix? {
            var r = result;
            return r != null ? new Codes.Matrix(r.size, r.size, 4, r.modules) : null;
        }

        function step(budget as Number) as Boolean {
            if (_phase == 0) {
                buildCodewords();
            } else if (_phase == 1) {
                eccStep();
            } else if (_phase == 2) {
                interleaveAndDrawFunctions();
            } else if (_phase == 3) {
                placeStep();
            } else if (_phase == 4) {
                packStep();
            } else if (_phase == 5) {
                maskStep();
            } else if (_phase == 6) {
                applyStep();
            }
            return _phase >= 7 || error != null;
        }

        // Phase 0: segments and version, then the bit stream, then blocks,
        // each in bounded steps:
        //   segment  the dynamic programme for one version class (versions
        //            1-9, 10-26, 27-40 count characters with different
        //            widths), SEGMENT_CHARS_PER_STEP characters per step,
        //            until a class fits the payload;
        //   write    the segments into the bit stream, WRITE_CHARS_PER_STEP
        //            characters per step, then terminator and padding;
        //   split    the codewords into the Reed-Solomon blocks.
        private function buildCodewords() as Void {
            if (_prep == PREP_SEGMENT) {
                segmentStep();
            } else if (_prep == PREP_WRITE) {
                writeStep();
            } else {
                splitBlocks();
            }
        }

        private function segmentStep() as Void {
            if (_data.size() == 0) {
                error = "QR needs some text";
                return;
            }
            var lowest = [1, 10, 27] as Array<Number>;
            var highest = [9, 26, 40] as Array<Number>;
            var forced = _version;
            var segmenter = _segmenter;
            if (segmenter == null) {
                if (forced > 0) {
                    _class = forced <= 9 ? 0 : (forced <= 26 ? 1 : 2);
                }
                // Skip a class the payload can't fit even as digits (10
                // bits per 3 characters), without segmenting for it.
                while (forced == 0 && _class < 2 && _data.size() * 10 / 3 > dataCodewords(highest[_class], _ec) * 8) {
                    _class++;
                }
                segmenter = new Segmenter(_data, lowest[_class]);
                _segmenter = segmenter;
            }
            if (!segmenter.step(SEGMENT_CHARS_PER_STEP)) {
                return;
            }
            _segmenter = null;
            var segments = segmenter.segments;
            var bits = segmentBits(segments, lowest[_class]);
            if (forced > 0) {
                if (bits > dataCodewords(forced, _ec) * 8) {
                    error = "too long for QR version " + forced;
                    return;
                }
            } else {
                for (var v = lowest[_class]; v <= highest[_class] && _version == 0; v++) {
                    if (bits <= dataCodewords(v, _ec) * 8) {
                        _version = v;
                    }
                }
                if (_version == 0) {
                    _class++;
                    if (_class > 2) {
                        error = "too long for a QR code at this error correction level (" + _data.size() + " bytes, at most "
                            + dataCodewords(40, _ec) + " in byte mode)";
                    }
                    return;
                }
            }
            _segments = segments;
            _writer = new BitWriter();
            _cursor = 0;
            _charAt = -1;
            _prep = PREP_WRITE;
        }

        // Write segment characters; _cursor is the segment (index into the
        // triples), _charAt the next character, -1 before its header.
        private function writeStep() as Void {
            var w = _writer as BitWriter;
            var segs = _segments;
            var d = _data;
            var budget = WRITE_CHARS_PER_STEP;
            while (budget > 0 && _cursor < segs.size()) {
                var mode = segs[_cursor];
                var end = segs[_cursor + 2];
                if (_charAt < 0) {
                    _charAt = segs[_cursor + 1];
                    w.put(mode, 4);
                    w.put(end - _charAt, charCountBits(mode, _version));
                }
                var i = _charAt;
                // Whole groups (3 digits, 2 alphanumerics) per step.
                var group = mode == MODE_NUMERIC ? 3 : (mode == MODE_ALPHANUMERIC ? 2 : 1);
                var take = budget / group * group;
                var stop = i + (take > group ? take : group);
                stop = stop < end ? stop : end;
                budget -= stop - i;
                if (mode == MODE_NUMERIC) {
                    while (i < stop) {
                        var count = stop - i >= 3 ? 3 : stop - i;
                        var value = 0;
                        for (var k = 0; k < count; k++) {
                            value = value * 10 + d[i + k] - 0x30;
                        }
                        w.put(value, [0, 4, 7, 10][count] as Number);
                        i += count;
                    }
                } else if (mode == MODE_ALPHANUMERIC) {
                    while (i < stop) {
                        if (stop - i >= 2) {
                            w.put(alnumValue(d[i]) * 45 + alnumValue(d[i + 1]), 11);
                            i += 2;
                        } else {
                            w.put(alnumValue(d[i]), 6);
                            i += 1;
                        }
                    }
                } else {
                    for (; i < stop; i++) {
                        w.put(d[i], 8);
                    }
                }
                _charAt = stop;
                if (stop >= end) {
                    _cursor += 3;
                    _charAt = -1;
                }
            }
            if (_cursor < segs.size()) {
                return;
            }
            // Terminator, byte alignment, pad codewords.
            var capacity = dataCodewords(_version, _ec);
            var terminator = capacity * 8 - w.bitCount;
            w.put(0, terminator < 4 ? terminator : 4);
            if (w.bitCount % 8 != 0) {
                w.put(0, 8 - w.bitCount % 8);
            }
            var pad = 0xEC;
            while (w.bytes.size() < capacity) {
                w.bytes.add(pad);
                pad = pad == 0xEC ? 0x11 : 0xEC;
            }
            _segments = [] as Array<Number>;
            _prep = PREP_SPLIT;
        }

        private function splitBlocks() as Void {
            var bytes = (_writer as BitWriter).bytes;
            _writer = null;
            var i = ((_version - 1) * 4 + _ec) * 5;
            var t = QrTables.BLOCKS;
            var at = 0;
            for (var g = 0; g < 2; g++) {
                var count = t[i + 1 + 2 * g] as Number;
                var len = t[i + 2 + 2 * g] as Number;
                for (var b = 0; b < count; b++) {
                    var block = new [len] as Array<Number>;
                    for (var k = 0; k < len; k++) {
                        block[k] = bytes[at + k];
                    }
                    at += len;
                    _blocks.add(block);
                }
            }
            _cursor = 0;
            _phase = 1;
        }

        // Phase 1: Reed-Solomon codewords, ECC_WORK_PER_STEP data symbols
        // times EC symbols per step (a version 40 block is 30 x 118).
        private function eccStep() as Void {
            var encoder = _encoder;
            if (encoder == null) {
                var i = ((_version - 1) * 4 + _ec) * 5;
                var n = QrTables.BLOCKS[i] as Number;
                var fresh = !theField().hasGenerator(n);
                encoder = new ReedSolomon.Encoder(theField(), _blocks[_cursor], n);
                _encoder = encoder;
                if (fresh) {
                    return; // the generator took this step
                }
            }
            if (!encoder.step(ECC_WORK_PER_STEP / encoder.remainder.size())) {
                return;
            }
            _encoder = null;
            _ecBlocks.add(encoder.remainder);
            _cursor++;
            if (_cursor >= _blocks.size()) {
                _cursor = 0;
                _codewords = []b;
                _phase = 2;
            }
        }

        // Phase 2: interleave the codewords, INTERLEAVE_PER_STEP per step
        // (_cursor is the position within the blocks, data then EC), then
        // draw the function patterns in a step of their own.
        private function interleaveStep() as Void {
            var longest = _blocks[_blocks.size() - 1].size(); // group-2 blocks are the longer ones
            var ecLen = _ecBlocks[0].size();
            var out = _codewords;
            var budget = INTERLEAVE_PER_STEP;
            while (_cursor < longest + ecLen && budget > 0) {
                var k = _cursor;
                var blocks = k < longest ? _blocks : _ecBlocks;
                var at = k < longest ? k : k - longest;
                for (var b = 0; b < blocks.size(); b++) {
                    if (at < blocks[b].size()) {
                        out.add(blocks[b][at]);
                    }
                }
                budget -= blocks.size();
                _cursor++;
            }
            if (_cursor < longest + ecLen) {
                return;
            }
            _blocks = [] as Array<Array<Number>>;
            _ecBlocks = [] as Array<Array<Number>>;
            _cursor = -1;
        }

        // After interleaving, _cursor counts down through the drawing:
        // -1 timing and finder patterns, -2 - a alignment row a, then the
        // format and version areas.
        private function interleaveAndDrawFunctions() as Void {
            if (_cursor >= 0) {
                interleaveStep();
                return;
            }
            var pos = QrTables.ALIGNMENT[_version - 1] as Array<Number>;
            if (_cursor == -1) {
                drawTimingAndFinders();
            } else if (-2 - _cursor < pos.size()) {
                drawAlignmentRow(pos, -2 - _cursor);
            } else {
                reserveFormatAndVersion();
                _cursor = _size - 1; // right column of the current column pair
                _bitIndex = 0;
                _phase = 3;
                return;
            }
            _cursor--;
        }

        private function drawTimingAndFinders() as Void {
            var n = 17 + 4 * _version;
            _size = n;
            _m = new [n * n]b;
            _function = new [n * n]b;
            for (var i = 0; i < n; i++) {
                setFunction(6, i, i % 2 == 0 ? 1 : 0);
                setFunction(i, 6, i % 2 == 0 ? 1 : 0);
            }
            // Finder patterns with separators.
            drawFinder(3, 3);
            drawFinder(n - 4, 3);
            drawFinder(3, n - 4);
        }

        // Alignment patterns in row a, except where they'd overlap the finders.
        private function drawAlignmentRow(pos as Array<Number>, a as Number) as Void {
            var count = pos.size();
            for (var b = 0; b < count; b++) {
                if ((a == 0 && b == 0) || (a == 0 && b == count - 1) || (a == count - 1 && b == 0)) {
                    continue;
                }
                drawAlignment(pos[a], pos[b]);
            }
        }

        private function reserveFormatAndVersion() as Void {
            var n = _size;
            // Format areas and the dark module's place stay light until the
            // mask is chosen (segno evaluates masks that way; ISO 18004:2015
            // 7.8 leaves format information out of the evaluation).
            for (var i = 0; i <= 8; i++) {
                if (i != 6) {
                    setFunction(8, i, 0);
                    setFunction(i, 8, 0);
                }
            }
            for (var i = 0; i < 8; i++) {
                setFunction(n - 1 - i, 8, 0);
                setFunction(8, n - 1 - i, 0);
            }
            setFunction(8, n - 8, 0);
            // Version areas (light for now).
            if (_version >= 7) {
                for (var i = 0; i < 18; i++) {
                    var a = n - 11 + i % 3;
                    var b = i / 3;
                    setFunction(a, b, 0);
                    setFunction(b, a, 0);
                }
            }
        }

        private function setFunction(x as Number, y as Number, dark as Number) as Void {
            var at = y * _size + x;
            _m[at] = dark;
            _function[at] = 1;
        }

        private function drawFinder(cx as Number, cy as Number) as Void {
            for (var dy = -4; dy <= 4; dy++) {
                for (var dx = -4; dx <= 4; dx++) {
                    var x = cx + dx;
                    var y = cy + dy;
                    if (x < 0 || y < 0 || x >= _size || y >= _size) {
                        continue;
                    }
                    var d = (dx.abs() > dy.abs() ? dx.abs() : dy.abs());
                    setFunction(x, y, d != 2 && d != 4 ? 1 : 0);
                }
            }
        }

        private function drawAlignment(cx as Number, cy as Number) as Void {
            for (var dy = -2; dy <= 2; dy++) {
                for (var dx = -2; dx <= 2; dx++) {
                    var d = (dx.abs() > dy.abs() ? dx.abs() : dy.abs());
                    setFunction(cx + dx, cy + dy, d != 1 ? 1 : 0);
                }
            }
        }

        // Phase 3: place the codeword bits in the zigzag, a few column pairs
        // per step.
        private function placeStep() as Void {
            var n = _size;
            var totalBits = _codewords.size() * 8;
            var budget = PLACE_MODULES_PER_STEP;
            while (_cursor >= 1 && budget > 0) {
                var right = _cursor == 6 ? 5 : _cursor;
                var upward = ((right + 1) & 2) == 0;
                for (var vert = 0; vert < n; vert++) {
                    var y = upward ? n - 1 - vert : vert;
                    for (var j = 0; j < 2; j++) {
                        var x = right - j;
                        var at = y * n + x;
                        if (_function[at] == 0 && _bitIndex < totalBits) {
                            _m[at] = (_codewords[_bitIndex >> 3] >> (7 - (_bitIndex & 7))) & 1;
                            _bitIndex++;
                        }
                    }
                }
                budget -= 2 * n;
                _cursor = right - 2;
            }
            if (_cursor < 1) {
                _codewords = []b;
                _cursor = 0;
                startPacking();
                _phase = 4;
            }
        }

        // ---- Packed lines (M8) ----------------------------------------
        // Mask scoring works on lines packed 16 modules per Number, so the
        // penalty rules run as a few bit operations per 16 modules instead
        // of a loop per module. Line layout: module i of a row or column is
        // bit (i + PAD) of the line, counted from bit 0 of word 0; PAD light
        // bits before the line and at least 16 after it let the N3 test look
        // 4 modules back and 10 ahead without special cases (outside the
        // symbol counts as light, which is what segno's clipped checks do).
        // Rows and columns are packed once; each mask is then
        // data XOR (pattern AND not-function), word by word.

        private function startPacking() as Void {
            var n = _size;
            var w = (n + PAD) / 16 + 2;
            _words = w;
            // Zeroed line by line with addAll (native), not word by word.
            var zeros = new [w] as Array<Number>;
            for (var k = 0; k < w; k++) {
                zeros[k] = 0;
            }
            _rows = [] as Array<Number>;
            _rowFree = [] as Array<Number>;
            _cols = [] as Array<Number>;
            _colFree = [] as Array<Number>;
            for (var line = 0; line < n; line++) {
                _rows.addAll(zeros);
                _rowFree.addAll(zeros);
                _cols.addAll(zeros);
                _colFree.addAll(zeros);
            }
            _lineMask = bitRange(PAD, n + PAD - 1);
            _n1Valid = bitRange(PAD, n + PAD - 5);
            _n2Valid = bitRange(PAD, n + PAD - 2);
            _cur = new [w] as Array<Number>;
            _prev = new [w] as Array<Number>;
        }

        // Words with bits first..last set.
        private function bitRange(first as Number, last as Number) as Array<Number> {
            var out = new [_words] as Array<Number>;
            for (var k = 0; k < _words; k++) {
                var word = 0;
                for (var b = 0; b < 16; b++) {
                    var p = k * 16 + b;
                    if (p >= first && p <= last) {
                        word |= 1 << b;
                    }
                }
                out[k] = word;
            }
            return out;
        }

        // Phase 4: pack rows and columns (modules and the non-function
        // mask), a few rows per step.
        private function packStep() as Void {
            var n = _size;
            var w = _words;
            var rows = PACK_MODULES_PER_STEP / n;
            for (var r = 0; r < rows && _cursor < n; r++) {
                var y = _cursor;
                var py = y + PAD;
                var colWord = py >> 4;
                var colBit = 1 << (py & 15);
                for (var x = 0; x < n; x++) {
                    var at = y * n + x;
                    var px = x + PAD;
                    var rowAt = y * w + (px >> 4);
                    var rowBit = 1 << (px & 15);
                    var colAt = x * w + colWord;
                    if (_m[at] != 0) {
                        _rows[rowAt] = _rows[rowAt] | rowBit;
                        _cols[colAt] = _cols[colAt] | colBit;
                    }
                    if (_function[at] == 0) {
                        _rowFree[rowAt] = _rowFree[rowAt] | rowBit;
                        _colFree[colAt] = _colFree[colAt] | colBit;
                    }
                }
                _cursor++;
            }
            if (_cursor < n) {
                return;
            }
            _function = []b;
            _cursor = 0;
            _maskIndex = _forceMask >= 0 ? _forceMask : 0;
            _patternMask = -1;
            _score = 0;
            _dark = 0;
            _maskPass = 0;
            _phase = 5;
        }

        // Mask m as packed lines: rowPattern[r] is row r (mod 12), across
        // the columns; columnPattern[c] is column c (mod 12), down the
        // rows. Every mask repeats every 12 modules along a row or a
        // column (mask 4 every 6 across and 4 down, the others every 2, 3
        // or 6), and every 12 lines; so twelve values are computed and
        // repeated over 48 bits (three words, a multiple of 12), then over
        // the line. maskBit gets coordinates shifted by 12 (the same mask
        // value) so they are never negative.
        private function buildPatterns(m as Number) as Void {
            _rowPattern = [] as Array<Array<Number>>;
            _columnPattern = [] as Array<Array<Number>>;
            for (var r = 0; r < 12; r++) {
                _rowPattern.add(repeated(m, r, true));
                _columnPattern.add(repeated(m, r, false));
            }
            _patternMask = m;
        }

        private function repeated(m as Number, fixed as Number, alongRow as Boolean) as Array<Number> {
            // Twelve mask values, starting at line position -PAD (+12).
            var twelve = new [12]b;
            for (var i = 0; i < 12; i++) {
                if (alongRow ? maskBit(m, 12 - PAD + i, fixed) : maskBit(m, fixed, 12 - PAD + i)) {
                    twelve[i] = 1;
                }
            }
            var period = [0, 0, 0];
            var at = 0;
            for (var p = 0; p < 48; p++) {
                if (twelve[at] != 0) {
                    period[p >> 4] = (period[p >> 4] as Number) | (1 << (p & 15));
                }
                at = at == 11 ? 0 : at + 1;
            }
            var out = new [_words] as Array<Number>;
            for (var k = 0; k < _words; k++) {
                out[k] = (period[k % 3] as Number) & (_lineMask[k] as Number);
            }
            return out;
        }

        // Phase 5: score masks (or take the forced one). Per mask: build its
        // patterns (one step), then the rows (N1, N2, N3 and the dark count)
        // and the columns (N1, N3), a bounded number of words per step.
        private function maskStep() as Void {
            if (_forceMask >= 0) {
                _bestMask = _forceMask;
                _phase = 6;
                return;
            }
            if (_patternMask != _maskIndex) {
                buildPatterns(_maskIndex);
                return;
            }
            var n = _size;
            var lines = (_maskPass == 0 ? ROW_WORDS_PER_STEP : COLUMN_WORDS_PER_STEP) / _words;
            if (lines < 1) {
                lines = 1;
            }
            for (var l = 0; l < lines && _cursor < n; l++) {
                if (_maskPass == 0) {
                    scoreRow(_cursor);
                } else {
                    scoreColumn(_cursor);
                }
                _cursor++;
            }
            if (_cursor < n) {
                return;
            }
            _cursor = 0;
            _maskPass++;
            if (_maskPass < 2) {
                return;
            }
            // N4: 10 points per 5 % away from half dark (integer form of segno's).
            var total = n * n;
            var deviation = (_dark * 100 - 50 * total).abs();
            _score += 10 * (deviation / (5 * total));
            scores.add(_score);
            if (_score < _bestScore) {
                _bestScore = _score;
                _bestMask = _maskIndex;
            }
            _maskIndex++;
            _maskPass = 0;
            _score = 0;
            _dark = 0;
            if (_maskIndex >= 8) {
                _phase = 6;
            }
        }

        // Masked line into `into`: data XOR (pattern AND free).
        private function maskLine(data as Array<Number>, free as Array<Number>, pattern as Array<Number>, line as Number,
                into as Array<Number>) as Void {
            var base = line * _words;
            for (var k = 0; k < _words; k++) {
                into[k] = (data[base + k] as Number) ^ ((pattern[k] as Number) & (free[base + k] as Number));
            }
        }

        private function scoreRow(y as Number) as Void {
            var swap = _prev;
            _prev = _cur;
            _cur = swap;
            var cur = _cur;
            maskLine(_rows, _rowFree, _rowPattern[y % 12], y, cur);
            _score += lineScore(cur);
            var pop = popTable();
            var dark = 0;
            for (var k = 0; k < _words; k++) {
                var c = cur[k] as Number;
                dark += pop[c & 0xFF] + pop[c >> 8];
            }
            _dark += dark;
            if (y == 0) {
                return;
            }
            // N2: 3 for every 2x2 block of one colour (with the row above).
            var prev = _prev;
            var blocks = 0;
            for (var k = 0; k < _words - 1; k++) {
                var c = (cur[k] as Number) | ((cur[k + 1] as Number) << 16);
                var q = (prev[k] as Number) | ((prev[k + 1] as Number) << 16);
                var same = ~((c ^ (c >> 1)) | (q ^ (q >> 1)) | (c ^ q)) & (_n2Valid[k] as Number);
                if (same != 0) {
                    blocks += pop[same & 0xFF] + pop[same >> 8];
                }
            }
            _score += 3 * blocks;
        }

        private function scoreColumn(x as Number) as Void {
            maskLine(_cols, _colFree, _columnPattern[x % 12], x, _cur);
            _score += lineScore(_cur);
        }

        // N1 and N3 of one packed row or column.
        //   N1: 3 + (run - 5) for every run of 5 or more equal modules. A
        //       run of length L has L - 4 windows of 5 equal modules, so N1
        //       is (windows) + 2 * (groups of windows).
        //   N3, as segno counts it: 40 for each 1011101 with 4 light
        //       modules before or after it (fewer at the edge); after a
        //       counted match the search continues behind it, otherwise 4
        //       modules on. Matches are rare, so they are walked one by one.
        // Positions s below are bit positions 4 before a match's first
        // module, so every look stays within the two words combined in e.
        private function lineScore(line as Array<Number>) as Number {
            var pop = popTable();
            var score = 0;
            var carry = 0;
            var nextAllowed = 0;
            for (var k = 0; k < _words - 1; k++) {
                var e = (line[k] as Number) | ((line[k + 1] as Number) << 16);
                var same = ~(e ^ (e >> 1));
                var windows = same & (same >> 1) & (same >> 2) & (same >> 3) & (_n1Valid[k] as Number);
                if (windows != 0) {
                    var starts = windows & ~((windows << 1) | carry) & 0xFFFF;
                    score += pop[windows & 0xFF] + pop[windows >> 8] + 2 * (pop[starts & 0xFF] + pop[starts >> 8]);
                }
                carry = (windows >> 15) & 1;
                var match = (e >> 4) & ~(e >> 5) & (e >> 6) & (e >> 7) & (e >> 8) & ~(e >> 9) & (e >> 10) & 0xFFFF;
                if (match == 0) {
                    continue;
                }
                var light = ~(e | (e >> 1) | (e >> 2) | (e >> 3)) | ~((e >> 11) | (e >> 12) | (e >> 13) | (e >> 14));
                for (var b = 0; b < 16; b++) {
                    var s = k * 16 + b;
                    if (((match >> b) & 1) == 0 || s < nextAllowed) {
                        continue;
                    }
                    if (((light >> b) & 1) != 0) {
                        score += 40;
                        nextAllowed = s + 7;
                    } else {
                        nextAllowed = s + 4;
                    }
                }
            }
            return score;
        }

        // Phase 6: apply the chosen mask to the module matrix, a few rows
        // per step (version 40 has 31,329 modules: far too many for one
        // event).
        private function applyStep() as Void {
            if (_patternMask != _bestMask) {
                buildPatterns(_bestMask);
                return;
            }
            var n = _size;
            var rows = APPLY_MODULES_PER_STEP / n;
            for (var r = 0; r < rows && _cursor < n; r++) {
                var y = _cursor;
                maskLine(_rows, _rowFree, _rowPattern[y % 12], y, _cur);
                var row = y * n;
                for (var x = 0; x < n; x++) {
                    var p = x + PAD;
                    _m[row + x] = ((_cur[p >> 4] as Number) >> (p & 15)) & 1;
                }
                _cursor++;
            }
            if (_cursor < n) {
                return;
            }
            _rows = [] as Array<Number>;
            _rowFree = [] as Array<Number>;
            _cols = [] as Array<Number>;
            _colFree = [] as Array<Number>;
            _rowPattern = [] as Array<Array<Number>>;
            _columnPattern = [] as Array<Array<Number>>;
            drawFormat(_bestMask);
            if (_version >= 7) {
                drawVersion();
            }
            result = new MatrixCode(n, _m, _version, _bestMask);
            _phase = 7;
        }

        private function drawFormat(mask as Number) as Void {
            var data = ((LEVEL_BITS[_ec] as Number) << 3) | mask;
            var rem = data;
            for (var i = 0; i < 10; i++) {
                rem = (rem << 1) ^ ((rem >> 9) * 0x537);
            }
            var bits = ((data << 10) | rem) ^ 0x5412;
            var n = _size;
            for (var i = 0; i <= 5; i++) {
                setModule(8, i, (bits >> i) & 1);
            }
            setModule(8, 7, (bits >> 6) & 1);
            setModule(8, 8, (bits >> 7) & 1);
            setModule(7, 8, (bits >> 8) & 1);
            for (var i = 9; i < 15; i++) {
                setModule(14 - i, 8, (bits >> i) & 1);
            }
            for (var i = 0; i < 8; i++) {
                setModule(n - 1 - i, 8, (bits >> i) & 1);
            }
            for (var i = 8; i < 15; i++) {
                setModule(8, n - 15 + i, (bits >> i) & 1);
            }
            setModule(8, n - 8, 1);
        }

        private function drawVersion() as Void {
            var rem = _version;
            for (var i = 0; i < 12; i++) {
                rem = (rem << 1) ^ ((rem >> 11) * 0x1F25);
            }
            var bits = (_version << 12) | rem;
            var n = _size;
            for (var i = 0; i < 18; i++) {
                var bit = (bits >> i) & 1;
                var a = n - 11 + i % 3;
                var b = i / 3;
                setModule(a, b, bit);
                setModule(b, a, bit);
            }
        }

        private function setModule(x as Number, y as Number, dark as Number) as Void {
            _m[y * _size + x] = dark;
        }
    }

    // A 256-entry table of set-bit counts, built on first use.
    var popCounts as ByteArray? = null;

    function popTable() as ByteArray {
        var t = popCounts;
        if (t == null) {
            t = new [256]b;
            for (var i = 1; i < 256; i++) {
                t[i] = t[i >> 1] + (i & 1);
            }
            popCounts = t;
        }
        return t;
    }

    // Mask pattern m at column x, row y: true flips a data module.
    function maskBit(m as Number, x as Number, y as Number) as Boolean {
        if (m == 0) {
            return (x + y) % 2 == 0;
        }
        if (m == 1) {
            return y % 2 == 0;
        }
        if (m == 2) {
            return x % 3 == 0;
        }
        if (m == 3) {
            return (x + y) % 3 == 0;
        }
        if (m == 4) {
            return (x / 3 + y / 2) % 2 == 0;
        }
        if (m == 5) {
            return x * y % 2 + x * y % 3 == 0;
        }
        if (m == 6) {
            return (x * y % 2 + x * y % 3) % 2 == 0;
        }
        return ((x + y) % 2 + x * y % 3) % 2 == 0;
    }
}