• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * QR Code generator library (Java)
3  *
4  * Copyright (c) Project Nayuki. (MIT License)
5  * https://www.nayuki.io/page/qr-code-generator-library
6  *
7  * Permission is hereby granted, free of charge, to any person obtaining a copy of
8  * this software and associated documentation files (the "Software"), to deal in
9  * the Software without restriction, including without limitation the rights to
10  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
11  * the Software, and to permit persons to whom the Software is furnished to do so,
12  * subject to the following conditions:
13  * - The above copyright notice and this permission notice shall be included in
14  *   all copies or substantial portions of the Software.
15  * - The Software is provided "as is", without warranty of any kind, express or
16  *   implied, including but not limited to the warranties of merchantability,
17  *   fitness for a particular purpose and noninfringement. In no event shall the
18  *   authors or copyright holders be liable for any claim, damages or other
19  *   liability, whether in an action of contract, tort or otherwise, arising from,
20  *   out of or in connection with the Software or the use or other dealings in the
21  *   Software.
22  */
23 
24 package io.nayuki.qrcodegen;
25 
26 import java.util.Arrays;
27 import java.util.List;
28 import java.util.Objects;
29 
30 
31 /**
32  * A QR Code symbol, which is a type of two-dimension barcode.
33  * Invented by Denso Wave and described in the ISO/IEC 18004 standard.
34  * <p>Instances of this class represent an immutable square grid of dark and light cells.
35  * The class provides static factory functions to create a QR Code from text or binary data.
36  * The class covers the QR Code Model 2 specification, supporting all versions (sizes)
37  * from 1 to 40, all 4 error correction levels, and 4 character encoding modes.</p>
38  * <p>Ways to create a QR Code object:</p>
39  * <ul>
40  *   <li><p>High level: Take the payload data and call {@link QrCode#encodeText(String,Ecc)}
41  *     or {@link QrCode#encodeBinary(byte[],Ecc)}.</p></li>
42  *   <li><p>Mid level: Custom-make the list of {@link QrSegment segments}
43  *     and call {@link QrCode#encodeSegments(List,Ecc)} or
44  *     {@link QrCode#encodeSegments(List,Ecc,int,int,int,boolean)}</p></li>
45  *   <li><p>Low level: Custom-make the array of data codeword bytes (including segment headers and
46  *     final padding, excluding error correction codewords), supply the appropriate version number,
47  *     and call the {@link QrCode#QrCode(int,Ecc,byte[],int) constructor}.</p></li>
48  * </ul>
49  * <p>(Note that all ways require supplying the desired error correction level.)</p>
50  * @see QrSegment
51  */
52 public final class QrCode {
53 
54 	/*---- Static factory functions (high level) ----*/
55 
56 	/**
57 	 * Returns a QR Code representing the specified Unicode text string at the specified error correction level.
58 	 * As a conservative upper bound, this function is guaranteed to succeed for strings that have 738 or fewer
59 	 * Unicode code points (not UTF-16 code units) if the low error correction level is used. The smallest possible
60 	 * QR Code version is automatically chosen for the output. The ECC level of the result may be higher than the
61 	 * ecl argument if it can be done without increasing the version.
62 	 * @param text the text to be encoded (not {@code null}), which can be any Unicode string
63 	 * @param ecl the error correction level to use (not {@code null}) (boostable)
64 	 * @return a QR Code (not {@code null}) representing the text
65 	 * @throws NullPointerException if the text or error correction level is {@code null}
66 	 * @throws DataTooLongException if the text fails to fit in the
67 	 * largest version QR Code at the ECL, which means it is too long
68 	 */
encodeText(String text, Ecc ecl)69 	public static QrCode encodeText(String text, Ecc ecl) {
70 		Objects.requireNonNull(text);
71 		Objects.requireNonNull(ecl);
72 		List<QrSegment> segs = QrSegment.makeSegments(text);
73 		return encodeSegments(segs, ecl);
74 	}
75 
76 
77 	/**
78 	 * Returns a QR Code representing the specified binary data at the specified error correction level.
79 	 * This function always encodes using the binary segment mode, not any text mode. The maximum number of
80 	 * bytes allowed is 2953. The smallest possible QR Code version is automatically chosen for the output.
81 	 * The ECC level of the result may be higher than the ecl argument if it can be done without increasing the version.
82 	 * @param data the binary data to encode (not {@code null})
83 	 * @param ecl the error correction level to use (not {@code null}) (boostable)
84 	 * @return a QR Code (not {@code null}) representing the data
85 	 * @throws NullPointerException if the data or error correction level is {@code null}
86 	 * @throws DataTooLongException if the data fails to fit in the
87 	 * largest version QR Code at the ECL, which means it is too long
88 	 */
encodeBinary(byte[] data, Ecc ecl)89 	public static QrCode encodeBinary(byte[] data, Ecc ecl) {
90 		Objects.requireNonNull(data);
91 		Objects.requireNonNull(ecl);
92 		QrSegment seg = QrSegment.makeBytes(data);
93 		return encodeSegments(Arrays.asList(seg), ecl);
94 	}
95 
96 
97 	/*---- Static factory functions (mid level) ----*/
98 
99 	/**
100 	 * Returns a QR Code representing the specified segments at the specified error correction
101 	 * level. The smallest possible QR Code version is automatically chosen for the output. The ECC level
102 	 * of the result may be higher than the ecl argument if it can be done without increasing the version.
103 	 * <p>This function allows the user to create a custom sequence of segments that switches
104 	 * between modes (such as alphanumeric and byte) to encode text in less space.
105 	 * This is a mid-level API; the high-level API is {@link #encodeText(String,Ecc)}
106 	 * and {@link #encodeBinary(byte[],Ecc)}.</p>
107 	 * @param segs the segments to encode
108 	 * @param ecl the error correction level to use (not {@code null}) (boostable)
109 	 * @return a QR Code (not {@code null}) representing the segments
110 	 * @throws NullPointerException if the list of segments, any segment, or the error correction level is {@code null}
111 	 * @throws DataTooLongException if the segments fail to fit in the
112 	 * largest version QR Code at the ECL, which means they are too long
113 	 */
encodeSegments(List<QrSegment> segs, Ecc ecl)114 	public static QrCode encodeSegments(List<QrSegment> segs, Ecc ecl) {
115 		return encodeSegments(segs, ecl, MIN_VERSION, MAX_VERSION, -1, true);
116 	}
117 
118 
119 	/**
120 	 * Returns a QR Code representing the specified segments with the specified encoding parameters.
121 	 * The smallest possible QR Code version within the specified range is automatically
122 	 * chosen for the output. Iff boostEcl is {@code true}, then the ECC level of the
123 	 * result may be higher than the ecl argument if it can be done without increasing
124 	 * the version. The mask number is either between 0 to 7 (inclusive) to force that
125 	 * mask, or &#x2212;1 to automatically choose an appropriate mask (which may be slow).
126 	 * <p>This function allows the user to create a custom sequence of segments that switches
127 	 * between modes (such as alphanumeric and byte) to encode text in less space.
128 	 * This is a mid-level API; the high-level API is {@link #encodeText(String,Ecc)}
129 	 * and {@link #encodeBinary(byte[],Ecc)}.</p>
130 	 * @param segs the segments to encode
131 	 * @param ecl the error correction level to use (not {@code null}) (boostable)
132 	 * @param minVersion the minimum allowed version of the QR Code (at least 1)
133 	 * @param maxVersion the maximum allowed version of the QR Code (at most 40)
134 	 * @param mask the mask number to use (between 0 and 7 (inclusive)), or &#x2212;1 for automatic mask
135 	 * @param boostEcl increases the ECC level as long as it doesn't increase the version number
136 	 * @return a QR Code (not {@code null}) representing the segments
137 	 * @throws NullPointerException if the list of segments, any segment, or the error correction level is {@code null}
138 	 * @throws IllegalArgumentException if 1 &#x2264; minVersion &#x2264; maxVersion &#x2264; 40
139 	 * or &#x2212;1 &#x2264; mask &#x2264; 7 is violated
140 	 * @throws DataTooLongException if the segments fail to fit in
141 	 * the maxVersion QR Code at the ECL, which means they are too long
142 	 */
encodeSegments(List<QrSegment> segs, Ecc ecl, int minVersion, int maxVersion, int mask, boolean boostEcl)143 	public static QrCode encodeSegments(List<QrSegment> segs, Ecc ecl, int minVersion, int maxVersion, int mask, boolean boostEcl) {
144 		Objects.requireNonNull(segs);
145 		Objects.requireNonNull(ecl);
146 		if (!(MIN_VERSION <= minVersion && minVersion <= maxVersion && maxVersion <= MAX_VERSION) || mask < -1 || mask > 7)
147 			throw new IllegalArgumentException("Invalid value");
148 
149 		// Find the minimal version number to use
150 		int version, dataUsedBits;
151 		for (version = minVersion; ; version++) {
152 			int dataCapacityBits = getNumDataCodewords(version, ecl) * 8;  // Number of data bits available
153 			dataUsedBits = QrSegment.getTotalBits(segs, version);
154 			if (dataUsedBits != -1 && dataUsedBits <= dataCapacityBits)
155 				break;  // This version number is found to be suitable
156 			if (version >= maxVersion) {  // All versions in the range could not fit the given data
157 				String msg = "Segment too long";
158 				if (dataUsedBits != -1)
159 					msg = String.format("Data length = %d bits, Max capacity = %d bits", dataUsedBits, dataCapacityBits);
160 				throw new DataTooLongException(msg);
161 			}
162 		}
163 		assert dataUsedBits != -1;
164 
165 		// Increase the error correction level while the data still fits in the current version number
166 		for (Ecc newEcl : Ecc.values()) {  // From low to high
167 			if (boostEcl && dataUsedBits <= getNumDataCodewords(version, newEcl) * 8)
168 				ecl = newEcl;
169 		}
170 
171 		// Concatenate all segments to create the data bit string
172 		BitBuffer bb = new BitBuffer();
173 		for (QrSegment seg : segs) {
174 			bb.appendBits(seg.mode.modeBits, 4);
175 			bb.appendBits(seg.numChars, seg.mode.numCharCountBits(version));
176 			bb.appendData(seg.data);
177 		}
178 		assert bb.bitLength() == dataUsedBits;
179 
180 		// Add terminator and pad up to a byte if applicable
181 		int dataCapacityBits = getNumDataCodewords(version, ecl) * 8;
182 		assert bb.bitLength() <= dataCapacityBits;
183 		bb.appendBits(0, Math.min(4, dataCapacityBits - bb.bitLength()));
184 		bb.appendBits(0, (8 - bb.bitLength() % 8) % 8);
185 		assert bb.bitLength() % 8 == 0;
186 
187 		// Pad with alternating bytes until data capacity is reached
188 		for (int padByte = 0xEC; bb.bitLength() < dataCapacityBits; padByte ^= 0xEC ^ 0x11)
189 			bb.appendBits(padByte, 8);
190 
191 		// Pack bits into bytes in big endian
192 		byte[] dataCodewords = new byte[bb.bitLength() / 8];
193 		for (int i = 0; i < bb.bitLength(); i++)
194 			dataCodewords[i >>> 3] |= bb.getBit(i) << (7 - (i & 7));
195 
196 		// Create the QR Code object
197 		return new QrCode(version, ecl, dataCodewords, mask);
198 	}
199 
200 
201 
202 	/*---- Instance fields ----*/
203 
204 	// Public immutable scalar parameters:
205 
206 	/** The version number of this QR Code, which is between 1 and 40 (inclusive).
207 	 * This determines the size of this barcode. */
208 	public final int version;
209 
210 	/** The width and height of this QR Code, measured in modules, between
211 	 * 21 and 177 (inclusive). This is equal to version &#xD7; 4 + 17. */
212 	public final int size;
213 
214 	/** The error correction level used in this QR Code, which is not {@code null}. */
215 	public final Ecc errorCorrectionLevel;
216 
217 	/** The index of the mask pattern used in this QR Code, which is between 0 and 7 (inclusive).
218 	 * <p>Even if a QR Code is created with automatic masking requested (mask =
219 	 * &#x2212;1), the resulting object still has a mask value between 0 and 7. */
220 	public final int mask;
221 
222 	// Private grids of modules/pixels, with dimensions of size*size:
223 
224 	// The modules of this QR Code (false = light, true = dark).
225 	// Immutable after constructor finishes. Accessed through getModule().
226 	private boolean[][] modules;
227 
228 	// Indicates function modules that are not subjected to masking. Discarded when constructor finishes.
229 	private boolean[][] isFunction;
230 
231 
232 
233 	/*---- Constructor (low level) ----*/
234 
235 	/**
236 	 * Constructs a QR Code with the specified version number,
237 	 * error correction level, data codeword bytes, and mask number.
238 	 * <p>This is a low-level API that most users should not use directly. A mid-level
239 	 * API is the {@link #encodeSegments(List,Ecc,int,int,int,boolean)} function.</p>
240 	 * @param ver the version number to use, which must be in the range 1 to 40 (inclusive)
241 	 * @param ecl the error correction level to use
242 	 * @param dataCodewords the bytes representing segments to encode (without ECC)
243 	 * @param msk the mask pattern to use, which is either &#x2212;1 for automatic choice or from 0 to 7 for fixed choice
244 	 * @throws NullPointerException if the byte array or error correction level is {@code null}
245 	 * @throws IllegalArgumentException if the version or mask value is out of range,
246 	 * or if the data is the wrong length for the specified version and error correction level
247 	 */
QrCode(int ver, Ecc ecl, byte[] dataCodewords, int msk)248 	public QrCode(int ver, Ecc ecl, byte[] dataCodewords, int msk) {
249 		// Check arguments and initialize fields
250 		if (ver < MIN_VERSION || ver > MAX_VERSION)
251 			throw new IllegalArgumentException("Version value out of range");
252 		if (msk < -1 || msk > 7)
253 			throw new IllegalArgumentException("Mask value out of range");
254 		version = ver;
255 		size = ver * 4 + 17;
256 		errorCorrectionLevel = Objects.requireNonNull(ecl);
257 		Objects.requireNonNull(dataCodewords);
258 		modules    = new boolean[size][size];  // Initially all light
259 		isFunction = new boolean[size][size];
260 
261 		// Compute ECC, draw modules, do masking
262 		drawFunctionPatterns();
263 		byte[] allCodewords = addEccAndInterleave(dataCodewords);
264 		drawCodewords(allCodewords);
265 		mask = handleConstructorMasking(msk);
266 		isFunction = null;
267 	}
268 
269 
270 
271 	/*---- Public instance methods ----*/
272 
273 	/**
274 	 * Returns the color of the module (pixel) at the specified coordinates, which is {@code false}
275 	 * for light or {@code true} for dark. The top left corner has the coordinates (x=0, y=0).
276 	 * If the specified coordinates are out of bounds, then {@code false} (light) is returned.
277 	 * @param x the x coordinate, where 0 is the left edge and size&#x2212;1 is the right edge
278 	 * @param y the y coordinate, where 0 is the top edge and size&#x2212;1 is the bottom edge
279 	 * @return {@code true} if the coordinates are in bounds and the module
280 	 * at that location is dark, or {@code false} (light) otherwise
281 	 */
getModule(int x, int y)282 	public boolean getModule(int x, int y) {
283 		return 0 <= x && x < size && 0 <= y && y < size && modules[y][x];
284 	}
285 
286 
287 
288 	/*---- Private helper methods for constructor: Drawing function modules ----*/
289 
290 	// Reads this object's version field, and draws and marks all function modules.
drawFunctionPatterns()291 	private void drawFunctionPatterns() {
292 		// Draw horizontal and vertical timing patterns
293 		for (int i = 0; i < size; i++) {
294 			setFunctionModule(6, i, i % 2 == 0);
295 			setFunctionModule(i, 6, i % 2 == 0);
296 		}
297 
298 		// Draw 3 finder patterns (all corners except bottom right; overwrites some timing modules)
299 		drawFinderPattern(3, 3);
300 		drawFinderPattern(size - 4, 3);
301 		drawFinderPattern(3, size - 4);
302 
303 		// Draw numerous alignment patterns
304 		int[] alignPatPos = getAlignmentPatternPositions();
305 		int numAlign = alignPatPos.length;
306 		for (int i = 0; i < numAlign; i++) {
307 			for (int j = 0; j < numAlign; j++) {
308 				// Don't draw on the three finder corners
309 				if (!(i == 0 && j == 0 || i == 0 && j == numAlign - 1 || i == numAlign - 1 && j == 0))
310 					drawAlignmentPattern(alignPatPos[i], alignPatPos[j]);
311 			}
312 		}
313 
314 		// Draw configuration data
315 		drawFormatBits(0);  // Dummy mask value; overwritten later in the constructor
316 		drawVersion();
317 	}
318 
319 
320 	// Draws two copies of the format bits (with its own error correction code)
321 	// based on the given mask and this object's error correction level field.
drawFormatBits(int msk)322 	private void drawFormatBits(int msk) {
323 		// Calculate error correction code and pack bits
324 		int data = errorCorrectionLevel.formatBits << 3 | msk;  // errCorrLvl is uint2, mask is uint3
325 		int rem = data;
326 		for (int i = 0; i < 10; i++)
327 			rem = (rem << 1) ^ ((rem >>> 9) * 0x537);
328 		int bits = (data << 10 | rem) ^ 0x5412;  // uint15
329 		assert bits >>> 15 == 0;
330 
331 		// Draw first copy
332 		for (int i = 0; i <= 5; i++)
333 			setFunctionModule(8, i, getBit(bits, i));
334 		setFunctionModule(8, 7, getBit(bits, 6));
335 		setFunctionModule(8, 8, getBit(bits, 7));
336 		setFunctionModule(7, 8, getBit(bits, 8));
337 		for (int i = 9; i < 15; i++)
338 			setFunctionModule(14 - i, 8, getBit(bits, i));
339 
340 		// Draw second copy
341 		for (int i = 0; i < 8; i++)
342 			setFunctionModule(size - 1 - i, 8, getBit(bits, i));
343 		for (int i = 8; i < 15; i++)
344 			setFunctionModule(8, size - 15 + i, getBit(bits, i));
345 		setFunctionModule(8, size - 8, true);  // Always dark
346 	}
347 
348 
349 	// Draws two copies of the version bits (with its own error correction code),
350 	// based on this object's version field, iff 7 <= version <= 40.
drawVersion()351 	private void drawVersion() {
352 		if (version < 7)
353 			return;
354 
355 		// Calculate error correction code and pack bits
356 		int rem = version;  // version is uint6, in the range [7, 40]
357 		for (int i = 0; i < 12; i++)
358 			rem = (rem << 1) ^ ((rem >>> 11) * 0x1F25);
359 		int bits = version << 12 | rem;  // uint18
360 		assert bits >>> 18 == 0;
361 
362 		// Draw two copies
363 		for (int i = 0; i < 18; i++) {
364 			boolean bit = getBit(bits, i);
365 			int a = size - 11 + i % 3;
366 			int b = i / 3;
367 			setFunctionModule(a, b, bit);
368 			setFunctionModule(b, a, bit);
369 		}
370 	}
371 
372 
373 	// Draws a 9*9 finder pattern including the border separator,
374 	// with the center module at (x, y). Modules can be out of bounds.
drawFinderPattern(int x, int y)375 	private void drawFinderPattern(int x, int y) {
376 		for (int dy = -4; dy <= 4; dy++) {
377 			for (int dx = -4; dx <= 4; dx++) {
378 				int dist = Math.max(Math.abs(dx), Math.abs(dy));  // Chebyshev/infinity norm
379 				int xx = x + dx, yy = y + dy;
380 				if (0 <= xx && xx < size && 0 <= yy && yy < size)
381 					setFunctionModule(xx, yy, dist != 2 && dist != 4);
382 			}
383 		}
384 	}
385 
386 
387 	// Draws a 5*5 alignment pattern, with the center module
388 	// at (x, y). All modules must be in bounds.
drawAlignmentPattern(int x, int y)389 	private void drawAlignmentPattern(int x, int y) {
390 		for (int dy = -2; dy <= 2; dy++) {
391 			for (int dx = -2; dx <= 2; dx++)
392 				setFunctionModule(x + dx, y + dy, Math.max(Math.abs(dx), Math.abs(dy)) != 1);
393 		}
394 	}
395 
396 
397 	// Sets the color of a module and marks it as a function module.
398 	// Only used by the constructor. Coordinates must be in bounds.
setFunctionModule(int x, int y, boolean isDark)399 	private void setFunctionModule(int x, int y, boolean isDark) {
400 		modules[y][x] = isDark;
401 		isFunction[y][x] = true;
402 	}
403 
404 
405 	/*---- Private helper methods for constructor: Codewords and masking ----*/
406 
407 	// Returns a new byte string representing the given data with the appropriate error correction
408 	// codewords appended to it, based on this object's version and error correction level.
addEccAndInterleave(byte[] data)409 	private byte[] addEccAndInterleave(byte[] data) {
410 		Objects.requireNonNull(data);
411 		if (data.length != getNumDataCodewords(version, errorCorrectionLevel))
412 			throw new IllegalArgumentException();
413 
414 		// Calculate parameter numbers
415 		int numBlocks = NUM_ERROR_CORRECTION_BLOCKS[errorCorrectionLevel.ordinal()][version];
416 		int blockEccLen = ECC_CODEWORDS_PER_BLOCK  [errorCorrectionLevel.ordinal()][version];
417 		int rawCodewords = getNumRawDataModules(version) / 8;
418 		int numShortBlocks = numBlocks - rawCodewords % numBlocks;
419 		int shortBlockLen = rawCodewords / numBlocks;
420 
421 		// Split data into blocks and append ECC to each block
422 		byte[][] blocks = new byte[numBlocks][];
423 		byte[] rsDiv = reedSolomonComputeDivisor(blockEccLen);
424 		for (int i = 0, k = 0; i < numBlocks; i++) {
425 			byte[] dat = Arrays.copyOfRange(data, k, k + shortBlockLen - blockEccLen + (i < numShortBlocks ? 0 : 1));
426 			k += dat.length;
427 			byte[] block = Arrays.copyOf(dat, shortBlockLen + 1);
428 			byte[] ecc = reedSolomonComputeRemainder(dat, rsDiv);
429 			System.arraycopy(ecc, 0, block, block.length - blockEccLen, ecc.length);
430 			blocks[i] = block;
431 		}
432 
433 		// Interleave (not concatenate) the bytes from every block into a single sequence
434 		byte[] result = new byte[rawCodewords];
435 		for (int i = 0, k = 0; i < blocks[0].length; i++) {
436 			for (int j = 0; j < blocks.length; j++) {
437 				// Skip the padding byte in short blocks
438 				if (i != shortBlockLen - blockEccLen || j >= numShortBlocks) {
439 					result[k] = blocks[j][i];
440 					k++;
441 				}
442 			}
443 		}
444 		return result;
445 	}
446 
447 
448 	// Draws the given sequence of 8-bit codewords (data and error correction) onto the entire
449 	// data area of this QR Code. Function modules need to be marked off before this is called.
drawCodewords(byte[] data)450 	private void drawCodewords(byte[] data) {
451 		Objects.requireNonNull(data);
452 		if (data.length != getNumRawDataModules(version) / 8)
453 			throw new IllegalArgumentException();
454 
455 		int i = 0;  // Bit index into the data
456 		// Do the funny zigzag scan
457 		for (int right = size - 1; right >= 1; right -= 2) {  // Index of right column in each column pair
458 			if (right == 6)
459 				right = 5;
460 			for (int vert = 0; vert < size; vert++) {  // Vertical counter
461 				for (int j = 0; j < 2; j++) {
462 					int x = right - j;  // Actual x coordinate
463 					boolean upward = ((right + 1) & 2) == 0;
464 					int y = upward ? size - 1 - vert : vert;  // Actual y coordinate
465 					if (!isFunction[y][x] && i < data.length * 8) {
466 						modules[y][x] = getBit(data[i >>> 3], 7 - (i & 7));
467 						i++;
468 					}
469 					// If this QR Code has any remainder bits (0 to 7), they were assigned as
470 					// 0/false/light by the constructor and are left unchanged by this method
471 				}
472 			}
473 		}
474 		assert i == data.length * 8;
475 	}
476 
477 
478 	// XORs the codeword modules in this QR Code with the given mask pattern.
479 	// The function modules must be marked and the codeword bits must be drawn
480 	// before masking. Due to the arithmetic of XOR, calling applyMask() with
481 	// the same mask value a second time will undo the mask. A final well-formed
482 	// QR Code needs exactly one (not zero, two, etc.) mask applied.
applyMask(int msk)483 	private void applyMask(int msk) {
484 		if (msk < 0 || msk > 7)
485 			throw new IllegalArgumentException("Mask value out of range");
486 		for (int y = 0; y < size; y++) {
487 			for (int x = 0; x < size; x++) {
488 				boolean invert;
489 				switch (msk) {
490 					case 0:  invert = (x + y) % 2 == 0;                    break;
491 					case 1:  invert = y % 2 == 0;                          break;
492 					case 2:  invert = x % 3 == 0;                          break;
493 					case 3:  invert = (x + y) % 3 == 0;                    break;
494 					case 4:  invert = (x / 3 + y / 2) % 2 == 0;            break;
495 					case 5:  invert = x * y % 2 + x * y % 3 == 0;          break;
496 					case 6:  invert = (x * y % 2 + x * y % 3) % 2 == 0;    break;
497 					case 7:  invert = ((x + y) % 2 + x * y % 3) % 2 == 0;  break;
498 					default:  throw new AssertionError();
499 				}
500 				modules[y][x] ^= invert & !isFunction[y][x];
501 			}
502 		}
503 	}
504 
505 
506 	// A messy helper function for the constructor. This QR Code must be in an unmasked state when this
507 	// method is called. The given argument is the requested mask, which is -1 for auto or 0 to 7 for fixed.
508 	// This method applies and returns the actual mask chosen, from 0 to 7.
handleConstructorMasking(int msk)509 	private int handleConstructorMasking(int msk) {
510 		if (msk == -1) {  // Automatically choose best mask
511 			int minPenalty = Integer.MAX_VALUE;
512 			for (int i = 0; i < 8; i++) {
513 				applyMask(i);
514 				drawFormatBits(i);
515 				int penalty = getPenaltyScore();
516 				if (penalty < minPenalty) {
517 					msk = i;
518 					minPenalty = penalty;
519 				}
520 				applyMask(i);  // Undoes the mask due to XOR
521 			}
522 		}
523 		assert 0 <= msk && msk <= 7;
524 		applyMask(msk);  // Apply the final choice of mask
525 		drawFormatBits(msk);  // Overwrite old format bits
526 		return msk;  // The caller shall assign this value to the final-declared field
527 	}
528 
529 
530 	// Calculates and returns the penalty score based on state of this QR Code's current modules.
531 	// This is used by the automatic mask choice algorithm to find the mask pattern that yields the lowest score.
getPenaltyScore()532 	private int getPenaltyScore() {
533 		int result = 0;
534 
535 		// Adjacent modules in row having same color, and finder-like patterns
536 		for (int y = 0; y < size; y++) {
537 			boolean runColor = false;
538 			int runX = 0;
539 			int[] runHistory = new int[7];
540 			for (int x = 0; x < size; x++) {
541 				if (modules[y][x] == runColor) {
542 					runX++;
543 					if (runX == 5)
544 						result += PENALTY_N1;
545 					else if (runX > 5)
546 						result++;
547 				} else {
548 					finderPenaltyAddHistory(runX, runHistory);
549 					if (!runColor)
550 						result += finderPenaltyCountPatterns(runHistory) * PENALTY_N3;
551 					runColor = modules[y][x];
552 					runX = 1;
553 				}
554 			}
555 			result += finderPenaltyTerminateAndCount(runColor, runX, runHistory) * PENALTY_N3;
556 		}
557 		// Adjacent modules in column having same color, and finder-like patterns
558 		for (int x = 0; x < size; x++) {
559 			boolean runColor = false;
560 			int runY = 0;
561 			int[] runHistory = new int[7];
562 			for (int y = 0; y < size; y++) {
563 				if (modules[y][x] == runColor) {
564 					runY++;
565 					if (runY == 5)
566 						result += PENALTY_N1;
567 					else if (runY > 5)
568 						result++;
569 				} else {
570 					finderPenaltyAddHistory(runY, runHistory);
571 					if (!runColor)
572 						result += finderPenaltyCountPatterns(runHistory) * PENALTY_N3;
573 					runColor = modules[y][x];
574 					runY = 1;
575 				}
576 			}
577 			result += finderPenaltyTerminateAndCount(runColor, runY, runHistory) * PENALTY_N3;
578 		}
579 
580 		// 2*2 blocks of modules having same color
581 		for (int y = 0; y < size - 1; y++) {
582 			for (int x = 0; x < size - 1; x++) {
583 				boolean color = modules[y][x];
584 				if (  color == modules[y][x + 1] &&
585 				      color == modules[y + 1][x] &&
586 				      color == modules[y + 1][x + 1])
587 					result += PENALTY_N2;
588 			}
589 		}
590 
591 		// Balance of dark and light modules
592 		int dark = 0;
593 		for (boolean[] row : modules) {
594 			for (boolean color : row) {
595 				if (color)
596 					dark++;
597 			}
598 		}
599 		int total = size * size;  // Note that size is odd, so dark/total != 1/2
600 		// Compute the smallest integer k >= 0 such that (45-5k)% <= dark/total <= (55+5k)%
601 		int k = (Math.abs(dark * 20 - total * 10) + total - 1) / total - 1;
602 		result += k * PENALTY_N4;
603 		return result;
604 	}
605 
606 
607 
608 	/*---- Private helper functions ----*/
609 
610 	// Returns an ascending list of positions of alignment patterns for this version number.
611 	// Each position is in the range [0,177), and are used on both the x and y axes.
612 	// This could be implemented as lookup table of 40 variable-length lists of unsigned bytes.
getAlignmentPatternPositions()613 	private int[] getAlignmentPatternPositions() {
614 		if (version == 1)
615 			return new int[]{};
616 		else {
617 			int numAlign = version / 7 + 2;
618 			int step;
619 			if (version == 32)  // Special snowflake
620 				step = 26;
621 			else  // step = ceil[(size - 13) / (numAlign * 2 - 2)] * 2
622 				step = (version * 4 + numAlign * 2 + 1) / (numAlign * 2 - 2) * 2;
623 			int[] result = new int[numAlign];
624 			result[0] = 6;
625 			for (int i = result.length - 1, pos = size - 7; i >= 1; i--, pos -= step)
626 				result[i] = pos;
627 			return result;
628 		}
629 	}
630 
631 
632 	// Returns the number of data bits that can be stored in a QR Code of the given version number, after
633 	// all function modules are excluded. This includes remainder bits, so it might not be a multiple of 8.
634 	// The result is in the range [208, 29648]. This could be implemented as a 40-entry lookup table.
getNumRawDataModules(int ver)635 	private static int getNumRawDataModules(int ver) {
636 		if (ver < MIN_VERSION || ver > MAX_VERSION)
637 			throw new IllegalArgumentException("Version number out of range");
638 
639 		int size = ver * 4 + 17;
640 		int result = size * size;   // Number of modules in the whole QR Code square
641 		result -= 8 * 8 * 3;        // Subtract the three finders with separators
642 		result -= 15 * 2 + 1;       // Subtract the format information and dark module
643 		result -= (size - 16) * 2;  // Subtract the timing patterns (excluding finders)
644 		// The five lines above are equivalent to: int result = (16 * ver + 128) * ver + 64;
645 		if (ver >= 2) {
646 			int numAlign = ver / 7 + 2;
647 			result -= (numAlign - 1) * (numAlign - 1) * 25;  // Subtract alignment patterns not overlapping with timing patterns
648 			result -= (numAlign - 2) * 2 * 20;  // Subtract alignment patterns that overlap with timing patterns
649 			// The two lines above are equivalent to: result -= (25 * numAlign - 10) * numAlign - 55;
650 			if (ver >= 7)
651 				result -= 6 * 3 * 2;  // Subtract version information
652 		}
653 		assert 208 <= result && result <= 29648;
654 		return result;
655 	}
656 
657 
658 	// Returns a Reed-Solomon ECC generator polynomial for the given degree. This could be
659 	// implemented as a lookup table over all possible parameter values, instead of as an algorithm.
reedSolomonComputeDivisor(int degree)660 	private static byte[] reedSolomonComputeDivisor(int degree) {
661 		if (degree < 1 || degree > 255)
662 			throw new IllegalArgumentException("Degree out of range");
663 		// Polynomial coefficients are stored from highest to lowest power, excluding the leading term which is always 1.
664 		// For example the polynomial x^3 + 255x^2 + 8x + 93 is stored as the uint8 array {255, 8, 93}.
665 		byte[] result = new byte[degree];
666 		result[degree - 1] = 1;  // Start off with the monomial x^0
667 
668 		// Compute the product polynomial (x - r^0) * (x - r^1) * (x - r^2) * ... * (x - r^{degree-1}),
669 		// and drop the highest monomial term which is always 1x^degree.
670 		// Note that r = 0x02, which is a generator element of this field GF(2^8/0x11D).
671 		int root = 1;
672 		for (int i = 0; i < degree; i++) {
673 			// Multiply the current product by (x - r^i)
674 			for (int j = 0; j < result.length; j++) {
675 				result[j] = (byte)reedSolomonMultiply(result[j] & 0xFF, root);
676 				if (j + 1 < result.length)
677 					result[j] ^= result[j + 1];
678 			}
679 			root = reedSolomonMultiply(root, 0x02);
680 		}
681 		return result;
682 	}
683 
684 
685 	// Returns the Reed-Solomon error correction codeword for the given data and divisor polynomials.
reedSolomonComputeRemainder(byte[] data, byte[] divisor)686 	private static byte[] reedSolomonComputeRemainder(byte[] data, byte[] divisor) {
687 		Objects.requireNonNull(data);
688 		Objects.requireNonNull(divisor);
689 		byte[] result = new byte[divisor.length];
690 		for (byte b : data) {  // Polynomial division
691 			int factor = (b ^ result[0]) & 0xFF;
692 			System.arraycopy(result, 1, result, 0, result.length - 1);
693 			result[result.length - 1] = 0;
694 			for (int i = 0; i < result.length; i++)
695 				result[i] ^= reedSolomonMultiply(divisor[i] & 0xFF, factor);
696 		}
697 		return result;
698 	}
699 
700 
701 	// Returns the product of the two given field elements modulo GF(2^8/0x11D). The arguments and result
702 	// are unsigned 8-bit integers. This could be implemented as a lookup table of 256*256 entries of uint8.
reedSolomonMultiply(int x, int y)703 	private static int reedSolomonMultiply(int x, int y) {
704 		assert x >> 8 == 0 && y >> 8 == 0;
705 		// Russian peasant multiplication
706 		int z = 0;
707 		for (int i = 7; i >= 0; i--) {
708 			z = (z << 1) ^ ((z >>> 7) * 0x11D);
709 			z ^= ((y >>> i) & 1) * x;
710 		}
711 		assert z >>> 8 == 0;
712 		return z;
713 	}
714 
715 
716 	// Returns the number of 8-bit data (i.e. not error correction) codewords contained in any
717 	// QR Code of the given version number and error correction level, with remainder bits discarded.
718 	// This stateless pure function could be implemented as a (40*4)-cell lookup table.
getNumDataCodewords(int ver, Ecc ecl)719 	static int getNumDataCodewords(int ver, Ecc ecl) {
720 		return getNumRawDataModules(ver) / 8
721 			- ECC_CODEWORDS_PER_BLOCK    [ecl.ordinal()][ver]
722 			* NUM_ERROR_CORRECTION_BLOCKS[ecl.ordinal()][ver];
723 	}
724 
725 
726 	// Can only be called immediately after a light run is added, and
727 	// returns either 0, 1, or 2. A helper function for getPenaltyScore().
finderPenaltyCountPatterns(int[] runHistory)728 	private int finderPenaltyCountPatterns(int[] runHistory) {
729 		int n = runHistory[1];
730 		assert n <= size * 3;
731 		boolean core = n > 0 && runHistory[2] == n && runHistory[3] == n * 3 && runHistory[4] == n && runHistory[5] == n;
732 		return (core && runHistory[0] >= n * 4 && runHistory[6] >= n ? 1 : 0)
733 		     + (core && runHistory[6] >= n * 4 && runHistory[0] >= n ? 1 : 0);
734 	}
735 
736 
737 	// Must be called at the end of a line (row or column) of modules. A helper function for getPenaltyScore().
finderPenaltyTerminateAndCount(boolean currentRunColor, int currentRunLength, int[] runHistory)738 	private int finderPenaltyTerminateAndCount(boolean currentRunColor, int currentRunLength, int[] runHistory) {
739 		if (currentRunColor) {  // Terminate dark run
740 			finderPenaltyAddHistory(currentRunLength, runHistory);
741 			currentRunLength = 0;
742 		}
743 		currentRunLength += size;  // Add light border to final run
744 		finderPenaltyAddHistory(currentRunLength, runHistory);
745 		return finderPenaltyCountPatterns(runHistory);
746 	}
747 
748 
749 	// Pushes the given value to the front and drops the last value. A helper function for getPenaltyScore().
finderPenaltyAddHistory(int currentRunLength, int[] runHistory)750 	private void finderPenaltyAddHistory(int currentRunLength, int[] runHistory) {
751 		if (runHistory[0] == 0)
752 			currentRunLength += size;  // Add light border to initial run
753 		System.arraycopy(runHistory, 0, runHistory, 1, runHistory.length - 1);
754 		runHistory[0] = currentRunLength;
755 	}
756 
757 
758 	// Returns true iff the i'th bit of x is set to 1.
getBit(int x, int i)759 	static boolean getBit(int x, int i) {
760 		return ((x >>> i) & 1) != 0;
761 	}
762 
763 
764 	/*---- Constants and tables ----*/
765 
766 	/** The minimum version number  (1) supported in the QR Code Model 2 standard. */
767 	public static final int MIN_VERSION =  1;
768 
769 	/** The maximum version number (40) supported in the QR Code Model 2 standard. */
770 	public static final int MAX_VERSION = 40;
771 
772 
773 	// For use in getPenaltyScore(), when evaluating which mask is best.
774 	private static final int PENALTY_N1 =  3;
775 	private static final int PENALTY_N2 =  3;
776 	private static final int PENALTY_N3 = 40;
777 	private static final int PENALTY_N4 = 10;
778 
779 
780 	private static final byte[][] ECC_CODEWORDS_PER_BLOCK = {
781 		// Version: (note that index 0 is for padding, and is set to an illegal value)
782 		//0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40    Error correction level
783 		{-1,  7, 10, 15, 20, 26, 18, 20, 24, 30, 18, 20, 24, 26, 30, 22, 24, 28, 30, 28, 28, 28, 28, 30, 30, 26, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30},  // Low
784 		{-1, 10, 16, 26, 18, 24, 16, 18, 22, 22, 26, 30, 22, 22, 24, 24, 28, 28, 26, 26, 26, 26, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28},  // Medium
785 		{-1, 13, 22, 18, 26, 18, 24, 18, 22, 20, 24, 28, 26, 24, 20, 30, 24, 28, 28, 26, 30, 28, 30, 30, 30, 30, 28, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30},  // Quartile
786 		{-1, 17, 28, 22, 16, 22, 28, 26, 26, 24, 28, 24, 28, 22, 24, 24, 30, 28, 28, 26, 28, 30, 24, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30},  // High
787 	};
788 
789 	private static final byte[][] NUM_ERROR_CORRECTION_BLOCKS = {
790 		// Version: (note that index 0 is for padding, and is set to an illegal value)
791 		//0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40    Error correction level
792 		{-1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 4,  4,  4,  4,  4,  6,  6,  6,  6,  7,  8,  8,  9,  9, 10, 12, 12, 12, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 24, 25},  // Low
793 		{-1, 1, 1, 1, 2, 2, 4, 4, 4, 5, 5,  5,  8,  9,  9, 10, 10, 11, 13, 14, 16, 17, 17, 18, 20, 21, 23, 25, 26, 28, 29, 31, 33, 35, 37, 38, 40, 43, 45, 47, 49},  // Medium
794 		{-1, 1, 1, 2, 2, 4, 4, 6, 6, 8, 8,  8, 10, 12, 16, 12, 17, 16, 18, 21, 20, 23, 23, 25, 27, 29, 34, 34, 35, 38, 40, 43, 45, 48, 51, 53, 56, 59, 62, 65, 68},  // Quartile
795 		{-1, 1, 1, 2, 4, 4, 4, 5, 6, 8, 8, 11, 11, 16, 16, 18, 16, 19, 21, 25, 25, 25, 34, 30, 32, 35, 37, 40, 42, 45, 48, 51, 54, 57, 60, 63, 66, 70, 74, 77, 81},  // High
796 	};
797 
798 
799 
800 	/*---- Public helper enumeration ----*/
801 
802 	/**
803 	 * The error correction level in a QR Code symbol.
804 	 */
805 	public enum Ecc {
806 		// Must be declared in ascending order of error protection
807 		// so that the implicit ordinal() and values() work properly
808 		/** The QR Code can tolerate about  7% erroneous codewords. */ LOW(1),
809 		/** The QR Code can tolerate about 15% erroneous codewords. */ MEDIUM(0),
810 		/** The QR Code can tolerate about 25% erroneous codewords. */ QUARTILE(3),
811 		/** The QR Code can tolerate about 30% erroneous codewords. */ HIGH(2);
812 
813 		// In the range 0 to 3 (unsigned 2-bit integer).
814 		final int formatBits;
815 
816 		// Constructor.
Ecc(int fb)817 		private Ecc(int fb) {
818 			formatBits = fb;
819 		}
820 	}
821 
822 }
823