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