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.
* - * @author srowen@google.com (Sean Owen) + *See ISO 18004:2006, 6.4.3 - 6.4.7
+ * + * @author Sean Owen */ final class DecodedBitStreamParser { /** * See ISO 18004:2006, 6.4.4 Table 5 */ - private static final char[] ALPHANUMERIC_CHARS = new char[]{ + private static final char[] ALPHANUMERIC_CHARS = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', ' ', '$', '%', '*', '+', '-', '.', '/', ':' }; - private static final String SHIFT_JIS = "Shift_JIS"; + private static final String SHIFT_JIS = "SJIS"; + private static final String EUC_JP = "EUC_JP"; private static final boolean ASSUME_SHIFT_JIS; + private static final String UTF8 = "UTF8"; + private static final String ISO88591 = "ISO8859_1"; static { String platformDefault = System.getProperty("file.encoding"); - ASSUME_SHIFT_JIS = SHIFT_JIS.equalsIgnoreCase(platformDefault) || - "EUC-JP".equalsIgnoreCase(platformDefault); + ASSUME_SHIFT_JIS = SHIFT_JIS.equalsIgnoreCase(platformDefault) || EUC_JP.equalsIgnoreCase(platformDefault); } private DecodedBitStreamParser() { } - static String decode(byte[] bytes, Version version) throws ReaderException { + static DecoderResult decode(byte[] bytes, Version version, ErrorCorrectionLevel ecLevel) throws ReaderException { BitSource bits = new BitSource(bytes); StringBuffer result = new StringBuffer(); + CharacterSetECI currentCharacterSetECI = null; + boolean fc1InEffect = false; + Vector byteSegments = new Vector(1); Mode mode; do { // While still another segment to read... - mode = Mode.forBits(bits.readBits(4)); + if (bits.available() < 4) { + // OK, assume we're done. Really, a TERMINATOR mode should have been recorded here + mode = Mode.TERMINATOR; + } else { + try { + mode = Mode.forBits(bits.readBits(4)); // mode is encoded by 4 bits + } catch (IllegalArgumentException iae) { + throw ReaderException.getInstance(); + } + } if (!mode.equals(Mode.TERMINATOR)) { - int count = bits.readBits(mode.getCharacterCountBits(version)); - if (mode.equals(Mode.NUMERIC)) { - decodeNumericSegment(bits, result, count); - } else if (mode.equals(Mode.ALPHANUMERIC)) { - decodeAlphanumericSegment(bits, result, count); - } else if (mode.equals(Mode.BYTE)) { - decodeByteSegment(bits, result, count); - } else if (mode.equals(Mode.KANJI)) { - decodeKanjiSegment(bits, result, count); + if (mode.equals(Mode.FNC1_FIRST_POSITION) || mode.equals(Mode.FNC1_SECOND_POSITION)) { + // We do little with FNC1 except alter the parsed result a bit according to the spec + fc1InEffect = true; + } else if (mode.equals(Mode.STRUCTURED_APPEND)) { + // not really supported; all we do is ignore it + // Read next 8 bits (symbol sequence #) and 8 bits (parity data), then continue + bits.readBits(16); + } else if (mode.equals(Mode.ECI)) { + // Count doesn't apply to ECI + int value = parseECIValue(bits); + currentCharacterSetECI = CharacterSetECI.getCharacterSetECIByValue(value); + if (currentCharacterSetECI == null) { + throw ReaderException.getInstance(); + } } else { - throw new ReaderException("Unsupported mode indicator: " + mode); + // 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.ALPHANUMERIC)) { + decodeAlphanumericSegment(bits, result, count, fc1InEffect); + } else if (mode.equals(Mode.BYTE)) { + decodeByteSegment(bits, result, count, currentCharacterSetECI, byteSegments); + } else if (mode.equals(Mode.KANJI)) { + decodeKanjiSegment(bits, result, count); + } else { + throw ReaderException.getInstance(); + } } } } while (!mode.equals(Mode.TERMINATOR)); - /* - int bitsLeft = bits.available(); - if (bitsLeft > 0) { - if (bitsLeft > 6 || bits.readBits(bitsLeft) != 0) { - throw new ReaderException("Excess bits or non-zero bits after terminator mode indicator"); - } - } - */ - return result.toString(); + return new DecoderResult(bytes, result.toString(), byteSegments.isEmpty() ? null : byteSegments, ecLevel); } 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) { @@ -104,39 +137,49 @@ final class DecodedBitStreamParser { } // Shift_JIS may not be supported in some environments: try { - result.append(new String(buffer, "Shift_JIS")); + result.append(new String(buffer, SHIFT_JIS)); } catch (UnsupportedEncodingException uee) { - throw new ReaderException("Can't decode SHIFT_JIS string: " + uee); + throw ReaderException.getInstance(); } } private static void decodeByteSegment(BitSource bits, StringBuffer result, - int count) throws ReaderException { + int count, + CharacterSetECI currentCharacterSetECI, + Vector byteSegments) throws ReaderException { byte[] readBytes = new byte[count]; if (count << 3 > bits.available()) { - throw new ReaderException("Count too large: " + count); + throw ReaderException.getInstance(); } for (int i = 0; i < count; i++) { readBytes[i] = (byte) bits.readBits(8); } + String encoding; + if (currentCharacterSetECI == null) { // The spec isn't clear on this mode; see // section 6.4.5: t does not say which encoding to assuming // upon decoding. I have seen ISO-8859-1 used as well as // Shift_JIS -- without anything like an ECI designator to // give a hint. - String encoding = guessEncoding(readBytes); + encoding = guessEncoding(readBytes); + } else { + encoding = currentCharacterSetECI.getEncodingName(); + } try { result.append(new String(readBytes, encoding)); } catch (UnsupportedEncodingException uce) { - throw new ReaderException(uce.toString()); + throw ReaderException.getInstance(); } + byteSegments.addElement(readBytes); } private static void decodeAlphanumericSegment(BitSource bits, StringBuffer result, - int count) { + int count, + boolean fc1InEffect) { // Read two characters at a time + int start = result.length(); while (count > 1) { int nextTwoCharsBits = bits.readBits(11); result.append(ALPHANUMERIC_CHARS[nextTwoCharsBits / 45]); @@ -144,18 +187,35 @@ final class DecodedBitStreamParser { count -= 2; } if (count == 1) { - // special case on char left + // special case: one character left result.append(ALPHANUMERIC_CHARS[bits.readBits(6)]); } + // See section 6.4.8.1, 6.4.8.2 + if (fc1InEffect) { + // We need to massage the result a bit if in an FNC1 mode: + for (int i = start; i < result.length(); i++) { + if (result.charAt(i) == '%') { + if (i < result.length() - 1 && result.charAt(i + 1) == '%') { + // %% is rendered as % + result.deleteCharAt(i + 1); + } else { + // In alpha mode, % should be converted to FNC1 separator 0x1D + result.setCharAt(i, (char) 0x1D); + } + } + } + } } 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); + throw ReaderException.getInstance(); } result.append(ALPHANUMERIC_CHARS[threeDigitsBits / 100]); result.append(ALPHANUMERIC_CHARS[(threeDigitsBits / 10) % 10]); @@ -163,16 +223,18 @@ final class DecodedBitStreamParser { 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); + throw ReaderException.getInstance(); } 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); + throw ReaderException.getInstance(); } result.append(ALPHANUMERIC_CHARS[digitBits]); } @@ -182,32 +244,108 @@ final class DecodedBitStreamParser { if (ASSUME_SHIFT_JIS) { return SHIFT_JIS; } - // For now, merely tries to distinguish ISO-8859-1 and Shift_JIS, + // 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; - for (int i = 0; i < length; i++) { + boolean canBeISO88591 = true; + boolean canBeShiftJIS = true; + int maybeDoubleByteCount = 0; + int maybeSingleByteKatakanaCount = 0; + boolean sawLatin1Supplement = false; + boolean lastWasPossibleDoubleByteStart = false; + for (int i = 0; i < length && (canBeISO88591 || canBeShiftJIS); i++) { int value = bytes[i] & 0xFF; - if (value >= 0x80 && value <= 0x9F && i < length - 1) { - // ISO-8859-1 shouldn't use this, but before we decide it is Shift_JIS, - // just double check that it is followed by a byte that's valid in - // the Shift_JIS encoding + 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 ((value & 0x1) == 0) { - // if even, - if (nextValue >= 0x40 && nextValue <= 0x9E) { - return SHIFT_JIS; - } + if (nextValue <= 0xBF && ((value == 0xC2 && nextValue >= 0xA0) || (value == 0xC3 && nextValue >= 0x80))) { + sawLatin1Supplement = true; + } + } + if (value >= 0x7F && value <= 0x9F) { + canBeISO88591 = false; + } + 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 { - if (nextValue >= 0x9F && nextValue <= 0x7C) { - return SHIFT_JIS; + // ... 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; } } - return "ISO-8859-1"; + // Distinguishing Shift_JIS and ISO-8859-1 can be a little tough. The crude heuristic is: + // - If we saw + // - at least three byte that starts a double-byte value (bytes that are rare in ISO-8859-1), or + // - over 5% of bytes that 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 UTF-8 + return UTF8; + } + + private static int parseECIValue(BitSource bits) { + int firstByte = bits.readBits(8); + if ((firstByte & 0x80) == 0) { + // just one byte + return firstByte & 0x7F; + } else if ((firstByte & 0xC0) == 0x80) { + // two bytes + int secondByte = bits.readBits(8); + return ((firstByte & 0x3F) << 8) | secondByte; + } else if ((firstByte & 0xE0) == 0xC0) { + // three bytes + int secondThirdBytes = bits.readBits(16); + return ((firstByte & 0x1F) << 16) | secondThirdBytes; + } + throw new IllegalArgumentException("Bad ECI bits starting with byte " + firstByte); } }