core/src/com/google/zxing/common/reedsolomon/GF256Poly.java

   1 /*
   2  * Copyright 2007 Google Inc.
   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 GF(256).
  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 srowen@google.com (Sean Owen)
  27  */
  28 final class GF256Poly {
  29
  30   /**
  31    * Polynimal representing the monomial 0.
  32    */
  33   static final GF256Poly ZERO = new GF256Poly(new int[]{0});
  34   /**
  35    * Polynimal representing the monomial 1.
  36    */
  37   static final GF256Poly ONE = new GF256Poly(new int[]{1});
  38
  39   private final int[] coefficients;
  40
  41   /**
  42    * @param coefficients coefficients as ints representing elements of GF(256), arranged
  43    * from most significant (highest-power term) coefficient to least significant
  44    * @throws IllegalArgumentException if argument is null or empty,
  45    * or if leading coefficient is 0 and this is not a
  46    * constant polynomial (that is, it is not the monomial "0")
  47    */
  48   GF256Poly(int[] coefficients) {
  49     if (coefficients == null || coefficients.length == 0) {
  50       throw new IllegalArgumentException();
  51     }
  52     if (coefficients.length > 1 && coefficients[0] == 0) {
  53       // Leading term must be non-zero for anything except the constant polynomial "0"
  54       int firstNonZero = 1;
  55       while (firstNonZero < coefficients.length && coefficients[firstNonZero] == 0) {
  56         firstNonZero++;
  57       }
  58       if (firstNonZero == coefficients.length) {
  59         this.coefficients = ZERO.coefficients;
  60       } else {
  61         this.coefficients = new int[coefficients.length - firstNonZero];
  62         System.arraycopy(coefficients,
  63             firstNonZero,
  64             this.coefficients,
  65             0,
  66             this.coefficients.length);
  67       }
  68     } else {
  69       this.coefficients = coefficients;
  70     }
  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 the monomial representing coefficient * x^degree
  89    */
  90   static GF256Poly buildMonomial(int degree, int coefficient) {
  91     if (degree < 0) {
  92       throw new IllegalArgumentException();
  93     }
  94     if (coefficient == 0) {
  95       return ZERO;
  96     }
  97     int[] coefficients = new int[degree + 1];
  98     coefficients[0] = coefficient;
  99     return new GF256Poly(coefficients);
 100   }
 101
 102   /**
 103    * @return coefficient of x^degree term in this polynomial
 104    */
 105   int getCoefficient(int degree) {
 106     return coefficients[coefficients.length - 1 - degree];
 107   }
 108
 109   /**
 110    * @return evaluation of this polynomial at a given point
 111    */
 112   int evaluateAt(int a) {
 113     if (a == 0) {
 114       // Just return the x^0 coefficient
 115       return getCoefficient(0);
 116     }
 117     final int size = coefficients.length;
 118     if (a == 1) {
 119       // Just the sum of the coefficients
 120       int result = 0;
 121       for (int i = 0; i < size; i++) {
 122         result = GF256.addOrSubtract(result, coefficients[i]);
 123       }
 124       return result;
 125     }
 126     int result = coefficients[0];
 127     for (int i = 1; i < size; i++) {
 128       result = GF256.addOrSubtract(GF256.multiply(a, result), coefficients[i]);
 129     }
 130     return result;
 131   }
 132
 133   int evaluateFormatDerivativeAt(int a) {
 134     int degree = getDegree();
 135     if (degree == 0) {
 136       // Derivative of a constant is zero.
 137       return 0;
 138     }
 139
 140     int aToTheI = 1;
 141     int sum = getCoefficient(1);
 142     int aSquared = GF256.multiply(a, a);
 143     for (int i = 2; i < degree; i += 2) {
 144       aToTheI = GF256.multiply(aSquared, aToTheI);
 145       sum = GF256.addOrSubtract(sum, GF256.multiply(aToTheI, getCoefficient(i + 1)));
 146     }
 147     return sum;
 148   }
 149
 150   GF256Poly addOrSubtract(GF256Poly other) {
 151     if (isZero()) {
 152       return other;
 153     }
 154     if (other.isZero()) {
 155       return this;
 156     }
 157
 158     int[] smallerCoefficients = this.coefficients;
 159     int[] largerCoefficients = other.coefficients;
 160     if (smallerCoefficients.length > largerCoefficients.length) {
 161       int[] temp = smallerCoefficients;
 162       smallerCoefficients = largerCoefficients;
 163       largerCoefficients = temp;
 164     }
 165     int[] sumDiff = new int[largerCoefficients.length];
 166     int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
 167     // Copy high-order terms only found in higher-degree polynomial's coefficients
 168     System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
 169
 170     for (int i = lengthDiff; i < largerCoefficients.length; i++) {
 171       sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
 172     }
 173
 174     return new GF256Poly(sumDiff);
 175   }
 176
 177   GF256Poly multiply(GF256Poly other) {
 178     if (isZero() || other.isZero()) {
 179       return ZERO;
 180     }
 181     int[] aCoefficients = this.coefficients;
 182     int aLength = aCoefficients.length;
 183     int[] bCoefficients = other.coefficients;
 184     int bLength = bCoefficients.length;
 185     int[] product = new int[aLength + bLength - 1];
 186     for (int i = 0; i < aLength; i++) {
 187       int aCoeff = aCoefficients[i];
 188       for (int j = 0; j < bLength; j++) {
 189         product[i + j] = GF256.addOrSubtract(product[i + j],
 190             GF256.multiply(aCoeff, bCoefficients[j]));
 191       }
 192     }
 193     return new GF256Poly(product);
 194   }
 195
 196   GF256Poly multiply(int scalar) {
 197     if (scalar == 0) {
 198       return ZERO;
 199     }
 200     if (scalar == 1) {
 201       return this;
 202     }
 203     int size = coefficients.length;
 204     int[] product = new int[size];
 205     System.arraycopy(coefficients, 0, product, 0, size);
 206     for (int i = 0; i < size; i++) {
 207       product[i] = GF256.multiply(product[i], scalar);
 208     }
 209     return new GF256Poly(product);
 210   }
 211
 212   GF256Poly multiplyByMonomial(int degree, int coefficient) {
 213     if (degree < 0) {
 214       throw new IllegalArgumentException();
 215     }
 216     if (coefficient == 0) {
 217       return ZERO;
 218     }
 219     int size = coefficients.length;
 220     int[] product = new int[size + degree];
 221     System.arraycopy(coefficients, 0, product, 0, size);
 222     for (int i = 0; i < size; i++) {
 223       product[i] = GF256.multiply(product[i], coefficient);
 224     }
 225     return new GF256Poly(product);
 226   }
 227
 228 }