cpp/core/src/zxing/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 <zxing/common/reedsolomon/GF256.h>
  25 #include <zxing/common/reedsolomon/GF256Poly.h>
  26 #include <zxing/common/IllegalArgumentException.h>
  27 #include <zxing/common/Array.h>
  28 #include <zxing/common/Counted.h>
  29
  30 namespace zxing {
  31 using namespace std;
  32
  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_((const int)0, 256), log_((const int)0, 256), zero_(refPoly(*this, 0)), one_(refPoly(*this, 1)) {
  46   int x = 1;
  47   for (int i = 0; i < 256; i++) {
  48     exp_[i] = x;
  49     x <<= 1;
  50     if (x >= 0x100) {
  51       x ^= primitive;
  52     }
  53   }
  54
  55   // log(0) == 0, but should never be used
  56   log_[0] = 0;
  57   for (int i = 0; i < 255; i++) {
  58     log_[exp_[i]] = i;
  59   }
  60 }
  61
  62 Ref<GF256Poly> GF256::getZero() {
  63   return zero_;
  64 }
  65
  66 Ref<GF256Poly> GF256::getOne() {
  67   return one_;
  68 }
  69
  70 Ref<GF256Poly> GF256::buildMonomial(int degree, int coefficient) {
  71 #ifdef DEBUG
  72   cout << __FUNCTION__ << "\n";
  73 #endif
  74   if (degree < 0) {
  75     throw IllegalArgumentException("Degree must be non-negative");
  76   }
  77   if (coefficient == 0) {
  78     return zero_;
  79   }
  80   int nCoefficients = degree + 1;
  81   ArrayRef<int> coefficients(new Array<int> (nCoefficients));
  82   coefficients[0] = coefficient;
  83   Ref<GF256Poly> result(new GF256Poly(*this, coefficients));
  84   return result;
  85 }
  86
  87 int GF256::addOrSubtract(int a, int b) {
  88   return a ^ b;
  89 }
  90
  91 int GF256::exp(int a) {
  92   return exp_[a];
  93 }
  94
  95 int GF256::log(int a) {
  96   if (a == 0) {
  97     throw IllegalArgumentException("Cannot take the logarithm of 0");
  98   }
  99   return log_[a];
 100 }
 101
 102 int GF256::inverse(int a) {
 103   if (a == 0) {
 104     throw IllegalArgumentException("Cannot calculate the inverse of 0");
 105   }
 106   return exp_[255 - log_[a]];
 107 }
 108
 109 int GF256::multiply(int a, int b) {
 110   if (a == 0 || b == 0) {
 111     return 0;
 112   }
 113   if (a == 1) {
 114     return b;
 115   }
 116   if (b == 1) {
 117     return a;
 118   }
 119   return exp_[(log_[a] + log_[b]) % 255];
 120 }
 121
 122 GF256 GF256::QR_CODE_FIELD(0x011D); // x^8 + x^4 + x^3 + x^2 + 1
 123 GF256 GF256::DATA_MATRIX_FIELD(0x012D); // x^8 + x^5 + x^3 + x^2 + 1
 124
 125 ostream& operator<<(ostream& out, const GF256& field) {
 126   out << "Field[\nexp=(";
 127   out << field.exp_[0];
 128   for (int i = 1; i < 256; i++) {
 129     out << "," << field.exp_[i];
 130   }
 131   out << "),\nlog=(";
 132   out << field.log_[0];
 133   for (int i = 1; i < 256; i++) {
 134     out << "," << field.log_[i];
 135   }
 136   out << ")\n]";
 137   return out;
 138 }
 139
 140 }