"Fossies" - the Fresh Open Source Software Archive

Member "unrar/rs.cpp" (4 May 2022, 4007 Bytes) of package /linux/misc/unrarsrc-6.1.7.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "rs.cpp" see the Fossies "Dox" file reference documentation.

    1 #include "rar.hpp"
    2 
    3 #define Clean(D,S)  {for (int I=0;I<(S);I++) (D)[I]=0;}
    4 
    5 void RSCoder::Init(int ParSize)
    6 {
    7   RSCoder::ParSize=ParSize; // Store the number of recovery volumes.
    8   FirstBlockDone=false;
    9   gfInit();
   10   pnInit();
   11 }
   12 
   13 
   14 // Initialize logarithms and exponents Galois field tables.
   15 void RSCoder::gfInit()
   16 {
   17   for (int I=0,J=1;I<MAXPAR;I++)
   18   {
   19     gfLog[J]=I;
   20     gfExp[I]=J;
   21     J<<=1;
   22     if (J > MAXPAR)
   23       J^=0x11D; // 0x11D field-generator polynomial (x^8+x^4+x^3+x^2+1).
   24   }
   25   for (int I=MAXPAR;I<MAXPOL;I++) // Avoid gfExp overflow check.
   26     gfExp[I]=gfExp[I-MAXPAR];
   27 }
   28 
   29 
   30 // Multiplication over Galois field. 
   31 inline int RSCoder::gfMult(int a,int b)
   32 {
   33   return(a==0 || b == 0 ? 0:gfExp[gfLog[a]+gfLog[b]]);
   34 }
   35 
   36 
   37 // Create the generator polynomial g(x).
   38 // g(x)=(x-a)(x-a^2)(x-a^3)..(x-a^N)
   39 void RSCoder::pnInit()
   40 {
   41   int p2[MAXPAR+1]; // Currently calculated part of g(x).
   42 
   43   Clean(p2,ParSize);
   44   p2[0]=1; // Set p2 polynomial to 1.
   45 
   46   for (int I=1;I<=ParSize;I++)
   47   {
   48     int p1[MAXPAR+1]; // We use p1 as current (x+a^i) expression.
   49     Clean(p1,ParSize);
   50     p1[0]=gfExp[I];
   51     p1[1]=1; // Set p1 polynomial to x+a^i.
   52 
   53     // Multiply the already calucated part of g(x) to next (x+a^i).
   54     pnMult(p1,p2,GXPol);
   55 
   56     // p2=g(x).
   57     for (int J=0;J<ParSize;J++)
   58       p2[J]=GXPol[J];
   59   }
   60 }
   61 
   62 
   63 // Multiply polynomial 'p1' to 'p2' and store the result in 'r'.
   64 void RSCoder::pnMult(int *p1,int *p2,int *r)
   65 {
   66   Clean(r,ParSize);
   67   for (int I=0;I<ParSize;I++)
   68     if (p1[I]!=0)
   69       for(int J=0;J<ParSize-I;J++)
   70         r[I+J]^=gfMult(p1[I],p2[J]);
   71 }
   72 
   73 
   74 void RSCoder::Encode(byte *Data,int DataSize,byte *DestData)
   75 {
   76   int ShiftReg[MAXPAR+1]; // Linear Feedback Shift Register.
   77 
   78   Clean(ShiftReg,ParSize+1);
   79   for (int I=0;I<DataSize;I++)
   80   {
   81     int D=Data[I]^ShiftReg[ParSize-1];
   82 
   83     // Use g(x) to define feedback taps.
   84     for (int J=ParSize-1;J>0;J--)
   85       ShiftReg[J]=ShiftReg[J-1]^gfMult(GXPol[J],D);
   86     ShiftReg[0]=gfMult(GXPol[0],D);
   87   }
   88   for (int I=0;I<ParSize;I++)
   89     DestData[I]=ShiftReg[ParSize-I-1];
   90 }
   91 
   92 
   93 bool RSCoder::Decode(byte *Data,int DataSize,int *EraLoc,int EraSize)
   94 {
   95   int SynData[MAXPOL]; // Syndrome data.
   96 
   97   bool AllZeroes=true;
   98   for (int I=0;I<ParSize;I++)
   99   {
  100     int Sum=0;
  101     for (int J=0;J<DataSize;J++)
  102       Sum=Data[J]^gfMult(gfExp[I+1],Sum);
  103     if ((SynData[I]=Sum)!=0)
  104       AllZeroes=false;
  105   }
  106 
  107   // If all syndrome numbers are zero, message does not have errors.
  108   if (AllZeroes)
  109     return(true);
  110 
  111   if (!FirstBlockDone) // Do things which we need to do once for all data.
  112   {
  113     FirstBlockDone=true;
  114 
  115     // Calculate the error locator polynomial.
  116     Clean(ELPol,ParSize+1);
  117     ELPol[0]=1;
  118 
  119     for (int EraPos=0;EraPos<EraSize;EraPos++)
  120       for (int I=ParSize,M=gfExp[DataSize-EraLoc[EraPos]-1];I>0;I--)
  121         ELPol[I]^=gfMult(M,ELPol[I-1]);
  122 
  123     ErrCount=0;
  124 
  125     // Find roots of error locator polynomial.
  126     for (int Root=MAXPAR-DataSize;Root<MAXPAR+1;Root++)
  127     {
  128       int Sum=0;
  129       for (int B=0;B<ParSize+1;B++)
  130         Sum^=gfMult(gfExp[(B*Root)%MAXPAR],ELPol[B]);
  131       if (Sum==0) // Root found.
  132       {
  133         ErrorLocs[ErrCount]=MAXPAR-Root; // Location of error.
  134 
  135         // Calculate the denominator for every error location.
  136         Dnm[ErrCount]=0;
  137         for (int I=1;I<ParSize+1;I+=2)
  138           Dnm[ErrCount]^= gfMult(ELPol[I],gfExp[Root*(I-1)%MAXPAR]);
  139 
  140         ErrCount++;
  141       }
  142     }
  143   }
  144 
  145   int EEPol[MAXPOL]; // Error Evaluator Polynomial.
  146   pnMult(ELPol,SynData,EEPol);
  147   // If errors are present and their number is correctable.
  148   if ((ErrCount<=ParSize) && ErrCount>0)
  149     for (int I=0;I<ErrCount;I++)
  150     {
  151       int Loc=ErrorLocs[I],DLoc=MAXPAR-Loc,N=0;
  152       for (int J=0;J<ParSize;J++) 
  153         N^=gfMult(EEPol[J],gfExp[DLoc*J%MAXPAR]);
  154       int DataPos=DataSize-Loc-1;
  155       // Perform bounds check and correct the data error.
  156       if (DataPos>=0 && DataPos<DataSize)
  157         Data[DataPos]^=gfMult(N,gfExp[MAXPAR-gfLog[Dnm[I]]]);
  158     }
  159   return(ErrCount<=ParSize); // Return true if success.
  160 }