extensions/net.sf.basedb.otp/trunk/src/io/nayuki/qrcodegen/QrCode.java

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

Generated on Tue Nov 21 03:28:52 2023 (UTC) by svndigest 0.11.2pre (dev build 1672)