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
24package io.nayuki.fastqrcodegen;
25
26import java.util.Arrays;
27import java.util.Objects;
28
29
30// Computes Reed-Solomon error correction codewords for given data codewords.
31final 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.
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.
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.
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