1 /*
2 * Copyright 2007 ZXing authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.zxing.common.reedsolomon;
18
19 /**
20 * <p>This class contains utility methods for performing mathematical operations over
21 * the Galois Fields. Operations use a given primitive polynomial in calculations.</p>
22 *
23 * <p>Throughout this package, elements of the GF are represented as an {@code int}
24 * for convenience and speed (but at the cost of memory).
25 * </p>
26 *
27 * @author Sean Owen
28 * @author David Olivier
29 */
30 public final class GenericGF {
31
32 public static final GenericGF AZTEC_DATA_12 = new GenericGF(0x1069, 4096, 1); // x^12 + x^6 + x^5 + x^3 + 1
33 public static final GenericGF AZTEC_DATA_10 = new GenericGF(0x409, 1024, 1); // x^10 + x^3 + 1
34 public static final GenericGF AZTEC_DATA_6 = new GenericGF(0x43, 64, 1); // x^6 + x + 1
35 public static final GenericGF AZTEC_PARAM = new GenericGF(0x13, 16, 1); // x^4 + x + 1
36 public static final GenericGF QR_CODE_FIELD_256 = new GenericGF(0x011D, 256, 0); // x^8 + x^4 + x^3 + x^2 + 1
37 public static final GenericGF DATA_MATRIX_FIELD_256 = new GenericGF(0x012D, 256, 1); // x^8 + x^5 + x^3 + x^2 + 1
38 public static final GenericGF AZTEC_DATA_8 = DATA_MATRIX_FIELD_256;
39 public static final GenericGF MAXICODE_FIELD_64 = AZTEC_DATA_6;
40
41 private final int[] expTable;
42 private final int[] logTable;
43 private final GenericGFPoly zero;
44 private final GenericGFPoly one;
45 private final int size;
46 private final int primitive;
47 private final int generatorBase;
48
49 /**
50 * Create a representation of GF(size) using the given primitive polynomial.
51 *
52 * @param primitive irreducible polynomial whose coefficients are represented by
53 * the bits of an int, where the least-significant bit represents the constant
54 * coefficient
55 * @param size the size of the field
56 * @param b the factor b in the generator polynomial can be 0- or 1-based
57 * (g(x) = (x+a^b)(x+a^(b+1))...(x+a^(b+2t-1))).
58 * In most cases it should be 1, but for QR code it is 0.
59 */
60 public GenericGF(int primitive, int size, int b) {
61 this.primitive = primitive;
62 this.size = size;
63 this.generatorBase = b;
64
65 expTable = new int[size];
66 logTable = new int[size];
67 int x = 1;
68 for (int i = 0; i < size; i++) {
69 expTable[i] = x;
70 x *= 2; // we're assuming the generator alpha is 2
71 if (x >= size) {
72 x ^= primitive;
73 x &= size - 1;
74 }
75 }
76 for (int i = 0; i < size - 1; i++) {
77 logTable[expTable[i]] = i;
78 }
79 // logTable[0] == 0 but this should never be used
80 zero = new GenericGFPoly(this, new int[]{0});
81 one = new GenericGFPoly(this, new int[]{1});
82 }
83
84 GenericGFPoly getZero() {
85 return zero;
86 }
87
88 GenericGFPoly getOne() {
89 return one;
90 }
91
92 /**
93 * @return the monomial representing coefficient * x^degree
94 */
95 GenericGFPoly buildMonomial(int degree, int coefficient) {
96 if (degree < 0) {
97 throw new IllegalArgumentException();
98 }
99 if (coefficient == 0) {
100 return zero;
101 }
102 int[] coefficients = new int[degree + 1];
103 coefficients[0] = coefficient;
104 return new GenericGFPoly(this, coefficients);
105 }
106
107 /**
108 * Implements both addition and subtraction -- they are the same in GF(size).
109 *
110 * @return sum/difference of a and b
111 */
112 static int addOrSubtract(int a, int b) {
113 return a ^ b;
114 }
115
116 /**
117 * @return 2 to the power of a in GF(size)
118 */
119 int exp(int a) {
120 return expTable[a];
121 }
122
123 /**
124 * @return base 2 log of a in GF(size)
125 */
126 int log(int a) {
127 if (a == 0) {
128 throw new IllegalArgumentException();
129 }
130 return logTable[a];
131 }
132
133 /**
134 * @return multiplicative inverse of a
135 */
136 int inverse(int a) {
137 if (a == 0) {
138 throw new ArithmeticException();
139 }
140 return expTable[size - logTable[a] - 1];
141 }
142
143 /**
144 * @return product of a and b in GF(size)
145 */
146 int multiply(int a, int b) {
147 if (a == 0 || b == 0) {
148 return 0;
149 }
150 return expTable[(logTable[a] + logTable[b]) % (size - 1)];
151 }
152
153 public int getSize() {
154 return size;
155 }
156
157 public int getGeneratorBase() {
158 return generatorBase;
159 }
160
161 @Override
162 public String toString() {
163 return "GF(0x" + Integer.toHexString(primitive) + ',' + size + ')';
164 }
165
166 }
167