RZ

01: /****** AlgoGF.hh / GF(2**32) Finite Field Arithmetic ******/
02: 
03: #ifndef _AlgoGF_HH
04: #define _AlgoGF_HH 1
05: 
06: /****** ******* ******* ******* ******* ******* ******* ******* ******* ******/ 
07: 
08: // all inlines -- no corresponding cc file
09: 
10: namespace GF {
11:     // in GF context we refer to GF(2**32) as 32 bit signed ints
12:     // in all other contexts we refer to GF(2**32) as 32 bit unsigned ints
13: 
14:     struct GFbinary32 {
15:         int const mod32;
16: 
17:         GFbinary32(int m): mod32(m) {}
18: 
19:         int multiply(int multiplicand, int multiplier)
20:         {
21:             int acc = 0;
22:             for (int i = 0; i < 32; ++i) {
23:                 if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
24:                 if (multiplier < 0) acc ^= multiplicand;
25:                 multiplier <<= 1;
26:             }
27:             return acc;
28:         }
29: 
30:         int exponentiate(int base, int power)
31:         {
32:             int acc = 1;
33:             for (int i = 0; i < 32; ++i) {
34:                 acc = multiply(acc, acc);
35:                 if (power < 0) acc = multiply(acc, base);
36:                 power <<= 1;
37:             }
38:             return acc;
39:         }
40: 
41:         int inverse(int x) { return exponentiate(x, -2); }
42:     };
43: 
44:     inline int checkKBin(int mod32,
45:         unsigned char const buffer[], unsigned int buflen, int chk = 0)
46:     {
47:         for (unsigned int i = 0; i < buflen; ++i) {
48:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
49:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
50:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
51:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
52:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
53:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
54:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
55:             if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
56:             chk ^= buffer[i];
57:         }
58:         return chk;
59:     }
60: 
61:     inline int check8out(int mod32, int advance, int chk, signed char out)
62:     {
63:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
64:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
65:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
66:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
67:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
68:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
69:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
70:         if (chk < 0) { chk <<= 1; chk ^= mod32; } else chk <<= 1;
71: 
72:         int acc = 0;
73:         if (out < 0) acc ^= advance; out <<= 1;
74:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
75:         if (out < 0) acc ^= advance; out <<= 1;       
76:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
77:         if (out < 0) acc ^= advance; out <<= 1;       
78:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
79:         if (out < 0) acc ^= advance; out <<= 1;       
80:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
81:         if (out < 0) acc ^= advance; out <<= 1;       
82:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
83:         if (out < 0) acc ^= advance; out <<= 1;       
84:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
85:         if (out < 0) acc ^= advance; out <<= 1;       
86:         if (acc < 0) { acc <<= 1; acc ^= mod32; } else acc <<= 1;
87:         if (out < 0) acc ^= advance; out <<= 1;       
88: 
89:         return chk ^ acc;
90:     }
91: 
92: }
93: 
94: #endif /****** AlgoGF.hh / GF(2**32) Finite Field Arithmetic ******/