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
17 package com.google.zxing.common.reedsolomon;
18
19 /**
20  * <p>Represents a polynomial whose coefficients are elements of a GF.
21  * Instances of this class are immutable.</p>
22  *
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>
25  *
26  * @author Sean Owen
27  */
28 final class GenericGFPoly {
29
30   private final GenericGF field;
31   private final int[] coefficients;
32
33   /**
34    * @param field the {@link GenericGF} instance representing the field to use
35    * to perform computations
36    * @param coefficients coefficients as ints representing elements of GF(size), 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")
41    */
42   GenericGFPoly(GenericGF field, int[] coefficients) {
43     if (coefficients.length == 0) {
44       throw new IllegalArgumentException();
45     }
46     this.field = field;
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"
50       int firstNonZero = 1;
51       while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {
52         firstNonZero++;
53       }
54       if (firstNonZero == coefficientsLength) {
55         this.coefficients = new int[]{0};
56       } else {
57         this.coefficients = new int[coefficientsLength - firstNonZero];
58         System.arraycopy(coefficients,
59             firstNonZero,
60             this.coefficients,
61             0,
62             this.coefficients.length);
63       }
64     } else {
65       this.coefficients = coefficients;
66     }
67   }
68
69   int[] getCoefficients() {
70     return coefficients;
71   }
72
73   /**
74    * @return degree of this polynomial
75    */
76   int getDegree() {
77     return coefficients.length - 1;
78   }
79
80   /**
81    * @return true iff this polynomial is the monomial "0"
82    */
83   boolean isZero() {
84     return coefficients[0] == 0;
85   }
86
87   /**
88    * @return coefficient of x^degree term in this polynomial
89    */
90   int getCoefficient(int degree) {
91     return coefficients[coefficients.length - 1 - degree];
92   }
93
94   /**
95    * @return evaluation of this polynomial at a given point
96    */
97   int evaluateAt(int a) {
98     if (a == 0) {
99       // Just return the x^0 coefficient
100       return getCoefficient(0);
101     }
102     if (a == 1) {
103       // Just the sum of the coefficients
104       int result = 0;
105       for (int coefficient : coefficients) {
106         result = GenericGF.addOrSubtract(result, coefficient);
107       }
108       return result;
109     }
110     int result = coefficients[0];
111     int size = coefficients.length;
112     for (int i = 1; i < size; i++) {
113       result = GenericGF.addOrSubtract(field.multiply(a, result), coefficients[i]);
114     }
115     return result;
116   }
117
118   GenericGFPoly addOrSubtract(GenericGFPoly other) {
119     if (!field.equals(other.field)) {
120       throw new IllegalArgumentException("GenericGFPolys do not have same GenericGF field");
121     }
122     if (isZero()) {
123       return other;
124     }
125     if (other.isZero()) {
126       return this;
127     }
128
129     int[] smallerCoefficients = this.coefficients;
130     int[] largerCoefficients = other.coefficients;
131     if (smallerCoefficients.length > largerCoefficients.length) {
132       int[] temp = smallerCoefficients;
133       smallerCoefficients = largerCoefficients;
134       largerCoefficients = temp;
135     }
136     int[] sumDiff = new int[largerCoefficients.length];
137     int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
138     // Copy high-order terms only found in higher-degree polynomial's coefficients
139     System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
140
141     for (int i = lengthDiff; i < largerCoefficients.length; i++) {
142       sumDiff[i] = GenericGF.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
143     }
144
145     return new GenericGFPoly(field, sumDiff);
146   }
147
148   GenericGFPoly multiply(GenericGFPoly other) {
149     if (!field.equals(other.field)) {
150       throw new IllegalArgumentException("GenericGFPolys do not have same GenericGF field");
151     }
152     if (isZero() || other.isZero()) {
153       return field.getZero();
154     }
155     int[] aCoefficients = this.coefficients;
156     int aLength = aCoefficients.length;
157     int[] bCoefficients = other.coefficients;
158     int bLength = bCoefficients.length;
159     int[] product = new int[aLength + bLength - 1];
160     for (int i = 0; i < aLength; i++) {
161       int aCoeff = aCoefficients[i];
162       for (int j = 0; j < bLength; j++) {
163         product[i + j] = GenericGF.addOrSubtract(product[i + j],
164             field.multiply(aCoeff, bCoefficients[j]));
165       }
166     }
167     return new GenericGFPoly(field, product);
168   }
169
170   GenericGFPoly multiply(int scalar) {
171     if (scalar == 0) {
172       return field.getZero();
173     }
174     if (scalar == 1) {
175       return this;
176     }
177     int size = coefficients.length;
178     int[] product = new int[size];
179     for (int i = 0; i < size; i++) {
180       product[i] = field.multiply(coefficients[i], scalar);
181     }
182     return new GenericGFPoly(field, product);
183   }
184
185   GenericGFPoly multiplyByMonomial(int degree, int coefficient) {
186     if (degree < 0) {
187       throw new IllegalArgumentException();
188     }
189     if (coefficient == 0) {
190       return field.getZero();
191     }
192     int size = coefficients.length;
193     int[] product = new int[size + degree];
194     for (int i = 0; i < size; i++) {
195       product[i] = field.multiply(coefficients[i], coefficient);
196     }
197     return new GenericGFPoly(field, product);
198   }
199
200   GenericGFPoly[] divide(GenericGFPoly other) {
201     if (!field.equals(other.field)) {
202       throw new IllegalArgumentException("GenericGFPolys do not have same GenericGF field");
203     }
204     if (other.isZero()) {
205       throw new IllegalArgumentException("Divide by 0");
206     }
207
208     GenericGFPoly quotient = field.getZero();
209     GenericGFPoly remainder = this;
210
211     int denominatorLeadingTerm = other.getCoefficient(other.getDegree());
212     int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);
213
214     while (remainder.getDegree() >= other.getDegree() && !remainder.isZero()) {
215       int degreeDifference = remainder.getDegree() - other.getDegree();
216       int scale = field.multiply(remainder.getCoefficient(remainder.getDegree()), inverseDenominatorLeadingTerm);
217       GenericGFPoly term = other.multiplyByMonomial(degreeDifference, scale);
218       GenericGFPoly iterationQuotient = field.buildMonomial(degreeDifference, scale);
219       quotient = quotient.addOrSubtract(iterationQuotient);
220       remainder = remainder.addOrSubtract(term);
221     }
222
223     return new GenericGFPoly[] { quotient, remainder };
224   }
225
226   @Override
227   public String toString() {
228     if (isZero()) {
229       return "0";
230     }
231     StringBuilder result = new StringBuilder(8 * getDegree());
232     for (int degree = getDegree(); degree >= 0; degree--) {
233       int coefficient = getCoefficient(degree);
234       if (coefficient != 0) {
235         if (coefficient < 0) {
236           if (degree == getDegree()) {
237             result.append("-");
238           } else {
239             result.append(" - ");
240           }
241           coefficient = -coefficient;
242         } else {
243           if (result.length() > 0) {
244             result.append(" + ");
245           }
246         }
247         if (degree == 0 || coefficient != 1) {
248           int alphaPower = field.log(coefficient);
249           if (alphaPower == 0) {
250             result.append('1');
251           } else if (alphaPower == 1) {
252             result.append('a');
253           } else {
254             result.append("a^");
255             result.append(alphaPower);
256           }
257         }
258         if (degree != 0) {
259           if (degree == 1) {
260             result.append('x');
261           } else {
262             result.append("x^");
263             result.append(degree);
264           }
265         }
266       }
267     }
268     return result.toString();
269   }
270
271 }
272