BitArray.php
1 week ago
BitMatrix.php
1 week ago
BitUtils.php
1 week ago
CharacterSetEci.php
1 week ago
EcBlock.php
1 week ago
EcBlocks.php
1 week ago
ErrorCorrectionLevel.php
1 week ago
FormatInformation.php
1 week ago
Mode.php
1 week ago
ReedSolomonCodec.php
1 week ago
Version.php
1 week ago
index.php
1 week 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 |