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