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