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   private final GF256 field;
  31   private final int[] coefficients;
  32
  33   /**
  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")
  41    */
  42   GF256Poly(GF256 field, int[] coefficients) {
  43     if (coefficients == null || coefficients.length == 0) {
  44       throw new IllegalArgumentException();
  45     }
  46     this.field = field;
  47     if (coefficients.length > 1 && coefficients[0] == 0) {
  48       // Leading term must be non-zero for anything except the constant polynomial "0"
  49       int firstNonZero = 1;
  50       while (firstNonZero < coefficients.length && coefficients[firstNonZero] == 0) {
  51         firstNonZero++;
  52       }
  53       if (firstNonZero == coefficients.length) {
  54         this.coefficients = field.getZero().coefficients;
  55       } else {
  56         this.coefficients = new int[coefficients.length - firstNonZero];
  57         System.arraycopy(coefficients,
  58             firstNonZero,
  59             this.coefficients,
  60             0,
  61             this.coefficients.length);
  62       }
  63     } else {
  64       this.coefficients = coefficients;
  65     }
  66   }
  67
  68   /**
  69    * @return degree of this polynomial
  70    */
  71   int getDegree() {
  72     return coefficients.length - 1;
  73   }
  74
  75   /**
  76    * @return true iff this polynomial is the monomial "0"
  77    */
  78   boolean isZero() {
  79     return coefficients[0] == 0;
  80   }
  81
  82   /**
  83    * @return coefficient of x^degree term in this polynomial
  84    */
  85   int getCoefficient(int degree) {
  86     return coefficients[coefficients.length - 1 - degree];
  87   }
  88
  89   /**
  90    * @return evaluation of this polynomial at a given point
  91    */
  92   int evaluateAt(int a) {
  93     if (a == 0) {
  94       // Just return the x^0 coefficient
  95       return getCoefficient(0);
  96     }
  97     int size = coefficients.length;
  98     if (a == 1) {
  99       // Just the sum of the coefficients
 100       int result = 0;
 101       for (int i = 0; i < size; i++) {
 102         result = GF256.addOrSubtract(result, coefficients[i]);
 103       }
 104       return result;
 105     }
 106     int result = coefficients[0];
 107     for (int i = 1; i < size; i++) {
 108       result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);
 109     }
 110     return result;
 111   }
 112
 113   /*
 114   int evaluateFormatDerivativeAt(int a) {
 115     int degree = getDegree();
 116     if (degree == 0) {
 117       // Derivative of a constant is zero.
 118       return 0;
 119     }
 120
 121     int aToTheI = 1;
 122     int sum = getCoefficient(1);
 123     int aSquared = field.multiply(a, a);
 124     for (int i = 2; i < degree; i += 2) {
 125       aToTheI = field.multiply(aSquared, aToTheI);
 126       sum = field.addOrSubtract(sum, field.multiply(aToTheI, getCoefficient(i + 1)));
 127     }
 128     return sum;
 129   }
 130    */
 131
 132   GF256Poly addOrSubtract(GF256Poly other) {
 133     if (!field.equals(other.field)) {
 134       throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
 135     }
 136     if (isZero()) {
 137       return other;
 138     }
 139     if (other.isZero()) {
 140       return this;
 141     }
 142
 143     int[] smallerCoefficients = this.coefficients;
 144     int[] largerCoefficients = other.coefficients;
 145     if (smallerCoefficients.length > largerCoefficients.length) {
 146       int[] temp = smallerCoefficients;
 147       smallerCoefficients = largerCoefficients;
 148       largerCoefficients = temp;
 149     }
 150     int[] sumDiff = new int[largerCoefficients.length];
 151     int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
 152     // Copy high-order terms only found in higher-degree polynomial's coefficients
 153     System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
 154
 155     for (int i = lengthDiff; i < largerCoefficients.length; i++) {
 156       sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
 157     }
 158
 159     return new GF256Poly(field, sumDiff);
 160   }
 161
 162   GF256Poly multiply(GF256Poly other) {
 163     if (!field.equals(other.field)) {
 164       throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
 165     }
 166     if (isZero() || other.isZero()) {
 167       return field.getZero();
 168     }
 169     int[] aCoefficients = this.coefficients;
 170     int aLength = aCoefficients.length;
 171     int[] bCoefficients = other.coefficients;
 172     int bLength = bCoefficients.length;
 173     int[] product = new int[aLength + bLength - 1];
 174     for (int i = 0; i < aLength; i++) {
 175       int aCoeff = aCoefficients[i];
 176       for (int j = 0; j < bLength; j++) {
 177         product[i + j] = GF256.addOrSubtract(product[i + j],
 178             field.multiply(aCoeff, bCoefficients[j]));
 179       }
 180     }
 181     return new GF256Poly(field, product);
 182   }
 183
 184   GF256Poly multiply(int scalar) {
 185     if (scalar == 0) {
 186       return field.getZero();
 187     }
 188     if (scalar == 1) {
 189       return this;
 190     }
 191     int size = coefficients.length;
 192     int[] product = new int[size];
 193     System.arraycopy(coefficients, 0, product, 0, size);
 194     for (int i = 0; i < size; i++) {
 195       product[i] = field.multiply(product[i], scalar);
 196     }
 197     return new GF256Poly(field, product);
 198   }
 199
 200   GF256Poly multiplyByMonomial(int degree, int coefficient) {
 201     if (degree < 0) {
 202       throw new IllegalArgumentException();
 203     }
 204     if (coefficient == 0) {
 205       return field.getZero();
 206     }
 207     int size = coefficients.length;
 208     int[] product = new int[size + degree];
 209     System.arraycopy(coefficients, 0, product, 0, size);
 210     for (int i = 0; i < size; i++) {
 211       product[i] = field.multiply(product[i], coefficient);
 212     }
 213     return new GF256Poly(field, product);
 214   }
 215
 216 }