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 −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 −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 ≤ minVersion ≤ maxVersion ≤ 40 139 * or −1 ≤ mask ≤ 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 × 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 * −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 −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−1 is the right edge 278 * @param y the y coordinate, where 0 is the top edge and size−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