/**
* <p>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.</p>
+ * the Galois Field GF(256). Operations use a given primitive polynomial in calculations.</p>
*
* <p>Throughout this package, elements of GF(256) are represented as an <code>int</code>
* for convenience and speed (but at the cost of memory).
*
* @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);
}
/**
*
* @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();
}
/**
* @return multiplicative inverse of a
*/
- static int inverse(int a) {
+ int inverse(int a) {
if (a == 0) {
throw new ArithmeticException();
}
* @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;
}
*/
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;
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,
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
*/
// 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;
}
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;
}
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;
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;
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) {
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);
}
}
*/
public final class ReedSolomonDecoder {
- private ReedSolomonDecoder() {
+ private final GF256 field;
+
+ public ReedSolomonDecoder(GF256 field) {
+ this.field = field;
}
/**
* @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()) {
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) {
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));
}
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()) {
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;
}
private static final ResultPoint[] NO_POINTS = new ResultPoint[0];
+ private final Decoder decoder = new Decoder();
+
/**
* Locates and decodes a QR code in an image.
*
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);
\r
import com.google.zxing.ReaderException;\r
import com.google.zxing.common.BitMatrix;\r
+import com.google.zxing.common.reedsolomon.GF256;\r
import com.google.zxing.common.reedsolomon.ReedSolomonDecoder;\r
import com.google.zxing.common.reedsolomon.ReedSolomonException;\r
\r
*/\r
public final class Decoder {\r
\r
- private Decoder() {\r
+ private final ReedSolomonDecoder rsDecoder;\r
+\r
+ public Decoder() {\r
+ rsDecoder = new ReedSolomonDecoder(GF256.QR_CODE_FIELD);\r
}\r
\r
/**\r
* @return text encoded within the QR Code\r
* @throws ReaderException if the QR Code cannot be decoded\r
*/\r
- public static String decode(boolean[][] image) throws ReaderException {\r
+ public String decode(boolean[][] image) throws ReaderException {\r
int dimension = image.length;\r
BitMatrix bits = new BitMatrix(dimension);\r
for (int i = 0; i < dimension; i++) {\r
* @return text encoded within the QR Code\r
* @throws ReaderException if the QR Code cannot be decoded\r
*/\r
- public static String decode(BitMatrix bits) throws ReaderException {\r
+ public String decode(BitMatrix bits) throws ReaderException {\r
\r
// Construct a parser and read version, error-correction level\r
BitMatrixParser parser = new BitMatrixParser(bits);\r
* @param numDataCodewords number of codewords that are data bytes\r
* @throws ReaderException if error correction fails\r
*/\r
- private static void correctErrors(byte[] codewordBytes, int numDataCodewords) throws ReaderException {\r
+ private void correctErrors(byte[] codewordBytes, int numDataCodewords) throws ReaderException {\r
int numCodewords = codewordBytes.length;\r
// First read into an array of ints\r
int[] codewordsInts = new int[numCodewords];\r
}\r
int numECCodewords = codewordBytes.length - numDataCodewords;\r
try {\r
- ReedSolomonDecoder.decode(codewordsInts, numECCodewords);\r
+ rsDecoder.decode(codewordsInts, numECCodewords);\r
} catch (ReedSolomonException rse) {\r
throw new ReaderException(rse.toString());\r
}\r
projects / zxing.git / commitdiff