1 /* 2 * Fast QR Code generator library 3 * 4 * Copyright (c) Project Nayuki. (MIT License) 5 * https://www.nayuki.io/page/fast-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.fastqrcodegen; 25 26 import java.util.Arrays; 27 import java.util.Objects; 28 29 30 // Computes Reed-Solomon error correction codewords for given data codewords. 31 final class ReedSolomonGenerator { 32 33 // Use this memoizer to get instances of this class. 34 public static final Memoizer<Integer,ReedSolomonGenerator> MEMOIZER 35 = new Memoizer<>(ReedSolomonGenerator::new); 36 37 38 // A table of size 256 * degree, where polynomialMultiply[i][j] = multiply(i, coefficients[j]). 39 // 'coefficients' is the temporary array computed in the constructor. 40 private byte[][] polynomialMultiply; 41 42 43 // Creates a Reed-Solomon ECC generator polynomial for the given degree. ReedSolomonGenerator(int degree)44 private ReedSolomonGenerator(int degree) { 45 if (degree < 1 || degree > 255) 46 throw new IllegalArgumentException("Degree out of range"); 47 48 // The divisor polynomial, whose coefficients are stored from highest to lowest power. 49 // For example, x^3 + 255x^2 + 8x + 93 is stored as the uint8 array {255, 8, 93}. 50 byte[] coefficients = new byte[degree]; 51 coefficients[degree - 1] = 1; // Start off with the monomial x^0 52 53 // Compute the product polynomial (x - r^0) * (x - r^1) * (x - r^2) * ... * (x - r^{degree-1}), 54 // and drop the highest monomial term which is always 1x^degree. 55 // Note that r = 0x02, which is a generator element of this field GF(2^8/0x11D). 56 int root = 1; 57 for (int i = 0; i < degree; i++) { 58 // Multiply the current product by (x - r^i) 59 for (int j = 0; j < coefficients.length; j++) { 60 coefficients[j] = (byte)multiply(coefficients[j] & 0xFF, root); 61 if (j + 1 < coefficients.length) 62 coefficients[j] ^= coefficients[j + 1]; 63 } 64 root = multiply(root, 0x02); 65 } 66 67 polynomialMultiply = new byte[256][degree]; 68 for (int i = 0; i < polynomialMultiply.length; i++) { 69 for (int j = 0; j < degree; j++) 70 polynomialMultiply[i][j] = (byte)multiply(i, coefficients[j] & 0xFF); 71 } 72 } 73 74 75 // Returns the error correction codeword for the given data polynomial and this divisor polynomial. getRemainder(byte[] data, int dataOff, int dataLen, byte[] result)76 public void getRemainder(byte[] data, int dataOff, int dataLen, byte[] result) { 77 Objects.requireNonNull(data); 78 Objects.requireNonNull(result); 79 int degree = polynomialMultiply[0].length; 80 assert result.length == degree; 81 82 Arrays.fill(result, (byte)0); 83 for (int i = dataOff, dataEnd = dataOff + dataLen; i < dataEnd; i++) { // Polynomial division 84 byte[] table = polynomialMultiply[(data[i] ^ result[0]) & 0xFF]; 85 for (int j = 0; j < degree - 1; j++) 86 result[j] = (byte)(result[j + 1] ^ table[j]); 87 result[degree - 1] = table[degree - 1]; 88 } 89 } 90 91 92 // Returns the product of the two given field elements modulo GF(2^8/0x11D). The arguments and result 93 // are unsigned 8-bit integers. This could be implemented as a lookup table of 256*256 entries of uint8. multiply(int x, int y)94 private static int multiply(int x, int y) { 95 assert x >> 8 == 0 && y >> 8 == 0; 96 // Russian peasant multiplication 97 int z = 0; 98 for (int i = 7; i >= 0; i--) { 99 z = (z << 1) ^ ((z >>> 7) * 0x11D); 100 z ^= ((y >>> i) & 1) * x; 101 } 102 assert z >>> 8 == 0; 103 return z; 104 } 105 106 } 107