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