Added Reed-Solomon encoder, suitable for QR Code encoding

[zxing.git] / core / src / com / google / zxing / common / reedsolomon / GF256Poly.java

diff --git a/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java b/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java
index 2c87a06..8f9bcb3 100644 (file)
--- a/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java
+++ b/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2007 Google Inc.
+ * Copyright 2007 ZXing authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -44,16 +44,17 @@ final class GF256Poly {
       throw new IllegalArgumentException();
     }
     this.field = field;
-    if (coefficients.length > 1 && coefficients[0] == 0) {
+    int coefficientsLength = coefficients.length;
+    if (coefficientsLength > 1 && coefficients[0] == 0) {
       // Leading term must be non-zero for anything except the constant polynomial "0"
       int firstNonZero = 1;
-      while (firstNonZero < coefficients.length && coefficients[firstNonZero] == 0) {
+      while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {
         firstNonZero++;
       }
-      if (firstNonZero == coefficients.length) {
+      if (firstNonZero == coefficientsLength) {
         this.coefficients = field.getZero().coefficients;
       } else {
-        this.coefficients = new int[coefficients.length - firstNonZero];
+        this.coefficients = new int[coefficientsLength - firstNonZero];
         System.arraycopy(coefficients,
             firstNonZero,
             this.coefficients,
@@ -65,6 +66,10 @@ final class GF256Poly {
     }
   }
 
+  int[] getCoefficients() {
+    return coefficients;
+  }
+
   /**
    * @return degree of this polynomial
    */
@@ -99,34 +104,17 @@ final class GF256Poly {
       // Just the sum of the coefficients
       int result = 0;
       for (int i = 0; i < size; i++) {
-        result = field.addOrSubtract(result, coefficients[i]);
+        result = GF256.addOrSubtract(result, coefficients[i]);
       }
       return result;
     }
     int result = coefficients[0];
     for (int i = 1; i < size; i++) {
-      result = field.addOrSubtract(field.multiply(a, result), coefficients[i]);
+      result = GF256.addOrSubtract(field.multiply(a, result), coefficients[i]);
     }
     return result;
   }
 
-  int evaluateFormatDerivativeAt(int a) {
-    int degree = getDegree();
-    if (degree == 0) {
-      // Derivative of a constant is zero.
-      return 0;
-    }
-
-    int aToTheI = 1;
-    int sum = getCoefficient(1);
-    int aSquared = field.multiply(a, a);
-    for (int i = 2; i < degree; i += 2) {
-      aToTheI = field.multiply(aSquared, aToTheI);
-      sum = field.addOrSubtract(sum, field.multiply(aToTheI, getCoefficient(i + 1)));
-    }
-    return sum;
-  }
-
   GF256Poly addOrSubtract(GF256Poly other) {
     if (!field.equals(other.field)) {
       throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
@@ -151,7 +139,7 @@ final class GF256Poly {
     System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
 
     for (int i = lengthDiff; i < largerCoefficients.length; i++) {
-      sumDiff[i] = field.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
+      sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
     }
 
     return new GF256Poly(field, sumDiff);
@@ -172,7 +160,7 @@ final class GF256Poly {
     for (int i = 0; i < aLength; i++) {
       int aCoeff = aCoefficients[i];
       for (int j = 0; j < bLength; j++) {
-        product[i + j] = field.addOrSubtract(product[i + j],
+        product[i + j] = GF256.addOrSubtract(product[i + j],
             field.multiply(aCoeff, bCoefficients[j]));
       }
     }
@@ -188,9 +176,8 @@ final class GF256Poly {
     }
     int size = coefficients.length;
     int[] product = new int[size];
-    System.arraycopy(coefficients, 0, product, 0, size);
     for (int i = 0; i < size; i++) {
-      product[i] = field.multiply(product[i], scalar);
+      product[i] = field.multiply(coefficients[i], scalar);
     }
     return new GF256Poly(field, product);
   }
@@ -204,11 +191,73 @@ final class GF256Poly {
     }
     int size = coefficients.length;
     int[] product = new int[size + degree];
-    System.arraycopy(coefficients, 0, product, 0, size);
     for (int i = 0; i < size; i++) {
-      product[i] = field.multiply(product[i], coefficient);
+      product[i] = field.multiply(coefficients[i], coefficient);
     }
     return new GF256Poly(field, product);
   }
 
+  GF256Poly[] divide(GF256Poly other) {
+    if (!field.equals(other.field)) {
+      throw new IllegalArgumentException("GF256Polys do not have same GF256 field");
+    }
+    if (other.isZero()) {
+      throw new IllegalArgumentException("Divide by 0");
+    }
+
+    GF256Poly quotient = field.getZero();
+    GF256Poly remainder = this;
+
+    int denominatorLeadingTerm = other.getCoefficient(other.getDegree());
+    int inverseDenominatorLeadingTerm = field.inverse(denominatorLeadingTerm);
+
+    while (remainder.getDegree() >= other.getDegree() && !remainder.isZero()) {
+      int degreeDifference = remainder.getDegree() - other.getDegree();
+      int scale = field.multiply(remainder.getCoefficient(remainder.getDegree()), inverseDenominatorLeadingTerm);
+      GF256Poly term = other.multiplyByMonomial(degreeDifference, scale);
+      GF256Poly iterationQuotient = field.buildMonomial(degreeDifference, scale);
+      quotient = quotient.addOrSubtract(iterationQuotient);
+      remainder = remainder.addOrSubtract(term);
+    }
+
+    return new GF256Poly[] { quotient, remainder };
+  }
+
+  public String toString() {
+    StringBuffer result = new StringBuffer(8 * getDegree());
+    for (int degree = getDegree(); degree >= 0; degree--) {
+      int coefficient = getCoefficient(degree);
+      if (coefficient != 0) {
+        if (coefficient < 0) {
+          result.append(" - ");
+          coefficient = -coefficient;
+        } else {
+          if (result.length() > 0) {
+            result.append(" + ");
+          }
+        }
+        if (degree == 0 || coefficient != 1) {
+          int alphaPower = field.log(coefficient);
+          if (alphaPower == 0) {
+            result.append('1');
+          } else if (alphaPower == 1) {
+            result.append('a');
+          } else {
+            result.append("a^");
+            result.append(alphaPower);
+          }
+        }
+        if (degree != 0) {
+          if (degree == 1) {
+            result.append('x');
+          } else {
+            result.append("x^");
+            result.append(degree);
+          }
+        }
+      }
+    }
+    return result.toString();
+  }
+
 }