From cea20855130df9761b7bbe3ab16c0e78207d77a4 Mon Sep 17 00:00:00 2001 From: srowen Date: Tue, 19 Feb 2008 16:14:34 +0000 Subject: [PATCH] Refactored Reed-Solomon so it can be used with different GF(256) primitive polynomials git-svn-id: http://zxing.googlecode.com/svn/trunk@209 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- .../zxing/common/reedsolomon/GF256.java | 62 ++++++++++++---- .../zxing/common/reedsolomon/GF256Poly.java | 74 ++++++++----------- .../reedsolomon/ReedSolomonDecoder.java | 55 +++++++------- .../com/google/zxing/qrcode/QRCodeReader.java | 6 +- .../google/zxing/qrcode/decoder/Decoder.java | 14 ++-- 5 files changed, 120 insertions(+), 91 deletions(-) diff --git a/core/src/com/google/zxing/common/reedsolomon/GF256.java b/core/src/com/google/zxing/common/reedsolomon/GF256.java index 2f4aa661..b2e88774 100644 --- a/core/src/com/google/zxing/common/reedsolomon/GF256.java +++ b/core/src/com/google/zxing/common/reedsolomon/GF256.java @@ -18,8 +18,7 @@ package com.google.zxing.common.reedsolomon; /** *

This class contains utility methods for performing mathematical operations over - * the Galois Field GF(256). Operations use the primitive polynomial - * x^8 + x^4 + x^3 + x^2 + 1 in calculations.

+ * the Galois Field GF(256). Operations use a given primitive polynomial in calculations.

* *

