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. Score all 8 masks with the ISO 18004:2015 penalty rules exactly as
//      segno computes them (format and version areas still light), keep
//      the lowest, then draw the format and version information.
// Each step does a bounded amount of work (one RS block, a few columns or
// rows), 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 looked at per job step: well below the 120,000-bytecode
    // watchdog limit of the smallest targets.
    const MODULES_PER_STEP = 2500;
    // Mask scoring costs more per module: the row pass applies the mask and
    // scores N1-N3, the column pass N1 and N3. Sized for the Forerunner
    // 255S's 120,000 bytecodes per event, where 1,200 row modules tripped
    // the watchdog in the UI flow.
    const ROW_MODULES_PER_STEP = 500;
    const COLUMN_MODULES_PER_STEP = 1000;

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

    function alnumValue(b as Number) as Number {
        if (b >= 0x80) {
            return -1;
        }
        var at = ALPHANUMERIC.find(b.toChar().toString());
        return at == null ? -1 : at;
    }

    // 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.
    function segment(data as ByteArray, v as Number) as Array<Number> {
        var n = data.size();
        var modes = [MODE_BYTE, MODE_ALPHANUMERIC, MODE_NUMERIC];
        var head = [(4 + charCountBits(MODE_BYTE, v)) * 6, (4 + charCountBits(MODE_ALPHANUMERIC, v)) * 6,
            (4 + charCountBits(MODE_NUMERIC, v)) * 6];
        var unit = [48, 33, 20];
        var inf = 0x3FFFFFFF;
        var prev = [head[0], head[1], head[2]];
        // choice[i * 3 + j] = the mode index the segment ending at i in mode j came from.
        var choice = new [n * 3]b;
        for (var i = 0; i < n; i++) {
            var b = data[i];
            var cur = [prev[0] + unit[0], alnumValue(b) >= 0 ? prev[1] + unit[1] : inf, isDigit(b) ? prev[2] + unit[2] : 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] as Number) >= 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] as Number) + 5) / 6 * 6 + (head[j] as Number);
                    if (switched < (cur[j] as Number)) {
                        cur[j] = switched;
                        choice[i * 3 + j] = k;
                    }
                }
            }
            prev = cur;
        }
        // The cheapest final mode, then walk back.
        var best = 0;
        for (var j = 1; j < 3; j++) {
            if ((prev[j] as Number) < (prev[best] as Number)) {
                best = j;
            }
        }
        // Walk back: the state after character i says which mode i was in.
        var charModes = new [n]b;
        var state = best;
        for (var i = n - 1; i >= 0; i--) {
            var charMode = choice[i * 3 + state];
            charModes[i] = charMode;
            state = charMode;
        }
        var segments = [] as Array<Number>;
        var start = 0;
        for (var i = 1; i <= n; i++) {
            if (i == n || charModes[i] != charModes[start]) {
                segments.add(modes[charModes[start]] as Number);
                segments.add(start);
                segments.add(i);
                start = i;
            }
        }
        return segments;
    }

    // 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.
    class BitWriter {
        var bytes as ByteArray = []b;
        var bitCount as Number = 0;

        function initialize() {
        }

        function put(value as Number, count as Number) as Void {
            for (var i = count - 1; i >= 0; i--) {
                if (bitCount % 8 == 0) {
                    bytes.add(0);
                }
                if (((value >> i) & 1) == 1) {
                    var at = bitCount / 8;
                    bytes[at] = bytes[at] | (0x80 >> (bitCount % 8));
                }
                bitCount++;
            }
        }
    }

    // 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;
        private var _masked as ByteArray = []b;
        private var _prevRow as ByteArray = []b;

        // 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.
        function percent() as Number {
            return _phase * 100 / 6;
        }

        // 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) {
                maskStep();
            } else if (_phase == 5) {
                finish();
            }
            return _phase >= 6 || error != null;
        }

        // Phase 0: segments, version, bit stream, blocks.
        private function buildCodewords() as Void {
            if (_data.size() == 0) {
                error = "QR needs some text";
                return;
            }
            var segments = null;
            var v = _version;
            if (v > 0) {
                segments = segment(_data, v);
                if (segmentBits(segments, v) > dataCodewords(v, _ec) * 8) {
                    error = "too long for QR version " + v;
                    return;
                }
            } else {
                for (var c = 0; c < 3 && v == 0; c++) {
                    var lo = [1, 10, 27][c] as Number;
                    var hi = [9, 26, 40][c] as Number;
                    var s = segment(_data, lo);
                    var bits = segmentBits(s, lo);
                    for (var tryV = lo; tryV <= hi; tryV++) {
                        if (bits <= dataCodewords(tryV, _ec) * 8) {
                            v = tryV;
                            segments = s;
                            break;
                        }
                    }
                }
                if (v == 0) {
                    error = "too long for a QR code at this error correction level (" + _data.size() + " bytes, at most "
                        + dataCodewords(40, _ec) + " in byte mode)";
                    return;
                }
            }
            _version = v;
            var capacity = dataCodewords(v, _ec);
            var w = new BitWriter();
            var segs = segments as Array<Number>;
            for (var s = 0; s < segs.size(); s += 3) {
                writeSegment(w, segs[s], segs[s + 1], segs[s + 2]);
            }
            // Terminator, byte alignment, pad codewords.
            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;
            }
            // Split into blocks.
            var i = ((v - 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] = w.bytes[at + k];
                    }
                    at += len;
                    _blocks.add(block);
                }
            }
            _cursor = 0;
            _phase = 1;
        }

        private function writeSegment(w as BitWriter, mode as Number, start as Number, end as Number) as Void {
            var count = end - start;
            w.put(mode, 4);
            w.put(count, charCountBits(mode, _version));
            var d = _data;
            if (mode == MODE_NUMERIC) {
                var i = start;
                while (i < end) {
                    var take = end - i >= 3 ? 3 : end - i;
                    var value = 0;
                    for (var k = 0; k < take; k++) {
                        value = value * 10 + d[i + k] - 0x30;
                    }
                    w.put(value, [0, 4, 7, 10][take] as Number);
                    i += take;
                }
            } else if (mode == MODE_ALPHANUMERIC) {
                var i = start;
                while (i < end) {
                    if (end - 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 (var i = start; i < end; i++) {
                    w.put(d[i], 8);
                }
            }
        }

        // Phase 1: Reed-Solomon codewords, one block per step.
        private function eccStep() as Void {
            var i = ((_version - 1) * 4 + _ec) * 5;
            var n = QrTables.BLOCKS[i] as Number;
            _ecBlocks.add(ReedSolomon.ecc(theField(), _blocks[_cursor], n));
            _cursor++;
            if (_cursor >= _blocks.size()) {
                _phase = 2;
            }
        }

        // Phase 2: interleave codewords; draw the function patterns.
        private function interleaveAndDrawFunctions() as Void {
            var out = []b;
            var longest = 0;
            for (var b = 0; b < _blocks.size(); b++) {
                if (_blocks[b].size() > longest) {
                    longest = _blocks[b].size();
                }
            }
            for (var k = 0; k < longest; k++) {
                for (var b = 0; b < _blocks.size(); b++) {
                    if (k < _blocks[b].size()) {
                        out.add(_blocks[b][k]);
                    }
                }
            }
            var ecLen = _ecBlocks[0].size();
            for (var k = 0; k < ecLen; k++) {
                for (var b = 0; b < _ecBlocks.size(); b++) {
                    out.add(_ecBlocks[b][k]);
                }
            }
            _codewords = out;
            _blocks = [] as Array<Array<Number>>;
            _ecBlocks = [] as Array<Array<Number>>;
            drawFunctionPatterns();
            _cursor = _size - 1; // right column of the current column pair
            _bitIndex = 0;
            _phase = 3;
        }

        private function drawFunctionPatterns() as Void {
            var n = 17 + 4 * _version;
            _size = n;
            _m = new [n * n]b;
            _function = new [n * n]b;
            // Timing patterns.
            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, except where they'd overlap the finders.
            var pos = QrTables.ALIGNMENT[_version - 1] as Array<Number>;
            var count = pos.size();
            for (var a = 0; a < count; a++) {
                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]);
                }
            }
            // 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 = 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;
                _maskIndex = _forceMask >= 0 ? _forceMask : 0;
                _cursor = 0;
                _score = 0;
                _dark = 0;
                _phase = 4;
            }
        }

        // Phase 4: score masks (or apply the forced one). Per mask, two
        // passes: the rows (apply the mask into a copy, then N1, N2, N3 and
        // the dark count), then the columns (N1, N3), each in steps sized to
        // its cost per module.
        private function maskStep() as Void {
            if (_forceMask >= 0) {
                _bestMask = _forceMask;
                _phase = 5;
                return;
            }
            var n = _size;
            var lines = (_maskPass == 0 ? ROW_MODULES_PER_STEP : COLUMN_MODULES_PER_STEP) / n;
            if (lines < 1) {
                lines = 1;
            }
            for (var l = 0; l < lines && _cursor < n; l++) {
                if (_maskPass == 0) {
                    applyMaskRow(_cursor);
                    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));
            if (_score < _bestScore) {
                _bestScore = _score;
                _bestMask = _maskIndex;
            }
            _maskIndex++;
            _maskPass = 0;
            _score = 0;
            _dark = 0;
            if (_maskIndex >= 8) {
                _masked = []b;
                _prevRow = []b;
                _phase = 5;
            }
        }

        private function applyMaskRow(y as Number) as Void {
            var n = _size;
            if (_masked.size() != n * n) {
                _masked = new [n * n]b;
            }
            var m = _maskIndex;
            var row = y * n;
            for (var x = 0; x < n; x++) {
                var at = row + x;
                var bit = _m[at];
                if (_function[at] == 0 && maskBit(m, x, y)) {
                    bit = bit ^ 1;
                }
                _masked[at] = bit;
            }
        }

        private function scoreRow(y as Number) as Void {
            var n = _size;
            var row = _masked.slice(y * n, y * n + n);
            _score += lineScore(row);
            var prev = _prevRow;
            var dark = 0;
            for (var x = 0; x < n; x++) {
                var c = row[x];
                dark += c;
                // N2: a 2x2 block of one colour with the row above.
                if (y > 0 && x > 0 && c == row[x - 1] && c == prev[x] && c == prev[x - 1]) {
                    _score += 3;
                }
            }
            _dark += dark;
            _prevRow = row;
        }

        private function scoreColumn(x as Number) as Void {
            var n = _size;
            var column = new [n]b;
            for (var y = 0; y < n; y++) {
                column[y] = _masked[y * n + x];
            }
            _score += lineScore(column);
        }

        // N1 and N3 of one row or column, in one pass. N1: 3 + (run - 5)
        // for every run of 5 or more equal modules. N3 as segno counts it:
        // 40 for each 1011101 with light modules (up to 4, fewer at the edge)
        // before or after it; after a counted match the search continues
        // behind it, otherwise 4 modules on (found with a rolling 7-bit window).
        private function lineScore(line as ByteArray) as Number {
            var n = line.size();
            var score = 0;
            var run = 1;
            var window = line[0];
            var nextAllowed = 0;
            for (var k = 1; k < n; k++) {
                var c = line[k];
                if (c == line[k - 1]) {
                    run++;
                } else {
                    if (run >= 5) {
                        score += run - 2;
                    }
                    run = 1;
                }
                window = ((window << 1) | c) & 0x7F;
                if (window == 0x5D && k >= 6) {
                    var idx = k - 6;
                    if (idx >= nextAllowed) {
                        var after = idx + 7;
                        if (idx == 0 || idx == n - 7 || allLight(line, idx - 4 < 0 ? 0 : idx - 4, idx)
                                || allLight(line, after, after + 4 > n ? n : after + 4)) {
                            score += 40;
                            nextAllowed = idx + 7;
                        } else {
                            nextAllowed = idx + 4;
                        }
                    }
                }
            }
            if (run >= 5) {
                score += run - 2;
            }
            return score;
        }

        private function allLight(line as ByteArray, from as Number, to as Number) as Boolean {
            for (var i = from; i < to; i++) {
                if (line[i] != 0) {
                    return false;
                }
            }
            return true;
        }

        // Phase 5: apply the chosen mask, draw format and version info.
        private function finish() as Void {
            var n = _size;
            var m = _bestMask;
            for (var y = 0; y < n; y++) {
                for (var x = 0; x < n; x++) {
                    var at = y * n + x;
                    if (_function[at] == 0 && maskBit(m, x, y)) {
                        _m[at] = _m[at] ^ 1;
                    }
                }
            }
            drawFormat(m);
            if (_version >= 7) {
                drawVersion();
            }
            result = new MatrixCode(n, _m, _version, m);
            _function = []b;
            _phase = 6;
        }

        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++) {
                setFunction(8, i, (bits >> i) & 1);
            }
            setFunction(8, 7, (bits >> 6) & 1);
            setFunction(8, 8, (bits >> 7) & 1);
            setFunction(7, 8, (bits >> 8) & 1);
            for (var i = 9; i < 15; i++) {
                setFunction(14 - i, 8, (bits >> i) & 1);
            }
            for (var i = 0; i < 8; i++) {
                setFunction(n - 1 - i, 8, (bits >> i) & 1);
            }
            for (var i = 8; i < 15; i++) {
                setFunction(8, n - 15 + i, (bits >> i) & 1);
            }
            setFunction(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;
                setFunction(a, b, bit);
                setFunction(b, a, bit);
            }
        }
    }

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