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

   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 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 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     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 = field.getZero().coefficients;
  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     int size = coefficients.length;
 103     if (a == 1) {
 104       // Just the sum of the coefficients
 105       int result = 0;
 106       for (int i = 0; i < size; i++) {
 107         result = GF256.addOrSubtract(result, coefficients[i]);
 108       }
 109       return result;
 110     }
 111     int result = coefficients[0];
 112     for (int i = 1; i < size; i++) {
 113       result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);
 114     }
 115     return result;
 116   }
 117
 118   GF256Poly addOrSubtract(GF256Poly other) {
 119     if (!field.equals(other.field)) {
 120       throw new IllegalArgumentException("GF256Polys do not have same GF256 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] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
 143     }
 144
 145     return new GF256Poly(field, sumDiff);
 146   }
 147
 148   GF256Poly multiply(GF256Poly other) {
 149     if (!field.equals(other.field)) {
 150       throw new IllegalArgumentException("GF256Polys do not have same GF256 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] = GF256.addOrSubtract(product[i + j],
 164             field.multiply(aCoeff, bCoefficients[j]));
 165       }
 166     }
 167     return new GF256Poly(field, product);
 168   }
 169
 170   GF256Poly 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 GF256Poly(field, product);
 183   }
 184
 185   GF256Poly 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 GF256Poly(field, product);
 198   }
 199
 200   GF256Poly[] divide(GF256Poly other) {
 201     if (!field.equals(other.field)) {
 202       throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
 203     }
 204     if (other.isZero()) {
 205       throw new IllegalArgumentException("Divide by 0");
 206     }
 207
 208     GF256Poly quotient = field.getZero();
 209     GF256Poly 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       GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);
 218       GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);
 219       quotient = quotient.addOrSubtract(iterationQuotient);
 220       remainder = remainder.addOrSubtract(term);
 221     }
 222
 223     return new GF256Poly[] { quotient, remainder };
 224   }
 225
 226   public String toString() {
 227     StringBuffer result = new StringBuffer(8 * getDegree());
 228     for (int degree = getDegree(); degree >= 0; degree--) {
 229       int coefficient = getCoefficient(degree);
 230       if (coefficient != 0) {
 231         if (coefficient < 0) {
 232           result.append(" - ");
 233           coefficient = -coefficient;
 234         } else {
 235           if (result.length() > 0) {
 236             result.append(" + ");
 237           }
 238         }
 239         if (degree == 0 || coefficient != 1) {
 240           int alphaPower = field.log(coefficient);
 241           if (alphaPower == 0) {
 242             result.append('1');
 243           } else if (alphaPower == 1) {
 244             result.append('a');
 245           } else {
 246             result.append("a^");
 247             result.append(alphaPower);
 248           }
 249         }
 250         if (degree != 0) {
 251           if (degree == 1) {
 252             result.append('x');
 253           } else {
 254             result.append("x^");
 255             result.append(degree);
 256           }
 257         }
 258       }
 259     }
 260     return result.toString();
 261   }
 262
 263 }