Throughout this package, elements of GF(256) are represented as an int * for convenience and speed (but at the cost of memory). @@ -27,28 +26,63 @@ package com.google.zxing.common.reedsolomon; * * @author srowen@google.com (Sean Owen) */ -final class GF256 { +public final class GF256 { - private static final int PRIMITIVE = 0x011D; - private static final int[] exp = new int[256]; - private static final int[] log = new int[256]; + public static final GF256 QR_CODE_FIELD = new GF256(0x011D); // x^8 + x^4 + x^3 + x^2 + 1 + public static final GF256 DATA_MATRIX_FIELD = new GF256(0x012D); // x^8 + x^5 + x^3 + x^2 + 1 - static { + private final int[] exp; + private final int[] log; + private final GF256Poly zero; + private final GF256Poly one; + + /** + * Create a representation of GF(256) using the given primitive polynomial. + * + * @param primitive irreducible polynomial whose coefficients are represented by + * the bits of an int, where the least-significant bit represents the constant + * coefficient + */ + private GF256(int primitive) { + exp = new int[256]; + log = new int[256]; int x = 1; for (int i = 0; i < 256; i++) { exp[i] = x; x <<= 1; // x = x * 2; we're assuming the generator alpha is 2 if (x >= 0x100) { - x ^= PRIMITIVE; + x ^= primitive; } } for (int i = 0; i < 255; i++) { log[exp[i]] = i; } // log[0] == 0 but this should never be used + zero = new GF256Poly(this, new int[]{0}); + one = new GF256Poly(this, new int[]{1}); } - private GF256() { + GF256Poly getZero() { + return zero; + } + + GF256Poly getOne() { + return one; + } + + /** + * @return the monomial representing coefficient * x^degree + */ + GF256Poly buildMonomial(int degree, int coefficient) { + if (degree < 0) { + throw new IllegalArgumentException(); + } + if (coefficient == 0) { + return zero; + } + int[] coefficients = new int[degree + 1]; + coefficients[0] = coefficient; + return new GF256Poly(this, coefficients); } /** @@ -56,21 +90,21 @@ final class GF256 { * * @return sum/difference of a and b */ - static int addOrSubtract(int a, int b) { + int addOrSubtract(int a, int b) { return a ^ b; } /** * @return 2 to the power of a in GF(256) */ - static int exp(int a) { + int exp(int a) { return exp[a]; } /** * @return base 2 log of a in GF(256) */ - static int log(int a) { + int log(int a) { if (a == 0) { throw new IllegalArgumentException(); } @@ -80,7 +114,7 @@ final class GF256 { /** * @return multiplicative inverse of a */ - static int inverse(int a) { + int inverse(int a) { if (a == 0) { throw new ArithmeticException(); } @@ -92,7 +126,7 @@ final class GF256 { * @param b * @return product of a and b in GF(256) */ - static int multiply(int a, int b) { + int multiply(int a, int b) { if (a == 0 || b == 0) { return 0; } diff --git a/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java b/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java index 280553ab..2c87a061 100644 --- a/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java +++ b/core/src/com/google/zxing/common/reedsolomon/GF256Poly.java @@ -27,28 +27,23 @@ package com.google.zxing.common.reedsolomon; */ final class GF256Poly { - /** - * Polynimal representing the monomial 0. - */ - static final GF256Poly ZERO = new GF256Poly(new int[]{0}); - /** - * Polynimal representing the monomial 1. - */ - static final GF256Poly ONE = new GF256Poly(new int[]{1}); - + private final GF256 field; private final int[] coefficients; /** + * @param field the {@link GF256} instance representing the field to use + * to perform computations * @param coefficients coefficients as ints representing elements of GF(256), arranged * from most significant (highest-power term) coefficient to least significant * @throws IllegalArgumentException if argument is null or empty, * or if leading coefficient is 0 and this is not a * constant polynomial (that is, it is not the monomial "0") */ - GF256Poly(int[] coefficients) { + GF256Poly(GF256 field, int[] coefficients) { if (coefficients == null || coefficients.length == 0) { throw new IllegalArgumentException(); } + this.field = field; if (coefficients.length > 1 && coefficients[0] == 0) { // Leading term must be non-zero for anything except the constant polynomial "0" int firstNonZero = 1; @@ -56,7 +51,7 @@ final class GF256Poly { firstNonZero++; } if (firstNonZero == coefficients.length) { - this.coefficients = ZERO.coefficients; + this.coefficients = field.getZero().coefficients; } else { this.coefficients = new int[coefficients.length - firstNonZero]; System.arraycopy(coefficients, @@ -84,21 +79,6 @@ final class GF256Poly { return coefficients[0] == 0; } - /** - * @return the monomial representing coefficient * x^degree - */ - static GF256Poly buildMonomial(int degree, int coefficient) { - if (degree < 0) { - throw new IllegalArgumentException(); - } - if (coefficient == 0) { - return ZERO; - } - int[] coefficients = new int[degree + 1]; - coefficients[0] = coefficient; - return new GF256Poly(coefficients); - } - /** * @return coefficient of x^degree term in this polynomial */ @@ -114,18 +94,18 @@ final class GF256Poly { // Just return the x^0 coefficient return getCoefficient(0); } - final int size = coefficients.length; + int size = coefficients.length; if (a == 1) { // Just the sum of the coefficients int result = 0; for (int i = 0; i < size; i++) { - result = GF256.addOrSubtract(result, coefficients[i]); + result = field.addOrSubtract(result, coefficients[i]); } return result; } int result = coefficients[0]; for (int i = 1; i < size; i++) { - result = GF256.addOrSubtract(GF256.multiply(a, result), coefficients[i]); + result = field.addOrSubtract(field.multiply(a, result), coefficients[i]); } return result; } @@ -139,15 +119,18 @@ final class GF256Poly { int aToTheI = 1; int sum = getCoefficient(1); - int aSquared = GF256.multiply(a, a); + int aSquared = field.multiply(a, a); for (int i = 2; i < degree; i += 2) { - aToTheI = GF256.multiply(aSquared, aToTheI); - sum = GF256.addOrSubtract(sum, GF256.multiply(aToTheI, getCoefficient(i + 1))); + 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"); + } if (isZero()) { return other; } @@ -168,15 +151,18 @@ final class GF256Poly { System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff); for (int i = lengthDiff; i < largerCoefficients.length; i++) { - sumDiff[i] = GF256.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]); + sumDiff[i] = field.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]); } - return new GF256Poly(sumDiff); + return new GF256Poly(field, sumDiff); } GF256Poly multiply(GF256Poly other) { + if (!field.equals(other.field)) { + throw new IllegalArgumentException("GF256Polys do not have same GF256 field"); + } if (isZero() || other.isZero()) { - return ZERO; + return field.getZero(); } int[] aCoefficients = this.coefficients; int aLength = aCoefficients.length; @@ -186,16 +172,16 @@ final class GF256Poly { for (int i = 0; i < aLength; i++) { int aCoeff = aCoefficients[i]; for (int j = 0; j < bLength; j++) { - product[i + j] = GF256.addOrSubtract(product[i + j], - GF256.multiply(aCoeff, bCoefficients[j])); + product[i + j] = field.addOrSubtract(product[i + j], + field.multiply(aCoeff, bCoefficients[j])); } } - return new GF256Poly(product); + return new GF256Poly(field, product); } GF256Poly multiply(int scalar) { if (scalar == 0) { - return ZERO; + return field.getZero(); } if (scalar == 1) { return this; @@ -204,9 +190,9 @@ final class GF256Poly { int[] product = new int[size]; System.arraycopy(coefficients, 0, product, 0, size); for (int i = 0; i < size; i++) { - product[i] = GF256.multiply(product[i], scalar); + product[i] = field.multiply(product[i], scalar); } - return new GF256Poly(product); + return new GF256Poly(field, product); } GF256Poly multiplyByMonomial(int degree, int coefficient) { @@ -214,15 +200,15 @@ final class GF256Poly { throw new IllegalArgumentException(); } if (coefficient == 0) { - return ZERO; + return field.getZero(); } 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] = GF256.multiply(product[i], coefficient); + product[i] = field.multiply(product[i], coefficient); } - return new GF256Poly(product); + return new GF256Poly(field, product); } } diff --git a/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java b/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java index a78783d1..39e81016 100644 --- a/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java +++ b/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java @@ -41,7 +41,10 @@ import java.util.Vector; */ public final class ReedSolomonDecoder { - private ReedSolomonDecoder() { + private final GF256 field; + + public ReedSolomonDecoder(GF256 field) { + this.field = field; } /** @@ -53,26 +56,26 @@ public final class ReedSolomonDecoder { * @param twoS number of error-correction codewords available * @throws ReedSolomonException if decoding fails for any reaosn */ - public static void decode(int[] received, int twoS) throws ReedSolomonException { - GF256Poly poly = new GF256Poly(received); + public void decode(int[] received, int twoS) throws ReedSolomonException { + GF256Poly poly = new GF256Poly(field, received); int[] syndromeCoefficients = new int[twoS]; for (int i = 0; i < twoS; i++) { - syndromeCoefficients[syndromeCoefficients.length - 1 - i] = poly.evaluateAt(GF256.exp(i)); + syndromeCoefficients[syndromeCoefficients.length - 1 - i] = poly.evaluateAt(field.exp(i)); } - GF256Poly syndrome = new GF256Poly(syndromeCoefficients); + GF256Poly syndrome = new GF256Poly(field, syndromeCoefficients); if (!syndrome.isZero()) { // Error GF256Poly[] sigmaOmega = - runEuclideanAlgorithm(GF256Poly.buildMonomial(twoS, 1), syndrome, twoS); + 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 - GF256.log(errorLocations[i]); - received[position] = GF256.addOrSubtract(received[position], errorMagnitudes[i]); + int position = received.length - 1 - field.log(errorLocations[i]); + received[position] = field.addOrSubtract(received[position], errorMagnitudes[i]); } } } - private static GF256Poly[] runEuclideanAlgorithm(GF256Poly a, GF256Poly b, int R) + private GF256Poly[] runEuclideanAlgorithm(GF256Poly a, GF256Poly b, int R) throws ReedSolomonException { // Assume a's degree is >= b's if (a.getDegree() < b.getDegree()) { @@ -83,10 +86,10 @@ public final class ReedSolomonDecoder { GF256Poly rLast = a; GF256Poly r = b; - GF256Poly sLast = GF256Poly.ONE; - GF256Poly s = GF256Poly.ZERO; - GF256Poly tLast = GF256Poly.ZERO; - GF256Poly t = GF256Poly.ONE; + GF256Poly sLast = field.getOne(); + GF256Poly s = field.getZero(); + GF256Poly tLast = field.getZero(); + GF256Poly t = field.getOne(); // Run Euclidean algorithm until r's degree is less than R/2 while (r.getDegree() >= R / 2) { @@ -103,13 +106,13 @@ public final class ReedSolomonDecoder { throw new ReedSolomonException("r_{i-1} was zero"); } r = rLastLast; - GF256Poly q = GF256Poly.ZERO; + GF256Poly q = field.getZero(); int denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree()); - int dltInverse = GF256.inverse(denominatorLeadingTerm); + int dltInverse = field.inverse(denominatorLeadingTerm); while (r.getDegree() >= rLast.getDegree() && !r.isZero()) { int degreeDiff = r.getDegree() - rLast.getDegree(); - int scale = GF256.multiply(r.getCoefficient(r.getDegree()), dltInverse); - q = q.addOrSubtract(GF256Poly.buildMonomial(degreeDiff, scale)); + int scale = field.multiply(r.getCoefficient(r.getDegree()), dltInverse); + q = q.addOrSubtract(field.buildMonomial(degreeDiff, scale)); r = r.addOrSubtract(rLast.multiplyByMonomial(degreeDiff, scale)); } @@ -122,19 +125,19 @@ public final class ReedSolomonDecoder { throw new ReedSolomonException("sigmaTilde(0) was zero"); } - int inverse = GF256.inverse(sigmaTildeAtZero); + int inverse = field.inverse(sigmaTildeAtZero); GF256Poly sigma = t.multiply(inverse); GF256Poly omega = r.multiply(inverse); return new GF256Poly[]{sigma, omega}; } - private static int[] findErrorLocations(GF256Poly errorLocator) + 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++) { if (errorLocator.evaluateAt(i) == 0) { - errorLocations.addElement(new Integer(GF256.inverse(i))); + errorLocations.addElement(new Integer(field.inverse(i))); } } if (errorLocations.size() != errorLocator.getDegree()) { @@ -147,22 +150,22 @@ public final class ReedSolomonDecoder { return result; } - private static int[] findErrorMagnitudes(GF256Poly errorEvaluator, + private int[] findErrorMagnitudes(GF256Poly errorEvaluator, int[] errorLocations) { // This is directly applying Forney's Formula int s = errorLocations.length; int[] result = new int[s]; for (int i = 0; i < errorLocations.length; i++) { - int xiInverse = GF256.inverse(errorLocations[i]); + int xiInverse = field.inverse(errorLocations[i]); int denominator = 1; for (int j = 0; j < s; j++) { if (i != j) { - denominator = GF256.multiply(denominator, - GF256.addOrSubtract(1, GF256.multiply(errorLocations[j], xiInverse))); + denominator = field.multiply(denominator, + field.addOrSubtract(1, field.multiply(errorLocations[j], xiInverse))); } } - result[i] = GF256.multiply(errorEvaluator.evaluateAt(xiInverse), - GF256.inverse(denominator)); + result[i] = field.multiply(errorEvaluator.evaluateAt(xiInverse), + field.inverse(denominator)); } return result; } diff --git a/core/src/com/google/zxing/qrcode/QRCodeReader.java b/core/src/com/google/zxing/qrcode/QRCodeReader.java index adece01a..7edea20c 100644 --- a/core/src/com/google/zxing/qrcode/QRCodeReader.java +++ b/core/src/com/google/zxing/qrcode/QRCodeReader.java @@ -38,6 +38,8 @@ public final class QRCodeReader implements Reader { private static final ResultPoint[] NO_POINTS = new ResultPoint[0]; + private final Decoder decoder = new Decoder(); + /** * Locates and decodes a QR code in an image. * @@ -54,11 +56,11 @@ public final class QRCodeReader implements Reader { ResultPoint[] points; if (hints != null && hints.containsKey(DecodeHintType.PURE_BARCODE)) { BitMatrix bits = extractPureBits(image); - text = Decoder.decode(bits); + text = decoder.decode(bits); points = NO_POINTS; } else { DetectorResult result = new Detector(image).detect(); - text = Decoder.decode(result.getBits()); + text = decoder.decode(result.getBits()); points = result.getPoints(); } return new Result(text, points); diff --git a/core/src/com/google/zxing/qrcode/decoder/Decoder.java b/core/src/com/google/zxing/qrcode/decoder/Decoder.java index 8279eeae..4f732457 100644 --- a/core/src/com/google/zxing/qrcode/decoder/Decoder.java +++ b/core/src/com/google/zxing/qrcode/decoder/Decoder.java @@ -18,6 +18,7 @@ package com.google.zxing.qrcode.decoder; import com.google.zxing.ReaderException; import com.google.zxing.common.BitMatrix; +import com.google.zxing.common.reedsolomon.GF256; import com.google.zxing.common.reedsolomon.ReedSolomonDecoder; import com.google.zxing.common.reedsolomon.ReedSolomonException; @@ -29,7 +30,10 @@ import com.google.zxing.common.reedsolomon.ReedSolomonException; */ public final class Decoder { - private Decoder() { + private final ReedSolomonDecoder rsDecoder; + + public Decoder() { + rsDecoder = new ReedSolomonDecoder(GF256.QR_CODE_FIELD); } /** @@ -40,7 +44,7 @@ public final class Decoder { * @return text encoded within the QR Code * @throws ReaderException if the QR Code cannot be decoded */ - public static String decode(boolean[][] image) throws ReaderException { + public String decode(boolean[][] image) throws ReaderException { int dimension = image.length; BitMatrix bits = new BitMatrix(dimension); for (int i = 0; i < dimension; i++) { @@ -60,7 +64,7 @@ public final class Decoder { * @return text encoded within the QR Code * @throws ReaderException if the QR Code cannot be decoded */ - public static String decode(BitMatrix bits) throws ReaderException { + public String decode(BitMatrix bits) throws ReaderException { // Construct a parser and read version, error-correction level BitMatrixParser parser = new BitMatrixParser(bits); @@ -103,7 +107,7 @@ public final class Decoder { * @param numDataCodewords number of codewords that are data bytes * @throws ReaderException if error correction fails */ - private static void correctErrors(byte[] codewordBytes, int numDataCodewords) throws ReaderException { + private void correctErrors(byte[] codewordBytes, int numDataCodewords) throws ReaderException { int numCodewords = codewordBytes.length; // First read into an array of ints int[] codewordsInts = new int[numCodewords]; @@ -112,7 +116,7 @@ public final class Decoder { } int numECCodewords = codewordBytes.length - numDataCodewords; try { - ReedSolomonDecoder.decode(codewordsInts, numECCodewords); + rsDecoder.decode(codewordsInts, numECCodewords); } catch (ReedSolomonException rse) { throw new ReaderException(rse.toString()); } -- 2.20.1