Subversion Repositories reedsolomon

//----------------------------------------------------------------------//

// The MIT License 

// 

// Copyright (c) 2010 Abhinav Agarwal, Alfred Man Cheuk Ng

// Contact: abhiag@gmail.com

// 

// Permission is hereby granted, free of charge, to any person 

// obtaining a copy of this software and associated documentation 

// files (the "Software"), to deal in the Software without 

// restriction, including without limitation the rights to use,

// copy, modify, merge, publish, distribute, sublicense, and/or sell

// copies of the Software, and to permit persons to whom the

// Software is furnished to do so, subject to the following conditions:

// 

// The above copyright notice and this permission notice shall be

// included in all copies or substantial portions of the Software.

// 

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,

// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES

// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND

// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT

// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,

// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR

// OTHER DEALINGS IN THE SOFTWARE.

//----------------------------------------------------------------------//

#include <iostream>

#include <fstream>

#include <list>

#include <cstring>

#include <cstdlib>

#include <regex.h>

using namespace std;

#define mm  8

#define nn  255

int pp [mm + 1];

int alpha_to [255 + 2];

int index_of [255 + 2];

// --------------------------------------------------------------------

void generate_gf (int* pp)

{

   int mask = 1;

   alpha_to [mm] = 0 ;

   for (int i = 0; i < mm; ++ i)

   {

      alpha_to [i] = mask;

      index_of [alpha_to [i]] = i;

      if (0 != pp [i])

         alpha_to[mm] ^= mask;

      mask <<= 1;

   }

   index_of [alpha_to [mm]] = mm;

   mask >>= 1;

   for (int i = mm + 1; i < nn; ++ i)

   {

      if (alpha_to [i - 1] >= mask)

         alpha_to [i] = alpha_to [mm] ^ ((alpha_to [i - 1] ^ mask) << 1);

      else

         alpha_to [i] = alpha_to [i - 1] << 1;

      index_of [alpha_to [i]] = i;

   }

   index_of [0] = -1;

}

// --------------------------------------------------------------------

unsigned char gfinv_lut (unsigned char a)

{

   unsigned char result = (nn - index_of [a]) % nn;

   return alpha_to[result];

}

// --------------------------------------------------------------------

void print (string& rLine)

{

   string sLine (rLine);

   string::size_type iLength = sLine.length ();

   for (string::size_type i = 0; i < iLength; ++ i)

      if ('\t' == sLine.at (i))

         sLine [i] = ' ';

   string::size_type iStart = sLine.find ("  ");

   while (string::npos != iStart)

   {

      string::size_type iEnd = iStart + 1;

      while ((iEnd < iLength) && (' ' == sLine.at (iEnd)))

         ++ iEnd;

      sLine.replace (iStart, iEnd - iStart, " ");

      iLength = sLine.length ();

      iStart = sLine.find ("  ");

   }

   if (' ' == sLine.at (0))

      sLine = sLine.substr (1);

   cout << sLine << endl;

}

// --------------------------------------------------------------------

int main (int argc, char* argv [])

