Debian Codegraph @

vendor/chillerlan/php-qrcode/src/Common/GenericGFPoly.php

raw
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 declare(strict_types=1);
12
13 namespace chillerlan\QRCode\Common;
14
15 use chillerlan\QRCode\QRCodeException;
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 /** @var int[] */
30 private array $coefficients;
31
32 /**
33 * @param int[] $coefficients array coefficients as ints representing elements of GF(size), arranged
34 * from most significant (highest-power term) coefficient to the least significant
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|null $degree = null){
40 $degree ??= 0;
41
42 if($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 * @deprecated 6.0.1 This method will be removed. In v7, use the property "GenericGFPoly::$coefficients" instead.
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 public function multiply(GenericGFPoly $other):self{
122
123 if($this->isZero() || $other->isZero()){
124 return new self([0]);
125 }
126
127 $product = array_fill(0, (count($this->coefficients) + count($other->coefficients) - 1), 0);
128
129 foreach($this->coefficients as $i => $aCoeff){
130 foreach($other->coefficients as $j => $bCoeff){
131 $product[($i + $j)] ^= GF256::multiply($aCoeff, $bCoeff);
132 }
133 }
134
135 return new self($product);
136 }
137
138 /**
139 * @return \chillerlan\QRCode\Common\GenericGFPoly[] [quotient, remainder]
140 * @throws \chillerlan\QRCode\QRCodeException
141 */
142 public function divide(GenericGFPoly $other):array{
143
144 if($other->isZero()){
145 throw new QRCodeException('Division by 0');
146 }
147
148 $quotient = new self([0]);
149 $remainder = clone $this;
150
151 $denominatorLeadingTerm = $other->getCoefficient($other->getDegree());
152 $inverseDenominatorLeadingTerm = GF256::inverse($denominatorLeadingTerm);
153
154 while($remainder->getDegree() >= $other->getDegree() && !$remainder->isZero()){
155 $scale = GF256::multiply($remainder->getCoefficient($remainder->getDegree()), $inverseDenominatorLeadingTerm);
156 $diff = ($remainder->getDegree() - $other->getDegree());
157 $quotient = $quotient->addOrSubtract(GF256::buildMonomial($diff, $scale));
158 $remainder = $remainder->addOrSubtract($other->multiplyByMonomial($diff, $scale));
159 }
160
161 return [$quotient, $remainder];
162
163 }
164
165 public function multiplyInt(int $scalar):self{
166
167 if($scalar === 0){
168 return new self([0]);
169 }
170
171 if($scalar === 1){
172 return $this;
173 }
174
175 $product = array_fill(0, count($this->coefficients), 0);
176
177 foreach($this->coefficients as $i => $c){
178 $product[$i] = GF256::multiply($c, $scalar);
179 }
180
181 return new self($product);
182 }
183
184 /**
185 * @throws \chillerlan\QRCode\QRCodeException
186 */
187 public function multiplyByMonomial(int $degree, int $coefficient):self{
188
189 if($degree < 0){
190 throw new QRCodeException('degree < 0');
191 }
192
193 if($coefficient === 0){
194 return new self([0]);
195 }
196
197 $product = array_fill(0, (count($this->coefficients) + $degree), 0);
198
199 foreach($this->coefficients as $i => $c){
200 $product[$i] = GF256::multiply($c, $coefficient);
201 }
202
203 return new self($product);
204 }
205
206 public function mod(GenericGFPoly $other):self{
207
208 if((count($this->coefficients) - count($other->coefficients)) < 0){
209 return $this;
210 }
211
212 $ratio = (GF256::log($this->coefficients[0]) - GF256::log($other->coefficients[0]));
213
214 foreach($other->coefficients as $i => $c){
215 $this->coefficients[$i] ^= GF256::exp(GF256::log($c) + $ratio);
216 }
217
218 return (new self($this->coefficients))->mod($other);
219 }
220
221 public function addOrSubtract(GenericGFPoly $other):self{
222
223 if($this->isZero()){
224 return $other;
225 }
226
227 if($other->isZero()){
228 return $this;
229 }
230
231 $smallerCoefficients = $this->coefficients;
232 $largerCoefficients = $other->coefficients;
233
234 if(count($smallerCoefficients) > count($largerCoefficients)){
235 $temp = $smallerCoefficients;
236 $smallerCoefficients = $largerCoefficients;
237 $largerCoefficients = $temp;
238 }
239
240 $sumDiff = array_fill(0, count($largerCoefficients), 0);
241 $lengthDiff = (count($largerCoefficients) - count($smallerCoefficients));
242 // Copy high-order terms only found in higher-degree polynomial's coefficients
243 array_splice($sumDiff, 0, $lengthDiff, array_slice($largerCoefficients, 0, $lengthDiff));
244
245 $countLargerCoefficients = count($largerCoefficients);
246
247 for($i = $lengthDiff; $i < $countLargerCoefficients; $i++){
248 $sumDiff[$i] = GF256::addOrSubtract($smallerCoefficients[($i - $lengthDiff)], $largerCoefficients[$i]);
249 }
250
251 return new self($sumDiff);
252 }
253
254 }