aboutsummaryrefslogtreecommitdiff
path: root/source/codes/Aztec.mc
diff options
context:
space:
mode:
Diffstat (limited to 'source/codes/Aztec.mc')
-rw-r--r--source/codes/Aztec.mc419
1 files changed, 286 insertions, 133 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).
generated by cgit v1.2.3 (git 2.39.1) at 2026-10-29 04:30:47 +0000