1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
// Author: cirakg & claude ai
// Summary: Reed-Solomon error-correction codewords over GF(2^m) for QR (and later Data Matrix and Aztec).
//
// 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.
import Toybox.Lang;
module ReedSolomon {
class Field {
var size as Number;
var exp as Array<Number>;
var log as Array<Number>;
var base as Number;
private var _generators as Dictionary<Number, Array<Number>> = {} as Dictionary<Number, Array<Number>>;
// 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>;
log = new [fieldSize] as Array<Number>;
var x = 1;
for (var i = 0; i < fieldSize - 1; i++) {
exp[i] = x;
log[x] = i;
x <<= 1;
if (x >= fieldSize) {
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)];
}
log[0] = 0;
}
function multiply(a as Number, b as Number) as Number {
if (a == 0 || b == 0) {
return 0;
}
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;
}
var g = [1] as Array<Number>;
for (var i = 0; i < n; i++) {
// Multiply by (x - a^(base + i)); in GF(2^m) minus is plus.
var root = exp[(base + i) % (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);
}
g = next;
}
var coefficients = g.slice(1, null) as Array<Number>;
_generators[n] = coefficients;
return coefficients;
}
}
// The n error-correction symbols of data (both as symbol values).
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];
}
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];
}
}
}
}
return rem;
}
}
|
