aboutsummaryrefslogtreecommitdiff
path: root/source/codes/DataMatrix.mc
diff options
context:
space:
mode:
Diffstat (limited to 'source/codes/DataMatrix.mc')
-rw-r--r--source/codes/DataMatrix.mc298
1 files changed, 196 insertions, 102 deletions
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;
}
}
}
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-29 01:54:07 +0000