+++ /dev/null
-/*\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
-\r
-using System;\r
-using System.Text;\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> srowen@google.com (Sean Owen)\r
- /// </author>\r
- public sealed class GF256Poly\r
- { \r
- private GF256 field;\r
- private int[] coefficients;\r
-\r
- /**\r
- * @param field the {@link GF256} instance representing the field to use\r
- * to perform computations\r
- * @param coefficients coefficients as ints representing elements of GF(256), arranged\r
- * from most significant (highest-power term) coefficient to least significant\r
- * @throws ArgumentException if argument is null or empty,\r
- * or if leading coefficient is 0 and this is not a\r
- * constant polynomial (that is, it is not the monomial "0")\r
- */\r
- public GF256Poly(GF256 field, int[] coefficients) {\r
- if (coefficients == null || coefficients.Length == 0) {\r
- throw new ArgumentException();\r
- }\r
- this.field = field;\r
- int coefficientsLength = coefficients.Length;\r
- if (coefficientsLength > 1 && coefficients[0] == 0) {\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
- firstNonZero++;\r
- }\r
- if (firstNonZero == coefficientsLength) {\r
- this.coefficients = field.getZero().coefficients;\r
- } else {\r
- this.coefficients = new int[coefficientsLength - firstNonZero];\r
- System.Array.Copy(coefficients,firstNonZero,this.coefficients,0,this.coefficients.Length);\r
- }\r
- } else {\r
- this.coefficients = coefficients;\r
- }\r
- }\r
-\r
- public int[] getCoefficients()\r
- {\r
- return coefficients;\r
- }\r
-\r
- /**\r
- * @return degree of this polynomial\r
- */\r
- public int getDegree()\r
- {\r
- return coefficients.Length - 1;\r
- }\r
-\r
- /**\r
- * @return true iff this polynomial is the monomial "0"\r
- */\r
- public bool isZero()\r
- {\r
- return coefficients[0] == 0;\r
- }\r
-\r
- /**\r
- * @return coefficient of x^degree term in this polynomial\r
- */\r
- public int getCoefficient(int degree)\r
- {\r
- return coefficients[coefficients.Length - 1 - degree];\r
- }\r
-\r
- /**\r
- * @return evaluation of this polynomial at a given point\r
- */\r
- public int evaluateAt(int a)\r
- {\r
- if (a == 0) {\r
- // Just return the x^0 coefficient\r
- return getCoefficient(0);\r
- }\r
- int size = coefficients.Length;\r
- int result = 0;\r
-\r
- if (a == 1) {\r
- // Just the sum of the coefficients\r
- result = 0;\r
- for (int i = 0; i < size; i++) {\r
- result = GF256.addOrSubtract(result, coefficients[i]);\r
- }\r
- return result;\r
- }\r
-\r
- result = coefficients[0];\r
- for (int i = 1; i < size; i++) {\r
- result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);\r
- }\r
- return result;\r
- }\r
-\r
- public GF256Poly addOrSubtract(GF256Poly other)\r
- {\r
- if (!field.Equals(other.field)) {\r
- throw new ArgumentException("GF256Polys do not have same GF256 field");\r
- }\r
- if (isZero()) {\r
- return other;\r
- }\r
- if (other.isZero()) {\r
- return this;\r
- }\r
-\r
- int[] smallerCoefficients = this.coefficients;\r
- int[] largerCoefficients = other.coefficients;\r
- if (smallerCoefficients.Length > largerCoefficients.Length) {\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
- System.Array.Copy(largerCoefficients, 0, sumDiff, 0, lengthDiff);\r
-\r
- for (int i = lengthDiff; i < largerCoefficients.Length; i++) {\r
- sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);\r
- }\r
-\r
- return new GF256Poly(field, sumDiff);\r
- }\r
-\r
- public GF256Poly multiply(GF256Poly other)\r
- {\r
- if (!field.Equals(other.field)) {\r
- throw new ArgumentException("GF256Polys do not have same GF256 field");\r
- }\r
- if (isZero() || other.isZero()) {\r
- return field.getZero();\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
- int aCoeff = aCoefficients[i];\r
- for (int j = 0; j < bLength; j++) {\r
- product[i + j] = GF256.addOrSubtract(product[i + j],\r
- field.multiply(aCoeff, bCoefficients[j]));\r
- }\r
- }\r
- return new GF256Poly(field, product);\r
- }\r
-\r
- public GF256Poly multiply(int scalar)\r
- {\r
- if (scalar == 0) {\r
- return field.getZero();\r
- }\r
- if (scalar == 1) {\r
- return this;\r
- }\r
- int size = coefficients.Length;\r
- int[] product = new int[size];\r
- for (int i = 0; i < size; i++) {\r
- product[i] = field.multiply(coefficients[i], scalar);\r
- }\r
- return new GF256Poly(field, product);\r
- }\r
-\r
- public GF256Poly multiplyByMonomial(int degree, int coefficient)\r
- {\r
- if (degree < 0) {\r
- throw new ArgumentException();\r
- }\r
- if (coefficient == 0) {\r
- return field.getZero();\r
- }\r
- int size = coefficients.Length;\r
- int[] product = new int[size + degree];\r
- for (int i = 0; i < size; i++) {\r
- product[i] = field.multiply(coefficients[i], coefficient);\r
- }\r
- return new GF256Poly(field, product);\r
- }\r
-\r
- public GF256Poly[] divide(GF256Poly other)\r
- {\r
- if (!field.Equals(other.field)) {\r
- throw new ArgumentException("GF256Polys do not have same GF256 field");\r
- }\r
- if (other.isZero()) {\r
- throw new ArgumentException("Divide by 0");\r
- }\r
-\r
- GF256Poly quotient = field.getZero();\r
- GF256Poly remainder = this;\r
-\r
- int denominatorLeadingTerm = other.getCoefficient(other.getDegree());\r
- int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);\r
-\r
- while (remainder.getDegree() >= other.getDegree() && !remainder.isZero()) {\r
- int degreeDifference = remainder.getDegree() - other.getDegree();\r
- int scale = field.multiply(remainder.getCoefficient(remainder.getDegree()), 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 String toString() {\r
- StringBuilder result = new StringBuilder(8 * getDegree());\r
- for (int degree = getDegree(); degree >= 0; degree--) {\r
- int coefficient = getCoefficient(degree);\r
- if (coefficient != 0) {\r
- if (coefficient < 0) {\r
- result.Append(" - ");\r
- coefficient = -coefficient;\r
- } else {\r
- if (result.Length > 0) {\r
- result.Append(" + ");\r
- }\r
- }\r
- if (degree == 0 || coefficient != 1) {\r
- int alphaPower = field.log(coefficient);\r
- if (alphaPower == 0) {\r
- result.Append('1');\r
- } else if (alphaPower == 1) {\r
- result.Append('a');\r
- } else {\r
- result.Append("a^");\r
- result.Append(alphaPower);\r
- }\r
- }\r
- if (degree != 0) {\r
- if (degree == 1) {\r
- result.Append('x');\r
- } else {\r
- result.Append("x^");\r
- result.Append(degree);\r
- }\r
- }\r
- }\r
- }\r
- return result.ToString();\r
- }\r
- \r
- }\r
-}
\ No newline at end of file
projects / zxing.git / blobdiff