M4RIE  0.20111004
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 
56 typedef struct gf2e_struct gf2e;
57 
62 struct gf2e_struct {
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 
80 gf2e *gf2e_init(const word minpoly);
81 
88 void gf2e_free(gf2e *ff);
89 
94 static inline word gf2e_inv(const gf2e *ff, word a) {
95  return gf2x_invmod(a, ff->minpoly, ff->degree);
96 }
97 
102 static inline word _gf2e_mul_table(const gf2e *ff, const word a, const word b) {
103  return ff->_mul[a][b];
104 }
105 
110 static 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 
119 static 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 
132 static 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 
166 static 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 
201 static inline void gf2e_t16_free(word *mul) {
202  m4ri_mm_free(mul);
203 }
204 
209 M4RIE_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
gf2e * gf2e_init(const word minpoly)
Definition: gf2e.c:4
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
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
for degrees < 64
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