src/gf.c

   1 /*
   2  * transsip - the telephony toolkit
   3  * By Daniel Borkmann <daniel@transsip.org>
   4  * Copyright 2012 Daniel Borkmann <dborkma@tik.ee.ethz.ch>,
   5  * Swiss federal institute of technology (ETH Zurich)
   6  * Subject to the GPL, version 2.
   7  * Based on Bhaskar Biswas and Nicolas Sendrier McEliece
   8  * implementation, LGPL 2.1.
   9  */
  10
  11 #include <stdio.h>
  12 #include <stdlib.h>
  13 #include <stdint.h>
  14
  15 #include "gf.h"
  16 #include "die.h"
  17 #include "xmalloc.h"
  18
  19 /* this is our primary consideration....think about changing!? */
  20 #define MAX_EXT_DEG     16
  21
  22 static const uint32_t prim_poly[MAX_EXT_DEG + 1] = {
  23         01,             /* extension degree 0 (!) never used */
  24         03,             /* extension degree 1 (!) never used */
  25         07,             /* extension degree 2 */
  26         013,            /* extension degree 3 */
  27         023,            /* extension degree 4 */
  28         045,            /* extension degree 5 */
  29         0103,           /* extension degree 6 */
  30         0203,           /* extension degree 7 */
  31         0435,           /* extension degree 8 */
  32         01041,          /* extension degree 9 */
  33         02011,          /* extension degree 10 */
  34         04005,          /* extension degree 11 */
  35         010123,         /* extension degree 12 */
  36         020033,         /* extension degree 13 */
  37         042103,         /* extension degree 14 */
  38         0100003,        /* extension degree 15 */
  39         0210013         /* extension degree 16 */
  40 };
  41
  42 uint32_t gf_extension_degree, gf_cardinality, gf_multiplicative_order;
  43
  44 gf16_t *gf_log_t, *gf_exp_t;
  45
  46 static int init_done = 0;
  47
  48 /* construct the table gf_exp[i]=alpha^i */
  49 static void gf_init_exp_table(void)
  50 {
  51         int i;
  52
  53         gf_exp_t = xzmalloc((1 << gf_extd()) * sizeof(*gf_exp_t));
  54         gf_exp_t[0] = 1;
  55         for (i = 1; i < gf_ord(); ++i) {
  56                 gf_exp_t[i] = gf_exp_t[i - 1] << 1;
  57                 if (gf_exp_t[i - 1] & (1 << (gf_extd() - 1)))
  58                         gf_exp_t[i] ^= prim_poly[gf_extd()];
  59         }
  60         /* hack for the multiplication */
  61         gf_exp_t[gf_ord()] = 1;
  62 }
  63
  64 /* construct the table gf_log[alpha^i]=i */
  65 static void gf_init_log_table(void)
  66 {
  67         int i;
  68
  69         gf_log_t = xzmalloc((1 << gf_extd()) * sizeof(*gf_log_t));
  70         gf_log_t[0] = gf_ord();
  71         for (i = 0; i < gf_ord() ; ++i)
  72                 gf_log_t[gf_exp_t[i]] = i;
  73 }
  74
  75 void gf_init(int extdeg)
  76 {
  77         if (extdeg > MAX_EXT_DEG)
  78                 panic("Extension degree %d not implemented !\n", extdeg);
  79         if (init_done != extdeg) {
  80                 if (init_done) {
  81                         xfree(gf_exp_t);
  82                         xfree(gf_log_t);
  83                 }
  84
  85                 gf_extension_degree = extdeg;
  86                 gf_cardinality = 1 << extdeg;
  87                 gf_multiplicative_order = gf_cardinality - 1;
  88                 gf_init_exp_table();
  89                 gf_init_log_table();
  90
  91                 init_done = extdeg;
  92         }
  93 }
  94
  95 /* we suppose i >= 0. Par convention 0^0 = 1 */
  96 gf16_t gf_pow(gf16_t x, int i)
  97 {
  98         if (i == 0)
  99                 return 1;
 100         else if (x == 0)
 101                 return 0;
 102         else {
 103                 /* i mod (q-1) */
 104                 while (i >> gf_extd())
 105                         i = (i & (gf_ord())) + (i >> gf_extd());
 106                 i *= gf_log_t[x];
 107                 while (i >> gf_extd())
 108                         i = (i & (gf_ord())) + (i >> gf_extd());
 109                 return gf_exp_t[i];
 110         }
 111 }
 112
 113 /* u8rnd is a function returning a random byte */
 114 gf16_t gf_rand(int (*rnd_u8)(void))
 115 {
 116         return (rnd_u8() ^ (rnd_u8() << 8)) & gf_ord();
 117 }