M4RIE 20250128
Loading...
Searching...
No Matches
gf2x.h
Go to the documentation of this file.
1
11#ifndef M4RIE_GF2X_H
12#define M4RIE_GF2X_H
13
14/******************************************************************************
15*
16* M4RIE: Linear Algebra over GF(2^e)
17*
18* Copyright (C) 2012 Martin Albrecht <martinralbrecht@googlemail.com>
19*
20* Distributed under the terms of the GNU General Public License (GEL)
21* version 2 or higher.
22*
23* This code is distributed in the hope that it will be useful,
24* but WITHOUT ANY WARRANTY; without even the implied warranty of
25* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
26* General Public License for more details.
27*
28* The full text of the GPL is available at:
29*
30* http://www.gnu.org/licenses/
31******************************************************************************/
32
33#include <m4ri/m4ri.h>
34
35#define __M4RIE_1tF(X) ~((X)-1)
37typedef int deg_t;
43static inline word gf2x_mul(const word a, const word b, deg_t d) {
44 word res = 0;
45
46 switch(d) {
47 case 32: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(31)) >>31) & (b<<31);
48 case 31: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(30)) >>30) & (b<<30);
49 case 30: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(29)) >>29) & (b<<29);
50 case 29: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(28)) >>28) & (b<<28);
51 case 28: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(27)) >>27) & (b<<27);
52 case 27: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(26)) >>26) & (b<<26);
53 case 26: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(25)) >>25) & (b<<25);
54 case 25: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(24)) >>24) & (b<<24);
55 case 24: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(23)) >>23) & (b<<23);
56 case 23: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(22)) >>22) & (b<<22);
57 case 22: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(21)) >>21) & (b<<21);
58 case 21: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(20)) >>20) & (b<<20);
59 case 20: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(19)) >>19) & (b<<19);
60 case 19: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(18)) >>18) & (b<<18);
61 case 18: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(17)) >>17) & (b<<17);
62 case 17: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(16)) >>16) & (b<<16);
63 case 16: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(15)) >>15) & (b<<15);
64 case 15: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(14)) >>14) & (b<<14);
65 case 14: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(13)) >>13) & (b<<13);
66 case 13: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(12)) >>12) & (b<<12);
67 case 12: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(11)) >>11) & (b<<11);
68 case 11: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW(10)) >>10) & (b<<10);
69 case 10: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 9)) >> 9) & (b<< 9);
70 case 9: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 8)) >> 8) & (b<< 8);
71 case 8: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 7)) >> 7) & (b<< 7);
72 case 7: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 6)) >> 6) & (b<< 6);
73 case 6: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 5)) >> 5) & (b<< 5);
74 case 5: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 4)) >> 4) & (b<< 4);
75 case 4: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 3)) >> 3) & (b<< 3);
76 case 3: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 2)) >> 2) & (b<< 2);
77 case 2: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 1)) >> 1) & (b<< 1);
78 case 1: res ^= __M4RIE_1tF((a & __M4RI_TWOPOW( 0)) >> 0) & (b<< 0);
79 break;
80 default:
81 m4ri_die("degree %d too big.\n",d);
82 }
83 return res;
84}
91static inline deg_t gf2x_deg(word a) {
92 deg_t degree = 0;
93 if( (a & 0xffffffff00000000ULL) != 0) { degree += 32; a>>=32; }
94 if( (a & 0xffff0000ULL) != 0) { degree += 16; a>>=16; }
95 if( (a & 0xff00ULL) != 0) { degree += 8; a>>= 8; }
96 if( (a & 0xf0ULL) != 0) { degree += 4; a>>= 4; }
97 if( (a & 0xcULL) != 0) { degree += 2; a>>= 2; }
98 if( (a & 0x2ULL) != 0) { degree += 1; a>>= 1; }
99 return degree;
100}
101
106static inline word gf2x_div(word a, word b) {
107 word res = 0;
108 word mask = 0;
109 const deg_t deg_b = gf2x_deg(b);
110 for(deg_t deg_a = gf2x_deg(a); deg_a >= deg_b; deg_a--) {
111 mask = __M4RIE_1tF(a>>deg_a);
112 res |= mask & __M4RI_TWOPOW(deg_a - deg_b);
113 a ^= mask & b<<(deg_a - deg_b);
114 }
115 return res;
116}
117
122static inline word gf2x_mod(word a, word b) {
123 const deg_t deg_b = gf2x_deg(b);
124 for(deg_t deg_a=gf2x_deg(a); deg_a>=deg_b; deg_a--) {
125 a ^= __M4RIE_1tF(a>>deg_a) & b<<(deg_a - deg_b);
126 }
127 return a;
128}
129
134static inline word gf2x_divmod(word a, word b, word *rem) {
135 word res = 0;
136 word mask = 0;
137 const deg_t deg_b = gf2x_deg(b);
138 for(deg_t deg_a=gf2x_deg(a); deg_a>=deg_b; deg_a--) {
139 mask = __M4RIE_1tF(a>>deg_a);
140 res |= mask & __M4RI_TWOPOW(deg_a - deg_b);
141 a ^= mask & b<<(deg_a - deg_b);
142 }
143 *rem = a;
144 return res;
145}
146
147
152static inline word gf2x_invmod(word a, word b, const deg_t d) {
153 word x = 0;
154 word lastx = 1;
155 word y = 1;
156 word lasty = 0;
157
158 word rem;
159 word quo;
160 word tmp = 0;
161
162 while (b != 0) {
163 quo = gf2x_divmod(a,b, &rem);
164 a = b; b = rem;
165 tmp = x; x = lastx ^ gf2x_mul(quo, x, d); lastx = tmp;
166 tmp = y; y = lasty ^ gf2x_mul(quo, y, d); lasty = tmp;
167 }
168 return lastx;
169}
170
171#endif //M4RIE_GF2X_H
int deg_t
Definition gf2x.h:37
static deg_t gf2x_deg(word a)
deg(a) in .
Definition gf2x.h:91
#define __M4RIE_1tF(X)
Definition gf2x.h:35
static word gf2x_mul(const word a, const word b, deg_t d)
a*b in with deg(a) and deg(b) < d.
Definition gf2x.h:43
static word gf2x_invmod(word a, word b, const deg_t d)
a^(-1) % b with deg(a), deg(b) <= d.
Definition gf2x.h:152
static word gf2x_mod(word a, word b)
a mod b in .
Definition gf2x.h:122
static word gf2x_divmod(word a, word b, word *rem)
a / b and a mod b in .
Definition gf2x.h:134
static word gf2x_div(word a, word b)
a / b in .
Definition gf2x.h:106