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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
20 #ifndef __GALOIS_H__
21 #define __GALOIS_H__
22
23 template <const unsigned int bits, const unsigned int generator, typename valuetype> class GaloisTable;
24 template <const unsigned int bits, const unsigned int generator, typename valuetype> class Galois;
25
26 template <class g> class GaloisLongMultiplyTable;
27
28 // This source file defines the Galois object for carrying out
29 // arithmetic in GF(2^16) using the generator 0x1100B.
30
31 // Also defined are the GaloisTable object (which contains log and
32 // anti log tables for use in multiplication and division), and
33 // the GaloisLongMultiplyTable object (which contains tables for
34 // carrying out multiplation of 16-bit galois numbers 8 bits at a time).
35
36 template <const unsigned int bits, const unsigned int generator, typename valuetype>
37 class GaloisTable
38 {
39 public:
40 typedef valuetype ValueType;
41
42 GaloisTable(void);
43
44 enum
45 {
46 Bits = bits,
47 Count = 1<<Bits,
48 Limit = Count-1,
49 Generator = generator,
50 };
51
52 ValueType log[Count];
53 ValueType antilog[Count];
54 };
55
56 template <const unsigned int bits, const unsigned int generator, typename valuetype>
57 class Galois
58 {
59 public:
60 typedef valuetype ValueType;
61
62 // Basic constructors
Galois(void)63 Galois(void) {};
64 Galois(ValueType v);
65
66 // Copy and assignment
Galois(const Galois & right)67 Galois(const Galois &right) {value = right.value;}
68 Galois& operator = (const Galois &right) { value = right.value; return *this;}
69
70 // Addition
71 Galois operator + (const Galois &right) const { return (value ^ right.value); }
72 Galois& operator += (const Galois &right) { value ^= right.value; return *this;}
73
74 // Subtraction
75 Galois operator - (const Galois &right) const { return (value ^ right.value); }
76 Galois& operator -= (const Galois &right) { value ^= right.value; return *this;}
77
78 // Multiplication
79 Galois operator * (const Galois &right) const;
80 Galois& operator *= (const Galois &right);
81
82 // Division
83 Galois operator / (const Galois &right) const;
84 Galois& operator /= (const Galois &right);
85
86 // Power
87 Galois pow(unsigned int right) const;
88 Galois operator ^ (unsigned int right) const;
89 Galois& operator ^= (unsigned int right);
90
91 // Cast to value and value access
ValueType(void)92 operator ValueType(void) const {return value;}
Value(void)93 ValueType Value(void) const {return value;}
94
95 // Direct log and antilog
96 ValueType Log(void) const;
97 ValueType ALog(void) const;
98
99 enum
100 {
101 Bits = GaloisTable<bits,generator,valuetype>::Bits,
102 Count = GaloisTable<bits,generator,valuetype>::Count,
103 Limit = GaloisTable<bits,generator,valuetype>::Limit,
104 };
105
106 protected:
107 ValueType value;
108
109 static GaloisTable<bits,generator,valuetype> table;
110 };
111
112 #ifdef LONGMULTIPLY
113 template <class g>
114 class GaloisLongMultiplyTable
115 {
116 public:
117 GaloisLongMultiplyTable(void);
118
119 typedef g G;
120
121 enum
122 {
123 Bytes = ((G::Bits + 7) >> 3),
124 Count = ((Bytes * (Bytes+1)) / 2),
125 };
126
127 G tables[Count * 256 * 256];
128 };
129 #endif
130
131 // Construct the log and antilog tables from the generator
132
133 template <const unsigned int bits, const unsigned int generator, typename valuetype>
GaloisTable(void)134 inline GaloisTable<bits,generator,valuetype>::GaloisTable(void)
135 {
136 u32 b = 1;
137
138 for (u32 l=0; l<Limit; l++)
139 {
140 log[b] = (ValueType)l;
141 antilog[l] = (ValueType)b;
142
143 b <<= 1;
144 if (b & Count) b ^= Generator;
145 }
146
147 log[0] = (ValueType)Limit;
148 antilog[Limit] = 0;
149 }
150
151
152 // The one and only galois log/antilog table object
153
154 template <const unsigned int bits, const unsigned int generator, typename valuetype>
155 GaloisTable<bits,generator,valuetype> Galois<bits,generator,valuetype>::table;
156
157
158 template <const unsigned int bits, const unsigned int generator, typename valuetype>
Galois(typename Galois<bits,generator,valuetype>::ValueType v)159 inline Galois<bits,generator,valuetype>::Galois(typename Galois<bits,generator,valuetype>::ValueType v)
160 {
161 value = v;
162 }
163
164 template <const unsigned int bits, const unsigned int generator, typename valuetype>
165 inline Galois<bits,generator,valuetype> Galois<bits,generator,valuetype>::operator * (const Galois<bits,generator,valuetype> &right) const
166 {
167 if (value == 0 || right.value == 0) return 0;
168 unsigned int sum = table.log[value] + table.log[right.value];
169 if (sum >= Limit)
170 {
171 return table.antilog[sum-Limit];
172 }
173 else
174 {
175 return table.antilog[sum];
176 }
177 }
178
179 template <const unsigned int bits, const unsigned int generator, typename valuetype>
180 inline Galois<bits,generator,valuetype>& Galois<bits,generator,valuetype>::operator *= (const Galois<bits,generator,valuetype> &right)
181 {
182 if (value == 0 || right.value == 0)
183 {
184 value = 0;
185 }
186 else
187 {
188 unsigned int sum = table.log[value] + table.log[right.value];
189 if (sum >= Limit)
190 {
191 value = table.antilog[sum-Limit];
192 }
193 else
194 {
195 value = table.antilog[sum];
196 }
197 }
198
199 return *this;
200 }
201
202 template <const unsigned int bits, const unsigned int generator, typename valuetype>
203 inline Galois<bits,generator,valuetype> Galois<bits,generator,valuetype>::operator / (const Galois<bits,generator,valuetype> &right) const
204 {
205 if (value == 0) return 0;
206
207 assert(right.value != 0);
208 if (right.value == 0) {return 0;} // Division by 0!
209
210 int sum = table.log[value] - table.log[right.value];
211 if (sum < 0)
212 {
213 return table.antilog[sum+Limit];
214 }
215 else
216 {
217 return table.antilog[sum];
218 }
219 }
220
221 template <const unsigned int bits, const unsigned int generator, typename valuetype>
222 inline Galois<bits,generator,valuetype>& Galois<bits,generator,valuetype>::operator /= (const Galois<bits,generator,valuetype> &right)
223 {
224 if (value == 0) return *this;
225
226 assert(right.value != 0);
227 if (right.value == 0) {return *this;} // Division by 0!
228
229 int sum = table.log[value] - table.log[right.value];
230 if (sum < 0)
231 {
232 value = table.antilog[sum+Limit];
233 }
234 else
235 {
236 value = table.antilog[sum];
237 }
238
239 return *this;
240 }
241
242 template <const unsigned int bits, const unsigned int generator, typename valuetype>
pow(unsigned int right)243 inline Galois<bits,generator,valuetype> Galois<bits,generator,valuetype>::pow(unsigned int right) const
244 {
245 if (right == 0) return 1;
246 if (value == 0) return 0;
247
248 unsigned int sum = table.log[value] * right;
249
250 sum = (sum >> Bits) + (sum & Limit);
251 if (sum >= Limit)
252 {
253 return table.antilog[sum-Limit];
254 }
255 else
256 {
257 return table.antilog[sum];
258 }
259 }
260
261 template <const unsigned int bits, const unsigned int generator, typename valuetype>
262 inline Galois<bits,generator,valuetype> Galois<bits,generator,valuetype>::operator ^ (unsigned int right) const
263 {
264 if (right == 0) return 1;
265 if (value == 0) return 0;
266
267 unsigned int sum = table.log[value] * right;
268
269 sum = (sum >> Bits) + (sum & Limit);
270 if (sum >= Limit)
271 {
272 return table.antilog[sum-Limit];
273 }
274 else
275 {
276 return table.antilog[sum];
277 }
278 }
279
280 template <const unsigned int bits, const unsigned int generator, typename valuetype>
281 inline Galois<bits,generator,valuetype>& Galois<bits,generator,valuetype>::operator ^= (unsigned int right)
282 {
283 if (right == 0) {value = 1; return *this;}
284 if (value == 0) return *this;
285
286 unsigned int sum = table.log[value] * right;
287
288 sum = (sum >> Bits) + (sum & Limit);
289 if (sum >= Limit)
290 {
291 value = table.antilog[sum-Limit];
292 }
293 else
294 {
295 value = table.antilog[sum];
296 }
297
298 return *this;
299 }
300
301 template <const unsigned int bits, const unsigned int generator, typename valuetype>
Log(void)302 inline valuetype Galois<bits,generator,valuetype>::Log(void) const
303 {
304 return table.log[value];
305 }
306
307 template <const unsigned int bits, const unsigned int generator, typename valuetype>
ALog(void)308 inline valuetype Galois<bits,generator,valuetype>::ALog(void) const
309 {
310 return table.antilog[value];
311 }
312
313 #ifdef LONGMULTIPLY
314 template <class g>
GaloisLongMultiplyTable(void)315 inline GaloisLongMultiplyTable<g>::GaloisLongMultiplyTable(void)
316 {
317 G *table = tables;
318
319 for (unsigned int i=0; i<Bytes; i++)
320 {
321 for (unsigned int j=i; j<Bytes; j++)
322 {
323 for (unsigned int ii=0; ii<256; ii++)
324 {
325 for (unsigned int jj=0; jj<256; jj++)
326 {
327 *table++ = G(ii << (8*i)) * G(jj << (8*j));
328 }
329 }
330 }
331 }
332 }
333 #endif
334
335 typedef Galois<8,0x11D,u8> Galois8;
336 typedef Galois<16,0x1100B,u16> Galois16;
337
338 #endif // __GALOIS_H__
339