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.WriterException;
20 import com.google.zxing.common.ByteArray;
21 import com.google.zxing.common.ByteMatrix;
22 import com.google.zxing.common.reedsolomon.GF256;
23 import com.google.zxing.common.reedsolomon.ReedSolomonEncoder;
24 import com.google.zxing.qrcode.decoder.ErrorCorrectionLevel;
25 import com.google.zxing.qrcode.decoder.Mode;
26 import com.google.zxing.qrcode.decoder.Version;
28 import java.util.Vector;
29 import java.io.UnsupportedEncodingException;
32 * @author satorux@google.com (Satoru Takabayashi) - creator
33 * @author dswitkin@google.com (Daniel Switkin) - ported from C++
35 public final class Encoder {
37 // The original table is defined in the table 5 of JISX0510:2004 (p.19).
38 private static final int[] ALPHANUMERIC_TABLE = {
39 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 0x00-0x0f
40 -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, // 0x10-0x1f
41 36, -1, -1, -1, 37, 38, -1, -1, -1, -1, 39, 40, -1, 41, 42, 43, // 0x20-0x2f
42 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 44, -1, -1, -1, -1, -1, // 0x30-0x3f
43 -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, // 0x40-0x4f
44 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1, // 0x50-0x5f
50 // The mask penalty calculation is complicated. See Table 21 of JISX0510:2004 (p.45) for details.
51 // Basically it applies four rules and summate all penalties.
52 private static int calculateMaskPenalty(ByteMatrix matrix) {
54 penalty += MaskUtil.applyMaskPenaltyRule1(matrix);
55 penalty += MaskUtil.applyMaskPenaltyRule2(matrix);
56 penalty += MaskUtil.applyMaskPenaltyRule3(matrix);
57 penalty += MaskUtil.applyMaskPenaltyRule4(matrix);
61 private static final class BlockPair {
63 private final ByteArray dataBytes;
64 private final ByteArray errorCorrectionBytes;
66 BlockPair(ByteArray data, ByteArray errorCorrection) {
68 errorCorrectionBytes = errorCorrection;
71 public ByteArray getDataBytes() {
75 public ByteArray getErrorCorrectionBytes() {
76 return errorCorrectionBytes;
81 // Encode "bytes" with the error correction level "getECLevel". The encoding mode will be chosen
82 // internally by chooseMode(). On success, store the result in "qrCode" and return true.
83 // We recommend you to use QRCode.EC_LEVEL_L (the lowest level) for
84 // "getECLevel" since our primary use is to show QR code on desktop screens. We don't need very
85 // strong error correction for this purpose.
87 // Note that there is no way to encode bytes in MODE_KANJI. We might want to add EncodeWithMode()
88 // with which clients can specify the encoding mode. For now, we don't need the functionality.
89 public static void encode(String content, ErrorCorrectionLevel ecLevel, QRCode qrCode)
90 throws WriterException {
91 // Step 1: Choose the mode (encoding).
92 Mode mode = chooseMode(content);
94 // Step 2: Append "bytes" into "dataBits" in appropriate encoding.
95 BitVector dataBits = new BitVector();
96 appendBytes(content, mode, dataBits);
97 // Step 3: Initialize QR code that can contain "dataBits".
98 int numInputBytes = dataBits.sizeInBytes();
99 initQRCode(numInputBytes, ecLevel, mode, qrCode);
101 // Step 4: Build another bit vector that contains header and data.
102 BitVector headerAndDataBits = new BitVector();
103 appendModeInfo(qrCode.getMode(), headerAndDataBits);
104 appendLengthInfo(content.length(), qrCode.getVersion(), qrCode.getMode(), headerAndDataBits);
105 headerAndDataBits.appendBitVector(dataBits);
107 // Step 5: Terminate the bits properly.
108 terminateBits(qrCode.getNumDataBytes(), headerAndDataBits);
110 // Step 6: Interleave data bits with error correction code.
111 BitVector finalBits = new BitVector();
112 interleaveWithECBytes(headerAndDataBits, qrCode.getNumTotalBytes(), qrCode.getNumDataBytes(),
113 qrCode.getNumRSBlocks(), finalBits);
115 // Step 7: Choose the mask pattern and set to "qrCode".
116 ByteMatrix matrix = new ByteMatrix(qrCode.getMatrixWidth(), qrCode.getMatrixWidth());
117 qrCode.setMaskPattern(chooseMaskPattern(finalBits, qrCode.getECLevel(), qrCode.getVersion(),
120 // Step 8. Build the matrix and set it to "qrCode".
121 MatrixUtil.buildMatrix(finalBits, qrCode.getECLevel(), qrCode.getVersion(),
122 qrCode.getMaskPattern(), matrix);
123 qrCode.setMatrix(matrix);
124 // Step 9. Make sure we have a valid QR Code.
125 if (!qrCode.isValid()) {
126 throw new WriterException("Invalid QR code: " + qrCode.toString());
130 // Return the code point of the table used in alphanumeric mode. Return -1 if there is no
131 // corresponding code in the table.
132 static int getAlphanumericCode(int code) {
133 if (code < ALPHANUMERIC_TABLE.length) {
134 return ALPHANUMERIC_TABLE[code];
139 // Choose the best mode by examining the content.
141 // Note that this function does not return MODE_KANJI, as we cannot distinguish Shift_JIS from
142 // other encodings such as ISO-8859-1, from data bytes alone. For example "\xE0\xE0" can be
143 // interpreted as one character in Shift_JIS, but also two characters in ISO-8859-1.
145 // JAVAPORT: This MODE_KANJI limitation sounds like a problem for us.
146 public static Mode chooseMode(String content) {
147 boolean hasNumeric = false;
148 boolean hasAlphanumeric = false;
149 for (int i = 0; i < content.length(); ++i) {
150 char c = content.charAt(i);
151 if (c >= '0' && c <= '9') {
153 } else if (getAlphanumericCode(c) != -1) {
154 hasAlphanumeric = true;
159 if (hasAlphanumeric) {
160 return Mode.ALPHANUMERIC;
161 } else if (hasNumeric) {
167 private static int chooseMaskPattern(BitVector bits, ErrorCorrectionLevel ecLevel, int version,
168 ByteMatrix matrix) throws WriterException {
170 int minPenalty = Integer.MAX_VALUE; // Lower penalty is better.
171 int bestMaskPattern = -1;
172 // We try all mask patterns to choose the best one.
173 for (int maskPattern = 0; maskPattern < QRCode.NUM_MASK_PATTERNS; maskPattern++) {
174 MatrixUtil.buildMatrix(bits, ecLevel, version, maskPattern, matrix);
175 int penalty = calculateMaskPenalty(matrix);
176 if (penalty < minPenalty) {
177 minPenalty = penalty;
178 bestMaskPattern = maskPattern;
181 return bestMaskPattern;
184 // Initialize "qrCode" according to "numInputBytes", "ecLevel", and "mode". On success, modify
186 private static void initQRCode(int numInputBytes, ErrorCorrectionLevel ecLevel, Mode mode, QRCode qrCode)
187 throws WriterException {
188 qrCode.setECLevel(ecLevel);
189 qrCode.setMode(mode);
191 // In the following comments, we use numbers of Version 7-H.
192 for (int versionNum = 1; versionNum <= 40; versionNum++) {
193 Version version = Version.getVersionForNumber(versionNum);
195 int numBytes = version.getTotalCodewords();
196 // getNumECBytes = 130
197 Version.ECBlocks ecBlocks = version.getECBlocksForLevel(ecLevel);
198 int numEcBytes = ecBlocks.getTotalECCodewords();
199 // getNumRSBlocks = 5
200 int numRSBlocks = ecBlocks.getNumBlocks();
201 // getNumDataBytes = 196 - 130 = 66
202 int numDataBytes = numBytes - numEcBytes;
203 // We want to choose the smallest version which can contain data of "numInputBytes" + some
204 // extra bits for the header (mode info and length info). The header can be three bytes
205 // (precisely 4 + 16 bits) at most. Hence we do +3 here.
206 if (numDataBytes >= numInputBytes + 3) {
207 // Yay, we found the proper rs block info!
208 qrCode.setVersion(versionNum);
209 qrCode.setNumTotalBytes(numBytes);
210 qrCode.setNumDataBytes(numDataBytes);
211 qrCode.setNumRSBlocks(numRSBlocks);
212 // getNumECBytes = 196 - 66 = 130
213 qrCode.setNumECBytes(numEcBytes);
214 // matrix width = 21 + 6 * 4 = 45
215 qrCode.setMatrixWidth(version.getDimensionForVersion());
219 throw new WriterException("Cannot find proper rs block info (input data too big?)");
222 // Terminate bits as described in 8.4.8 and 8.4.9 of JISX0510:2004 (p.24).
223 static void terminateBits(int numDataBytes, BitVector bits) throws WriterException {
224 int capacity = numDataBytes << 3;
225 if (bits.size() > capacity) {
226 throw new WriterException("data bits cannot fit in the QR Code" + bits.size() + " > " + capacity);
228 // Append termination bits. See 8.4.8 of JISX0510:2004 (p.24) for details.
229 for (int i = 0; i < 4 && bits.size() < capacity; ++i) {
232 int numBitsInLastByte = bits.size() % 8;
233 // If the last byte isn't 8-bit aligned, we'll add padding bits.
234 if (numBitsInLastByte > 0) {
235 int numPaddingBits = 8 - numBitsInLastByte;
236 for (int i = 0; i < numPaddingBits; ++i) {
240 // Should be 8-bit aligned here.
241 if (bits.size() % 8 != 0) {
242 throw new WriterException("Number of bits is not a multiple of 8");
244 // If we have more space, we'll fill the space with padding patterns defined in 8.4.9 (p.24).
245 int numPaddingBytes = numDataBytes - bits.sizeInBytes();
246 for (int i = 0; i < numPaddingBytes; ++i) {
248 bits.appendBits(0xec, 8);
250 bits.appendBits(0x11, 8);
253 if (bits.size() != capacity) {
254 throw new WriterException("Bits size does not equal capacity");
258 // Get number of data bytes and number of error correction bytes for block id "blockID". Store
259 // the result in "numDataBytesInBlock", and "numECBytesInBlock". See table 12 in 8.5.1 of
260 // JISX0510:2004 (p.30)
261 static void getNumDataBytesAndNumECBytesForBlockID(int numTotalBytes, int numDataBytes,
262 int numRSBlocks, int blockID, int[] numDataBytesInBlock,
263 int[] numECBytesInBlock) throws WriterException {
264 if (blockID >= numRSBlocks) {
265 throw new WriterException("Block ID too large");
267 // numRsBlocksInGroup2 = 196 % 5 = 1
268 int numRsBlocksInGroup2 = numTotalBytes % numRSBlocks;
269 // numRsBlocksInGroup1 = 5 - 1 = 4
270 int numRsBlocksInGroup1 = numRSBlocks - numRsBlocksInGroup2;
271 // numTotalBytesInGroup1 = 196 / 5 = 39
272 int numTotalBytesInGroup1 = numTotalBytes / numRSBlocks;
273 // numTotalBytesInGroup2 = 39 + 1 = 40
274 int numTotalBytesInGroup2 = numTotalBytesInGroup1 + 1;
275 // numDataBytesInGroup1 = 66 / 5 = 13
276 int numDataBytesInGroup1 = numDataBytes / numRSBlocks;
277 // numDataBytesInGroup2 = 13 + 1 = 14
278 int numDataBytesInGroup2 = numDataBytesInGroup1 + 1;
279 // numEcBytesInGroup1 = 39 - 13 = 26
280 int numEcBytesInGroup1 = numTotalBytesInGroup1 - numDataBytesInGroup1;
281 // numEcBytesInGroup2 = 40 - 14 = 26
282 int numEcBytesInGroup2 = numTotalBytesInGroup2 - numDataBytesInGroup2;
285 if (numEcBytesInGroup1 != numEcBytesInGroup2) {
286 throw new WriterException("EC bytes mismatch");
289 if (numRSBlocks != numRsBlocksInGroup1 + numRsBlocksInGroup2) {
290 throw new WriterException("RS blocks mismatch");
292 // 196 = (13 + 26) * 4 + (14 + 26) * 1
294 ((numDataBytesInGroup1 + numEcBytesInGroup1) *
295 numRsBlocksInGroup1) +
296 ((numDataBytesInGroup2 + numEcBytesInGroup2) *
297 numRsBlocksInGroup2)) {
298 throw new WriterException("Total bytes mismatch");
301 if (blockID < numRsBlocksInGroup1) {
302 numDataBytesInBlock[0] = numDataBytesInGroup1;
303 numECBytesInBlock[0] = numEcBytesInGroup1;
305 numDataBytesInBlock[0] = numDataBytesInGroup2;
306 numECBytesInBlock[0] = numEcBytesInGroup2;
310 // Interleave "bits" with corresponding error correction bytes. On success, store the result in
311 // "result" and return true. The interleave rule is complicated. See 8.6
312 // of JISX0510:2004 (p.37) for details.
313 static void interleaveWithECBytes(BitVector bits, int numTotalBytes,
314 int numDataBytes, int numRSBlocks, BitVector result) throws WriterException {
316 // "bits" must have "getNumDataBytes" bytes of data.
317 if (bits.sizeInBytes() != numDataBytes) {
318 throw new WriterException("Number of bits and data bytes does not match");
321 // Step 1. Divide data bytes into blocks and generate error correction bytes for them. We'll
322 // store the divided data bytes blocks and error correction bytes blocks into "blocks".
323 int dataBytesOffset = 0;
324 int maxNumDataBytes = 0;
325 int maxNumEcBytes = 0;
327 // Since, we know the number of reedsolmon blocks, we can initialize the vector with the number.
328 Vector blocks = new Vector(numRSBlocks);
330 for (int i = 0; i < numRSBlocks; ++i) {
331 int[] numDataBytesInBlock = new int[1];
332 int[] numEcBytesInBlock = new int[1];
333 getNumDataBytesAndNumECBytesForBlockID(
334 numTotalBytes, numDataBytes, numRSBlocks, i,
335 numDataBytesInBlock, numEcBytesInBlock);
337 ByteArray dataBytes = new ByteArray();
338 dataBytes.set(bits.getArray(), dataBytesOffset, numDataBytesInBlock[0]);
339 ByteArray ecBytes = generateECBytes(dataBytes, numEcBytesInBlock[0]);
340 blocks.addElement(new BlockPair(dataBytes, ecBytes));
342 maxNumDataBytes = Math.max(maxNumDataBytes, dataBytes.size());
343 maxNumEcBytes = Math.max(maxNumEcBytes, ecBytes.size());
344 dataBytesOffset += numDataBytesInBlock[0];
346 if (numDataBytes != dataBytesOffset) {
347 throw new WriterException("Data bytes does not match offset");
350 // First, place data blocks.
351 for (int i = 0; i < maxNumDataBytes; ++i) {
352 for (int j = 0; j < blocks.size(); ++j) {
353 ByteArray dataBytes = ((BlockPair) blocks.elementAt(j)).getDataBytes();
354 if (i < dataBytes.size()) {
355 result.appendBits(dataBytes.at(i), 8);
359 // Then, place error correction blocks.
360 for (int i = 0; i < maxNumEcBytes; ++i) {
361 for (int j = 0; j < blocks.size(); ++j) {
362 ByteArray ecBytes = ((BlockPair) blocks.elementAt(j)).getErrorCorrectionBytes();
363 if (i < ecBytes.size()) {
364 result.appendBits(ecBytes.at(i), 8);
368 if (numTotalBytes != result.sizeInBytes()) { // Should be same.
369 throw new WriterException("Interleaving error: " + numTotalBytes + " and " + result.sizeInBytes() +
374 static ByteArray generateECBytes(ByteArray dataBytes, int numEcBytesInBlock) {
375 int numDataBytes = dataBytes.size();
376 int[] toEncode = new int[numDataBytes + numEcBytesInBlock];
377 for (int i = 0; i < numDataBytes; i++) {
378 toEncode[i] = dataBytes.at(i);
380 new ReedSolomonEncoder(GF256.QR_CODE_FIELD).encode(toEncode, numEcBytesInBlock);
382 ByteArray ecBytes = new ByteArray(numEcBytesInBlock);
383 for (int i = 0; i < numEcBytesInBlock; i++) {
384 ecBytes.set(i, toEncode[numDataBytes + i]);
389 // Append mode info. On success, store the result in "bits" and return true. On error, return
391 static void appendModeInfo(Mode mode, BitVector bits) {
392 bits.appendBits(mode.getBits(), 4);
396 // Append length info. On success, store the result in "bits" and return true. On error, return
398 static void appendLengthInfo(int numLetters, int version, Mode mode, BitVector bits) throws WriterException {
399 int numBits = mode.getCharacterCountBits(Version.getVersionForNumber(version));
400 if (numLetters > ((1 << numBits) - 1)) {
401 throw new WriterException(numLetters + "is bigger than" + ((1 << numBits) - 1));
403 bits.appendBits(numLetters, numBits);
406 // Append "bytes" in "mode" mode (encoding) into "bits". On success, store the result in "bits"
408 static void appendBytes(String content, Mode mode, BitVector bits) throws WriterException {
409 if (mode.equals(Mode.NUMERIC)) {
410 appendNumericBytes(content, bits);
411 } else if (mode.equals(Mode.ALPHANUMERIC)) {
412 appendAlphanumericBytes(content, bits);
413 } else if (mode.equals(Mode.BYTE)) {
414 append8BitBytes(content, bits);
415 } else if (mode.equals(Mode.KANJI)) {
416 appendKanjiBytes(content, bits);
418 throw new WriterException("Invalid mode: " + mode);
422 static void appendNumericBytes(String content, BitVector bits) {
423 int length = content.length();
426 int num1 = content.charAt(i) - '0';
427 if (i + 2 < length) {
428 // Encode three numeric letters in ten bits.
429 int num2 = content.charAt(i + 1) - '0';
430 int num3 = content.charAt(i + 2) - '0';
431 bits.appendBits(num1 * 100 + num2 * 10 + num3, 10);
433 } else if (i + 1 < length) {
434 // Encode two numeric letters in seven bits.
435 int num2 = content.charAt(i + 1) - '0';
436 bits.appendBits(num1 * 10 + num2, 7);
439 // Encode one numeric letter in four bits.
440 bits.appendBits(num1, 4);
446 static void appendAlphanumericBytes(String content, BitVector bits) throws WriterException {
447 int length = content.length();
450 int code1 = getAlphanumericCode(content.charAt(i));
452 throw new WriterException();
454 if (i + 1 < length) {
455 int code2 = getAlphanumericCode(content.charAt(i + 1));
457 throw new WriterException();
459 // Encode two alphanumeric letters in 11 bits.
460 bits.appendBits(code1 * 45 + code2, 11);
463 // Encode one alphanumeric letter in six bits.
464 bits.appendBits(code1, 6);
470 static void append8BitBytes(String content, BitVector bits) throws WriterException {
473 bytes = content.getBytes("ISO-8859-1"); // TODO support specifying encoding?
474 } catch (UnsupportedEncodingException uee) {
475 throw new WriterException(uee.toString());
477 for (int i = 0; i < bytes.length; ++i) {
478 bits.appendBits(bytes[i], 8);
482 static void appendKanjiBytes(String content, BitVector bits) throws WriterException {
485 bytes = content.getBytes("Shift_JIS");
486 } catch (UnsupportedEncodingException uee) {
487 throw new WriterException(uee.toString());
489 int length = bytes.length;
490 for (int i = 0; i < length; i += 2) {
491 int byte1 = bytes[i] & 0xFF;
492 int byte2 = bytes[i + 1] & 0xFF;
493 int code = (byte1 << 8) | byte2;
495 if (code >= 0x8140 && code <= 0x9ffc) {
496 subtracted = code - 0x8140;
497 } else if (code >= 0xe040 && code <= 0xebbf) {
498 subtracted = code - 0xc140;
500 if (subtracted == -1) {
501 throw new WriterException("Invalid byte sequence");
503 int encoded = ((subtracted >> 8) * 0xc0) + (subtracted & 0xff);
504 bits.appendBits(encoded, 13);