{

   ifstream file;

   file.open (argv [1]);

   if (false == file.is_open ())

   {

      cerr << "Failed to open file '" << argv [1] << "'. Quitting." << endl;

      return 1;

   }

   cout << endl;

   string sPolynomial;

   list <string>   lstPotentialPolyDefs;

   //   while (false == file.eof ())

   //{

      char zLine [1000];

      file.getline (zLine, 1000);

      string sLine (zLine);

      if (0 != strstr (zLine, "Polynomial "))

      {

         // we've found a line that may have the primitive  

         // polynomial defined in it. Now we need to read   

         // till the end of the line (till a ;) and store   

         // all that for later...                           

         while (0 != strchr (zLine, ';'))

         {

            file.getline (zLine, 1000);

            sLine += zLine;

         }

         lstPotentialPolyDefs.push_back (sLine);

      }

//       else if (0 != strstr (zLine, "IReedSolomon "))

//       {

//          // we've found the line where the ReedSolomon      

//          // decoder is instantiated. The primitive          

//          // polynomial will be used here. We can use this   

//          // to extract it...                                

//          string sLine (zLine);

//       while (0 == strchr (zLine, ';'))

//          {

//             file.getline (zLine, 1000);

//             sLine += zLine;

//          }

//          cout << "Line with ReedSolomon decoder instantiation." << endl;

//          cout << endl << "\t";

//          print (sLine);

//          cout << endl;

//          // check that we have the correct line...          

//          if ((string::npos == sLine.find ("<-")) ||

//              (string::npos == sLine.find ("mkReedSolomon")))

//          {

//             cout << "Got the wrong line! Can't continue." << endl;

//             return 1;

//          }

//          // extract the polynomial used in the              

//          // mkReedSolomon line...                           

//          string::size_type iStart = sLine.find ("(");

//          string::size_type iEnd = sLine.rfind (")");

//          string sPolynomialVariable = sLine.substr (iStart + 1, iEnd - iStart - 1);

//          // check if the polynomial has been defined        

//          // in-place...                                     

//          regex_t regexp;

//          string sPattern = "[0-9]'[bdohBDOH][0-9]*";

//          int ret = regcomp (&regexp, sPattern.c_str (), REG_EXTENDED);

//          if (0 != ret)

//          {

//             char zError [1000];

//             regerror (ret, &regexp, zError, 1000);

//             cerr << "Regular expression " << sPattern 

//                  << " failed to compile. Error : " << zError << endl;

//             return 1;

//          }

//          if (0 == regexec (&regexp, sPolynomialVariable.c_str (), 0, NULL, 0))

//          {

//             // we have an in-line definition of the poly... 

//             sPolynomial = sPolynomialVariable;

//             cout << "Primitive polynomial found inline." << endl;

//             cout << "polynomial : " << sPolynomial << endl;

//             break;

//          }

//          else

//          {

            // we need to search through the lines we       

            // previously saved to find the location where  

            // the polynomial was defined...                

            cout << endl;

            cout << "ReedSolomon instantiation uses a polynomial declared elsewhere."

                 << endl << "Searching for the declaration." << endl << endl;

            bool bPolynomialFound = false;

            list <string>::iterator ite;

            for (ite = lstPotentialPolyDefs.begin ();

                ite != lstPotentialPolyDefs.end ();

                ++ ite)

            {

               string& rLine = *ite;

               cout << "\t";

               print (rLine);

               cout << endl;

//                if (string::npos != sLine.find ("primitive_polynomial"))

//                {

                  string::size_type iStart = rLine.find ("=");

                  string::size_type iEnd = rLine.rfind (";");

                  ++ iStart;

                  while (rLine.at (iStart) == ' ')

                     ++ iStart;

                  sPolynomial = rLine.substr (iStart, iEnd - iStart);

                  cout << endl;

                  cout << "Primitive polynomial found as a separate declaration." << endl;

                  cout << "polynomial : " << sPolynomial << endl;

                  bPolynomialFound = true;

                  break;

                  //               }

            }

            if (false == bPolynomialFound)

            {

               cerr << "Failed to find polynomial as a separate declaration, " << endl

                    << "and polynomial is not present inline. Cannot continue." << endl;

               return 1;

            }

            //         }

            //      }

            //}

   // process extracted polynomial...           

   if (string::npos == sPolynomial.find ("b"))

   {

      cerr << "Currently only polynomials declared in the binary format are supported."

           << "Quitting. " << endl;

      return 1;

   }

   int iLength = sPolynomial.length ();

   int j = 0;

   for (int i = iLength - 1; i > 2; -- i)

      pp [j++] = ('1' == sPolynomial.at (i))? 1 : 0;

   // The MSB of the primitive polynomial is always 1.

   // This bit is not included in the polynomial      

   // declared in mkReedSolomon.                      

   pp [j] = 1;

   generate_gf (pp);

   // generate the BlueSpec file with gf_inv... 

   cout << "Generating BlueSpec file with Galois field inversion code..." << endl;

   ofstream ofsGenerated (argv [2]);

   if (false == ofsGenerated.is_open ())

   {

      cerr << "Failed to open file '" << argv [2] << "' for writing. Quitting." << endl;

      return 1;

   }

//   ofsGenerated << "import GFTypes::*;" << endl;

//   ofsGenerated << endl << endl;

   ofsGenerated << "// ---------------------------------------------------------" << endl;

   ofsGenerated << "function Byte gf_inv (Byte a);" << endl;

   ofsGenerated << endl;

   ofsGenerated << "   case (a) matches" << endl;

   for (int i = 0; i < 256; ++ i)

   {

      unsigned char inv = gfinv_lut ((unsigned char) i);

      ofsGenerated << "        " << i << " : return " << (int) inv << ";" << endl;

   }

   ofsGenerated << "   endcase" << endl;

   ofsGenerated << "endfunction" << endl;

   ofsGenerated << endl;

   cout << "Done." << endl << endl;

}