GF256Poly.cs 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
  1. /*
  2. * Copyright 2007 ZXing authors
  3. *
  4. * Licensed under the Apache License, Version 2.0 (the "License");
  5. * you may not use this file except in compliance with the License.
  6. * You may obtain a copy of the License at
  7. *
  8. * http://www.apache.org/licenses/LICENSE-2.0
  9. *
  10. * Unless required by applicable law or agreed to in writing, software
  11. * distributed under the License is distributed on an "AS IS" BASIS,
  12. * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13. * See the License for the specific language governing permissions and
  14. * limitations under the License.
  15. */
  16. using System;
  17. namespace FastReport.Barcode.QRCode
  18. {
  19. /*/// <summary> <p>Represents a polynomial whose coefficients are elements of GF(256).
  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. /// </summary>
  26. /// <author> Sean Owen
  27. /// </author>
  28. /// <author>www.Redivivus.in (suraj.supekar@redivivus.in) - Ported from ZXING Java Source
  29. /// </author>*/
  30. internal sealed class GF256Poly
  31. {
  32. internal int[] Coefficients
  33. {
  34. get
  35. {
  36. return coefficients;
  37. }
  38. }
  39. /*/// <returns> degree of this polynomial
  40. /// </returns>*/
  41. internal int Degree
  42. {
  43. get
  44. {
  45. return coefficients.Length - 1;
  46. }
  47. }
  48. /*/// <returns> true iff this polynomial is the monomial "0"
  49. /// </returns>*/
  50. internal bool Zero
  51. {
  52. get
  53. {
  54. return coefficients[0] == 0;
  55. }
  56. }
  57. //UPGRADE_NOTE: Final was removed from the declaration of 'field '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  58. private GF256 field;
  59. //UPGRADE_NOTE: Final was removed from the declaration of 'coefficients '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"
  60. private int[] coefficients;
  61. /*/// <param name="field">the {@link GF256} instance representing the field to use
  62. /// to perform computations
  63. /// </param>
  64. /// <param name="coefficients">coefficients as ints representing elements of GF(256), arranged
  65. /// from most significant (highest-power term) coefficient to least significant
  66. /// </param>
  67. /// <throws> IllegalArgumentException if argument is null or empty, </throws>
  68. /// <summary> or if leading coefficient is 0 and this is not a
  69. /// constant polynomial (that is, it is not the monomial "0")
  70. /// </summary>*/
  71. internal GF256Poly(GF256 field, int[] coefficients)
  72. {
  73. if (coefficients == null || coefficients.Length == 0)
  74. {
  75. throw new System.ArgumentException();
  76. }
  77. this.field = field;
  78. int coefficientsLength = coefficients.Length;
  79. if (coefficientsLength > 1 && coefficients[0] == 0)
  80. {
  81. // Leading term must be non-zero for anything except the constant polynomial "0"
  82. int firstNonZero = 1;
  83. while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0)
  84. {
  85. firstNonZero++;
  86. }
  87. if (firstNonZero == coefficientsLength)
  88. {
  89. this.coefficients = field.Zero.coefficients;
  90. }
  91. else
  92. {
  93. this.coefficients = new int[coefficientsLength - firstNonZero];
  94. Array.Copy(coefficients, firstNonZero, this.coefficients, 0, this.coefficients.Length);
  95. }
  96. }
  97. else
  98. {
  99. this.coefficients = coefficients;
  100. }
  101. }
  102. /*/// <returns> coefficient of x^degree term in this polynomial
  103. /// </returns>*/
  104. internal int getCoefficient(int degree)
  105. {
  106. return coefficients[coefficients.Length - 1 - degree];
  107. }
  108. internal GF256Poly addOrSubtract(GF256Poly other)
  109. {
  110. if (!field.Equals(other.field))
  111. {
  112. throw new System.ArgumentException("GF256Polys do not have same GF256 field");
  113. }
  114. if (Zero)
  115. {
  116. return other;
  117. }
  118. if (other.Zero)
  119. {
  120. return this;
  121. }
  122. int[] smallerCoefficients = this.coefficients;
  123. int[] largerCoefficients = other.coefficients;
  124. if (smallerCoefficients.Length > largerCoefficients.Length)
  125. {
  126. int[] temp = smallerCoefficients;
  127. smallerCoefficients = largerCoefficients;
  128. largerCoefficients = temp;
  129. }
  130. int[] sumDiff = new int[largerCoefficients.Length];
  131. int lengthDiff = largerCoefficients.Length - smallerCoefficients.Length;
  132. // Copy high-order terms only found in higher-degree polynomial's coefficients
  133. Array.Copy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
  134. for (int i = lengthDiff; i < largerCoefficients.Length; i++)
  135. {
  136. sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
  137. }
  138. return new GF256Poly(field, sumDiff);
  139. }
  140. internal GF256Poly multiply(GF256Poly other)
  141. {
  142. if (!field.Equals(other.field))
  143. {
  144. throw new System.ArgumentException("GF256Polys do not have same GF256 field");
  145. }
  146. if (Zero || other.Zero)
  147. {
  148. return field.Zero;
  149. }
  150. int[] aCoefficients = this.coefficients;
  151. int aLength = aCoefficients.Length;
  152. int[] bCoefficients = other.coefficients;
  153. int bLength = bCoefficients.Length;
  154. int[] product = new int[aLength + bLength - 1];
  155. for (int i = 0; i < aLength; i++)
  156. {
  157. int aCoeff = aCoefficients[i];
  158. for (int j = 0; j < bLength; j++)
  159. {
  160. product[i + j] = GF256.addOrSubtract(product[i + j], field.multiply(aCoeff, bCoefficients[j]));
  161. }
  162. }
  163. return new GF256Poly(field, product);
  164. }
  165. internal GF256Poly multiplyByMonomial(int degree, int coefficient)
  166. {
  167. if (degree < 0)
  168. {
  169. throw new System.ArgumentException();
  170. }
  171. if (coefficient == 0)
  172. {
  173. return field.Zero;
  174. }
  175. int size = coefficients.Length;
  176. int[] product = new int[size + degree];
  177. for (int i = 0; i < size; i++)
  178. {
  179. product[i] = field.multiply(coefficients[i], coefficient);
  180. }
  181. return new GF256Poly(field, product);
  182. }
  183. internal GF256Poly[] divide(GF256Poly other)
  184. {
  185. if (!field.Equals(other.field))
  186. {
  187. throw new System.ArgumentException("GF256Polys do not have same GF256 field");
  188. }
  189. if (other.Zero)
  190. {
  191. throw new System.ArgumentException("Divide by 0");
  192. }
  193. GF256Poly quotient = field.Zero;
  194. GF256Poly remainder = this;
  195. int denominatorLeadingTerm = other.getCoefficient(other.Degree);
  196. int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);
  197. while (remainder.Degree >= other.Degree && !remainder.Zero)
  198. {
  199. int degreeDifference = remainder.Degree - other.Degree;
  200. int scale = field.multiply(remainder.getCoefficient(remainder.Degree), inverseDenominatorLeadingTerm);
  201. GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);
  202. GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);
  203. quotient = quotient.addOrSubtract(iterationQuotient);
  204. remainder = remainder.addOrSubtract(term);
  205. }
  206. return new GF256Poly[] { quotient, remainder };
  207. }
  208. }
  209. }