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