}
}
+ int[] getCoefficients() {
+ return coefficients;
+ }
+
/**
* @return degree of this polynomial
*/
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");
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();
+ }
+
}
--- /dev/null
+/*
+ * 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 java.util.Vector;
+
+/**
+ * <p>Implements Reed-Solomon enbcoding, as the name implies.</p>
+ *
+ * @author srowen@google.com (Sean Owen)
+ * @author William Rucklidge
+ */
+public final class ReedSolomonEncoder {
+
+ private final GF256 field;
+ private final Vector cachedGenerators;
+
+ public ReedSolomonEncoder(GF256 field) {
+ if (!GF256.QR_CODE_FIELD.equals(field)) {
+ throw new IllegalArgumentException("Only QR Code is supported at this time");
+ }
+ this.field = field;
+ this.cachedGenerators = new Vector();
+ cachedGenerators.addElement(new GF256Poly(field, new int[] { 1 }));
+ }
+
+ private GF256Poly buildGenerator(int degree) {
+ if (degree >= cachedGenerators.size()) {
+ GF256Poly lastGenerator = (GF256Poly) cachedGenerators.elementAt(cachedGenerators.size() - 1);
+ for (int d = cachedGenerators.size(); d <= degree; d++) {
+ GF256Poly nextGenerator = lastGenerator.multiply(new GF256Poly(field, new int[] { 1, field.exp(d - 1) }));
+ cachedGenerators.addElement(nextGenerator);
+ lastGenerator = nextGenerator;
+ }
+ }
+ return (GF256Poly) cachedGenerators.elementAt(degree);
+ }
+
+ public void encode(int[] toEncode, int ecBytes) {
+ int dataBytes = toEncode.length - ecBytes;
+ GF256Poly generator = buildGenerator(ecBytes);
+ int[] infoCoefficients = new int[dataBytes];
+ System.arraycopy(toEncode, 0, infoCoefficients, 0, dataBytes);
+ GF256Poly info = new GF256Poly(field, infoCoefficients);
+ info = info.multiplyByMonomial(ecBytes, 1);
+ GF256Poly remainder = info.divide(generator)[1];
+ System.arraycopy(remainder.getCoefficients(), 0, toEncode, dataBytes, ecBytes);
+ }
+
+}
}
}
+ static void doTestQRCodeEncoding(int[] dataBytes, int[] expectedECBytes) {
+ int[] toEncode = new int[dataBytes.length + expectedECBytes.length];
+ System.arraycopy(dataBytes, 0, toEncode, 0, dataBytes.length);
+ new ReedSolomonEncoder(GF256.QR_CODE_FIELD).encode(toEncode, expectedECBytes.length);
+ assertArraysEqual(dataBytes, 0, toEncode, 0, dataBytes.length);
+ assertArraysEqual(expectedECBytes, 0, toEncode, dataBytes.length, expectedECBytes.length);
+ }
+
+ private static void assertArraysEqual(int[] expected, int expectedOffset, int[] actual, int actualOffset, int length) {
+ for (int i = 0; i < length; i++) {
+ assertEquals(expected[expectedOffset + i], actual[actualOffset + i]);
+ }
+ }
+
}
\ No newline at end of file
--- /dev/null
+/*
+ * 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;
+
+/**
+ * @author srowen@google.com (Sean Owen)
+ */
+public final class ReedSolomonEncoderQRCodeTestCase extends AbstractReedSolomonTestCase {
+
+ /**
+ * Tests example given in ISO 18004, Annex I
+ */
+ public void testISO18004Example() {
+ int[] dataBytes = new int[] {
+ 0x10, 0x20, 0x0C, 0x56, 0x61, 0x80, 0xEC, 0x11,
+ 0xEC, 0x11, 0xEC, 0x11, 0xEC, 0x11, 0xEC, 0x11 };
+ int[] expectedECBytes = new int[] {
+ 0xA5, 0x24, 0xD4, 0xC1, 0xED, 0x36, 0xC7, 0x87,
+ 0x2C, 0x55 };
+ doTestQRCodeEncoding(dataBytes, expectedECBytes);
+ }
+
+ // Need more tests I am sure
+
+}
projects / zxing.git / commitdiff