"Fossies" - the Fresh Open Source Software Archive 
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 }