Debian Codegraph @

vendor/chillerlan/php-qrcode/src/Decoder/ReedSolomonDecoder.php

raw
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 }