2 * Copyright 2007 Google Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package com.google.zxing.common.reedsolomon;
20 * <p>Represents a polynomial whose coefficients are elements of GF(256).
21 * Instances of this class are immutable.</p>
23 * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
24 * port of his C++ Reed-Solomon implementation.</p>
26 * @author srowen@google.com (Sean Owen)
28 final class GF256Poly {
30 private final GF256 field;
31 private final int[] coefficients;
34 * @param field the {@link GF256} instance representing the field to use
35 * to perform computations
36 * @param coefficients coefficients as ints representing elements of GF(256), arranged
37 * from most significant (highest-power term) coefficient to least significant
38 * @throws IllegalArgumentException if argument is null or empty,
39 * or if leading coefficient is 0 and this is not a
40 * constant polynomial (that is, it is not the monomial "0")
42 GF256Poly(GF256 field, int[] coefficients) {
43 if (coefficients == null || coefficients.length == 0) {
44 throw new IllegalArgumentException();
47 int coefficientsLength = coefficients.length;
48 if (coefficientsLength > 1 && coefficients[0] == 0) {
49 // Leading term must be non-zero for anything except the constant polynomial "0"
51 while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {
54 if (firstNonZero == coefficientsLength) {
55 this.coefficients = field.getZero().coefficients;
57 this.coefficients = new int[coefficientsLength - firstNonZero];
58 System.arraycopy(coefficients,
62 this.coefficients.length);
65 this.coefficients = coefficients;
70 * @return degree of this polynomial
73 return coefficients.length - 1;
77 * @return true iff this polynomial is the monomial "0"
80 return coefficients[0] == 0;
84 * @return coefficient of x^degree term in this polynomial
86 int getCoefficient(int degree) {
87 return coefficients[coefficients.length - 1 - degree];
91 * @return evaluation of this polynomial at a given point
93 int evaluateAt(int a) {
95 // Just return the x^0 coefficient
96 return getCoefficient(0);
98 int size = coefficients.length;
100 // Just the sum of the coefficients
102 for (int i = 0; i < size; i++) {
103 result = GF256.addOrSubtract(result, coefficients[i]);
107 int result = coefficients[0];
108 for (int i = 1; i < size; i++) {
109 result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);
115 int evaluateFormatDerivativeAt(int a) {
116 int degree = getDegree();
118 // Derivative of a constant is zero.
123 int sum = getCoefficient(1);
124 int aSquared = field.multiply(a, a);
125 for (int i = 2; i < degree; i += 2) {
126 aToTheI = field.multiply(aSquared, aToTheI);
127 sum = field.addOrSubtract(sum, field.multiply(aToTheI, getCoefficient(i + 1)));
133 GF256Poly addOrSubtract(GF256Poly other) {
134 if (!field.equals(other.field)) {
135 throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
140 if (other.isZero()) {
144 int[] smallerCoefficients = this.coefficients;
145 int[] largerCoefficients = other.coefficients;
146 if (smallerCoefficients.length > largerCoefficients.length) {
147 int[] temp = smallerCoefficients;
148 smallerCoefficients = largerCoefficients;
149 largerCoefficients = temp;
151 int[] sumDiff = new int[largerCoefficients.length];
152 int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
153 // Copy high-order terms only found in higher-degree polynomial's coefficients
154 System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
156 for (int i = lengthDiff; i < largerCoefficients.length; i++) {
157 sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
160 return new GF256Poly(field, sumDiff);
163 GF256Poly multiply(GF256Poly other) {
164 if (!field.equals(other.field)) {
165 throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
167 if (isZero() || other.isZero()) {
168 return field.getZero();
170 int[] aCoefficients = this.coefficients;
171 int aLength = aCoefficients.length;
172 int[] bCoefficients = other.coefficients;
173 int bLength = bCoefficients.length;
174 int[] product = new int[aLength + bLength - 1];
175 for (int i = 0; i < aLength; i++) {
176 int aCoeff = aCoefficients[i];
177 for (int j = 0; j < bLength; j++) {
178 product[i + j] = GF256.addOrSubtract(product[i + j],
179 field.multiply(aCoeff, bCoefficients[j]));
182 return new GF256Poly(field, product);
185 GF256Poly multiply(int scalar) {
187 return field.getZero();
192 int size = coefficients.length;
193 int[] product = new int[size];
194 for (int i = 0; i < size; i++) {
195 product[i] = field.multiply(coefficients[i], scalar);
197 return new GF256Poly(field, product);
200 GF256Poly multiplyByMonomial(int degree, int coefficient) {
202 throw new IllegalArgumentException();
204 if (coefficient == 0) {
205 return field.getZero();
207 int size = coefficients.length;
208 int[] product = new int[size + degree];
209 for (int i = 0; i < size; i++) {
210 product[i] = field.multiply(coefficients[i], coefficient);
212 return new GF256Poly(field, product);