M4RIE 20250128
Loading...
Searching...
No Matches
gf2e.h
Go to the documentation of this file.
1
9#ifndef M4RIE_GF2E_H
10#define M4RIE_GF2E_H
11
12/******************************************************************************
13*
14* M4RIE: Linear Algebra over GF(2^e)
15*
16* Copyright (C) 2010,2011 Martin Albrecht <martinralbrecht@googlemail.com>
17*
18* Distributed under the terms of the GNU General Public License (GPL)
19* version 2 or higher.
20*
21* This code is distributed in the hope that it will be useful,
22* but WITHOUT ANY WARRANTY; without even the implied warranty of
23* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
24* General Public License for more details.
25*
26* The full text of the GPL is available at:
27*
28* http://www.gnu.org/licenses/
29******************************************************************************/
30
31#include <m4ri/m4ri.h>
32#include <m4rie/gf2x.h>
33
34#ifdef _WIN32
35 #if defined(DLL_EXPORT) && defined(M4RIE_BUILDING_M4RIE)
36 #define M4RIE_DLL_EXPORT __declspec(dllexport)
37 #elif defined(M4RI_USE_DLL) && !defined(M4RIE_BUILDING_M4RIE)
38 #define M4RIE_DLL_EXPORT __declspec(dllimport)
39 #else
40 #define M4RIE_DLL_EXPORT
41 #endif
42#else
43 #define M4RIE_DLL_EXPORT
44#endif
45
50#define M4RIE_MAX_DEGREE 16
51
56typedef struct gf2e_struct gf2e;
57
64 word minpoly;
66 word *pow_gen;
67 word *red;
68 word **_mul;
70 word (*inv)(const gf2e *ff, const word a);
71 word (*mul)(const gf2e *ff, const word a, const word b);
72};
73
80gf2e *gf2e_init(const word minpoly);
81
88void gf2e_free(gf2e *ff);
89
94static inline word gf2e_inv(const gf2e *ff, word a) {
95 return gf2x_invmod(a, ff->minpoly, ff->degree);
96}
97
102static inline word _gf2e_mul_table(const gf2e *ff, const word a, const word b) {
103 return ff->_mul[a][b];
104}
105
110static inline word _gf2e_mul_arith(const gf2e *ff, const word a, const word b) {
111 const word res = gf2x_mul(a, b, ff->degree);
112 return res ^ ff->red[res>>ff->degree];
113}
114
119static inline word gf2e_mul(const gf2e *ff, const word a, const word b) {
120 if( ff->_mul != NULL )
121 return _gf2e_mul_table(ff, a, b);
122 else
123 return _gf2e_mul_arith(ff, a, b);
124}
125
132static inline size_t gf2e_degree_to_w(const gf2e *ff) {
133 switch(ff->degree) {
134 case 2:
135 return 2;
136 case 3:
137 case 4:
138 return 4;
139 case 5:
140 case 6:
141 case 7:
142 case 8:
143 return 8;
144 case 9:
145 case 10:
146 case 11:
147 case 12:
148 case 13:
149 case 14:
150 case 15:
151 case 16:
152 return 16;
153 default:
154 m4ri_die("degree %d not supported.\n",ff->degree);
155 }
156 return 0;
157}
158
166static inline word *gf2e_t16_init(const gf2e *ff, const word a) {
167 word *mul = (word*)m4ri_mm_calloc(1<<16, sizeof(word));
168
169 const deg_t w = gf2e_degree_to_w(ff);
170 const word mask_w = (1<<w)-1;
171
175 for(word i=0; i<1<<16; i++) {
176 switch(w) {
177 case 2:
178 mul[i] = gf2e_mul(ff, a, ((i>>0)&mask_w))<<0 | gf2e_mul(ff, a, ((i>> 2)&mask_w))<< 2 | gf2e_mul(ff, a, ((i>> 4)&mask_w))<< 4 | gf2e_mul(ff, a, ((i>> 6)&mask_w))<< 6;
179 mul[i] |= gf2e_mul(ff, a, ((i>>8)&mask_w))<<8 | gf2e_mul(ff, a, ((i>>10)&mask_w))<<10 | gf2e_mul(ff, a, ((i>>12)&mask_w))<<12 | gf2e_mul(ff, a, ((i>>14)&mask_w))<<14;
180 break;
181 case 4:
182 mul[i] = gf2e_mul(ff, a, (i&mask_w)) | gf2e_mul(ff, a, ((i>>4)&mask_w))<<4 | gf2e_mul(ff, a, ((i>>8)&mask_w))<<8 | gf2e_mul(ff, a, ((i>>12)&mask_w))<<12;
183 break;
184 case 8:
185 mul[i] = gf2e_mul(ff, a, (i&mask_w)) | gf2e_mul(ff, a, ((i>>8)&mask_w))<<8;
186 break;
187 case 16:
188 mul[i] = gf2e_mul(ff, a, (i&mask_w));
189 break;
190 };
191 }
192 return mul;
193}
194
201static inline void gf2e_t16_free(word *mul) {
202 m4ri_mm_free(mul);
203}
204
209M4RIE_DLL_EXPORT extern const word* irreducible_polynomials[17];
210
211#endif //M4RIE_GF2E_H
void gf2e_free(gf2e *ff)
Definition gf2e.c:56
static word _gf2e_mul_table(const gf2e *ff, const word a, const word b)
a*b in using a table lookups.
Definition gf2e.h:102
static size_t gf2e_degree_to_w(const gf2e *ff)
Definition gf2e.h:132
static void gf2e_t16_free(word *mul)
Free multiplication table.
Definition gf2e.h:201
static word _gf2e_mul_arith(const gf2e *ff, const word a, const word b)
a*b in using a gf2x_mul() lookups.
Definition gf2e.h:110
gf2e * gf2e_init(const word minpoly)
Definition gf2e.c:4
static word * gf2e_t16_init(const gf2e *ff, const word a)
Definition gf2e.h:166
static word gf2e_mul(const gf2e *ff, const word a, const word b)
a*b in .
Definition gf2e.h:119
M4RIE_DLL_EXPORT const word * irreducible_polynomials[17]
all Irreducible polynomials over GF(2) up to degree 16.
Definition gf2e.c:85
static word gf2e_inv(const gf2e *ff, word a)
a^(-1) % minpoly
Definition gf2e.h:94
int deg_t
Definition gf2x.h:37
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
Definition gf2e.h:62
deg_t degree
Definition gf2e.h:63
word ** _mul
Definition gf2e.h:68
word minpoly
Definition gf2e.h:64
word * red
Definition gf2e.h:67
word(* inv)(const gf2e *ff, const word a)
Definition gf2e.h:70
word * pow_gen
Definition gf2e.h:66
word(* mul)(const gf2e *ff, const word a, const word b)
Definition gf2e.h:71