aboutsummaryrefslogtreecommitdiffstats
path: root/libraries/zxing/src/com/google/zxing/common
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/zxing/src/com/google/zxing/common')
-rw-r--r--libraries/zxing/src/com/google/zxing/common/BitArray.java246
-rw-r--r--libraries/zxing/src/com/google/zxing/common/BitMatrix.java247
-rw-r--r--libraries/zxing/src/com/google/zxing/common/BitSource.java97
-rw-r--r--libraries/zxing/src/com/google/zxing/common/CharacterSetECI.java110
-rw-r--r--libraries/zxing/src/com/google/zxing/common/Collections.java53
-rw-r--r--libraries/zxing/src/com/google/zxing/common/Comparator.java27
-rw-r--r--libraries/zxing/src/com/google/zxing/common/DecoderResult.java61
-rw-r--r--libraries/zxing/src/com/google/zxing/common/DefaultGridSampler.java86
-rw-r--r--libraries/zxing/src/com/google/zxing/common/DetectorResult.java46
-rw-r--r--libraries/zxing/src/com/google/zxing/common/ECI.java52
-rw-r--r--libraries/zxing/src/com/google/zxing/common/GlobalHistogramBinarizer.java194
-rw-r--r--libraries/zxing/src/com/google/zxing/common/GridSampler.java156
-rw-r--r--libraries/zxing/src/com/google/zxing/common/HybridBinarizer.java185
-rw-r--r--libraries/zxing/src/com/google/zxing/common/PerspectiveTransform.java148
-rw-r--r--libraries/zxing/src/com/google/zxing/common/StringUtils.java192
-rw-r--r--libraries/zxing/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java209
-rw-r--r--libraries/zxing/src/com/google/zxing/common/detector/WhiteRectangleDetector.java347
-rw-r--r--libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGF.java188
-rw-r--r--libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGFPoly.java263
-rw-r--r--libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java194
-rw-r--r--libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonEncoder.java75
-rw-r--r--libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonException.java31
22 files changed, 3207 insertions, 0 deletions
diff --git a/libraries/zxing/src/com/google/zxing/common/BitArray.java b/libraries/zxing/src/com/google/zxing/common/BitArray.java
new file mode 100644
index 000000000..6eb0d57c6
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/BitArray.java
@@ -0,0 +1,246 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>A simple, fast array of bits, represented compactly by an array of ints internally.</p>
+ *
+ * @author Sean Owen
+ */
+public final class BitArray {
+ // I have changed these members to be public so ProGuard can inline get() and set(). Ideally
+ // they'd be private and we'd use the -allowaccessmodification flag, but Dalvik rejects the
+ // resulting binary at runtime on Android. If we find a solution to this, these should be changed
+ // back to private.
+ public int[] bits;
+ public int size;
+
+ public BitArray() {
+ this.size = 0;
+ this.bits = new int[1];
+ }
+
+ public BitArray(int size) {
+ this.size = size;
+ this.bits = makeArray(size);
+ }
+
+ public int getSize() {
+ return size;
+ }
+
+ public int getSizeInBytes() {
+ return (size + 7) >> 3;
+ }
+
+ private void ensureCapacity(int size) {
+ if (size > bits.length << 5) {
+ int[] newBits = makeArray(size);
+ System.arraycopy(bits, 0, newBits, 0, bits.length);
+ this.bits = newBits;
+ }
+ }
+
+ /**
+ * @param i bit to get
+ * @return true iff bit i is set
+ */
+ public boolean get(int i) {
+ return (bits[i >> 5] & (1 << (i & 0x1F))) != 0;
+ }
+
+ /**
+ * Sets bit i.
+ *
+ * @param i bit to set
+ */
+ public void set(int i) {
+ bits[i >> 5] |= 1 << (i & 0x1F);
+ }
+
+ /**
+ * Flips bit i.
+ *
+ * @param i bit to set
+ */
+ public void flip(int i) {
+ bits[i >> 5] ^= 1 << (i & 0x1F);
+ }
+
+ /**
+ * Sets a block of 32 bits, starting at bit i.
+ *
+ * @param i first bit to set
+ * @param newBits the new value of the next 32 bits. Note again that the least-significant bit
+ * corresponds to bit i, the next-least-significant to i+1, and so on.
+ */
+ public void setBulk(int i, int newBits) {
+ bits[i >> 5] = newBits;
+ }
+
+ /**
+ * Clears all bits (sets to false).
+ */
+ public void clear() {
+ int max = bits.length;
+ for (int i = 0; i < max; i++) {
+ bits[i] = 0;
+ }
+ }
+
+ /**
+ * Efficient method to check if a range of bits is set, or not set.
+ *
+ * @param start start of range, inclusive.
+ * @param end end of range, exclusive
+ * @param value if true, checks that bits in range are set, otherwise checks that they are not set
+ * @return true iff all bits are set or not set in range, according to value argument
+ * @throws IllegalArgumentException if end is less than or equal to start
+ */
+ public boolean isRange(int start, int end, boolean value) {
+ if (end < start) {
+ throw new IllegalArgumentException();
+ }
+ if (end == start) {
+ return true; // empty range matches
+ }
+ end--; // will be easier to treat this as the last actually set bit -- inclusive
+ int firstInt = start >> 5;
+ int lastInt = end >> 5;
+ for (int i = firstInt; i <= lastInt; i++) {
+ int firstBit = i > firstInt ? 0 : start & 0x1F;
+ int lastBit = i < lastInt ? 31 : end & 0x1F;
+ int mask;
+ if (firstBit == 0 && lastBit == 31) {
+ mask = -1;
+ } else {
+ mask = 0;
+ for (int j = firstBit; j <= lastBit; j++) {
+ mask |= 1 << j;
+ }
+ }
+
+ // Return false if we're looking for 1s and the masked bits[i] isn't all 1s (that is,
+ // equals the mask, or we're looking for 0s and the masked portion is not all 0s
+ if ((bits[i] & mask) != (value ? mask : 0)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public void appendBit(boolean bit) {
+ ensureCapacity(size + 1);
+ if (bit) {
+ bits[size >> 5] |= (1 << (size & 0x1F));
+ }
+ size++;
+ }
+
+ /**
+ * Appends the least-significant bits, from value, in order from most-significant to
+ * least-significant. For example, appending 6 bits from 0x000001E will append the bits
+ * 0, 1, 1, 1, 1, 0 in that order.
+ */
+ public void appendBits(int value, int numBits) {
+ if (numBits < 0 || numBits > 32) {
+ throw new IllegalArgumentException("Num bits must be between 0 and 32");
+ }
+ ensureCapacity(size + numBits);
+ for (int numBitsLeft = numBits; numBitsLeft > 0; numBitsLeft--) {
+ appendBit(((value >> (numBitsLeft - 1)) & 0x01) == 1);
+ }
+ }
+
+ public void appendBitArray(BitArray other) {
+ int otherSize = other.getSize();
+ ensureCapacity(size + otherSize);
+ for (int i = 0; i < otherSize; i++) {
+ appendBit(other.get(i));
+ }
+ }
+
+ public void xor(BitArray other) {
+ if (bits.length != other.bits.length) {
+ throw new IllegalArgumentException("Sizes don't match");
+ }
+ for (int i = 0; i < bits.length; i++) {
+ // The last byte could be incomplete (i.e. not have 8 bits in
+ // it) but there is no problem since 0 XOR 0 == 0.
+ bits[i] ^= other.bits[i];
+ }
+ }
+
+ /**
+ *
+ * @param bitOffset first bit to start writing
+ * @param array array to write into. Bytes are written most-significant byte first. This is the opposite
+ * of the internal representation, which is exposed by {@link #getBitArray()}
+ * @param offset position in array to start writing
+ * @param numBytes how many bytes to write
+ */
+ public void toBytes(int bitOffset, byte[] array, int offset, int numBytes) {
+ for (int i = 0; i < numBytes; i++) {
+ int theByte = 0;
+ for (int j = 0; j < 8; j++) {
+ if (get(bitOffset)) {
+ theByte |= 1 << (7 - j);
+ }
+ bitOffset++;
+ }
+ array[offset + i] = (byte) theByte;
+ }
+ }
+
+ /**
+ * @return underlying array of ints. The first element holds the first 32 bits, and the least
+ * significant bit is bit 0.
+ */
+ public int[] getBitArray() {
+ return bits;
+ }
+
+ /**
+ * Reverses all bits in the array.
+ */
+ public void reverse() {
+ int[] newBits = new int[bits.length];
+ int size = this.size;
+ for (int i = 0; i < size; i++) {
+ if (get(size - i - 1)) {
+ newBits[i >> 5] |= 1 << (i & 0x1F);
+ }
+ }
+ bits = newBits;
+ }
+
+ private static int[] makeArray(int size) {
+ return new int[(size + 31) >> 5];
+ }
+
+ public String toString() {
+ StringBuffer result = new StringBuffer(size);
+ for (int i = 0; i < size; i++) {
+ if ((i & 0x07) == 0) {
+ result.append(' ');
+ }
+ result.append(get(i) ? 'X' : '.');
+ }
+ return result.toString();
+ }
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/BitMatrix.java b/libraries/zxing/src/com/google/zxing/common/BitMatrix.java
new file mode 100644
index 000000000..8bf75b289
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/BitMatrix.java
@@ -0,0 +1,247 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>Represents a 2D matrix of bits. In function arguments below, and throughout the common
+ * module, x is the column position, and y is the row position. The ordering is always x, y.
+ * The origin is at the top-left.</p>
+ *
+ * <p>Internally the bits are represented in a 1-D array of 32-bit ints. However, each row begins
+ * with a new int. This is done intentionally so that we can copy out a row into a BitArray very
+ * efficiently.</p>
+ *
+ * <p>The ordering of bits is row-major. Within each int, the least significant bits are used first,
+ * meaning they represent lower x values. This is compatible with BitArray's implementation.</p>
+ *
+ * @author Sean Owen
+ * @author dswitkin@google.com (Daniel Switkin)
+ */
+public final class BitMatrix {
+ // Just like BitArray, these need to be public so ProGuard can inline them.
+ public final int width;
+ public final int height;
+ public final int rowSize;
+ public final int[] bits;
+
+ // A helper to construct a square matrix.
+ public BitMatrix(int dimension) {
+ this(dimension, dimension);
+ }
+
+ public BitMatrix(int width, int height) {
+ if (width < 1 || height < 1) {
+ throw new IllegalArgumentException("Both dimensions must be greater than 0");
+ }
+ this.width = width;
+ this.height = height;
+ this.rowSize = (width + 31) >> 5;
+ bits = new int[rowSize * height];
+ }
+
+ /**
+ * <p>Gets the requested bit, where true means black.</p>
+ *
+ * @param x The horizontal component (i.e. which column)
+ * @param y The vertical component (i.e. which row)
+ * @return value of given bit in matrix
+ */
+ public boolean get(int x, int y) {
+ int offset = y * rowSize + (x >> 5);
+ return ((bits[offset] >>> (x & 0x1f)) & 1) != 0;
+ }
+
+ /**
+ * <p>Sets the given bit to true.</p>
+ *
+ * @param x The horizontal component (i.e. which column)
+ * @param y The vertical component (i.e. which row)
+ */
+ public void set(int x, int y) {
+ int offset = y * rowSize + (x >> 5);
+ bits[offset] |= 1 << (x & 0x1f);
+ }
+
+ /**
+ * <p>Flips the given bit.</p>
+ *
+ * @param x The horizontal component (i.e. which column)
+ * @param y The vertical component (i.e. which row)
+ */
+ public void flip(int x, int y) {
+ int offset = y * rowSize + (x >> 5);
+ bits[offset] ^= 1 << (x & 0x1f);
+ }
+
+ /**
+ * Clears all bits (sets to false).
+ */
+ public void clear() {
+ int max = bits.length;
+ for (int i = 0; i < max; i++) {
+ bits[i] = 0;
+ }
+ }
+
+ /**
+ * <p>Sets a square region of the bit matrix to true.</p>
+ *
+ * @param left The horizontal position to begin at (inclusive)
+ * @param top The vertical position to begin at (inclusive)
+ * @param width The width of the region
+ * @param height The height of the region
+ */
+ public void setRegion(int left, int top, int width, int height) {
+ if (top < 0 || left < 0) {
+ throw new IllegalArgumentException("Left and top must be nonnegative");
+ }
+ if (height < 1 || width < 1) {
+ throw new IllegalArgumentException("Height and width must be at least 1");
+ }
+ int right = left + width;
+ int bottom = top + height;
+ if (bottom > this.height || right > this.width) {
+ throw new IllegalArgumentException("The region must fit inside the matrix");
+ }
+ for (int y = top; y < bottom; y++) {
+ int offset = y * rowSize;
+ for (int x = left; x < right; x++) {
+ bits[offset + (x >> 5)] |= 1 << (x & 0x1f);
+ }
+ }
+ }
+
+ /**
+ * A fast method to retrieve one row of data from the matrix as a BitArray.
+ *
+ * @param y The row to retrieve
+ * @param row An optional caller-allocated BitArray, will be allocated if null or too small
+ * @return The resulting BitArray - this reference should always be used even when passing
+ * your own row
+ */
+ public BitArray getRow(int y, BitArray row) {
+ if (row == null || row.getSize() < width) {
+ row = new BitArray(width);
+ }
+ int offset = y * rowSize;
+ for (int x = 0; x < rowSize; x++) {
+ row.setBulk(x << 5, bits[offset + x]);
+ }
+ return row;
+ }
+
+ /**
+ * This is useful in detecting a corner of a 'pure' barcode.
+ *
+ * @return {x,y} coordinate of top-left-most 1 bit, or null if it is all white
+ */
+ public int[] getTopLeftOnBit() {
+ int bitsOffset = 0;
+ while (bitsOffset < bits.length && bits[bitsOffset] == 0) {
+ bitsOffset++;
+ }
+ if (bitsOffset == bits.length) {
+ return null;
+ }
+ int y = bitsOffset / rowSize;
+ int x = (bitsOffset % rowSize) << 5;
+
+ int theBits = bits[bitsOffset];
+ int bit = 0;
+ while ((theBits << (31-bit)) == 0) {
+ bit++;
+ }
+ x += bit;
+ return new int[] {x, y};
+ }
+
+ public int[] getBottomRightOnBit() {
+ int bitsOffset = bits.length - 1;
+ while (bitsOffset >= 0 && bits[bitsOffset] == 0) {
+ bitsOffset--;
+ }
+ if (bitsOffset < 0) {
+ return null;
+ }
+
+ int y = bitsOffset / rowSize;
+ int x = (bitsOffset % rowSize) << 5;
+
+ int theBits = bits[bitsOffset];
+ int bit = 31;
+ while ((theBits >>> bit) == 0) {
+ bit--;
+ }
+ x += bit;
+
+ return new int[] {x, y};
+ }
+
+ /**
+ * @return The width of the matrix
+ */
+ public int getWidth() {
+ return width;
+ }
+
+ /**
+ * @return The height of the matrix
+ */
+ public int getHeight() {
+ return height;
+ }
+
+ public boolean equals(Object o) {
+ if (!(o instanceof BitMatrix)) {
+ return false;
+ }
+ BitMatrix other = (BitMatrix) o;
+ if (width != other.width || height != other.height ||
+ rowSize != other.rowSize || bits.length != other.bits.length) {
+ return false;
+ }
+ for (int i = 0; i < bits.length; i++) {
+ if (bits[i] != other.bits[i]) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ public int hashCode() {
+ int hash = width;
+ hash = 31 * hash + width;
+ hash = 31 * hash + height;
+ hash = 31 * hash + rowSize;
+ for (int i = 0; i < bits.length; i++) {
+ hash = 31 * hash + bits[i];
+ }
+ return hash;
+ }
+
+ public String toString() {
+ StringBuffer result = new StringBuffer(height * (width + 1));
+ for (int y = 0; y < height; y++) {
+ for (int x = 0; x < width; x++) {
+ result.append(get(x, y) ? "X " : " ");
+ }
+ result.append('\n');
+ }
+ return result.toString();
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/BitSource.java b/libraries/zxing/src/com/google/zxing/common/BitSource.java
new file mode 100644
index 000000000..a61ac5105
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/BitSource.java
@@ -0,0 +1,97 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>This provides an easy abstraction to read bits at a time from a sequence of bytes, where the
+ * number of bits read is not often a multiple of 8.</p>
+ *
+ * <p>This class is thread-safe but not reentrant. Unless the caller modifies the bytes array
+ * it passed in, in which case all bets are off.</p>
+ *
+ * @author Sean Owen
+ */
+public final class BitSource {
+
+ private final byte[] bytes;
+ private int byteOffset;
+ private int bitOffset;
+
+ /**
+ * @param bytes bytes from which this will read bits. Bits will be read from the first byte first.
+ * Bits are read within a byte from most-significant to least-significant bit.
+ */
+ public BitSource(byte[] bytes) {
+ this.bytes = bytes;
+ }
+
+ /**
+ * @param numBits number of bits to read
+ * @return int representing the bits read. The bits will appear as the least-significant
+ * bits of the int
+ * @throws IllegalArgumentException if numBits isn't in [1,32]
+ */
+ public int readBits(int numBits) {
+ if (numBits < 1 || numBits > 32) {
+ throw new IllegalArgumentException();
+ }
+
+ int result = 0;
+
+ // First, read remainder from current byte
+ if (bitOffset > 0) {
+ int bitsLeft = 8 - bitOffset;
+ int toRead = numBits < bitsLeft ? numBits : bitsLeft;
+ int bitsToNotRead = bitsLeft - toRead;
+ int mask = (0xFF >> (8 - toRead)) << bitsToNotRead;
+ result = (bytes[byteOffset] & mask) >> bitsToNotRead;
+ numBits -= toRead;
+ bitOffset += toRead;
+ if (bitOffset == 8) {
+ bitOffset = 0;
+ byteOffset++;
+ }
+ }
+
+ // Next read whole bytes
+ if (numBits > 0) {
+ while (numBits >= 8) {
+ result = (result << 8) | (bytes[byteOffset] & 0xFF);
+ byteOffset++;
+ numBits -= 8;
+ }
+
+ // Finally read a partial byte
+ if (numBits > 0) {
+ int bitsToNotRead = 8 - numBits;
+ int mask = (0xFF >> bitsToNotRead) << bitsToNotRead;
+ result = (result << numBits) | ((bytes[byteOffset] & mask) >> bitsToNotRead);
+ bitOffset += numBits;
+ }
+ }
+
+ return result;
+ }
+
+ /**
+ * @return number of bits that can be read successfully
+ */
+ public int available() {
+ return 8 * (bytes.length - byteOffset) - bitOffset;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/CharacterSetECI.java b/libraries/zxing/src/com/google/zxing/common/CharacterSetECI.java
new file mode 100644
index 000000000..42b7fa9f6
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/CharacterSetECI.java
@@ -0,0 +1,110 @@
+/*
+ * 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;
+
+import java.util.Hashtable;
+
+/**
+ * Encapsulates a Character Set ECI, according to "Extended Channel Interpretations" 5.3.1.1
+ * of ISO 18004.
+ *
+ * @author Sean Owen
+ */
+public final class CharacterSetECI extends ECI {
+
+ private static Hashtable VALUE_TO_ECI;
+ private static Hashtable NAME_TO_ECI;
+
+ private static void initialize() {
+ VALUE_TO_ECI = new Hashtable(29);
+ NAME_TO_ECI = new Hashtable(29);
+ // TODO figure out if these values are even right!
+ addCharacterSet(0, "Cp437");
+ addCharacterSet(1, new String[] {"ISO8859_1", "ISO-8859-1"});
+ addCharacterSet(2, "Cp437");
+ addCharacterSet(3, new String[] {"ISO8859_1", "ISO-8859-1"});
+ addCharacterSet(4, "ISO8859_2");
+ addCharacterSet(5, "ISO8859_3");
+ addCharacterSet(6, "ISO8859_4");
+ addCharacterSet(7, "ISO8859_5");
+ addCharacterSet(8, "ISO8859_6");
+ addCharacterSet(9, "ISO8859_7");
+ addCharacterSet(10, "ISO8859_8");
+ addCharacterSet(11, "ISO8859_9");
+ addCharacterSet(12, "ISO8859_10");
+ addCharacterSet(13, "ISO8859_11");
+ addCharacterSet(15, "ISO8859_13");
+ addCharacterSet(16, "ISO8859_14");
+ addCharacterSet(17, "ISO8859_15");
+ addCharacterSet(18, "ISO8859_16");
+ addCharacterSet(20, new String[] {"SJIS", "Shift_JIS"});
+ }
+
+ private final String encodingName;
+
+ private CharacterSetECI(int value, String encodingName) {
+ super(value);
+ this.encodingName = encodingName;
+ }
+
+ public String getEncodingName() {
+ return encodingName;
+ }
+
+ private static void addCharacterSet(int value, String encodingName) {
+ CharacterSetECI eci = new CharacterSetECI(value, encodingName);
+ VALUE_TO_ECI.put(new Integer(value), eci); // can't use valueOf
+ NAME_TO_ECI.put(encodingName, eci);
+ }
+
+ private static void addCharacterSet(int value, String[] encodingNames) {
+ CharacterSetECI eci = new CharacterSetECI(value, encodingNames[0]);
+ VALUE_TO_ECI.put(new Integer(value), eci); // can't use valueOf
+ for (int i = 0; i < encodingNames.length; i++) {
+ NAME_TO_ECI.put(encodingNames[i], eci);
+ }
+ }
+
+ /**
+ * @param value character set ECI value
+ * @return CharacterSetECI representing ECI of given value, or null if it is legal but
+ * unsupported
+ * @throws IllegalArgumentException if ECI value is invalid
+ */
+ public static CharacterSetECI getCharacterSetECIByValue(int value) {
+ if (VALUE_TO_ECI == null) {
+ initialize();
+ }
+ if (value < 0 || value >= 900) {
+ throw new IllegalArgumentException("Bad ECI value: " + value);
+ }
+ return (CharacterSetECI) VALUE_TO_ECI.get(new Integer(value));
+ }
+
+ /**
+ * @param name character set ECI encoding name
+ * @return CharacterSetECI representing ECI for character encoding, or null if it is legal
+ * but unsupported
+ */
+ public static CharacterSetECI getCharacterSetECIByName(String name) {
+ if (NAME_TO_ECI == null) {
+ initialize();
+ }
+ return (CharacterSetECI) NAME_TO_ECI.get(name);
+ }
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/Collections.java b/libraries/zxing/src/com/google/zxing/common/Collections.java
new file mode 100644
index 000000000..319ebfe6d
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/Collections.java
@@ -0,0 +1,53 @@
+/*
+ * 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.
+ * 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;
+
+import java.util.Vector;
+
+/**
+ * <p>This is basically a substitute for <code>java.util.Collections</code>, which is not
+ * present in MIDP 2.0 / CLDC 1.1.</p>
+ *
+ * @author Sean Owen
+ */
+public final class Collections {
+
+ private Collections() {
+ }
+
+ /**
+ * Sorts its argument (destructively) using insert sort; in the context of this package
+ * insertion sort is simple and efficient given its relatively small inputs.
+ *
+ * @param vector vector to sort
+ * @param comparator comparator to define sort ordering
+ */
+ public static void insertionSort(Vector vector, Comparator comparator) {
+ int max = vector.size();
+ for (int i = 1; i < max; i++) {
+ Object value = vector.elementAt(i);
+ int j = i - 1;
+ Object valueB;
+ while (j >= 0 && comparator.compare((valueB = vector.elementAt(j)), value) > 0) {
+ vector.setElementAt(valueB, j + 1);
+ j--;
+ }
+ vector.setElementAt(value, j + 1);
+ }
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/Comparator.java b/libraries/zxing/src/com/google/zxing/common/Comparator.java
new file mode 100644
index 000000000..e1be15e31
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/Comparator.java
@@ -0,0 +1,27 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * This is merely a clone of <code>Comparator</code> since it is not available in
+ * CLDC 1.1 / MIDP 2.0.
+ */
+public interface Comparator {
+
+ int compare(Object o1, Object o2);
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/DecoderResult.java b/libraries/zxing/src/com/google/zxing/common/DecoderResult.java
new file mode 100644
index 000000000..7e0855333
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/DecoderResult.java
@@ -0,0 +1,61 @@
+/*
+ * 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.
+ * 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;
+
+import java.util.Vector;
+
+/**
+ * <p>Encapsulates the result of decoding a matrix of bits. This typically
+ * applies to 2D barcode formats. For now it contains the raw bytes obtained,
+ * as well as a String interpretation of those bytes, if applicable.</p>
+ *
+ * @author Sean Owen
+ */
+public final class DecoderResult {
+
+ private final byte[] rawBytes;
+ private final String text;
+ private final Vector byteSegments;
+ private final String ecLevel;
+
+ public DecoderResult(byte[] rawBytes, String text, Vector byteSegments, String ecLevel) {
+ if (rawBytes == null && text == null) {
+ throw new IllegalArgumentException();
+ }
+ this.rawBytes = rawBytes;
+ this.text = text;
+ this.byteSegments = byteSegments;
+ this.ecLevel = ecLevel;
+ }
+
+ public byte[] getRawBytes() {
+ return rawBytes;
+ }
+
+ public String getText() {
+ return text;
+ }
+
+ public Vector getByteSegments() {
+ return byteSegments;
+ }
+
+ public String getECLevel() {
+ return ecLevel;
+ }
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/DefaultGridSampler.java b/libraries/zxing/src/com/google/zxing/common/DefaultGridSampler.java
new file mode 100644
index 000000000..74c9e7c6b
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/DefaultGridSampler.java
@@ -0,0 +1,86 @@
+/*
+ * 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.
+ * 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;
+
+import com.google.zxing.NotFoundException;
+
+/**
+ * @author Sean Owen
+ */
+public final class DefaultGridSampler extends GridSampler {
+
+ public BitMatrix sampleGrid(BitMatrix image,
+ int dimensionX,
+ int dimensionY,
+ float p1ToX, float p1ToY,
+ float p2ToX, float p2ToY,
+ float p3ToX, float p3ToY,
+ float p4ToX, float p4ToY,
+ float p1FromX, float p1FromY,
+ float p2FromX, float p2FromY,
+ float p3FromX, float p3FromY,
+ float p4FromX, float p4FromY) throws NotFoundException {
+
+ PerspectiveTransform transform = PerspectiveTransform.quadrilateralToQuadrilateral(
+ p1ToX, p1ToY, p2ToX, p2ToY, p3ToX, p3ToY, p4ToX, p4ToY,
+ p1FromX, p1FromY, p2FromX, p2FromY, p3FromX, p3FromY, p4FromX, p4FromY);
+
+ return sampleGrid(image, dimensionX, dimensionY, transform);
+ }
+
+ public BitMatrix sampleGrid(BitMatrix image,
+ int dimensionX,
+ int dimensionY,
+ PerspectiveTransform transform) throws NotFoundException {
+ if (dimensionX <= 0 || dimensionY <= 0) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ BitMatrix bits = new BitMatrix(dimensionX, dimensionY);
+ float[] points = new float[dimensionX << 1];
+ for (int y = 0; y < dimensionY; y++) {
+ int max = points.length;
+ float iValue = (float) y + 0.5f;
+ for (int x = 0; x < max; x += 2) {
+ points[x] = (float) (x >> 1) + 0.5f;
+ points[x + 1] = iValue;
+ }
+ transform.transformPoints(points);
+ // Quick check to see if points transformed to something inside the image;
+ // sufficient to check the endpoints
+ checkAndNudgePoints(image, points);
+ try {
+ for (int x = 0; x < max; x += 2) {
+ if (image.get((int) points[x], (int) points[x + 1])) {
+ // Black(-ish) pixel
+ bits.set(x >> 1, y);
+ }
+ }
+ } catch (ArrayIndexOutOfBoundsException aioobe) {
+ // This feels wrong, but, sometimes if the finder patterns are misidentified, the resulting
+ // transform gets "twisted" such that it maps a straight line of points to a set of points
+ // whose endpoints are in bounds, but others are not. There is probably some mathematical
+ // way to detect this about the transformation that I don't know yet.
+ // This results in an ugly runtime exception despite our clever checks above -- can't have
+ // that. We could check each point's coordinates but that feels duplicative. We settle for
+ // catching and wrapping ArrayIndexOutOfBoundsException.
+ throw NotFoundException.getNotFoundInstance();
+ }
+ }
+ return bits;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/DetectorResult.java b/libraries/zxing/src/com/google/zxing/common/DetectorResult.java
new file mode 100644
index 000000000..ea4794d17
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/DetectorResult.java
@@ -0,0 +1,46 @@
+/*
+ * 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.
+ * 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;
+
+import com.google.zxing.ResultPoint;
+
+/**
+ * <p>Encapsulates the result of detecting a barcode in an image. This includes the raw
+ * matrix of black/white pixels corresponding to the barcode, and possibly points of interest
+ * in the image, like the location of finder patterns or corners of the barcode in the image.</p>
+ *
+ * @author Sean Owen
+ */
+public class DetectorResult {
+
+ private final BitMatrix bits;
+ private final ResultPoint[] points;
+
+ public DetectorResult(BitMatrix bits, ResultPoint[] points) {
+ this.bits = bits;
+ this.points = points;
+ }
+
+ public BitMatrix getBits() {
+ return bits;
+ }
+
+ public ResultPoint[] getPoints() {
+ return points;
+ }
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/ECI.java b/libraries/zxing/src/com/google/zxing/common/ECI.java
new file mode 100644
index 000000000..444c779c2
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/ECI.java
@@ -0,0 +1,52 @@
+/*
+ * 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;
+
+/**
+ * Superclass of classes encapsulating types ECIs, according to "Extended Channel Interpretations"
+ * 5.3 of ISO 18004.
+ *
+ * @author Sean Owen
+ */
+public abstract class ECI {
+
+ private final int value;
+
+ ECI(int value) {
+ this.value = value;
+ }
+
+ public int getValue() {
+ return value;
+ }
+
+ /**
+ * @param value ECI value
+ * @return ECI representing ECI of given value, or null if it is legal but unsupported
+ * @throws IllegalArgumentException if ECI value is invalid
+ */
+ public static ECI getECIByValue(int value) {
+ if (value < 0 || value > 999999) {
+ throw new IllegalArgumentException("Bad ECI value: " + value);
+ }
+ if (value < 900) { // Character set ECIs use 000000 - 000899
+ return CharacterSetECI.getCharacterSetECIByValue(value);
+ }
+ return null;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/GlobalHistogramBinarizer.java b/libraries/zxing/src/com/google/zxing/common/GlobalHistogramBinarizer.java
new file mode 100644
index 000000000..4fa2a887b
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/GlobalHistogramBinarizer.java
@@ -0,0 +1,194 @@
+/*
+ * Copyright 2009 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;
+
+import com.google.zxing.Binarizer;
+import com.google.zxing.LuminanceSource;
+import com.google.zxing.NotFoundException;
+
+/**
+ * This Binarizer implementation uses the old ZXing global histogram approach. It is suitable
+ * for low-end mobile devices which don't have enough CPU or memory to use a local thresholding
+ * algorithm. However, because it picks a global black point, it cannot handle difficult shadows
+ * and gradients.
+ *
+ * Faster mobile devices and all desktop applications should probably use HybridBinarizer instead.
+ *
+ * @author dswitkin@google.com (Daniel Switkin)
+ * @author Sean Owen
+ */
+public class GlobalHistogramBinarizer extends Binarizer {
+
+ private static final int LUMINANCE_BITS = 5;
+ private static final int LUMINANCE_SHIFT = 8 - LUMINANCE_BITS;
+ private static final int LUMINANCE_BUCKETS = 1 << LUMINANCE_BITS;
+
+ private byte[] luminances = null;
+ private int[] buckets = null;
+
+ public GlobalHistogramBinarizer(LuminanceSource source) {
+ super(source);
+ }
+
+ // Applies simple sharpening to the row data to improve performance of the 1D Readers.
+ public BitArray getBlackRow(int y, BitArray row) throws NotFoundException {
+ LuminanceSource source = getLuminanceSource();
+ int width = source.getWidth();
+ if (row == null || row.getSize() < width) {
+ row = new BitArray(width);
+ } else {
+ row.clear();
+ }
+
+ initArrays(width);
+ byte[] localLuminances = source.getRow(y, luminances);
+ int[] localBuckets = buckets;
+ for (int x = 0; x < width; x++) {
+ int pixel = localLuminances[x] & 0xff;
+ localBuckets[pixel >> LUMINANCE_SHIFT]++;
+ }
+ int blackPoint = estimateBlackPoint(localBuckets);
+
+ int left = localLuminances[0] & 0xff;
+ int center = localLuminances[1] & 0xff;
+ for (int x = 1; x < width - 1; x++) {
+ int right = localLuminances[x + 1] & 0xff;
+ // A simple -1 4 -1 box filter with a weight of 2.
+ int luminance = ((center << 2) - left - right) >> 1;
+ if (luminance < blackPoint) {
+ row.set(x);
+ }
+ left = center;
+ center = right;
+ }
+ return row;
+ }
+
+ // Does not sharpen the data, as this call is intended to only be used by 2D Readers.
+ public BitMatrix getBlackMatrix() throws NotFoundException {
+ LuminanceSource source = getLuminanceSource();
+ int width = source.getWidth();
+ int height = source.getHeight();
+ BitMatrix matrix = new BitMatrix(width, height);
+
+ // Quickly calculates the histogram by sampling four rows from the image. This proved to be
+ // more robust on the blackbox tests than sampling a diagonal as we used to do.
+ initArrays(width);
+ int[] localBuckets = buckets;
+ for (int y = 1; y < 5; y++) {
+ int row = height * y / 5;
+ byte[] localLuminances = source.getRow(row, luminances);
+ int right = (width << 2) / 5;
+ for (int x = width / 5; x < right; x++) {
+ int pixel = localLuminances[x] & 0xff;
+ localBuckets[pixel >> LUMINANCE_SHIFT]++;
+ }
+ }
+ int blackPoint = estimateBlackPoint(localBuckets);
+
+ // We delay reading the entire image luminance until the black point estimation succeeds.
+ // Although we end up reading four rows twice, it is consistent with our motto of
+ // "fail quickly" which is necessary for continuous scanning.
+ byte[] localLuminances = source.getMatrix();
+ for (int y = 0; y < height; y++) {
+ int offset = y * width;
+ for (int x = 0; x< width; x++) {
+ int pixel = localLuminances[offset + x] & 0xff;
+ if (pixel < blackPoint) {
+ matrix.set(x, y);
+ }
+ }
+ }
+
+ return matrix;
+ }
+
+ public Binarizer createBinarizer(LuminanceSource source) {
+ return new GlobalHistogramBinarizer(source);
+ }
+
+ private void initArrays(int luminanceSize) {
+ if (luminances == null || luminances.length < luminanceSize) {
+ luminances = new byte[luminanceSize];
+ }
+ if (buckets == null) {
+ buckets = new int[LUMINANCE_BUCKETS];
+ } else {
+ for (int x = 0; x < LUMINANCE_BUCKETS; x++) {
+ buckets[x] = 0;
+ }
+ }
+ }
+
+ private static int estimateBlackPoint(int[] buckets) throws NotFoundException {
+ // Find the tallest peak in the histogram.
+ int numBuckets = buckets.length;
+ int maxBucketCount = 0;
+ int firstPeak = 0;
+ int firstPeakSize = 0;
+ for (int x = 0; x < numBuckets; x++) {
+ if (buckets[x] > firstPeakSize) {
+ firstPeak = x;
+ firstPeakSize = buckets[x];
+ }
+ if (buckets[x] > maxBucketCount) {
+ maxBucketCount = buckets[x];
+ }
+ }
+
+ // Find the second-tallest peak which is somewhat far from the tallest peak.
+ int secondPeak = 0;
+ int secondPeakScore = 0;
+ for (int x = 0; x < numBuckets; x++) {
+ int distanceToBiggest = x - firstPeak;
+ // Encourage more distant second peaks by multiplying by square of distance.
+ int score = buckets[x] * distanceToBiggest * distanceToBiggest;
+ if (score > secondPeakScore) {
+ secondPeak = x;
+ secondPeakScore = score;
+ }
+ }
+
+ // Make sure firstPeak corresponds to the black peak.
+ if (firstPeak > secondPeak) {
+ int temp = firstPeak;
+ firstPeak = secondPeak;
+ secondPeak = temp;
+ }
+
+ // If there is too little contrast in the image to pick a meaningful black point, throw rather
+ // than waste time trying to decode the image, and risk false positives.
+ if (secondPeak - firstPeak <= numBuckets >> 4) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ // Find a valley between them that is low and closer to the white peak.
+ int bestValley = secondPeak - 1;
+ int bestValleyScore = -1;
+ for (int x = secondPeak - 1; x > firstPeak; x--) {
+ int fromFirst = x - firstPeak;
+ int score = fromFirst * fromFirst * (secondPeak - x) * (maxBucketCount - buckets[x]);
+ if (score > bestValleyScore) {
+ bestValley = x;
+ bestValleyScore = score;
+ }
+ }
+
+ return bestValley << LUMINANCE_SHIFT;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/GridSampler.java b/libraries/zxing/src/com/google/zxing/common/GridSampler.java
new file mode 100644
index 000000000..7f26c264e
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/GridSampler.java
@@ -0,0 +1,156 @@
+/*
+ * 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.
+ * 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;
+
+import com.google.zxing.NotFoundException;
+
+/**
+ * Implementations of this class can, given locations of finder patterns for a QR code in an
+ * image, sample the right points in the image to reconstruct the QR code, accounting for
+ * perspective distortion. It is abstracted since it is relatively expensive and should be allowed
+ * to take advantage of platform-specific optimized implementations, like Sun's Java Advanced
+ * Imaging library, but which may not be available in other environments such as J2ME, and vice
+ * versa.
+ *
+ * The implementation used can be controlled by calling {@link #setGridSampler(GridSampler)}
+ * with an instance of a class which implements this interface.
+ *
+ * @author Sean Owen
+ */
+public abstract class GridSampler {
+
+ private static GridSampler gridSampler = new DefaultGridSampler();
+
+ /**
+ * Sets the implementation of GridSampler used by the library. One global
+ * instance is stored, which may sound problematic. But, the implementation provided
+ * ought to be appropriate for the entire platform, and all uses of this library
+ * in the whole lifetime of the JVM. For instance, an Android activity can swap in
+ * an implementation that takes advantage of native platform libraries.
+ *
+ * @param newGridSampler The platform-specific object to install.
+ */
+ public static void setGridSampler(GridSampler newGridSampler) {
+ if (newGridSampler == null) {
+ throw new IllegalArgumentException();
+ }
+ gridSampler = newGridSampler;
+ }
+
+ /**
+ * @return the current implementation of GridSampler
+ */
+ public static GridSampler getInstance() {
+ return gridSampler;
+ }
+
+ /**
+ * Samples an image for a rectangular matrix of bits of the given dimension.
+ * @param image image to sample
+ * @param dimensionX width of {@link BitMatrix} to sample from image
+ * @param dimensionY height of {@link BitMatrix} to sample from image
+ * @return {@link BitMatrix} representing a grid of points sampled from the image within a region
+ * defined by the "from" parameters
+ * @throws NotFoundException if image can't be sampled, for example, if the transformation defined
+ * by the given points is invalid or results in sampling outside the image boundaries
+ */
+ public abstract BitMatrix sampleGrid(BitMatrix image,
+ int dimensionX,
+ int dimensionY,
+ float p1ToX, float p1ToY,
+ float p2ToX, float p2ToY,
+ float p3ToX, float p3ToY,
+ float p4ToX, float p4ToY,
+ float p1FromX, float p1FromY,
+ float p2FromX, float p2FromY,
+ float p3FromX, float p3FromY,
+ float p4FromX, float p4FromY) throws NotFoundException;
+
+ public abstract BitMatrix sampleGrid(BitMatrix image,
+ int dimensionX,
+ int dimensionY,
+ PerspectiveTransform transform) throws NotFoundException;
+
+ /**
+ * <p>Checks a set of points that have been transformed to sample points on an image against
+ * the image's dimensions to see if the point are even within the image.</p>
+ *
+ * <p>This method will actually "nudge" the endpoints back onto the image if they are found to be
+ * barely (less than 1 pixel) off the image. This accounts for imperfect detection of finder
+ * patterns in an image where the QR Code runs all the way to the image border.</p>
+ *
+ * <p>For efficiency, the method will check points from either end of the line until one is found
+ * to be within the image. Because the set of points are assumed to be linear, this is valid.</p>
+ *
+ * @param image image into which the points should map
+ * @param points actual points in x1,y1,...,xn,yn form
+ * @throws NotFoundException if an endpoint is lies outside the image boundaries
+ */
+ protected static void checkAndNudgePoints(BitMatrix image, float[] points) throws NotFoundException {
+ int width = image.getWidth();
+ int height = image.getHeight();
+ // Check and nudge points from start until we see some that are OK:
+ boolean nudged = true;
+ for (int offset = 0; offset < points.length && nudged; offset += 2) {
+ int x = (int) points[offset];
+ int y = (int) points[offset + 1];
+ if (x < -1 || x > width || y < -1 || y > height) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ nudged = false;
+ if (x == -1) {
+ points[offset] = 0.0f;
+ nudged = true;
+ } else if (x == width) {
+ points[offset] = width - 1;
+ nudged = true;
+ }
+ if (y == -1) {
+ points[offset + 1] = 0.0f;
+ nudged = true;
+ } else if (y == height) {
+ points[offset + 1] = height - 1;
+ nudged = true;
+ }
+ }
+ // Check and nudge points from end:
+ nudged = true;
+ for (int offset = points.length - 2; offset >= 0 && nudged; offset -= 2) {
+ int x = (int) points[offset];
+ int y = (int) points[offset + 1];
+ if (x < -1 || x > width || y < -1 || y > height) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ nudged = false;
+ if (x == -1) {
+ points[offset] = 0.0f;
+ nudged = true;
+ } else if (x == width) {
+ points[offset] = width - 1;
+ nudged = true;
+ }
+ if (y == -1) {
+ points[offset + 1] = 0.0f;
+ nudged = true;
+ } else if (y == height) {
+ points[offset + 1] = height - 1;
+ nudged = true;
+ }
+ }
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/HybridBinarizer.java b/libraries/zxing/src/com/google/zxing/common/HybridBinarizer.java
new file mode 100644
index 000000000..b482c1a22
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/HybridBinarizer.java
@@ -0,0 +1,185 @@
+/*
+ * Copyright 2009 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;
+
+import com.google.zxing.Binarizer;
+import com.google.zxing.LuminanceSource;
+import com.google.zxing.NotFoundException;
+
+/**
+ * This class implements a local thresholding algorithm, which while slower than the
+ * GlobalHistogramBinarizer, is fairly efficient for what it does. It is designed for
+ * high frequency images of barcodes with black data on white backgrounds. For this application,
+ * it does a much better job than a global blackpoint with severe shadows and gradients.
+ * However it tends to produce artifacts on lower frequency images and is therefore not
+ * a good general purpose binarizer for uses outside ZXing.
+ *
+ * This class extends GlobalHistogramBinarizer, using the older histogram approach for 1D readers,
+ * and the newer local approach for 2D readers. 1D decoding using a per-row histogram is already
+ * inherently local, and only fails for horizontal gradients. We can revisit that problem later,
+ * but for now it was not a win to use local blocks for 1D.
+ *
+ * This Binarizer is the default for the unit tests and the recommended class for library users.
+ *
+ * @author dswitkin@google.com (Daniel Switkin)
+ */
+public final class HybridBinarizer extends GlobalHistogramBinarizer {
+
+ // This class uses 5x5 blocks to compute local luminance, where each block is 8x8 pixels.
+ // So this is the smallest dimension in each axis we can accept.
+ private static final int MINIMUM_DIMENSION = 40;
+
+ private BitMatrix matrix = null;
+
+ public HybridBinarizer(LuminanceSource source) {
+ super(source);
+ }
+
+ public BitMatrix getBlackMatrix() throws NotFoundException {
+ binarizeEntireImage();
+ return matrix;
+ }
+
+ public Binarizer createBinarizer(LuminanceSource source) {
+ return new HybridBinarizer(source);
+ }
+
+ // Calculates the final BitMatrix once for all requests. This could be called once from the
+ // constructor instead, but there are some advantages to doing it lazily, such as making
+ // profiling easier, and not doing heavy lifting when callers don't expect it.
+ private void binarizeEntireImage() throws NotFoundException {
+ if (matrix == null) {
+ LuminanceSource source = getLuminanceSource();
+ if (source.getWidth() >= MINIMUM_DIMENSION && source.getHeight() >= MINIMUM_DIMENSION) {
+ byte[] luminances = source.getMatrix();
+ int width = source.getWidth();
+ int height = source.getHeight();
+ int subWidth = width >> 3;
+ if ((width & 0x07) != 0) {
+ subWidth++;
+ }
+ int subHeight = height >> 3;
+ if ((height & 0x07) != 0) {
+ subHeight++;
+ }
+ int[][] blackPoints = calculateBlackPoints(luminances, subWidth, subHeight, width, height);
+
+ matrix = new BitMatrix(width, height);
+ calculateThresholdForBlock(luminances, subWidth, subHeight, width, height, blackPoints, matrix);
+ } else {
+ // If the image is too small, fall back to the global histogram approach.
+ matrix = super.getBlackMatrix();
+ }
+ }
+ }
+
+ // For each 8x8 block in the image, calculate the average black point using a 5x5 grid
+ // of the blocks around it. Also handles the corner cases (fractional blocks are computed based
+ // on the last 8 pixels in the row/column which are also used in the previous block).
+ private static void calculateThresholdForBlock(byte[] luminances, int subWidth, int subHeight,
+ int width, int height, int[][] blackPoints, BitMatrix matrix) {
+ for (int y = 0; y < subHeight; y++) {
+ int yoffset = y << 3;
+ if ((yoffset + 8) >= height) {
+ yoffset = height - 8;
+ }
+ for (int x = 0; x < subWidth; x++) {
+ int xoffset = x << 3;
+ if ((xoffset + 8) >= width) {
+ xoffset = width - 8;
+ }
+ int left = x > 1 ? x : 2;
+ left = left < subWidth - 2 ? left : subWidth - 3;
+ int top = y > 1 ? y : 2;
+ top = top < subHeight - 2 ? top : subHeight - 3;
+ int sum = 0;
+ for (int z = -2; z <= 2; z++) {
+ int[] blackRow = blackPoints[top + z];
+ sum += blackRow[left - 2];
+ sum += blackRow[left - 1];
+ sum += blackRow[left];
+ sum += blackRow[left + 1];
+ sum += blackRow[left + 2];
+ }
+ int average = sum / 25;
+ threshold8x8Block(luminances, xoffset, yoffset, average, width, matrix);
+ }
+ }
+ }
+
+ // Applies a single threshold to an 8x8 block of pixels.
+ private static void threshold8x8Block(byte[] luminances, int xoffset, int yoffset, int threshold,
+ int stride, BitMatrix matrix) {
+ for (int y = 0; y < 8; y++) {
+ int offset = (yoffset + y) * stride + xoffset;
+ for (int x = 0; x < 8; x++) {
+ int pixel = luminances[offset + x] & 0xff;
+ if (pixel < threshold) {
+ matrix.set(xoffset + x, yoffset + y);
+ }
+ }
+ }
+ }
+
+ // Calculates a single black point for each 8x8 block of pixels and saves it away.
+ private static int[][] calculateBlackPoints(byte[] luminances, int subWidth, int subHeight,
+ int width, int height) {
+ int[][] blackPoints = new int[subHeight][subWidth];
+ for (int y = 0; y < subHeight; y++) {
+ int yoffset = y << 3;
+ if ((yoffset + 8) >= height) {
+ yoffset = height - 8;
+ }
+ for (int x = 0; x < subWidth; x++) {
+ int xoffset = x << 3;
+ if ((xoffset + 8) >= width) {
+ xoffset = width - 8;
+ }
+ int sum = 0;
+ int min = 255;
+ int max = 0;
+ for (int yy = 0; yy < 8; yy++) {
+ int offset = (yoffset + yy) * width + xoffset;
+ for (int xx = 0; xx < 8; xx++) {
+ int pixel = luminances[offset + xx] & 0xff;
+ sum += pixel;
+ if (pixel < min) {
+ min = pixel;
+ }
+ if (pixel > max) {
+ max = pixel;
+ }
+ }
+ }
+
+ // If the contrast is inadequate, use half the minimum, so that this block will be
+ // treated as part of the white background, but won't drag down neighboring blocks
+ // too much.
+ int average;
+ if (max - min > 24) {
+ average = sum >> 6;
+ } else {
+ // When min == max == 0, let average be 1 so all is black
+ average = max == 0 ? 1 : min >> 1;
+ }
+ blackPoints[y][x] = average;
+ }
+ }
+ return blackPoints;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/PerspectiveTransform.java b/libraries/zxing/src/com/google/zxing/common/PerspectiveTransform.java
new file mode 100644
index 000000000..9e65baff1
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/PerspectiveTransform.java
@@ -0,0 +1,148 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>This class implements a perspective transform in two dimensions. Given four source and four
+ * destination points, it will compute the transformation implied between them. The code is based
+ * directly upon section 3.4.2 of George Wolberg's "Digital Image Warping"; see pages 54-56.</p>
+ *
+ * @author Sean Owen
+ */
+public final class PerspectiveTransform {
+
+ private final float a11, a12, a13, a21, a22, a23, a31, a32, a33;
+
+ private PerspectiveTransform(float a11, float a21, float a31,
+ float a12, float a22, float a32,
+ float a13, float a23, float a33) {
+ this.a11 = a11;
+ this.a12 = a12;
+ this.a13 = a13;
+ this.a21 = a21;
+ this.a22 = a22;
+ this.a23 = a23;
+ this.a31 = a31;
+ this.a32 = a32;
+ this.a33 = a33;
+ }
+
+ public static PerspectiveTransform quadrilateralToQuadrilateral(float x0, float y0,
+ float x1, float y1,
+ float x2, float y2,
+ float x3, float y3,
+ float x0p, float y0p,
+ float x1p, float y1p,
+ float x2p, float y2p,
+ float x3p, float y3p) {
+
+ PerspectiveTransform qToS = quadrilateralToSquare(x0, y0, x1, y1, x2, y2, x3, y3);
+ PerspectiveTransform sToQ = squareToQuadrilateral(x0p, y0p, x1p, y1p, x2p, y2p, x3p, y3p);
+ return sToQ.times(qToS);
+ }
+
+ public void transformPoints(float[] points) {
+ int max = points.length;
+ float a11 = this.a11;
+ float a12 = this.a12;
+ float a13 = this.a13;
+ float a21 = this.a21;
+ float a22 = this.a22;
+ float a23 = this.a23;
+ float a31 = this.a31;
+ float a32 = this.a32;
+ float a33 = this.a33;
+ for (int i = 0; i < max; i += 2) {
+ float x = points[i];
+ float y = points[i + 1];
+ float denominator = a13 * x + a23 * y + a33;
+ points[i] = (a11 * x + a21 * y + a31) / denominator;
+ points[i + 1] = (a12 * x + a22 * y + a32) / denominator;
+ }
+ }
+
+ /** Convenience method, not optimized for performance. */
+ public void transformPoints(float[] xValues, float[] yValues) {
+ int n = xValues.length;
+ for (int i = 0; i < n; i ++) {
+ float x = xValues[i];
+ float y = yValues[i];
+ float denominator = a13 * x + a23 * y + a33;
+ xValues[i] = (a11 * x + a21 * y + a31) / denominator;
+ yValues[i] = (a12 * x + a22 * y + a32) / denominator;
+ }
+ }
+
+ public static PerspectiveTransform squareToQuadrilateral(float x0, float y0,
+ float x1, float y1,
+ float x2, float y2,
+ float x3, float y3) {
+ float dy2 = y3 - y2;
+ float dy3 = y0 - y1 + y2 - y3;
+ if (dy2 == 0.0f && dy3 == 0.0f) {
+ return new PerspectiveTransform(x1 - x0, x2 - x1, x0,
+ y1 - y0, y2 - y1, y0,
+ 0.0f, 0.0f, 1.0f);
+ } else {
+ float dx1 = x1 - x2;
+ float dx2 = x3 - x2;
+ float dx3 = x0 - x1 + x2 - x3;
+ float dy1 = y1 - y2;
+ float denominator = dx1 * dy2 - dx2 * dy1;
+ float a13 = (dx3 * dy2 - dx2 * dy3) / denominator;
+ float a23 = (dx1 * dy3 - dx3 * dy1) / denominator;
+ return new PerspectiveTransform(x1 - x0 + a13 * x1, x3 - x0 + a23 * x3, x0,
+ y1 - y0 + a13 * y1, y3 - y0 + a23 * y3, y0,
+ a13, a23, 1.0f);
+ }
+ }
+
+ public static PerspectiveTransform quadrilateralToSquare(float x0, float y0,
+ float x1, float y1,
+ float x2, float y2,
+ float x3, float y3) {
+ // Here, the adjoint serves as the inverse:
+ return squareToQuadrilateral(x0, y0, x1, y1, x2, y2, x3, y3).buildAdjoint();
+ }
+
+ PerspectiveTransform buildAdjoint() {
+ // Adjoint is the transpose of the cofactor matrix:
+ return new PerspectiveTransform(a22 * a33 - a23 * a32,
+ a23 * a31 - a21 * a33,
+ a21 * a32 - a22 * a31,
+ a13 * a32 - a12 * a33,
+ a11 * a33 - a13 * a31,
+ a12 * a31 - a11 * a32,
+ a12 * a23 - a13 * a22,
+ a13 * a21 - a11 * a23,
+ a11 * a22 - a12 * a21);
+ }
+
+ PerspectiveTransform times(PerspectiveTransform other) {
+ return new PerspectiveTransform(a11 * other.a11 + a21 * other.a12 + a31 * other.a13,
+ a11 * other.a21 + a21 * other.a22 + a31 * other.a23,
+ a11 * other.a31 + a21 * other.a32 + a31 * other.a33,
+ a12 * other.a11 + a22 * other.a12 + a32 * other.a13,
+ a12 * other.a21 + a22 * other.a22 + a32 * other.a23,
+ a12 * other.a31 + a22 * other.a32 + a32 * other.a33,
+ a13 * other.a11 + a23 * other.a12 + a33 * other.a13,
+ a13 * other.a21 + a23 * other.a22 + a33 * other.a23,
+ a13 * other.a31 + a23 * other.a32 + a33 * other.a33);
+
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/StringUtils.java b/libraries/zxing/src/com/google/zxing/common/StringUtils.java
new file mode 100644
index 000000000..97999f997
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/StringUtils.java
@@ -0,0 +1,192 @@
+/*
+ * Copyright (C) 2010 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;
+
+import java.util.Hashtable;
+
+import com.google.zxing.DecodeHintType;
+
+/**
+ * Common string-related functions.
+ *
+ * @author Sean Owen
+ */
+public final class StringUtils {
+
+ private static final String PLATFORM_DEFAULT_ENCODING =
+ System.getProperty("file.encoding");
+ public static final String SHIFT_JIS = "SJIS";
+ public static final String GB2312 = "GB2312";
+ private static final String EUC_JP = "EUC_JP";
+ private static final String UTF8 = "UTF8";
+ private static final String ISO88591 = "ISO8859_1";
+ private static final boolean ASSUME_SHIFT_JIS =
+ SHIFT_JIS.equalsIgnoreCase(PLATFORM_DEFAULT_ENCODING) ||
+ EUC_JP.equalsIgnoreCase(PLATFORM_DEFAULT_ENCODING);
+
+ private StringUtils() {}
+
+ /**
+ * @param bytes bytes encoding a string, whose encoding should be guessed
+ * @param hints decode hints if applicable
+ * @return name of guessed encoding; at the moment will only guess one of:
+ * {@link #SHIFT_JIS}, {@link #UTF8}, {@link #ISO88591}, or the platform
+ * default encoding if none of these can possibly be correct
+ */
+ public static String guessEncoding(byte[] bytes, Hashtable hints) {
+ if (hints != null) {
+ String characterSet = (String) hints.get(DecodeHintType.CHARACTER_SET);
+ if (characterSet != null) {
+ return characterSet;
+ }
+ }
+ // Does it start with the UTF-8 byte order mark? then guess it's UTF-8
+ if (bytes.length > 3 &&
+ bytes[0] == (byte) 0xEF &&
+ bytes[1] == (byte) 0xBB &&
+ bytes[2] == (byte) 0xBF) {
+ return UTF8;
+ }
+ // For now, merely tries to distinguish ISO-8859-1, UTF-8 and Shift_JIS,
+ // which should be by far the most common encodings. ISO-8859-1
+ // should not have bytes in the 0x80 - 0x9F range, while Shift_JIS
+ // uses this as a first byte of a two-byte character. If we see this
+ // followed by a valid second byte in Shift_JIS, assume it is Shift_JIS.
+ // If we see something else in that second byte, we'll make the risky guess
+ // that it's UTF-8.
+ int length = bytes.length;
+ boolean canBeISO88591 = true;
+ boolean canBeShiftJIS = true;
+ boolean canBeUTF8 = true;
+ int utf8BytesLeft = 0;
+ int maybeDoubleByteCount = 0;
+ int maybeSingleByteKatakanaCount = 0;
+ boolean sawLatin1Supplement = false;
+ boolean sawUTF8Start = false;
+ boolean lastWasPossibleDoubleByteStart = false;
+
+ for (int i = 0;
+ i < length && (canBeISO88591 || canBeShiftJIS || canBeUTF8);
+ i++) {
+
+ int value = bytes[i] & 0xFF;
+
+ // UTF-8 stuff
+ if (value >= 0x80 && value <= 0xBF) {
+ if (utf8BytesLeft > 0) {
+ utf8BytesLeft--;
+ }
+ } else {
+ if (utf8BytesLeft > 0) {
+ canBeUTF8 = false;
+ }
+ if (value >= 0xC0 && value <= 0xFD) {
+ sawUTF8Start = true;
+ int valueCopy = value;
+ while ((valueCopy & 0x40) != 0) {
+ utf8BytesLeft++;
+ valueCopy <<= 1;
+ }
+ }
+ }
+
+ // ISO-8859-1 stuff
+
+ if ((value == 0xC2 || value == 0xC3) && i < length - 1) {
+ // This is really a poor hack. The slightly more exotic characters people might want to put in
+ // a QR Code, by which I mean the Latin-1 supplement characters (e.g. u-umlaut) have encodings
+ // that start with 0xC2 followed by [0xA0,0xBF], or start with 0xC3 followed by [0x80,0xBF].
+ int nextValue = bytes[i + 1] & 0xFF;
+ if (nextValue <= 0xBF &&
+ ((value == 0xC2 && nextValue >= 0xA0) || (value == 0xC3 && nextValue >= 0x80))) {
+ sawLatin1Supplement = true;
+ }
+ }
+ if (value >= 0x7F && value <= 0x9F) {
+ canBeISO88591 = false;
+ }
+
+ // Shift_JIS stuff
+
+ if (value >= 0xA1 && value <= 0xDF) {
+ // count the number of characters that might be a Shift_JIS single-byte Katakana character
+ if (!lastWasPossibleDoubleByteStart) {
+ maybeSingleByteKatakanaCount++;
+ }
+ }
+ if (!lastWasPossibleDoubleByteStart &&
+ ((value >= 0xF0 && value <= 0xFF) || value == 0x80 || value == 0xA0)) {
+ canBeShiftJIS = false;
+ }
+ if ((value >= 0x81 && value <= 0x9F) || (value >= 0xE0 && value <= 0xEF)) {
+ // These start double-byte characters in Shift_JIS. Let's see if it's followed by a valid
+ // second byte.
+ if (lastWasPossibleDoubleByteStart) {
+ // If we just checked this and the last byte for being a valid double-byte
+ // char, don't check starting on this byte. If this and the last byte
+ // formed a valid pair, then this shouldn't be checked to see if it starts
+ // a double byte pair of course.
+ lastWasPossibleDoubleByteStart = false;
+ } else {
+ // ... otherwise do check to see if this plus the next byte form a valid
+ // double byte pair encoding a character.
+ lastWasPossibleDoubleByteStart = true;
+ if (i >= bytes.length - 1) {
+ canBeShiftJIS = false;
+ } else {
+ int nextValue = bytes[i + 1] & 0xFF;
+ if (nextValue < 0x40 || nextValue > 0xFC) {
+ canBeShiftJIS = false;
+ } else {
+ maybeDoubleByteCount++;
+ }
+ // There is some conflicting information out there about which bytes can follow which in
+ // double-byte Shift_JIS characters. The rule above seems to be the one that matches practice.
+ }
+ }
+ } else {
+ lastWasPossibleDoubleByteStart = false;
+ }
+ }
+ if (utf8BytesLeft > 0) {
+ canBeUTF8 = false;
+ }
+
+ // Easy -- if assuming Shift_JIS and no evidence it can't be, done
+ if (canBeShiftJIS && ASSUME_SHIFT_JIS) {
+ return SHIFT_JIS;
+ }
+ if (canBeUTF8 && sawUTF8Start) {
+ return UTF8;
+ }
+ // Distinguishing Shift_JIS and ISO-8859-1 can be a little tough. The crude heuristic is:
+ // - If we saw
+ // - at least 3 bytes that starts a double-byte value (bytes that are rare in ISO-8859-1), or
+ // - over 5% of bytes could be single-byte Katakana (also rare in ISO-8859-1),
+ // - and, saw no sequences that are invalid in Shift_JIS, then we conclude Shift_JIS
+ if (canBeShiftJIS && (maybeDoubleByteCount >= 3 || 20 * maybeSingleByteKatakanaCount > length)) {
+ return SHIFT_JIS;
+ }
+ // Otherwise, we default to ISO-8859-1 unless we know it can't be
+ if (!sawLatin1Supplement && canBeISO88591) {
+ return ISO88591;
+ }
+ // Otherwise, we take a wild guess with platform encoding
+ return PLATFORM_DEFAULT_ENCODING;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java b/libraries/zxing/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java
new file mode 100644
index 000000000..950a22364
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/detector/MonochromeRectangleDetector.java
@@ -0,0 +1,209 @@
+/*
+ * Copyright 2009 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.detector;
+
+import com.google.zxing.NotFoundException;
+import com.google.zxing.ResultPoint;
+import com.google.zxing.common.BitMatrix;
+
+/**
+ * <p>A somewhat generic detector that looks for a barcode-like rectangular region within an image.
+ * It looks within a mostly white region of an image for a region of black and white, but mostly
+ * black. It returns the four corners of the region, as best it can determine.</p>
+ *
+ * @author Sean Owen
+ */
+public final class MonochromeRectangleDetector {
+
+ private static final int MAX_MODULES = 32;
+
+ private final BitMatrix image;
+
+ public MonochromeRectangleDetector(BitMatrix image) {
+ this.image = image;
+ }
+
+ /**
+ * <p>Detects a rectangular region of black and white -- mostly black -- with a region of mostly
+ * white, in an image.</p>
+ *
+ * @return {@link ResultPoint}[] describing the corners of the rectangular region. The first and
+ * last points are opposed on the diagonal, as are the second and third. The first point will be
+ * the topmost point and the last, the bottommost. The second point will be leftmost and the
+ * third, the rightmost
+ * @throws NotFoundException if no Data Matrix Code can be found
+ */
+ public ResultPoint[] detect() throws NotFoundException {
+ int height = image.getHeight();
+ int width = image.getWidth();
+ int halfHeight = height >> 1;
+ int halfWidth = width >> 1;
+ int deltaY = Math.max(1, height / (MAX_MODULES << 3));
+ int deltaX = Math.max(1, width / (MAX_MODULES << 3));
+
+ int top = 0;
+ int bottom = height;
+ int left = 0;
+ int right = width;
+ ResultPoint pointA = findCornerFromCenter(halfWidth, 0, left, right,
+ halfHeight, -deltaY, top, bottom, halfWidth >> 1);
+ top = (int) pointA.getY() - 1;
+ ResultPoint pointB = findCornerFromCenter(halfWidth, -deltaX, left, right,
+ halfHeight, 0, top, bottom, halfHeight >> 1);
+ left = (int) pointB.getX() - 1;
+ ResultPoint pointC = findCornerFromCenter(halfWidth, deltaX, left, right,
+ halfHeight, 0, top, bottom, halfHeight >> 1);
+ right = (int) pointC.getX() + 1;
+ ResultPoint pointD = findCornerFromCenter(halfWidth, 0, left, right,
+ halfHeight, deltaY, top, bottom, halfWidth >> 1);
+ bottom = (int) pointD.getY() + 1;
+
+ // Go try to find point A again with better information -- might have been off at first.
+ pointA = findCornerFromCenter(halfWidth, 0, left, right,
+ halfHeight, -deltaY, top, bottom, halfWidth >> 2);
+
+ return new ResultPoint[] { pointA, pointB, pointC, pointD };
+ }
+
+ /**
+ * Attempts to locate a corner of the barcode by scanning up, down, left or right from a center
+ * point which should be within the barcode.
+ *
+ * @param centerX center's x component (horizontal)
+ * @param deltaX same as deltaY but change in x per step instead
+ * @param left minimum value of x
+ * @param right maximum value of x
+ * @param centerY center's y component (vertical)
+ * @param deltaY change in y per step. If scanning up this is negative; down, positive;
+ * left or right, 0
+ * @param top minimum value of y to search through (meaningless when di == 0)
+ * @param bottom maximum value of y
+ * @param maxWhiteRun maximum run of white pixels that can still be considered to be within
+ * the barcode
+ * @return a {@link com.google.zxing.ResultPoint} encapsulating the corner that was found
+ * @throws NotFoundException if such a point cannot be found
+ */
+ private ResultPoint findCornerFromCenter(int centerX, int deltaX, int left, int right,
+ int centerY, int deltaY, int top, int bottom, int maxWhiteRun) throws NotFoundException {
+ int[] lastRange = null;
+ for (int y = centerY, x = centerX;
+ y < bottom && y >= top && x < right && x >= left;
+ y += deltaY, x += deltaX) {
+ int[] range;
+ if (deltaX == 0) {
+ // horizontal slices, up and down
+ range = blackWhiteRange(y, maxWhiteRun, left, right, true);
+ } else {
+ // vertical slices, left and right
+ range = blackWhiteRange(x, maxWhiteRun, top, bottom, false);
+ }
+ if (range == null) {
+ if (lastRange == null) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ // lastRange was found
+ if (deltaX == 0) {
+ int lastY = y - deltaY;
+ if (lastRange[0] < centerX) {
+ if (lastRange[1] > centerX) {
+ // straddle, choose one or the other based on direction
+ return new ResultPoint(deltaY > 0 ? lastRange[0] : lastRange[1], lastY);
+ }
+ return new ResultPoint(lastRange[0], lastY);
+ } else {
+ return new ResultPoint(lastRange[1], lastY);
+ }
+ } else {
+ int lastX = x - deltaX;
+ if (lastRange[0] < centerY) {
+ if (lastRange[1] > centerY) {
+ return new ResultPoint(lastX, deltaX < 0 ? lastRange[0] : lastRange[1]);
+ }
+ return new ResultPoint(lastX, lastRange[0]);
+ } else {
+ return new ResultPoint(lastX, lastRange[1]);
+ }
+ }
+ }
+ lastRange = range;
+ }
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ /**
+ * Computes the start and end of a region of pixels, either horizontally or vertically, that could
+ * be part of a Data Matrix barcode.
+ *
+ * @param fixedDimension if scanning horizontally, this is the row (the fixed vertical location)
+ * where we are scanning. If scanning vertically it's the column, the fixed horizontal location
+ * @param maxWhiteRun largest run of white pixels that can still be considered part of the
+ * barcode region
+ * @param minDim minimum pixel location, horizontally or vertically, to consider
+ * @param maxDim maximum pixel location, horizontally or vertically, to consider
+ * @param horizontal if true, we're scanning left-right, instead of up-down
+ * @return int[] with start and end of found range, or null if no such range is found
+ * (e.g. only white was found)
+ */
+ private int[] blackWhiteRange(int fixedDimension, int maxWhiteRun, int minDim, int maxDim,
+ boolean horizontal) {
+
+ int center = (minDim + maxDim) >> 1;
+
+ // Scan left/up first
+ int start = center;
+ while (start >= minDim) {
+ if (horizontal ? image.get(start, fixedDimension) : image.get(fixedDimension, start)) {
+ start--;
+ } else {
+ int whiteRunStart = start;
+ do {
+ start--;
+ } while (start >= minDim && !(horizontal ? image.get(start, fixedDimension) :
+ image.get(fixedDimension, start)));
+ int whiteRunSize = whiteRunStart - start;
+ if (start < minDim || whiteRunSize > maxWhiteRun) {
+ start = whiteRunStart;
+ break;
+ }
+ }
+ }
+ start++;
+
+ // Then try right/down
+ int end = center;
+ while (end < maxDim) {
+ if (horizontal ? image.get(end, fixedDimension) : image.get(fixedDimension, end)) {
+ end++;
+ } else {
+ int whiteRunStart = end;
+ do {
+ end++;
+ } while (end < maxDim && !(horizontal ? image.get(end, fixedDimension) :
+ image.get(fixedDimension, end)));
+ int whiteRunSize = end - whiteRunStart;
+ if (end >= maxDim || whiteRunSize > maxWhiteRun) {
+ end = whiteRunStart;
+ break;
+ }
+ }
+ }
+ end--;
+
+ return end > start ? new int[]{start, end} : null;
+ }
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/detector/WhiteRectangleDetector.java b/libraries/zxing/src/com/google/zxing/common/detector/WhiteRectangleDetector.java
new file mode 100644
index 000000000..31d87e9d0
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/detector/WhiteRectangleDetector.java
@@ -0,0 +1,347 @@
+/*
+ * Copyright 2010 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.detector;
+
+import com.google.zxing.NotFoundException;
+import com.google.zxing.ResultPoint;
+import com.google.zxing.common.BitMatrix;
+
+/**
+ * <p>
+ * Detects a candidate barcode-like rectangular region within an image. It
+ * starts around the center of the image, increases the size of the candidate
+ * region until it finds a white rectangular region. By keeping track of the
+ * last black points it encountered, it determines the corners of the barcode.
+ * </p>
+ *
+ * @author David Olivier
+ */
+public final class WhiteRectangleDetector {
+
+ private static final int INIT_SIZE = 30;
+ private static final int CORR = 1;
+
+ private final BitMatrix image;
+ private final int height;
+ private final int width;
+ private final int leftInit;
+ private final int rightInit;
+ private final int downInit;
+ private final int upInit;
+
+ /**
+ * @throws NotFoundException if image is too small
+ */
+ public WhiteRectangleDetector(BitMatrix image) throws NotFoundException {
+ this.image = image;
+ height = image.getHeight();
+ width = image.getWidth();
+ leftInit = (width - INIT_SIZE) >> 1;
+ rightInit = (width + INIT_SIZE) >> 1;
+ upInit = (height - INIT_SIZE) >> 1;
+ downInit = (height + INIT_SIZE) >> 1;
+ if (upInit < 0 || leftInit < 0 || downInit >= height || rightInit >= width) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ }
+
+ /**
+ * @throws NotFoundException if image is too small
+ */
+ public WhiteRectangleDetector(BitMatrix image, int initSize, int x, int y) throws NotFoundException {
+ this.image = image;
+ height = image.getHeight();
+ width = image.getWidth();
+ int halfsize = initSize >> 1;
+ leftInit = x - halfsize;
+ rightInit = x + halfsize;
+ upInit = y - halfsize;
+ downInit = y + halfsize;
+ if (upInit < 0 || leftInit < 0 || downInit >= height || rightInit >= width) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ }
+
+ /**
+ * <p>
+ * Detects a candidate barcode-like rectangular region within an image. It
+ * starts around the center of the image, increases the size of the candidate
+ * region until it finds a white rectangular region.
+ * </p>
+ *
+ * @return {@link ResultPoint[]} describing the corners of the rectangular
+ * region. The first and last points are opposed on the diagonal, as
+ * are the second and third. The first point will be the topmost
+ * point and the last, the bottommost. The second point will be
+ * leftmost and the third, the rightmost
+ * @throws NotFoundException if no Data Matrix Code can be found
+ */
+ public ResultPoint[] detect() throws NotFoundException {
+
+ int left = leftInit;
+ int right = rightInit;
+ int up = upInit;
+ int down = downInit;
+ boolean sizeExceeded = false;
+ boolean aBlackPointFoundOnBorder = true;
+ boolean atLeastOneBlackPointFoundOnBorder = false;
+
+ while (aBlackPointFoundOnBorder) {
+
+ aBlackPointFoundOnBorder = false;
+
+ // .....
+ // . |
+ // .....
+ boolean rightBorderNotWhite = true;
+ while (rightBorderNotWhite && right < width) {
+ rightBorderNotWhite = containsBlackPoint(up, down, right, false);
+ if (rightBorderNotWhite) {
+ right++;
+ aBlackPointFoundOnBorder = true;
+ }
+ }
+
+ if (right >= width) {
+ sizeExceeded = true;
+ break;
+ }
+
+ // .....
+ // . .
+ // .___.
+ boolean bottomBorderNotWhite = true;
+ while (bottomBorderNotWhite && down < height) {
+ bottomBorderNotWhite = containsBlackPoint(left, right, down, true);
+ if (bottomBorderNotWhite) {
+ down++;
+ aBlackPointFoundOnBorder = true;
+ }
+ }
+
+ if (down >= height) {
+ sizeExceeded = true;
+ break;
+ }
+
+ // .....
+ // | .
+ // .....
+ boolean leftBorderNotWhite = true;
+ while (leftBorderNotWhite && left >= 0) {
+ leftBorderNotWhite = containsBlackPoint(up, down, left, false);
+ if (leftBorderNotWhite) {
+ left--;
+ aBlackPointFoundOnBorder = true;
+ }
+ }
+
+ if (left < 0) {
+ sizeExceeded = true;
+ break;
+ }
+
+ // .___.
+ // . .
+ // .....
+ boolean topBorderNotWhite = true;
+ while (topBorderNotWhite && up >= 0) {
+ topBorderNotWhite = containsBlackPoint(left, right, up, true);
+ if (topBorderNotWhite) {
+ up--;
+ aBlackPointFoundOnBorder = true;
+ }
+ }
+
+ if (up < 0) {
+ sizeExceeded = true;
+ break;
+ }
+
+ if (aBlackPointFoundOnBorder) {
+ atLeastOneBlackPointFoundOnBorder = true;
+ }
+
+ }
+
+ if (!sizeExceeded && atLeastOneBlackPointFoundOnBorder) {
+
+ int maxSize = right - left;
+
+ ResultPoint z = null;
+ for (int i = 1; i < maxSize; i++) {
+ z = getBlackPointOnSegment(left, down - i, left + i, down);
+ if (z != null) {
+ break;
+ }
+ }
+
+ if (z == null) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ ResultPoint t = null;
+ //go down right
+ for (int i = 1; i < maxSize; i++) {
+ t = getBlackPointOnSegment(left, up + i, left + i, up);
+ if (t != null) {
+ break;
+ }
+ }
+
+ if (t == null) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ ResultPoint x = null;
+ //go down left
+ for (int i = 1; i < maxSize; i++) {
+ x = getBlackPointOnSegment(right, up + i, right - i, up);
+ if (x != null) {
+ break;
+ }
+ }
+
+ if (x == null) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ ResultPoint y = null;
+ //go up left
+ for (int i = 1; i < maxSize; i++) {
+ y = getBlackPointOnSegment(right, down - i, right - i, down);
+ if (y != null) {
+ break;
+ }
+ }
+
+ if (y == null) {
+ throw NotFoundException.getNotFoundInstance();
+ }
+
+ return centerEdges(y, z, x, t);
+
+ } else {
+ throw NotFoundException.getNotFoundInstance();
+ }
+ }
+
+ /**
+ * Ends up being a bit faster than Math.round(). This merely rounds its
+ * argument to the nearest int, where x.5 rounds up.
+ */
+ private static int round(float d) {
+ return (int) (d + 0.5f);
+ }
+
+ private ResultPoint getBlackPointOnSegment(float aX, float aY, float bX, float bY) {
+ int dist = distanceL2(aX, aY, bX, bY);
+ float xStep = (bX - aX) / dist;
+ float yStep = (bY - aY) / dist;
+
+ for (int i = 0; i < dist; i++) {
+ int x = round(aX + i * xStep);
+ int y = round(aY + i * yStep);
+ if (image.get(x, y)) {
+ return new ResultPoint(x, y);
+ }
+ }
+ return null;
+ }
+
+ private static int distanceL2(float aX, float aY, float bX, float bY) {
+ float xDiff = aX - bX;
+ float yDiff = aY - bY;
+ return round((float) Math.sqrt(xDiff * xDiff + yDiff * yDiff));
+ }
+
+ /**
+ * recenters the points of a constant distance towards the center
+ *
+ * @param y bottom most point
+ * @param z left most point
+ * @param x right most point
+ * @param t top most point
+ * @return {@link ResultPoint}[] describing the corners of the rectangular
+ * region. The first and last points are opposed on the diagonal, as
+ * are the second and third. The first point will be the topmost
+ * point and the last, the bottommost. The second point will be
+ * leftmost and the third, the rightmost
+ */
+ private ResultPoint[] centerEdges(ResultPoint y, ResultPoint z,
+ ResultPoint x, ResultPoint t) {
+
+ //
+ // t t
+ // z x
+ // x OR z
+ // y y
+ //
+
+ float yi = y.getX();
+ float yj = y.getY();
+ float zi = z.getX();
+ float zj = z.getY();
+ float xi = x.getX();
+ float xj = x.getY();
+ float ti = t.getX();
+ float tj = t.getY();
+
+ if (yi < width / 2) {
+ return new ResultPoint[]{
+ new ResultPoint(ti - CORR, tj + CORR),
+ new ResultPoint(zi + CORR, zj + CORR),
+ new ResultPoint(xi - CORR, xj - CORR),
+ new ResultPoint(yi + CORR, yj - CORR)};
+ } else {
+ return new ResultPoint[]{
+ new ResultPoint(ti + CORR, tj + CORR),
+ new ResultPoint(zi + CORR, zj - CORR),
+ new ResultPoint(xi - CORR, xj + CORR),
+ new ResultPoint(yi - CORR, yj - CORR)};
+ }
+ }
+
+ /**
+ * Determines whether a segment contains a black point
+ *
+ * @param a min value of the scanned coordinate
+ * @param b max value of the scanned coordinate
+ * @param fixed value of fixed coordinate
+ * @param horizontal set to true if scan must be horizontal, false if vertical
+ * @return true if a black point has been found, else false.
+ */
+ private boolean containsBlackPoint(int a, int b, int fixed, boolean horizontal) {
+
+ if (horizontal) {
+ for (int x = a; x <= b; x++) {
+ if (image.get(x, fixed)) {
+ return true;
+ }
+ }
+ } else {
+ for (int y = a; y <= b; y++) {
+ if (image.get(fixed, y)) {
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+} \ No newline at end of file
diff --git a/libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGF.java b/libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGF.java
new file mode 100644
index 000000000..859c379ee
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGF.java
@@ -0,0 +1,188 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>This class contains utility methods for performing mathematical operations over
+ * the Galois Fields. Operations use a given primitive polynomial in calculations.</p>
+ *
+ * <p>Throughout this package, elements of the GF are represented as an <code>int</code>
+ * for convenience and speed (but at the cost of memory).
+ * </p>
+ *
+ * @author Sean Owen
+ * @author David Olivier
+ */
+public final class GenericGF {
+
+ public static final GenericGF AZTEC_DATA_12 = new GenericGF(0x1069, 4096); // x^12 + x^6 + x^5 + x^3 + 1
+ public static final GenericGF AZTEC_DATA_10 = new GenericGF(0x409, 1024); // x^10 + x^3 + 1
+ public static final GenericGF AZTEC_DATA_6 = new GenericGF(0x43, 64); // x^6 + x + 1
+ public static final GenericGF AZTEC_PARAM = new GenericGF(0x13, 16); // x^4 + x + 1
+ public static final GenericGF QR_CODE_FIELD_256 = new GenericGF(0x011D, 256); // x^8 + x^4 + x^3 + x^2 + 1
+ public static final GenericGF DATA_MATRIX_FIELD_256 = new GenericGF(0x012D, 256); // x^8 + x^5 + x^3 + x^2 + 1
+ public static final GenericGF AZTEC_DATA_8 = DATA_MATRIX_FIELD_256;
+
+ private static final int INITIALIZATION_THRESHOLD = 0;
+
+ private int[] expTable;
+ private int[] logTable;
+ private GenericGFPoly zero;
+ private GenericGFPoly one;
+ private final int size;
+ private final int primitive;
+ private boolean initialized = false;
+
+ /**
+ * Create a representation of GF(size) 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
+ */
+ public GenericGF(int primitive, int size) {
+ this.primitive = primitive;
+ this.size = size;
+
+ if (size <= INITIALIZATION_THRESHOLD){
+ initialize();
+ }
+ }
+
+ private void initialize(){
+ expTable = new int[size];
+ logTable = new int[size];
+ int x = 1;
+ for (int i = 0; i < size; i++) {
+ expTable[i] = x;
+ x <<= 1; // x = x * 2; we're assuming the generator alpha is 2
+ if (x >= size) {
+ x ^= primitive;
+ x &= size-1;
+ }
+ }
+ for (int i = 0; i < size-1; i++) {
+ logTable[expTable[i]] = i;
+ }
+ // logTable[0] == 0 but this should never be used
+ zero = new GenericGFPoly(this, new int[]{0});
+ one = new GenericGFPoly(this, new int[]{1});
+ initialized = true;
+ }
+
+ private void checkInit(){
+ if (!initialized) {
+ initialize();
+ }
+ }
+
+ GenericGFPoly getZero() {
+ checkInit();
+
+ return zero;
+ }
+
+ GenericGFPoly getOne() {
+ checkInit();
+
+ return one;
+ }
+
+ /**
+ * @return the monomial representing coefficient * x^degree
+ */
+ GenericGFPoly buildMonomial(int degree, int coefficient) {
+ checkInit();
+
+ if (degree < 0) {
+ throw new IllegalArgumentException();
+ }
+ if (coefficient == 0) {
+ return zero;
+ }
+ int[] coefficients = new int[degree + 1];
+ coefficients[0] = coefficient;
+ return new GenericGFPoly(this, coefficients);
+ }
+
+ /**
+ * Implements both addition and subtraction -- they are the same in GF(size).
+ *
+ * @return sum/difference of a and b
+ */
+ static int addOrSubtract(int a, int b) {
+ return a ^ b;
+ }
+
+ /**
+ * @return 2 to the power of a in GF(size)
+ */
+ int exp(int a) {
+ checkInit();
+
+ return expTable[a];
+ }
+
+ /**
+ * @return base 2 log of a in GF(size)
+ */
+ int log(int a) {
+ checkInit();
+
+ if (a == 0) {
+ throw new IllegalArgumentException();
+ }
+ return logTable[a];
+ }
+
+ /**
+ * @return multiplicative inverse of a
+ */
+ int inverse(int a) {
+ checkInit();
+
+ if (a == 0) {
+ throw new ArithmeticException();
+ }
+ return expTable[size - logTable[a] - 1];
+ }
+
+ /**
+ * @param a
+ * @param b
+ * @return product of a and b in GF(size)
+ */
+ int multiply(int a, int b) {
+ checkInit();
+
+ if (a == 0 || b == 0) {
+ return 0;
+ }
+
+ if (a<0 || b <0 || a>=size || b >=size){
+ a++;
+ }
+
+ int logSum = logTable[a] + logTable[b];
+ return expTable[(logSum % size) + logSum / size];
+ }
+
+ public int getSize(){
+ return size;
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGFPoly.java b/libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGFPoly.java
new file mode 100644
index 000000000..056802287
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/reedsolomon/GenericGFPoly.java
@@ -0,0 +1,263 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>Represents a polynomial whose coefficients are elements of a GF.
+ * Instances of this class are immutable.</p>
+ *
+ * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
+ * port of his C++ Reed-Solomon implementation.</p>
+ *
+ * @author Sean Owen
+ */
+final class GenericGFPoly {
+
+ private final GenericGF field;
+ private final int[] coefficients;
+
+ /**
+ * @param field the {@link GenericGF} instance representing the field to use
+ * to perform computations
+ * @param coefficients coefficients as ints representing elements of GF(size), 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")
+ */
+ GenericGFPoly(GenericGF field, int[] coefficients) {
+ if (coefficients == null || coefficients.length == 0) {
+ throw new IllegalArgumentException();
+ }
+ this.field = field;
+ int coefficientsLength = coefficients.length;
+ if (coefficientsLength > 1 && coefficients[0] == 0) {
+ // Leading term must be non-zero for anything except the constant polynomial "0"
+ int firstNonZero = 1;
+ while (firstNonZero < coefficientsLength && coefficients[firstNonZero] == 0) {
+ firstNonZero++;
+ }
+ if (firstNonZero == coefficientsLength) {
+ this.coefficients = field.getZero().coefficients;
+ } else {
+ this.coefficients = new int[coefficientsLength - firstNonZero];
+ System.arraycopy(coefficients,
+ firstNonZero,
+ this.coefficients,
+ 0,
+ this.coefficients.length);
+ }
+ } else {
+ this.coefficients = coefficients;
+ }
+ }
+
+ int[] getCoefficients() {
+ return coefficients;
+ }
+
+ /**
+ * @return degree of this polynomial
+ */
+ int getDegree() {
+ return coefficients.length - 1;
+ }
+
+ /**
+ * @return true iff this polynomial is the monomial "0"
+ */
+ boolean isZero() {
+ return coefficients[0] == 0;
+ }
+
+ /**
+ * @return coefficient of x^degree term in this polynomial
+ */
+ int getCoefficient(int degree) {
+ return coefficients[coefficients.length - 1 - degree];
+ }
+
+ /**
+ * @return evaluation of this polynomial at a given point
+ */
+ int evaluateAt(int a) {
+ if (a == 0) {
+ // Just return the x^0 coefficient
+ return getCoefficient(0);
+ }
+ int size = coefficients.length;
+ if (a == 1) {
+ // Just the sum of the coefficients
+ int result = 0;
+ for (int i = 0; i < size; i++) {
+ result = GenericGF.addOrSubtract(result, coefficients[i]);
+ }
+ return result;
+ }
+ int result = coefficients[0];
+ for (int i = 1; i < size; i++) {
+ result = GenericGF.addOrSubtract(field.multiply(a, result), coefficients[i]);
+ }
+ return result;
+ }
+
+ GenericGFPoly addOrSubtract(GenericGFPoly other) {
+ if (!field.equals(other.field)) {
+ throw new IllegalArgumentException("GenericGFPolys do not have same GenericGF field");
+ }
+ if (isZero()) {
+ return other;
+ }
+ if (other.isZero()) {
+ return this;
+ }
+
+ int[] smallerCoefficients = this.coefficients;
+ int[] largerCoefficients = other.coefficients;
+ if (smallerCoefficients.length > largerCoefficients.length) {
+ int[] temp = smallerCoefficients;
+ smallerCoefficients = largerCoefficients;
+ largerCoefficients = temp;
+ }
+ int[] sumDiff = new int[largerCoefficients.length];
+ int lengthDiff = largerCoefficients.length - smallerCoefficients.length;
+ // Copy high-order terms only found in higher-degree polynomial's coefficients
+ System.arraycopy(largerCoefficients, 0, sumDiff, 0, lengthDiff);
+
+ for (int i = lengthDiff; i < largerCoefficients.length; i++) {
+ sumDiff[i] = GenericGF.addOrSubtract(smallerCoefficients[i - lengthDiff], largerCoefficients[i]);
+ }
+
+ return new GenericGFPoly(field, sumDiff);
+ }
+
+ GenericGFPoly multiply(GenericGFPoly other) {
+ if (!field.equals(other.field)) {
+ throw new IllegalArgumentException("GenericGFPolys do not have same GenericGF field");
+ }
+ if (isZero() || other.isZero()) {
+ return field.getZero();
+ }
+ int[] aCoefficients = this.coefficients;
+ int aLength = aCoefficients.length;
+ int[] bCoefficients = other.coefficients;
+ int bLength = bCoefficients.length;
+ int[] product = new int[aLength + bLength - 1];
+ for (int i = 0; i < aLength; i++) {
+ int aCoeff = aCoefficients[i];
+ for (int j = 0; j < bLength; j++) {
+ product[i + j] = GenericGF.addOrSubtract(product[i + j],
+ field.multiply(aCoeff, bCoefficients[j]));
+ }
+ }
+ return new GenericGFPoly(field, product);
+ }
+
+ GenericGFPoly multiply(int scalar) {
+ if (scalar == 0) {
+ return field.getZero();
+ }
+ if (scalar == 1) {
+ return this;
+ }
+ int size = coefficients.length;
+ int[] product = new int[size];
+ for (int i = 0; i < size; i++) {
+ product[i] = field.multiply(coefficients[i], scalar);
+ }
+ return new GenericGFPoly(field, product);
+ }
+
+ GenericGFPoly multiplyByMonomial(int degree, int coefficient) {
+ if (degree < 0) {
+ throw new IllegalArgumentException();
+ }
+ if (coefficient == 0) {
+ return field.getZero();
+ }
+ int size = coefficients.length;
+ int[] product = new int[size + degree];
+ for (int i = 0; i < size; i++) {
+ product[i] = field.multiply(coefficients[i], coefficient);
+ }
+ return new GenericGFPoly(field, product);
+ }
+
+ GenericGFPoly[] divide(GenericGFPoly other) {
+ if (!field.equals(other.field)) {
+ throw new IllegalArgumentException("GenericGFPolys do not have same GenericGF field");
+ }
+ if (other.isZero()) {
+ throw new IllegalArgumentException("Divide by 0");
+ }
+
+ GenericGFPoly quotient = field.getZero();
+ GenericGFPoly 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);
+ GenericGFPoly term = other.multiplyByMonomial(degreeDifference, scale);
+ GenericGFPoly iterationQuotient = field.buildMonomial(degreeDifference, scale);
+ quotient = quotient.addOrSubtract(iterationQuotient);
+ remainder = remainder.addOrSubtract(term);
+ }
+
+ return new GenericGFPoly[] { 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();
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java b/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java
new file mode 100644
index 000000000..b523fd34b
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java
@@ -0,0 +1,194 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>Implements Reed-Solomon decoding, as the name implies.</p>
+ *
+ * <p>The algorithm will not be explained here, but the following references were helpful
+ * in creating this implementation:</p>
+ *
+ * <ul>
+ * <li>Bruce Maggs.
+ * <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps">
+ * "Decoding Reed-Solomon Codes"</a> (see discussion of Forney's Formula)</li>
+ * <li>J.I. Hall. <a href="www.mth.msu.edu/~jhall/classes/codenotes/GRS.pdf">
+ * "Chapter 5. Generalized Reed-Solomon Codes"</a>
+ * (see discussion of Euclidean algorithm)</li>
+ * </ul>
+ *
+ * <p>Much credit is due to William Rucklidge since portions of this code are an indirect
+ * port of his C++ Reed-Solomon implementation.</p>
+ *
+ * @author Sean Owen
+ * @author William Rucklidge
+ * @author sanfordsquires
+ */
+public final class ReedSolomonDecoder {
+
+ private final GenericGF field;
+
+ public ReedSolomonDecoder(GenericGF field) {
+ this.field = field;
+ }
+
+ /**
+ * <p>Decodes given set of received codewords, which include both data and error-correction
+ * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place,
+ * in the input.</p>
+ *
+ * @param received data and error-correction codewords
+ * @param twoS number of error-correction codewords available
+ * @throws ReedSolomonException if decoding fails for any reason
+ */
+ public void decode(int[] received, int twoS) throws ReedSolomonException {
+ GenericGFPoly poly = new GenericGFPoly(field, received);
+ int[] syndromeCoefficients = new int[twoS];
+ boolean dataMatrix = field.equals(GenericGF.DATA_MATRIX_FIELD_256);
+ boolean noError = true;
+ for (int i = 0; i < twoS; 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;
+ }
+ GenericGFPoly syndrome = new GenericGFPoly(field, syndromeCoefficients);
+ GenericGFPoly[] sigmaOmega =
+ runEuclideanAlgorithm(field.buildMonomial(twoS, 1), syndrome, twoS);
+ GenericGFPoly sigma = sigmaOmega[0];
+ GenericGFPoly 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] = GenericGF.addOrSubtract(received[position], errorMagnitudes[i]);
+ }
+ }
+
+ private GenericGFPoly[] runEuclideanAlgorithm(GenericGFPoly a, GenericGFPoly b, int R)
+ throws ReedSolomonException {
+ // Assume a's degree is >= b's
+ if (a.getDegree() < b.getDegree()) {
+ GenericGFPoly temp = a;
+ a = b;
+ b = temp;
+ }
+
+ GenericGFPoly rLast = a;
+ GenericGFPoly r = b;
+ GenericGFPoly sLast = field.getOne();
+ GenericGFPoly s = field.getZero();
+ GenericGFPoly tLast = field.getZero();
+ GenericGFPoly t = field.getOne();
+
+ // Run Euclidean algorithm until r's degree is less than R/2
+ while (r.getDegree() >= R / 2) {
+ GenericGFPoly rLastLast = rLast;
+ GenericGFPoly sLastLast = sLast;
+ GenericGFPoly tLastLast = tLast;
+ rLast = r;
+ sLast = s;
+ tLast = t;
+
+ // Divide rLastLast by rLast, with quotient in q and remainder in r
+ if (rLast.isZero()) {
+ // Oops, Euclidean algorithm already terminated?
+ throw new ReedSolomonException("r_{i-1} was zero");
+ }
+ r = rLastLast;
+ GenericGFPoly q = field.getZero();
+ int denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree());
+ int dltInverse = field.inverse(denominatorLeadingTerm);
+ while (r.getDegree() >= rLast.getDegree() && !r.isZero()) {
+ int degreeDiff = r.getDegree() - rLast.getDegree();
+ int scale = field.multiply(r.getCoefficient(r.getDegree()), dltInverse);
+ q = q.addOrSubtract(field.buildMonomial(degreeDiff, scale));
+ r = r.addOrSubtract(rLast.multiplyByMonomial(degreeDiff, scale));
+ }
+
+ s = q.multiply(sLast).addOrSubtract(sLastLast);
+ t = q.multiply(tLast).addOrSubtract(tLastLast);
+ }
+
+ int sigmaTildeAtZero = t.getCoefficient(0);
+ if (sigmaTildeAtZero == 0) {
+ throw new ReedSolomonException("sigmaTilde(0) was zero");
+ }
+
+ int inverse = field.inverse(sigmaTildeAtZero);
+ GenericGFPoly sigma = t.multiply(inverse);
+ GenericGFPoly omega = r.multiply(inverse);
+ return new GenericGFPoly[]{sigma, omega};
+ }
+
+ private int[] findErrorLocations(GenericGFPoly errorLocator) throws ReedSolomonException {
+ // This is a direct application of Chien's search
+ 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 < field.getSize() && e < numErrors; i++) {
+ if (errorLocator.evaluateAt(i) == 0) {
+ result[e] = field.inverse(i);
+ e++;
+ }
+ }
+ if (e != numErrors) {
+ throw new ReedSolomonException("Error locator degree does not match number of roots");
+ }
+ return result;
+ }
+
+ private int[] findErrorMagnitudes(GenericGFPoly 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 < s; i++) {
+ int xiInverse = field.inverse(errorLocations[i]);
+ int denominator = 1;
+ for (int j = 0; j < s; j++) {
+ if (i != j) {
+ //denominator = field.multiply(denominator,
+ // GenericGF.addOrSubtract(1, field.multiply(errorLocations[j], xiInverse)));
+ // Above should work but fails on some Apple and Linux JDKs due to a Hotspot bug.
+ // Below is a funny-looking workaround from Steven Parkes
+ int term = field.multiply(errorLocations[j], xiInverse);
+ int termPlus1 = (term & 0x1) == 0 ? term | 1 : term & ~1;
+ denominator = field.multiply(denominator, termPlus1);
+ }
+ }
+ 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/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonEncoder.java b/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonEncoder.java
new file mode 100644
index 000000000..05e2ae03a
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonEncoder.java
@@ -0,0 +1,75 @@
+/*
+ * 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 Sean Owen
+ * @author William Rucklidge
+ */
+public final class ReedSolomonEncoder {
+
+ private final GenericGF field;
+ private final Vector cachedGenerators;
+
+ public ReedSolomonEncoder(GenericGF field) {
+ if (!GenericGF.QR_CODE_FIELD_256.equals(field)) {
+ throw new IllegalArgumentException("Only QR Code is supported at this time");
+ }
+ this.field = field;
+ this.cachedGenerators = new Vector();
+ cachedGenerators.addElement(new GenericGFPoly(field, new int[] { 1 }));
+ }
+
+ private GenericGFPoly buildGenerator(int degree) {
+ if (degree >= cachedGenerators.size()) {
+ GenericGFPoly lastGenerator = (GenericGFPoly) cachedGenerators.elementAt(cachedGenerators.size() - 1);
+ for (int d = cachedGenerators.size(); d <= degree; d++) {
+ GenericGFPoly nextGenerator = lastGenerator.multiply(new GenericGFPoly(field, new int[] { 1, field.exp(d - 1) }));
+ cachedGenerators.addElement(nextGenerator);
+ lastGenerator = nextGenerator;
+ }
+ }
+ return (GenericGFPoly) cachedGenerators.elementAt(degree);
+ }
+
+ public void encode(int[] toEncode, int ecBytes) {
+ if (ecBytes == 0) {
+ throw new IllegalArgumentException("No error correction bytes");
+ }
+ int dataBytes = toEncode.length - ecBytes;
+ if (dataBytes <= 0) {
+ throw new IllegalArgumentException("No data bytes provided");
+ }
+ GenericGFPoly generator = buildGenerator(ecBytes);
+ int[] infoCoefficients = new int[dataBytes];
+ System.arraycopy(toEncode, 0, infoCoefficients, 0, dataBytes);
+ GenericGFPoly info = new GenericGFPoly(field, infoCoefficients);
+ info = info.multiplyByMonomial(ecBytes, 1);
+ GenericGFPoly remainder = info.divide(generator)[1];
+ int[] coefficients = remainder.getCoefficients();
+ int numZeroCoefficients = ecBytes - coefficients.length;
+ for (int i = 0; i < numZeroCoefficients; i++) {
+ toEncode[dataBytes + i] = 0;
+ }
+ System.arraycopy(coefficients, 0, toEncode, dataBytes + numZeroCoefficients, coefficients.length);
+ }
+
+}
diff --git a/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonException.java b/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonException.java
new file mode 100644
index 000000000..d5b45a612
--- /dev/null
+++ b/libraries/zxing/src/com/google/zxing/common/reedsolomon/ReedSolomonException.java
@@ -0,0 +1,31 @@
+/*
+ * 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.
+ * 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;
+
+/**
+ * <p>Thrown when an exception occurs during Reed-Solomon decoding, such as when
+ * there are too many errors to correct.</p>
+ *
+ * @author Sean Owen
+ */
+public final class ReedSolomonException extends Exception {
+
+ public ReedSolomonException(String message) {
+ super(message);
+ }
+
+} \ No newline at end of file