ReedSolomonDecoder::correctErrors() - Code Metrics - Inspection of ":shower:" - chillerlan/php-qrcode - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — main ( bb73f7...8c75d8 )

by smiley

created 2022-05-10 12:56 UTC

ReedSolomonDecoder::correctErrors() A

↳ Parent: ReedSolomonDecoder

Complexity

Conditions	3
Paths	4

Size

Total Lines	17
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	3
eloc	7
nc	4
nop	2
dl	0
loc	17
rs	10
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, as the name implies.
 *
 * 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{

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

		foreach($dataBlocks as $dataBlock){
			[$numDataCodewords, $codewordBytes] = $dataBlock;

			$corrected = $this->correctErrors($codewordBytes, $numDataCodewords);

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

		return $resultBytes;
	}

	/**
	 * 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 $R):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 R/2
		while(2 * $r->getDegree() >= $R){
			$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, as the name implies.
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			/**
38			* Error-correct and copy data blocks together into a stream of bytes
39			*/
40			public function decode(array $dataBlocks):array{
41			$resultBytes = [];
42
43			foreach($dataBlocks as $dataBlock){
44			[$numDataCodewords, $codewordBytes] = $dataBlock;
45
46			$corrected = $this->correctErrors($codewordBytes, $numDataCodewords);
47
48			for($i = 0; $i < $numDataCodewords; $i++){
49			$resultBytes[] = $corrected[$i];
50			}
51			}
52
53			return $resultBytes;
54			}
55
56			/**
57			* Given data and error-correction codewords received, possibly corrupted by errors, attempts to
58			* correct the errors in-place using Reed-Solomon error correction.
59			*/
60			private function correctErrors(array $codewordBytes, int $numDataCodewords):array{
61			// First read into an array of ints
62			$codewordsInts = [];
63
64			foreach($codewordBytes as $codewordByte){
65			$codewordsInts[] = $codewordByte & 0xFF;
66			}
67
68			$decoded = $this->decodeWords($codewordsInts, (count($codewordBytes) - $numDataCodewords));
69
70			// Copy back into array of bytes -- only need to worry about the bytes that were data
71			// We don't care about errors in the error-correction codewords
72			for($i = 0; $i < $numDataCodewords; $i++){
73			$codewordBytes[$i] = $decoded[$i];
74			}
75
76			return $codewordBytes;
77			}
78
79			/**
80			* Decodes given set of received codewords, which include both data and error-correction
81			* codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place,
82			* in the input.
83			*
84			* @param array $received data and error-correction codewords
85			* @param int $numEccCodewords number of error-correction codewords available
86			*
87			* @return int[]
88			* @throws \chillerlan\QRCode\QRCodeException if decoding fails for any reason
89			*/
90			private function decodeWords(array $received, int $numEccCodewords):array{
91			$poly = new GenericGFPoly($received);
92			$syndromeCoefficients = [];
93			$error = false;
94
95			for($i = 0; $i < $numEccCodewords; $i++){
96			$syndromeCoefficients[$i] = $poly->evaluateAt(GF256::exp($i));
97
98			if($syndromeCoefficients[$i] !== 0){
99			$error = true;
100			}
101			}
102
103			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...
104			return $received;
105			}
106
107			[$sigma, $omega] = $this->runEuclideanAlgorithm(
108			GF256::buildMonomial($numEccCodewords, 1),
109			new GenericGFPoly(array_reverse($syndromeCoefficients)),
110			$numEccCodewords
111			);
112
113			$errorLocations = $this->findErrorLocations($sigma);
114			$errorMagnitudes = $this->findErrorMagnitudes($omega, $errorLocations);
115			$errorLocationsCount = count($errorLocations);
116			$receivedCount = count($received);
117
118			for($i = 0; $i < $errorLocationsCount; $i++){
119			$position = $receivedCount - 1 - GF256::log($errorLocations[$i]);
120
121			if($position < 0){
122			throw new QRCodeException('Bad error location');
123			}
124
125			$received[$position] ^= $errorMagnitudes[$i];
126			}
127
128			return $received;
129			}
130
131			/**
132			* @return \chillerlan\QRCode\Common\GenericGFPoly[] [sigma, omega]
133			* @throws \chillerlan\QRCode\QRCodeException
134			*/
135			private function runEuclideanAlgorithm(GenericGFPoly $a, GenericGFPoly $b, int $R):array{
136			// Assume a's degree is >= b's
137			if($a->getDegree() < $b->getDegree()){
138			$temp = $a;
139			$a = $b;
140			$b = $temp;
141			}
142
143			$rLast = $a;
144			$r = $b;
145			$tLast = new GenericGFPoly([0]);
146			$t = new GenericGFPoly([1]);
147
148			// Run Euclidean algorithm until r's degree is less than R/2
149			while(2 * $r->getDegree() >= $R){
150			$rLastLast = $rLast;
151			$tLastLast = $tLast;
152			$rLast = $r;
153			$tLast = $t;
154
155			// Divide rLastLast by rLast, with quotient in q and remainder in r
156			[$q, $r] = $rLastLast->divide($rLast);
157
158			$t = $q->multiply($tLast)->addOrSubtract($tLastLast);
159
160			if($r->getDegree() >= $rLast->getDegree()){
161			throw new QRCodeException('Division algorithm failed to reduce polynomial?');
162			}
163			}
164
165			$sigmaTildeAtZero = $t->getCoefficient(0);
166
167			if($sigmaTildeAtZero === 0){
168			throw new QRCodeException('sigmaTilde(0) was zero');
169			}
170
171			$inverse = GF256::inverse($sigmaTildeAtZero);
172
173			return [$t->multiplyInt($inverse), $r->multiplyInt($inverse)];
174			}
175
176			/**
177			* @throws \chillerlan\QRCode\QRCodeException
178			*/
179			private function findErrorLocations(GenericGFPoly $errorLocator):array{
180			// This is a direct application of Chien's search
181			$numErrors = $errorLocator->getDegree();
182
183			if($numErrors === 1){ // shortcut
184			return [$errorLocator->getCoefficient(1)];
185			}
186
187			$result = array_fill(0, $numErrors, 0);
188			$e = 0;
189
190			for($i = 1; $i < 256 && $e < $numErrors; $i++){
191			if($errorLocator->evaluateAt($i) === 0){
192			$result[$e] = GF256::inverse($i);
193			$e++;
194			}
195			}
196
197			if($e !== $numErrors){
198			throw new QRCodeException('Error locator degree does not match number of roots');
199			}
200
201			return $result;
202			}
203
204			/**
205			*
206			*/
207			private function findErrorMagnitudes(GenericGFPoly $errorEvaluator, array $errorLocations):array{
208			// This is directly applying Forney's Formula
209			$s = count($errorLocations);
210			$result = [];
211
212			for($i = 0; $i < $s; $i++){
213			$xiInverse = GF256::inverse($errorLocations[$i]);
214			$denominator = 1;
215
216			for($j = 0; $j < $s; $j++){
217			if($i !== $j){
218			# $denominator = GF256::multiply($denominator, GF256::addOrSubtract(1, GF256::multiply($errorLocations[$j], $xiInverse)));
219			// Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug.
220			// Below is a funny-looking workaround from Steven Parkes
221			$term = GF256::multiply($errorLocations[$j], $xiInverse);
222			$denominator = GF256::multiply($denominator, (($term & 0x1) === 0 ? $term \| 1 : $term & ~1));
223			}
224			}
225
226			$result[$i] = GF256::multiply($errorEvaluator->evaluateAt($xiInverse), GF256::inverse($denominator));
227			}
228
229			return $result;
230			}
231
232			}
233

chillerlan / php-qrcode

Push — main ( bb73f7...8c75d8 )

ReedSolomonDecoder::correctErrors() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like