1<?php 2declare(strict_types = 1); 3 4namespace BaconQrCode\Common; 5 6use BaconQrCode\Exception\InvalidArgumentException; 7use BaconQrCode\Exception\RuntimeException; 8use SplFixedArray; 9 10/** 11 * Reed-Solomon codec for 8-bit characters. 12 * 13 * Based on libfec by Phil Karn, KA9Q. 14 */ 15final 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