ReedSolomonDecoder::decodeWords() - Code Metrics - chillerlan/php-qrcode - Measure and Improve Code Quality continuously with Scrutinizer

ReedSolomonDecoder::decodeWords() B
last analyzed 2023-06-21 14:22 UTC

↳ Parent: ReedSolomonDecoder

Complexity

Conditions	6
Paths	12

Size

Total Lines	39
Code Lines	23

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	6
eloc	23
nc	12
nop	2
dl	0
loc	39
rs	8.9297
c	0
b	0
f	0

<?php
/**
 * Class ReedSolomonDecoder
 *
 * @created      24.01.2021
 * @author       ZXing Authors
 * @author       Smiley <[email protected]>
 * @copyright    2021 Smiley
 * @license      Apache-2.0
 */

namespace chillerlan\QRCode\Common;

use chillerlan\QRCode\QRCodeException;
use function array_fill, array_reverse, count;

/**
 * Implements Reed-Solomon decoding
 *
 * The algorithm will not be explained here, but the following references were helpful
 * in creating this implementation:
 *
 * - Bruce Maggs "Decoding Reed-Solomon Codes" (see discussion of Forney's Formula)
 *   http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps
 * - J.I. Hall. "Chapter 5. Generalized Reed-Solomon Codes" (see discussion of Euclidean algorithm)
 *   https://users.math.msu.edu/users/halljo/classes/codenotes/GRS.pdf
 *
 * Much credit is due to William Rucklidge since portions of this code are an indirect
 * port of his C++ Reed-Solomon implementation.
 *
 * @author Sean Owen
 * @author William Rucklidge
 * @author sanfordsquires
 */
final class ReedSolomonDecoder{

	private Version  $version;
	private EccLevel $eccLevel;

	/**
	 * ReedSolomonDecoder constructor
	 */
	public function __construct(Version $version, EccLevel $eccLevel){
		$this->version  = $version;
		$this->eccLevel = $eccLevel;
	}

	/**
	 * Error-correct and copy data blocks together into a stream of bytes
	 */
	public function decode(array $rawCodewords):BitBuffer{
		$dataBlocks  = $this->deinterleaveRawBytes($rawCodewords);
		$dataBytes   = [];

		foreach($dataBlocks as [$numDataCodewords, $codewordBytes]){
			$corrected = $this->correctErrors($codewordBytes, $numDataCodewords);

			for($i = 0; $i < $numDataCodewords; $i++){
				$dataBytes[] = $corrected[$i];
			}
		}

		return new BitBuffer($dataBytes);
	}

	/**
	 * When QR Codes use multiple data blocks, they are actually interleaved.
	 * That is, the first byte of data block 1 to n is written, then the second bytes, and so on. This
	 * method will separate the data into original blocks.
	 *
	 * @throws \chillerlan\QRCode\Decoder\QRCodeDecoderException
	 */
	private function deinterleaveRawBytes(array $rawCodewords):array{
		// Figure out the number and size of data blocks used by this version and
		// error correction level
		[$numEccCodewords, $eccBlocks] = $this->version->getRSBlocks($this->eccLevel);

		// Now establish DataBlocks of the appropriate size and number of data codewords
		$result          = [];//new DataBlock[$totalBlocks];
		$numResultBlocks = 0;

		foreach($eccBlocks as [$numEccBlocks, $eccPerBlock]){
			for($i = 0; $i < $numEccBlocks; $i++, $numResultBlocks++){
				$result[$numResultBlocks] = [$eccPerBlock, array_fill(0, ($numEccCodewords + $eccPerBlock), 0)];
			}
		}

		// All blocks have the same amount of data, except that the last n
		// (where n may be 0) have 1 more byte. Figure out where these start.
		/** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */
		$shorterBlocksTotalCodewords = count($result[0][1]);
		$longerBlocksStartAt         = (count($result) - 1);

		while($longerBlocksStartAt >= 0){
			$numCodewords = count($result[$longerBlocksStartAt][1]);

			if($numCodewords == $shorterBlocksTotalCodewords){
				break;
			}

			$longerBlocksStartAt--;
		}

		$longerBlocksStartAt++;

		$shorterBlocksNumDataCodewords = ($shorterBlocksTotalCodewords - $numEccCodewords);
		// The last elements of result may be 1 element longer;
		// first fill out as many elements as all of them have
		$rawCodewordsOffset = 0;

		for($i = 0; $i < $shorterBlocksNumDataCodewords; $i++){
			for($j = 0; $j < $numResultBlocks; $j++){
				$result[$j][1][$i] = $rawCodewords[$rawCodewordsOffset++];
			}
		}

		// Fill out the last data block in the longer ones
		for($j = $longerBlocksStartAt; $j < $numResultBlocks; $j++){
			$result[$j][1][$shorterBlocksNumDataCodewords] = $rawCodewords[$rawCodewordsOffset++];
		}

		// Now add in error correction blocks
		/** @phan-suppress-next-line PhanTypePossiblyInvalidDimOffset */
		$max = count($result[0][1]);

		for($i = $shorterBlocksNumDataCodewords; $i < $max; $i++){
			for($j = 0; $j < $numResultBlocks; $j++){
				$iOffset                 = ($j < $longerBlocksStartAt) ? $i : ($i + 1);
				$result[$j][1][$iOffset] = $rawCodewords[$rawCodewordsOffset++];
			}
		}

		// DataBlocks containing original bytes, "de-interleaved" from representation in the QR Code
		return $result;
	}

