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