From 88f1cac4fa530fc30fd6ef01970af11c7a959b8e Mon Sep 17 00:00:00 2001 From: cirakg Date: Wed, 21 Oct 2026 03:55:01 +0200 Subject: fix(codes): bound every 2D encoding step under the watchdog; draw large codes from runs M6's step sizes were estimates, only exercised with small codes. With the largest inputs the app accepts, every 2D encoder tripped the watchdog on the Forerunner 255S (and the biggest steps were far over the 768 KB watches' limit), so a large code added from the phone would have stopped the app during settings processing at every start. - QR: resumable segmentation, Reed-Solomon, interleaving, function patterns and final mask; mask scoring on rows and columns packed 16 modules per word (same penalties, checked against the per-module rules). - Reed-Solomon: resumable field tables and generator, encoder shifting with native slice. - Data Matrix, Aztec, PDF417: resumable encodation, stuffing, compaction, placement and build; Data Matrix's grid as a byte array (90 KB -> 35 KB); PDF417 refuses text that can't fit the screen before compacting. - Cache format 2 with 16-bit sizes (wide PDF417 was cached wrong); packing in steps; codes drawn as runs, and from a bitmap painted in steps when a frame can't draw all runs. - The job runner does two steps per tick on 768 KB watches; gen_products --check verifies each product's watchdogCount fits that. - CodeView renews full brightness (AMOLED) or the backlight (MIP) for up to a minute from its single ticker; a tap restarts the minute. Co-Authored-By: Claude Opus 5.5 --- source/codes/ReedSolomon.mc | 205 ++++++++++++++++++++++++++++++++------------ 1 file changed, 148 insertions(+), 57 deletions(-) (limited to 'source/codes/ReedSolomon.mc') 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; var log as Array; 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> = {} as Dictionary>; + // 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 = [] as Array; + 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; + _primitive = primitive; + exp = new [fieldSize - 1] as Array; log = new [fieldSize] as Array; - 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; + 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 { - 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; + _pendingRoot = 0; } - var g = [1] as Array; - 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; - 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; - _generators[n] = coefficients; - return coefficients; + _generators[n] = g.slice(1, null) as Array; + _pendingN = 0; + _pending = [] as Array; + return true; + } + + // Coefficients of the generator with n roots, highest degree first, + // without the leading 1. + function generator(n as Number) as Array { + buildGenerator(n, 0x7FFFFFFF); + return _generators[n] as Array; } } - // 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, n as Number) as Array { - var g = field.generator(n); - var rem = new [n] as Array; - for (var k = 0; k < n; k++) { - rem[k] = 0; - } - var exp = field.exp; - var log = field.log; - var logG = new [n] as Array; - 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; + + private var _exp as Array; + private var _log as Array; + private var _logG as Array; + private var _data as Array; + private var _i as Number = 0; + + function initialize(field as Field, data as Array, n as Number) { + var g = field.generator(n); + _exp = field.exp; + _log = field.log; + _data = data; + remainder = new [n] as Array; + _logG = new [n] as Array; + 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; + 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; } } -- cgit v1.2.3