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