ErrorCorrection.cpp Example File

 // -*- mode:c++; tab-width:2; indent-tabs-mode:nil; c-basic-offset:2 -*-
 /*
  * Copyright 2012 ZXing authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  *
  * 2012-09-19 HFN translation from Java into C++
  */

 #include <zxing/pdf417/decoder/ec/ErrorCorrection.h>
 #include <zxing/pdf417/decoder/ec/ModulusPoly.h>
 #include <zxing/pdf417/decoder/ec/ModulusGF.h>

 using std::vector;
 using zxing::Ref;
 using zxing::ArrayRef;
 using zxing::pdf417::decoder::ec::ErrorCorrection;
 using zxing::pdf417::decoder::ec::ModulusPoly;
 using zxing::pdf417::decoder::ec::ModulusGF;

 /**
  * <p>PDF417 error correction implementation.</p>
  *
  * <p>This <a href="http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Example">example</a>
  * is quite useful in understanding the algorithm.</p>
  *
  * @author Sean Owen
  * @see com.google.zxing.common.reedsolomon.ReedSolomonDecoder
  */

 ErrorCorrection::ErrorCorrection()
     : field_(ModulusGF::PDF417_GF)
 {
 }

 void ErrorCorrection::decode(ArrayRef<int> received,
                              int numECCodewords,
                              ArrayRef<int> erasures)
 {
   Ref<ModulusPoly> poly (new ModulusPoly(field_, received));
   ArrayRef<int> S( new Array<int>(numECCodewords));
   bool error = false;
   for (int i = numECCodewords; i > 0; i--) {
     int eval = poly->evaluateAt(field_.exp(i));
     S[numECCodewords - i] = eval;
     if (eval != 0) {
       error = true;
     }
   }

   if (error) {

     Ref<ModulusPoly> knownErrors = field_.getOne();
     for (int i=0;i<erasures->size();i++) {
       int b = field_.exp(received->size() - 1 - erasures[i]);
       // Add (1 - bx) term:
       ArrayRef<int> one_minus_b_x(new Array<int>(2));
       one_minus_b_x[1]=field_.subtract(0,b);
       one_minus_b_x[0]=1;
       Ref<ModulusPoly> term (new ModulusPoly(field_,one_minus_b_x));
       knownErrors = knownErrors->multiply(term);
     }

     Ref<ModulusPoly> syndrome (new ModulusPoly(field_, S));
     //syndrome = syndrome.multiply(knownErrors);

     vector<Ref<ModulusPoly> > sigmaOmega (
         runEuclideanAlgorithm(field_.buildMonomial(numECCodewords, 1), syndrome, numECCodewords));
     Ref<ModulusPoly> sigma = sigmaOmega[0];
     Ref<ModulusPoly> omega = sigmaOmega[1];

     //sigma = sigma.multiply(knownErrors);

     ArrayRef<int> errorLocations = findErrorLocations(sigma);
     ArrayRef<int> errorMagnitudes = findErrorMagnitudes(omega, sigma, errorLocations);

     for (int i = 0; i < errorLocations->size(); i++) {
       int position = received->size() - 1 - field_.log(errorLocations[i]);
       if (position < 0) {
         throw ReedSolomonException("Bad error location!");
       }
       received[position] = field_.subtract(received[position], errorMagnitudes[i]);
 #if (defined (DEBUG)  && defined _WIN32)
       {
         WCHAR szmsg[256];
         swprintf(szmsg,L"ErrorCorrection::decode: fix @ %d, new value = %d\n",
                  position, received[position]);
         OutputDebugString(szmsg);
       }
 #endif
     }
   }
 }

 vector<Ref<ModulusPoly> >  ErrorCorrection::runEuclideanAlgorithm(Ref<ModulusPoly> a, Ref<ModulusPoly> b, int R)
 {
   // Assume a's degree is >= b's
   if (a->getDegree() < b->getDegree()) {
     Ref<ModulusPoly> temp = a;
     a = b;
     b = temp;
   }

   Ref<ModulusPoly> rLast ( a);
   Ref<ModulusPoly> r ( b);
   Ref<ModulusPoly> tLast ( field_.getZero());
   Ref<ModulusPoly> t ( field_.getOne());

   // Run Euclidean algorithm until r's degree is less than R/2
   while (r->getDegree() >= R / 2) {
     Ref<ModulusPoly> rLastLast (rLast);
     Ref<ModulusPoly> tLastLast (tLast);
     rLast = r;
     tLast = t;

     // Divide rLastLast by rLast, with quotient in q and remainder in r
     if (rLast->isZero()) {
       // Oops, Euclidean algorithm already terminated?
       throw ReedSolomonException("Euclidean algorithm already terminated?");
     }
     r = rLastLast;
     Ref<ModulusPoly> q (field_.getZero());
     int denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());
     int dltInverse = field_.inverse(denominatorLeadingTerm);
     while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {
       int degreeDiff = r->getDegree() - rLast->getDegree();
       int scale = field_.multiply(r->getCoefficient(r->getDegree()), dltInverse);
       q = q->add(field_.buildMonomial(degreeDiff, scale));
       r = r->subtract(rLast->multiplyByMonomial(degreeDiff, scale));
     }

           t = q->multiply(tLast)->subtract(tLastLast)->negative();
   }

   int sigmaTildeAtZero = t->getCoefficient(0);
   if (sigmaTildeAtZero == 0) {
     throw ReedSolomonException("sigmaTilde = 0!");
   }

   int inverse = field_.inverse(sigmaTildeAtZero);
   Ref<ModulusPoly> sigma (t->multiply(inverse));
   Ref<ModulusPoly> omega (r->multiply(inverse));
         vector<Ref<ModulusPoly> > v(2);
         v[0] = sigma;
         v[1] = omega;
   return v;
 }

 ArrayRef<int> ErrorCorrection::findErrorLocations(Ref<ModulusPoly> errorLocator)  {
   // This is a direct application of Chien's search
   int numErrors = errorLocator->getDegree();
   ArrayRef<int> result( new Array<int>(numErrors));
   int e = 0;
   for (int i = 1; i < field_.getSize() && e < numErrors; i++) {
     if (errorLocator->evaluateAt(i) == 0) {
       result[e] = field_.inverse(i);
       e++;
     }
   }
   if (e != numErrors) {
 #if (defined (DEBUG) && defined _WIN32)
           char sz[128];
           sprintf(sz,"Error number inconsistency, %d/%d!",e,numErrors);
     throw ReedSolomonException(sz);
 #else
           throw ReedSolomonException("Error number inconsistency!");
 #endif
   }
 #if (defined (DEBUG) && defined _WIN32)
   {
     WCHAR szmsg[256];
     swprintf(szmsg,L"ErrorCorrection::findErrorLocations: found %d errors.\n",
              e);
     OutputDebugString(szmsg);
   }
 #endif
   return result;
 }

 ArrayRef<int> ErrorCorrection::findErrorMagnitudes(Ref<ModulusPoly> errorEvaluator,
                                                    Ref<ModulusPoly> errorLocator,
                                                    ArrayRef<int> errorLocations) {
         int i;
   int errorLocatorDegree = errorLocator->getDegree();
   ArrayRef<int> formalDerivativeCoefficients (new Array<int>(errorLocatorDegree));
   for (i = 1; i <= errorLocatorDegree; i++) {
     formalDerivativeCoefficients[errorLocatorDegree - i] =
         field_.multiply(i, errorLocator->getCoefficient(i));
   }
   Ref<ModulusPoly> formalDerivative (new ModulusPoly(field_, formalDerivativeCoefficients));

   // This is directly applying Forney's Formula
   int s = errorLocations->size();
   ArrayRef<int> result ( new Array<int>(s));
   for (i = 0; i < s; i++) {
     int xiInverse = field_.inverse(errorLocations[i]);
     int numerator = field_.subtract(0, errorEvaluator->evaluateAt(xiInverse));
     int denominator = field_.inverse(formalDerivative->evaluateAt(xiInverse));
     result[i] = field_.multiply(numerator, denominator);
   }
   return result;
 }