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

Passed

Push — v5 ( 043137...387bee )

by smiley

created 2021-01-16 19:26 UTC

GenericGFPoly::addOrSubtract() A

↳ Parent: GenericGFPoly

Complexity

Conditions	5
Paths	6

Size

Total Lines	31
Code Lines	17

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	5
eloc	17
nc	6
nop	1
dl	0
loc	31
rs	9.3888
c	1
b	0
f	0

<?php
/**
 * Class GenericGFPoly
 *
 * @filesource   GenericGFPoly.php
 * @created      16.01.2021
 * @package      chillerlan\QRCode\Common
 * @author       ZXing Authors
 * @author       Smiley <[email protected]>
 * @copyright    2021 Smiley
 * @license      Apache-2.0
 */

namespace chillerlan\QRCode\Common;

use InvalidArgumentException;

use function array_fill, array_slice, array_splice, count;

/**
 * <p>Represents a polynomial whose coefficients are elements of a GF.
 * Instances of this class are immutable.</p>
 *
 * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
 * port of his C++ Reed-Solomon implementation.</p>
 *
 * @author Sean Owen
 */
final class GenericGFPoly{

	private array $coefficients;

	/**
	 * @param array|null $coefficients array coefficients as ints representing elements of GF(size), arranged
	 *                                 from most significant (highest-power term) coefficient to least significant
	 * @param int|null   $degree
	 *
	 * @throws \InvalidArgumentException if argument is null or empty, or if leading coefficient is 0 and this is not a
	 *                                  constant polynomial (that is, it is not the monomial "0")
	 */
	public function __construct(array $coefficients, int $degree = null){
		$degree ??= 0;

		if(empty($coefficients)){
			throw new InvalidArgumentException('arg $coefficients is empty');
		}

		if($degree < 0){
			throw new InvalidArgumentException('negative degree');
		}

		$coefficientsLength = count($coefficients);

		// Leading term must be non-zero for anything except the constant polynomial "0"
		$firstNonZero = 0;

		while($firstNonZero < $coefficientsLength && $coefficients[$firstNonZero] === 0){
			$firstNonZero++;
		}

		if($firstNonZero === $coefficientsLength){
			$this->coefficients = [0];
		}
		else{
			$this->coefficients = array_fill(0, $coefficientsLength - $firstNonZero + $degree, 0);

			for($i = 0; $i < $coefficientsLength - $firstNonZero; $i++){
				$this->coefficients[$i] = $coefficients[$i + $firstNonZero];
			}
		}
	}

	/**
	 * @return int $coefficient of x^degree term in this polynomial
	 */
	public function getCoefficient(int $degree):int{
		return $this->coefficients[count($this->coefficients) - 1 - $degree];
	}

	/**
	 * @return int[]
	 */
	public function getCoefficients():array{
		return $this->coefficients;
	}

	/**
	 * @return int $degree of this polynomial
	 */
	public function getDegree():int{
		return count($this->coefficients) - 1;
	}

	/**
	 * @return bool true if this polynomial is the monomial "0"
	 */
	public function isZero():bool{
		return $this->coefficients[0] === 0;
	}

	/**
	 * @return int evaluation of this polynomial at a given point
	 */
	public function evaluateAt(int $a):int{

		if($a === 0){
			// Just return the x^0 coefficient
			return $this->getCoefficient(0);
		}

		$result = 0;

		foreach($this->coefficients as $c){
			// if $a === 1 just the sum of the coefficients
			$result = GF256::addOrSubtract(($a === 1 ? $result : GF256::multiply($a, $result)), $c);
		}

		return $result;
	}

	/**
	 * @param \chillerlan\QRCode\Common\GenericGFPoly $other
	 *
	 * @return \chillerlan\QRCode\Common\GenericGFPoly
	 */
	public function multiply(GenericGFPoly $other):GenericGFPoly{

		if($this->isZero() || $other->isZero()){
			return new self([0]);
		}

		$product = array_fill(0, count($this->coefficients) + count($other->coefficients) - 1, 0);

		foreach($this->coefficients as $i => $aCoeff){
			foreach($other->coefficients as $j => $bCoeff){
				$product[$i + $j] ^= GF256::multiply($aCoeff, $bCoeff);
			}
		}

		return new self($product);
	}

