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
  36   static {
  37     int x = 1;
  38     for (int i = 0; i < 256; i++) {
  39       exp[i] = x;
  40       x <<= 1; // x = x * 2; we're assuming the generator alpha is 2
  41       if (x >= 0x100) {
  42         x ^= PRIMITIVE;
  43       }
  44     }
  45     for (int i = 0; i < 255; i++) {
  46       log[exp[i]] = i;
  47     }
  48     // log[0] == 0 but this should never be used
  49   }
  50
  51   private GF256() {
  52   }
  53
  54   /**
  55    * Implements both addition and subtraction -- they are the same in GF(256).
  56    *
  57    * @return sum/difference of a and b
  58    */
  59   static int addOrSubtract(int a, int b) {
  60     return a ^ b;
  61   }
  62
  63   /**
  64    * @return 2 to the power of a in GF(256)
  65    */
  66   static int exp(int a) {
  67     return exp[a];
  68   }
  69
  70   /**
  71    * @return base 2 log of a in GF(256)
  72    */
  73   static int log(int a) {
  74     if (a == 0) {
  75       throw new IllegalArgumentException();
  76     }
  77     return log[a];
  78   }
  79
  80   /**
  81    * @return multiplicative inverse of a
  82    */
  83   static int inverse(int a) {
  84     if (a == 0) {
  85       throw new ArithmeticException();
  86     }
  87     return exp[255 - log[a]];
  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 }