csharp/common/reedsolomon/GF256.cs

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