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     Matrix matrix = new Matrix(qr_code.matrix_width(), qr_code.matrix_width());
 329     qr_code.set_mask_pattern(ChooseMaskPattern(final_bits,
 330         qr_code.ec_level(),
 331         qr_code.version(),
 332         matrix));
 333     if (qr_code.mask_pattern() == -1) {
 334       // There was an error.
 335       delete matrix;
 336       return false;
 337     }
 338
 339     // Step 8.  Build the matrix and set it to "qr_code".
 340     MatrixUtil.BuildMatrix(final_bits,
 341       qr_code.ec_level(),
 342       qr_code.version(),
 343       qr_code.mask_pattern(), matrix);
 344     qr_code.set_matrix(matrix);
 345     // Step 9.  Make sure we have a valid QR Code.
 346     if (!qr_code.IsValid()) {
 347       Debug.LOG_ERROR("Invalid QR code: " + qr_code.DebugString());
 348       return false;
 349     }
 350     return true;
 351   }
 352
 353   // The functions below are public but not intended to be used
 354   // outside the library.  We make them public for ease of unit
 355   // testing with gUnit.
 356
 357   // Return the code point of the table used in alphanumeric mode.
 358   // Return -1 if there is no corresponding code in the table.
 359   static int GetAlphanumericCode(int code) {
 360     if (code < arraysize(kAlphanumericTable)) {
 361       return kAlphanumericTable[code];
 362     }
 363     return -1;
 364   }
 365
 366   // Choose the best mode from the content of "bytes".
 367   // The function is guaranteed to return valid mode.
 368   //
 369   // Note that the function does not return MODE_KANJI, as we cannot
 370   // distinguish Shift_JIS from other encodings such as ISO-8859-1, from
 371   // data bytes alone.  For example "\xE0\xE0" can be interpreted as one
 372   // character in Shift_JIS, but also two characters in ISO-8859-1.
 373   static int ChooseMode(final StringPiece &bytes) {
 374     boolean has_numeric = false;
 375     boolean has_alphanumeric = false;
 376     boolean has_other = false;
 377     for (int i = 0; i < bytes.size(); ++i) {
 378       final int byte = bytes[i];
 379       if (byte >= '0' && byte <= '9') {
 380       has_numeric = true;
 381     } else if (GetAlphanumericCode(byte) != -1) {
 382       has_alphanumeric = true;
 383     } else {
 384       has_other = true;
 385     }
 386     }
 387     if (has_other) {
 388       return QRCode.MODE_8BIT_BYTE;
 389     } else if (has_alphanumeric) {
 390       return QRCode.MODE_ALPHANUMERIC;
 391     } else if (has_numeric) {
 392       return QRCode.MODE_NUMERIC;
 393     }
 394     // "bytes" must be empty to reach here.
 395     Debug.DCHECK(bytes.empty());
 396     return QRCode.MODE_8BIT_BYTE;
 397   }
 398
 399   private static int ChooseMaskPattern(final BitVector &bits, int ec_level, int version,
 400       Matrix matrix) {
 401     if (!QRCode.IsValidMatrixWidth(matrix.width())) {
 402       Debug.LOG_ERROR("Invalid matrix width: " + matrix.width());
 403       return -1;
 404     }
 405
 406     int min_penalty = Integer.MAX_VALUE;  // Lower penalty is better.
 407     int best_mask_pattern = -1;
 408     // We try all mask patterns to choose the best one.
 409     for (int i = 0; i < kNumMaskPatterns; ++i) {
 410       final int mask_pattern = i;
 411       if (!MatrixUtil.BuildMatrix(bits, ec_level, version,
 412           mask_pattern, matrix)) {
 413         return -1;
 414       }
 415       final int penalty = MaskUtil.CalculateMaskPenalty(matrix);
 416       Debug.LOG_INFO("mask_pattern: " + mask_pattern + ", " + "penalty: " + penalty);
 417       if (penalty < min_penalty) {
 418         min_penalty = penalty;
 419         best_mask_pattern = mask_pattern;
 420       }
 421     }
 422     return best_mask_pattern;
 423   }
 424
 425   // Initialize "qr_code" according to "num_input_bytes", "ec_level",
 426   // and "mode". On success, modify "qr_code" and return true.  On
 427   // error, return false.
 428   static boolean InitQRCode(int num_input_bytes, int ec_level, int mode, QRCode *qr_code) {
 429     qr_code.set_ec_level(ec_level);
 430     qr_code.set_mode(mode);
 431
 432     if (!QRCode.IsValidECLevel(ec_level)) {
 433     Debug.LOG_ERROR("Invalid EC level: " + ec_level);
 434     return false;
 435   }
 436
 437     // In the following comments, we use numbers of Version 7-H.
 438     for (int i = 0; i < arraysize(kRSBlockTable); ++i) {
 439       final RSBlockInfo &row = kRSBlockTable[i];
 440       // num_bytes = 196
 441       final int num_bytes = row.num_bytes;
 442       // num_ec_bytes = 130
 443       final int num_ec_bytes  = row.block_info[ec_level].num_ec_bytes;
 444       // num_rs_blocks = 5
 445       final int num_rs_blocks = row.block_info[ec_level].num_rs_blocks;
 446       // num_data_bytes = 196 - 130 = 66
 447       final int num_data_bytes = num_bytes - num_ec_bytes;
 448       // We want to choose the smallest version which can contain data
 449       // of "num_input_bytes" + some extra bits for the header (mode
 450       // info and length info). The header can be three bytes
 451       // (precisely 4 + 16 bits) at most.  Hence we do +3 here.
 452       if (num_data_bytes >= num_input_bytes + 3) {
 453         // Yay, we found the proper rs block info!
 454         qr_code.set_version(i + 1);
 455         qr_code.set_num_total_bytes(num_bytes);
 456         qr_code.set_num_data_bytes(num_data_bytes);
 457         qr_code.set_num_rs_blocks(num_rs_blocks);
 458         // num_ec_bytes = 196 - 66 = 130
 459         qr_code.set_num_ec_bytes(num_bytes - num_data_bytes);
 460         // num_matrix_width = 21 + 6 * 4 = 45
 461         qr_code.set_matrix_width(21 + i * 4);
 462         return true;
 463       }
 464     }
 465     Debug.LOG_ERROR("Cannot find proper rs block info (input data too big?)");
 466     return false;
 467   }
 468
 469   // Terminate bits as described in 8.4.8 and 8.4.9 of JISX0510:2004
 470   // (p.24).
 471   static boolean TerminateBits(int num_data_bytes, BitVector *bits) {
 472     final int capacity = num_data_bytes * 8;
 473     if (bits.size() > capacity) {
 474       Debug.LOG_ERROR("data bits cannot fit in the QR Code" + bits.size() + " > " + capacity);
 475       return false;
 476     }
 477     // Append termination bits.
 478     // See 8.4.8 of JISX0510:2004 (p.24) for details.
 479     for (int i = 0; i < 4 && bits.size() < capacity; ++i) {
 480       bits.AppendBit(0);
 481     }
 482     final int num_bits_in_last_byte = bits.size() % 8;
 483     // If the last byte isn't 8-bit aligned, we'll add padding bits.
 484     if (num_bits_in_last_byte > 0) {
 485       final int num_padding_bits = 8 - num_bits_in_last_byte;
 486       for (int i = 0; i < num_padding_bits; ++i) {
 487         bits.AppendBit(0);
 488       }
 489     }
 490     // Should be 8-bit aligned here.
 491     Debug.DCHECK_EQ(0, bits.size() % 8);
 492     // If we have more space, we'll fill the space with padding patterns
 493     // defined in 8.4.9 (p.24).
 494     final int num_padding_bytes = num_data_bytes - bits.num_bytes();
 495     for (int i = 0; i < num_padding_bytes; ++i) {
 496       if (i % 2 == 0) {
 497         bits.AppendBits(0xec, 8);
 498       } else {
 499         bits.AppendBits(0x11, 8);
 500       }
 501     }
 502     Debug.DCHECK_EQ(bits.size(), capacity);  // Should be same.
 503     return bits.size() == capacity;
 504   }
 505
 506   // Get number of data bytes and number of error correction bytes for
 507   // block id "block_id". Store the result in
 508   // "num_data_bytes_in_block", and "num_ec_bytes_in_block".
 509   // See table 12 in 8.5.1 of JISX0510:2004 (p.30)
 510   static void GetNumDataBytesAndNumECBytesForBlockID(
 511       int num_total_bytes,
 512       int num_data_bytes,
 513       int num_rs_blocks,
 514       int block_id,
 515       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 = num_data_bytes_in_group1;
 550       *num_ec_bytes_in_block = num_ec_bytes_in_group1;
 551     } else {
 552       *num_data_bytes_in_block = num_data_bytes_in_group2;
 553       *num_ec_bytes_in_block = num_ec_bytes_in_group2;
 554     }
 555   }
 556
 557   // Interleave "bits" with corresponding error correction bytes.  On
 558   // success, store the result in "result" and return true.  On error,
 559   // return false.
 560   // The interleave rule is complicated.  See 8.6 of JISX0510:2004
 561   // (p.37) for details.
 562   static boolean InterleaveWithECBytes(final BitVector &bits,
 563                                        int num_total_bytes,
 564                                        int num_data_bytes,
 565                                        int num_rc_blocks,
 566                                        BitVector *result) {
 567     // "bits" must have "num_data_bytes" bytes of data.
 568     Debug.DCHECK(bits.num_bytes() == num_data_bytes);
 569
 570     // Step 1.  Divide data bytes into blocks and generate error
 571     // correction bytes for them.  We'll store the divided data bytes
 572     // blocks and error correction bytes blocks into "blocks".
 573     typedef pair<StringPiece, String> BlockPair;
 574     int data_bytes_offset = 0;
 575     final String &encoded_bytes = bits.ToString();
 576     int max_num_data_bytes = 0;  // StringPiece's size is "int".
 577     size_t max_num_ec_bytes = 0;  // STL String's size is "size_t".
 578     vector<BlockPair> blocks;
 579     // Since, we know the number of reedsolmon blocks, we can initialize
 580     // the vector with the number.
 581     blocks.resize(num_rs_blocks);
 582
 583     for (int i = 0; i < num_rs_blocks; ++i) {
 584       int num_data_bytes_in_block, num_ec_bytes_in_block;
 585       GetNumDataBytesAndNumECBytesForBlockID(
 586           num_total_bytes, num_data_bytes, num_rs_blocks, i,
 587           &num_data_bytes_in_block, &num_ec_bytes_in_block);
 588       // We modify the objects in the vector instead of copying new
 589       // objects to the vector.  In particular, we want to avoid String
 590       // copies.
 591       StringPiece *data_bytes = &(blocks[i].first);
 592       String *ec_bytes = &(blocks[i].second);
 593
 594       data_bytes.set(encoded_bytes.data() + data_bytes_offset,
 595           num_data_bytes_in_block);
 596       GenerateECBytes(*data_bytes, num_ec_bytes_in_block, ec_bytes);
 597
 598       max_num_data_bytes = max(max_num_data_bytes, data_bytes.size());
 599       max_num_ec_bytes = max(max_num_ec_bytes, ec_bytes.size());
 600       data_bytes_offset += num_data_bytes_in_block;
 601     }
 602     Debug.DCHECK_EQ(num_data_bytes, data_bytes_offset);
 603
 604     // First, place data blocks.
 605     for (int i = 0; i < max_num_data_bytes; ++i) {
 606       for (int j = 0; j < blocks.size(); ++j) {
 607         final StringPiece &data_bytes = blocks[j].first;
 608         if (i < data_bytes.size()) {
 609           result.AppendBits(data_bytes[i], 8);
 610         }
 611       }
 612     }
 613     // Then, place error correction blocks.
 614     for (int i = 0; i < max_num_ec_bytes; ++i) {
 615       for (int j = 0; j < blocks.size(); ++j) {
 616         final String &ec_bytes = blocks[j].second;
 617         if (i < ec_bytes.size()) {
 618           result.AppendBits(ec_bytes[i], 8);
 619         }
 620       }
 621     }
 622     if (num_total_bytes == result.num_bytes()) {  // Should be same.
 623       return true;
 624     }
 625     Debug.LOG_ERROR("Interleaving error: " + num_total_bytes + " and " + result.num_bytes() +
 626         "differ.");
 627     return false;
 628   }
 629
 630   // Append mode info.  On success, store the result in "bits" and
 631   // return true.  On error, return false.
 632   static boolean AppendModeInfo(int mode, BitVector *bits) {
 633     final int code = QRCode.GetModeCode(mode);
 634     if (code == -1) {
 635       Debug.LOG_ERROR("Invalid mode: " + mode);
 636       return false;
 637     }
 638     bits.AppendBits(code, 4);
 639     return true;
 640   }
 641
 642
 643   // Append length info.  On success, store the result in "bits" and
 644   // return true.  On error, return false.
 645   static boolean AppendLengthInfo(int num_bytes, int version, int mode, BitVector *bits) {
 646     int num_letters = num_bytes;
 647     // In Kanji mode, a letter is represented in two bytes.
 648     if (mode == QRCode.MODE_KANJI) {
 649     Debug.DCHECK_EQ(0, num_letters % 2);
 650     num_letters /= 2;
 651   }
 652
 653     final int num_bits = QRCode.GetNumBitsForLength(version, mode);
 654     if (num_bits == -1) {
 655       Debug.LOG_ERROR("num_bits unset");
 656       return false;
 657     }
 658     if (num_letters > ((1 << num_bits) - 1)) {
 659       Debug.LOG_ERROR(num_letters + "is bigger than" + ((1 << num_bits) - 1));
 660       return false;
 661     }
 662     bits.AppendBits(num_letters, num_bits);
 663     return true;
 664   }
 665
 666   // Append "bytes" in "mode" mode (encoding) into "bits". On success, store the result in "bits"
 667   // and return true. On error, return false.
 668   static boolean AppendBytes(final StringPiece &bytes, int mode, BitVector *bits) {
 669     switch (mode) {
 670       case QRCode.MODE_NUMERIC:
 671       return AppendNumericBytes(bytes, bits);
 672       case QRCode.MODE_ALPHANUMERIC:
 673       return AppendAlphanumericBytes(bytes, bits);
 674       case QRCode.MODE_8BIT_BYTE:
 675       return Append8BitBytes(bytes, bits);
 676       case QRCode.MODE_KANJI:
 677       return AppendKanjiBytes(bytes, bits);
 678       default:
 679         break;
 680     }
 681     Debug.LOG_ERROR("Invalid mode: " + mode);
 682     return false;
 683   }
 684
 685   // Append "bytes" to "bits" using QRCode.MODE_NUMERIC mode. On success, store the result in "bits"
 686   // and return true. On error, return false.
 687   static boolean AppendNumericBytes(final StringPiece &bytes, BitVector *bits) {
 688     // Validate all the bytes first.
 689     for (int i = 0; i < bytes.size(); ++i) {
 690       if (!isdigit(bytes[i])) {
 691         return false;
 692       }
 693     }
 694     for (int i = 0; i < bytes.size();) {
 695       final int num1 = bytes[i] - '0';
 696       if (i + 2 < bytes.size()) {
 697         // Encode three numeric letters in ten bits.
 698         final int num2 = bytes[i + 1] - '0';
 699         final int num3 = bytes[i + 2] - '0';
 700         bits.AppendBits(num1 * 100 + num2 * 10 + num3, 10);
 701         i += 3;
 702       } else if (i + 1 < bytes.size()) {
 703         // Encode two numeric letters in seven bits.
 704         final int num2 = bytes[i + 1] - '0';
 705         bits.AppendBits(num1 * 10 + num2, 7);
 706         i += 2;
 707       } else {
 708         // Encode one numeric letter in four bits.
 709         bits.AppendBits(num1, 4);
 710         ++i;
 711       }
 712     }
 713     return true;
 714   }
 715
 716   // Append "bytes" to "bits" using QRCode.MODE_ALPHANUMERIC mode.
 717   // On success, store the result in "bits" and return true.  On error,
 718   // return false.
 719   static boolean AppendAlphanumericBytes(final StringPiece &bytes,
 720                                          BitVector *bits) {
 721     for (int i = 0; i < bytes.size();) {
 722       final int code1 = GetAlphanumericCode(bytes[i]);
 723       if (code1 == -1) {
 724         return false;
 725       }
 726       if (i + 1 < bytes.size()) {
 727         final int code2 = GetAlphanumericCode(bytes[i + 1]);
 728         if (code2 == -1) {
 729           return false;
 730         }
 731         // Encode two alphanumeric letters in 11 bits.
 732         bits.AppendBits(code1 * 45 + code2, 11);
 733         i += 2;
 734       } else {
 735         // Encode one alphanumeric letter in six bits.
 736         bits.AppendBits(code1, 6);
 737         ++i;
 738       }
 739     }
 740     return true;
 741   }
 742
 743   // Append "bytes" to "bits" using QRCode.MODE_8BIT_BYTE mode.
 744   // On success, store the result in "bits" and return true.  On error,
 745   // return false.
 746   static boolean Append8BitBytes(final StringPiece &bytes, BitVector *bits) {
 747     for (int i = 0; i < bytes.size(); ++i) {
 748       bits.AppendBits(bytes[i], 8);
 749     }
 750     return true;
 751   }
 752
 753   // Append "bytes" to "bits" using QRCode.MODE_KANJI mode.
 754   // On success, store the result in "bits" and return true.  On error,
 755   // return false.
 756   // See 8.4.5 of JISX0510:2004 (p.21) for how to encode Kanji bytes.
 757   static boolean AppendKanjiBytes(final StringPiece &bytes, BitVector *bits) {
 758     if (bytes.size() % 2 != 0) {
 759       Debug.LOG_ERROR("Invalid byte sequence: " + bytes);
 760       return false;
 761     }
 762     for (int i = 0; i < bytes.size(); i += 2) {
 763       Debug.DCHECK(IsValidKanji(bytes[i], bytes[i + 1]));
 764       final int code = (static_cast<int>(bytes[i]) << 8 | bytes[i + 1]);
 765       int subtracted = -1;
 766       if (code >= 0x8140 && code <= 0x9ffc) {
 767         subtracted = code - 0x8140;
 768       } else if (code >= 0xe040 && code <= 0xebbf) {
 769         subtracted = code - 0xc140;
 770       }
 771       if (subtracted == -1) {
 772         Debug.LOG_ERROR("Invalid byte sequence: " + bytes);
 773         return false;
 774       }
 775       final int encoded = ((subtracted >> 8) * 0xc0) + (subtracted & 0xff);
 776       bits.AppendBits(encoded, 13);
 777     }
 778     return true;
 779   }
 780
 781   // Only call once
 782   static {
 783     InitECPolynomials();
 784   }
 785
 786   // Initialize "g_ec_polynomials" with numbers in kECPolynomials.
 787   private static void InitECPolynomials() {
 788     final GaloisField &field = GaloisField.GetField(kFieldSize);
 789     for (int i = 0; i < arraysize(kECPolynomials); ++i) {
 790       final ECPolyInfo& ec_poly_info = kECPolynomials[i];
 791       final int ec_length = ec_poly_info.ec_length;
 792       vector<GF_Element> *coeffs = new vector<GF_Element>;
 793       // The number of coefficients is one more than "ec_length".
 794       // That's why the termination condition is <= instead of <.
 795       for (int j = 0; j <= ec_length; ++j) {
 796         // We need exp'ed numbers for later use.
 797         final int coeff = field.Exp(ec_poly_info.coeffs[j]);
 798         coeffs.push_back(coeff);
 799       }
 800       // Reverse the coefficients since the numbers in kECPolynomials
 801       // are ordered in reverse order to the order GF_Poly expects.
 802       reverse(coeffs.begin(), coeffs.end());
 803
 804       GF_Poly *ec_poly = new GF_Poly(coeffs, GaloisField.GetField(kFieldSize));
 805       g_ec_polynomials[ec_length] = ec_poly;
 806     }
 807   }
 808
 809   // Get error correction polynomials.  The polynomials are
 810   // defined in Appendix A of JISX0510 2004 (p. 59). In the appendix,
 811   // they use exponential notations for the polynomials.  We need to
 812   // apply GaloisField.Log() to all coefficients generated by the
 813   // function to compare numbers with the ones in the appendix.
 814   //
 815   // Example:
 816   // - Input: 17
 817   // - Output (in reverse order)
 818   //   {119,66,83,120,119,22,197,83,249,41,143,134,85,53,125,99,79}
 819   // - Log()'ed output (in reverse order)
 820   //   {0,43,139,206,78,43,239,123,206,214,147,24,99,150,39,243,163,136}
 821   static final GF_Poly &GetECPoly(int ec_length) {
 822     Debug.DCHECK_GE(kMaxNumECBytes, ec_length);
 823     final GF_Poly *ec_poly = g_ec_polynomials[ec_length];
 824     Debug.DCHECK(ec_poly);
 825     return *ec_poly;
 826   }
 827
 828   // Generate error correction bytes of "ec_length".
 829   //
 830   // Example:
 831   // - Input:  {32,65,205,69,41,220,46,128,236}, ec_length = 17
 832   // - Output: {42,159,74,221,244,169,239,150,138,70,237,85,224,96,74,219,61}
 833   static void GenerateECBytes(final StringPiece &data_bytes,
 834                               int ec_length,
 835                               String *ec_bytes) {
 836     // First, fill the vector with "ec_length" copies of 0.
 837     // They are low-order zero coefficients.
 838     vector<GF_Element> *coeffs = new vector<GF_Element>(ec_length, 0);
 839     // Then copy data_bytes backward.
 840     copy(data_bytes.rbegin(), data_bytes.rend(), back_inserter(*coeffs));
 841     // Now we have data polynomial.
 842     GF_Poly data_poly(coeffs, GaloisField.GetField(kFieldSize));
 843
 844     // Get error correction polynomial.
 845     final GF_Poly &ec_poly = GetECPoly(ec_length);
 846     pair<GF_Poly*, GF_Poly*> divrem = GF_Poly.DivRem(data_poly, ec_poly);
 847
 848     // Basically, the coefficients in the remainder polynomial are the
 849     // error correction bytes.
 850     GF_Poly *remainder = divrem.second;
 851     ec_bytes.reserve(ec_length);
 852     // However, high-order zero cofficients in the remainder polynomial
 853     // are ommited.  We should add zero by ourselvs.
 854     final int num_pruned_zero_coeffs = ec_length - (remainder.degree() + 1);
 855     for (int i = 0; i < num_pruned_zero_coeffs; ++i) {
 856       ec_bytes.push_back(0);
 857     }
 858     // Copy the remainder numbers to "ec_bytes".
 859     for (int i = remainder.degree(); i >= 0; --i) {
 860       ec_bytes.push_back(remainder.coeff(i));
 861     }
 862     Debug.DCHECK_EQ(ec_length, ec_bytes.size());
 863
 864     // Deallocate quotient and reminder.
 865     delete divrem.first;
 866     delete divrem.second;
 867   }
 868
 869   // Check if "byte1" and "byte2" can compose a valid Kanji letter
 870   // (2-byte Shift_JIS letter).
 871   // The numbers are from http://ja.wikipedia.org/wiki/Shift_JIS.
 872   static boolean IsValidKanji(final char byte1, final char byte2) {
 873     return (byte2 != 0x7f &&
 874         ((byte1 >= 0x81 && byte1 <= 0x9f &&
 875             byte2 >= 0x40 && byte2 <= 0xfc) ||
 876             ((byte1 >= 0xe0 && byte1 <= 0xfc &&
 877                 byte2 >= 0x40 && byte2 <= 0xfc))));
 878   }
 879
 880   // Check if "bytes" is a valid Kanji sequence.
 881   static boolean IsValidKanjiSequence(final StringPiece &bytes) {
 882     if (bytes.size() % 2 != 0) {
 883       return false;
 884     }
 885     int i = 0;
 886     for (; i < bytes.size(); i += 2) {
 887       if (!IsValidKanji(bytes[i], bytes[i + 1])) {
 888         break;
 889       }
 890     }
 891     return i == bytes.size();  // Consumed all bytes?
 892   }
 893
 894 }