woocommerce-pos
/
vendor_prefixed
/
chillerlan
/
php-qrcode
/
src
/
Decoder
/
ReedSolomonDecoder.php
ReedSolomonDecoder.php in WCPOS – Point of Sale (POS) plugin for WooCommerce 1.10.19, at vendor_prefixed/chillerlan/php-qrcode/src/Decoder/ReedSolomonDecoder.php
| 1 | <?php |
| 2 | |
| 3 | /** |
| 4 | * Class ReedSolomonDecoder |
| 5 | * |
| 6 | * @created 24.01.2021 |
| 7 | * @author ZXing Authors |
| 8 | * @author Smiley <smiley@chillerlan.net> |
| 9 | * @copyright 2021 Smiley |
| 10 | * @license Apache-2.0 |
| 11 | */ |
| 12 | namespace WCPOS\Vendor\chillerlan\QRCode\Decoder; |
| 13 | |
| 14 | use WCPOS\Vendor\chillerlan\QRCode\Common\BitBuffer; |
| 15 | use WCPOS\Vendor\chillerlan\QRCode\Common\EccLevel; |
| 16 | use WCPOS\Vendor\chillerlan\QRCode\Common\GenericGFPoly; |
| 17 | use WCPOS\Vendor\chillerlan\QRCode\Common\GF256; |
| 18 | use WCPOS\Vendor\chillerlan\QRCode\Common\Version; |
| 19 | use function array_fill, array_reverse, count; |
| 20 | /** |
| 21 | * Implements Reed-Solomon decoding |
| 22 | * |
| 23 | * The algorithm will not be explained here, but the following references were helpful |
| 24 | * in creating this implementation: |
| 25 | * |
| 26 | * - Bruce Maggs "Decoding Reed-Solomon Codes" (see discussion of Forney's Formula) |
| 27 | * http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps |
| 28 | * - J.I. Hall. "Chapter 5. Generalized Reed-Solomon Codes" (see discussion of Euclidean algorithm) |
| 29 | * https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf |
| 30 | * |
| 31 | * Much credit is due to William Rucklidge since portions of this code are an indirect |
| 32 | * port of his C++ Reed-Solomon implementation. |
| 33 | * |
| 34 | * @author Sean Owen |
| 35 | * @author William Rucklidge |
| 36 | * @author sanfordsquires |
| 37 | */ |
| 38 | final class ReedSolomonDecoder |
| 39 | { |
| 40 | private Version $version; |
| 41 | private EccLevel $eccLevel; |
| 42 | /** |
| 43 | * ReedSolomonDecoder constructor |
| 44 | */ |
| 45 | public function __construct(Version $version, EccLevel $eccLevel) |
| 46 | { |
| 47 | $this->version = $version; |
| 48 | $this->eccLevel = $eccLevel; |
| 49 | } |
| 50 | /** |
| 51 | * Error-correct and copy data blocks together into a stream of bytes |
| 52 | */ |
| 53 | public function decode(array $rawCodewords) : BitBuffer |
| 54 | { |
| 55 | $dataBlocks = $this->deinterleaveRawBytes($rawCodewords); |
| 56 | $dataBytes = []; |
| 57 | foreach ($dataBlocks as [$numDataCodewords, $codewordBytes]) { |
| 58 | $corrected = $this->correctErrors($codewordBytes, $numDataCodewords); |
| 59 | for ($i = 0; $i < $numDataCodewords; $i++) { |
| 60 | $dataBytes[] = $corrected[$i]; |
| 61 | } |
| 62 | } |
| 63 | return new BitBuffer($dataBytes); |
| 64 | } |
| 65 | /** |
| 66 | * When QR Codes use multiple data blocks, they are actually interleaved. |
| 67 | * That is, the first byte of data block 1 to n is written, then the second bytes, and so on. This |
| 68 | * method will separate the data into original blocks. |
| 69 | * |
| 70 | * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException |
| 71 | */ |
| 72 | private function deinterleaveRawBytes(array $rawCodewords) : array |
| 73 | { |
| 74 | // Figure out the number and size of data blocks used by this version and |
| 75 | // error correction level |
| 76 | [$numEccCodewords, $eccBlocks] = $this->version->getRSBlocks($this->eccLevel); |
| 77 | // Now establish DataBlocks of the appropriate size and number of data codewords |
| 78 | $result = []; |
| 79 | //new DataBlock[$totalBlocks]; |
| 80 | $numResultBlocks = 0; |
| 81 | foreach ($eccBlocks as [$numEccBlocks, $eccPerBlock]) { |
| 82 | for ($i = 0; $i < $numEccBlocks; $i++, $numResultBlocks++) { |
| 83 | $result[$numResultBlocks] = [$eccPerBlock, array_fill(0, $numEccCodewords + $eccPerBlock, 0)]; |
| 84 | } |
| 85 | } |
| 86 | // All blocks have the same amount of data, except that the last n |
| 87 | // (where n may be 0) have 1 more byte. Figure out where these start. |
| 88 | /** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */ |
| 89 | $shorterBlocksTotalCodewords = count($result[0][1]); |
| 90 | $longerBlocksStartAt = count($result) - 1; |
| 91 | while ($longerBlocksStartAt >= 0) { |
| 92 | $numCodewords = count($result[$longerBlocksStartAt][1]); |
| 93 | if ($numCodewords === $shorterBlocksTotalCodewords) { |
| 94 | break; |
| 95 | } |
| 96 | $longerBlocksStartAt--; |
| 97 | } |
| 98 | $longerBlocksStartAt++; |
| 99 | $shorterBlocksNumDataCodewords = $shorterBlocksTotalCodewords - $numEccCodewords; |
| 100 | // The last elements of result may be 1 element longer; |
| 101 | // first fill out as many elements as all of them have |
| 102 | $rawCodewordsOffset = 0; |
| 103 | for ($i = 0; $i < $shorterBlocksNumDataCodewords; $i++) { |
| 104 | for ($j = 0; $j < $numResultBlocks; $j++) { |
| 105 | $result[$j][1][$i] = $rawCodewords[$rawCodewordsOffset++]; |
| 106 | } |
| 107 | } |
| 108 | // Fill out the last data block in the longer ones |
| 109 | for ($j = $longerBlocksStartAt; $j < $numResultBlocks; $j++) { |
| 110 | $result[$j][1][$shorterBlocksNumDataCodewords] = $rawCodewords[$rawCodewordsOffset++]; |
| 111 | } |
| 112 | // Now add in error correction blocks |
| 113 | /** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */ |
| 114 | $max = count($result[0][1]); |
| 115 | for ($i = $shorterBlocksNumDataCodewords; $i < $max; $i++) { |
| 116 | for ($j = 0; $j < $numResultBlocks; $j++) { |
| 117 | $iOffset = $j < $longerBlocksStartAt ? $i : $i + 1; |
| 118 | $result[$j][1][$iOffset] = $rawCodewords[$rawCodewordsOffset++]; |
| 119 | } |
| 120 | } |
| 121 | // DataBlocks containing original bytes, "de-interleaved" from representation in the QR Code |
| 122 | return $result; |
| 123 | } |
| 124 | /** |
| 125 | * Given data and error-correction codewords received, possibly corrupted by errors, attempts to |
| 126 | * correct the errors in-place using Reed-Solomon error correction. |
| 127 | */ |
| 128 | private function correctErrors(array $codewordBytes, int $numDataCodewords) : array |
| 129 | { |
| 130 | // First read into an array of ints |
| 131 | $codewordsInts = []; |
| 132 | foreach ($codewordBytes as $codewordByte) { |
| 133 | $codewordsInts[] = $codewordByte & 0xff; |
| 134 | } |
| 135 | $decoded = $this->decodeWords($codewordsInts, count($codewordBytes) - $numDataCodewords); |
| 136 | // Copy back into array of bytes -- only need to worry about the bytes that were data |
| 137 | // We don't care about errors in the error-correction codewords |
| 138 | for ($i = 0; $i < $numDataCodewords; $i++) { |
| 139 | $codewordBytes[$i] = $decoded[$i]; |
| 140 | } |
| 141 | return $codewordBytes; |
| 142 | } |
| 143 | /** |
| 144 | * Decodes given set of received codewords, which include both data and error-correction |
| 145 | * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place, |
| 146 | * in the input. |
| 147 | * |
| 148 | * @param array $received data and error-correction codewords |
| 149 | * @param int $numEccCodewords number of error-correction codewords available |
| 150 | * |
| 151 | * @return int[] |
| 152 | * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException if decoding fails for any reason |
| 153 | */ |
| 154 | private function decodeWords(array $received, int $numEccCodewords) : array |
| 155 | { |
| 156 | $poly = new GenericGFPoly($received); |
| 157 | $syndromeCoefficients = []; |
| 158 | $error = \false; |
| 159 | for ($i = 0; $i < $numEccCodewords; $i++) { |
| 160 | $syndromeCoefficients[$i] = $poly->evaluateAt(GF256::exp($i)); |
| 161 | if ($syndromeCoefficients[$i] !== 0) { |
| 162 | $error = \true; |
| 163 | } |
| 164 | } |
| 165 | if (!$error) { |
| 166 | return $received; |
| 167 | } |
| 168 | [$sigma, $omega] = $this->runEuclideanAlgorithm(GF256::buildMonomial($numEccCodewords, 1), new GenericGFPoly(array_reverse($syndromeCoefficients)), $numEccCodewords); |
| 169 | $errorLocations = $this->findErrorLocations($sigma); |
| 170 | $errorMagnitudes = $this->findErrorMagnitudes($omega, $errorLocations); |
| 171 | $errorLocationsCount = count($errorLocations); |
| 172 | $receivedCount = count($received); |
| 173 | for ($i = 0; $i < $errorLocationsCount; $i++) { |
| 174 | $position = $receivedCount - 1 - GF256::log($errorLocations[$i]); |
| 175 | if ($position < 0) { |
| 176 | throw new QRCodeDecoderException('Bad error location'); |
| 177 | } |
| 178 | $received[$position] ^= $errorMagnitudes[$i]; |
| 179 | } |
| 180 | return $received; |
| 181 | } |
| 182 | /** |
| 183 | * @return \chillerlan\QRCode\Common\GenericGFPoly[] [sigma, omega] |
| 184 | * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException |
| 185 | */ |
| 186 | private function runEuclideanAlgorithm(GenericGFPoly $a, GenericGFPoly $b, int $z) : array |
| 187 | { |
| 188 | // Assume a's degree is >= b's |
| 189 | if ($a->getDegree() < $b->getDegree()) { |
| 190 | $temp = $a; |
| 191 | $a = $b; |
| 192 | $b = $temp; |
| 193 | } |
| 194 | $rLast = $a; |
| 195 | $r = $b; |
| 196 | $tLast = new GenericGFPoly([0]); |
| 197 | $t = new GenericGFPoly([1]); |
| 198 | // Run Euclidean algorithm until r's degree is less than z/2 |
| 199 | while (2 * $r->getDegree() >= $z) { |
| 200 | $rLastLast = $rLast; |
| 201 | $tLastLast = $tLast; |
| 202 | $rLast = $r; |
| 203 | $tLast = $t; |
| 204 | // Divide rLastLast by rLast, with quotient in q and remainder in r |
| 205 | [$q, $r] = $rLastLast->divide($rLast); |
| 206 | $t = $q->multiply($tLast)->addOrSubtract($tLastLast); |
| 207 | if ($r->getDegree() >= $rLast->getDegree()) { |
| 208 | throw new QRCodeDecoderException('Division algorithm failed to reduce polynomial?'); |
| 209 | } |
| 210 | } |
| 211 | $sigmaTildeAtZero = $t->getCoefficient(0); |
| 212 | if ($sigmaTildeAtZero === 0) { |
| 213 | throw new QRCodeDecoderException('sigmaTilde(0) was zero'); |
| 214 | } |
| 215 | $inverse = GF256::inverse($sigmaTildeAtZero); |
| 216 | return [$t->multiplyInt($inverse), $r->multiplyInt($inverse)]; |
| 217 | } |
| 218 | /** |
| 219 | * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException |
| 220 | */ |
| 221 | private function findErrorLocations(GenericGFPoly $errorLocator) : array |
| 222 | { |
| 223 | // This is a direct application of Chien's search |
| 224 | $numErrors = $errorLocator->getDegree(); |
| 225 | if ($numErrors === 1) { |
| 226 | // shortcut |
| 227 | return [$errorLocator->getCoefficient(1)]; |
| 228 | } |
| 229 | $result = array_fill(0, $numErrors, 0); |
| 230 | $e = 0; |
| 231 | for ($i = 1; $i < 256 && $e < $numErrors; $i++) { |
| 232 | if ($errorLocator->evaluateAt($i) === 0) { |
| 233 | $result[$e] = GF256::inverse($i); |
| 234 | $e++; |
| 235 | } |
| 236 | } |
| 237 | if ($e !== $numErrors) { |
| 238 | throw new QRCodeDecoderException('Error locator degree does not match number of roots'); |
| 239 | } |
| 240 | return $result; |
| 241 | } |
| 242 | /** |
| 243 | * |
| 244 | */ |
| 245 | private function findErrorMagnitudes(GenericGFPoly $errorEvaluator, array $errorLocations) : array |
| 246 | { |
| 247 | // This is directly applying Forney's Formula |
| 248 | $s = count($errorLocations); |
| 249 | $result = []; |
| 250 | for ($i = 0; $i < $s; $i++) { |
| 251 | $xiInverse = GF256::inverse($errorLocations[$i]); |
| 252 | $denominator = 1; |
| 253 | for ($j = 0; $j < $s; $j++) { |
| 254 | if ($i !== $j) { |
| 255 | # $denominator = GF256::multiply($denominator, GF256::addOrSubtract(1, GF256::multiply($errorLocations[$j], $xiInverse))); |
| 256 | // Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug. |
| 257 | // Below is a funny-looking workaround from Steven Parkes |
| 258 | $term = GF256::multiply($errorLocations[$j], $xiInverse); |
| 259 | $denominator = GF256::multiply($denominator, ($term & 0x1) === 0 ? $term | 1 : $term & ~1); |
| 260 | } |
| 261 | } |
| 262 | $result[$i] = GF256::multiply($errorEvaluator->evaluateAt($xiInverse), GF256::inverse($denominator)); |
| 263 | } |
| 264 | return $result; |
| 265 | } |
| 266 | } |
| 267 |