1 // This file is part of par2cmdline (a PAR 2.0 compatible file verification and
2 // repair tool). See http://parchive.sourceforge.net for details of PAR 2.0.
3 //
4 // Copyright (c) 2003 Peter Brian Clements
5 //
6 // par2cmdline is free software; you can redistribute it and/or modify
7 // it under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 2 of the License, or
9 // (at your option) any later version.
10 //
11 // par2cmdline is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program; if not, write to the Free Software
18 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
19
20 #include "par2cmdline.h"
21
22 #ifdef _MSC_VER
23 #ifdef _DEBUG
24 #undef THIS_FILE
25 static char THIS_FILE[]=__FILE__;
26 #define new DEBUG_NEW
27 #endif
28 #endif
29
gcd(u32 a,u32 b)30 u32 gcd(u32 a, u32 b)
31 {
32 if (a && b)
33 {
34 while (a && b)
35 {
36 if (a>b)
37 {
38 a = a%b;
39 }
40 else
41 {
42 b = b%a;
43 }
44 }
45
46 return a+b;
47 }
48 else
49 {
50 return 0;
51 }
52 }
53
SetInput(const vector<bool> & present)54 template <> bool ReedSolomon<Galois8>::SetInput(const vector<bool> &present)
55 {
56 inputcount = (u32)present.size();
57
58 datapresentindex = new u32[inputcount];
59 datamissingindex = new u32[inputcount];
60 database = new G::ValueType[inputcount];
61
62 G::ValueType base = 1;
63
64 for (unsigned int index=0; index<inputcount; index++)
65 {
66 // Record the index of the file in the datapresentindex array
67 // or the datamissingindex array
68 if (present[index])
69 {
70 datapresentindex[datapresent++] = index;
71 }
72 else
73 {
74 datamissingindex[datamissing++] = index;
75 }
76
77 database[index] = base++;
78 }
79
80 return true;
81 }
82
SetInput(u32 count)83 template <> bool ReedSolomon<Galois8>::SetInput(u32 count)
84 {
85 inputcount = count;
86
87 datapresentindex = new u32[inputcount];
88 datamissingindex = new u32[inputcount];
89 database = new G::ValueType[inputcount];
90
91 G::ValueType base = 1;
92
93 for (unsigned int index=0; index<count; index++)
94 {
95 // Record that the file is present
96 datapresentindex[datapresent++] = index;
97
98 database[index] = base++;
99 }
100
101 return true;
102 }
103
Process(size_t size,u32 inputindex,const void * inputbuffer,u32 outputindex,void * outputbuffer)104 template <> bool ReedSolomon<Galois8>::Process(size_t size, u32 inputindex, const void *inputbuffer, u32 outputindex, void *outputbuffer)
105 {
106 // Look up the appropriate element in the RS matrix
107 Galois8 factor = leftmatrix[outputindex * (datapresent + datamissing) + inputindex];
108
109 // Do nothing if the factor happens to be 0
110 if (factor == 0)
111 return eSuccess;
112
113 #ifdef LONGMULTIPLY
114 // The 8-bit long multiplication tables
115 Galois8 *table = glmt->tables;
116
117 // Split the factor into Low and High bytes
118 unsigned int fl = (factor >> 0) & 0xff;
119
120 // Get the four separate multiplication tables
121 Galois8 *LL = &table[(0*256 + fl) * 256 + 0]; // factor.low * source.low
122
123 // Combine the four multiplication tables into two
124 unsigned int L[256];
125
126 unsigned int *pL = &L[0];
127
128 for (unsigned int i=0; i<256; i++)
129 {
130 *pL = *LL;
131
132 pL++;
133 LL++;
134 }
135
136 // Treat the buffers as arrays of 32-bit unsigned ints.
137 u32 *src4 = (u32 *)inputbuffer;
138 u32 *end4 = (u32 *)&((u8*)inputbuffer)[size & ~3];
139 u32 *dst4 = (u32 *)outputbuffer;
140
141 // Process the data
142 while (src4 < end4)
143 {
144 u32 s = *src4++;
145
146 // Use the two lookup tables computed earlier
147 *dst4++ ^= (L[(s >> 0) & 0xff] )
148 ^ (L[(s >> 8) & 0xff] << 8 )
149 ^ (L[(s >> 16)& 0xff] << 16)
150 ^ (L[(s >> 24)& 0xff] << 24);
151 }
152
153 // Process any left over bytes at the end of the buffer
154 if (size & 3)
155 {
156 u8 *src1 = &((u8*)inputbuffer)[size & ~3];
157 u8 *end1 = &((u8*)inputbuffer)[size];
158 u8 *dst1 = &((u8*)outputbuffer)[size & ~3];
159
160 // Process the data
161 while (src1 < end1)
162 {
163 u8 s = *src1++;
164 *dst1++ ^= L[s];
165 }
166 }
167 #else
168 // Treat the buffers as arrays of 16-bit Galois values.
169
170 Galois8 *src = (Galois8 *)inputbuffer;
171 Galois8 *end = (Galois8 *)&((u8*)inputbuffer)[size];
172 Galois8 *dst = (Galois8 *)outputbuffer;
173
174 // Process the data
175 while (src < end)
176 {
177 *dst++ += *src++ * factor;
178 }
179 #endif
180
181 return eSuccess;
182 }
183
184
185
186 ////////////////////////////////////////////////////////////////////////////////////////////
187
188
189
190 // Set which of the source files are present and which are missing
191 // and compute the base values to use for the vandermonde matrix.
SetInput(const vector<bool> & present)192 template <> bool ReedSolomon<Galois16>::SetInput(const vector<bool> &present)
193 {
194 inputcount = (u32)present.size();
195
196 datapresentindex = new u32[inputcount];
197 datamissingindex = new u32[inputcount];
198 database = new G::ValueType[inputcount];
199
200 unsigned int logbase = 0;
201
202 for (unsigned int index=0; index<inputcount; index++)
203 {
204 // Record the index of the file in the datapresentindex array
205 // or the datamissingindex array
206 if (present[index])
207 {
208 datapresentindex[datapresent++] = index;
209 }
210 else
211 {
212 datamissingindex[datamissing++] = index;
213 }
214
215 // Determine the next useable base value.
216 // Its log must must be relatively prime to 65535
217 while (gcd(G::Limit, logbase) != 1)
218 {
219 logbase++;
220 }
221 if (logbase >= G::Limit)
222 {
223 cerr << "Too many input blocks for Reed Solomon matrix." << endl;
224 return false;
225 }
226 G::ValueType base = G(logbase++).ALog();
227
228 database[index] = base;
229 }
230
231 return true;
232 }
233
234 // Record that the specified number of source files are all present
235 // and compute the base values to use for the vandermonde matrix.
SetInput(u32 count)236 template <> bool ReedSolomon<Galois16>::SetInput(u32 count)
237 {
238 inputcount = count;
239
240 datapresentindex = new u32[inputcount];
241 datamissingindex = new u32[inputcount];
242 database = new G::ValueType[inputcount];
243
244 unsigned int logbase = 0;
245
246 for (unsigned int index=0; index<count; index++)
247 {
248 // Record that the file is present
249 datapresentindex[datapresent++] = index;
250
251 // Determine the next useable base value.
252 // Its log must must be relatively prime to 65535
253 while (gcd(G::Limit, logbase) != 1)
254 {
255 logbase++;
256 }
257 if (logbase >= G::Limit)
258 {
259 cerr << "Too many input blocks for Reed Solomon matrix." << endl;
260 return false;
261 }
262 G::ValueType base = G(logbase++).ALog();
263
264 database[index] = base;
265 }
266
267 return true;
268 }
269
Process(size_t size,u32 inputindex,const void * inputbuffer,u32 outputindex,void * outputbuffer)270 template <> bool ReedSolomon<Galois16>::Process(size_t size, u32 inputindex, const void *inputbuffer, u32 outputindex, void *outputbuffer)
271 {
272 // Look up the appropriate element in the RS matrix
273
274 Galois16 factor = leftmatrix[outputindex * (datapresent + datamissing) + inputindex];
275 // Do nothing if the factor happens to be 0
276 if (factor == 0)
277 return eSuccess;
278
279 #ifdef LONGMULTIPLY
280 // The 8-bit long multiplication tables
281 Galois16 *table = glmt->tables;
282
283 // Split the factor into Low and High bytes
284 unsigned int fl = (factor >> 0) & 0xff;
285 unsigned int fh = (factor >> 8) & 0xff;
286
287 // Get the four separate multiplication tables
288 Galois16 *LL = &table[(0*256 + fl) * 256 + 0]; // factor.low * source.low
289 Galois16 *LH = &table[(1*256 + fl) * 256 + 0]; // factor.low * source.high
290 Galois16 *HL = &table[(1*256 + 0) * 256 + fh]; // factor.high * source.low
291 Galois16 *HH = &table[(2*256 + fh) * 256 + 0]; // factor.high * source.high
292
293 // Combine the four multiplication tables into two
294 unsigned int L[256];
295 unsigned int H[256];
296
297 #if __BYTE_ORDER == __LITTLE_ENDIAN
298 unsigned int *pL = &L[0];
299 unsigned int *pH = &H[0];
300 #else
301 unsigned int *pL = &H[0];
302 unsigned int *pH = &L[0];
303 #endif
304
305 for (unsigned int i=0; i<256; i++)
306 {
307 #if __BYTE_ORDER == __LITTLE_ENDIAN
308 *pL = *LL + *HL;
309 #else
310 unsigned int temp = *LL + *HL;
311 *pL = (temp >> 8) & 0xff | (temp << 8) & 0xff00;
312 #endif
313
314 pL++;
315 LL++;
316 HL+=256;
317
318 #if __BYTE_ORDER == __LITTLE_ENDIAN
319 *pH = *LH + *HH;
320 #else
321 temp = *LH + *HH;
322 *pH = (temp >> 8) & 0xff | (temp << 8) & 0xff00;
323 #endif
324
325 pH++;
326 LH++;
327 HH++;
328 }
329
330 // Treat the buffers as arrays of 32-bit unsigned ints.
331 u32 *src = (u32 *)inputbuffer;
332 u32 *end = (u32 *)&((u8*)inputbuffer)[size];
333 u32 *dst = (u32 *)outputbuffer;
334
335 // Process the data
336 while (src < end)
337 {
338 u32 s = *src++;
339
340 // Use the two lookup tables computed earlier
341 //#if __BYTE_ORDER == __LITTLE_ENDIAN
342 u32 d = *dst ^ (L[(s >> 0) & 0xff] )
343 ^ (H[(s >> 8) & 0xff] )
344 ^ (L[(s >> 16)& 0xff] << 16)
345 ^ (H[(s >> 24)& 0xff] << 16);
346 *dst++ = d;
347 //#else
348 // *dst++ ^= (L[(s >> 8) & 0xff] )
349 // ^ (H[(s >> 0) & 0xff] )
350 // ^ (L[(s >> 24)& 0xff] << 16)
351 // ^ (H[(s >> 16)& 0xff] << 16);
352 //#endif
353 }
354 #else
355 // Treat the buffers as arrays of 16-bit Galois values.
356
357 // BUG: This only works for __LITTLE_ENDIAN
358 Galois16 *src = (Galois16 *)inputbuffer;
359 Galois16 *end = (Galois16 *)&((u8*)inputbuffer)[size];
360 Galois16 *dst = (Galois16 *)outputbuffer;
361
362 // Process the data
363 while (src < end)
364 {
365 *dst++ += *src++ * factor;
366 }
367 #endif
368
369 return eSuccess;
370 }
371
372