private FormatInformation parsedFormatInfo;\r
\r
/**\r
- * @throws com.google.zxing.ReaderException\r
- * if dimension is not >= 21 and 1 mod 4\r
+ * @param bitMatrix {@link BitMatrix} to parse\r
+ * @throws ReaderException if dimension is not >= 21 and 1 mod 4\r
*/\r
BitMatrixParser(BitMatrix bitMatrix) throws ReaderException {\r
int dimension = bitMatrix.getDimension();\r
this.bitMatrix = bitMatrix;\r
}\r
\r
+ /**\r
+ * <p>Reads format information from one of its two locations within the QR Code.</p>\r
+ *\r
+ * @return {@link FormatInformation} encapsulating the QR Code's format info\r
+ * @throws ReaderException if both format information locations cannot be parsed as\r
+ * the valid encoding of format information\r
+ */\r
FormatInformation readFormatInformation() throws ReaderException {\r
\r
if (parsedFormatInfo != null) {\r
throw new ReaderException("Could not decode format information");\r
}\r
\r
+ /**\r
+ * <p>Reads version information from one of its two locations within the QR Code.</p>\r
+ *\r
+ * @return {@link Version} encapsulating the QR Code's version\r
+ * @throws ReaderException if both version information locations cannot be parsed as\r
+ * the valid encoding of version information\r
+ */\r
Version readVersion() throws ReaderException {\r
\r
if (parsedVersion != null) {\r
return bitMatrix.get(i, j) ? (versionBits << 1) | 0x1 : versionBits << 1;\r
}\r
\r
+ /**\r
+ * <p>Reads the bits in the {@link BitMatrix} representing the finder pattern in the\r
+ * correct order in order to reconstitute the codewords bytes contained within the\r
+ * QR Code.</p>\r
+ *\r
+ * @return bytes encoded within the QR Code\r
+ * @throws ReaderException if the exact number of bytes expected is not read\r
+ */\r
byte[] readCodewords() throws ReaderException {\r
\r
FormatInformation formatInfo = readFormatInformation();\r
Version version = readVersion();\r
\r
+ // Get the data mask for the format used in this QR Code. This will exclude\r
+ // some bits from reading as we wind through the bit matrix.\r
DataMask dataMask = DataMask.forReference((int) formatInfo.getDataMask());\r
int dimension = bitMatrix.getDimension();\r
dataMask.unmaskBitMatrix(bitMatrix.getBits(), dimension);\r
int resultOffset = 0;\r
int currentByte = 0;\r
int bitsRead = 0;\r
+ // Read columns in pairs, from right to left\r
for (int j = dimension - 1; j > 0; j -= 2) {\r
if (j == 6) {\r
// Skip whole column with vertical alignment pattern;\r
// saves time and makes the other code proceed more cleanly\r
j--;\r
}\r
+ // Read alternatingly from bottom to top then top to bottom\r
for (int count = 0; count < dimension; count++) {\r
int i = readingUp ? dimension - 1 - count : count;\r
for (int col = 0; col < 2; col++) {\r
+ // Ignore bits covered by the function pattern\r
if (!functionPattern.get(i, j - col)) {\r
+ // Read a bit\r
bitsRead++;\r
currentByte <<= 1;\r
if (bitMatrix.get(i, j - col)) {\r
currentByte |= 1;\r
}\r
+ // If we've made a whole byte, save it off\r
if (bitsRead == 8) {\r
result[resultOffset++] = (byte) currentByte;\r
bitsRead = 0;\r
package com.google.zxing.qrcode.decoder;\r
\r
/**\r
- * This provides an easy abstraction to read bits at a time from a sequence of bytes, where the\r
- * number of bits read is not often a multiple of 8.\r
+ * <p>This provides an easy abstraction to read bits at a time from a sequence of bytes, where the\r
+ * number of bits read is not often a multiple of 8.</p>\r
+ *\r
+ * <p>This class is not thread-safe.</p>\r
*\r
* @author srowen@google.com (Sean Owen)\r
*/\r
private int byteOffset;\r
private int bitOffset;\r
\r
+ /**\r
+ * @param bytes bytes from which this will read bits. Bits will be read from the first byte first.\r
+ * Bits are read within a byte from most-significant to least-significant bit.\r
+ */\r
BitSource(byte[] bytes) {\r
this.bytes = bytes;\r
}\r
\r
/**\r
+ * @param numBits number of bits to read\r
+ * @return int representing the bits read. The bits will appear as the least-significant\r
+ * bits of the int\r
* @throws IllegalArgumentException if numBits isn't in [1,32]\r
*/\r
int readBits(int numBits) {\r
return result;\r
}\r
\r
+ /**\r
+ * @return number of bits that can be read successfully\r
+ */\r
int available() {\r
return 8 * (bytes.length - byteOffset) - bitOffset;\r
}\r
package com.google.zxing.qrcode.decoder;\r
\r
/**\r
+ * <p>Encapsulates a block of data within a QR Code. QR Codes may split their data into\r
+ * multiple blocks, each of which is a unit of data and error-correction codewords. Each\r
+ * is represented by an instance of this class.</p>\r
+ *\r
* @author srowen@google.com (Sean Owen)\r
*/\r
final class DataBlock {\r
this.codewords = codewords;\r
}\r
\r
+ /**\r
+ * <p>When QR Codes use multiple data blocks, they are actually interleave the bytes of each of them.\r
+ * That is, the first byte of data block 1 to n is written, then the second bytes, and so on. This\r
+ * method will separate the data into original blocks.</p>\r
+ *\r
+ * @param rawCodewords bytes as read directly from the QR Code\r
+ * @param version version of the QR Code\r
+ * @param ecLevel error-correction level of the QR Code\r
+ * @return {@link DataBlock}s containing original bytes, "de-interleaved" from representation in the\r
+ * QR Code\r
+ */\r
static DataBlock[] getDataBlocks(byte[] rawCodewords,\r
Version version,\r
ErrorCorrectionLevel ecLevel) {\r
+ // Figure out the number and size of data blocks used by this version and\r
+ // error correction level\r
Version.ECBlocks ecBlocks = version.getECBlocksForLevel(ecLevel);\r
+\r
+ // First count the total number of data blocks\r
int totalBlocks = 0;\r
Version.ECB[] ecBlockArray = ecBlocks.getECBlocks();\r
for (int i = 0; i < ecBlockArray.length; i++) {\r
totalBlocks += ecBlockArray[i].getCount();\r
}\r
+\r
+ // Now establish DataBlocks of the appropriate size and number of data codewords\r
DataBlock[] result = new DataBlock[totalBlocks];\r
int numResultBlocks = 0;\r
for (int j = 0; j < ecBlockArray.length; j++) {\r
for (int i = 0; i < ecBlock.getCount(); i++) {\r
int numDataCodewords = ecBlock.getDataCodewords();\r
int numBlockCodewords = ecBlocks.getECCodewords() + numDataCodewords;\r
- result[numResultBlocks++] =\r
- new DataBlock(numDataCodewords, new byte[numBlockCodewords]);\r
+ result[numResultBlocks++] = new DataBlock(numDataCodewords, new byte[numBlockCodewords]);\r
}\r
}\r
\r
int shorterBlocksTotalCodewords = result[0].codewords.length;\r
int longerBlocksStartAt = result.length - 1;\r
while (longerBlocksStartAt >= 0) {\r
- int numCodewords =\r
- result[longerBlocksStartAt].codewords.length;\r
+ int numCodewords = result[longerBlocksStartAt].codewords.length;\r
if (numCodewords == shorterBlocksTotalCodewords) {\r
break;\r
}\r
if (numCodewords != shorterBlocksTotalCodewords + 1) {\r
- throw new IllegalStateException(\r
- "Data block sizes differ by more than 1");\r
+ throw new IllegalStateException("Data block sizes differ by more than 1");\r
}\r
longerBlocksStartAt--;\r
}\r
longerBlocksStartAt++;\r
\r
- int shorterBlocksNumDataCodewords =\r
- shorterBlocksTotalCodewords - ecBlocks.getECCodewords();\r
+ int shorterBlocksNumDataCodewords = shorterBlocksTotalCodewords - ecBlocks.getECCodewords();\r
// The last elements of result may be 1 element longer;\r
// first fill out as many elements as all of them have\r
int rawCodewordsOffset = 0;\r
}\r
// Fill out the last data block in the longer ones\r
for (int j = longerBlocksStartAt; j < numResultBlocks; j++) {\r
- result[j].codewords[shorterBlocksNumDataCodewords] =\r
- rawCodewords[rawCodewordsOffset++];\r
+ result[j].codewords[shorterBlocksNumDataCodewords] = rawCodewords[rawCodewordsOffset++];\r
}\r
// Now add in error correction blocks\r
int max = result[0].codewords.length;\r
package com.google.zxing.qrcode.decoder;\r
\r
/**\r
- * Encapsulates data masks for the data bits in a QR code, per ISO 18004:2006 6.8. Implementations\r
+ * <p>Encapsulates data masks for the data bits in a QR code, per ISO 18004:2006 6.8. Implementations\r
* of this class can un-mask a raw BitMatrix. For simplicity, they will unmask the entire BitMatrix,\r
* including areas used for finder patterns, timing patterns, etc. These areas should be unused\r
- * after the point they are unmasked anyway.\r
+ * after the point they are unmasked anyway.</p>\r
*\r
- * Note that the diagram in section 6.8.1 is misleading since it indicates that i is column position\r
- * and j is row position. In fact, as the text says, i is row position and j is column position.\r
+ * <p>Note that the diagram in section 6.8.1 is misleading since it indicates that i is column position\r
+ * and j is row position. In fact, as the text says, i is row position and j is column position.</p>\r
*\r
* @author srowen@google.com (Sean Owen)\r
*/\r
private DataMask() {\r
}\r
\r
+ /**\r
+ * <p>Implementations of this method reverse the data masking process applied to a QR Code and\r
+ * make its bits ready to read.</p>\r
+ *\r
+ * @param bits representation of QR Code bits from {@link com.google.zxing.common.BitMatrix#getBits()}\r
+ * @param dimension dimension of QR Code, represented by bits, being unmasked\r
+ */\r
abstract void unmaskBitMatrix(int[] bits, int dimension);\r
\r
+ /**\r
+ * @param reference a value between 0 and 7 indicating one of the eight possible\r
+ * data mask patterns a QR Code may use\r
+ * @return {@link DataMask} encapsulating the data mask pattern\r
+ */\r
static DataMask forReference(int reference) {\r
if (reference < 0 || reference > 7) {\r
throw new IllegalArgumentException();\r
import java.io.UnsupportedEncodingException;
/**
- * See ISO 18004:2006, 6.4.3 - 6.4.7
+ * <p>QR Codes can encode text as bits in one of several modes, and can use multiple modes
+ * in one QR Code. This class decodes the bits back into text.</p>
+ *
+ * <p>See ISO 18004:2006, 6.4.3 - 6.4.7</p>
*
* @author srowen@google.com (Sean Owen)
*/
Mode mode;
do {
// While still another segment to read...
- mode = Mode.forBits(bits.readBits(4));
+ mode = Mode.forBits(bits.readBits(4)); // mode is encoded by 4 bits
if (!mode.equals(Mode.TERMINATOR)) {
+ // How many characters will follow, encoded in this mode?
int count = bits.readBits(mode.getCharacterCountBits(version));
if (mode.equals(Mode.NUMERIC)) {
decodeNumericSegment(bits, result, count);
} else if (mode.equals(Mode.KANJI)) {
decodeKanjiSegment(bits, result, count);
} else {
- throw new ReaderException("Unsupported mode indicator: " + mode);
+ throw new ReaderException("Unsupported mode indicator");
}
}
} while (!mode.equals(Mode.TERMINATOR));
+ // I thought it wasn't allowed to leave extra bytes after the terminator but it happens
/*
int bitsLeft = bits.available();
if (bitsLeft > 0) {
private static void decodeKanjiSegment(BitSource bits,
StringBuffer result,
int count) throws ReaderException {
+ // Each character will require 2 bytes. Read the characters as 2-byte pairs
+ // and decode as Shift_JIS afterwards
byte[] buffer = new byte[2 * count];
int offset = 0;
while (count > 0) {
+ // Each 13 bits encodes a 2-byte character
int twoBytes = bits.readBits(13);
int assembledTwoBytes = ((twoBytes / 0x0C0) << 8) | (twoBytes % 0x0C0);
if (assembledTwoBytes < 0x01F00) {
count -= 2;
}
if (count == 1) {
- // special case on char left
+ // special case: one character left
result.append(ALPHANUMERIC_CHARS[bits.readBits(6)]);
}
}
private static void decodeNumericSegment(BitSource bits,
StringBuffer result,
int count) throws ReaderException {
+ // Read three digits at a time
while (count >= 3) {
+ // Each 10 bits encodes three digits
int threeDigitsBits = bits.readBits(10);
if (threeDigitsBits >= 1000) {
throw new ReaderException("Illegal value for 3-digit unit: " + threeDigitsBits);
count -= 3;
}
if (count == 2) {
+ // Two digits left over to read, encoded in 7 bits
int twoDigitsBits = bits.readBits(7);
if (twoDigitsBits >= 100) {
throw new ReaderException("Illegal value for 2-digit unit: " + twoDigitsBits);
result.append(ALPHANUMERIC_CHARS[twoDigitsBits / 10]);
result.append(ALPHANUMERIC_CHARS[twoDigitsBits % 10]);
} else if (count == 1) {
+ // One digit left over to read
int digitBits = bits.readBits(4);
if (digitBits >= 10) {
throw new ReaderException("Illegal value for digit unit: " + digitBits);
import com.google.zxing.common.reedsolomon.ReedSolomonException;\r
\r
/**\r
+ * <p>The main class which implements QR Code decoding -- as opposed to locating and extracting\r
+ * the QR Code from an image.</p>\r
+ *\r
* @author srowen@google.com (Sean Owen)\r
*/\r
public final class Decoder {\r
private Decoder() {\r
}\r
\r
+ /**\r
+ * <p>Convenience method that can decode a QR Code represented as a 2D array of booleans.\r
+ * "true" is taken to mean a black module.</p>\r
+ *\r
+ * @param image booleans representing white/black QR Code modules\r
+ * @return text encoded within the QR Code\r
+ * @throws ReaderException if the QR Code cannot be decoded\r
+ */\r
public static String decode(boolean[][] image) throws ReaderException {\r
int dimension = image.length;\r
BitMatrix bits = new BitMatrix(dimension);\r
return decode(bits);\r
}\r
\r
+ /**\r
+ * <p>Decodes a QR Code represented as a {@link BitMatrix}. A 1 or "true" is taken to mean a black module.</p>\r
+ *\r
+ * @param bits booleans representing white/black QR Code modules\r
+ * @return text encoded within the QR Code\r
+ * @throws ReaderException if the QR Code cannot be decoded\r
+ */\r
public static String decode(BitMatrix bits) throws ReaderException {\r
+\r
+ // Construct a parser and read version, error-correction level\r
BitMatrixParser parser = new BitMatrixParser(bits);\r
Version version = parser.readVersion();\r
ErrorCorrectionLevel ecLevel = parser.readFormatInformation().getErrorCorrectionLevel();\r
+\r
+ // Read codewords\r
byte[] codewords = parser.readCodewords();\r
+ // Separate into data blocks\r
DataBlock[] dataBlocks = DataBlock.getDataBlocks(codewords, version, ecLevel);\r
+\r
+ // Count total number of data bytes\r
int totalBytes = 0;\r
for (int i = 0; i < dataBlocks.length; i++) {\r
totalBytes += dataBlocks[i].getNumDataCodewords();\r
}\r
byte[] resultBytes = new byte[totalBytes];\r
int resultOffset = 0;\r
+\r
+ // Error-correct and copy data blocks together into a stream of bytes\r
for (int j = 0; j < dataBlocks.length; j++) {\r
DataBlock dataBlock = dataBlocks[j];\r
byte[] codewordBytes = dataBlock.getCodewords();\r
}\r
}\r
\r
+ // Decode the contents of that stream of bytes\r
return DecodedBitStreamParser.decode(resultBytes, version);\r
}\r
\r
- private static void correctErrors(byte[] codewordBytes, int numDataCodewords)\r
- throws ReaderException {\r
+ /**\r
+ * <p>Given data and error-correction codewords received, possibly corrupted by errors, attempts to\r
+ * correct the errors in-place using Reed-Solomon error correction.</p>\r
+ *\r
+ * @param codewordBytes data and error correction codewords\r
+ * @param numDataCodewords number of codewords that are data bytes\r
+ * @throws ReaderException if error correction fails\r
+ */\r
+ private static void correctErrors(byte[] codewordBytes, int numDataCodewords) throws ReaderException {\r
int numCodewords = codewordBytes.length;\r
+ // First read into an array of ints\r
int[] codewordsInts = new int[numCodewords];\r
for (int i = 0; i < numCodewords; i++) {\r
codewordsInts[i] = codewordBytes[i] & 0xFF;\r
} catch (ReedSolomonException rse) {\r
throw new ReaderException(rse.toString());\r
}\r
+ // Copy back into array of bytes -- only need to worry about the bytes that were data\r
+ // We don't care about errors in the error-correction codewords\r
for (int i = 0; i < numDataCodewords; i++) {\r
codewordBytes[i] = (byte) codewordsInts[i];\r
}\r
private final int ordinal;
- private ErrorCorrectionLevel(final int ordinal) {
+ private ErrorCorrectionLevel(int ordinal) {
this.ordinal = ordinal;
}
return ordinal;
}
+ /**
+ * @param bits int containing the two bits encoding a QR Code's error correction level
+ * @return {@link ErrorCorrectionLevel} representing the encoded error correction level
+ */
static ErrorCorrectionLevel forBits(int bits) {
return FOR_BITS[bits];
}
package com.google.zxing.qrcode.decoder;
/**
+ * <p>Encapsulates a QR Code's format information, including the data mask used and
+ * error correction level.</p>
+ *
* @author srowen@google.com (Sean Owen)
+ * @see DataMask
+ * @see ErrorCorrectionLevel
*/
final class FormatInformation {
{0x2BED, 0x1F},
};
+ /** Offset i holds the number of 1 bits in the binary representation of i */
private static final int[] BITS_SET_IN_HALF_BYTE =
new int[]{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
private FormatInformation(int formatInfo) {
// Bits 3,4
- errorCorrectionLevel =
- ErrorCorrectionLevel.forBits((formatInfo >> 3) & 0x03);
+ errorCorrectionLevel = ErrorCorrectionLevel.forBits((formatInfo >> 3) & 0x03);
// Bottom 3 bits
dataMask = (byte) (formatInfo & 0x07);
}
static int numBitsDiffering(int a, int b) {
- a ^= b;
- return
- BITS_SET_IN_HALF_BYTE[a & 0x0F] +
+ a ^= b; // a now has a 1 bit exactly where its bit differs with b's
+ // Count bits set quickly with a series of lookups:
+ return BITS_SET_IN_HALF_BYTE[a & 0x0F] +
BITS_SET_IN_HALF_BYTE[(a >>> 4 & 0x0F)] +
BITS_SET_IN_HALF_BYTE[(a >>> 8 & 0x0F)] +
BITS_SET_IN_HALF_BYTE[(a >>> 12 & 0x0F)] +
BITS_SET_IN_HALF_BYTE[(a >>> 28 & 0x0F)];
}
+ /**
+ *
+ * @param rawFormatInfo
+ * @return
+ */
static FormatInformation decodeFormatInformation(int rawFormatInfo) {
FormatInformation formatInfo = doDecodeFormatInformation(rawFormatInfo);
if (formatInfo != null) {
return doDecodeFormatInformation(rawFormatInfo ^ FORMAT_INFO_MASK_QR);
}
- private static FormatInformation doDecodeFormatInformation(
- int rawFormatInfo) {
+ private static FormatInformation doDecodeFormatInformation(int rawFormatInfo) {
// Unmask:
int unmaskedFormatInfo = rawFormatInfo ^ FORMAT_INFO_MASK_QR;
+ // Find the int in FORMAT_INFO_DECODE_LOOKUP with fewest bits differing
int bestDifference = Integer.MAX_VALUE;
int bestFormatInfo = 0;
for (int i = 0; i < FORMAT_INFO_DECODE_LOOKUP.length; i++) {
int[] decodeInfo = FORMAT_INFO_DECODE_LOOKUP[i];
int targetInfo = decodeInfo[0];
if (targetInfo == unmaskedFormatInfo) {
+ // Found an exact match
return new FormatInformation(decodeInfo[1]);
}
int bitsDifference = numBitsDiffering(unmaskedFormatInfo, targetInfo);
this.characterCountBitsForVersions = characterCountBitsForVersions;
}
+ /**
+ * @param bits four bits encoding a QR Code data mode
+ * @return {@link Mode} encoded by these bits
+ * @throws ReaderException if bits do not correspond to a known mode
+ */
static Mode forBits(int bits) throws ReaderException {
switch (bits) {
case 0x0:
}
}
+ /**
+ * @param version version in question
+ * @return number of bits used, in this QR Code symbol {@link Version}, to encode the
+ * count of characters that will follow encoded in this {@link Mode}
+ */
int getCharacterCountBits(Version version) {
int number = version.getVersionNumber();
int offset;
return ecBlocks[ecLevel.ordinal()];\r
}\r
\r
- public static Version getProvisionalVersionForDimension(int dimension)\r
- throws ReaderException {\r
+ /**\r
+ * <p>Deduces version information purely from QR Code dimensions.</p>\r
+ *\r
+ * @param dimension dimension in modules\r
+ * @return {@link Version} for a QR Code of that dimension\r
+ * @throws ReaderException if dimension is not 1 mod 4\r
+ */\r
+ public static Version getProvisionalVersionForDimension(int dimension) throws ReaderException {\r
if (dimension % 4 != 1) {\r
throw new ReaderException("Dimension must be 1 mod 4");\r
}\r
return getVersionForNumber((dimension - 17) >> 2);\r
}\r
\r
- public static Version getVersionForNumber(int versionNumber)\r
- throws ReaderException {\r
+ public static Version getVersionForNumber(int versionNumber) throws ReaderException {\r
if (versionNumber < 1 || versionNumber > 40) {\r
- throw new ReaderException(\r
- "versionNumber must be between 1 and 40");\r
+ throw new ReaderException("versionNumber must be between 1 and 40");\r
}\r
return VERSIONS[versionNumber - 1];\r
}\r
\r
- static Version decodeVersionInformation(int versionBits)\r
- throws ReaderException {\r
+ static Version decodeVersionInformation(int versionBits) throws ReaderException {\r
int bestDifference = Integer.MAX_VALUE;\r
int bestVersion = 0;\r
for (int i = 0; i < VERSION_DECODE_INFO.length; i++) {\r
int targetVersion = VERSION_DECODE_INFO[i];\r
+ // Do the version info bits match exactly? done.\r
if (targetVersion == versionBits) {\r
return getVersionForNumber(i + 7);\r
}\r
- int bitsDifference =\r
- FormatInformation.numBitsDiffering(versionBits, targetVersion);\r
+ // Otherwise see if this is the closest to a real version info bit string\r
+ // we have seen so far\r
+ int bitsDifference = FormatInformation.numBitsDiffering(versionBits, targetVersion);\r
if (bitsDifference < bestDifference) {\r
bestVersion = i + 7;\r
}\r
}\r
+ // We can tolerate up to 3 bits of error since no two version info codewords will\r
+ // differ in less than 4 bits.\r
if (bestDifference <= 3) {\r
return getVersionForNumber(bestVersion);\r
}\r
+ // If we didn't find a close enough match, fail\r
return null;\r
}\r
\r
projects / zxing.git / commitdiff