GenericGFPoly.php 9.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289
  1. <?php
  2. /*
  3. * Copyright 2007 ZXing authors
  4. *
  5. * Licensed under the Apache License, Version 2.0 (the "License");
  6. * you may not use this file except in compliance with the License.
  7. * You may obtain a copy of the License at
  8. *
  9. * http://www.apache.org/licenses/LICENSE-2.0
  10. *
  11. * Unless required by applicable law or agreed to in writing, software
  12. * distributed under the License is distributed on an "AS IS" BASIS,
  13. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14. * See the License for the specific language governing permissions and
  15. * limitations under the License.
  16. */
  17. namespace Zxing\Common\Reedsolomon;
  18. /**
  19. * <p>Represents a polynomial whose coefficients are elements of a GF.
  20. * Instances of this class are immutable.</p>
  21. *
  22. * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
  23. * port of his C++ Reed-Solomon implementation.</p>
  24. *
  25. * @author Sean Owen
  26. */
  27. final class GenericGFPoly
  28. {
  29. private $field;
  30. private $coefficients;
  31. /**
  32. * @param field the {@link GenericGF} instance representing the field to use
  33. * to perform computations
  34. * @param coefficients array coefficients as ints representing elements of GF(size), arranged
  35. * from most significant (highest-power term) coefficient to least significant
  36. *
  37. * @throws InvalidArgumentException if argument is null or empty,
  38. * 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($field, $coefficients)
  42. {
  43. if (count($coefficients) == 0) {
  44. throw new \InvalidArgumentException();
  45. }
  46. $this->field = $field;
  47. $coefficientsLength = count($coefficients);
  48. if ($coefficientsLength > 1 && $coefficients[0] == 0) {
  49. // Leading term must be non-zero for anything except the constant polynomial "0"
  50. $firstNonZero = 1;
  51. while ($firstNonZero < $coefficientsLength && $coefficients[$firstNonZero] == 0) {
  52. $firstNonZero++;
  53. }
  54. if ($firstNonZero == $coefficientsLength) {
  55. $this->coefficients = [0];
  56. } else {
  57. $this->coefficients = fill_array(0, $coefficientsLength - $firstNonZero, 0);
  58. $this->coefficients = arraycopy($coefficients,
  59. $firstNonZero,
  60. $this->coefficients,
  61. 0,
  62. count($this->coefficients));
  63. }
  64. } else {
  65. $this->coefficients = $coefficients;
  66. }
  67. }
  68. public function getCoefficients()
  69. {
  70. return $this->coefficients;
  71. }
  72. /**
  73. * @return evaluation of this polynomial at a given point
  74. */
  75. public function evaluateAt($a)
  76. {
  77. if ($a == 0) {
  78. // Just return the x^0 coefficient
  79. return $this->getCoefficient(0);
  80. }
  81. $size = count($this->coefficients);
  82. if ($a == 1) {
  83. // Just the sum of the coefficients
  84. $result = 0;
  85. foreach ($this->coefficients as $coefficient) {
  86. $result = GenericGF::addOrSubtract($result, $coefficient);
  87. }
  88. return $result;
  89. }
  90. $result = $this->coefficients[0];
  91. for ($i = 1; $i < $size; $i++) {
  92. $result = GenericGF::addOrSubtract($this->field->multiply($a, $result), $this->coefficients[$i]);
  93. }
  94. return $result;
  95. }
  96. /**
  97. * @return coefficient of x^degree term in this polynomial
  98. */
  99. public function getCoefficient($degree)
  100. {
  101. return $this->coefficients[count($this->coefficients) - 1 - $degree];
  102. }
  103. public function multiply($other)
  104. {
  105. if (is_int($other)) {
  106. return $this->multiply_($other);
  107. }
  108. if ($this->field !== $other->field) {
  109. throw new \InvalidArgumentException("GenericGFPolys do not have same GenericGF field");
  110. }
  111. if ($this->isZero() || $other->isZero()) {
  112. return $this->field->getZero();
  113. }
  114. $aCoefficients = $this->coefficients;
  115. $aLength = count($aCoefficients);
  116. $bCoefficients = $other->coefficients;
  117. $bLength = count($bCoefficients);
  118. $product = fill_array(0, $aLength + $bLength - 1, 0);
  119. for ($i = 0; $i < $aLength; $i++) {
  120. $aCoeff = $aCoefficients[$i];
  121. for ($j = 0; $j < $bLength; $j++) {
  122. $product[$i + $j] = GenericGF::addOrSubtract($product[$i + $j],
  123. $this->field->multiply($aCoeff, $bCoefficients[$j]));
  124. }
  125. }
  126. return new GenericGFPoly($this->field, $product);
  127. }
  128. public function multiply_($scalar)
  129. {
  130. if ($scalar == 0) {
  131. return $this->field->getZero();
  132. }
  133. if ($scalar == 1) {
  134. return $this;
  135. }
  136. $size = count($this->coefficients);
  137. $product = fill_array(0, $size, 0);
  138. for ($i = 0; $i < $size; $i++) {
  139. $product[$i] = $this->field->multiply($this->coefficients[$i], $scalar);
  140. }
  141. return new GenericGFPoly($this->field, $product);
  142. }
  143. /**
  144. * @return true iff this polynomial is the monomial "0"
  145. */
  146. public function isZero()
  147. {
  148. return $this->coefficients[0] == 0;
  149. }
  150. public function multiplyByMonomial($degree, $coefficient)
  151. {
  152. if ($degree < 0) {
  153. throw new \InvalidArgumentException();
  154. }
  155. if ($coefficient == 0) {
  156. return $this->field->getZero();
  157. }
  158. $size = count($this->coefficients);
  159. $product = fill_array(0, $size + $degree, 0);
  160. for ($i = 0; $i < $size; $i++) {
  161. $product[$i] = $this->field->multiply($this->coefficients[$i], $coefficient);
  162. }
  163. return new GenericGFPoly($this->field, $product);
  164. }
  165. public function divide($other)
  166. {
  167. if ($this->field !== $other->field) {
  168. throw new \InvalidArgumentException("GenericGFPolys do not have same GenericGF field");
  169. }
  170. if ($other->isZero()) {
  171. throw new \InvalidArgumentException("Divide by 0");
  172. }
  173. $quotient = $this->field->getZero();
  174. $remainder = $this;
  175. $denominatorLeadingTerm = $other->getCoefficient($other->getDegree());
  176. $inverseDenominatorLeadingTerm = $this->field->inverse($denominatorLeadingTerm);
  177. while ($remainder->getDegree() >= $other->getDegree() && !$remainder->isZero()) {
  178. $degreeDifference = $remainder->getDegree() - $other->getDegree();
  179. $scale = $this->field->multiply($remainder->getCoefficient($remainder->getDegree()), $inverseDenominatorLeadingTerm);
  180. $term = $other->multiplyByMonomial($degreeDifference, $scale);
  181. $iterationQuotient = $this->field->buildMonomial($degreeDifference, $scale);
  182. $quotient = $quotient->addOrSubtract($iterationQuotient);
  183. $remainder = $remainder->addOrSubtract($term);
  184. }
  185. return [$quotient, $remainder];
  186. }
  187. /**
  188. * @return degree of this polynomial
  189. */
  190. public function getDegree()
  191. {
  192. return count($this->coefficients) - 1;
  193. }
  194. public function addOrSubtract($other)
  195. {
  196. if ($this->field !== $other->field) {
  197. throw new \InvalidArgumentException("GenericGFPolys do not have same GenericGF field");
  198. }
  199. if ($this->isZero()) {
  200. return $other;
  201. }
  202. if ($other->isZero()) {
  203. return $this;
  204. }
  205. $smallerCoefficients = $this->coefficients;
  206. $largerCoefficients = $other->coefficients;
  207. if (count($smallerCoefficients) > count($largerCoefficients)) {
  208. $temp = $smallerCoefficients;
  209. $smallerCoefficients = $largerCoefficients;
  210. $largerCoefficients = $temp;
  211. }
  212. $sumDiff = fill_array(0, count($largerCoefficients), 0);
  213. $lengthDiff = count($largerCoefficients) - count($smallerCoefficients);
  214. // Copy high-order terms only found in higher-degree polynomial's coefficients
  215. $sumDiff = arraycopy($largerCoefficients, 0, $sumDiff, 0, $lengthDiff);
  216. $countLargerCoefficients = count($largerCoefficients);
  217. for ($i = $lengthDiff; $i < $countLargerCoefficients; $i++) {
  218. $sumDiff[$i] = GenericGF::addOrSubtract($smallerCoefficients[$i - $lengthDiff], $largerCoefficients[$i]);
  219. }
  220. return new GenericGFPoly($this->field, $sumDiff);
  221. }
  222. //@Override
  223. public function toString()
  224. {
  225. $result = '';
  226. for ($degree = $this->getDegree(); $degree >= 0; $degree--) {
  227. $coefficient = $this->getCoefficient($degree);
  228. if ($coefficient != 0) {
  229. if ($coefficient < 0) {
  230. $result .= " - ";
  231. $coefficient = -$coefficient;
  232. } else {
  233. if (strlen($result) > 0) {
  234. $result .= " + ";
  235. }
  236. }
  237. if ($degree == 0 || $coefficient != 1) {
  238. $alphaPower = $this->field->log($coefficient);
  239. if ($alphaPower == 0) {
  240. $result .= '1';
  241. } else if ($alphaPower == 1) {
  242. $result .= 'a';
  243. } else {
  244. $result .= "a^";
  245. $result .= ($alphaPower);
  246. }
  247. }
  248. if ($degree != 0) {
  249. if ($degree == 1) {
  250. $result .= 'x';
  251. } else {
  252. $result .= "x^";
  253. $result .= $degree;
  254. }
  255. }
  256. }
  257. }
  258. return $result;
  259. }
  260. }