Pileus Git - ~andy/freeotp/blob - src/com/google/zxing/common/reedsolomon/GenericGF.java

   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 static final int INITIALIZATION_THRESHOLD = 0;
  42
  43   private int[] expTable;
  44   private int[] logTable;
  45   private GenericGFPoly zero;
  46   private GenericGFPoly one;
  47   private final int size;
  48   private final int primitive;
  49   private final int generatorBase;
  50   private boolean initialized = false;
  51
  52   /**
  53    * Create a representation of GF(size) using the given primitive polynomial.
  54    *
  55    * @param primitive irreducible polynomial whose coefficients are represented by
  56    *  the bits of an int, where the least-significant bit represents the constant
  57    *  coefficient
  58    * @param size the size of the field
  59    * @param b the factor b in the generator polynomial can be 0- or 1-based
  60    *  (g(x) = (x+a^b)(x+a^(b+1))...(x+a^(b+2t-1))).
  61    *  In most cases it should be 1, but for QR code it is 0.
  62    */
  63   public GenericGF(int primitive, int size, int b) {
  64         this.primitive = primitive;
  65     this.size = size;
  66     this.generatorBase = b;
  67
  68     if (size <= INITIALIZATION_THRESHOLD) {
  69         initialize();
  70     }
  71   }
  72
  73   private void initialize() {
  74     expTable = new int[size];
  75     logTable = new int[size];
  76     int x = 1;
  77     for (int i = 0; i < size; i++) {
  78       expTable[i] = x;
  79       x <<= 1; // x = x * 2; we're assuming the generator alpha is 2
  80       if (x >= size) {
  81         x ^= primitive;
  82         x &= size-1;
  83       }
  84     }
  85     for (int i = 0; i < size-1; i++) {
  86       logTable[expTable[i]] = i;
  87     }
  88     // logTable[0] == 0 but this should never be used
  89     zero = new GenericGFPoly(this, new int[]{0});
  90     one = new GenericGFPoly(this, new int[]{1});
  91     initialized = true;
  92   }
  93
  94   private void checkInit() {
  95         if (!initialized) {
  96       initialize();
  97     }
  98   }
  99
 100   GenericGFPoly getZero() {
 101         checkInit();
 102
 103     return zero;
 104   }
 105
 106   GenericGFPoly getOne() {
 107         checkInit();
 108
 109     return one;
 110   }
 111
 112   /**
 113    * @return the monomial representing coefficient * x^degree
 114    */
 115   GenericGFPoly buildMonomial(int degree, int coefficient) {
 116         checkInit();
 117
 118     if (degree < 0) {
 119       throw new IllegalArgumentException();
 120     }
 121     if (coefficient == 0) {
 122       return zero;
 123     }
 124     int[] coefficients = new int[degree + 1];
 125     coefficients[0] = coefficient;
 126     return new GenericGFPoly(this, coefficients);
 127   }
 128
 129   /**
 130    * Implements both addition and subtraction -- they are the same in GF(size).
 131    *
 132    * @return sum/difference of a and b
 133    */
 134   static int addOrSubtract(int a, int b) {
 135     return a ^ b;
 136   }
 137
 138   /**
 139    * @return 2 to the power of a in GF(size)
 140    */
 141   int exp(int a) {
 142         checkInit();
 143
 144     return expTable[a];
 145   }
 146
 147   /**
 148    * @return base 2 log of a in GF(size)
 149    */
 150   int log(int a) {
 151         checkInit();
 152
 153     if (a == 0) {
 154       throw new IllegalArgumentException();
 155     }
 156     return logTable[a];
 157   }
 158
 159   /**
 160    * @return multiplicative inverse of a
 161    */
 162   int inverse(int a) {
 163         checkInit();
 164
 165     if (a == 0) {
 166       throw new ArithmeticException();
 167     }
 168     return expTable[size - logTable[a] - 1];
 169   }
 170
 171   /**
 172    * @return product of a and b in GF(size)
 173    */
 174   int multiply(int a, int b) {
 175         checkInit();
 176
 177     if (a == 0 || b == 0) {
 178       return 0;
 179     }
 180     return expTable[(logTable[a] + logTable[b]) % (size - 1)];
 181   }
 182
 183   public int getSize() {
 184         return size;
 185   }
 186
 187   public int getGeneratorBase() {
 188     return generatorBase;
 189   }
 190
 191   @Override
 192   public String toString() {
 193     return "GF(0x" + Integer.toHexString(primitive) + ',' + size + ')';
 194   }
 195
 196 }