From: srowen Date: Wed, 12 Nov 2008 12:59:47 +0000 (+0000) Subject: Updates from sanfordsquires to fix RS decoding for Datamatrix X-Git-Url: http://git.rot13.org/?p=zxing.git;a=commitdiff_plain;h=d420554bc509d08feb59ac81cd48a10d3b5e6042 Updates from sanfordsquires to fix RS decoding for Datamatrix git-svn-id: http://zxing.googlecode.com/svn/trunk@688 59b500cc-1b3d-0410-9834-0bbf25fbcc57 --- diff --git a/AUTHORS b/AUTHORS index b1ab642d..f5a202f2 100644 --- a/AUTHORS +++ b/AUTHORS @@ -12,5 +12,6 @@ Joseph Wain (Google) Matthew Schulkind (Google) Matt York (LifeMarks) Paul Hackenberger +sanfordsquires (?) Sean Owen (Google) Vince Francis (LifeMarks) diff --git a/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java b/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java index 2d93c5ff..4c000d3d 100644 --- a/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java +++ b/core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java @@ -36,6 +36,7 @@ package com.google.zxing.common.reedsolomon; * * @author srowen@google.com (Sean Owen) * @author William Rucklidge + * @author sanfordsquires */ public final class ReedSolomonDecoder { @@ -52,16 +53,15 @@ public final class ReedSolomonDecoder { * * @param received data and error-correction codewords * @param twoS number of error-correction codewords available - * @param dataMatrix if true, then uses a calculation that matches the Data Matrix - * standard rather than the one used in QR Code * @throws ReedSolomonException if decoding fails for any reason */ - public void decode(int[] received, int twoS, boolean dataMatrix) throws ReedSolomonException { + 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++) { - // This difference in syndrome calculation appears to be correct, but then causes issues below + // 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) { @@ -72,19 +72,17 @@ public final class ReedSolomonDecoder { return; } GF256Poly syndrome = new GF256Poly(field, syndromeCoefficients); - if (dataMatrix) { - // TODO Not clear this is correct for DataMatrix, but it gives almost-correct behavior; - // works except when number of errors is the maximum allowable. - syndrome = syndrome.multiply(field.buildMonomial(1, 1)); - } 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); + 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]); } } @@ -165,7 +163,7 @@ public final class ReedSolomonDecoder { 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]; @@ -180,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; } diff --git a/core/src/com/google/zxing/datamatrix/decoder/Decoder.java b/core/src/com/google/zxing/datamatrix/decoder/Decoder.java index 65311761..f70ae45e 100644 --- a/core/src/com/google/zxing/datamatrix/decoder/Decoder.java +++ b/core/src/com/google/zxing/datamatrix/decoder/Decoder.java @@ -118,7 +118,7 @@ public final class Decoder { } int numECCodewords = codewordBytes.length - numDataCodewords; try { - rsDecoder.decode(codewordsInts, numECCodewords, true); + rsDecoder.decode(codewordsInts, numECCodewords); } catch (ReedSolomonException rse) { throw new ReaderException(rse.toString()); } diff --git a/core/src/com/google/zxing/qrcode/decoder/Decoder.java b/core/src/com/google/zxing/qrcode/decoder/Decoder.java index a8be9e88..0ee7954b 100644 --- a/core/src/com/google/zxing/qrcode/decoder/Decoder.java +++ b/core/src/com/google/zxing/qrcode/decoder/Decoder.java @@ -118,7 +118,7 @@ public final class Decoder { } int numECCodewords = codewordBytes.length - numDataCodewords; try { - rsDecoder.decode(codewordsInts, numECCodewords, false); + rsDecoder.decode(codewordsInts, numECCodewords); } catch (ReedSolomonException rse) { throw new ReaderException(rse.toString()); } diff --git a/core/test/src/com/google/zxing/common/reedsolomon/AbstractReedSolomonTestCase.java b/core/test/src/com/google/zxing/common/reedsolomon/AbstractReedSolomonTestCase.java new file mode 100644 index 00000000..6f7a615b --- /dev/null +++ b/core/test/src/com/google/zxing/common/reedsolomon/AbstractReedSolomonTestCase.java @@ -0,0 +1,42 @@ +/* + * Copyright 2008 ZXing authors + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.google.zxing.common.reedsolomon; + +import junit.framework.TestCase; + +import java.util.BitSet; +import java.util.Random; + +/** + * @author srowen@google.com (Sean Owen) + */ +abstract class AbstractReedSolomonTestCase extends TestCase { + + static void corrupt(int[] received, int howMany, Random random) { + BitSet corrupted = new BitSet(received.length); + for (int j = 0; j < howMany; j++) { + int location = random.nextInt(received.length); + if (corrupted.get(location)) { + j--; + } else { + corrupted.set(location); + received[location] = (received[location] + 1 + random.nextInt(255)) & 0xFF; + } + } + } + +} \ No newline at end of file diff --git a/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderDataMatrixTestCase.java b/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderDataMatrixTestCase.java index 657c8a46..a9bbd8cd 100644 --- a/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderDataMatrixTestCase.java +++ b/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderDataMatrixTestCase.java @@ -16,15 +16,13 @@ package com.google.zxing.common.reedsolomon; -import junit.framework.TestCase; - -import java.util.BitSet; import java.util.Random; /** * @author srowen@google.com (Sean Owen) + * @author sanfordsquires */ -public final class ReedSolomonDecoderDataMatrixTestCase extends TestCase { +public final class ReedSolomonDecoderDataMatrixTestCase extends AbstractReedSolomonTestCase { private static final int[] DM_CODE_TEST = { 142, 164, 186 }; private static final int[] DM_CODE_TEST_WITH_EC = { 142, 164, 186, 114, 25, 5, 88, 102 }; @@ -54,8 +52,7 @@ public final class ReedSolomonDecoderDataMatrixTestCase extends TestCase { Random random = new Random(0xDEADBEEFL); for (int i = 0; i < DM_CODE_TEST.length; i++) { // # iterations is kind of arbitrary System.arraycopy(DM_CODE_TEST_WITH_EC, 0, received, 0, received.length); - // TODO we aren't testing max errors really since there is a known bug here - corrupt(received, DM_CODE_CORRECTABLE - 1, random); + corrupt(received, DM_CODE_CORRECTABLE, random); checkQRRSDecode(received); } } @@ -74,23 +71,10 @@ public final class ReedSolomonDecoderDataMatrixTestCase extends TestCase { } private void checkQRRSDecode(int[] received) throws ReedSolomonException { - dmRSDecoder.decode(received, 2 * DM_CODE_CORRECTABLE, true); + dmRSDecoder.decode(received, 2 * DM_CODE_CORRECTABLE); for (int i = 0; i < DM_CODE_TEST.length; i++) { assertEquals(received[i], DM_CODE_TEST[i]); } } - private static void corrupt(int[] received, int howMany, Random random) { - BitSet corrupted = new BitSet(received.length); - for (int j = 0; j < howMany; j++) { - int location = random.nextInt(received.length); - if (corrupted.get(location)) { - j--; - } else { - corrupted.set(location); - int newByte = random.nextInt(256); - received[location] = newByte; - } - } - } } \ No newline at end of file diff --git a/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderQRCodeTestCase.java b/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderQRCodeTestCase.java index 3fb675e5..18a5b4cb 100644 --- a/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderQRCodeTestCase.java +++ b/core/test/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoderQRCodeTestCase.java @@ -16,15 +16,12 @@ package com.google.zxing.common.reedsolomon; -import junit.framework.TestCase; - -import java.util.BitSet; import java.util.Random; /** * @author srowen@google.com (Sean Owen) */ -public final class ReedSolomonDecoderQRCodeTestCase extends TestCase { +public final class ReedSolomonDecoderQRCodeTestCase extends AbstractReedSolomonTestCase { /** See ISO 18004, Appendix I, from which this example is taken. */ private static final int[] QR_CODE_TEST = @@ -79,23 +76,10 @@ public final class ReedSolomonDecoderQRCodeTestCase extends TestCase { } private void checkQRRSDecode(int[] received) throws ReedSolomonException { - qrRSDecoder.decode(received, 2*QR_CODE_CORRECTABLE, false); + qrRSDecoder.decode(received, 2*QR_CODE_CORRECTABLE); for (int i = 0; i < QR_CODE_TEST.length; i++) { assertEquals(received[i], QR_CODE_TEST[i]); } } - private static void corrupt(int[] received, int howMany, Random random) { - BitSet corrupted = new BitSet(received.length); - for (int j = 0; j < howMany; j++) { - int location = random.nextInt(received.length); - if (corrupted.get(location)) { - j--; - } else { - corrupted.set(location); - int newByte = random.nextInt(256); - received[location] = newByte; - } - } - } } \ No newline at end of file