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