gf2e.h

Go to the documentation of this file.

 
#ifndef M4RIE_GF2E_H
#define M4RIE_GF2E_H
 
/******************************************************************************
*
*            M4RIE: Linear Algebra over GF(2^e)
*
*    Copyright (C) 2010,2011 Martin Albrecht <martinralbrecht@googlemail.com>
*
*  Distributed under the terms of the GNU General Public License (GPL)
*  version 2 or higher.
*
*    This code is distributed in the hope that it will be useful,
*    but WITHOUT ANY WARRANTY; without even the implied warranty of
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
*    General Public License for more details.
*
*  The full text of the GPL is available at:
*
*                  http://www.gnu.org/licenses/
******************************************************************************/
 
#include <m4ri/m4ri.h>
#include <m4rie/gf2x.h>
 
#ifdef _WIN32
  #if defined(DLL_EXPORT) && defined(M4RIE_BUILDING_M4RIE)
    #define M4RIE_DLL_EXPORT __declspec(dllexport)
  #elif defined(M4RI_USE_DLL) && !defined(M4RIE_BUILDING_M4RIE)
    #define M4RIE_DLL_EXPORT __declspec(dllimport)
  #else
    #define M4RIE_DLL_EXPORT
  #endif
#else
  #define M4RIE_DLL_EXPORT
#endif

 
#define M4RIE_MAX_DEGREE 16

 
typedef struct gf2e_struct gf2e;

 
struct gf2e_struct {
  deg_t degree;    
  word minpoly;   
 
  word *pow_gen; 
  word *red;     
  word **_mul;   
 
  word (*inv)(const gf2e *ff, const word a); 
  word (*mul)(const gf2e *ff, const word a, const word b); 
};

 
gf2e *gf2e_init(const word minpoly);

 
void gf2e_free(gf2e *ff);

 
static inline word gf2e_inv(const gf2e *ff, word a) {
  return gf2x_invmod(a, ff->minpoly, ff->degree);
}

 
static inline word _gf2e_mul_table(const gf2e *ff, const word a, const word b) {
  return ff->_mul[a][b];
}

 
static inline word _gf2e_mul_arith(const gf2e *ff, const word a, const word b) {
  const word res = gf2x_mul(a, b, ff->degree);
  return res ^ ff->red[res>>ff->degree];
}

 
static inline word gf2e_mul(const gf2e *ff, const word a, const word b) {
  if( ff->_mul != NULL )
    return _gf2e_mul_table(ff, a, b);
  else
    return _gf2e_mul_arith(ff, a, b);
}

 
static inline size_t gf2e_degree_to_w(const gf2e *ff) {
  switch(ff->degree) {
  case 2:
    return 2;
  case  3:
  case  4:
    return 4;
  case  5:
  case  6:
  case  7:
  case  8:
    return 8;
  case  9:
  case 10:
  case 11:
  case 12:
  case 13:
  case 14:
  case 15:
  case 16:
    return 16;
  default:
    m4ri_die("degree %d not supported.\n",ff->degree);
  }
  return 0;
}

 
static inline word *gf2e_t16_init(const gf2e *ff, const word a) {
  word *mul = (word*)m4ri_mm_calloc(1<<16, sizeof(word));
 
  const deg_t w = gf2e_degree_to_w(ff);
  const word mask_w = (1<<w)-1;

  for(word i=0; i<1<<16; i++) {
    switch(w) {
    case 2:
      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;
      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;
      break;
    case 4:
      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;
      break;
    case 8:
      mul[i]  = gf2e_mul(ff, a, (i&mask_w)) | gf2e_mul(ff, a, ((i>>8)&mask_w))<<8;
      break;
    case 16:
      mul[i]  = gf2e_mul(ff, a, (i&mask_w));
      break;
    };
  }
  return mul;
}

 
static inline void gf2e_t16_free(word *mul) {
  m4ri_mm_free(mul);
}

 
M4RIE_DLL_EXPORT extern const word* irreducible_polynomials[17];
 
#endif //M4RIE_GF2E_H