symbian/QQrDecoder/zxing/common/reedsolomon/ReedSolomonDecoder.cpp

   1 /*
   2  *  ReedSolomonDecoder.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
  23 #include <memory>
  24 #include <zxing/common/reedsolomon/ReedSolomonDecoder.h>
  25 #include <zxing/common/reedsolomon/GF256.h>
  26 #include <zxing/common/reedsolomon/GF256Poly.h>
  27 #include <zxing/common/reedsolomon/ReedSolomonException.h>
  28 #include <zxing/common/IllegalArgumentException.h>
  29
  30 using namespace std;
  31
  32 namespace zxing {
  33
  34 ReedSolomonDecoder::ReedSolomonDecoder(GF256 &fld) :
  35     field(fld) {
  36 }
  37
  38 ReedSolomonDecoder::~ReedSolomonDecoder() {
  39 }
  40
  41 void ReedSolomonDecoder::decode(ArrayRef<int> received, int twoS) {
  42
  43   Ref<GF256Poly> poly(new GF256Poly(field, received));
  44
  45
  46 #ifdef DEBUG
  47   cout << "decoding with poly " << *poly << "\n";
  48 #endif
  49
  50   ArrayRef<int> syndromeCoefficients(new Array<int> (twoS));
  51
  52
  53 #ifdef DEBUG
  54   cout << "syndromeCoefficients array = " <<
  55        syndromeCoefficients.array_ << "\n";
  56 #endif
  57
  58   bool noError = true;
  59   for (int i = 0; i < twoS; i++) {
  60     int eval = poly->evaluateAt(field.exp(i));
  61     syndromeCoefficients[syndromeCoefficients->size() - 1 - i] = eval;
  62     if (eval != 0) {
  63       noError = false;
  64     }
  65   }
  66   if (noError) {
  67     return;
  68   }
  69
  70   Ref<GF256Poly> syndrome(new GF256Poly(field, syndromeCoefficients));
  71   Ref<GF256Poly> monomial(field.buildMonomial(twoS, 1));
  72   vector<Ref<GF256Poly> > sigmaOmega(runEuclideanAlgorithm(monomial, syndrome, twoS));
  73   ArrayRef<int> errorLocations = findErrorLocations(sigmaOmega[0]);
  74   ArrayRef<int> errorMagitudes = findErrorMagnitudes(sigmaOmega[1], errorLocations);
  75   for (unsigned i = 0; i < errorLocations->size(); i++) {
  76     int position = received->size() - 1 - field.log(errorLocations[i]);
  77     //TODO: check why the position would be invalid
  78     if (position < 0 || (size_t)position >= received.size())
  79       throw IllegalArgumentException("Invalid position (ReedSolomonDecoder)");
  80     received[position] = GF256::addOrSubtract(received[position], errorMagitudes[i]);
  81   }
  82 }
  83
  84 vector<Ref<GF256Poly> > ReedSolomonDecoder::runEuclideanAlgorithm(Ref<GF256Poly> a, Ref<GF256Poly> b, int R) {
  85   // Assume a's degree is >= b's
  86   if (a->getDegree() < b->getDegree()) {
  87     Ref<GF256Poly> tmp = a;
  88     a = b;
  89     b = tmp;
  90   }
  91
  92   Ref<GF256Poly> rLast(a);
  93   Ref<GF256Poly> r(b);
  94   Ref<GF256Poly> sLast(field.getOne());
  95   Ref<GF256Poly> s(field.getZero());
  96   Ref<GF256Poly> tLast(field.getZero());
  97   Ref<GF256Poly> t(field.getOne());
  98
  99
 100   // Run Euclidean algorithm until r's degree is less than R/2
 101   while (r->getDegree() >= R / 2) {
 102     Ref<GF256Poly> rLastLast(rLast);
 103     Ref<GF256Poly> sLastLast(sLast);
 104     Ref<GF256Poly> tLastLast(tLast);
 105     rLast = r;
 106     sLast = s;
 107     tLast = t;
 108
 109
 110     // Divide rLastLast by rLast, with quotient q and remainder r
 111     if (rLast->isZero()) {
 112       // Oops, Euclidean algorithm already terminated?
 113       throw ReedSolomonException("r_{i-1} was zero");
 114     }
 115     r = rLastLast;
 116     Ref<GF256Poly> q(field.getZero());
 117     int denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());
 118     int dltInverse = field.inverse(denominatorLeadingTerm);
 119     while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {
 120       int degreeDiff = r->getDegree() - rLast->getDegree();
 121       int scale = field.multiply(r->getCoefficient(r->getDegree()), dltInverse);
 122       q = q->addOrSubtract(field.buildMonomial(degreeDiff, scale));
 123       r = r->addOrSubtract(rLast->multiplyByMonomial(degreeDiff, scale));
 124     }
 125
 126     s = q->multiply(sLast)->addOrSubtract(sLastLast);
 127     t = q->multiply(tLast)->addOrSubtract(tLastLast);
 128   }
 129
 130   int sigmaTildeAtZero = t->getCoefficient(0);
 131   if (sigmaTildeAtZero == 0) {
 132     throw ReedSolomonException("sigmaTilde(0) was zero");
 133   }
 134
 135   int inverse = field.inverse(sigmaTildeAtZero);
 136   Ref<GF256Poly> sigma(t->multiply(inverse));
 137   Ref<GF256Poly> omega(r->multiply(inverse));
 138
 139
 140 #ifdef DEBUG
 141   cout << "t = " << *t << "\n";
 142   cout << "r = " << *r << "\n";
 143   cout << "sigma = " << *sigma << "\n";
 144   cout << "omega = " << *omega << "\n";
 145 #endif
 146
 147   vector<Ref<GF256Poly> > result(2);
 148   result[0] = sigma;
 149   result[1] = omega;
 150   return result;
 151 }
 152
 153 ArrayRef<int> ReedSolomonDecoder::findErrorLocations(Ref<GF256Poly> errorLocator) {
 154   // This is a direct application of Chien's search
 155   int numErrors = errorLocator->getDegree();
 156   if (numErrors == 1) { // shortcut
 157     ArrayRef<int> result(1);
 158     result[0] = errorLocator->getCoefficient(1);
 159     return result;
 160   }
 161   ArrayRef<int> result(numErrors);
 162   int e = 0;
 163   for (int i = 1; i < 256 && e < numErrors; i++) {
 164     // cout << "errorLocator(" << i << ") == " << errorLocator->evaluateAt(i) << "\n";
 165     if (errorLocator->evaluateAt(i) == 0) {
 166       result[e] = field.inverse(i);
 167       e++;
 168     }
 169   }
 170   if (e != numErrors) {
 171     throw ReedSolomonException("Error locator degree does not match number of roots");
 172   }
 173   return result;
 174 }
 175
 176 ArrayRef<int> ReedSolomonDecoder::findErrorMagnitudes(Ref<GF256Poly> errorEvaluator, ArrayRef<int> errorLocations) {
 177   // This is directly applying Forney's Formula
 178   int s = errorLocations.size();
 179   ArrayRef<int> result(s);
 180   for (int i = 0; i < s; i++) {
 181     int xiInverse = field.inverse(errorLocations[i]);
 182     int denominator = 1;
 183     for (int j = 0; j < s; j++) {
 184       if (i != j) {
 185         denominator = field.multiply(denominator, GF256::addOrSubtract(1, field.multiply(errorLocations[j],
 186                                      xiInverse)));
 187       }
 188     }
 189     result[i] = field.multiply(errorEvaluator->evaluateAt(xiInverse), field.inverse(denominator));
 190   }
 191   return result;
 192 }
 193 }