core/src/com/google/zxing/common/reedsolomon/GF256.java

   1 /*
   2  * Copyright 2007 Google Inc.
   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 Field GF(256). Operations use the primitive polynomial
  22  * x^8 + x^4 + x^3 + x^2 + 1 in calculations.</p>
  23  *
  24  * <p>Throughout this package, elements of GF(256) are represented as an <code>int</code>
  25  * for convenience and speed (but at the cost of memory).
  26  * Only the bottom 8 bits are really used.</p>
  27  *
  28  * @author srowen@google.com (Sean Owen)
  29  */
  30 final class GF256 {
  31
  32   private static final int PRIMITIVE = 0x011D;
  33   private static final int[] exp = new int[256];
  34   private static final int[] log = new int[256];
  35   static {
  36     int x = 1;
  37     for (int i = 0; i < 256; i++) {
  38       exp[i] = x;
  39       x <<= 1; // x = x * 2; we're assuming the generator alpha is 2
  40       if (x >= 0x100) {
  41         x ^= PRIMITIVE;
  42       }
  43     }
  44     for (int i = 0; i < 255; i++) {
  45       log[exp[i]] = i;
  46     }
  47     // log[0] == 0 but this should never be used
  48   }
  49
  50   private GF256() {
  51   }
  52
  53   /**
  54    * Implements both addition and subtraction -- they are the same in GF(256).
  55    *
  56    * @return sum/difference of a and b
  57    */
  58   static int addOrSubtract(int a, int b) {
  59     return a ^ b;
  60   }
  61
  62   /**
  63    * @return 2 to the power of a in GF(256)
  64    */
  65   static int exp(int a) {
  66     return exp[a];
  67   }
  68
  69   /**
  70    * @return base 2 log of a in GF(256)
  71    */
  72   static int log(int a) {
  73     if (a == 0) {
  74       throw new IllegalArgumentException();
  75     }
  76     return log[a];
  77   }
  78
  79   /**
  80    * @return multiplicative inverse of a
  81    */
  82   static int inverse(int a) {
  83     if (a == 0) {
  84       throw new ArithmeticException();
  85     }
  86     return exp[255 - log[a]];
  87   }
  88
  89   /**
  90    *
  91    * @param a
  92    * @param b
  93    * @return product of a and b in GF(256)
  94    */
  95   static int multiply(int a, int b) {
  96     if (a == 0 || b == 0) {
  97       return 0;
  98     }
  99     if (a == 1) {
 100       return b;
 101     }
 102     if (b == 1) {
 103       return a;
 104     }
 105     return exp[(log[a] + log[b]) % 255];
 106   }
 107
 108 }