2 * Copyright 2008 ZXing authors
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 package com.google.zxing.qrcode.encoder;
19 import com.google.zxing.common.ByteMatrix;
20 import com.google.zxing.common.reedsolomon.GF256;
21 import com.google.zxing.common.reedsolomon.ReedSolomonEncoder;
23 import java.util.Vector;
26 * @author satorux@google.com (Satoru Takabayashi) - creator
27 * @author dswitkin@google.com (Daniel Switkin) - ported from C++
29 public final class Encoder {
31 // The original table is defined in the table 5 of JISX0510:2004 (p.19).
32 private 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
41 private static final class RSBlockInfo {
46 public RSBlockInfo(int num_bytes, int[][] block_info) {
47 this.num_bytes = num_bytes;
48 this.block_info = block_info;
53 // The table is from table 12 of JISX0510:2004 (p. 30). The "block_info" parts are ordered by
54 // L, M, Q, H. Within each block_info, the 0th element is num_ec_bytes, and the 1st element is
55 // num_rs_blocks. The table was doublechecked by komatsu.
56 private static final RSBlockInfo kRSBlockTable[] = {
57 new RSBlockInfo( 26, new int[][]{ { 7, 1}, { 10, 1}, { 13, 1}, { 17, 1}}), // Version 1
58 new RSBlockInfo( 44, new int[][]{ { 10, 1}, { 16, 1}, { 22, 1}, { 28, 1}}), // Version 2
59 new RSBlockInfo( 70, new int[][]{ { 15, 1}, { 26, 1}, { 36, 2}, { 44, 2}}), // Version 3
60 new RSBlockInfo( 100, new int[][]{ { 20, 1}, { 36, 2}, { 52, 2}, { 64, 4}}), // Version 4
61 new RSBlockInfo( 134, new int[][]{ { 26, 1}, { 48, 2}, { 72, 4}, { 88, 4}}), // Version 5
62 new RSBlockInfo( 172, new int[][]{ { 36, 2}, { 64, 4}, { 96, 4}, { 112, 4}}), // Version 6
63 new RSBlockInfo( 196, new int[][]{ { 40, 2}, { 72, 4}, { 108, 6}, { 130, 5}}), // Version 7
64 new RSBlockInfo( 242, new int[][]{ { 48, 2}, { 88, 4}, { 132, 6}, { 156, 6}}), // Version 8
65 new RSBlockInfo( 292, new int[][]{ { 60, 2}, { 110, 5}, { 160, 8}, { 192, 8}}), // Version 9
66 new RSBlockInfo( 346, new int[][]{ { 72, 4}, { 130, 5}, { 192, 8}, { 224, 8}}), // Version 10
67 new RSBlockInfo( 404, new int[][]{ { 80, 4}, { 150, 5}, { 224, 8}, { 264, 11}}), // Version 11
68 new RSBlockInfo( 466, new int[][]{ { 96, 4}, { 176, 8}, { 260, 10}, { 308, 11}}), // Version 12
69 new RSBlockInfo( 532, new int[][]{ {104, 4}, { 198, 9}, { 288, 12}, { 352, 16}}), // Version 13
70 new RSBlockInfo( 581, new int[][]{ {120, 4}, { 216, 9}, { 320, 16}, { 384, 16}}), // Version 14
71 new RSBlockInfo( 655, new int[][]{ {132, 6}, { 240, 10}, { 360, 12}, { 432, 18}}), // Version 15
72 new RSBlockInfo( 733, new int[][]{ {144, 6}, { 280, 10}, { 408, 17}, { 480, 16}}), // Version 16
73 new RSBlockInfo( 815, new int[][]{ {168, 6}, { 308, 11}, { 448, 16}, { 532, 19}}), // Version 17
74 new RSBlockInfo( 901, new int[][]{ {180, 6}, { 338, 13}, { 504, 18}, { 588, 21}}), // Version 18
75 new RSBlockInfo( 991, new int[][]{ {196, 7}, { 364, 14}, { 546, 21}, { 650, 25}}), // Version 19
76 new RSBlockInfo(1085, new int[][]{ {224, 8}, { 416, 16}, { 600, 20}, { 700, 25}}), // Version 20
77 new RSBlockInfo(1156, new int[][]{ {224, 8}, { 442, 17}, { 644, 23}, { 750, 25}}), // Version 21
78 new RSBlockInfo(1258, new int[][]{ {252, 9}, { 476, 17}, { 690, 23}, { 816, 34}}), // Version 22
79 new RSBlockInfo(1364, new int[][]{ {270, 9}, { 504, 18}, { 750, 25}, { 900, 30}}), // Version 23
80 new RSBlockInfo(1474, new int[][]{ {300, 10}, { 560, 20}, { 810, 27}, { 960, 32}}), // Version 24
81 new RSBlockInfo(1588, new int[][]{ {312, 12}, { 588, 21}, { 870, 29}, {1050, 35}}), // Version 25
82 new RSBlockInfo(1706, new int[][]{ {336, 12}, { 644, 23}, { 952, 34}, {1110, 37}}), // Version 26
83 new RSBlockInfo(1828, new int[][]{ {360, 12}, { 700, 25}, {1020, 34}, {1200, 40}}), // Version 27
84 new RSBlockInfo(1921, new int[][]{ {390, 13}, { 728, 26}, {1050, 35}, {1260, 42}}), // Version 28
85 new RSBlockInfo(2051, new int[][]{ {420, 14}, { 784, 28}, {1140, 38}, {1350, 45}}), // Version 29
86 new RSBlockInfo(2185, new int[][]{ {450, 15}, { 812, 29}, {1200, 40}, {1440, 48}}), // Version 30
87 new RSBlockInfo(2323, new int[][]{ {480, 16}, { 868, 31}, {1290, 43}, {1530, 51}}), // Version 31
88 new RSBlockInfo(2465, new int[][]{ {510, 17}, { 924, 33}, {1350, 45}, {1620, 54}}), // Version 32
89 new RSBlockInfo(2611, new int[][]{ {540, 18}, { 980, 35}, {1440, 48}, {1710, 57}}), // Version 33
90 new RSBlockInfo(2761, new int[][]{ {570, 19}, {1036, 37}, {1530, 51}, {1800, 60}}), // Version 34
91 new RSBlockInfo(2876, new int[][]{ {570, 19}, {1064, 38}, {1590, 53}, {1890, 63}}), // Version 35
92 new RSBlockInfo(3034, new int[][]{ {600, 20}, {1120, 40}, {1680, 56}, {1980, 66}}), // Version 36
93 new RSBlockInfo(3196, new int[][]{ {630, 21}, {1204, 43}, {1770, 59}, {2100, 70}}), // Version 37
94 new RSBlockInfo(3362, new int[][]{ {660, 22}, {1260, 45}, {1860, 62}, {2220, 74}}), // Version 38
95 new RSBlockInfo(3532, new int[][]{ {720, 24}, {1316, 47}, {1950, 65}, {2310, 77}}), // Version 39
96 new RSBlockInfo(3706, new int[][]{ {750, 25}, {1372, 49}, {2040, 68}, {2430, 81}}), // Version 40
99 private static final int kMaxNumECBytes = 68; // See the table in Appendix A.
101 private static final class ECPolyInfo {
106 public ECPolyInfo(int ec_length, int[] coefficients) {
107 this.ec_length = ec_length;
108 this.coeffs = coefficients;
113 // The numbers were generated using the logic found in http://www.d-project.com/qrcode/. We use
114 // generated numbers instead of the logic itself (don't want to copy it). The numbers are supposed
115 // to be identical to the ones in the table in Appendix A of JISX0510:2004 (p. 30). However, there
116 // are some cases the spec seems to be wrong.
117 private static final ECPolyInfo kECPolynomials[] = {
119 new int[]{ 0, 87, 229, 146, 149, 238, 102, 21 }),
120 // The spec lacks the coefficient for x^5 (a^46 x^5). Tested a QR code of Version 1-M (uses 10
121 // error correction bytes) with a cell phone and it worked.
123 new int[]{ 0, 251, 67, 46, 61, 118, 70, 64, 94, 32, 45 }),
125 new int[]{ 0, 74, 152, 176, 100, 86, 100, 106, 104, 130, 218, 206,
128 new int[]{ 0, 8, 183, 61, 91, 202, 37, 51, 58, 58, 237, 140,
131 new int[]{ 0, 120, 104, 107, 109, 102, 161, 76, 3, 91, 191, 147,
132 169, 182, 194, 225, 120 }),
134 new int[]{ 0, 43, 139, 206, 78, 43, 239, 123, 206, 214, 147, 24,
135 99, 150, 39, 243, 163, 136 }),
137 new int[]{ 0, 215, 234, 158, 94, 184, 97, 118, 170, 79, 187, 152,
138 148, 252, 179, 5, 98, 96, 153 }),
140 new int[]{ 0, 17, 60, 79, 50, 61, 163, 26, 187, 202, 180, 221,
141 225, 83, 239, 156, 164, 212, 212, 188, 190 }),
143 new int[]{ 0, 210, 171, 247, 242, 93, 230, 14, 109, 221, 53, 200,
144 74, 8, 172, 98, 80, 219, 134, 160, 105, 165, 231 }),
146 new int[]{ 0, 229, 121, 135, 48, 211, 117, 251, 126, 159, 180, 169,
147 152, 192, 226, 228, 218, 111, 0, 117, 232, 87, 96, 227,
150 new int[]{ 0, 173, 125, 158, 2, 103, 182, 118, 17, 145, 201, 111,
151 28, 165, 53, 161, 21, 245, 142, 13, 102, 48, 227, 153,
154 new int[]{ 0, 168, 223, 200, 104, 224, 234, 108, 180, 110, 190, 195,
155 147, 205, 27, 232, 201, 21, 43, 245, 87, 42, 195, 212,
156 119, 242, 37, 9, 123 }),
158 new int[]{ 0, 41, 173, 145, 152, 216, 31, 179, 182, 50, 48, 110,
159 86, 239, 96, 222, 125, 42, 173, 226, 193, 224, 130, 156,
160 37, 251, 216, 238, 40, 192, 180 }),
161 // In the spec, the coefficient for x^10 is a^60 but we use the generated number a^69 instead
162 // (probably it's typo in the spec).
164 // Anyway, there seems to be no way that error correction bytes bigger than 30 can be used in RS
165 // blocks, according to table 12. It's weird why the spec has numbers for error correction bytes
166 // of 32 and bigger in this table here.
168 new int[]{ 0, 10, 6, 106, 190, 249, 167, 4, 67, 209, 138, 138,
169 32, 242, 123, 89, 27, 120, 185, 80, 156, 38, 69, 171,
170 60, 28, 222, 80, 52, 254, 185, 220, 241 }),
172 new int[]{ 0, 111, 77, 146, 94, 26, 21, 108, 19, 105, 94, 113,
173 193, 86, 140, 163, 125, 58, 158, 229, 239, 218, 103, 56,
174 70, 114, 61, 183, 129, 167, 13, 98, 62, 129, 51 }),
176 new int[]{ 0, 200, 183, 98, 16, 172, 31, 246, 234, 60, 152, 115,
177 0, 167, 152, 113, 248, 238, 107, 18, 63, 218, 37, 87,
178 210, 105, 177, 120, 74, 121, 196, 117, 251, 113, 233, 30,
180 // The spec doesn't have a row for 38 but just in case.
182 new int[]{ 0, 159, 34, 38, 228, 230, 59, 243, 95, 49, 218, 176,
183 164, 20, 65, 45, 111, 39, 81, 49, 118, 113, 222, 193,
184 250, 242, 168, 217, 41, 164, 247, 177, 30, 238, 18, 120,
187 new int[]{ 0, 59, 116, 79, 161, 252, 98, 128, 205, 128, 161, 247,
188 57, 163, 56, 235, 106, 53, 26, 187, 174, 226, 104, 170,
189 7, 175, 35, 181, 114, 88, 41, 47, 163, 125, 134, 72,
190 20, 232, 53, 35, 15 }),
192 new int[]{ 0, 250, 103, 221, 230, 25, 18, 137, 231, 0, 3, 58,
193 242, 221, 191, 110, 84, 230, 8, 188, 106, 96, 147, 15,
194 131, 139, 34, 101, 223, 39, 101, 213, 199, 237, 254, 201,
195 123, 171, 162, 194, 117, 50, 96 }),
197 new int[]{ 0, 190, 7, 61, 121, 71, 246, 69, 55, 168, 188, 89,
198 243, 191, 25, 72, 123, 9, 145, 14, 247, 1, 238, 44,
199 78, 143, 62, 224, 126, 118, 114, 68, 163, 52, 194, 217,
200 147, 204, 169, 37, 130, 113, 102, 73, 181 }),
202 new int[]{ 0, 112, 94, 88, 112, 253, 224, 202, 115, 187, 99, 89,
203 5, 54, 113, 129, 44, 58, 16, 135, 216, 169, 211, 36,
204 1, 4, 96, 60, 241, 73, 104, 234, 8, 249, 245, 119,
205 174, 52, 25, 157, 224, 43, 202, 223, 19, 82, 15 }),
207 new int[]{ 0, 228, 25, 196, 130, 211, 146, 60, 24, 251, 90, 39,
208 102, 240, 61, 178, 63, 46, 123, 115, 18, 221, 111, 135,
209 160, 182, 205, 107, 206, 95, 150, 120, 184, 91, 21, 247,
210 156, 140, 238, 191, 11, 94, 227, 84, 50, 163, 39, 34,
213 new int[]{ 0, 232, 125, 157, 161, 164, 9, 118, 46, 209, 99, 203,
214 193, 35, 3, 209, 111, 195, 242, 203, 225, 46, 13, 32,
215 160, 126, 209, 130, 160, 242, 215, 242, 75, 77, 42, 189,
216 32, 113, 65, 124, 69, 228, 114, 235, 175, 124, 170, 215,
219 new int[]{ 0, 116, 50, 86, 186, 50, 220, 251, 89, 192, 46, 86,
220 127, 124, 19, 184, 233, 151, 215, 22, 14, 59, 145, 37,
221 242, 203, 134, 254, 89, 190, 94, 59, 65, 124, 113, 100,
222 233, 235, 121, 22, 76, 86, 97, 39, 242, 200, 220, 101,
223 33, 239, 254, 116, 51 }),
225 new int[]{ 0, 183, 26, 201, 87, 210, 221, 113, 21, 46, 65, 45,
226 50, 238, 184, 249, 225, 102, 58, 209, 218, 109, 165, 26,
227 95, 184, 192, 52, 245, 35, 254, 238, 175, 172, 79, 123,
228 25, 122, 43, 120, 108, 215, 80, 128, 201, 235, 8, 153,
229 59, 101, 31, 198, 76, 31, 156 }),
231 new int[]{ 0, 106, 120, 107, 157, 164, 216, 112, 116, 2, 91, 248,
232 163, 36, 201, 202, 229, 6, 144, 254, 155, 135, 208, 170,
233 209, 12, 139, 127, 142, 182, 249, 177, 174, 190, 28, 10,
234 85, 239, 184, 101, 124, 152, 206, 96, 23, 163, 61, 27,
235 196, 247, 151, 154, 202, 207, 20, 61, 10 }),
237 new int[]{ 0, 82, 116, 26, 247, 66, 27, 62, 107, 252, 182, 200,
238 185, 235, 55, 251, 242, 210, 144, 154, 237, 176, 141, 192,
239 248, 152, 249, 206, 85, 253, 142, 65, 165, 125, 23, 24,
240 30, 122, 240, 214, 6, 129, 218, 29, 145, 127, 134, 206,
241 245, 117, 29, 41, 63, 159, 142, 233, 125, 148, 123 }),
243 new int[]{ 0, 107, 140, 26, 12, 9, 141, 243, 197, 226, 197, 219,
244 45, 211, 101, 219, 120, 28, 181, 127, 6, 100, 247, 2,
245 205, 198, 57, 115, 219, 101, 109, 160, 82, 37, 38, 238,
246 49, 160, 209, 121, 86, 11, 124, 30, 181, 84, 25, 194,
247 87, 65, 102, 190, 220, 70, 27, 209, 16, 89, 7, 33,
249 // The spec lacks the coefficient for x^5 (a^127 x^5). Anyway the number will not be used. See
250 // the comment for 32.
252 new int[]{ 0, 65, 202, 113, 98, 71, 223, 248, 118, 214, 94, 0,
253 122, 37, 23, 2, 228, 58, 121, 7, 105, 135, 78, 243,
254 118, 70, 76, 223, 89, 72, 50, 70, 111, 194, 17, 212,
255 126, 181, 35, 221, 117, 235, 11, 229, 149, 147, 123, 213,
256 40, 115, 6, 200, 100, 26, 246, 182, 218, 127, 215, 36,
259 new int[]{ 0, 45, 51, 175, 9, 7, 158, 159, 49, 68, 119, 92,
260 123, 177, 204, 187, 254, 200, 78, 141, 149, 119, 26, 127,
261 53, 160, 93, 199, 212, 29, 24, 145, 156, 208, 150, 218,
262 209, 4, 216, 91, 47, 184, 146, 47, 140, 195, 195, 125,
263 242, 238, 63, 99, 108, 140, 230, 242, 31, 204, 11, 178,
264 243, 217, 156, 213, 231 }),
266 new int[]{ 0, 5, 118, 222, 180, 136, 136, 162, 51, 46, 117, 13,
267 215, 81, 17, 139, 247, 197, 171, 95, 173, 65, 137, 178,
268 68, 111, 95, 101, 41, 72, 214, 169, 197, 95, 7, 44,
269 154, 77, 111, 236, 40, 121, 143, 63, 87, 80, 253, 240,
270 126, 217, 77, 34, 232, 106, 50, 168, 82, 76, 146, 67,
271 106, 171, 25, 132, 93, 45, 105 }),
273 new int[]{ 0, 247, 159, 223, 33, 224, 93, 77, 70, 90, 160, 32,
274 254, 43, 150, 84, 101, 190, 205, 133, 52, 60, 202, 165,
275 220, 203, 151, 93, 84, 15, 84, 253, 173, 160, 89, 227,
276 52, 199, 97, 95, 231, 52, 177, 41, 125, 137, 241, 166,
277 225, 118, 2, 54, 32, 82, 215, 175, 198, 43, 238, 235,
278 27, 101, 184, 127, 3, 5, 8, 163, 238 }),
281 private static final class BlockPair {
283 private ByteArray dataBytes;
284 private ByteArray errorCorrectionBytes;
286 public BlockPair(ByteArray data, ByteArray errorCorrection) {
288 errorCorrectionBytes = errorCorrection;
291 public ByteArray getDataBytes() {
295 public ByteArray getErrorCorrectionBytes() {
296 return errorCorrectionBytes;
301 // Encode "bytes" with the error correction level "ec_level". The encoding mode will be chosen
302 // internally by ChooseMode(). On success, store the result in "qr_code" and return true. On
303 // error, return false. We recommend you to use QRCode.EC_LEVEL_L (the lowest level) for
304 // "ec_level" since our primary use is to show QR code on desktop screens. We don't need very
305 // strong error correction for this purpose.
307 // Note that there is no way to encode bytes in MODE_KANJI. We might want to add EncodeWithMode()
308 // with which clients can specify the encoding mode. For now, we don't need the functionality.
309 public static boolean Encode(final ByteArray bytes, int ec_level, QRCode qr_code) {
310 // Step 1: Choose the mode (encoding).
311 final int mode = ChooseMode(bytes);
313 // Step 2: Append "bytes" into "data_bits" in appropriate encoding.
314 BitVector data_bits = new BitVector();
315 if (!AppendBytes(bytes, mode, data_bits)) {
318 // Step 3: Initialize QR code that can contain "data_bits".
319 final int num_input_bytes = data_bits.num_bytes();
320 if (!InitQRCode(num_input_bytes, ec_level, mode, qr_code)) {
324 // Step 4: Build another bit vector that contains header and data.
325 BitVector header_and_data_bits = new BitVector();
326 if (!AppendModeInfo(qr_code.mode(), header_and_data_bits)) {
329 if (!AppendLengthInfo(bytes.size(), qr_code.version(), qr_code.mode(), header_and_data_bits)) {
332 header_and_data_bits.AppendBitVector(data_bits);
334 // Step 5: Terminate the bits properly.
335 if (!TerminateBits(qr_code.num_data_bytes(), header_and_data_bits)) {
339 // Step 6: Interleave data bits with error correction code.
340 BitVector final_bits = new BitVector();
341 InterleaveWithECBytes(header_and_data_bits, qr_code.num_total_bytes(), qr_code.num_data_bytes(),
342 qr_code.num_rs_blocks(), final_bits);
344 // Step 7: Choose the mask pattern and set to "qr_code".
345 ByteMatrix matrix = new ByteMatrix(qr_code.matrix_width(), qr_code.matrix_width());
346 qr_code.set_mask_pattern(ChooseMaskPattern(final_bits, qr_code.ec_level(), qr_code.version(),
348 if (qr_code.mask_pattern() == -1) {
349 // There was an error.
353 // Step 8. Build the matrix and set it to "qr_code".
354 MatrixUtil.BuildMatrix(final_bits, qr_code.ec_level(), qr_code.version(),
355 qr_code.mask_pattern(), matrix);
356 qr_code.set_matrix(matrix);
357 // Step 9. Make sure we have a valid QR Code.
358 if (!qr_code.IsValid()) {
359 Debug.LOG_ERROR("Invalid QR code: " + qr_code.toString());
365 // Return the code point of the table used in alphanumeric mode. Return -1 if there is no
366 // corresponding code in the table.
367 static int GetAlphanumericCode(int code) {
368 if (code < kAlphanumericTable.length) {
369 return kAlphanumericTable[code];
374 // Choose the best mode by examining the content of "bytes". The function is guaranteed to return
377 // Note that this function does not return MODE_KANJI, as we cannot distinguish Shift_JIS from
378 // other encodings such as ISO-8859-1, from data bytes alone. For example "\xE0\xE0" can be
379 // interpreted as one character in Shift_JIS, but also two characters in ISO-8859-1.
381 // JAVAPORT: This MODE_KANJI limitation sounds like a problem for us.
382 public static int ChooseMode(final ByteArray bytes) {
383 boolean has_numeric = false;
384 boolean has_alphanumeric = false;
385 boolean has_other = false;
386 for (int i = 0; i < bytes.size(); ++i) {
387 final int oneByte = bytes.at(i);
388 if (oneByte >= '0' && oneByte <= '9') {
390 } else if (GetAlphanumericCode(oneByte) != -1) {
391 has_alphanumeric = true;
397 return QRCode.MODE_8BIT_BYTE;
398 } else if (has_alphanumeric) {
399 return QRCode.MODE_ALPHANUMERIC;
400 } else if (has_numeric) {
401 return QRCode.MODE_NUMERIC;
403 // "bytes" must be empty to reach here.
404 Debug.DCHECK(bytes.empty());
405 return QRCode.MODE_8BIT_BYTE;
408 private static int ChooseMaskPattern(final BitVector bits, int ec_level, int version,
410 if (!QRCode.IsValidMatrixWidth(matrix.width())) {
411 Debug.LOG_ERROR("Invalid matrix width: " + matrix.width());
415 int min_penalty = Integer.MAX_VALUE; // Lower penalty is better.
416 int best_mask_pattern = -1;
417 // We try all mask patterns to choose the best one.
418 for (int i = 0; i < QRCode.kNumMaskPatterns; ++i) {
419 final int mask_pattern = i;
420 if (!MatrixUtil.BuildMatrix(bits, ec_level, version,
421 mask_pattern, matrix)) {
424 final int penalty = MaskUtil.CalculateMaskPenalty(matrix);
425 Debug.LOG_INFO("mask_pattern: " + mask_pattern + ", " + "penalty: " + penalty);
426 if (penalty < min_penalty) {
427 min_penalty = penalty;
428 best_mask_pattern = mask_pattern;
431 return best_mask_pattern;
434 // Initialize "qr_code" according to "num_input_bytes", "ec_level", and "mode". On success, modify
435 // "qr_code" and return true. On error, return false.
436 private static boolean InitQRCode(int num_input_bytes, int ec_level, int mode, QRCode qr_code) {
437 qr_code.set_ec_level(ec_level);
438 qr_code.set_mode(mode);
440 if (!QRCode.IsValidECLevel(ec_level)) {
441 Debug.LOG_ERROR("Invalid EC level: " + ec_level);
445 // In the following comments, we use numbers of Version 7-H.
446 for (int i = 0; i < kRSBlockTable.length; ++i) {
447 final RSBlockInfo row = kRSBlockTable[i];
449 final int num_bytes = row.num_bytes;
450 // num_ec_bytes = 130
451 final int num_ec_bytes = row.block_info[ec_level][0];
453 final int num_rs_blocks = row.block_info[ec_level][1];
454 // num_data_bytes = 196 - 130 = 66
455 final int num_data_bytes = num_bytes - num_ec_bytes;
456 // We want to choose the smallest version which can contain data of "num_input_bytes" + some
457 // extra bits for the header (mode info and length info). The header can be three bytes
458 // (precisely 4 + 16 bits) at most. Hence we do +3 here.
459 if (num_data_bytes >= num_input_bytes + 3) {
460 // Yay, we found the proper rs block info!
461 qr_code.set_version(i + 1);
462 qr_code.set_num_total_bytes(num_bytes);
463 qr_code.set_num_data_bytes(num_data_bytes);
464 qr_code.set_num_rs_blocks(num_rs_blocks);
465 // num_ec_bytes = 196 - 66 = 130
466 qr_code.set_num_ec_bytes(num_bytes - num_data_bytes);
467 // num_matrix_width = 21 + 6 * 4 = 45
468 qr_code.set_matrix_width(21 + i * 4);
472 Debug.LOG_ERROR("Cannot find proper rs block info (input data too big?)");
476 // Terminate bits as described in 8.4.8 and 8.4.9 of JISX0510:2004 (p.24).
477 static boolean TerminateBits(int num_data_bytes, BitVector bits) {
478 final int capacity = num_data_bytes * 8;
479 if (bits.size() > capacity) {
480 Debug.LOG_ERROR("data bits cannot fit in the QR Code" + bits.size() + " > " + capacity);
483 // Append termination bits. See 8.4.8 of JISX0510:2004 (p.24) for details.
484 for (int i = 0; i < 4 && bits.size() < capacity; ++i) {
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) {
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 defined in 8.4.9 (p.24).
498 final int num_padding_bytes = num_data_bytes - bits.num_bytes();
499 for (int i = 0; i < num_padding_bytes; ++i) {
501 bits.AppendBits(0xec, 8);
503 bits.AppendBits(0x11, 8);
506 Debug.DCHECK_EQ(bits.size(), capacity); // Should be same.
507 return bits.size() == capacity;
510 // Get number of data bytes and number of error correction bytes for block id "block_id". Store
511 // the result in "num_data_bytes_in_block", and "num_ec_bytes_in_block". See table 12 in 8.5.1 of
512 // JISX0510:2004 (p.30)
513 static void GetNumDataBytesAndNumECBytesForBlockID(int num_total_bytes, int num_data_bytes,
514 int num_rs_blocks, int block_id, int[] num_data_bytes_in_block,
515 int[] num_ec_bytes_in_block) {
516 Debug.DCHECK_LT(block_id, num_rs_blocks);
517 // num_rs_blocks_in_group2 = 196 % 5 = 1
518 final int num_rs_blocks_in_group2 = num_total_bytes % num_rs_blocks;
519 // num_rs_blocks_in_group1 = 5 - 1 = 4
520 final int num_rs_blocks_in_group1 = num_rs_blocks - num_rs_blocks_in_group2;
521 // num_total_bytes_in_group1 = 196 / 5 = 39
522 final int num_total_bytes_in_group1 = num_total_bytes / num_rs_blocks;
523 // num_total_bytes_in_group2 = 39 + 1 = 40
524 final int num_total_bytes_in_group2 = num_total_bytes_in_group1 + 1;
525 // num_data_bytes_in_group1 = 66 / 5 = 13
526 final int num_data_bytes_in_group1 = num_data_bytes / num_rs_blocks;
527 // num_data_bytes_in_group2 = 13 + 1 = 14
528 final int num_data_bytes_in_group2 = num_data_bytes_in_group1 + 1;
529 // num_ec_bytes_in_group1 = 39 - 13 = 26
530 final int num_ec_bytes_in_group1 = num_total_bytes_in_group1 -
531 num_data_bytes_in_group1;
532 // num_ec_bytes_in_group2 = 40 - 14 = 26
533 final int num_ec_bytes_in_group2 = num_total_bytes_in_group2 -
534 num_data_bytes_in_group2;
537 Debug.DCHECK_EQ(num_ec_bytes_in_group1, num_ec_bytes_in_group2);
539 Debug.DCHECK_EQ(num_rs_blocks, num_rs_blocks_in_group1 + num_rs_blocks_in_group2);
540 // 196 = (13 + 26) * 4 + (14 + 26) * 1
541 Debug.DCHECK_EQ(num_total_bytes,
542 ((num_data_bytes_in_group1 + num_ec_bytes_in_group1) *
543 num_rs_blocks_in_group1) +
544 ((num_data_bytes_in_group2 + num_ec_bytes_in_group2) *
545 num_rs_blocks_in_group2));
547 if (block_id < num_rs_blocks_in_group1) {
548 num_data_bytes_in_block[0] = num_data_bytes_in_group1;
549 num_ec_bytes_in_block[0] = num_ec_bytes_in_group1;
551 num_data_bytes_in_block[0] = num_data_bytes_in_group2;
552 num_ec_bytes_in_block[0] = num_ec_bytes_in_group2;
556 // Interleave "bits" with corresponding error correction bytes. On success, store the result in
557 // "result" and return true. On error, return false. The interleave rule is complicated. See 8.6
558 // of JISX0510:2004 (p.37) for details.
559 static boolean InterleaveWithECBytes(final BitVector bits, int num_total_bytes,
560 int num_data_bytes, int num_rs_blocks, BitVector result) {
562 // "bits" must have "num_data_bytes" bytes of data.
563 Debug.DCHECK(bits.num_bytes() == num_data_bytes);
565 // Step 1. Divide data bytes into blocks and generate error correction bytes for them. We'll
566 // store the divided data bytes blocks and error correction bytes blocks into "blocks".
567 int data_bytes_offset = 0;
568 int max_num_data_bytes = 0;
569 int max_num_ec_bytes = 0;
571 // Since, we know the number of reedsolmon blocks, we can initialize the vector with the number.
572 Vector blocks = new Vector(num_rs_blocks);
574 for (int i = 0; i < num_rs_blocks; ++i) {
575 int[] num_data_bytes_in_block = new int[1];
576 int[] num_ec_bytes_in_block = new int[1];
577 GetNumDataBytesAndNumECBytesForBlockID(
578 num_total_bytes, num_data_bytes, num_rs_blocks, i,
579 num_data_bytes_in_block, num_ec_bytes_in_block);
581 ByteArray data_bytes = new ByteArray();
582 data_bytes.set(bits.getArray(), data_bytes_offset, num_data_bytes_in_block[0]);
583 ByteArray ec_bytes = GenerateECBytes(data_bytes, num_ec_bytes_in_block[0]);
584 blocks.addElement(new BlockPair(data_bytes, ec_bytes));
586 max_num_data_bytes = Math.max(max_num_data_bytes, data_bytes.size());
587 max_num_ec_bytes = Math.max(max_num_ec_bytes, ec_bytes.size());
588 data_bytes_offset += num_data_bytes_in_block[0];
590 Debug.DCHECK_EQ(num_data_bytes, data_bytes_offset);
592 // First, place data blocks.
593 for (int i = 0; i < max_num_data_bytes; ++i) {
594 for (int j = 0; j < blocks.size(); ++j) {
595 final ByteArray data_bytes = ((BlockPair) blocks.elementAt(j)).getDataBytes();
596 if (i < data_bytes.size()) {
597 result.AppendBits(data_bytes.at(i), 8);
601 // Then, place error correction blocks.
602 for (int i = 0; i < max_num_ec_bytes; ++i) {
603 for (int j = 0; j < blocks.size(); ++j) {
604 final ByteArray ec_bytes = ((BlockPair) blocks.elementAt(j)).getErrorCorrectionBytes();
605 if (i < ec_bytes.size()) {
606 result.AppendBits(ec_bytes.at(i), 8);
610 if (num_total_bytes == result.num_bytes()) { // Should be same.
613 Debug.LOG_ERROR("Interleaving error: " + num_total_bytes + " and " + result.num_bytes() +
618 static ByteArray GenerateECBytes(ByteArray data_bytes, int num_ec_bytes_in_block) {
619 int numDataBytes = data_bytes.size();
620 int[] toEncode = new int[numDataBytes + num_ec_bytes_in_block];
621 for (int i = 0; i < numDataBytes; i++) {
622 toEncode[i] = data_bytes.at(i);
624 new ReedSolomonEncoder(GF256.QR_CODE_FIELD).encode(toEncode, num_ec_bytes_in_block);
626 ByteArray ec_bytes = new ByteArray(num_ec_bytes_in_block);
627 for (int i = 0; i < num_ec_bytes_in_block; i++) {
628 ec_bytes.set(i, toEncode[numDataBytes + i]);
633 // Append mode info. On success, store the result in "bits" and return true. On error, return
635 static boolean AppendModeInfo(int mode, BitVector bits) {
636 final int code = QRCode.GetModeCode(mode);
638 Debug.LOG_ERROR("Invalid mode: " + mode);
641 bits.AppendBits(code, 4);
646 // Append length info. On success, store the result in "bits" and return true. On error, return
648 static boolean AppendLengthInfo(int num_bytes, int version, int mode, BitVector bits) {
649 int num_letters = num_bytes;
650 // In Kanji mode, a letter is represented in two bytes.
651 if (mode == QRCode.MODE_KANJI) {
652 Debug.DCHECK_EQ(0, num_letters % 2);
656 final int num_bits = QRCode.GetNumBitsForLength(version, mode);
657 if (num_bits == -1) {
658 Debug.LOG_ERROR("num_bits unset");
661 if (num_letters > ((1 << num_bits) - 1)) {
662 Debug.LOG_ERROR(num_letters + "is bigger than" + ((1 << num_bits) - 1));
665 bits.AppendBits(num_letters, num_bits);
669 // Append "bytes" in "mode" mode (encoding) into "bits". On success, store the result in "bits"
670 // and return true. On error, return false.
671 static boolean AppendBytes(final ByteArray bytes, int mode, BitVector bits) {
673 case QRCode.MODE_NUMERIC:
674 return AppendNumericBytes(bytes, bits);
675 case QRCode.MODE_ALPHANUMERIC:
676 return AppendAlphanumericBytes(bytes, bits);
677 case QRCode.MODE_8BIT_BYTE:
678 return Append8BitBytes(bytes, bits);
679 case QRCode.MODE_KANJI:
680 return AppendKanjiBytes(bytes, bits);
684 Debug.LOG_ERROR("Invalid mode: " + mode);
688 // Append "bytes" to "bits" using QRCode.MODE_NUMERIC mode. On success, store the result in "bits"
689 // and return true. On error, return false.
690 static boolean AppendNumericBytes(final ByteArray bytes, BitVector bits) {
691 // Validate all the bytes first.
692 for (int i = 0; i < bytes.size(); ++i) {
693 int oneByte = bytes.at(i);
694 if (oneByte < '0' || oneByte > '9') {
698 for (int i = 0; i < bytes.size();) {
699 final int num1 = bytes.at(i) - '0';
700 if (i + 2 < bytes.size()) {
701 // Encode three numeric letters in ten bits.
702 final int num2 = bytes.at(i + 1) - '0';
703 final int num3 = bytes.at(i + 2) - '0';
704 bits.AppendBits(num1 * 100 + num2 * 10 + num3, 10);
706 } else if (i + 1 < bytes.size()) {
707 // Encode two numeric letters in seven bits.
708 final int num2 = bytes.at(i + 1) - '0';
709 bits.AppendBits(num1 * 10 + num2, 7);
712 // Encode one numeric letter in four bits.
713 bits.AppendBits(num1, 4);
720 // Append "bytes" to "bits" using QRCode.MODE_ALPHANUMERIC mode. On success, store the result in
721 // "bits" and return true. On error, return false.
722 static boolean AppendAlphanumericBytes(final ByteArray bytes, BitVector bits) {
723 for (int i = 0; i < bytes.size();) {
724 final int code1 = GetAlphanumericCode(bytes.at(i));
728 if (i + 1 < bytes.size()) {
729 final int code2 = GetAlphanumericCode(bytes.at(i + 1));
733 // Encode two alphanumeric letters in 11 bits.
734 bits.AppendBits(code1 * 45 + code2, 11);
737 // Encode one alphanumeric letter in six bits.
738 bits.AppendBits(code1, 6);
745 // Append "bytes" to "bits" using QRCode.MODE_8BIT_BYTE mode. On success, store the result in
746 // "bits" and return true. On error, return false.
747 static boolean Append8BitBytes(final ByteArray bytes, BitVector bits) {
748 for (int i = 0; i < bytes.size(); ++i) {
749 bits.AppendBits(bytes.at(i), 8);
754 // Append "bytes" to "bits" using QRCode.MODE_KANJI mode. On success, store the result in "bits"
755 // and return true. On error, return false. See 8.4.5 of JISX0510:2004 (p.21) for how to encode
757 static boolean AppendKanjiBytes(final ByteArray bytes, BitVector bits) {
758 if (bytes.size() % 2 != 0) {
759 Debug.LOG_ERROR("Invalid byte sequence: " + bytes);
762 for (int i = 0; i < bytes.size(); i += 2) {
763 Debug.DCHECK(IsValidKanji(bytes.at(i), bytes.at(i + 1)));
764 final int code = (bytes.at(i) << 8) | bytes.at(i + 1);
766 if (code >= 0x8140 && code <= 0x9ffc) {
767 subtracted = code - 0x8140;
768 } else if (code >= 0xe040 && code <= 0xebbf) {
769 subtracted = code - 0xc140;
771 if (subtracted == -1) {
772 Debug.LOG_ERROR("Invalid byte sequence: " + bytes);
775 final int encoded = ((subtracted >> 8) * 0xc0) + (subtracted & 0xff);
776 bits.AppendBits(encoded, 13);
781 // Check if "byte1" and "byte2" can compose a valid Kanji letter (2-byte Shift_JIS letter). The
782 // numbers are from http://ja.wikipedia.org/wiki/Shift_JIS.
783 static boolean IsValidKanji(final int byte1, final int byte2) {
784 return (byte2 != 0x7f &&
785 ((byte1 >= 0x81 && byte1 <= 0x9f &&
786 byte2 >= 0x40 && byte2 <= 0xfc) ||
787 ((byte1 >= 0xe0 && byte1 <= 0xfc &&
788 byte2 >= 0x40 && byte2 <= 0xfc))));
791 // Check if "bytes" is a valid Kanji sequence. Used by the unit tests.
792 static boolean IsValidKanjiSequence(final ByteArray bytes) {
793 if (bytes.size() % 2 != 0) {
797 for (; i < bytes.size(); i += 2) {
798 if (!IsValidKanji(bytes.at(i), bytes.at(i + 1))) {
802 return i == bytes.size(); // Consumed all bytes?