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