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
  24 import java.util.Vector;
  25
  26 /**
  27  * @author satorux@google.com (Satoru Takabayashi) - creator
  28  * @author dswitkin@google.com (Daniel Switkin) - ported from C++
  29  */
  30 public final class Encoder {
  31
  32   // The original table is defined in the table 5 of JISX0510:2004 (p.19).
  33   private static final int kAlphanumericTable[] = {
  34       -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  // 0x00-0x0f
  35       -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  // 0x10-0x1f
  36       36, -1, -1, -1, 37, 38, -1, -1, -1, -1, 39, 40, -1, 41, 42, 43,  // 0x20-0x2f
  37       0,   1,  2,  3,  4,  5,  6,  7,  8,  9, 44, -1, -1, -1, -1, -1,  // 0x30-0x3f
  38       -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,  // 0x40-0x4f
  39       25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1,  // 0x50-0x5f
  40   };
  41
  42   private static final class RSBlockInfo {
  43
  44     int num_bytes;
  45     int block_info[][];
  46
  47     public RSBlockInfo(int num_bytes, int[][] block_info) {
  48       this.num_bytes = num_bytes;
  49       this.block_info = block_info;
  50     }
  51
  52   }
  53
  54   // The table is from table 12 of JISX0510:2004 (p. 30). The "block_info" parts are ordered by
  55   // L, M, Q, H. Within each block_info, the 0th element is num_ec_bytes, and the 1st element is
  56   // num_rs_blocks. The table was doublechecked by komatsu.
  57   private static final RSBlockInfo kRSBlockTable[] = {
  58       new RSBlockInfo(  26, new int[][]{ {  7,  1}, {  10,  1}, {  13,  1}, {  17,  1}}),  // Version  1
  59       new RSBlockInfo(  44, new int[][]{ { 10,  1}, {  16,  1}, {  22,  1}, {  28,  1}}),  // Version  2
  60       new RSBlockInfo(  70, new int[][]{ { 15,  1}, {  26,  1}, {  36,  2}, {  44,  2}}),  // Version  3
  61       new RSBlockInfo( 100, new int[][]{ { 20,  1}, {  36,  2}, {  52,  2}, {  64,  4}}),  // Version  4
  62       new RSBlockInfo( 134, new int[][]{ { 26,  1}, {  48,  2}, {  72,  4}, {  88,  4}}),  // Version  5
  63       new RSBlockInfo( 172, new int[][]{ { 36,  2}, {  64,  4}, {  96,  4}, { 112,  4}}),  // Version  6
  64       new RSBlockInfo( 196, new int[][]{ { 40,  2}, {  72,  4}, { 108,  6}, { 130,  5}}),  // Version  7
  65       new RSBlockInfo( 242, new int[][]{ { 48,  2}, {  88,  4}, { 132,  6}, { 156,  6}}),  // Version  8
  66       new RSBlockInfo( 292, new int[][]{ { 60,  2}, { 110,  5}, { 160,  8}, { 192,  8}}),  // Version  9
  67       new RSBlockInfo( 346, new int[][]{ { 72,  4}, { 130,  5}, { 192,  8}, { 224,  8}}),  // Version 10
  68       new RSBlockInfo( 404, new int[][]{ { 80,  4}, { 150,  5}, { 224,  8}, { 264, 11}}),  // Version 11
  69       new RSBlockInfo( 466, new int[][]{ { 96,  4}, { 176,  8}, { 260, 10}, { 308, 11}}),  // Version 12
  70       new RSBlockInfo( 532, new int[][]{ {104,  4}, { 198,  9}, { 288, 12}, { 352, 16}}),  // Version 13
  71       new RSBlockInfo( 581, new int[][]{ {120,  4}, { 216,  9}, { 320, 16}, { 384, 16}}),  // Version 14
  72       new RSBlockInfo( 655, new int[][]{ {132,  6}, { 240, 10}, { 360, 12}, { 432, 18}}),  // Version 15
  73       new RSBlockInfo( 733, new int[][]{ {144,  6}, { 280, 10}, { 408, 17}, { 480, 16}}),  // Version 16
  74       new RSBlockInfo( 815, new int[][]{ {168,  6}, { 308, 11}, { 448, 16}, { 532, 19}}),  // Version 17
  75       new RSBlockInfo( 901, new int[][]{ {180,  6}, { 338, 13}, { 504, 18}, { 588, 21}}),  // Version 18
  76       new RSBlockInfo( 991, new int[][]{ {196,  7}, { 364, 14}, { 546, 21}, { 650, 25}}),  // Version 19
  77       new RSBlockInfo(1085, new int[][]{ {224,  8}, { 416, 16}, { 600, 20}, { 700, 25}}),  // Version 20
  78       new RSBlockInfo(1156, new int[][]{ {224,  8}, { 442, 17}, { 644, 23}, { 750, 25}}),  // Version 21
  79       new RSBlockInfo(1258, new int[][]{ {252,  9}, { 476, 17}, { 690, 23}, { 816, 34}}),  // Version 22
  80       new RSBlockInfo(1364, new int[][]{ {270,  9}, { 504, 18}, { 750, 25}, { 900, 30}}),  // Version 23
  81       new RSBlockInfo(1474, new int[][]{ {300, 10}, { 560, 20}, { 810, 27}, { 960, 32}}),  // Version 24
  82       new RSBlockInfo(1588, new int[][]{ {312, 12}, { 588, 21}, { 870, 29}, {1050, 35}}),  // Version 25
  83       new RSBlockInfo(1706, new int[][]{ {336, 12}, { 644, 23}, { 952, 34}, {1110, 37}}),  // Version 26
  84       new RSBlockInfo(1828, new int[][]{ {360, 12}, { 700, 25}, {1020, 34}, {1200, 40}}),  // Version 27
  85       new RSBlockInfo(1921, new int[][]{ {390, 13}, { 728, 26}, {1050, 35}, {1260, 42}}),  // Version 28
  86       new RSBlockInfo(2051, new int[][]{ {420, 14}, { 784, 28}, {1140, 38}, {1350, 45}}),  // Version 29
  87       new RSBlockInfo(2185, new int[][]{ {450, 15}, { 812, 29}, {1200, 40}, {1440, 48}}),  // Version 30
  88       new RSBlockInfo(2323, new int[][]{ {480, 16}, { 868, 31}, {1290, 43}, {1530, 51}}),  // Version 31
  89       new RSBlockInfo(2465, new int[][]{ {510, 17}, { 924, 33}, {1350, 45}, {1620, 54}}),  // Version 32
  90       new RSBlockInfo(2611, new int[][]{ {540, 18}, { 980, 35}, {1440, 48}, {1710, 57}}),  // Version 33
  91       new RSBlockInfo(2761, new int[][]{ {570, 19}, {1036, 37}, {1530, 51}, {1800, 60}}),  // Version 34
  92       new RSBlockInfo(2876, new int[][]{ {570, 19}, {1064, 38}, {1590, 53}, {1890, 63}}),  // Version 35
  93       new RSBlockInfo(3034, new int[][]{ {600, 20}, {1120, 40}, {1680, 56}, {1980, 66}}),  // Version 36
  94       new RSBlockInfo(3196, new int[][]{ {630, 21}, {1204, 43}, {1770, 59}, {2100, 70}}),  // Version 37
  95       new RSBlockInfo(3362, new int[][]{ {660, 22}, {1260, 45}, {1860, 62}, {2220, 74}}),  // Version 38
  96       new RSBlockInfo(3532, new int[][]{ {720, 24}, {1316, 47}, {1950, 65}, {2310, 77}}),  // Version 39
  97       new RSBlockInfo(3706, new int[][]{ {750, 25}, {1372, 49}, {2040, 68}, {2430, 81}}),  // Version 40
  98   };
  99
 100   private static final class BlockPair {
 101
 102     private ByteArray dataBytes;
 103     private ByteArray errorCorrectionBytes;
 104
 105     public BlockPair(ByteArray data, ByteArray errorCorrection) {
 106       dataBytes = data;
 107       errorCorrectionBytes = errorCorrection;
 108     }
 109
 110     public ByteArray getDataBytes() {
 111       return dataBytes;
 112     }
 113
 114     public ByteArray getErrorCorrectionBytes() {
 115       return errorCorrectionBytes;
 116     }
 117
 118   }
 119
 120   // Encode "bytes" with the error correction level "ec_level". The encoding mode will be chosen
 121   // internally by ChooseMode(). On success, store the result in "qr_code" and return true. On
 122   // error, return false. We recommend you to use QRCode.EC_LEVEL_L (the lowest level) for
 123   // "ec_level" since our primary use is to show QR code on desktop screens. We don't need very
 124   // strong error correction for this purpose.
 125   //
 126   // Note that there is no way to encode bytes in MODE_KANJI. We might want to add EncodeWithMode()
 127   // with which clients can specify the encoding mode. For now, we don't need the functionality.
 128   public static boolean Encode(final ByteArray bytes, int ec_level, QRCode qr_code) {
 129     // Step 1: Choose the mode (encoding).
 130     final int mode = ChooseMode(bytes);
 131
 132     // Step 2: Append "bytes" into "data_bits" in appropriate encoding.
 133     BitVector data_bits = new BitVector();
 134     if (!AppendBytes(bytes, mode, data_bits)) {
 135       return false;
 136     }
 137     // Step 3: Initialize QR code that can contain "data_bits".
 138     final int num_input_bytes = data_bits.num_bytes();
 139     if (!InitQRCode(num_input_bytes, ec_level, mode, qr_code)) {
 140       return false;
 141     }
 142
 143     // Step 4: Build another bit vector that contains header and data.
 144     BitVector header_and_data_bits = new BitVector();
 145     if (!AppendModeInfo(qr_code.mode(), header_and_data_bits)) {
 146       return false;
 147     }
 148     if (!AppendLengthInfo(bytes.size(), qr_code.version(), qr_code.mode(), header_and_data_bits)) {
 149       return false;
 150     }
 151     header_and_data_bits.AppendBitVector(data_bits);
 152
 153     // Step 5: Terminate the bits properly.
 154     if (!TerminateBits(qr_code.num_data_bytes(), header_and_data_bits)) {
 155       return false;
 156     }
 157
 158     // Step 6: Interleave data bits with error correction code.
 159     BitVector final_bits = new BitVector();
 160     InterleaveWithECBytes(header_and_data_bits, qr_code.num_total_bytes(), qr_code.num_data_bytes(),
 161         qr_code.num_rs_blocks(), final_bits);
 162
 163     // Step 7: Choose the mask pattern and set to "qr_code".
 164     ByteMatrix matrix = new ByteMatrix(qr_code.matrix_width(), qr_code.matrix_width());
 165     qr_code.set_mask_pattern(ChooseMaskPattern(final_bits, qr_code.ec_level(), qr_code.version(),
 166         matrix));
 167     if (qr_code.mask_pattern() == -1) {
 168       // There was an error.
 169       return false;
 170     }
 171
 172     // Step 8.  Build the matrix and set it to "qr_code".
 173     MatrixUtil.BuildMatrix(final_bits, qr_code.ec_level(), qr_code.version(),
 174         qr_code.mask_pattern(), matrix);
 175     qr_code.set_matrix(matrix);
 176     // Step 9.  Make sure we have a valid QR Code.
 177     if (!qr_code.IsValid()) {
 178       Debug.LOG_ERROR("Invalid QR code: " + qr_code.toString());
 179       return false;
 180     }
 181     return true;
 182   }
 183
 184   // Return the code point of the table used in alphanumeric mode. Return -1 if there is no
 185   // corresponding code in the table.
 186   static int GetAlphanumericCode(int code) {
 187     if (code < kAlphanumericTable.length) {
 188       return kAlphanumericTable[code];
 189     }
 190     return -1;
 191   }
 192
 193   // Choose the best mode by examining the content of "bytes". The function is guaranteed to return
 194   // a valid mode.
 195   //
 196   // Note that this function does not return MODE_KANJI, as we cannot distinguish Shift_JIS from
 197   // other encodings such as ISO-8859-1, from data bytes alone. For example "\xE0\xE0" can be
 198   // interpreted as one character in Shift_JIS, but also two characters in ISO-8859-1.
 199   //
 200   // JAVAPORT: This MODE_KANJI limitation sounds like a problem for us.
 201   public static int ChooseMode(final ByteArray bytes) {
 202     boolean has_numeric = false;
 203     boolean has_alphanumeric = false;
 204     boolean has_other = false;
 205     for (int i = 0; i < bytes.size(); ++i) {
 206       final int oneByte = bytes.at(i);
 207       if (oneByte >= '0' && oneByte <= '9') {
 208         has_numeric = true;
 209       } else if (GetAlphanumericCode(oneByte) != -1) {
 210         has_alphanumeric = true;
 211       } else {
 212         has_other = true;
 213       }
 214     }
 215     if (has_other) {
 216       return QRCode.MODE_8BIT_BYTE;
 217     } else if (has_alphanumeric) {
 218       return QRCode.MODE_ALPHANUMERIC;
 219     } else if (has_numeric) {
 220       return QRCode.MODE_NUMERIC;
 221     }
 222     // "bytes" must be empty to reach here.
 223     Debug.DCHECK(bytes.empty());
 224     return QRCode.MODE_8BIT_BYTE;
 225   }
 226
 227   private static int ChooseMaskPattern(final BitVector bits, int ec_level, int version,
 228       ByteMatrix matrix) {
 229     if (!QRCode.IsValidMatrixWidth(matrix.width())) {
 230       Debug.LOG_ERROR("Invalid matrix width: " + matrix.width());
 231       return -1;
 232     }
 233
 234     int min_penalty = Integer.MAX_VALUE;  // Lower penalty is better.
 235     int best_mask_pattern = -1;
 236     // We try all mask patterns to choose the best one.
 237     for (int i = 0; i < QRCode.kNumMaskPatterns; ++i) {
 238       final int mask_pattern = i;
 239       if (!MatrixUtil.BuildMatrix(bits, ec_level, version,
 240           mask_pattern, matrix)) {
 241         return -1;
 242       }
 243       final int penalty = MaskUtil.CalculateMaskPenalty(matrix);
 244       Debug.LOG_INFO("mask_pattern: " + mask_pattern + ", " + "penalty: " + penalty);
 245       if (penalty < min_penalty) {
 246         min_penalty = penalty;
 247         best_mask_pattern = mask_pattern;
 248       }
 249     }
 250     return best_mask_pattern;
 251   }
 252
 253   // Initialize "qr_code" according to "num_input_bytes", "ec_level", and "mode". On success, modify
 254   // "qr_code" and return true. On error, return false.
 255   private static boolean InitQRCode(int num_input_bytes, int ec_level, int mode, QRCode qr_code) {
 256     qr_code.set_ec_level(ec_level);
 257     qr_code.set_mode(mode);
 258
 259     if (!QRCode.IsValidECLevel(ec_level)) {
 260       Debug.LOG_ERROR("Invalid EC level: " + ec_level);
 261       return false;
 262     }
 263
 264     // In the following comments, we use numbers of Version 7-H.
 265     for (int i = 0; i < kRSBlockTable.length; ++i) {
 266       final RSBlockInfo row = kRSBlockTable[i];
 267       // num_bytes = 196
 268       final int num_bytes = row.num_bytes;
 269       // num_ec_bytes = 130
 270       final int num_ec_bytes  = row.block_info[ec_level][0];
 271       // num_rs_blocks = 5
 272       final int num_rs_blocks = row.block_info[ec_level][1];
 273       // num_data_bytes = 196 - 130 = 66
 274       final int num_data_bytes = num_bytes - num_ec_bytes;
 275       // We want to choose the smallest version which can contain data of "num_input_bytes" + some
 276       // extra bits for the header (mode info and length info). The header can be three bytes
 277       // (precisely 4 + 16 bits) at most. Hence we do +3 here.
 278       if (num_data_bytes >= num_input_bytes + 3) {
 279         // Yay, we found the proper rs block info!
 280         qr_code.set_version(i + 1);
 281         qr_code.set_num_total_bytes(num_bytes);
 282         qr_code.set_num_data_bytes(num_data_bytes);
 283         qr_code.set_num_rs_blocks(num_rs_blocks);
 284         // num_ec_bytes = 196 - 66 = 130
 285         qr_code.set_num_ec_bytes(num_bytes - num_data_bytes);
 286         // num_matrix_width = 21 + 6 * 4 = 45
 287         qr_code.set_matrix_width(21 + i * 4);
 288         return true;
 289       }
 290     }
 291     Debug.LOG_ERROR("Cannot find proper rs block info (input data too big?)");
 292     return false;
 293   }
 294
 295   // Terminate bits as described in 8.4.8 and 8.4.9 of JISX0510:2004 (p.24).
 296   static boolean TerminateBits(int num_data_bytes, BitVector bits) {
 297     final int capacity = num_data_bytes * 8;
 298     if (bits.size() > capacity) {
 299       Debug.LOG_ERROR("data bits cannot fit in the QR Code" + bits.size() + " > " + capacity);
 300       return false;
 301     }
 302     // Append termination bits. See 8.4.8 of JISX0510:2004 (p.24) for details.
 303     for (int i = 0; i < 4 && bits.size() < capacity; ++i) {
 304       bits.AppendBit(0);
 305     }
 306     final int num_bits_in_last_byte = bits.size() % 8;
 307     // If the last byte isn't 8-bit aligned, we'll add padding bits.
 308     if (num_bits_in_last_byte > 0) {
 309       final int num_padding_bits = 8 - num_bits_in_last_byte;
 310       for (int i = 0; i < num_padding_bits; ++i) {
 311         bits.AppendBit(0);
 312       }
 313     }
 314     // Should be 8-bit aligned here.
 315     Debug.DCHECK_EQ(0, bits.size() % 8);
 316     // If we have more space, we'll fill the space with padding patterns defined in 8.4.9 (p.24).
 317     final int num_padding_bytes = num_data_bytes - bits.num_bytes();
 318     for (int i = 0; i < num_padding_bytes; ++i) {
 319       if (i % 2 == 0) {
 320         bits.AppendBits(0xec, 8);
 321       } else {
 322         bits.AppendBits(0x11, 8);
 323       }
 324     }
 325     Debug.DCHECK_EQ(bits.size(), capacity);  // Should be same.
 326     return bits.size() == capacity;
 327   }
 328
 329   // Get number of data bytes and number of error correction bytes for block id "block_id". Store
 330   // the result in "num_data_bytes_in_block", and "num_ec_bytes_in_block". See table 12 in 8.5.1 of
 331   // JISX0510:2004 (p.30)
 332   static void GetNumDataBytesAndNumECBytesForBlockID(int num_total_bytes, int num_data_bytes,
 333       int num_rs_blocks, int block_id, int[] num_data_bytes_in_block,
 334       int[] num_ec_bytes_in_block) {
 335     Debug.DCHECK_LT(block_id, num_rs_blocks);
 336     // num_rs_blocks_in_group2 = 196 % 5 = 1
 337     final int num_rs_blocks_in_group2 = num_total_bytes % num_rs_blocks;
 338     // num_rs_blocks_in_group1 = 5 - 1 = 4
 339     final int num_rs_blocks_in_group1 = num_rs_blocks - num_rs_blocks_in_group2;
 340     // num_total_bytes_in_group1 = 196 / 5 = 39
 341     final int num_total_bytes_in_group1 = num_total_bytes / num_rs_blocks;
 342     // num_total_bytes_in_group2 = 39 + 1 = 40
 343     final int num_total_bytes_in_group2 = num_total_bytes_in_group1 + 1;
 344     // num_data_bytes_in_group1 = 66 / 5 = 13
 345     final int num_data_bytes_in_group1 = num_data_bytes / num_rs_blocks;
 346     // num_data_bytes_in_group2 = 13 + 1 = 14
 347     final int num_data_bytes_in_group2 = num_data_bytes_in_group1 + 1;
 348     // num_ec_bytes_in_group1 = 39 - 13 = 26
 349     final int num_ec_bytes_in_group1 = num_total_bytes_in_group1 -
 350         num_data_bytes_in_group1;
 351     // num_ec_bytes_in_group2 = 40 - 14 = 26
 352     final int num_ec_bytes_in_group2 = num_total_bytes_in_group2 -
 353         num_data_bytes_in_group2;
 354     // Sanity checks.
 355     // 26 = 26
 356     Debug.DCHECK_EQ(num_ec_bytes_in_group1, num_ec_bytes_in_group2);
 357     // 5 = 4 + 1.
 358     Debug.DCHECK_EQ(num_rs_blocks, num_rs_blocks_in_group1 + num_rs_blocks_in_group2);
 359     // 196 = (13 + 26) * 4 + (14 + 26) * 1
 360     Debug.DCHECK_EQ(num_total_bytes,
 361         ((num_data_bytes_in_group1 + num_ec_bytes_in_group1) *
 362             num_rs_blocks_in_group1) +
 363             ((num_data_bytes_in_group2 + num_ec_bytes_in_group2) *
 364                 num_rs_blocks_in_group2));
 365
 366     if (block_id < num_rs_blocks_in_group1) {
 367       num_data_bytes_in_block[0] = num_data_bytes_in_group1;
 368       num_ec_bytes_in_block[0] = num_ec_bytes_in_group1;
 369     } else {
 370       num_data_bytes_in_block[0] = num_data_bytes_in_group2;
 371       num_ec_bytes_in_block[0] = num_ec_bytes_in_group2;
 372     }
 373   }
 374
 375   // Interleave "bits" with corresponding error correction bytes. On success, store the result in
 376   // "result" and return true. On error, return false. The interleave rule is complicated. See 8.6
 377   // of JISX0510:2004 (p.37) for details.
 378   static boolean InterleaveWithECBytes(final BitVector bits, int num_total_bytes,
 379       int num_data_bytes, int num_rs_blocks, BitVector result) {
 380
 381     // "bits" must have "num_data_bytes" bytes of data.
 382     Debug.DCHECK(bits.num_bytes() == num_data_bytes);
 383
 384     // Step 1.  Divide data bytes into blocks and generate error correction bytes for them. We'll
 385     // store the divided data bytes blocks and error correction bytes blocks into "blocks".
 386     int data_bytes_offset = 0;
 387     int max_num_data_bytes = 0;
 388     int max_num_ec_bytes = 0;
 389
 390     // Since, we know the number of reedsolmon blocks, we can initialize the vector with the number.
 391     Vector blocks = new Vector(num_rs_blocks);
 392
 393     for (int i = 0; i < num_rs_blocks; ++i) {
 394       int[] num_data_bytes_in_block = new int[1];
 395       int[] num_ec_bytes_in_block = new int[1];
 396       GetNumDataBytesAndNumECBytesForBlockID(
 397           num_total_bytes, num_data_bytes, num_rs_blocks, i,
 398           num_data_bytes_in_block, num_ec_bytes_in_block);
 399
 400       ByteArray data_bytes = new ByteArray();
 401       data_bytes.set(bits.getArray(), data_bytes_offset, num_data_bytes_in_block[0]);
 402       ByteArray ec_bytes = GenerateECBytes(data_bytes, num_ec_bytes_in_block[0]);
 403       blocks.addElement(new BlockPair(data_bytes, ec_bytes));
 404
 405       max_num_data_bytes = Math.max(max_num_data_bytes, data_bytes.size());
 406       max_num_ec_bytes = Math.max(max_num_ec_bytes, ec_bytes.size());
 407       data_bytes_offset += num_data_bytes_in_block[0];
 408     }
 409     Debug.DCHECK_EQ(num_data_bytes, data_bytes_offset);
 410
 411     // First, place data blocks.
 412     for (int i = 0; i < max_num_data_bytes; ++i) {
 413       for (int j = 0; j < blocks.size(); ++j) {
 414         final ByteArray data_bytes = ((BlockPair) blocks.elementAt(j)).getDataBytes();
 415         if (i < data_bytes.size()) {
 416           result.AppendBits(data_bytes.at(i), 8);
 417         }
 418       }
 419     }
 420     // Then, place error correction blocks.
 421     for (int i = 0; i < max_num_ec_bytes; ++i) {
 422       for (int j = 0; j < blocks.size(); ++j) {
 423         final ByteArray ec_bytes = ((BlockPair) blocks.elementAt(j)).getErrorCorrectionBytes();
 424         if (i < ec_bytes.size()) {
 425           result.AppendBits(ec_bytes.at(i), 8);
 426         }
 427       }
 428     }
 429     if (num_total_bytes == result.num_bytes()) {  // Should be same.
 430       return true;
 431     }
 432     Debug.LOG_ERROR("Interleaving error: " + num_total_bytes + " and " + result.num_bytes() +
 433         " differ.");
 434     return false;
 435   }
 436
 437   static ByteArray GenerateECBytes(ByteArray data_bytes, int num_ec_bytes_in_block) {
 438     int numDataBytes = data_bytes.size();
 439     int[] toEncode = new int[numDataBytes + num_ec_bytes_in_block];
 440     for (int i = 0; i < numDataBytes; i++) {
 441       toEncode[i] = data_bytes.at(i);
 442     }
 443     new ReedSolomonEncoder(GF256.QR_CODE_FIELD).encode(toEncode, num_ec_bytes_in_block);
 444
 445     ByteArray ec_bytes = new ByteArray(num_ec_bytes_in_block);
 446     for (int i = 0; i < num_ec_bytes_in_block; i++) {
 447       ec_bytes.set(i, toEncode[numDataBytes + i]);
 448     }
 449     return ec_bytes;
 450   }
 451
 452   // Append mode info. On success, store the result in "bits" and return true. On error, return
 453   // false.
 454   static boolean AppendModeInfo(int mode, BitVector bits) {
 455     final int code = QRCode.GetModeCode(mode);
 456     if (code == -1) {
 457       Debug.LOG_ERROR("Invalid mode: " + mode);
 458       return false;
 459     }
 460     bits.AppendBits(code, 4);
 461     return true;
 462   }
 463
 464
 465   // Append length info. On success, store the result in "bits" and return true. On error, return
 466   // false.
 467   static boolean AppendLengthInfo(int num_bytes, int version, int mode, BitVector bits) {
 468     int num_letters = num_bytes;
 469     // In Kanji mode, a letter is represented in two bytes.
 470     if (mode == QRCode.MODE_KANJI) {
 471       Debug.DCHECK_EQ(0, num_letters % 2);
 472       num_letters /= 2;
 473     }
 474
 475     final int num_bits = QRCode.GetNumBitsForLength(version, mode);
 476     if (num_bits == -1) {
 477       Debug.LOG_ERROR("num_bits unset");
 478       return false;
 479     }
 480     if (num_letters > ((1 << num_bits) - 1)) {
 481       Debug.LOG_ERROR(num_letters + "is bigger than" + ((1 << num_bits) - 1));
 482       return false;
 483     }
 484     bits.AppendBits(num_letters, num_bits);
 485     return true;
 486   }
 487
 488   // Append "bytes" in "mode" mode (encoding) into "bits". On success, store the result in "bits"
 489   // and return true. On error, return false.
 490   static boolean AppendBytes(final ByteArray bytes, int mode, BitVector bits) {
 491     switch (mode) {
 492       case QRCode.MODE_NUMERIC:
 493         return AppendNumericBytes(bytes, bits);
 494       case QRCode.MODE_ALPHANUMERIC:
 495         return AppendAlphanumericBytes(bytes, bits);
 496       case QRCode.MODE_8BIT_BYTE:
 497         return Append8BitBytes(bytes, bits);
 498       case QRCode.MODE_KANJI:
 499         return AppendKanjiBytes(bytes, bits);
 500       default:
 501         break;
 502     }
 503     Debug.LOG_ERROR("Invalid mode: " + mode);
 504     return false;
 505   }
 506
 507   // Append "bytes" to "bits" using QRCode.MODE_NUMERIC mode. On success, store the result in "bits"
 508   // and return true. On error, return false.
 509   static boolean AppendNumericBytes(final ByteArray bytes, BitVector bits) {
 510     // Validate all the bytes first.
 511     for (int i = 0; i < bytes.size(); ++i) {
 512       int oneByte = bytes.at(i);
 513       if (oneByte < '0' || oneByte > '9') {
 514         return false;
 515       }
 516     }
 517     for (int i = 0; i < bytes.size();) {
 518       final int num1 = bytes.at(i) - '0';
 519       if (i + 2 < bytes.size()) {
 520         // Encode three numeric letters in ten bits.
 521         final int num2 = bytes.at(i + 1) - '0';
 522         final int num3 = bytes.at(i + 2) - '0';
 523         bits.AppendBits(num1 * 100 + num2 * 10 + num3, 10);
 524         i += 3;
 525       } else if (i + 1 < bytes.size()) {
 526         // Encode two numeric letters in seven bits.
 527         final int num2 = bytes.at(i + 1) - '0';
 528         bits.AppendBits(num1 * 10 + num2, 7);
 529         i += 2;
 530       } else {
 531         // Encode one numeric letter in four bits.
 532         bits.AppendBits(num1, 4);
 533         ++i;
 534       }
 535     }
 536     return true;
 537   }
 538
 539   // Append "bytes" to "bits" using QRCode.MODE_ALPHANUMERIC mode. On success, store the result in
 540   // "bits" and return true. On error, return false.
 541   static boolean AppendAlphanumericBytes(final ByteArray bytes, BitVector bits) {
 542     for (int i = 0; i < bytes.size();) {
 543       final int code1 = GetAlphanumericCode(bytes.at(i));
 544       if (code1 == -1) {
 545         return false;
 546       }
 547       if (i + 1 < bytes.size()) {
 548         final int code2 = GetAlphanumericCode(bytes.at(i + 1));
 549         if (code2 == -1) {
 550           return false;
 551         }
 552         // Encode two alphanumeric letters in 11 bits.
 553         bits.AppendBits(code1 * 45 + code2, 11);
 554         i += 2;
 555       } else {
 556         // Encode one alphanumeric letter in six bits.
 557         bits.AppendBits(code1, 6);
 558         ++i;
 559       }
 560     }
 561     return true;
 562   }
 563
 564   // Append "bytes" to "bits" using QRCode.MODE_8BIT_BYTE mode. On success, store the result in
 565   // "bits" and return true. On error, return false.
 566   static boolean Append8BitBytes(final ByteArray bytes, BitVector bits) {
 567     for (int i = 0; i < bytes.size(); ++i) {
 568       bits.AppendBits(bytes.at(i), 8);
 569     }
 570     return true;
 571   }
 572
 573   // Append "bytes" to "bits" using QRCode.MODE_KANJI mode. On success, store the result in "bits"
 574   // and return true. On error, return false. See 8.4.5 of JISX0510:2004 (p.21) for how to encode
 575   // Kanji bytes.
 576   static boolean AppendKanjiBytes(final ByteArray bytes, BitVector bits) {
 577     if (bytes.size() % 2 != 0) {
 578       // JAVAPORT: Our log implementation throws, which causes the unit test to fail.
 579       //Debug.LOG_ERROR("Invalid byte sequence: " + bytes);
 580       return false;
 581     }
 582     for (int i = 0; i < bytes.size(); i += 2) {
 583       Debug.DCHECK(IsValidKanji(bytes.at(i), bytes.at(i + 1)));
 584       final int code = (bytes.at(i) << 8) | bytes.at(i + 1);
 585       int subtracted = -1;
 586       if (code >= 0x8140 && code <= 0x9ffc) {
 587         subtracted = code - 0x8140;
 588       } else if (code >= 0xe040 && code <= 0xebbf) {
 589         subtracted = code - 0xc140;
 590       }
 591       if (subtracted == -1) {
 592         Debug.LOG_ERROR("Invalid byte sequence: " + bytes);
 593         return false;
 594       }
 595       final int encoded = ((subtracted >> 8) * 0xc0) + (subtracted & 0xff);
 596       bits.AppendBits(encoded, 13);
 597     }
 598     return true;
 599   }
 600
 601   // Check if "byte1" and "byte2" can compose a valid Kanji letter (2-byte Shift_JIS letter). The
 602   // numbers are from http://ja.wikipedia.org/wiki/Shift_JIS.
 603   static boolean IsValidKanji(final int byte1, final int byte2) {
 604     return (byte2 != 0x7f &&
 605         ((byte1 >= 0x81 && byte1 <= 0x9f &&
 606             byte2 >= 0x40 && byte2 <= 0xfc) ||
 607             ((byte1 >= 0xe0 && byte1 <= 0xfc &&
 608                 byte2 >= 0x40 && byte2 <= 0xfc))));
 609   }
 610
 611   // Check if "bytes" is a valid Kanji sequence. Used by the unit tests.
 612   static boolean IsValidKanjiSequence(final ByteArray bytes) {
 613     if (bytes.size() % 2 != 0) {
 614       return false;
 615     }
 616     int i = 0;
 617     for (; i < bytes.size(); i += 2) {
 618       if (!IsValidKanji(bytes.at(i), bytes.at(i + 1))) {
 619         break;
 620       }
 621     }
 622     return i == bytes.size();  // Consumed all bytes?
 623   }
 624
 625 }