1 #include "rar.hpp"
2
3 #define Clean(D,S) {for (int I=0;I<(S);I++) (D)[I]=0;}
4
RSCoder(int ParSize)5 RSCoder::RSCoder(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.
gfInit()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 & 0x100)
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++)
26 gfExp[I]=gfExp[I-MAXPAR];
27 }
28
29
30 // Multiplication over Galois field.
gfMult(int a,int b)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)
pnInit()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'.
pnMult(int * p1,int * p2,int * 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
Encode(byte * Data,int DataSize,byte * DestData)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
Decode(byte * Data,int DataSize,int * EraLoc,int EraSize)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=Data[0],J=1,Exp=gfExp[I+1];
101 for (;J+8<=DataSize;J+=8) // Unroll the loop for speed.
102 {
103 Sum=Data[J]^gfMult(Exp,Sum);
104 Sum=Data[J+1]^gfMult(Exp,Sum);
105 Sum=Data[J+2]^gfMult(Exp,Sum);
106 Sum=Data[J+3]^gfMult(Exp,Sum);
107 Sum=Data[J+4]^gfMult(Exp,Sum);
108 Sum=Data[J+5]^gfMult(Exp,Sum);
109 Sum=Data[J+6]^gfMult(Exp,Sum);
110 Sum=Data[J+7]^gfMult(Exp,Sum);
111 }
112
113 for (;J<DataSize;J++)
114 Sum=Data[J]^gfMult(Exp,Sum);
115 if ((SynData[I]=Sum)!=0)
116 AllZeroes=false;
117 }
118
119 // If all syndrome numbers are zero, message does not have errors.
120 if (AllZeroes)
121 return(true);
122
123 if (!FirstBlockDone) // Do things which we need to do once for all data.
124 {
125 FirstBlockDone=true;
126
127 // Calculate the error locator polynomial.
128 Clean(ELPol,ParSize+1);
129 ELPol[0]=1;
130
131 for (int EraPos=0;EraPos<EraSize;EraPos++)
132 for (int I=ParSize,M=gfExp[DataSize-EraLoc[EraPos]-1];I>0;I--)
133 ELPol[I]^=gfMult(M,ELPol[I-1]);
134
135 ErrCount=0;
136
137 // Find roots of error locator polynomial.
138 for (int Root=MAXPAR-DataSize;Root<MAXPAR+1;Root++)
139 {
140 int Sum=0;
141 for (int B=0;B<ParSize+1;B++)
142 Sum^=gfMult(gfExp[(B*Root)%MAXPAR],ELPol[B]);
143 if (Sum==0) // Root found.
144 {
145 ErrorLocs[ErrCount]=MAXPAR-Root; // Location of error.
146
147 // Calculate the denominator for every error location.
148 Dnm[ErrCount]=0;
149 for (int I=1;I<ParSize+1;I+=2)
150 Dnm[ErrCount]^= gfMult(ELPol[I],gfExp[Root*(I-1)%MAXPAR]);
151
152 ErrCount++;
153 }
154 }
155 }
156
157 int EEPol[MAXPOL]; // Error Evaluator Polynomial.
158 pnMult(ELPol,SynData,EEPol);
159 // If errors are present and their number is correctable.
160 if ((ErrCount<=ParSize) && ErrCount>0)
161 for (int I=0;I<ErrCount;I++)
162 {
163 int Loc=ErrorLocs[I],DLoc=MAXPAR-Loc,N=0;
164 for (int J=0;J<ParSize;J++)
165 N^=gfMult(EEPol[J],gfExp[DLoc*J%MAXPAR]);
166 int DataPos=DataSize-Loc-1;
167 // Perform bounds check and correct the data error.
168 if (DataPos>=0 && DataPos<DataSize)
169 Data[DataPos]^=gfMult(N,gfExp[MAXPAR-gfLog[Dnm[I]]]);
170 }
171 return(ErrCount<=ParSize); // Return true if success.
172 }
173