Debian Codegraph @

src/Common/ReedSolomonCodec.php

raw
1 <?php
2 declare(strict_types = 1);
3
4 namespace BaconQrCode\Common;
5
6 use BaconQrCode\Exception\InvalidArgumentException;
7 use BaconQrCode\Exception\RuntimeException;
8 use SplFixedArray;
9
10 /**
11 * Reed-Solomon codec for 8-bit characters.
12 *
13 * Based on libfec by Phil Karn, KA9Q.
14 */
15 final class ReedSolomonCodec
16 {
17 /**
18 * Symbol size in bits.
19 */
20 private int $symbolSize;
21
22 /**
23 * Block size in symbols.
24 */
25 private int $blockSize;
26
27 /**
28 * First root of RS code generator polynomial, index form.
29 */
30 private int $firstRoot;
31
32 /**
33 * Primitive element to generate polynomial roots, index form.
34 */
35 private int $primitive;
36
37 /**
38 * Prim-th root of 1, index form.
39 */
40 private int $iPrimitive;
41
42 /**
43 * RS code generator polynomial degree (number of roots).
44 */
45 private int $numRoots;
46
47 /**
48 * Padding bytes at front of shortened block.
49 */
50 private int $padding;
51
52 /**
53 * Log lookup table.
54 *
55 * @var SplFixedArray
56 */
57 private SplFixedArray $alphaTo;
58
59 /**
60 * Anti-Log lookup table.
61 *
62 * @var SplFixedArray
63 */
64 private SplFixedArray $indexOf;
65
66 /**
67 * Generator polynomial.
68 *
69 * @var SplFixedArray
70 */
71 private SplFixedArray $generatorPoly;
72
73 /**
74 * @throws InvalidArgumentException if symbol size ist not between 0 and 8
75 * @throws InvalidArgumentException if first root is invalid
76 * @throws InvalidArgumentException if num roots is invalid
77 * @throws InvalidArgumentException if padding is invalid
78 * @throws RuntimeException if field generator polynomial is not primitive
79 */
80 public function __construct(
81 int $symbolSize,
82 int $gfPoly,
83 int $firstRoot,
84 int $primitive,
85 int $numRoots,
86 int $padding
87 ) {
88 if ($symbolSize < 0 || $symbolSize > 8) {
89 throw new InvalidArgumentException('Symbol size must be between 0 and 8');
90 }
91
92 if ($firstRoot < 0 || $firstRoot >= (1 << $symbolSize)) {
93 throw new InvalidArgumentException('First root must be between 0 and ' . (1 << $symbolSize));
94 }
95
96 if ($numRoots < 0 || $numRoots >= (1 << $symbolSize)) {
97 throw new InvalidArgumentException('Num roots must be between 0 and ' . (1 << $symbolSize));
98 }
99
100 if ($padding < 0 || $padding >= ((1 << $symbolSize) - 1 - $numRoots)) {
101 throw new InvalidArgumentException(
102 'Padding must be between 0 and ' . ((1 << $symbolSize) - 1 - $numRoots)
103 );
104 }
105
106 $this->symbolSize = $symbolSize;
107 $this->blockSize = (1 << $symbolSize) - 1;
108 $this->padding = $padding;
109 $this->alphaTo = SplFixedArray::fromArray(array_fill(0, $this->blockSize + 1, 0), false);
110 $this->indexOf = SplFixedArray::fromArray(array_fill(0, $this->blockSize + 1, 0), false);
111
112 // Generate galous field lookup table
113 $this->indexOf[0] = $this->blockSize;
114 $this->alphaTo[$this->blockSize] = 0;
115
116 $sr = 1;
117
118 for ($i = 0; $i < $this->blockSize; ++$i) {
119 $this->indexOf[$sr] = $i;
120 $this->alphaTo[$i] = $sr;
121
122 $sr <<= 1;
123
124 if ($sr & (1 << $symbolSize)) {
125 $sr ^= $gfPoly;
126 }
127
128 $sr &= $this->blockSize;
129 }
130
131 if (1 !== $sr) {
132 throw new RuntimeException('Field generator polynomial is not primitive');
133 }
134
135 // Form RS code generator polynomial from its roots
136 $this->generatorPoly = SplFixedArray::fromArray(array_fill(0, $numRoots + 1, 0), false);
137 $this->firstRoot = $firstRoot;
138 $this->primitive = $primitive;
139 $this->numRoots = $numRoots;
140
141 // Find prim-th root of 1, used in decoding
142 for ($iPrimitive = 1; ($iPrimitive % $primitive) !== 0; $iPrimitive += $this->blockSize) {
143 }
144
145 $this->iPrimitive = intdiv($iPrimitive, $primitive);
146
147 $this->generatorPoly[0] = 1;
148
149 for ($i = 0, $root = $firstRoot * $primitive; $i < $numRoots; ++$i, $root += $primitive) {
150 $this->generatorPoly[$i + 1] = 1;
151
152 for ($j = $i; $j > 0; $j--) {
153 if ($this->generatorPoly[$j] !== 0) {
154 $this->generatorPoly[$j] = $this->generatorPoly[$j - 1] ^ $this->alphaTo[
155 $this->modNn($this->indexOf[$this->generatorPoly[$j]] + $root)
156 ];
157 } else {
158 $this->generatorPoly[$j] = $this->generatorPoly[$j - 1];
159 }
160 }
161
162 $this->generatorPoly[$j] = $this->alphaTo[$this->modNn($this->indexOf[$this->generatorPoly[0]] + $root)];
163 }
164
165 // Convert generator poly to index form for quicker encoding
166 for ($i = 0; $i <= $numRoots; ++$i) {
167 $this->generatorPoly[$i] = $this->indexOf[$this->generatorPoly[$i]];
168 }
169 }
170
171 /**
172 * Encodes data and writes result back into parity array.
173 */
174 public function encode(SplFixedArray $data, SplFixedArray $parity) : void
175 {
176 for ($i = 0; $i < $this->numRoots; ++$i) {
177 $parity[$i] = 0;
178 }
179
180 $iterations = $this->blockSize - $this->numRoots - $this->padding;
181
182 for ($i = 0; $i < $iterations; ++$i) {
183 $feedback = $this->indexOf[$data[$i] ^ $parity[0]];
184
185 if ($feedback !== $this->blockSize) {
186 // Feedback term is non-zero
187 $feedback = $this->modNn($this->blockSize - $this->generatorPoly[$this->numRoots] + $feedback);
188
189 for ($j = 1; $j < $this->numRoots; ++$j) {
190 $parity[$j] = $parity[$j] ^ $this->alphaTo[
191 $this->modNn($feedback + $this->generatorPoly[$this->numRoots - $j])
192 ];
193 }
194 }
195
196 for ($j = 0; $j < $this->numRoots - 1; ++$j) {
197 $parity[$j] = $parity[$j + 1];
198 }
199
200 if ($feedback !== $this->blockSize) {
201 $parity[$this->numRoots - 1] = $this->alphaTo[$this->modNn($feedback + $this->generatorPoly[0])];
202 } else {
203 $parity[$this->numRoots - 1] = 0;
204 }
205 }
206 }
207
208 /**
209 * Decodes received data.
210 */
211 public function decode(SplFixedArray $data, ?SplFixedArray $erasures = null) : ?int
212 {
213 // This speeds up the initialization a bit.
214 $numRootsPlusOne = SplFixedArray::fromArray(array_fill(0, $this->numRoots + 1, 0), false);
215 $numRoots = SplFixedArray::fromArray(array_fill(0, $this->numRoots, 0), false);
216
217 $lambda = clone $numRootsPlusOne;
218 $b = clone $numRootsPlusOne;
219 $t = clone $numRootsPlusOne;
220 $omega = clone $numRootsPlusOne;
221 $root = clone $numRoots;
222 $loc = clone $numRoots;
223
224 $numErasures = (null !== $erasures ? count($erasures) : 0);
225
226 // Form the Syndromes; i.e., evaluate data(x) at roots of g(x)
227 $syndromes = SplFixedArray::fromArray(array_fill(0, $this->numRoots, $data[0]), false);
228
229 for ($i = 1; $i < $this->blockSize - $this->padding; ++$i) {
230 for ($j = 0; $j < $this->numRoots; ++$j) {
231 if ($syndromes[$j] === 0) {
232 $syndromes[$j] = $data[$i];
233 } else {
234 $syndromes[$j] = $data[$i] ^ $this->alphaTo[
235 $this->modNn($this->indexOf[$syndromes[$j]] + ($this->firstRoot + $j) * $this->primitive)
236 ];
237 }
238 }
239 }
240
241 // Convert syndromes to index form, checking for nonzero conditions
242 $syndromeError = 0;
243
244 for ($i = 0; $i < $this->numRoots; ++$i) {
245 $syndromeError |= $syndromes[$i];
246 $syndromes[$i] = $this->indexOf[$syndromes[$i]];
247 }
248
249 if (! $syndromeError) {
250 // If syndrome is zero, data[] is a codeword and there are no errors to correct, so return data[]
251 // unmodified.
252 return 0;
253 }
254
255 $lambda[0] = 1;
256
257 if ($numErasures > 0) {
258 // Init lambda to be the erasure locator polynomial
259 $lambda[1] = $this->alphaTo[$this->modNn($this->primitive * ($this->blockSize - 1 - $erasures[0]))];
260
261 for ($i = 1; $i < $numErasures; ++$i) {
262 $u = $this->modNn($this->primitive * ($this->blockSize - 1 - $erasures[$i]));
263
264 for ($j = $i + 1; $j > 0; --$j) {
265 $tmp = $this->indexOf[$lambda[$j - 1]];
266
267 if ($tmp !== $this->blockSize) {
268 $lambda[$j] = $lambda[$j] ^ $this->alphaTo[$this->modNn($u + $tmp)];
269 }
270 }
271 }
272 }
273
274 for ($i = 0; $i <= $this->numRoots; ++$i) {
275 $b[$i] = $this->indexOf[$lambda[$i]];
276 }
277
278 // Begin Berlekamp-Massey algorithm to determine error+erasure locator polynomial
279 $r = $numErasures;
280 $el = $numErasures;
281
282 while (++$r <= $this->numRoots) {
283 // Compute discrepancy at the r-th step in poly form
284 $discrepancyR = 0;
285
286 for ($i = 0; $i < $r; ++$i) {
287 if ($lambda[$i] !== 0 && $syndromes[$r - $i - 1] !== $this->blockSize) {
288 $discrepancyR ^= $this->alphaTo[
289 $this->modNn($this->indexOf[$lambda[$i]] + $syndromes[$r - $i - 1])
290 ];
291 }
292 }
293
294 $discrepancyR = $this->indexOf[$discrepancyR];
295
296 if ($discrepancyR === $this->blockSize) {
297 $tmp = $b->toArray();
298 array_unshift($tmp, $this->blockSize);
299 array_pop($tmp);
300 $b = SplFixedArray::fromArray($tmp, false);
301 continue;
302 }
303
304 $t[0] = $lambda[0];
305
306 for ($i = 0; $i < $this->numRoots; ++$i) {
307 if ($b[$i] !== $this->blockSize) {
308 $t[$i + 1] = $lambda[$i + 1] ^ $this->alphaTo[$this->modNn($discrepancyR + $b[$i])];
309 } else {
310 $t[$i + 1] = $lambda[$i + 1];
311 }
312 }
313
314 if (2 * $el <= $r + $numErasures - 1) {
315 $el = $r + $numErasures - $el;
316
317 for ($i = 0; $i <= $this->numRoots; ++$i) {
318 $b[$i] = (
319 $lambda[$i] === 0
320 ? $this->blockSize
321 : $this->modNn($this->indexOf[$lambda[$i]] - $discrepancyR + $this->blockSize)
322 );
323 }
324 } else {
325 $tmp = $b->toArray();
326 array_unshift($tmp, $this->blockSize);
327 array_pop($tmp);
328 $b = SplFixedArray::fromArray($tmp, false);
329 }
330
331 $lambda = clone $t;
332 }
333
334 // Convert lambda to index form and compute deg(lambda(x))
335 $degLambda = 0;
336
337 for ($i = 0; $i <= $this->numRoots; ++$i) {
338 $lambda[$i] = $this->indexOf[$lambda[$i]];
339
340 if ($lambda[$i] !== $this->blockSize) {
341 $degLambda = $i;
342 }
343 }
344
345 // Find roots of the error+erasure locator polynomial by Chien search.
346 $reg = clone $lambda;
347 $reg[0] = 0;
348 $count = 0;
349 $i = 1;
350
351 for ($k = $this->iPrimitive - 1; $i <= $this->blockSize; ++$i, $k = $this->modNn($k + $this->iPrimitive)) {
352 $q = 1;
353
354 for ($j = $degLambda; $j > 0; $j--) {
355 if ($reg[$j] !== $this->blockSize) {
356 $reg[$j] = $this->modNn($reg[$j] + $j);
357 $q ^= $this->alphaTo[$reg[$j]];
358 }
359 }
360
361 if ($q !== 0) {
362 // Not a root
363 continue;
364 }
365
366 // Store root (index-form) and error location number
367 $root[$count] = $i;
368 $loc[$count] = $k;
369
370 if (++$count === $degLambda) {
371 break;
372 }
373 }
374
375 if ($degLambda !== $count) {
376 // deg(lambda) unequal to number of roots: uncorrectable error detected
377 return null;
378 }
379
380 // Compute err+eras evaluate poly omega(x) = s(x)*lambda(x) (modulo x**numRoots). In index form. Also find
381 // deg(omega).
382 $degOmega = $degLambda - 1;
383
384 for ($i = 0; $i <= $degOmega; ++$i) {
385 $tmp = 0;
386
387 for ($j = $i; $j >= 0; --$j) {
388 if ($syndromes[$i - $j] !== $this->blockSize && $lambda[$j] !== $this->blockSize) {
389 $tmp ^= $this->alphaTo[$this->modNn($syndromes[$i - $j] + $lambda[$j])];
390 }
391 }
392
393 $omega[$i] = $this->indexOf[$tmp];
394 }
395
396 // Compute error values in poly-form. num1 = omega(inv(X(l))), num2 = inv(X(l))**(firstRoot-1) and
397 // den = lambda_pr(inv(X(l))) all in poly form.
398 for ($j = $count - 1; $j >= 0; --$j) {
399 $num1 = 0;
400
401 for ($i = $degOmega; $i >= 0; $i--) {
402 if ($omega[$i] !== $this->blockSize) {
403 $num1 ^= $this->alphaTo[$this->modNn($omega[$i] + $i * $root[$j])];
404 }
405 }
406
407 $num2 = $this->alphaTo[$this->modNn($root[$j] * ($this->firstRoot - 1) + $this->blockSize)];
408 $den = 0;
409
410 // lambda[i+1] for i even is the formal derivativelambda_pr of lambda[i]
411 for ($i = min($degLambda, $this->numRoots - 1) & ~1; $i >= 0; $i -= 2) {
412 if ($lambda[$i + 1] !== $this->blockSize) {
413 $den ^= $this->alphaTo[$this->modNn($lambda[$i + 1] + $i * $root[$j])];
414 }
415 }
416
417 // Apply error to data
418 if ($num1 !== 0 && $loc[$j] >= $this->padding) {
419 $data[$loc[$j] - $this->padding] = $data[$loc[$j] - $this->padding] ^ (
420 $this->alphaTo[
421 $this->modNn(
422 $this->indexOf[$num1] + $this->indexOf[$num2] + $this->blockSize - $this->indexOf[$den]
423 )
424 ]
425 );
426 }
427 }
428
429 if (null !== $erasures) {
430 if (count($erasures) < $count) {
431 $erasures->setSize($count);
432 }
433
434 for ($i = 0; $i < $count; $i++) {
435 $erasures[$i] = $loc[$i];
436 }
437 }
438
439 return $count;
440 }
441
442 /**
443 * Computes $x % GF_SIZE, where GF_SIZE is 2**GF_BITS - 1, without a slow divide.
444 */
445 private function modNn(int $x) : int
446 {
447 while ($x >= $this->blockSize) {
448 $x -= $this->blockSize;
449 $x = ($x >> $this->symbolSize) + ($x & $this->blockSize);
450 }
451
452 return $x;
453 }
454 }