Updates from sanfordsquires to fix RS decoding for Datamatrix

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

diff --git a/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java b/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java
index 4cb00fb..4c000d3 100644 (file)
--- a/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java
+++ b/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.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.
@@ -16,8 +16,6 @@
 
 package com.google.zxing.common.reedsolomon;
 
-import java.util.Vector;
-
 /**
  * <p>Implements Reed-Solomon decoding, as the name implies.</p>
  *
@@ -38,6 +36,7 @@ import java.util.Vector;
  *
  * @author srowen@google.com (Sean Owen)
  * @author William Rucklidge
+ * @author sanfordsquires
  */
 public final class ReedSolomonDecoder {
 
@@ -54,24 +53,37 @@ public final class ReedSolomonDecoder {
    *
    * @param received data and error-correction codewords
    * @param twoS number of error-correction codewords available
-   * @throws ReedSolomonException if decoding fails for any reaosn
+   * @throws ReedSolomonException if decoding fails for any reason
    */
   public void decode(int[] received, int twoS) throws ReedSolomonException {
     GF256Poly poly = new GF256Poly(field, received);
     int[] syndromeCoefficients = new int[twoS];
+    boolean dataMatrix = field.equals(GF256.DATA_MATRIX_FIELD);
+    boolean noError = true;
     for (int i = 0; i < twoS; i++) {
-      syndromeCoefficients[syndromeCoefficients.length - 1 - i] = poly.evaluateAt(field.exp(i));
+      // Thanks to sanfordsquires for this fix:
+      int eval = poly.evaluateAt(field.exp(dataMatrix ? i + 1 : i));
+      syndromeCoefficients[syndromeCoefficients.length - 1 - i] = eval;
+      if (eval != 0) {
+        noError = false;
+      }
+    }
+    if (noError) {
+      return;
     }
     GF256Poly syndrome = new GF256Poly(field, syndromeCoefficients);
-    if (!syndrome.isZero()) { // Error
-      GF256Poly[] sigmaOmega =
-          runEuclideanAlgorithm(field.buildMonomial(twoS, 1), syndrome, twoS);
-      int[] errorLocations = findErrorLocations(sigmaOmega[0]);
-      int[] errorMagnitudes = findErrorMagnitudes(sigmaOmega[1], errorLocations);
-      for (int i = 0; i < errorLocations.length; i++) {
-        int position = received.length - 1 - field.log(errorLocations[i]);
-        received[position] = GF256.addOrSubtract(received[position], errorMagnitudes[i]);
+    GF256Poly[] sigmaOmega =
+        runEuclideanAlgorithm(field.buildMonomial(twoS, 1), syndrome, twoS);
+    GF256Poly sigma = sigmaOmega[0];
+    GF256Poly omega = sigmaOmega[1];
+    int[] errorLocations = findErrorLocations(sigma);
+    int[] errorMagnitudes = findErrorMagnitudes(omega, errorLocations, dataMatrix);
+    for (int i = 0; i < errorLocations.length; i++) {
+      int position = received.length - 1 - field.log(errorLocations[i]);
+      if (position < 0) {
+        throw new ReedSolomonException("Bad error location");
       }
+      received[position] = GF256.addOrSubtract(received[position], errorMagnitudes[i]);
     }
   }
 
@@ -131,31 +143,31 @@ public final class ReedSolomonDecoder {
     return new GF256Poly[]{sigma, omega};
   }
 
-  private int[] findErrorLocations(GF256Poly errorLocator)
-      throws ReedSolomonException {
+  private int[] findErrorLocations(GF256Poly errorLocator) throws ReedSolomonException {
     // This is a direct application of Chien's search
-    Vector errorLocations = new Vector(3);
-    for (int i = 1; i < 256; i++) {
+    int numErrors = errorLocator.getDegree();
+    if (numErrors == 1) { // shortcut
+      return new int[] { errorLocator.getCoefficient(1) };
+    }
+    int[] result = new int[numErrors];
+    int e = 0;
+    for (int i = 1; i < 256 && e < numErrors; i++) {
       if (errorLocator.evaluateAt(i) == 0) {
-        errorLocations.addElement(new Integer(field.inverse(i)));
+        result[e] = field.inverse(i);
+        e++;
       }
     }
-    if (errorLocations.size() != errorLocator.getDegree()) {
+    if (e != numErrors) {
       throw new ReedSolomonException("Error locator degree does not match number of roots");
     }
-    int[] result = new int[errorLocations.size()]; // Can't use toArray() here
-    for (int i = 0; i < result.length; i++) {
-      result[i] = ((Integer) errorLocations.elementAt(i)).intValue();
-    }
     return result;
   }
 
-  private int[] findErrorMagnitudes(GF256Poly errorEvaluator,
-                                           int[] errorLocations) {
+  private int[] findErrorMagnitudes(GF256Poly errorEvaluator, int[] errorLocations, boolean dataMatrix) {
     // This is directly applying Forney's Formula
     int s = errorLocations.length;
     int[] result = new int[s];
-    for (int i = 0; i < errorLocations.length; i++) {
+    for (int i = 0; i < s; i++) {
       int xiInverse = field.inverse(errorLocations[i]);
       int denominator = 1;
       for (int j = 0; j < s; j++) {
@@ -166,6 +178,10 @@ public final class ReedSolomonDecoder {
       }
       result[i] = field.multiply(errorEvaluator.evaluateAt(xiInverse),
           field.inverse(denominator));
+      // Thanks to sanfordsquires for this fix:
+      if (dataMatrix) {
+        result[i] = field.multiply(result[i], xiInverse);
+      }
     }
     return result;
   }