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