diff options
Diffstat (limited to 'source/codes')
| -rw-r--r-- | source/codes/Aztec.mc | 419 | ||||
| -rw-r--r-- | source/codes/Codes.mc | 279 | ||||
| -rw-r--r-- | source/codes/DataMatrix.mc | 298 | ||||
| -rw-r--r-- | source/codes/Pdf417.mc | 286 | ||||
| -rw-r--r-- | source/codes/Qr.mc | 971 | ||||
| -rw-r--r-- | source/codes/ReedSolomon.mc | 205 |
6 files changed, 1767 insertions, 691 deletions
diff --git a/source/codes/Aztec.mc b/source/codes/Aztec.mc index 29b6c95..495abbf 100644 --- a/source/codes/Aztec.mc +++ b/source/codes/Aztec.mc @@ -36,8 +36,17 @@ module Aztec { // Error-correction percentage per option: Low, Medium (default), Quartile, High. const EC_PERCENT = [10, 23, 36, 50]; const QUIET = 2; - const RS_SYMBOLS_PER_STEP = 40; - const PAIRS_PER_STEP = 600; + // Work per step: each was checked in the simulator by running two + // steps per event on the Forerunner 255S (120,000 bytecodes per event) + // with a 1,400-byte payload (32 layers, GF(4096), 830 EC codewords). + const BYTES_PER_STEP = 200; // high-level encoding + const STUFF_BITS_PER_STEP = 1000; // bit stuffing + const FIELD_ENTRIES_PER_STEP = 500; // GF(1024) / GF(4096) tables + const GENERATOR_WORK_PER_STEP = 500; // generator coefficient updates + const ECC_WORK_PER_STEP = 400; // data symbols x EC symbols + const GRID_LINES_PER_STEP = 4; // reference grid + const WORDS_PER_STEP = 50; // codewords into bits + const PAIRS_PER_STEP = 250; // spiral bit pairs // Text modes. const UPPER = 0; @@ -88,57 +97,90 @@ module Aztec { // The data bits of text (see step 1). function encodeBits(data as ByteArray) as ByteArray { - var out = new Bits(); - var mode = UPPER; - var i = 0; - var n = data.size(); - while (i < n) { - var c = classOf(data[i]); - if (c == -1) { - // A space: in the current text mode if it has one. - out.put(1, mode == DIGIT ? 4 : 5); - i++; - continue; - } - if (c == BINARY) { - // Binary Shift needs Upper or Lower; from Digit latch to Upper. - if (mode == DIGIT) { - out.put(14, 4); - mode = UPPER; + var encoder = new BitEncoder(data); + while (!encoder.step(data.size() + 1)) { + } + return encoder.out.bits; + } + + // encodeBits() in steps of about `bytes` input bytes. A Binary Shift + // run's length is written first, then its bytes, across steps. + class BitEncoder { + var out as Bits = new Bits(); + + private var _data as ByteArray; + private var _i as Number = 0; + private var _mode as Number = UPPER; + private var _runEnd as Number = -1; + + function initialize(data as ByteArray) { + _data = data; + } + + // True when every byte is encoded. + function step(bytes as Number) as Boolean { + var data = _data; + var n = data.size(); + var budget = bytes; + while (budget > 0 && _i < n) { + if (_runEnd >= 0) { + var stop = _i + budget < _runEnd ? _i + budget : _runEnd; + budget -= stop - _i; + for (var k = _i; k < stop; k++) { + out.put(data[k], 8); + } + _i = stop; + if (_i >= _runEnd) { + _runEnd = -1; + } + continue; } - var end = i; - while (end < n && end - i < 2078 && classOf(data[end]) == BINARY) { - end++; + budget--; + var c = classOf(data[_i]); + if (c == -1) { + // A space: in the current text mode if it has one. + out.put(1, _mode == DIGIT ? 4 : 5); + _i++; + continue; } - var length = end - i; - out.put(31, 5); - if (length <= 31) { - out.put(length, 5); - } else { - out.put(0, 5); - out.put(length - 31, 11); + if (c == BINARY) { + // Binary Shift needs Upper or Lower; from Digit latch to Upper. + if (_mode == DIGIT) { + out.put(14, 4); + _mode = UPPER; + } + var end = _i; + while (end < n && end - _i < 2078 && classOf(data[end]) == BINARY) { + end++; + } + var length = end - _i; + budget -= length / 4; // the scan + out.put(31, 5); + if (length <= 31) { + out.put(length, 5); + } else { + out.put(0, 5); + out.put(length - 31, 11); + } + _runEnd = end; + continue; } - for (var k = i; k < end; k++) { - out.put(data[k], 8); + if (c != _mode) { + latch(out, _mode, c); + _mode = c; } - i = end; - continue; - } - if (c != mode) { - latch(out, mode, c); - mode = c; - } - var b = data[i]; - if (mode == UPPER) { - out.put(b - 0x41 + 2, 5); - } else if (mode == LOWER) { - out.put(b - 0x61 + 2, 5); - } else { - out.put(b - 0x30 + 2, 4); + var b = data[_i]; + if (_mode == UPPER) { + out.put(b - 0x41 + 2, 5); + } else if (_mode == LOWER) { + out.put(b - 0x61 + 2, 5); + } else { + out.put(b - 0x30 + 2, 4); + } + _i++; } - i++; + return _i >= n && _runEnd < 0; } - return out.bits; } // Latch codes between the text modes (ISO 24778 table 2). @@ -164,41 +206,72 @@ module Aztec { // size - 1 bits are all equal gets the opposite last bit; the final // partial codeword is padded with ones (its last bit 0 if all ones). function stuff(bits as ByteArray, size as Number) as Array<Number> { - var out = [] as Array<Number>; - var value = 0; - var count = 0; - var i = 0; - while (i < bits.size()) { - if (count == size - 1) { - var allZero = value == 0; - var allOne = value == (1 << (size - 1)) - 1; - if (allZero || allOne) { - value = (value << 1) | (allZero ? 1 : 0); + var stuffer = new Stuffer(bits, size); + stuffer.step(bits.size()); + return stuffer.out; + } + + // stuff() in steps of `count` input bits. + class Stuffer { + var out as Array<Number> = [] as Array<Number>; + var size as Number; + + private var _bits as ByteArray; + private var _value as Number = 0; + private var _count as Number = 0; + private var _i as Number = 0; + + function initialize(bits as ByteArray, codewordBits as Number) { + _bits = bits; + size = codewordBits; + } + + // True when every bit is in (and the last codeword padded). + function step(count as Number) as Boolean { + var bits = _bits; + var stop = _i + count < bits.size() ? _i + count : bits.size(); + var value = _value; + var have = _count; + var i = _i; + while (i < stop) { + if (have == size - 1) { + var allZero = value == 0; + var allOne = value == (1 << (size - 1)) - 1; + if (allZero || allOne) { + value = (value << 1) | (allZero ? 1 : 0); + out.add(value); + value = 0; + have = 0; + continue; + } + } + value = (value << 1) | bits[i]; + have++; + i++; + if (have == size) { out.add(value); value = 0; - count = 0; - continue; + have = 0; } } - value = (value << 1) | bits[i]; - count++; - i++; - if (count == size) { - out.add(value); - value = 0; - count = 0; - } - } - if (count > 0) { - for (var k = count; k < size; k++) { - value = (value << 1) | 1; + _value = value; + _count = have; + _i = i; + if (i < bits.size()) { + return false; } - if (value == (1 << size) - 1) { - value = value - 1; + if (have > 0) { + for (var k = have; k < size; k++) { + value = (value << 1) | 1; + } + if (value == (1 << size) - 1) { + value = value - 1; + } + out.add(value); + _count = 0; } - out.add(value); + return true; } - return out; } // Encode synchronously (tests). @@ -217,8 +290,13 @@ module Aztec { private var _phase as Number = 0; private var _words as Array<Number> = [] as Array<Number>; private var _dataCount as Number = 0; - private var _rem as Array<Number> = [] as Array<Number>; private var _field as ReedSolomon.Field? = null; + private var _encoder as ReedSolomon.Encoder? = null; + private var _bitEncoder as BitEncoder? = null; + private var _stuffer as Stuffer? = null; + private var _stuffed as Dictionary<Number, Array<Number>> = {} as Dictionary<Number, Array<Number>>; + private var _configIndex as Number = 0; + private var _gridAt as Number = 0; private var _at as Number = 0; private var _m as ByteArray = []b; private var _result as Codes.Matrix? = null; @@ -237,7 +315,7 @@ module Aztec { } function percent() as Number { - return _phase * 25; + return _phase * 100 / 6; } function matrix() as Codes.Matrix? { @@ -246,65 +324,109 @@ module Aztec { function step(budget as Number) as Boolean { if (_phase == 0) { - prepare(); + encodeStep(); } else if (_phase == 1) { - eccStep(); + chooseStep(); } else if (_phase == 2) { + fieldStep(); + } else if (_phase == 3) { + eccStep(); + } else if (_phase == 4) { + matrixStep(); + } else if (_phase == 5) { placeStep(); } - return _phase >= 3 || error != null; + return _phase >= 6 || error != null; } - private function prepare() as Void { + // Phase 0: the data bits, BYTES_PER_STEP bytes per step. + private function encodeStep() as Void { if (_data.size() == 0) { error = "Aztec needs some text"; return; } - var bits = encodeBits(_data); - for (var i = 0; i < CONFIGS.size() && config.size() == 0; i++) { - var c = CONFIGS[i] as Array<Number>; - var words = stuff(bits, c[4]); + var encoder = _bitEncoder; + if (encoder == null) { + encoder = new BitEncoder(_data); + _bitEncoder = encoder; + } + if (!encoder.step(BYTES_PER_STEP)) { + return; + } + _bits = encoder.out.bits; + _bitEncoder = null; + _phase = 1; + } + + // Phase 1: the first configuration that holds the data. A size the + // bits can't fit even unstuffed is skipped without stuffing; the + // stuffed codewords are computed once per codeword size, in steps. + private function chooseStep() as Void { + while (_configIndex < CONFIGS.size()) { + var c = CONFIGS[_configIndex] as Array<Number>; + var lowerBound = (_bits.size() + c[4] - 1) / c[4]; + if ((lowerBound + 3) * 100 >= c[3] * (100 - _ec)) { + _configIndex++; + continue; + } + var words = _stuffed[c[4]]; + if (words == null) { + var stuffer = _stuffer; + if (stuffer == null || stuffer.size != c[4]) { + stuffer = new Stuffer(_bits, c[4]); + _stuffer = stuffer; + } + if (!stuffer.step(STUFF_BITS_PER_STEP)) { + return; + } + words = stuffer.out; + _stuffed[c[4]] = words; + _stuffer = null; + } if ((words.size() + 3) * 100 < c[3] * (100 - _ec)) { config = c; _words = words; + break; } + _configIndex++; } + _stuffed = {} as Dictionary<Number, Array<Number>>; if (config.size() == 0) { error = "too long for an Aztec code"; return; } _dataCount = _words.size(); - var ecCount = config[3] - _dataCount; _field = new ReedSolomon.Field(polynomial(config[4]), 1 << config[4], 1); - _rem = new [ecCount] as Array<Number>; - for (var k = 0; k < ecCount; k++) { - _rem[k] = 0; - } - _at = 0; - _phase = 1; + _phase = 2; } - private function eccStep() as Void { + // Phase 2: GF(1024) and GF(4096) tables and the generator, in steps. + private function fieldStep() as Void { var f = _field as ReedSolomon.Field; - var n = _rem.size(); - var g = f.generator(n); - var end = _at + RS_SYMBOLS_PER_STEP < _dataCount ? _at + RS_SYMBOLS_PER_STEP : _dataCount; - for (var i = _at; i < end; i++) { - var factor = _words[i] ^ _rem[0]; - for (var k = 0; k < n - 1; k++) { - _rem[k] = _rem[k + 1] ^ f.multiply(g[k], factor); - } - _rem[n - 1] = f.multiply(g[n - 1], factor); + if (!f.grow(FIELD_ENTRIES_PER_STEP)) { + return; + } + var n = config[3] - _dataCount; + if (!f.buildGenerator(n, GENERATOR_WORK_PER_STEP)) { + return; } - _at = end; - if (_at < _dataCount) { + _encoder = new ReedSolomon.Encoder(f, _words, n); + _phase = 3; + } + + // Phase 3: Reed-Solomon, ECC_WORK_PER_STEP data symbols times EC + // symbols per step (at least one data symbol). + private function eccStep() as Void { + var encoder = _encoder as ReedSolomon.Encoder; + var n = encoder.remainder.size(); + if (!encoder.step(ECC_WORK_PER_STEP / n > 0 ? ECC_WORK_PER_STEP / n : 1)) { return; } - _words.addAll(_rem); - _rem = [] as Array<Number>; + _words.addAll(encoder.remainder); + _encoder = null; _field = null; - startMatrix(); - _phase = 2; + _at = -1; + _phase = 4; } private function setDark(x as Number, y as Number, dark as Number) as Void { @@ -312,55 +434,86 @@ module Aztec { _m[y * size + x] = dark; } - // Finder, orientation marks and reference grid; then the spiral state. - private function startMatrix() as Void { + // Phase 4: finder and orientation marks (one step), the reference + // grid of full-range symbols (GRID_LINES_PER_STEP lines per step), + // the codeword bits (WORDS_PER_STEP codewords per step); then the + // spiral state. + private function matrixStep() as Void { var size = config[0]; var compact = config[1] == 1; var c = size / 2; var r = compact ? 5 : 7; - _m = new [size * size]b; - for (var x = -r; x < r; x++) { - for (var y = -r; y < r; y++) { - var d = x.abs() > y.abs() ? x.abs() : y.abs(); - setDark(c + x, c + y, (d + 1) % 2); - } + if (_at == -1) { + drawFinder(size, compact, c, r); + _gridAt = 0; + _at = compact ? -3 : -2; + return; } - setDark(c - r, c - r, 1); - setDark(c - r, c - r + 1, 1); - setDark(c - r + 1, c - r, 1); - setDark(c + r, c - r, 1); - setDark(c + r, c - r + 1, 1); - setDark(c + r, c + r - 1, 1); - if (!compact) { - for (var x = -c; x <= c; x++) { - for (var y = -c; y <= c; y++) { + if (_at == -2) { + // Lines at multiples of 16 from the centre, across and down. + var half = c / 16; + var lines = 2 * half + 1; + for (var n = 0; n < GRID_LINES_PER_STEP && _gridAt < 2 * lines; n++) { + var v = (_gridAt % lines - half) * 16; + var across = _gridAt < lines; + for (var t = -c; t <= c; t++) { + var x = across ? t : v; + var y = across ? v : t; if (x >= -r && x <= r && y >= -r && y <= r) { continue; } - if (x % 16 == 0 || y % 16 == 0) { - setDark(c + x, c + y, ((x + y + 1) % 2 + 2) % 2); - } + setDark(c + x, c + y, ((x + y + 1) % 2 + 2) % 2); } + _gridAt++; } + if (_gridAt >= 2 * lines) { + _at = -3; + } + return; } // All codeword bits, most significant first, then reversed: the // spiral starts from the last bit (as the reference does). var bits = config[4]; - var all = new [_words.size() * bits]b; - var at = all.size() - 1; - for (var i = 0; i < _words.size(); i++) { + if (_bits.size() != _words.size() * bits) { + _bits = new [_words.size() * bits]b; + _gridAt = 0; + } + var all = _bits; + var stop = _gridAt + WORDS_PER_STEP < _words.size() ? _gridAt + WORDS_PER_STEP : _words.size(); + for (var i = _gridAt; i < stop; i++) { + var at = all.size() - 1 - i * bits; for (var k = bits - 1; k >= 0; k--) { all[at] = (_words[i] >> k) & 1; at--; } } - _bits = all; + _gridAt = stop; + if (_gridAt < _words.size()) { + return; + } _at = 0; _num = 2; _side = 0; _layer = 0; _x = c - r; _y = c - r - 1; + _phase = 5; + } + + private function drawFinder(size as Number, compact as Boolean, c as Number, r as Number) as Void { + _m = new [size * size]b; + for (var x = -r; x < r; x++) { + for (var y = -r; y < r; y++) { + var d = x.abs() > y.abs() ? x.abs() : y.abs(); + setDark(c + x, c + y, (d + 1) % 2); + } + } + setDark(c - r, c - r, 1); + setDark(c - r, c - r + 1, 1); + setDark(c - r + 1, c - r, 1); + setDark(c + r, c - r, 1); + setDark(c + r, c - r + 1, 1); + setDark(c + r, c + r - 1, 1); } // The data spiral, PAIRS_PER_STEP bit pairs per step (a port of @@ -460,7 +613,7 @@ module Aztec { addModeMessage(); _words = [] as Array<Number>; _result = new Codes.Matrix(size, size, QUIET, _m); - _phase = 3; + _phase = 6; } // True on a reference-grid line (Python's % 16 == 0 for any sign). diff --git a/source/codes/Codes.mc b/source/codes/Codes.mc index f157b37..247acfa 100644 --- a/source/codes/Codes.mc +++ b/source/codes/Codes.mc @@ -76,55 +76,262 @@ module Codes { return height * rowHeight; } - // Compact form for the encrypted cache: width, height, quiet zone, - // row height (one byte each), then the modules packed 8 per byte - // (eight per loop round: this runs in one event, under the watchdog). + // The cache form (Packed), in one go: tests and small codes. Jobs + // use Packer. function toBytes() as ByteArray { - var m = modules; + var packer = new Packer(self); + Jobs.runToCompletion(packer, 1); + return packer.result; + } + + // A matrix from its cache form, unpacked in one go (tests); the app + // draws from Packed through RunFinder instead. + static function fromBytes(data as ByteArray) as Matrix? { + var packed = Packed.parse(data); + if (packed == null) { + return null; + } + var n = packed.width * packed.height; + var bits = new [n]b; + for (var i = 0; i < n; i++) { + bits[i] = packed.moduleAt(i); + } + var matrix = new Matrix(packed.width, packed.height, packed.quiet, bits); + matrix.rowHeight = packed.rowHeight; + return matrix; + } + } + + // A matrix packed 8 modules per byte, as cached (sealed) in the vault: + // FORMAT (2) | width (2 bytes) | height (2 bytes) | quiet | rowHeight + // | modules, row-major, most significant bit first + // Version 0.7 cached one byte of width, too few for wide PDF417 + // symbols; such a cache doesn't parse, and the code is encoded again. + class Packed { + static const FORMAT = 2; + static const HEADER = 7; + + var width as Number; + var height as Number; + var quiet as Number; + var rowHeight as Number; + var bytes as ByteArray; + + function initialize(data as ByteArray) { + bytes = data; + width = (data[1] << 8) | data[2]; + height = (data[3] << 8) | data[4]; + quiet = data[5]; + rowHeight = data[6]; + } + + // The cache bytes as a Packed, or null when they are not format 2 or + // the size doesn't match. + static function parse(data as ByteArray?) as Packed? { + if (data == null || data.size() < HEADER || data[0] != FORMAT) { + return null; + } + var p = new Packed(data); + var n = p.width * p.height; + if (p.width == 0 || p.height == 0 || p.rowHeight == 0 || data.size() != HEADER + (n + 7) / 8) { + return null; + } + return p; + } + + function drawnHeight() as Number { + return height * rowHeight; + } + + // Module i (row-major), 1 = dark. + function moduleAt(i as Number) as Number { + return (bytes[HEADER + (i >> 3)] >> (7 - (i & 7))) & 1; + } + } + + // Matrix -> Packed bytes, BYTES_PER_STEP output bytes (8 modules each) + // per step. + class Packer extends Jobs.Job { + static const BYTES_PER_STEP = 300; + + var result as ByteArray = []b; + + private var _matrix as Matrix; + private var _i as Number = 0; + + function initialize(matrix as Matrix) { + Job.initialize(); + _matrix = matrix; + var w = matrix.width; + var h = matrix.height; + result = new [Packed.HEADER + (w * h + 7) / 8]b; + result[0] = Packed.FORMAT; + result[1] = (w >> 8) & 0xFF; + result[2] = w & 0xFF; + result[3] = (h >> 8) & 0xFF; + result[4] = h & 0xFF; + result[5] = matrix.quiet; + result[6] = matrix.rowHeight; + } + + function step(budget as Number) as Boolean { + var m = _matrix.modules; var n = m.size(); var full = n / 8; - var out = new [4 + (n + 7) / 8]b; - out[0] = width; - out[1] = height; - out[2] = quiet; - out[3] = rowHeight; - for (var i = 0; i < full; i++) { + var out = result; + var stop = _i + BYTES_PER_STEP < full ? _i + BYTES_PER_STEP : full; + for (var i = _i; i < stop; i++) { var k = i * 8; - out[4 + i] = (m[k] << 7) | (m[k + 1] << 6) | (m[k + 2] << 5) | (m[k + 3] << 4) + out[Packed.HEADER + i] = (m[k] << 7) | (m[k + 1] << 6) | (m[k + 2] << 5) | (m[k + 3] << 4) | (m[k + 4] << 3) | (m[k + 5] << 2) | (m[k + 6] << 1) | m[k + 7]; } + _i = stop; + if (_i < full) { + return false; + } for (var k = full * 8; k < n; k++) { - out[4 + full] = out[4 + full] | (m[k] << (7 - k % 8)); + out[Packed.HEADER + full] = out[Packed.HEADER + full] | (m[k] << (7 - k % 8)); } - return out; + return true; } + } - static function fromBytes(data as ByteArray) as Matrix? { - if (data.size() < 4) { - return null; + // A code as the dark runs of each stored row, ready to draw with one + // fillRectangle per run (drawing module by module in onUpdate would be + // too much for the watchdog with large codes). Each run is + // (row << 20) | (first column << 10) | length. + class Runs { + var width as Number; + var height as Number; + var quiet as Number; + var rowHeight as Number; + var runs as Array<Number> = [] as Array<Number>; + + function initialize(packed as Packed) { + width = packed.width; + height = packed.height; + quiet = packed.quiet; + rowHeight = packed.rowHeight; + } + + function drawnHeight() as Number { + return height * rowHeight; + } + } + + // Packed -> Runs, about MODULES_PER_STEP modules (whole rows) per step; + // all-light and all-dark bytes are taken eight modules at a time. + class RunFinder extends Jobs.Job { + static const MODULES_PER_STEP = 800; + + var result as Runs; + + private var _packed as Packed; + private var _row as Number = 0; + + function initialize(packed as Packed) { + Job.initialize(); + _packed = packed; + result = new Runs(packed); + } + + function step(budget as Number) as Boolean { + var p = _packed; + var w = p.width; + var bytes = p.bytes; + var runs = result.runs; + var rows = MODULES_PER_STEP / w > 0 ? MODULES_PER_STEP / w : 1; + var last = _row + rows < p.height ? _row + rows : p.height; + for (var y = _row; y < last; y++) { + var bit = y * w; + var end = bit + w; + while (bit < end) { + var b = bytes[Packed.HEADER + (bit >> 3)]; + if ((bit & 7) == 0 && bit + 8 <= end && b == 0) { + bit += 8; + continue; + } + if (((b >> (7 - (bit & 7))) & 1) == 0) { + bit++; + continue; + } + var start = bit; + while (bit < end) { + var c = bytes[Packed.HEADER + (bit >> 3)]; + if ((bit & 7) == 0 && bit + 8 <= end && c == 0xFF) { + bit += 8; + } else if (((c >> (7 - (bit & 7))) & 1) == 1) { + bit++; + } else { + break; + } + } + runs.add((y << 20) | ((start - y * w) << 10) | (bit - start)); + } } - var w = data[0]; - var h = data[1]; - var n = w * h; - if (w == 0 || h == 0 || data[3] == 0 || data.size() != 4 + (n + 7) / 8) { - return null; + _row = last; + return _row >= p.height; + } + } + + // A 2D code from the cache or a fresh encoding to Runs: encode (unless + // cached), pack (`cache` then holds the bytes to store), find the runs. + class DisplayJob extends Jobs.Job { + var error as String? = null; + var cache as ByteArray? = null; + var runs as Runs? = null; + + private var _encoder as MatrixJob?; + private var _packer as Packer? = null; + private var _finder as RunFinder? = null; + + // Either an encoder (fresh) or the cached bytes. + function initialize(encoder as MatrixJob?, packed as Packed?) { + Job.initialize(); + _encoder = encoder; + if (packed != null) { + _finder = new RunFinder(packed); } - var bits = new [(n + 7) / 8 * 8]b; - for (var i = 0; i < (n + 7) / 8; i++) { - var v = data[4 + i]; - var k = i * 8; - bits[k] = (v >> 7) & 1; - bits[k + 1] = (v >> 6) & 1; - bits[k + 2] = (v >> 5) & 1; - bits[k + 3] = (v >> 4) & 1; - bits[k + 4] = (v >> 3) & 1; - bits[k + 5] = (v >> 2) & 1; - bits[k + 6] = (v >> 1) & 1; - bits[k + 7] = v & 1; + } + + // Progress 0-100: encoding is most of it. + function percent() as Number { + var e = _encoder; + return e != null ? e.percent() * 9 / 10 : 90; + } + + function step(budget as Number) as Boolean { + var finder = _finder; + if (finder != null) { + if (!finder.step(budget)) { + return false; + } + runs = finder.result; + _finder = null; + return true; } - var matrix = new Matrix(w, h, data[2], bits.size() == n ? bits : bits.slice(0, n)); - matrix.rowHeight = data[3]; - return matrix; + var packer = _packer; + if (packer != null) { + if (packer.step(budget)) { + cache = packer.result; + _packer = null; + _finder = new RunFinder(new Packed(packer.result)); + } + return false; + } + var encoder = _encoder as MatrixJob; + if (!encoder.step(budget)) { + return false; + } + var matrix = encoder.matrix(); + var err = encoder.error; + if (err != null || matrix == null) { + error = err != null ? err : "could not encode"; + return true; + } + _packer = new Packer(matrix); + _encoder = null; + return false; } } diff --git a/source/codes/DataMatrix.mc b/source/codes/DataMatrix.mc index 45d5ff0..76a29e8 100644 --- a/source/codes/DataMatrix.mc +++ b/source/codes/DataMatrix.mc @@ -9,8 +9,8 @@ // 2. Pick the smallest square size, pad (129, then randomised pads). // 3. Reed-Solomon over GF(256) (x^8+x^5+x^3+x^2+1, roots a^1..a^n), // per interleaved block, in chunks. -// 4. Place the codewords with the standard "utah" placement, a few -// diagonal sweeps per step, then add the finder and clock patterns of +// 4. Place the codewords with the standard "utah" placement, one +// diagonal pass per step, then add the finder and clock patterns of // every data region. // Verified against ppf.datamatrix (ASCII mode) and by decoding with zxing-cpp. @@ -32,9 +32,14 @@ module DataMatrix { const PAD = 129; const UPPER_SHIFT = 235; const BASE256_LATCH = 231; - // Work per step, sized for the 120,000-bytecode watchdog. - const RS_SYMBOLS_PER_STEP = 40; - const SWEEPS_PER_STEP = 6; + // The placement grid's mark for the fixed dark corner modules. + const FIXED_DARK = 0xFFFF; + // Work per step: each was checked in the simulator by running two + // steps per event on the Forerunner 255S (120,000 bytecodes per event), + // with a 1,500-byte payload (144 x 144 modules). + const BYTES_PER_STEP = 250; // codeword encodation + const ECC_WORK_PER_STEP = 400; // data symbols x EC symbols + const BUILD_MODULES_PER_STEP = 300; // symbol modules var field as ReedSolomon.Field? = null; @@ -49,41 +54,83 @@ module DataMatrix { // Codewords for data: ASCII, or Base256 when cheaper (non-ASCII text). function codewords(data as ByteArray) as Array<Number> { - var ascii = [] as Array<Number>; - var highBytes = 0; - var i = 0; - while (i < data.size()) { - var b = data[i]; - if (b >= 0x30 && b <= 0x39 && i + 1 < data.size() && data[i + 1] >= 0x30 && data[i + 1] <= 0x39) { - ascii.add(130 + (b - 0x30) * 10 + data[i + 1] - 0x30); - i += 2; - continue; - } - if (b >= 128) { - ascii.add(UPPER_SHIFT); - ascii.add(b - 128 + 1); - highBytes++; - } else { - ascii.add(b + 1); - } - i++; + var builder = new CodewordBuilder(data); + while (!builder.step(data.size() + 1)) { } - var n = data.size(); - var base256Cost = 1 + (n <= 249 ? 1 : 2) + n; - if (highBytes == 0 || ascii.size() <= base256Cost) { - return ascii; - } - var out = [BASE256_LATCH] as Array<Number>; - if (n <= 249) { - out.add(randomise255(n, 2)); - } else { - out.add(randomise255(n / 250 + 249, 2)); - out.add(randomise255(n % 250, 3)); + return builder.result; + } + + // codewords() in bounded steps: the ASCII encodation, then (when + // Base256 is cheaper) the Base256 one, `bytes` input bytes per step. + class CodewordBuilder { + var result as Array<Number> = [] as Array<Number>; + + private var _data as ByteArray; + private var _ascii as Array<Number> = [] as Array<Number>; + private var _highBytes as Number = 0; + private var _i as Number = 0; + private var _base256 as Array<Number>? = null; + private var _k as Number = 0; + + function initialize(data as ByteArray) { + _data = data; } - for (var k = 0; k < n; k++) { - out.add(randomise255(data[k], out.size() + 1)); + + // True when result is ready. + function step(bytes as Number) as Boolean { + var data = _data; + var n = data.size(); + if (_i < n) { + var stop = _i + bytes < n ? _i + bytes : n; + var i = _i; + var ascii = _ascii; + while (i < stop) { + var b = data[i]; + if (b >= 0x30 && b <= 0x39 && i + 1 < n && data[i + 1] >= 0x30 && data[i + 1] <= 0x39) { + ascii.add(130 + (b - 0x30) * 10 + data[i + 1] - 0x30); + i += 2; + continue; + } + if (b >= 128) { + ascii.add(UPPER_SHIFT); + ascii.add(b - 128 + 1); + _highBytes++; + } else { + ascii.add(b + 1); + } + i++; + } + _i = i; + return false; + } + var out = _base256; + if (out == null) { + var base256Cost = 1 + (n <= 249 ? 1 : 2) + n; + if (_highBytes == 0 || _ascii.size() <= base256Cost) { + result = _ascii; + return true; + } + out = [BASE256_LATCH] as Array<Number>; + if (n <= 249) { + out.add(randomise255(n, 2)); + } else { + out.add(randomise255(n / 250 + 249, 2)); + out.add(randomise255(n % 250, 3)); + } + _base256 = out; + _ascii = [] as Array<Number>; + } + var stop = _k + bytes < n ? _k + bytes : n; + for (var k = _k; k < stop; k++) { + out.add(randomise255(data[k], out.size() + 1)); + } + _k = stop; + if (_k < n) { + return false; + } + result = out; + return true; } - return out; } // The 255-state randomising of Base256 values at 1-based position pos. @@ -113,15 +160,21 @@ module DataMatrix { private var _size as Array<Number> = [] as Array<Number>; private var _cw as Array<Number> = [] as Array<Number>; private var _blocks as Array<Array<Number>> = [] as Array<Array<Number>>; - private var _rem as Array<Number> = [] as Array<Number>; + private var _builder as CodewordBuilder? = null; + private var _encoder as ReedSolomon.Encoder? = null; private var _block as Number = 0; - private var _at as Number = 0; + private var _buildRow as Number = 0; + private var _modules as ByteArray = []b; private var _ecTotal as Array<Number> = [] as Array<Number>; // Placement state. private var _nrow as Number = 0; private var _ncol as Number = 0; - private var _place as Array<Number> = [] as Array<Number>; // 10 * codeword + bit, 0 = empty, -1 = fixed dark + // Placement grid, two bytes per module (big-endian): 10 * codeword + + // bit, 0 = empty, FIXED_DARK. Bytes, not Numbers: a 132 x 132 grid of + // Numbers took about 90 KB of the Forerunner 255S's 512 KB. + private var _place as ByteArray = []b; private var _chr as Number = 1; + private var _downPass as Boolean = false; private var _row as Number = 4; private var _col as Number = 0; private var _result as Codes.Matrix? = null; @@ -132,7 +185,7 @@ module DataMatrix { } function percent() as Number { - return _phase * 25; + return _phase * 20; } function matrix() as Codes.Matrix? { @@ -145,20 +198,31 @@ module DataMatrix { } else if (_phase == 1) { eccStep(); } else if (_phase == 2) { - placeStep(); + startPlacement(); } else if (_phase == 3) { + placeStep(); + } else if (_phase == 4) { build(); } - return _phase >= 4 || error != null; + return _phase >= 5 || error != null; } - // Codewords, size, padding, blocks. + // Codewords (BYTES_PER_STEP per step), then size, padding, blocks. private function prepare() as Void { if (_data.size() == 0) { error = "Data Matrix needs some text"; return; } - var cw = codewords(_data); + var builder = _builder; + if (builder == null) { + builder = new CodewordBuilder(_data); + _builder = builder; + } + if (!builder.step(BYTES_PER_STEP)) { + return; + } + _builder = null; + var cw = builder.result; for (var i = 0; i < SIZES.size() && _size.size() == 0; i++) { var s = SIZES[i] as Array<Number>; if (cw.size() <= s[3]) { @@ -186,63 +250,68 @@ module DataMatrix { _blocks.add(block); } _ecTotal = new [_size[4]] as Array<Number>; - startBlock(); _phase = 1; } - private function startBlock() as Void { - var n = _size[4] / _size[5]; - _rem = new [n] as Array<Number>; - for (var k = 0; k < n; k++) { - _rem[k] = 0; - } - _at = 0; - } - - // Reed-Solomon, RS_SYMBOLS_PER_STEP data symbols per step. + // Reed-Solomon (the shared encoder: the same remainder as ISO 16022 + // annex E), ECC_WORK_PER_STEP data symbols times EC symbols per step. private function eccStep() as Void { - var f = theField(); - var data = _blocks[_block]; - var n = _rem.size(); - var g = f.generator(n); - var end = _at + RS_SYMBOLS_PER_STEP < data.size() ? _at + RS_SYMBOLS_PER_STEP : data.size(); - for (var i = _at; i < end; i++) { - var factor = data[i] ^ _rem[0]; - for (var k = 0; k < n - 1; k++) { - _rem[k] = _rem[k + 1] ^ f.multiply(g[k], factor); + var blocks = _size[5]; + var n = _size[4] / blocks; + var encoder = _encoder; + if (encoder == null) { + var fresh = !theField().hasGenerator(n); + encoder = new ReedSolomon.Encoder(theField(), _blocks[_block], n); + _encoder = encoder; + if (fresh) { + return; // the generator took this step } - _rem[n - 1] = f.multiply(g[n - 1], factor); } - _at = end; - if (_at < data.size()) { + if (!encoder.step(ECC_WORK_PER_STEP / n > 0 ? ECC_WORK_PER_STEP / n : 1)) { return; } + _encoder = null; // Interleave this block's EC codewords. - var blocks = _size[5]; for (var k = 0; k < n; k++) { - _ecTotal[_block + k * blocks] = _rem[k]; + _ecTotal[_block + k * blocks] = encoder.remainder[k]; } _block++; if (_block < blocks) { - startBlock(); return; } _cw.addAll(_ecTotal); _blocks = [] as Array<Array<Number>>; + _phase = 2; + } + + // The empty placement grid (a new ByteArray is zeroed natively). + private function startPlacement() as Void { _nrow = _size[1] * _size[2]; _ncol = _nrow; - _place = new [_nrow * _ncol] as Array<Number>; - for (var k = 0; k < _place.size(); k++) { - _place[k] = 0; - } - _phase = 2; + _place = new [2 * _nrow * _ncol]b; + _phase = 3; + } + + private function placeAt(i as Number) as Number { + return (_place[2 * i] << 8) | _place[2 * i + 1]; } - // ISO 16022 annex F placement, SWEEPS_PER_STEP diagonal sweeps per step. + private function setPlace(i as Number, v as Number) as Void { + _place[2 * i] = (v >> 8) & 0xFF; + _place[2 * i + 1] = v & 0xFF; + } + + // ISO 16022 annex F placement, one diagonal pass per step: each + // sweep is a pass up and to the right (after the corner cases), then + // one down and to the left (_downPass). private function placeStep() as Void { var nrow = _nrow; var ncol = _ncol; - for (var s = 0; s < SWEEPS_PER_STEP && (_row < nrow || _col < ncol); s++) { + if (!_downPass) { + if (_row >= nrow && _col >= ncol) { + finishPlacement(); + return; + } if (_row == nrow && _col == 0) { corner1(); } @@ -256,7 +325,8 @@ module DataMatrix { corner4(); } do { - if (_row < nrow && _col >= 0 && _place[_row * ncol + _col] == 0) { + var at = 2 * (_row * ncol + _col); + if (_row < nrow && _col >= 0 && _place[at] == 0 && _place[at + 1] == 0) { utah(_row, _col); } _row -= 2; @@ -264,24 +334,33 @@ module DataMatrix { } while (_row >= 0 && _col < ncol); _row += 1; _col += 3; - do { - if (_row >= 0 && _col < ncol && _place[_row * ncol + _col] == 0) { - utah(_row, _col); - } - _row += 2; - _col -= 2; - } while (_row < nrow && _col >= 0); - _row += 3; - _col += 1; - } - if (_row < nrow || _col < ncol) { + _downPass = true; return; } - if (_place[nrow * ncol - 1] == 0) { - _place[nrow * ncol - 1] = -1; - _place[nrow * ncol - ncol - 2] = -1; + do { + var at = 2 * (_row * ncol + _col); + if (_row >= 0 && _col < ncol && _place[at] == 0 && _place[at + 1] == 0) { + utah(_row, _col); + } + _row += 2; + _col -= 2; + } while (_row < nrow && _col >= 0); + _row += 3; + _col += 1; + _downPass = false; + if (_row >= nrow && _col >= ncol) { + finishPlacement(); } - _phase = 3; + } + + // The fixed corner modules when the grid leaves them empty. + private function finishPlacement() as Void { + var n = _nrow * _ncol; + if (placeAt(n - 1) == 0) { + setPlace(n - 1, FIXED_DARK); + setPlace(n - _ncol - 2, FIXED_DARK); + } + _phase = 4; } private function setModule(row as Number, col as Number, bit as Number) as Void { @@ -295,7 +374,10 @@ module DataMatrix { c += _ncol; r += 4 - ((_ncol + 4) % 8); } - _place[r * _ncol + c] = 10 * _chr + bit; + var v = 10 * _chr + bit; + var at = 2 * (r * _ncol + c); + _place[at] = v >> 8; + _place[at + 1] = v & 0xFF; } private function utah(row as Number, col as Number) as Void { @@ -359,13 +441,19 @@ module DataMatrix { } // The symbol: data modules mapped into the regions, plus each - // region's finder (solid left and bottom) and clock (top, right). + // region's finder (solid left and bottom) and clock (top, right); + // BUILD_MODULES_PER_STEP modules (whole rows) per step. private function build() as Void { var size = _size[0]; var region = _size[1]; var box = region + 2; - var m = new [size * size]b; - for (var y = 0; y < size; y++) { + if (_modules.size() == 0) { + _modules = new [size * size]b; + } + var m = _modules; + var rows = BUILD_MODULES_PER_STEP / size > 0 ? BUILD_MODULES_PER_STEP / size : 1; + var last = _buildRow + rows < size ? _buildRow + rows : size; + for (var y = _buildRow; y < last; y++) { var ry = y % box; for (var x = 0; x < size; x++) { var rx = x % box; @@ -379,8 +467,9 @@ module DataMatrix { } else { var mr = (y / box) * region + ry - 1; var mc = (x / box) * region + rx - 1; - var v = _place[mr * _ncol + mc]; - if (v == -1) { + var at = 2 * (mr * _ncol + mc); + var v = (_place[at] << 8) | _place[at + 1]; + if (v == FIXED_DARK) { dark = 1; } else if (v > 0) { var cw = _cw[v / 10 - 1]; @@ -390,9 +479,14 @@ module DataMatrix { m[y * size + x] = dark; } } - _place = [] as Array<Number>; + _buildRow = last; + if (_buildRow < size) { + return; + } + _place = []b; + _modules = []b; _result = new Codes.Matrix(size, size, QUIET, m); - _phase = 4; + _phase = 5; } } } diff --git a/source/codes/Pdf417.mc b/source/codes/Pdf417.mc index b17b5df..a294aa7 100644 --- a/source/codes/Pdf417.mc +++ b/source/codes/Pdf417.mc @@ -53,7 +53,12 @@ module Pdf417 { [[29], [29, 27], [29, 28], []] ]; const PREFERENCE = [1, 0, 2, 3]; // lower, upper, mixed, punctuation - const EC_STEP_WORDS = 20; + // 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 { @@ -62,61 +67,179 @@ module Pdf417 { // Data codewords (without length descriptor and padding). function dataCodewords(data as ByteArray, text as Array<Array<Number>>) as Array<Number> { - // Runs of one kind: [kind, start, end) triples. - var runs = [] as Array<Number>; - for (var i = 0; i < data.size(); i++) { - var kind = kindOf(data[i], text); - var n = runs.size(); - if (n > 0 && runs[n - 3] == kind) { - runs[n - 1] = i + 1; + 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 { - runs.add(kind); - runs.add(i); - runs.add(i + 1); + compact(budget); } + return _stage == 3; } - // Short digit runs next to text become text. - for (var r = 0; r < runs.size(); r += 3) { - if (runs[r] == 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))) { - runs[r] = -KIND_TEXT - 10; // marked; resolved below so later checks see the original kinds + + 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; } } - for (var r = 0; r < runs.size(); r += 3) { - if (runs[r] == -KIND_TEXT - 10) { - runs[r] = KIND_TEXT; + + // 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; } } - // Merge equal neighbours. - var merged = [] as Array<Number>; - for (var r = 0; r < runs.size(); r += 3) { - var n = merged.size(); - if (n > 0 && merged[n - 3] == runs[r]) { - merged[n - 1] = runs[r + 2]; - } else { - merged.add(runs[r]); - merged.add(runs[r + 1]); - merged.add(runs[r + 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); } } - var out = [] as Array<Number>; - for (var r = 0; r < merged.size(); r += 3) { - var kind = merged[r]; - var start = merged[r + 1]; - var end = merged[r + 2]; - if (r > 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))); - } - if (kind == KIND_TEXT) { - compactText(data, start, end, text, out); - } else if (kind == KIND_NUMERIC) { - compactNumeric(data, start, end, out); + + private function textValue(v as Number) as Void { + if (_half < 0) { + _half = v; } else { - compactBytes(data, start, end, out); + out.add(30 * _half + v); + _half = -1; } } - return out; } function kindOf(b as Number, text as Array<Array<Number>>) as Number { @@ -133,30 +256,6 @@ module Pdf417 { return KIND_BYTE; } - function compactText(data as ByteArray, start as Number, end as Number, text as Array<Array<Number>>, out as Array<Number>) as Void { - var interim = [] as Array<Number>; - var submode = UPPER; - for (var i = start; i < end; 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; - } - } - interim.addAll((SWITCHES[submode] as Array)[next] as Array<Number>); - submode = next; - } - interim.add(text[submode][c] as Number); - } - for (var i = 0; i < interim.size(); i += 2) { - out.add(30 * interim[i] + (i + 1 < interim.size() ? interim[i + 1] : 29)); - } - } - // 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) { @@ -261,6 +360,8 @@ module Pdf417 { 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; @@ -301,12 +402,34 @@ module Pdf417 { 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 = dataCodewords(_data, table(Rez.JsonData.Pdf417Text) as Array<Array<Number>>); + 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()); } @@ -329,6 +452,7 @@ module Pdf417 { } _words = [length] as Array<Number>; _words.addAll(data); + _dataWords = null; for (var i = 0; i < padding; i++) { _words.add(PAD); } @@ -343,6 +467,22 @@ module Pdf417 { _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--) { @@ -362,11 +502,13 @@ module Pdf417 { return false; } - // Reed-Solomon mod 929 (pdf417gen's form), EC_STEP_WORDS words per step. + // 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 end = _at + EC_STEP_WORDS < _words.size() ? _at + EC_STEP_WORDS : _words.size(); + 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--) { @@ -392,7 +534,7 @@ module Pdf417 { // 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 < 4 && _at < rows; k++) { + 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); diff --git a/source/codes/Qr.mc b/source/codes/Qr.mc index 1fa69da..1fac051 100644 --- a/source/codes/Qr.mc +++ b/source/codes/Qr.mc @@ -9,11 +9,14 @@ // 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. +// 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), because version 40 is far beyond one event's watchdog budget. +// 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; @@ -26,15 +29,31 @@ module Qr { 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; + // 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; + // 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; @@ -70,12 +89,20 @@ module Qr { 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 { - if (b >= 0x80) { - return -1; + 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; } - var at = ALPHANUMERIC.find(b.toChar().toString()); - return at == null ? -1 : at; + return b < 0x80 ? t[b] - 1 : -1; } // Optimal segmentation for a version class: [mode, start, end) triples @@ -84,64 +111,133 @@ module Qr { // 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; + // 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; + } } - // 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; + } + 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; } - 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; + + // 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; } } - // 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; + + // 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; } } - return segments; } // Bits needed for segments at version v. @@ -162,25 +258,28 @@ module Qr { return total; } - // A growing bit stream packed into codewords. + // 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 { - 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++; + _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); } } @@ -230,8 +329,32 @@ module Qr { 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; + // 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. @@ -245,7 +368,7 @@ module Qr { // Progress 0-100 for the UI. function percent() as Number { - return _phase * 100 / 6; + return _phase * 100 / 7; } // The code as a generic matrix with QR's 4-module quiet zone. @@ -264,55 +387,146 @@ module Qr { } else if (_phase == 3) { placeStep(); } else if (_phase == 4) { - maskStep(); + packStep(); } else if (_phase == 5) { - finish(); + maskStep(); + } else if (_phase == 6) { + applyStep(); } - return _phase >= 6 || error != null; + return _phase >= 7 || error != null; } - // Phase 0: segments, version, bit stream, blocks. + // 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 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; + 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 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; - } + for (var v = lowest[_class]; v <= highest[_class] && _version == 0; v++) { + if (bits <= dataCodewords(v, _ec) * 8) { + _version = v; } } - 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)"; + 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; } } - _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]); + _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) { @@ -323,8 +537,14 @@ module Qr { w.bytes.add(pad); pad = pad == 0xEC ? 0x11 : 0xEC; } - // Split into blocks. - var i = ((v - 1) * 4 + _ec) * 5; + _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++) { @@ -333,7 +553,7 @@ module Qr { 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]; + block[k] = bytes[at + k]; } at += len; _blocks.add(block); @@ -343,88 +563,89 @@ module Qr { _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, 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 } } - } - - // 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)); + 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 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]); + // 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++; } - 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]); - } + if (_cursor < longest + ecLen) { + return; } - _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; + _cursor = -1; } - private function drawFunctionPatterns() as Void { + // 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; - // 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); @@ -433,17 +654,21 @@ module Qr { 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>; + } + + // 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 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]); + 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). @@ -503,7 +728,7 @@ module Qr { private function placeStep() as Void { var n = _size; var totalBits = _codewords.size() * 8; - var budget = MODULES_PER_STEP; + var budget = PLACE_MODULES_PER_STEP; while (_cursor >= 1 && budget > 0) { var right = _cursor == 6 ? 5 : _cursor; var upward = ((right + 1) & 2) == 0; @@ -523,32 +748,167 @@ module Qr { } if (_cursor < 1) { _codewords = []b; - _maskIndex = _forceMask >= 0 ? _forceMask : 0; _cursor = 0; - _score = 0; - _dark = 0; + startPacking(); _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. + // ---- 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 = 5; + _phase = 6; + return; + } + if (_patternMask != _maskIndex) { + buildPatterns(_maskIndex); return; } var n = _size; - var lines = (_maskPass == 0 ? ROW_MODULES_PER_STEP : COLUMN_MODULES_PER_STEP) / n; + 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) { - applyMaskRow(_cursor); scoreRow(_cursor); } else { scoreColumn(_cursor); @@ -567,6 +927,7 @@ module Qr { 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; @@ -576,126 +937,135 @@ module Qr { _score = 0; _dark = 0; if (_maskIndex >= 8) { - _masked = []b; - _prevRow = []b; - _phase = 5; + _phase = 6; } } - 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; + // 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 n = _size; - var row = _masked.slice(y * n, y * n + n); - _score += lineScore(row); - var prev = _prevRow; + 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 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; - } + for (var k = 0; k < _words; k++) { + var c = cur[k] as Number; + dark += pop[c & 0xFF] + pop[c >> 8]; } _dark += dark; - _prevRow = row; + 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 { - var n = _size; - var column = new [n]b; - for (var y = 0; y < n; y++) { - column[y] = _masked[y * n + x]; - } - _score += lineScore(column); + maskLine(_cols, _colFree, _columnPattern[x % 12], x, _cur); + _score += lineScore(_cur); } - // 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(); + // 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 run = 1; - var window = line[0]; + var carry = 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; + 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]); } - 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; - } + 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; } } } - 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; - } + // 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; } - 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++) { + 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 at = y * n + x; - if (_function[at] == 0 && maskBit(m, x, y)) { - _m[at] = _m[at] ^ 1; - } + var p = x + PAD; + _m[row + x] = ((_cur[p >> 4] as Number) >> (p & 15)) & 1; } + _cursor++; } - drawFormat(m); + 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, m); - _function = []b; - _phase = 6; + result = new MatrixCode(n, _m, _version, _bestMask); + _phase = 7; } private function drawFormat(mask as Number) as Void { @@ -707,21 +1077,21 @@ module Qr { var bits = ((data << 10) | rem) ^ 0x5412; var n = _size; for (var i = 0; i <= 5; i++) { - setFunction(8, i, (bits >> i) & 1); + setModule(8, i, (bits >> i) & 1); } - setFunction(8, 7, (bits >> 6) & 1); - setFunction(8, 8, (bits >> 7) & 1); - setFunction(7, 8, (bits >> 8) & 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++) { - setFunction(14 - i, 8, (bits >> i) & 1); + setModule(14 - i, 8, (bits >> i) & 1); } for (var i = 0; i < 8; i++) { - setFunction(n - 1 - i, 8, (bits >> i) & 1); + setModule(n - 1 - i, 8, (bits >> i) & 1); } for (var i = 8; i < 15; i++) { - setFunction(8, n - 15 + i, (bits >> i) & 1); + setModule(8, n - 15 + i, (bits >> i) & 1); } - setFunction(8, n - 8, 1); + setModule(8, n - 8, 1); } private function drawVersion() as Void { @@ -735,10 +1105,29 @@ module Qr { var bit = (bits >> i) & 1; var a = n - 11 + i % 3; var b = i / 3; - setFunction(a, b, bit); - setFunction(b, a, bit); + 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. diff --git a/source/codes/ReedSolomon.mc b/source/codes/ReedSolomon.mc index a69fb1a..58339ae 100644 --- a/source/codes/ReedSolomon.mc +++ b/source/codes/ReedSolomon.mc @@ -1,12 +1,18 @@ // Author: cirakg & claude ai -// Summary: Reed-Solomon error-correction codewords over GF(2^m) for QR (and later Data Matrix and Aztec). +// Summary: Reed-Solomon error-correction codewords over GF(2^m) for QR, Data Matrix and Aztec, resumable for large symbols. // // A Field is GF(2^m) with a primitive polynomial and the exponent the // generator's roots start at (QR: 0x11D, base 0; Data Matrix: 0x12D, -// base 1). Generator polynomials are cached per field and length. ecc() -// is the remainder of data * x^n divided by the generator: the standard -// systematic encoding, one multiply-accumulate per data symbol and EC -// symbol, so a caller budgets blocks per job step. +// base 1). Generator polynomials are cached per field and length. The +// error-correction symbols are the remainder of data * x^n divided by the +// generator: the standard systematic encoding, one multiply-accumulate per +// data symbol and EC symbol. +// +// Large Aztec symbols need GF(4096) and up to 832 EC symbols, far more than +// one event's watchdog budget, so every part can run in steps: the field's +// tables (grow), the generator (buildGenerator) and the division (Encoder). +// Fields of up to 256 elements are built at once (a few thousand +// bytecodes). import Toybox.Lang; @@ -14,31 +20,64 @@ module ReedSolomon { class Field { var size as Number; + // exp has 2 * size entries once ready (exp[a + b] needs no modulo). var exp as Array<Number>; var log as Array<Number>; var base as Number; + private var _primitive as Number; + private var _filled as Number = 0; + private var _x as Number = 1; private var _generators as Dictionary<Number, Array<Number>> = {} as Dictionary<Number, Array<Number>>; + // The generator being built in steps: its length, coefficients so far + // (leading 1 first) and the next root. + private var _pendingN as Number = 0; + private var _pending as Array<Number> = [] as Array<Number>; + private var _pendingRoot as Number = 0; // primitive: the field polynomial including x^m (0x11D for GF(256)). function initialize(primitive as Number, fieldSize as Number, generatorBase as Number) { size = fieldSize; base = generatorBase; - exp = new [2 * fieldSize] as Array<Number>; + _primitive = primitive; + exp = new [fieldSize - 1] as Array<Number>; log = new [fieldSize] as Array<Number>; - var x = 1; - for (var i = 0; i < fieldSize - 1; i++) { + log[0] = 0; + if (fieldSize <= 256) { + grow(fieldSize); + } + } + + function isReady() as Boolean { + return exp.size() == 2 * size; + } + + // Fill up to `count` more table entries; true when the field is ready. + function grow(count as Number) as Boolean { + if (isReady()) { + return true; + } + var stop = _filled + count < size - 1 ? _filled + count : size - 1; + var x = _x; + for (var i = _filled; i < stop; i++) { exp[i] = x; log[x] = i; x <<= 1; - if (x >= fieldSize) { - x ^= primitive; + if (x >= size) { + x ^= _primitive; } } - // Doubled table: exp[a + b] needs no modulo. - for (var i = fieldSize - 1; i < 2 * fieldSize; i++) { - exp[i] = exp[i - (fieldSize - 1)]; + _x = x; + _filled = stop; + if (_filled < size - 1) { + return false; } - log[0] = 0; + // Doubled table: exp[size - 1 + j] = exp[j] for j = 0 .. size. + var first = exp; + exp = first.slice(0, null) as Array<Number>; + exp.addAll(first); + exp.add(first[0]); + exp.add(first[1]); + return true; } function multiply(a as Number, b as Number) as Number { @@ -48,63 +87,115 @@ module ReedSolomon { return exp[log[a] + log[b]]; } - // Coefficients of the generator with n roots, highest degree first, - // without the leading 1. - function generator(n as Number) as Array<Number> { - var cached = _generators[n]; - if (cached != null) { - return cached; + // True when generator(n) is cached. + function hasGenerator(n as Number) as Boolean { + return _generators.hasKey(n); + } + + // Build generator(n) with about `work` coefficient updates (at least + // one root); true when it is cached. + function buildGenerator(n as Number, work as Number) as Boolean { + if (_generators.hasKey(n)) { + return true; + } + if (_pendingN != n) { + _pendingN = n; + _pending = [1] as Array<Number>; + _pendingRoot = 0; } - var g = [1] as Array<Number>; - for (var i = 0; i < n; i++) { + var g = _pending; + var budget = work; + while (_pendingRoot < n && budget > 0) { // Multiply by (x - a^(base + i)); in GF(2^m) minus is plus. - var root = exp[(base + i) % (size - 1)]; + var logRoot = (base + _pendingRoot) % (size - 1); var next = new [g.size() + 1] as Array<Number>; - for (var k = 0; k < next.size(); k++) { - next[k] = 0; - } - for (var k = 0; k < g.size(); k++) { - next[k] = next[k] ^ g[k]; - next[k + 1] = next[k + 1] ^ multiply(g[k], root); + next[0] = g[0]; + for (var k = 1; k < g.size(); k++) { + var c = g[k - 1]; + next[k] = g[k] ^ (c == 0 ? 0 : exp[log[c] + logRoot]); } + var last = g[g.size() - 1]; + next[g.size()] = last == 0 ? 0 : exp[log[last] + logRoot]; + budget -= g.size(); g = next; + _pendingRoot++; + } + _pending = g; + if (_pendingRoot < n) { + return false; } - var coefficients = g.slice(1, null) as Array<Number>; - _generators[n] = coefficients; - return coefficients; + _generators[n] = g.slice(1, null) as Array<Number>; + _pendingN = 0; + _pending = [] as Array<Number>; + return true; + } + + // Coefficients of the generator with n roots, highest degree first, + // without the leading 1. + function generator(n as Number) as Array<Number> { + buildGenerator(n, 0x7FFFFFFF); + return _generators[n] as Array<Number>; } } - // The n error-correction symbols of data (both as symbol values). + // The n error-correction symbols of data (both as symbol values), in + // one go. Jobs use Encoder to spread a long block over several steps. function ecc(field as Field, data as Array<Number>, n as Number) as Array<Number> { - var g = field.generator(n); - var rem = new [n] as Array<Number>; - for (var k = 0; k < n; k++) { - rem[k] = 0; - } - var exp = field.exp; - var log = field.log; - var logG = new [n] as Array<Number>; - for (var k = 0; k < n; k++) { - logG[k] = g[k] == 0 ? -1 : log[g[k]]; - } - for (var i = 0; i < data.size(); i++) { - var factor = data[i] ^ rem[0]; - // Shift the remainder left by one symbol. - for (var k = 0; k < n - 1; k++) { - rem[k] = rem[k + 1]; + var encoder = new Encoder(field, data, n); + encoder.step(data.size()); + return encoder.remainder; + } + + // ecc() as a resumable computation: step() feeds a number of data + // symbols; `remainder` holds the error-correction symbols at the end. + // The field must be ready and generator(n) cached (or cheap). + class Encoder { + var remainder as Array<Number>; + + private var _exp as Array<Number>; + private var _log as Array<Number>; + private var _logG as Array<Number>; + private var _data as Array<Number>; + private var _i as Number = 0; + + function initialize(field as Field, data as Array<Number>, n as Number) { + var g = field.generator(n); + _exp = field.exp; + _log = field.log; + _data = data; + remainder = new [n] as Array<Number>; + _logG = new [n] as Array<Number>; + for (var k = 0; k < n; k++) { + remainder[k] = 0; + _logG[k] = g[k] == 0 ? -1 : _log[g[k]]; } - rem[n - 1] = 0; - if (factor != 0) { - var lf = log[factor]; - for (var k = 0; k < n; k++) { - var lg = logG[k]; - if (lg >= 0) { - rem[k] = rem[k] ^ exp[lf + lg]; + } + + // Up to `symbols` more data symbols; true when all are in. + function step(symbols as Number) as Boolean { + var rem = remainder; + var n = rem.size(); + var exp = _exp; + var logG = _logG; + var stop = _i + symbols < _data.size() ? _i + symbols : _data.size(); + for (var i = _i; i < stop; i++) { + var factor = _data[i] ^ rem[0]; + // Shift the remainder left by one symbol (natively). + rem = rem.slice(1, null) as Array<Number>; + rem.add(0); + if (factor != 0) { + var lf = _log[factor]; + for (var k = 0; k < n; k++) { + var lg = logG[k]; + if (lg >= 0) { + rem[k] = rem[k] ^ exp[lf + lg]; + } } } } + remainder = rem; + _i = stop; + return _i >= _data.size(); } - return rem; } } |