cpp/core/src/common/reedsolomon/GF256Poly.cpp

   1 /*
   2  *  GF256Poly.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 <iostream>
  22 #include <sstream>
  23 #include "GF256Poly.h"
  24 #include "GF256.h"
  25 #include "../IllegalArgumentException.h"
  26
  27 using namespace common;
  28
  29 namespace reedsolomon {
  30
  31   void GF256Poly::fixCoefficients() {
  32     int coefficientsLength = coefficients.size();
  33     if (coefficientsLength > 1 && coefficients[0] == 0) {
  34       // Leading term must be non-zero for anything except
  35       // the constant polynomial "0"
  36       int firstNonZero = 1;
  37       while (firstNonZero < coefficientsLength &&
  38              coefficients[firstNonZero] == 0) {
  39         firstNonZero++;
  40       }
  41       if (firstNonZero == coefficientsLength) {
  42         coefficientsLength = field.getZero()->coefficients.size();
  43         coefficients.reset(new Array<int>(coefficientsLength));
  44         *coefficients = *(field.getZero()->coefficients);
  45       } else {
  46         ArrayRef<int>c(coefficients);
  47         coefficientsLength -= firstNonZero;
  48         coefficients.reset(new Array<int>(coefficientsLength));
  49         for (int i = 0; i < coefficientsLength; i++) {
  50           coefficients[i] = c[i + firstNonZero];
  51         }
  52       }
  53     }
  54   }
  55
  56   GF256Poly::GF256Poly(GF256 &f, ArrayRef<int> c) :
  57   Counted(), field(f), coefficients(c) {
  58 #ifdef DEBUG
  59     cout << "instantiating GF256Poly @ " << this << " with Array " << c.array_ << "(" << c.array_->count_ << "), size " << c.size() << ", ";
  60     cout << "coefficients size = " << coefficients.size() << "\n";
  61 #endif
  62     fixCoefficients();
  63   }
  64
  65   GF256Poly::~GF256Poly() {
  66 #ifdef DEBUG
  67     cout << "destroying GF256Poly @ " << this << "\n";
  68 #endif
  69   }
  70
  71   int GF256Poly::getDegree() {
  72     return coefficients.size() - 1;
  73   }
  74
  75   bool GF256Poly::isZero() {
  76     return coefficients[0] == 0;
  77   }
  78
  79   int GF256Poly::getCoefficient(int degree) {
  80     return coefficients[coefficients.size() - 1 - degree];
  81   }
  82
  83   int GF256Poly::evaluateAt(int a) {
  84     if (a == 0) {
  85       return getCoefficient(0);
  86     }
  87     int size = coefficients.size();
  88     if (a == 1) {
  89       // Just the sum of the coefficients
  90       int result = 0;
  91       for (int i = 0; i < size; i++) {
  92         result = GF256::addOrSubtract(result, coefficients[i]);
  93       }
  94       return result;
  95     }
  96     int result = coefficients[0];
  97     for (int i = 1; i < size; i++) {
  98       result = GF256::addOrSubtract(field.multiply(a, result),
  99                                     coefficients[i]);
 100     }
 101     return result;
 102   }
 103
 104   GF256Poly *GF256Poly::addOrSubtract(GF256Poly *b) {
 105     if (&field != &b->field) {
 106       throw new IllegalArgumentException("Fields must be the same");
 107     }
 108     if (isZero()) {
 109       return b;
 110     }
 111     if (b->isZero()) {
 112       return this;
 113     }
 114
 115     ArrayRef<int> largerCoefficients = coefficients;
 116     ArrayRef<int> smallerCoefficients = b->coefficients;
 117     if (smallerCoefficients.size() > largerCoefficients.size()) {
 118       ArrayRef<int> tmp(smallerCoefficients);
 119       smallerCoefficients = largerCoefficients;
 120       largerCoefficients = tmp;
 121     }
 122
 123     ArrayRef<int> sumDiff(new Array<int>(largerCoefficients.size()));
 124
 125     unsigned lengthDiff = largerCoefficients.size() - smallerCoefficients.size();
 126     for (unsigned i = 0; i < lengthDiff; i++) {
 127       sumDiff[i] = largerCoefficients[i];
 128     }
 129     for (unsigned i = lengthDiff; i < largerCoefficients.size(); i++) {
 130       sumDiff[i] = GF256::addOrSubtract(smallerCoefficients[i - lengthDiff],
 131                                             largerCoefficients[i]);
 132     }
 133     return new GF256Poly(field, sumDiff);
 134   }
 135
 136   GF256Poly *GF256Poly::multiply(GF256Poly *b) {
 137     if (&field != &b->field) {
 138       throw new IllegalArgumentException("Fields must be the same");
 139     }
 140     if (isZero() || b->isZero()) {
 141       return field.getZero();
 142     }
 143     ArrayRef<int> aCoefficients = coefficients;
 144     int aLength = aCoefficients.size();
 145     ArrayRef<int> bCoefficients = b->coefficients;
 146     int bLength = bCoefficients.size();
 147     int productLength = aLength + bLength - 1;
 148     ArrayRef<int> product(new Array<int>(productLength));
 149     for (int i = 0; i < aLength; i++) {
 150       int aCoeff = aCoefficients[i];
 151       for (int j = 0; j < bLength; j++) {
 152         product[i + j] =
 153         GF256::addOrSubtract(product[i + j],
 154                              field.multiply(aCoeff, bCoefficients[j]));
 155       }
 156     }
 157
 158     return new GF256Poly(field, product);
 159   }
 160
 161   GF256Poly *GF256Poly::multiply(int scalar) {
 162     if (scalar == 0) {
 163       return field.getZero();
 164     }
 165     if (scalar == 1) {
 166       return this;
 167     }
 168     int size = coefficients.size();
 169     ArrayRef<int> product(new Array<int>(size));
 170     for (int i = 0; i < size; i++) {
 171       product[i] = field.multiply(coefficients[i], scalar);
 172     }
 173     return new GF256Poly(field, product);
 174   }
 175
 176   GF256Poly *GF256Poly::multiplyByMonomial(int degree,
 177                                            int coefficient) {
 178     if (degree < 0) {
 179       throw new IllegalArgumentException("Degree must be non-negative");
 180     }
 181     if (coefficient == 0) {
 182       return field.getZero();
 183     }
 184     int size = coefficients.size();
 185     ArrayRef<int> product (new Array<int>(size + degree));
 186     for (int i = 0; i < size; i++) {
 187       product[i] = field.multiply(coefficients[i], coefficient);
 188     }
 189     return new GF256Poly(field, product);
 190   }
 191
 192   const char *GF256Poly::description() const {
 193     ostringstream result;
 194     result << *this;
 195     return result.str().c_str();
 196   }
 197
 198
 199   ostream& operator<<(ostream& out, const GF256Poly& p)
 200   {
 201     GF256Poly &poly = const_cast<GF256Poly&>(p);
 202     out << "Poly[" << poly.coefficients.size() << "]";
 203     if (poly.coefficients.size() > 0) {
 204       out << "(" << poly.coefficients[0];
 205       for (unsigned i = 1; i < poly.coefficients.size(); i++) {
 206         out << "," << poly.coefficients[i];
 207       }
 208       out << ")";
 209     }
 210     return out;
 211   }
 212
 213 }