	/**
	 * @param \chillerlan\QRCode\Common\GenericGFPoly $other
	 *
	 * @return \chillerlan\QRCode\Common\GenericGFPoly[] [quotient, remainder]
	 */
	public function divide(GenericGFPoly $other):array{

		if($other->isZero()){
			throw new InvalidArgumentException('Division by 0');
		}

		$quotient  = new self([0]);
		$remainder = clone $this;

		$denominatorLeadingTerm        = $other->getCoefficient($other->getDegree());
		$inverseDenominatorLeadingTerm = GF256::inverse($denominatorLeadingTerm);

		while($remainder->getDegree() >= $other->getDegree() && !$remainder->isZero()){
			$scale     = GF256::multiply($remainder->getCoefficient($remainder->getDegree()), $inverseDenominatorLeadingTerm);
			$diff      = $remainder->getDegree() - $other->getDegree();
			$quotient  = $quotient->addOrSubtract(GF256::buildMonomial($diff, $scale));
			$remainder = $remainder->addOrSubtract($other->multiplyByMonomial($diff, $scale));
		}

		return [$quotient, $remainder];

	}

	/**
	 * @param int $scalar
	 *
	 * @return \chillerlan\QRCode\Common\GenericGFPoly
	 */
	public function multiplyInt(int $scalar):GenericGFPoly{

		if($scalar === 0){
			return new self([0]);
		}

		if($scalar === 1){
			return $this;
		}

		$product = array_fill(0, count($this->coefficients), 0);

		foreach($this->coefficients as $i => $c){
			$product[$i] = GF256::multiply($c, $scalar);
		}

		return new self($product);
	}

	/**
	 * @param int $degree
	 * @param int $coefficient
	 *
	 * @return \chillerlan\QRCode\Common\GenericGFPoly
	 */
	public function multiplyByMonomial(int $degree, int $coefficient):GenericGFPoly{

		if($degree < 0){
			throw new InvalidArgumentException();
		}

		if($coefficient === 0){
			return new self([0]);
		}

		$product = array_fill(0, count($this->coefficients) + $degree, 0);

		foreach($this->coefficients as $i => $c){
			$product[$i] = GF256::multiply($c, $coefficient);
		}

		return new self($product);
	}

	/**
	 * @param \chillerlan\QRCode\Common\GenericGFPoly $other
	 *
	 * @return \chillerlan\QRCode\Common\GenericGFPoly
	 */
	public function mod(GenericGFPoly $other):GenericGFPoly{

		if(count($this->coefficients) - count($other->coefficients) < 0){
			return $this;
		}

		$ratio = GF256::log($this->coefficients[0]) - GF256::log($other->coefficients[0]);

		foreach($other->coefficients as $i => $c){
			$this->coefficients[$i] ^= GF256::exp(GF256::log($c) + $ratio);
		}

		return (new self($this->coefficients))->mod($other);
	}

	/**
	 * @param \chillerlan\QRCode\Common\GenericGFPoly $other
	 *
	 * @return \chillerlan\QRCode\Common\GenericGFPoly
	 */
	public function addOrSubtract(GenericGFPoly $other):GenericGFPoly{

		if($this->isZero()){
			return $other;
		}

		if($other->isZero()){
			return $this;
		}

		$smallerCoefficients = $this->coefficients;
		$largerCoefficients  = $other->coefficients;

		if(count($smallerCoefficients) > count($largerCoefficients)){
			$temp                = $smallerCoefficients;
			$smallerCoefficients = $largerCoefficients;
			$largerCoefficients  = $temp;
		}

		$sumDiff    = array_fill(0, count($largerCoefficients), 0);
		$lengthDiff = count($largerCoefficients) - count($smallerCoefficients);
		// Copy high-order terms only found in higher-degree polynomial's coefficients
		array_splice($sumDiff, 0, $lengthDiff, array_slice($largerCoefficients, 0, $lengthDiff));

		$countLargerCoefficients = count($largerCoefficients);

		for($i = $lengthDiff; $i < $countLargerCoefficients; $i++){
			$sumDiff[$i] = GF256::addOrSubtract($smallerCoefficients[$i - $lengthDiff], $largerCoefficients[$i]);
		}

		return new self($sumDiff);
	}

}


