core/src/com/google/zxing/qrcode/encoder/Encoder.java

   1 /*
   2  * Copyright 2008 ZXing authors
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.google.zxing.qrcode.encoder;
  18
  19 import com.google.zxing.common.ByteMatrix;
  20 import com.google.zxing.common.ByteArray;
  21 import com.google.zxing.common.reedsolomon.GF256;
  22 import com.google.zxing.common.reedsolomon.ReedSolomonEncoder;
  23 import com.google.zxing.WriterException;
  24 import com.google.zxing.qrcode.decoder.ErrorCorrectionLevel;
  25
  26 import java.util.Vector;
  27
  28 /**
  29  * @author satorux@google.com (Satoru Takabayashi) - creator
  30  * @author dswitkin@google.com (Daniel Switkin) - ported from C++
  31  */
  32 public final class Encoder {
  33
  34   // The original table is defined in the table 5 of JISX0510:2004 (p.19).
  35   private static final int[] ALPHANUMERIC_TABLE = {
  36       -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  // 0x00-0x0f
  37       -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  // 0x10-0x1f
  38       36, -1, -1, -1, 37, 38, -1, -1, -1, -1, 39, 40, -1, 41, 42, 43,  // 0x20-0x2f
  39       0,   1,  2,  3,  4,  5,  6,  7,  8,  9, 44, -1, -1, -1, -1, -1,  // 0x30-0x3f
  40       -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,  // 0x40-0x4f
  41       25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,  // 0x50-0x5f
  42   };
  43
  44   private static final class RSBlockInfo {
  45
  46     final int numBytes;
  47     final int[][] blockInfo;
  48
  49     public RSBlockInfo(int numBytes, int[][] blockInfo) {
  50       this.numBytes = numBytes;
  51       this.blockInfo = blockInfo;
  52     }
  53
  54   }
  55
  56   // The table is from table 12 of JISX0510:2004 (p. 30). The "blockInfo" parts are ordered by
  57   // L, M, Q, H. Within each blockInfo, the 0th element is getNumECBytes, and the 1st element is
  58   // getNumRSBlocks. The table was doublechecked by komatsu.
  59   private static final RSBlockInfo[] RS_BLOCK_TABLE = {
  60       new RSBlockInfo(  26, new int[][]{ {  7,  1}, {  10,  1}, {  13,  1}, {  17,  1}}),  // Version  1
  61       new RSBlockInfo(  44, new int[][]{ { 10,  1}, {  16,  1}, {  22,  1}, {  28,  1}}),  // Version  2
  62       new RSBlockInfo(  70, new int[][]{ { 15,  1}, {  26,  1}, {  36,  2}, {  44,  2}}),  // Version  3
  63       new RSBlockInfo( 100, new int[][]{ { 20,  1}, {  36,  2}, {  52,  2}, {  64,  4}}),  // Version  4
  64       new RSBlockInfo( 134, new int[][]{ { 26,  1}, {  48,  2}, {  72,  4}, {  88,  4}}),  // Version  5
  65       new RSBlockInfo( 172, new int[][]{ { 36,  2}, {  64,  4}, {  96,  4}, { 112,  4}}),  // Version  6
  66       new RSBlockInfo( 196, new int[][]{ { 40,  2}, {  72,  4}, { 108,  6}, { 130,  5}}),  // Version  7
  67       new RSBlockInfo( 242, new int[][]{ { 48,  2}, {  88,  4}, { 132,  6}, { 156,  6}}),  // Version  8
  68       new RSBlockInfo( 292, new int[][]{ { 60,  2}, { 110,  5}, { 160,  8}, { 192,  8}}),  // Version  9
  69       new RSBlockInfo( 346, new int[][]{ { 72,  4}, { 130,  5}, { 192,  8}, { 224,  8}}),  // Version 10
  70       new RSBlockInfo( 404, new int[][]{ { 80,  4}, { 150,  5}, { 224,  8}, { 264, 11}}),  // Version 11
  71       new RSBlockInfo( 466, new int[][]{ { 96,  4}, { 176,  8}, { 260, 10}, { 308, 11}}),  // Version 12
  72       new RSBlockInfo( 532, new int[][]{ {104,  4}, { 198,  9}, { 288, 12}, { 352, 16}}),  // Version 13
  73       new RSBlockInfo( 581, new int[][]{ {120,  4}, { 216,  9}, { 320, 16}, { 384, 16}}),  // Version 14
  74       new RSBlockInfo( 655, new int[][]{ {132,  6}, { 240, 10}, { 360, 12}, { 432, 18}}),  // Version 15
  75       new RSBlockInfo( 733, new int[][]{ {144,  6}, { 280, 10}, { 408, 17}, { 480, 16}}),  // Version 16
  76       new RSBlockInfo( 815, new int[][]{ {168,  6}, { 308, 11}, { 448, 16}, { 532, 19}}),  // Version 17
  77       new RSBlockInfo( 901, new int[][]{ {180,  6}, { 338, 13}, { 504, 18}, { 588, 21}}),  // Version 18
  78       new RSBlockInfo( 991, new int[][]{ {196,  7}, { 364, 14}, { 546, 21}, { 650, 25}}),  // Version 19
  79       new RSBlockInfo(1085, new int[][]{ {224,  8}, { 416, 16}, { 600, 20}, { 700, 25}}),  // Version 20
  80       new RSBlockInfo(1156, new int[][]{ {224,  8}, { 442, 17}, { 644, 23}, { 750, 25}}),  // Version 21
  81       new RSBlockInfo(1258, new int[][]{ {252,  9}, { 476, 17}, { 690, 23}, { 816, 34}}),  // Version 22
  82       new RSBlockInfo(1364, new int[][]{ {270,  9}, { 504, 18}, { 750, 25}, { 900, 30}}),  // Version 23
  83       new RSBlockInfo(1474, new int[][]{ {300, 10}, { 560, 20}, { 810, 27}, { 960, 32}}),  // Version 24
  84       new RSBlockInfo(1588, new int[][]{ {312, 12}, { 588, 21}, { 870, 29}, {1050, 35}}),  // Version 25
  85       new RSBlockInfo(1706, new int[][]{ {336, 12}, { 644, 23}, { 952, 34}, {1110, 37}}),  // Version 26
  86       new RSBlockInfo(1828, new int[][]{ {360, 12}, { 700, 25}, {1020, 34}, {1200, 40}}),  // Version 27
  87       new RSBlockInfo(1921, new int[][]{ {390, 13}, { 728, 26}, {1050, 35}, {1260, 42}}),  // Version 28
  88       new RSBlockInfo(2051, new int[][]{ {420, 14}, { 784, 28}, {1140, 38}, {1350, 45}}),  // Version 29
  89       new RSBlockInfo(2185, new int[][]{ {450, 15}, { 812, 29}, {1200, 40}, {1440, 48}}),  // Version 30
  90       new RSBlockInfo(2323, new int[][]{ {480, 16}, { 868, 31}, {1290, 43}, {1530, 51}}),  // Version 31
  91       new RSBlockInfo(2465, new int[][]{ {510, 17}, { 924, 33}, {1350, 45}, {1620, 54}}),  // Version 32
  92       new RSBlockInfo(2611, new int[][]{ {540, 18}, { 980, 35}, {1440, 48}, {1710, 57}}),  // Version 33
  93       new RSBlockInfo(2761, new int[][]{ {570, 19}, {1036, 37}, {1530, 51}, {1800, 60}}),  // Version 34
  94       new RSBlockInfo(2876, new int[][]{ {570, 19}, {1064, 38}, {1590, 53}, {1890, 63}}),  // Version 35
  95       new RSBlockInfo(3034, new int[][]{ {600, 20}, {1120, 40}, {1680, 56}, {1980, 66}}),  // Version 36
  96       new RSBlockInfo(3196, new int[][]{ {630, 21}, {1204, 43}, {1770, 59}, {2100, 70}}),  // Version 37
  97       new RSBlockInfo(3362, new int[][]{ {660, 22}, {1260, 45}, {1860, 62}, {2220, 74}}),  // Version 38
  98       new RSBlockInfo(3532, new int[][]{ {720, 24}, {1316, 47}, {1950, 65}, {2310, 77}}),  // Version 39
  99       new RSBlockInfo(3706, new int[][]{ {750, 25}, {1372, 49}, {2040, 68}, {2430, 81}}),  // Version 40
 100   };
 101
 102   private static final class BlockPair {
 103
 104     private final ByteArray dataBytes;
 105     private final ByteArray errorCorrectionBytes;
 106
 107     public BlockPair(ByteArray data, ByteArray errorCorrection) {
 108       dataBytes = data;
 109       errorCorrectionBytes = errorCorrection;
 110     }
 111
 112     public ByteArray getDataBytes() {
 113       return dataBytes;
 114     }
 115
 116     public ByteArray getErrorCorrectionBytes() {
 117       return errorCorrectionBytes;
 118     }
 119
 120   }
 121
 122   // Encode "bytes" with the error correction level "getECLevel". The encoding mode will be chosen
 123   // internally by chooseMode(). On success, store the result in "qrCode" and return true.
 124   // We recommend you to use QRCode.EC_LEVEL_L (the lowest level) for
 125   // "getECLevel" since our primary use is to show QR code on desktop screens. We don't need very
 126   // strong error correction for this purpose.
 127   //
 128   // Note that there is no way to encode bytes in MODE_KANJI. We might want to add EncodeWithMode()
 129   // with which clients can specify the encoding mode. For now, we don't need the functionality.
 130   public static void encode(final ByteArray bytes, ErrorCorrectionLevel ecLevel, QRCode qrCode)
 131       throws WriterException {
 132     // Step 1: Choose the mode (encoding).
 133     final int mode = chooseMode(bytes);
 134
 135     // Step 2: Append "bytes" into "dataBits" in appropriate encoding.
 136     BitVector dataBits = new BitVector();
 137     appendBytes(bytes, mode, dataBits);
 138     // Step 3: Initialize QR code that can contain "dataBits".
 139     final int numInputBytes = dataBits.sizeInBytes();
 140     initQRCode(numInputBytes, ecLevel, mode, qrCode);
 141
 142     // Step 4: Build another bit vector that contains header and data.
 143     BitVector headerAndDataBits = new BitVector();
 144     appendModeInfo(qrCode.getMode(), headerAndDataBits);
 145     appendLengthInfo(bytes.size(), qrCode.getVersion(), qrCode.getMode(), headerAndDataBits);
 146     headerAndDataBits.appendBitVector(dataBits);
 147
 148     // Step 5: Terminate the bits properly.
 149     terminateBits(qrCode.getNumDataBytes(), headerAndDataBits);
 150
 151     // Step 6: Interleave data bits with error correction code.
 152     BitVector finalBits = new BitVector();
 153     interleaveWithECBytes(headerAndDataBits, qrCode.getNumTotalBytes(), qrCode.getNumDataBytes(),
 154         qrCode.getNumRSBlocks(), finalBits);
 155
 156     // Step 7: Choose the mask pattern and set to "qrCode".
 157     ByteMatrix matrix = new ByteMatrix(qrCode.getMatrixWidth(), qrCode.getMatrixWidth());
 158     qrCode.setMaskPattern(chooseMaskPattern(finalBits, qrCode.getECLevel(), qrCode.getVersion(),
 159         matrix));
 160
 161     // Step 8.  Build the matrix and set it to "qrCode".
 162     MatrixUtil.buildMatrix(finalBits, qrCode.getECLevel(), qrCode.getVersion(),
 163         qrCode.getMaskPattern(), matrix);
 164     qrCode.setMatrix(matrix);
 165     // Step 9.  Make sure we have a valid QR Code.
 166     if (!qrCode.isValid()) {
 167       throw new WriterException("Invalid QR code: " + qrCode.toString());
 168     }
 169   }
 170
 171   // Return the code point of the table used in alphanumeric mode. Return -1 if there is no
 172   // corresponding code in the table.
 173   static int getAlphanumericCode(int code) {
 174     if (code < ALPHANUMERIC_TABLE.length) {
 175       return ALPHANUMERIC_TABLE[code];
 176     }
 177     return -1;
 178   }
 179
 180   // Choose the best mode by examining the content of "bytes". The function is guaranteed to return
 181   // a valid mode.
 182   //
 183   // Note that this function does not return MODE_KANJI, as we cannot distinguish Shift_JIS from
 184   // other encodings such as ISO-8859-1, from data bytes alone. For example "\xE0\xE0" can be
 185   // interpreted as one character in Shift_JIS, but also two characters in ISO-8859-1.
 186   //
 187   // JAVAPORT: This MODE_KANJI limitation sounds like a problem for us.
 188   public static int chooseMode(final ByteArray bytes) throws WriterException {
 189     boolean hasNumeric = false;
 190     boolean hasAlphanumeric = false;
 191     boolean hasOther = false;
 192     for (int i = 0; i < bytes.size(); ++i) {
 193       final int oneByte = bytes.at(i);
 194       if (oneByte >= '0' && oneByte <= '9') {
 195         hasNumeric = true;
 196       } else if (getAlphanumericCode(oneByte) != -1) {
 197         hasAlphanumeric = true;
 198       } else {
 199         hasOther = true;
 200       }
 201     }
 202     if (hasOther) {
 203       return QRCode.MODE_8BIT_BYTE;
 204     } else if (hasAlphanumeric) {
 205       return QRCode.MODE_ALPHANUMERIC;
 206     } else if (hasNumeric) {
 207       return QRCode.MODE_NUMERIC;
 208     }
 209     // "bytes" must be empty to reach here.
 210     if (!bytes.empty()) {
 211       throw new WriterException("Bytes left over");
 212     }
 213     return QRCode.MODE_8BIT_BYTE;
 214   }
 215
 216   private static int chooseMaskPattern(final BitVector bits, ErrorCorrectionLevel ecLevel, int version,
 217       ByteMatrix matrix) throws WriterException {
 218     if (!QRCode.isValidMatrixWidth(matrix.width())) {
 219       throw new WriterException("Invalid matrix width: " + matrix.width());
 220     }
 221
 222     int minPenalty = Integer.MAX_VALUE;  // Lower penalty is better.
 223     int bestMaskPattern = -1;
 224     // We try all mask patterns to choose the best one.
 225     for (int maskPattern = 0; maskPattern < QRCode.NUM_MASK_PATTERNS; maskPattern++) {
 226       MatrixUtil.buildMatrix(bits, ecLevel, version, maskPattern, matrix);
 227       final int penalty = MaskUtil.calculateMaskPenalty(matrix);
 228       if (penalty < minPenalty) {
 229         minPenalty = penalty;
 230         bestMaskPattern = maskPattern;
 231       }
 232     }
 233     return bestMaskPattern;
 234   }
 235
 236   // Initialize "qrCode" according to "numInputBytes", "ecLevel", and "mode". On success, modify
 237   // "qrCode" and return true.
 238   private static void initQRCode(int numInputBytes, ErrorCorrectionLevel ecLevel, int mode, QRCode qrCode)
 239       throws WriterException {
 240     qrCode.setECLevel(ecLevel);
 241     qrCode.setMode(mode);
 242
 243     // In the following comments, we use numbers of Version 7-H.
 244     for (int i = 0; i < RS_BLOCK_TABLE.length; ++i) {
 245       final RSBlockInfo row = RS_BLOCK_TABLE[i];
 246       // numBytes = 196
 247       final int numBytes = row.numBytes;
 248       // getNumECBytes = 130
 249       final int numEcBytes  = row.blockInfo[ecLevel.ordinal()][0];
 250       // getNumRSBlocks = 5
 251       final int numRSBlocks = row.blockInfo[ecLevel.ordinal()][1];
 252       // getNumDataBytes = 196 - 130 = 66
 253       final int numDataBytes = numBytes - numEcBytes;
 254       // We want to choose the smallest version which can contain data of "numInputBytes" + some
 255       // extra bits for the header (mode info and length info). The header can be three bytes
 256       // (precisely 4 + 16 bits) at most. Hence we do +3 here.
 257       if (numDataBytes >= numInputBytes + 3) {
 258         // Yay, we found the proper rs block info!
 259         qrCode.setVersion(i + 1);
 260         qrCode.setNumTotalBytes(numBytes);
 261         qrCode.setNumDataBytes(numDataBytes);
 262         qrCode.setNumRSBlocks(numRSBlocks);
 263         // getNumECBytes = 196 - 66 = 130
 264         qrCode.setNumECBytes(numBytes - numDataBytes);
 265         // matrix width = 21 + 6 * 4 = 45
 266         qrCode.setMatrixWidth(21 + i * 4);
 267         return;
 268       }
 269     }
 270     throw new WriterException("Cannot find proper rs block info (input data too big?)");
 271   }
 272
 273   // Terminate bits as described in 8.4.8 and 8.4.9 of JISX0510:2004 (p.24).
 274   static void terminateBits(int numDataBytes, BitVector bits) throws WriterException {
 275     final int capacity = numDataBytes * 8;
 276     if (bits.size() > capacity) {
 277       throw new WriterException("data bits cannot fit in the QR Code" + bits.size() + " > " + capacity);
 278     }
 279     // Append termination bits. See 8.4.8 of JISX0510:2004 (p.24) for details.
 280     for (int i = 0; i < 4 && bits.size() < capacity; ++i) {
 281       bits.appendBit(0);
 282     }
 283     final int numBitsInLastByte = bits.size() % 8;
 284     // If the last byte isn't 8-bit aligned, we'll add padding bits.
 285     if (numBitsInLastByte > 0) {
 286       final int numPaddingBits = 8 - numBitsInLastByte;
 287       for (int i = 0; i < numPaddingBits; ++i) {
 288         bits.appendBit(0);
 289       }
 290     }
 291     // Should be 8-bit aligned here.
 292     if (bits.size() % 8 != 0) {
 293       throw new WriterException("Number of bits is not a multiple of 8");
 294     }
 295     // If we have more space, we'll fill the space with padding patterns defined in 8.4.9 (p.24).
 296     final int numPaddingBytes = numDataBytes - bits.sizeInBytes();
 297     for (int i = 0; i < numPaddingBytes; ++i) {
 298       if (i % 2 == 0) {
 299         bits.appendBits(0xec, 8);
 300       } else {
 301         bits.appendBits(0x11, 8);
 302       }
 303     }
 304     if (bits.size() != capacity) {
 305       throw new WriterException("Bits size does not equal capacity");
 306     }
 307   }
 308
 309   // Get number of data bytes and number of error correction bytes for block id "blockID". Store
 310   // the result in "numDataBytesInBlock", and "numECBytesInBlock". See table 12 in 8.5.1 of
 311   // JISX0510:2004 (p.30)
 312   static void getNumDataBytesAndNumECBytesForBlockID(int numTotalBytes, int numDataBytes,
 313       int numRSBlocks, int blockID, int[] numDataBytesInBlock,
 314       int[] numECBytesInBlock) throws WriterException {
 315     if (blockID >= numRSBlocks) {
 316       throw new WriterException("Block ID too large");
 317     }
 318     // numRsBlocksInGroup2 = 196 % 5 = 1
 319     final int numRsBlocksInGroup2 = numTotalBytes % numRSBlocks;
 320     // numRsBlocksInGroup1 = 5 - 1 = 4
 321     final int numRsBlocksInGroup1 = numRSBlocks - numRsBlocksInGroup2;
 322     // numTotalBytesInGroup1 = 196 / 5 = 39
 323     final int numTotalBytesInGroup1 = numTotalBytes / numRSBlocks;
 324     // numTotalBytesInGroup2 = 39 + 1 = 40
 325     final int numTotalBytesInGroup2 = numTotalBytesInGroup1 + 1;
 326     // numDataBytesInGroup1 = 66 / 5 = 13
 327     final int numDataBytesInGroup1 = numDataBytes / numRSBlocks;
 328     // numDataBytesInGroup2 = 13 + 1 = 14
 329     final int numDataBytesInGroup2 = numDataBytesInGroup1 + 1;
 330     // numEcBytesInGroup1 = 39 - 13 = 26
 331     final int numEcBytesInGroup1 = numTotalBytesInGroup1 - numDataBytesInGroup1;
 332     // numEcBytesInGroup2 = 40 - 14 = 26
 333     final int numEcBytesInGroup2 = numTotalBytesInGroup2 - numDataBytesInGroup2;
 334     // Sanity checks.
 335     // 26 = 26
 336     if (numEcBytesInGroup1 != numEcBytesInGroup2) {
 337       throw new WriterException("EC bytes mismatch");
 338     }
 339     // 5 = 4 + 1.
 340     if (numRSBlocks != numRsBlocksInGroup1 + numRsBlocksInGroup2) {
 341       throw new WriterException("RS blocks mismatch");
 342     }
 343     // 196 = (13 + 26) * 4 + (14 + 26) * 1
 344     if (numTotalBytes !=
 345         ((numDataBytesInGroup1 + numEcBytesInGroup1) *
 346             numRsBlocksInGroup1) +
 347             ((numDataBytesInGroup2 + numEcBytesInGroup2) *
 348                 numRsBlocksInGroup2)) {
 349       throw new WriterException("Total bytes mismatch");
 350     }
 351
 352     if (blockID < numRsBlocksInGroup1) {
 353       numDataBytesInBlock[0] = numDataBytesInGroup1;
 354       numECBytesInBlock[0] = numEcBytesInGroup1;
 355     } else {
 356       numDataBytesInBlock[0] = numDataBytesInGroup2;
 357       numECBytesInBlock[0] = numEcBytesInGroup2;
 358     }
 359   }
 360
 361   // Interleave "bits" with corresponding error correction bytes. On success, store the result in
 362   // "result" and return true. The interleave rule is complicated. See 8.6
 363   // of JISX0510:2004 (p.37) for details.
 364   static void interleaveWithECBytes(final BitVector bits, int numTotalBytes,
 365       int numDataBytes, int numRSBlocks, BitVector result) throws WriterException {
 366
 367     // "bits" must have "getNumDataBytes" bytes of data.
 368     if (bits.sizeInBytes() != numDataBytes) {
 369       throw new WriterException("Number of bits and data bytes does not match");
 370     }
 371
 372     // Step 1.  Divide data bytes into blocks and generate error correction bytes for them. We'll
 373     // store the divided data bytes blocks and error correction bytes blocks into "blocks".
 374     int dataBytesOffset = 0;
 375     int maxNumDataBytes = 0;
 376     int maxNumEcBytes = 0;
 377
 378     // Since, we know the number of reedsolmon blocks, we can initialize the vector with the number.
 379     Vector blocks = new Vector(numRSBlocks);
 380
 381     for (int i = 0; i < numRSBlocks; ++i) {
 382       int[] numDataBytesInBlock = new int[1];
 383       int[] numEcBytesInBlock = new int[1];
 384       getNumDataBytesAndNumECBytesForBlockID(
 385           numTotalBytes, numDataBytes, numRSBlocks, i,
 386           numDataBytesInBlock, numEcBytesInBlock);
 387
 388       ByteArray dataBytes = new ByteArray();
 389       dataBytes.set(bits.getArray(), dataBytesOffset, numDataBytesInBlock[0]);
 390       ByteArray ecBytes = generateECBytes(dataBytes, numEcBytesInBlock[0]);
 391       blocks.addElement(new BlockPair(dataBytes, ecBytes));
 392
 393       maxNumDataBytes = Math.max(maxNumDataBytes, dataBytes.size());
 394       maxNumEcBytes = Math.max(maxNumEcBytes, ecBytes.size());
 395       dataBytesOffset += numDataBytesInBlock[0];
 396     }
 397     if (numDataBytes != dataBytesOffset) {
 398       throw new WriterException("Data bytes does not match offset");
 399     }
 400
 401     // First, place data blocks.
 402     for (int i = 0; i < maxNumDataBytes; ++i) {
 403       for (int j = 0; j < blocks.size(); ++j) {
 404         final ByteArray dataBytes = ((BlockPair) blocks.elementAt(j)).getDataBytes();
 405         if (i < dataBytes.size()) {
 406           result.appendBits(dataBytes.at(i), 8);
 407         }
 408       }
 409     }
 410     // Then, place error correction blocks.
 411     for (int i = 0; i < maxNumEcBytes; ++i) {
 412       for (int j = 0; j < blocks.size(); ++j) {
 413         final ByteArray ecBytes = ((BlockPair) blocks.elementAt(j)).getErrorCorrectionBytes();
 414         if (i < ecBytes.size()) {
 415           result.appendBits(ecBytes.at(i), 8);
 416         }
 417       }
 418     }
 419     if (numTotalBytes != result.sizeInBytes()) {  // Should be same.
 420       throw new WriterException("Interleaving error: " + numTotalBytes + " and " + result.sizeInBytes() +
 421         " differ.");
 422     }
 423   }
 424
 425   static ByteArray generateECBytes(ByteArray dataBytes, int numEcBytesInBlock) {
 426     int numDataBytes = dataBytes.size();
 427     int[] toEncode = new int[numDataBytes + numEcBytesInBlock];
 428     for (int i = 0; i < numDataBytes; i++) {
 429       toEncode[i] = dataBytes.at(i);
 430     }
 431     new ReedSolomonEncoder(GF256.QR_CODE_FIELD).encode(toEncode, numEcBytesInBlock);
 432
 433     ByteArray ecBytes = new ByteArray(numEcBytesInBlock);
 434     for (int i = 0; i < numEcBytesInBlock; i++) {
 435       ecBytes.set(i, toEncode[numDataBytes + i]);
 436     }
 437     return ecBytes;
 438   }
 439
 440   // Append mode info. On success, store the result in "bits" and return true. On error, return
 441   // false.
 442   static void appendModeInfo(int mode, BitVector bits) throws WriterException {
 443     final int code = QRCode.getModeCode(mode);
 444     bits.appendBits(code, 4);
 445   }
 446
 447
 448   // Append length info. On success, store the result in "bits" and return true. On error, return
 449   // false.
 450   static void appendLengthInfo(int numBytes, int version, int mode, BitVector bits) throws WriterException {
 451     int numLetters = numBytes;
 452     // In Kanji mode, a letter is represented in two bytes.
 453     if (mode == QRCode.MODE_KANJI) {
 454       if (numLetters % 2 != 0) {
 455         throw new WriterException("Number of letters must be even");
 456       }
 457       numLetters /= 2;
 458     }
 459
 460     final int numBits = QRCode.getNumBitsForLength(version, mode);
 461     if (numLetters > ((1 << numBits) - 1)) {
 462       throw new WriterException(numLetters + "is bigger than" + ((1 << numBits) - 1));
 463     }
 464     bits.appendBits(numLetters, numBits);
 465   }
 466
 467   // Append "bytes" in "mode" mode (encoding) into "bits". On success, store the result in "bits"
 468   // and return true.
 469   static void appendBytes(final ByteArray bytes, int mode, BitVector bits) throws WriterException {
 470     switch (mode) {
 471       case QRCode.MODE_NUMERIC:
 472         appendNumericBytes(bytes, bits);
 473         break;
 474       case QRCode.MODE_ALPHANUMERIC:
 475         appendAlphanumericBytes(bytes, bits);
 476         break;
 477       case QRCode.MODE_8BIT_BYTE:
 478         append8BitBytes(bytes, bits);
 479         break;
 480       case QRCode.MODE_KANJI:
 481         appendKanjiBytes(bytes, bits);
 482         break;
 483       default:
 484         throw new WriterException("Invalid mode: " + mode);
 485     }
 486   }
 487
 488   // Append "bytes" to "bits" using QRCode.MODE_NUMERIC mode. On success, store the result in "bits"
 489   // and return true.
 490   static void appendNumericBytes(final ByteArray bytes, BitVector bits) throws WriterException {
 491     // Validate all the bytes first.
 492     for (int i = 0; i < bytes.size(); ++i) {
 493       int oneByte = bytes.at(i);
 494       if (oneByte < '0' || oneByte > '9') {
 495         throw new WriterException("Non-digit found");
 496       }
 497     }
 498     for (int i = 0; i < bytes.size();) {
 499       final int num1 = bytes.at(i) - '0';
 500       if (i + 2 < bytes.size()) {
 501         // Encode three numeric letters in ten bits.
 502         final int num2 = bytes.at(i + 1) - '0';
 503         final int num3 = bytes.at(i + 2) - '0';
 504         bits.appendBits(num1 * 100 + num2 * 10 + num3, 10);
 505         i += 3;
 506       } else if (i + 1 < bytes.size()) {
 507         // Encode two numeric letters in seven bits.
 508         final int num2 = bytes.at(i + 1) - '0';
 509         bits.appendBits(num1 * 10 + num2, 7);
 510         i += 2;
 511       } else {
 512         // Encode one numeric letter in four bits.
 513         bits.appendBits(num1, 4);
 514         ++i;
 515       }
 516     }
 517   }
 518
 519   // Append "bytes" to "bits" using QRCode.MODE_ALPHANUMERIC mode. On success, store the result in
 520   // "bits" and return true.
 521   static void appendAlphanumericBytes(final ByteArray bytes, BitVector bits) throws WriterException {
 522     for (int i = 0; i < bytes.size();) {
 523       final int code1 = getAlphanumericCode(bytes.at(i));
 524       if (code1 == -1) {
 525         throw new WriterException();
 526       }
 527       if (i + 1 < bytes.size()) {
 528         final int code2 = getAlphanumericCode(bytes.at(i + 1));
 529         if (code2 == -1) {
 530           throw new WriterException();
 531         }
 532         // Encode two alphanumeric letters in 11 bits.
 533         bits.appendBits(code1 * 45 + code2, 11);
 534         i += 2;
 535       } else {
 536         // Encode one alphanumeric letter in six bits.
 537         bits.appendBits(code1, 6);
 538         ++i;
 539       }
 540     }
 541   }
 542
 543   // Append "bytes" to "bits" using QRCode.MODE_8BIT_BYTE mode. On success, store the result in
 544   // "bits" and return true.
 545   static void append8BitBytes(final ByteArray bytes, BitVector bits) {
 546     for (int i = 0; i < bytes.size(); ++i) {
 547       bits.appendBits(bytes.at(i), 8);
 548     }
 549   }
 550
 551   // Append "bytes" to "bits" using QRCode.MODE_KANJI mode. On success, store the result in "bits"
 552   // and return true. See 8.4.5 of JISX0510:2004 (p.21) for how to encode
 553   // Kanji bytes.
 554   static void appendKanjiBytes(final ByteArray bytes, BitVector bits) throws WriterException {
 555     if (bytes.size() % 2 != 0) {
 556       throw new WriterException("Number of bytes must be even");
 557     }
 558     for (int i = 0; i < bytes.size(); i += 2) {
 559       if (!isValidKanji(bytes.at(i), bytes.at(i + 1))) {
 560         throw new WriterException("Invalid Kanji at " + i);
 561       }
 562       final int code = (bytes.at(i) << 8) | bytes.at(i + 1);
 563       int subtracted = -1;
 564       if (code >= 0x8140 && code <= 0x9ffc) {
 565         subtracted = code - 0x8140;
 566       } else if (code >= 0xe040 && code <= 0xebbf) {
 567         subtracted = code - 0xc140;
 568       }
 569       if (subtracted == -1) {
 570         throw new WriterException("Invalid byte sequence: " + bytes);
 571       }
 572       final int encoded = ((subtracted >> 8) * 0xc0) + (subtracted & 0xff);
 573       bits.appendBits(encoded, 13);
 574     }
 575   }
 576
 577   // Check if "byte1" and "byte2" can compose a valid Kanji letter (2-byte Shift_JIS letter). The
 578   // numbers are from http://ja.wikipedia.org/wiki/Shift_JIS.
 579   static boolean isValidKanji(final int byte1, final int byte2) {
 580     return (byte2 != 0x7f &&
 581         ((byte1 >= 0x81 && byte1 <= 0x9f &&
 582             byte2 >= 0x40 && byte2 <= 0xfc) ||
 583             ((byte1 >= 0xe0 && byte1 <= 0xfc &&
 584                 byte2 >= 0x40 && byte2 <= 0xfc))));
 585   }
 586
 587   // Check if "bytes" is a valid Kanji sequence. Used by the unit tests.
 588   static boolean isValidKanjiSequence(final ByteArray bytes) {
 589     if (bytes.size() % 2 != 0) {
 590       return false;
 591     }
 592     int i = 0;
 593     for (; i < bytes.size(); i += 2) {
 594       if (!isValidKanji(bytes.at(i), bytes.at(i + 1))) {
 595         break;
 596       }
 597     }
 598     return i == bytes.size();  // Consumed all bytes?
 599   }
 600
 601 }