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).</p> 25 * 26 * <p>The size of the GF is assumed to be a power of two.</p> 27 * 28 * @author Sean Owen 29 * @author David Olivier 30 */ 31 public final class GenericGF { 32 33 public static final GenericGF AZTEC_DATA_12 = new GenericGF(0b1000001101001, 4096, 1); // x^12 + x^6 + x^5 + x^3 + 1 34 public static final GenericGF AZTEC_DATA_10 = new GenericGF(0b10000001001, 1024, 1); // x^10 + x^3 + 1 35 public static final GenericGF AZTEC_DATA_6 = new GenericGF(0b1000011, 64, 1); // x^6 + x + 1 36 public static final GenericGF AZTEC_PARAM = new GenericGF(0b10011, 16, 1); // x^4 + x + 1 37 public static final GenericGF QR_CODE_FIELD_256 = new GenericGF(0b100011101, 256, 0); // x^8 + x^4 + x^3 + x^2 + 1 38 public static final GenericGF DATA_MATRIX_FIELD_256 = new GenericGF(0b100101101, 256, 1); // x^8 + x^5 + x^3 + x^2 + 1 39 public static final GenericGF AZTEC_DATA_8 = DATA_MATRIX_FIELD_256; 40 public static final GenericGF MAXICODE_FIELD_64 = AZTEC_DATA_6; 41 42 private final int[] expTable; 43 private final int[] logTable; 44 private final GenericGFPoly zero; 45 private final GenericGFPoly one; 46 private final int size; 47 private final int primitive; 48 private final int generatorBase; 49 50 /** 51 * Create a representation of GF(size) using the given primitive polynomial. 52 * 53 * @param primitive irreducible polynomial whose coefficients are represented by 54 * the bits of an int, where the least-significant bit represents the constant 55 * coefficient 56 * @param size the size of the field 57 * @param b the factor b in the generator polynomial can be 0- or 1-based 58 * (g(x) = (x+a^b)(x+a^(b+1))...(x+a^(b+2t-1))). 59 * In most cases it should be 1, but for QR code it is 0. 60 */ GenericGF(int primitive, int size, int b)61 public GenericGF(int primitive, int size, int b) { 62 this.primitive = primitive; 63 this.size = size; 64 this.generatorBase = b; 65 66 expTable = new int[size]; 67 logTable = new int[size]; 68 int x = 1; 69 for (int i = 0; i < size; i++) { 70 expTable[i] = x; 71 x *= 2; // 2 (the polynomial x) is a primitive element 72 if (x >= size) { 73 x ^= primitive; 74 x &= size - 1; 75 } 76 } 77 for (int i = 0; i < size - 1; i++) { 78 logTable[expTable[i]] = i; 79 } 80 // logTable[0] == 0 but this should never be used 81 zero = new GenericGFPoly(this, new int[]{0}); 82 one = new GenericGFPoly(this, new int[]{1}); 83 } 84 getZero()85 GenericGFPoly getZero() { 86 return zero; 87 } 88 getOne()89 GenericGFPoly getOne() { 90 return one; 91 } 92 93 /** 94 * @return the monomial representing coefficient * x^degree 95 */ buildMonomial(int degree, int coefficient)96 GenericGFPoly buildMonomial(int degree, int coefficient) { 97 if (degree < 0) { 98 throw new IllegalArgumentException(); 99 } 100 if (coefficient == 0) { 101 return zero; 102 } 103 int[] coefficients = new int[degree + 1]; 104 coefficients[0] = coefficient; 105 return new GenericGFPoly(this, coefficients); 106 } 107 108 /** 109 * Implements both addition and subtraction -- they are the same in GF(size). 110 * 111 * @return sum/difference of a and b 112 */ addOrSubtract(int a, int b)113 static int addOrSubtract(int a, int b) { 114 return a ^ b; 115 } 116 117 /** 118 * @return 2 to the power of a in GF(size) 119 */ exp(int a)120 int exp(int a) { 121 return expTable[a]; 122 } 123 124 /** 125 * @return base 2 log of a in GF(size) 126 */ log(int a)127 int log(int a) { 128 if (a == 0) { 129 throw new IllegalArgumentException(); 130 } 131 return logTable[a]; 132 } 133 134 /** 135 * @return multiplicative inverse of a 136 */ inverse(int a)137 int inverse(int a) { 138 if (a == 0) { 139 throw new ArithmeticException(); 140 } 141 return expTable[size - logTable[a] - 1]; 142 } 143 144 /** 145 * @return product of a and b in GF(size) 146 */ multiply(int a, int b)147 int multiply(int a, int b) { 148 if (a == 0 || b == 0) { 149 return 0; 150 } 151 return expTable[(logTable[a] + logTable[b]) % (size - 1)]; 152 } 153 getSize()154 public int getSize() { 155 return size; 156 } 157 getGeneratorBase()158 public int getGeneratorBase() { 159 return generatorBase; 160 } 161 162 @Override toString()163 public String toString() { 164 return "GF(0x" + Integer.toHexString(primitive) + ',' + size + ')'; 165 } 166 167 } 168