woocommerce-pos / vendor_prefixed / chillerlan / php-qrcode / src / Common / GenericGFPoly.php

GenericGFPoly.php in WCPOS – Point of Sale (POS) plugin for WooCommerce 1.10.20, at vendor_prefixed/chillerlan/php-qrcode/src/Common/GenericGFPoly.php

217 lines 7.5 KB

Raw Download Zip

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