cpp/core/src/common/reedsolomon/GF256.cpp

   1 /*
   2  *  GF256.cpp
   3  *  zxing
   4  *
   5  *  Created by Christian Brunschen on 05/05/2008.
   6  *  Copyright 2008 Google UK. All rights reserved.
   7  *
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  */
  20
  21 #include <valarray>
  22 #include <vector>
  23 #include <iostream>
  24 #include "GF256.h"
  25 #include "GF256Poly.h"
  26 #include "../IllegalArgumentException.h"
  27 #include "../Array.h"
  28 #include "../Counted.h"
  29
  30 using namespace common;
  31
  32 namespace reedsolomon {
  33   static inline ArrayRef<int> makeArray(int value) {
  34     ArrayRef<int> valuesRef(new Array<int>(value, 1));
  35     return valuesRef;
  36   }
  37
  38   static inline Ref<GF256Poly> refPoly(GF256 &field, int value) {
  39     ArrayRef<int> values(makeArray(value));
  40     Ref<GF256Poly> result(new GF256Poly(field, values));
  41     return result;
  42   }
  43
  44   GF256::GF256(int primitive) :
  45   exp_(256),
  46   log_(256),
  47   zero_(refPoly(*this, 0)),
  48   one_(refPoly(*this, 1)) {
  49     int x = 1;
  50     for (int i = 0; i < 256; i++) {
  51       exp_[i] = x;
  52       x <<= 1;
  53       if (x >= 0x100) {
  54         x ^= primitive;
  55       }
  56
  57       // log(0) == 0, but should never be used
  58       log_[0] = 0;
  59       for (int i = 0; i < 255; i++) {
  60         log_[exp_[i]] = i;
  61       }
  62     }
  63   }
  64
  65   Ref<GF256Poly> GF256::getZero() {
  66     return zero_;
  67   }
  68
  69   Ref<GF256Poly> GF256::getOne() {
  70     return one_;
  71   }
  72
  73   Ref<GF256Poly> GF256::buildMonomial(int degree, int coefficient) {
  74 #ifdef DEBUG
  75     cout << __FUNCTION__ << "\n";
  76 #endif
  77     if (degree < 0) {
  78       throw new IllegalArgumentException("Degree must be non-negative");
  79     }
  80     if (coefficient == 0) {
  81       return zero_;
  82     }
  83     int nCoefficients = degree + 1;
  84     ArrayRef<int> coefficients(new Array<int>(nCoefficients));
  85     coefficients[0] = coefficient;
  86     Ref<GF256Poly> result(new GF256Poly(*this, coefficients));
  87     return result;
  88   }
  89
  90   int GF256::addOrSubtract(int a, int b) {
  91     return a ^ b;
  92   }
  93
  94   int GF256::exp(int a) {
  95     return exp_[a];
  96   }
  97
  98   int GF256::log(int a) {
  99     if (a == 0) {
 100       throw new IllegalArgumentException("Cannot take the logarithm of 0");
 101     }
 102     return log_[a];
 103   }
 104
 105   int GF256::inverse(int a) {
 106     if (a == 0) {
 107       throw new IllegalArgumentException("Cannot calculate the inverse of 0");
 108     }
 109     return exp_[255 - log_[a]];
 110   }
 111
 112   int GF256::multiply(int a, int b) {
 113     if (a == 0 || b == 0) {
 114       return 0;
 115     }
 116     if (a == 1) {
 117       return b;
 118     }
 119     if (b == 1) {
 120       return a;
 121     }
 122     return exp_[(log_[a] + log_[b]) % 255];
 123   }
 124
 125   GF256 GF256::QR_CODE_FIELD(0x011D); // x^8 + x^4 + x^3 + x^2 + 1
 126   GF256 GF256::DATA_MATRIX_FIELD(0x012D);  // x^8 + x^5 + x^3 + x^2 + 1
 127
 128   ostream& operator<<(ostream& out, const GF256& field)
 129   {
 130     out << "Field[\nexp=(";
 131     out << field.exp_[0];
 132     for (int i = 1; i < 256; i++) {
 133       out << "," << field.exp_[i];
 134     }
 135     out << "),\nlog=(";
 136     out << field.log_[0];
 137     for (int i = 1; i < 256; i++) {
 138       out << "," << field.log_[i];
 139     }
 140     out << ")\n]";
 141     return out;
 142   }
 143
 144 }