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

GenericGFPoly::multiplyByMonomial() A
last analyzed 2023-06-21 14:22 UTC

↳ Parent: GenericGFPoly

Complexity

Conditions	4
Paths	4

Size

Total Lines	17
Code Lines	8

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
eloc	8
nc	4
nop	2
dl	0
loc	17
rs	10
c	1
b	0
f	0

<?php
/**
 * Class GenericGFPoly
 *
 * @created      16.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_slice, array_splice, count;

/**
 * Represents a polynomial whose coefficients are elements of a GF.
 * Instances of this class are immutable.
 *
 * 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
 */
final class GenericGFPoly{

	private array $coefficients;

	/**
	 * @param array      $coefficients array coefficients as ints representing elements of GF(size), arranged
	 *                                 from most significant (highest-power term) coefficient to the least significant
	 * @param int|null   $degree
	 *
	 * @throws \chillerlan\QRCode\QRCodeException 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 QRCodeException('arg $coefficients is empty');
		}

		if($degree < 0){
			throw new QRCodeException('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++;
		}

		$this->coefficients = [0];

		if($firstNonZero !== $coefficientsLength){
			$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;
	}

	/**
	 *
	 */
	public function multiply(GenericGFPoly $other):self{

		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);
	}

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

		if($other->isZero()){
			throw new QRCodeException('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];

	}

	/**
	 *
	 */
	public function multiplyInt(int $scalar):self{

		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);
	}

	/**
	 * @throws \chillerlan\QRCode\QRCodeException
	 */
	public function multiplyByMonomial(int $degree, int $coefficient):self{

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

		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);
	}

	/**
	 *
	 */
	public function mod(GenericGFPoly $other):self{

		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);
	}

	/**
	 *
	 */
	public function addOrSubtract(GenericGFPoly $other):self{

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

chillerlan / php-qrcode

GenericGFPoly::multiplyByMonomial() A last analyzed 2023-06-21 14:22 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

GenericGFPoly::multiplyByMonomial() A
last analyzed 2023-06-21 14:22 UTC