1			<?php
2			/**
3			* Class GenericGFPoly
4			*
5			* @filesource GenericGFPoly.php
6			* @created 16.01.2021
7			* @package chillerlan\QRCode\Common
8			* @author ZXing Authors
9			* @author Smiley <[email protected]>
10			* @copyright 2021 Smiley
11			* @license Apache-2.0
12			*/
13
14			namespace chillerlan\QRCode\Common;
15
16			use InvalidArgumentException;
17
18			use function array_fill, array_slice, array_splice, count;
19
20			/**
21			* <p>Represents a polynomial whose coefficients are elements of a GF.
22			* Instances of this class are immutable.</p>
23			*
24			* <p>Much credit is due to William Rucklidge since portions of this code are an indirect
25			* port of his C++ Reed-Solomon implementation.</p>
26			*
27			* @author Sean Owen
28			*/
29			final class GenericGFPoly{
30
31			private array $coefficients;
32
33			/**
34			* @param array\|null $coefficients array coefficients as ints representing elements of GF(size), arranged
35			* from most significant (highest-power term) coefficient to least significant
36			* @param int\|null $degree
37			*
38			* @throws \InvalidArgumentException if argument is null or empty, or if leading coefficient is 0 and this is not a
39			* constant polynomial (that is, it is not the monomial "0")
40			*/
41			public function __construct(array $coefficients, int $degree = null){
42			$degree ??= 0;
43
44			if(empty($coefficients)){
45			throw new InvalidArgumentException('arg $coefficients is empty');
46			}
47
48			if($degree < 0){
49			throw new InvalidArgumentException('negative degree');
50			}
51
52			$coefficientsLength = count($coefficients);
53
54			// Leading term must be non-zero for anything except the constant polynomial "0"
55			$firstNonZero = 0;
56
57			while($firstNonZero < $coefficientsLength && $coefficients[$firstNonZero] === 0){
58			$firstNonZero++;
59			}
60
61			if($firstNonZero === $coefficientsLength){
62			$this->coefficients = [0];
63			}
64			else{
65			$this->coefficients = array_fill(0, $coefficientsLength - $firstNonZero + $degree, 0);
66
67			for($i = 0; $i < $coefficientsLength - $firstNonZero; $i++){
68			$this->coefficients[$i] = $coefficients[$i + $firstNonZero];
69			}
70			}
71			}
72
73			/**
74			* @return int $coefficient of x^degree term in this polynomial
75			*/
76			public function getCoefficient(int $degree):int{
77			return $this->coefficients[count($this->coefficients) - 1 - $degree];
78			}
79
80			/**
81			* @return int[]
82			*/
83			public function getCoefficients():array{
84			return $this->coefficients;
85			}
86
87			/**
88			* @return int $degree of this polynomial
89			*/
90			public function getDegree():int{
91			return count($this->coefficients) - 1;
92			}
93
94			/**
95			* @return bool true if this polynomial is the monomial "0"
96			*/
97			public function isZero():bool{
98			return $this->coefficients[0] === 0;
99			}
100
101			/**
102			* @return int evaluation of this polynomial at a given point
103			*/
104			public function evaluateAt(int $a):int{
105
106			if($a === 0){
107			// Just return the x^0 coefficient
108			return $this->getCoefficient(0);
109			}
110
111			$result = 0;
112
113			foreach($this->coefficients as $c){
114			// if $a === 1 just the sum of the coefficients
115			$result = GF256::addOrSubtract(($a === 1 ? $result : GF256::multiply($a, $result)), $c);
116			}
117
118			return $result;
119			}
120
121			/**
122			* @param \chillerlan\QRCode\Common\GenericGFPoly $other
123			*
124			* @return \chillerlan\QRCode\Common\GenericGFPoly
125			*/
126			public function multiply(GenericGFPoly $other):GenericGFPoly{
127
128			if($this->isZero() \|\| $other->isZero()){
129			return new self([0]);
130			}
131
132			$product = array_fill(0, count($this->coefficients) + count($other->coefficients) - 1, 0);
133
134			foreach($this->coefficients as $i => $aCoeff){
135			foreach($other->coefficients as $j => $bCoeff){
136			$product[$i + $j] ^= GF256::multiply($aCoeff, $bCoeff);
137			}
138			}
139
140			return new self($product);
141			}
142
143			/**
144			* @param \chillerlan\QRCode\Common\GenericGFPoly $other
145			*
146			* @return \chillerlan\QRCode\Common\GenericGFPoly[] [quotient, remainder]
147			*/
148			public function divide(GenericGFPoly $other):array{
149
150			if($other->isZero()){
151			throw new InvalidArgumentException('Division by 0');
152			}
153
154			$quotient = new self([0]);
155			$remainder = clone $this;
156
157			$denominatorLeadingTerm = $other->getCoefficient($other->getDegree());
158			$inverseDenominatorLeadingTerm = GF256::inverse($denominatorLeadingTerm);
159
160			while($remainder->getDegree() >= $other->getDegree() && !$remainder->isZero()){
161			$scale = GF256::multiply($remainder->getCoefficient($remainder->getDegree()), $inverseDenominatorLeadingTerm);
162			$diff = $remainder->getDegree() - $other->getDegree();
163			$quotient = $quotient->addOrSubtract(GF256::buildMonomial($diff, $scale));
164			$remainder = $remainder->addOrSubtract($other->multiplyByMonomial($diff, $scale));
165			}
166
167			return [$quotient, $remainder];
168
169			}
170
171			/**
172			* @param int $scalar
173			*
174			* @return \chillerlan\QRCode\Common\GenericGFPoly
175			*/
176			public function multiplyInt(int $scalar):GenericGFPoly{
177
178			if($scalar === 0){
179			return new self([0]);
180			}
181
182			if($scalar === 1){
183			return $this;
184			}
185
186			$product = array_fill(0, count($this->coefficients), 0);
187
188			foreach($this->coefficients as $i => $c){
189			$product[$i] = GF256::multiply($c, $scalar);
190			}
191
192			return new self($product);
193			}
194
195			/**
196			* @param int $degree
197			* @param int $coefficient
198			*
199			* @return \chillerlan\QRCode\Common\GenericGFPoly
200			*/
201			public function multiplyByMonomial(int $degree, int $coefficient):GenericGFPoly{
202
203			if($degree < 0){
204			throw new InvalidArgumentException();
205			}
206
207			if($coefficient === 0){
208			return new self([0]);
209			}
210
211			$product = array_fill(0, count($this->coefficients) + $degree, 0);
212
213			foreach($this->coefficients as $i => $c){
214			$product[$i] = GF256::multiply($c, $coefficient);
215			}
216
217			return new self($product);
218			}
219
220			/**
221			* @param \chillerlan\QRCode\Common\GenericGFPoly $other
222			*
223			* @return \chillerlan\QRCode\Common\GenericGFPoly
224			*/
225			public function mod(GenericGFPoly $other):GenericGFPoly{
226
227			if(count($this->coefficients) - count($other->coefficients) < 0){
228			return $this;
229			}
230
231			$ratio = GF256::log($this->coefficients[0]) - GF256::log($other->coefficients[0]);
232
233			foreach($other->coefficients as $i => $c){
234			$this->coefficients[$i] ^= GF256::exp(GF256::log($c) + $ratio);
235			}
236
237			return (new self($this->coefficients))->mod($other);
238			}
239
240			/**
241			* @param \chillerlan\QRCode\Common\GenericGFPoly $other
242			*
243			* @return \chillerlan\QRCode\Common\GenericGFPoly
244			*/
245			public function addOrSubtract(GenericGFPoly $other):GenericGFPoly{
246
247			if($this->isZero()){
248			return $other;
249			}
250
251			if($other->isZero()){
252			return $this;
253			}
254
255			$smallerCoefficients = $this->coefficients;
256			$largerCoefficients = $other->coefficients;
257
258			if(count($smallerCoefficients) > count($largerCoefficients)){
259			$temp = $smallerCoefficients;
260			$smallerCoefficients = $largerCoefficients;
261			$largerCoefficients = $temp;
262			}
263
264			$sumDiff = array_fill(0, count($largerCoefficients), 0);
265			$lengthDiff = count($largerCoefficients) - count($smallerCoefficients);
266			// Copy high-order terms only found in higher-degree polynomial's coefficients
267			array_splice($sumDiff, 0, $lengthDiff, array_slice($largerCoefficients, 0, $lengthDiff));
268
269			$countLargerCoefficients = count($largerCoefficients);
270
271			for($i = $lengthDiff; $i < $countLargerCoefficients; $i++){
272			$sumDiff[$i] = GF256::addOrSubtract($smallerCoefficients[$i - $lengthDiff], $largerCoefficients[$i]);
273			}
274
275			return new self($sumDiff);
276			}
277
278			}
279

chillerlan / php-qrcode

Push — v5 ( 043137...387bee )

GenericGFPoly::addOrSubtract() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like