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