	/**
	 * Given data and error-correction codewords received, possibly corrupted by errors, attempts to
	 * correct the errors in-place using Reed-Solomon error correction.
	 */
	private function correctErrors(array $codewordBytes, int $numDataCodewords):array{
		// First read into an array of ints
		$codewordsInts = [];

		foreach($codewordBytes as $codewordByte){
			$codewordsInts[] = ($codewordByte & 0xFF);
		}

		$decoded = $this->decodeWords($codewordsInts, (count($codewordBytes) - $numDataCodewords));

		// Copy back into array of bytes -- only need to worry about the bytes that were data
		// We don't care about errors in the error-correction codewords
		for($i = 0; $i < $numDataCodewords; $i++){
			$codewordBytes[$i] = $decoded[$i];
		}

		return $codewordBytes;
	}

	/**
	 * Decodes given set of received codewords, which include both data and error-correction
	 * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place,
	 * in the input.
	 *
	 * @param array $received        data and error-correction codewords
	 * @param int   $numEccCodewords number of error-correction codewords available
	 *
	 * @return int[]
	 * @throws \chillerlan\QRCode\QRCodeException if decoding fails for any reason
	 */
	private function decodeWords(array $received, int $numEccCodewords):array{
		$poly                 = new GenericGFPoly($received);
		$syndromeCoefficients = [];
		$error                = false;

		for($i = 0; $i < $numEccCodewords; $i++){
			$syndromeCoefficients[$i] = $poly->evaluateAt(GF256::exp($i));

			if($syndromeCoefficients[$i] !== 0){
				$error = true;
			}
		}

		if(!$error){

			return $received;
		}

		[$sigma, $omega] = $this->runEuclideanAlgorithm(
			GF256::buildMonomial($numEccCodewords, 1),
			new GenericGFPoly(array_reverse($syndromeCoefficients)),
			$numEccCodewords
		);

		$errorLocations      = $this->findErrorLocations($sigma);
		$errorMagnitudes     = $this->findErrorMagnitudes($omega, $errorLocations);
		$errorLocationsCount = count($errorLocations);
		$receivedCount       = count($received);

		for($i = 0; $i < $errorLocationsCount; $i++){
			$position = ($receivedCount - 1 - GF256::log($errorLocations[$i]));

			if($position < 0){
				throw new QRCodeException('Bad error location');
			}

			$received[$position] ^= $errorMagnitudes[$i];
		}

		return $received;
	}

	/**
	 * @return \chillerlan\QRCode\Common\GenericGFPoly[] [sigma, omega]
	 * @throws \chillerlan\QRCode\QRCodeException
	 */
	private function runEuclideanAlgorithm(GenericGFPoly $a, GenericGFPoly $b, int $z):array{
		// Assume a's degree is >= b's
		if($a->getDegree() < $b->getDegree()){
			$temp = $a;
			$a    = $b;
			$b    = $temp;
		}

		$rLast = $a;
		$r     = $b;
		$tLast = new GenericGFPoly([0]);
		$t     = new GenericGFPoly([1]);

		// Run Euclidean algorithm until r's degree is less than z/2
		while((2 * $r->getDegree()) >= $z){
			$rLastLast = $rLast;
			$tLastLast = $tLast;
			$rLast     = $r;
			$tLast     = $t;

			// Divide rLastLast by rLast, with quotient in q and remainder in r
			[$q, $r] = $rLastLast->divide($rLast);

			$t = $q->multiply($tLast)->addOrSubtract($tLastLast);

			if($r->getDegree() >= $rLast->getDegree()){
				throw new QRCodeException('Division algorithm failed to reduce polynomial?');
			}
		}

		$sigmaTildeAtZero = $t->getCoefficient(0);

		if($sigmaTildeAtZero === 0){
			throw new QRCodeException('sigmaTilde(0) was zero');
		}

		$inverse = GF256::inverse($sigmaTildeAtZero);

		return [$t->multiplyInt($inverse), $r->multiplyInt($inverse)];
	}

	/**
	 * @throws \chillerlan\QRCode\QRCodeException
	 */
	private function findErrorLocations(GenericGFPoly $errorLocator):array{
		// This is a direct application of Chien's search
		$numErrors = $errorLocator->getDegree();

		if($numErrors === 1){ // shortcut
			return [$errorLocator->getCoefficient(1)];
		}

		$result = array_fill(0, $numErrors, 0);
		$e      = 0;

		for($i = 1; $i < 256 && $e < $numErrors; $i++){
			if($errorLocator->evaluateAt($i) === 0){
				$result[$e] = GF256::inverse($i);
				$e++;
			}
		}

		if($e !== $numErrors){
			throw new QRCodeException('Error locator degree does not match number of roots');
		}

		return $result;
	}

	/**
	 *
	 */
	private function findErrorMagnitudes(GenericGFPoly $errorEvaluator, array $errorLocations):array{
		// This is directly applying Forney's Formula
		$s      = count($errorLocations);
		$result = [];

		for($i = 0; $i < $s; $i++){
			$xiInverse   = GF256::inverse($errorLocations[$i]);
			$denominator = 1;

			for($j = 0; $j < $s; $j++){
				if($i !== $j){
#					$denominator = GF256::multiply($denominator, GF256::addOrSubtract(1, GF256::multiply($errorLocations[$j], $xiInverse)));
					// Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug.
					// Below is a funny-looking workaround from Steven Parkes
					$term        = GF256::multiply($errorLocations[$j], $xiInverse);
					$denominator = GF256::multiply($denominator, ((($term & 0x1) === 0) ? ($term | 1) : ($term & ~1)));
				}
			}

			$result[$i] = GF256::multiply($errorEvaluator->evaluateAt($xiInverse), GF256::inverse($denominator));
		}

		return $result;
	}

}


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

chillerlan / php-qrcode

ReedSolomonDecoder::decodeWords() B last analyzed 2023-06-21 14:22 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

ReedSolomonDecoder::decodeWords() B
last analyzed 2023-06-21 14:22 UTC