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