--- /dev/null
+/*\r
+* Copyright 2007 ZXing authors\r
+*\r
+* Licensed under the Apache License, Version 2.0 (the "License");\r
+* you may not use this file except in compliance with the License.\r
+* You may obtain a copy of the License at\r
+*\r
+* http://www.apache.org/licenses/LICENSE-2.0\r
+*\r
+* Unless required by applicable law or agreed to in writing, software\r
+* distributed under the License is distributed on an "AS IS" BASIS,\r
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+* See the License for the specific language governing permissions and\r
+* limitations under the License.\r
+*/\r
+using System;\r
+namespace com.google.zxing.common.reedsolomon\r
+{\r
+ \r
+ /// <summary> <p>Represents a polynomial whose coefficients are elements of GF(256).\r
+ /// Instances of this class are immutable.</p>\r
+ /// \r
+ /// <p>Much credit is due to William Rucklidge since portions of this code are an indirect\r
+ /// port of his C++ Reed-Solomon implementation.</p>\r
+ /// \r
+ /// </summary>\r
+ /// <author> Sean Owen\r
+ /// </author>\r
+ /// <author>www.Redivivus.in (suraj.supekar@redivivus.in) - Ported from ZXING Java Source \r
+ /// </author>\r
+ sealed class GF256Poly\r
+ {\r
+ internal int[] Coefficients\r
+ {\r
+ get\r
+ {\r
+ return coefficients;\r
+ }\r
+ \r
+ }\r
+ /// <returns> degree of this polynomial\r
+ /// </returns>\r
+ internal int Degree\r
+ {\r
+ get\r
+ {\r
+ return coefficients.Length - 1;\r
+ }\r
+ \r
+ }\r
+ /// <returns> true iff this polynomial is the monomial "0"\r
+ /// </returns>\r
+ internal bool Zero\r
+ {\r
+ get\r
+ {\r
+ return coefficients[0] == 0;\r
+ }\r
+ \r
+ }\r
+ \r
+ //UPGRADE_NOTE: Final was removed from the declaration of 'field '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
+ private GF256 field;\r
+ //UPGRADE_NOTE: Final was removed from the declaration of 'coefficients '. "ms-help://MS.VSCC.v80/dv_commoner/local/redirect.htm?index='!DefaultContextWindowIndex'&keyword='jlca1003'"\r
+ private int[] coefficients;\r
+ \r
+ /// <param name="field">the {@link GF256} instance representing the field to use\r
+ /// to perform computations\r
+ /// </param>\r
+ /// <param name="coefficients">coefficients as ints representing elements of GF(256), arranged\r
+ /// from most significant (highest-power term) coefficient to least significant\r
+ /// </param>\r
+ /// <throws> IllegalArgumentException if argument is null or empty, </throws>\r
+ /// <summary> or if leading coefficient is 0 and this is not a\r
+ /// constant polynomial (that is, it is not the monomial "0")\r
+ /// </summary>\r
+ internal GF256Poly(GF256 field, int[] coefficients)\r
+ {\r
+ if (coefficients == null || coefficients.Length == 0)\r
+ {\r
+ throw new System.ArgumentException();\r
+ }\r
+ this.field = field;\r
+ int coefficientsLength = coefficients.Length;\r
+ if (coefficientsLength > 1 && coefficients[0] == 0)\r
+ {\r
+ // Leading term must be non-zero for anything except the constant polynomial "0"\r
+ int firstNonZero = 1;\r
+ while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0)\r
+ {\r
+ firstNonZero++;\r
+ }\r
+ if (firstNonZero == coefficientsLength)\r
+ {\r
+ this.coefficients = field.Zero.coefficients;\r
+ }\r
+ else\r
+ {\r
+ this.coefficients = new int[coefficientsLength - firstNonZero];\r
+ Array.Copy(coefficients, firstNonZero, this.coefficients, 0, this.coefficients.Length);\r
+ }\r
+ }\r
+ else\r
+ {\r
+ this.coefficients = coefficients;\r
+ }\r
+ }\r
+ \r
+ /// <returns> coefficient of x^degree term in this polynomial\r
+ /// </returns>\r
+ internal int getCoefficient(int degree)\r
+ {\r
+ return coefficients[coefficients.Length - 1 - degree];\r
+ }\r
+ \r
+ /// <returns> evaluation of this polynomial at a given point\r
+ /// </returns>\r
+ internal int evaluateAt(int a)\r
+ {\r
+ if (a == 0)\r
+ {\r
+ // Just return the x^0 coefficient\r
+ return getCoefficient(0);\r
+ }\r
+ int size = coefficients.Length;\r
+ if (a == 1)\r
+ {\r
+ // Just the sum of the coefficients\r
+ int result = 0;\r
+ for (int i = 0; i < size; i++)\r
+ {\r
+ result = GF256.addOrSubtract(result, coefficients[i]);\r
+ }\r
+ return result;\r
+ }\r
+ int result2 = coefficients[0];\r
+ for (int i = 1; i < size; i++)\r
+ {\r
+ result2 = GF256.addOrSubtract(field.multiply(a, result2), coefficients[i]);\r
+ }\r
+ return result2;\r
+ }\r
+ \r
+ internal GF256Poly addOrSubtract(GF256Poly other)\r
+ {\r
+ if (!field.Equals(other.field))\r
+ {\r
+ throw new System.ArgumentException("GF256Polys do not have same GF256 field");\r
+ }\r
+ if (Zero)\r
+ {\r
+ return other;\r
+ }\r
+ if (other.Zero)\r
+ {\r
+ return this;\r
+ }\r
+ \r
+ int[] smallerCoefficients = this.coefficients;\r
+ int[] largerCoefficients = other.coefficients;\r
+ if (smallerCoefficients.Length > largerCoefficients.Length)\r
+ {\r
+ int[] temp = smallerCoefficients;\r
+ smallerCoefficients = largerCoefficients;\r
+ largerCoefficients = temp;\r
+ }\r
+ int[] sumDiff = new int[largerCoefficients.Length];\r
+ int lengthDiff = largerCoefficients.Length - smallerCoefficients.Length;\r
+ // Copy high-order terms only found in higher-degree polynomial's coefficients\r
+ Array.Copy(largerCoefficients, 0, sumDiff, 0, lengthDiff);\r
+ \r
+ for (int i = lengthDiff; i < largerCoefficients.Length; i++)\r
+ {\r
+ sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);\r
+ }\r
+ \r
+ return new GF256Poly(field, sumDiff);\r
+ }\r
+ \r
+ internal GF256Poly multiply(GF256Poly other)\r
+ {\r
+ if (!field.Equals(other.field))\r
+ {\r
+ throw new System.ArgumentException("GF256Polys do not have same GF256 field");\r
+ }\r
+ if (Zero || other.Zero)\r
+ {\r
+ return field.Zero;\r
+ }\r
+ int[] aCoefficients = this.coefficients;\r
+ int aLength = aCoefficients.Length;\r
+ int[] bCoefficients = other.coefficients;\r
+ int bLength = bCoefficients.Length;\r
+ int[] product = new int[aLength + bLength - 1];\r
+ for (int i = 0; i < aLength; i++)\r
+ {\r
+ int aCoeff = aCoefficients[i];\r
+ for (int j = 0; j < bLength; j++)\r
+ {\r
+ product[i + j] = GF256.addOrSubtract(product[i + j], field.multiply(aCoeff, bCoefficients[j]));\r
+ }\r
+ }\r
+ return new GF256Poly(field, product);\r
+ }\r
+ \r
+ internal GF256Poly multiply(int scalar)\r
+ {\r
+ if (scalar == 0)\r
+ {\r
+ return field.Zero;\r
+ }\r
+ if (scalar == 1)\r
+ {\r
+ return this;\r
+ }\r
+ int size = coefficients.Length;\r
+ int[] product = new int[size];\r
+ for (int i = 0; i < size; i++)\r
+ {\r
+ product[i] = field.multiply(coefficients[i], scalar);\r
+ }\r
+ return new GF256Poly(field, product);\r
+ }\r
+ \r
+ internal GF256Poly multiplyByMonomial(int degree, int coefficient)\r
+ {\r
+ if (degree < 0)\r
+ {\r
+ throw new System.ArgumentException();\r
+ }\r
+ if (coefficient == 0)\r
+ {\r
+ return field.Zero;\r
+ }\r
+ int size = coefficients.Length;\r
+ int[] product = new int[size + degree];\r
+ for (int i = 0; i < size; i++)\r
+ {\r
+ product[i] = field.multiply(coefficients[i], coefficient);\r
+ }\r
+ return new GF256Poly(field, product);\r
+ }\r
+ \r
+ internal GF256Poly[] divide(GF256Poly other)\r
+ {\r
+ if (!field.Equals(other.field))\r
+ {\r
+ throw new System.ArgumentException("GF256Polys do not have same GF256 field");\r
+ }\r
+ if (other.Zero)\r
+ {\r
+ throw new System.ArgumentException("Divide by 0");\r
+ }\r
+ \r
+ GF256Poly quotient = field.Zero;\r
+ GF256Poly remainder = this;\r
+ \r
+ int denominatorLeadingTerm = other.getCoefficient(other.Degree);\r
+ int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);\r
+ \r
+ while (remainder.Degree >= other.Degree && !remainder.Zero)\r
+ {\r
+ int degreeDifference = remainder.Degree - other.Degree;\r
+ int scale = field.multiply(remainder.getCoefficient(remainder.Degree), inverseDenominatorLeadingTerm);\r
+ GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);\r
+ GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);\r
+ quotient = quotient.addOrSubtract(iterationQuotient);\r
+ remainder = remainder.addOrSubtract(term);\r
+ }\r
+ \r
+ return new GF256Poly[]{quotient, remainder};\r
+ }\r
+ \r
+ public override System.String ToString()\r
+ {\r
+ System.Text.StringBuilder result = new System.Text.StringBuilder(8 * Degree);\r
+ for (int degree = Degree; degree >= 0; degree--)\r
+ {\r
+ int coefficient = getCoefficient(degree);\r
+ if (coefficient != 0)\r
+ {\r
+ if (coefficient < 0)\r
+ {\r
+ result.Append(" - ");\r
+ coefficient = - coefficient;\r
+ }\r
+ else\r
+ {\r
+ if (result.Length > 0)\r
+ {\r
+ result.Append(" + ");\r
+ }\r
+ }\r
+ if (degree == 0 || coefficient != 1)\r
+ {\r
+ int alphaPower = field.log(coefficient);\r
+ if (alphaPower == 0)\r
+ {\r
+ result.Append('1');\r
+ }\r
+ else if (alphaPower == 1)\r
+ {\r
+ result.Append('a');\r
+ }\r
+ else\r
+ {\r
+ result.Append("a^");\r
+ result.Append(alphaPower);\r
+ }\r
+ }\r
+ if (degree != 0)\r
+ {\r
+ if (degree == 1)\r
+ {\r
+ result.Append('x');\r
+ }\r
+ else\r
+ {\r
+ result.Append("x^");\r
+ result.Append(degree);\r
+ }\r
+ }\r
+ }\r
+ }\r
+ return result.ToString();\r
+ }\r
+ }\r
+}
\ No newline at end of file
projects / zxing.git / blobdiff