001/*
002 * Copyright 2007 ZXing authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *      http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.itextpdf.text.pdf.qrcode;
018
019/**
020 * <p>Represents a polynomial whose coefficients are elements of GF(256).
021 * Instances of this class are immutable.</p>
022 *
023 * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
024 * port of his C++ Reed-Solomon implementation.</p>
025 *
026 * @author Sean Owen
027 * @since 5.0.2
028 */
029final class GF256Poly {
030
031  private final GF256 field;
032  private final int[] coefficients;
033
034  /**
035   * @param field the {@link GF256} instance representing the field to use
036   * to perform computations
037   * @param coefficients coefficients as ints representing elements of GF(256), arranged
038   * from most significant (highest-power term) coefficient to least significant
039   * @throws IllegalArgumentException if argument is null or empty,
040   * or if leading coefficient is 0 and this is not a
041   * constant polynomial (that is, it is not the monomial "0")
042   */
043  GF256Poly(GF256 field, int[] coefficients) {
044    if (coefficients == null || coefficients.length == 0) {
045      throw new IllegalArgumentException();
046    }
047    this.field = field;
048    int coefficientsLength = coefficients.length;
049    if (coefficientsLength > 1 && coefficients[0] == 0) {
050      // Leading term must be non-zero for anything except the constant polynomial "0"
051      int firstNonZero = 1;
052      while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {
053        firstNonZero++;
054      }
055      if (firstNonZero == coefficientsLength) {
056        this.coefficients = field.getZero().coefficients;
057      } else {
058        this.coefficients = new int[coefficientsLength - firstNonZero];
059        System.arraycopy(coefficients,
060            firstNonZero,
061            this.coefficients,
062            0,
063            this.coefficients.length);
064      }
065    } else {
066      this.coefficients = coefficients;
067    }
068  }
069
070  int[] getCoefficients() {
071    return coefficients;
072  }
073
074  /**
075   * @return degree of this polynomial
076   */
077  int getDegree() {
078    return coefficients.length - 1;
079  }
080
081  /**
082   * @return true iff this polynomial is the monomial "0"
083   */
084  boolean isZero() {
085    return coefficients[0] == 0;
086  }
087
088  /**
089   * @return coefficient of x^degree term in this polynomial
090   */
091  int getCoefficient(int degree) {
092    return coefficients[coefficients.length - 1 - degree];
093  }
094
095  /**
096   * @return evaluation of this polynomial at a given point
097   */
098  int evaluateAt(int a) {
099    if (a == 0) {
100      // Just return the x^0 coefficient
101      return getCoefficient(0);
102    }
103    int size = coefficients.length;
104    if (a == 1) {
105      // Just the sum of the coefficients
106      int result = 0;
107      for (int i = 0; i < size; i++) {
108        result = GF256.addOrSubtract(result, coefficients[i]);
109      }
110      return result;
111    }
112    int result = coefficients[0];
113    for (int i = 1; i < size; i++) {
114      result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);
115    }
116    return result;
117  }
118
119  GF256Poly addOrSubtract(GF256Poly other) {
120    if (!field.equals(other.field)) {
121      throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
122    }
123    if (isZero()) {
124      return other;
125    }
126    if (other.isZero()) {
127      return this;
128    }
129
130    int[] smallerCoefficients = this.coefficients;
131    int[] largerCoefficients = other.coefficients;
132    if (smallerCoefficients.length > largerCoefficients.length) {
133      int[] temp = smallerCoefficients;
134      smallerCoefficients = largerCoefficients;
135      largerCoefficients = temp;
136    }
137    int[] sumDiff = new int[largerCoefficients.length];
138    int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
139    // Copy high-order terms only found in higher-degree polynomial's coefficients
140    System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
141
142    for (int i = lengthDiff; i < largerCoefficients.length; i++) {
143      sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
144    }
145
146    return new GF256Poly(field, sumDiff);
147  }
148
149  GF256Poly multiply(GF256Poly other) {
150    if (!field.equals(other.field)) {
151      throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
152    }
153    if (isZero() || other.isZero()) {
154      return field.getZero();
155    }
156    int[] aCoefficients = this.coefficients;
157    int aLength = aCoefficients.length;
158    int[] bCoefficients = other.coefficients;
159    int bLength = bCoefficients.length;
160    int[] product = new int[aLength + bLength - 1];
161    for (int i = 0; i < aLength; i++) {
162      int aCoeff = aCoefficients[i];
163      for (int j = 0; j < bLength; j++) {
164        product[i + j] = GF256.addOrSubtract(product[i + j],
165            field.multiply(aCoeff, bCoefficients[j]));
166      }
167    }
168    return new GF256Poly(field, product);
169  }
170
171  GF256Poly multiply(int scalar) {
172    if (scalar == 0) {
173      return field.getZero();
174    }
175    if (scalar == 1) {
176      return this;
177    }
178    int size = coefficients.length;
179    int[] product = new int[size];
180    for (int i = 0; i < size; i++) {
181      product[i] = field.multiply(coefficients[i], scalar);
182    }
183    return new GF256Poly(field, product);
184  }
185
186  GF256Poly multiplyByMonomial(int degree, int coefficient) {
187    if (degree < 0) {
188      throw new IllegalArgumentException();
189    }
190    if (coefficient == 0) {
191      return field.getZero();
192    }
193    int size = coefficients.length;
194    int[] product = new int[size + degree];
195    for (int i = 0; i < size; i++) {
196      product[i] = field.multiply(coefficients[i], coefficient);
197    }
198    return new GF256Poly(field, product);
199  }
200
201  GF256Poly[] divide(GF256Poly other) {
202    if (!field.equals(other.field)) {
203      throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
204    }
205    if (other.isZero()) {
206      throw new IllegalArgumentException("Divide by 0");
207    }
208
209    GF256Poly quotient = field.getZero();
210    GF256Poly remainder = this;
211
212    int denominatorLeadingTerm = other.getCoefficient(other.getDegree());
213    int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);
214
215    while (remainder.getDegree() >= other.getDegree() && !remainder.isZero()) {
216      int degreeDifference = remainder.getDegree() - other.getDegree();
217      int scale = field.multiply(remainder.getCoefficient(remainder.getDegree()), inverseDenominatorLeadingTerm);
218      GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);
219      GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);
220      quotient = quotient.addOrSubtract(iterationQuotient);
221      remainder = remainder.addOrSubtract(term);
222    }
223
224    return new GF256Poly[] { quotient, remainder };
225  }
226
227  public String toString() {
228    StringBuffer result = new StringBuffer(8 * getDegree());
229    for (int degree = getDegree(); degree >= 0; degree--) {
230      int coefficient = getCoefficient(degree);
231      if (coefficient != 0) {
232        if (coefficient < 0) {
233          result.append(" - ");
234          coefficient = -coefficient;
235        } else {
236          if (result.length() > 0) {
237            result.append(" + ");
238          }
239        }
240        if (degree == 0 || coefficient != 1) {
241          int alphaPower = field.log(coefficient);
242          if (alphaPower == 0) {
243            result.append('1');
244          } else if (alphaPower == 1) {
245            result.append('a');
246          } else {
247            result.append("a^");
248            result.append(alphaPower);
249          }
250        }
251        if (degree != 0) {
252          if (degree == 1) {
253            result.append('x');
254          } else {
255            result.append("x^");
256            result.append(degree);
257          }
258        }
259      }
260    }
261    return result.toString();
262  }
263
264}