From ece5448eb342296f8ae99d2f32162c0c437f9ccd Mon Sep 17 00:00:00 2001 From: Daniel Borkmann Date: Sat, 2 Jun 2012 16:00:17 +0200 Subject: [PATCH] gf: add gf operations Signed-off-by: Daniel Borkmann --- src/gf.c | 117 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/gf.h | 57 ++++++++++++++++++++++++ src/transsip/Makefile | 1 + 3 files changed, 175 insertions(+) create mode 100644 src/gf.c create mode 100644 src/gf.h diff --git a/src/gf.c b/src/gf.c new file mode 100644 index 0000000..541914d --- /dev/null +++ b/src/gf.c @@ -0,0 +1,117 @@ +/* + * transsip - the telephony toolkit + * By Daniel Borkmann + * Copyright 2012 Daniel Borkmann , + * Swiss federal institute of technology (ETH Zurich) + * Subject to the GPL, version 2. + * Based on Bhaskar Biswas and Nicolas Sendrier McEliece + * implementation, LGPL 2.1. + */ + +#include +#include +#include + +#include "gf.h" +#include "die.h" +#include "xmalloc.h" + +/* this is our primary consideration....think about changing!? */ +#define MAX_EXT_DEG 16 + +static const uint32_t prim_poly[MAX_EXT_DEG + 1] = { + 01, /* extension degree 0 (!) never used */ + 03, /* extension degree 1 (!) never used */ + 07, /* extension degree 2 */ + 013, /* extension degree 3 */ + 023, /* extension degree 4 */ + 045, /* extension degree 5 */ + 0103, /* extension degree 6 */ + 0203, /* extension degree 7 */ + 0435, /* extension degree 8 */ + 01041, /* extension degree 9 */ + 02011, /* extension degree 10 */ + 04005, /* extension degree 11 */ + 010123, /* extension degree 12 */ + 020033, /* extension degree 13 */ + 042103, /* extension degree 14 */ + 0100003, /* extension degree 15 */ + 0210013 /* extension degree 16 */ +}; + +uint32_t gf_extension_degree, gf_cardinality, gf_multiplicative_order; + +gf16_t *gf_log_t, *gf_exp_t; + +static int init_done = 0; + +/* construct the table gf_exp[i]=alpha^i */ +static void gf_init_exp_table(void) +{ + int i; + + gf_exp_t = xzmalloc((1 << gf_extd()) * sizeof(*gf_exp_t)); + gf_exp_t[0] = 1; + for (i = 1; i < gf_ord(); ++i) { + gf_exp_t[i] = gf_exp_t[i - 1] << 1; + if (gf_exp_t[i - 1] & (1 << (gf_extd() - 1))) + gf_exp_t[i] ^= prim_poly[gf_extd()]; + } + /* hack for the multiplication */ + gf_exp_t[gf_ord()] = 1; +} + +/* construct the table gf_log[alpha^i]=i */ +static void gf_init_log_table(void) +{ + int i; + + gf_log_t = xzmalloc((1 << gf_extd()) * sizeof(*gf_log_t)); + gf_log_t[0] = gf_ord(); + for (i = 0; i < gf_ord() ; ++i) + gf_log_t[gf_exp_t[i]] = i; +} + +void gf_init(int extdeg) +{ + if (extdeg > MAX_EXT_DEG) + panic("Extension degree %d not implemented !\n", extdeg); + if (init_done != extdeg) { + if (init_done) { + xfree(gf_exp_t); + xfree(gf_log_t); + } + + gf_extension_degree = extdeg; + gf_cardinality = 1 << extdeg; + gf_multiplicative_order = gf_cardinality - 1; + gf_init_exp_table(); + gf_init_log_table(); + + init_done = extdeg; + } +} + +/* we suppose i >= 0. Par convention 0^0 = 1 */ +gf16_t gf_pow(gf16_t x, int i) +{ + if (i == 0) + return 1; + else if (x == 0) + return 0; + else { + /* i mod (q-1) */ + while (i >> gf_extd()) + i = (i & (gf_ord())) + (i >> gf_extd()); + i *= gf_log_t[x]; + while (i >> gf_extd()) + i = (i & (gf_ord())) + (i >> gf_extd()); + return gf_exp_t[i]; + } +} + +/* u8rnd is a function returning a random byte */ +gf16_t gf_rand(int (*rnd_u8)(void)) +{ + return (rnd_u8() ^ (rnd_u8() << 8)) & gf_ord(); +} diff --git a/src/gf.h b/src/gf.h new file mode 100644 index 0000000..b440d51 --- /dev/null +++ b/src/gf.h @@ -0,0 +1,57 @@ +/* + * transsip - the telephony toolkit + * By Daniel Borkmann + * Copyright 2012 Daniel Borkmann , + * Swiss federal institute of technology (ETH Zurich) + * Subject to the GPL, version 2. + * Based on Bhaskar Biswas and Nicolas Sendrier McEliece + * implementation, LGPL 2.1. + */ + +#ifndef GF_H +#define GF_H + +#include + +typedef uint16_t gf16_t; + +extern uint32_t gf_extension_degree, gf_cardinality, gf_multiplicative_order; +extern gf16_t *gf_log_t, *gf_exp_t; + +#define gf_extd() gf_extension_degree +#define gf_card() gf_cardinality +#define gf_ord() gf_multiplicative_order + +#define gf_unit() 1 +#define gf_zero() 0 + +#define gf_add(x, y) ((x) ^ (y)) +#define gf_sub(x, y) ((x) ^ (y)) +#define gf_exp(i) gf_exp_t[i] /* alpha^i */ +#define gf_log(x) gf_log_t[x] /* return i when x=alpha^i */ + +#define gf_zdo(t, func) ((t) ? (func) : 0) + +/** + * residual modulo q-1 + * when -q < d < 0, we get (q-1+d) + * when 0 <= d < q, we get (d) + * when q <= d < 2q-1, we get (d-q+1) + * we obtain a value between 0 and (q-1) included, the class of 0 is + * represented by 0 or q-1 (this is why we write + * _K->exp[q-1] = _K->exp[0] = 1) + */ +#define _gf_modq_1(d) (((d) & gf_ord()) + ((d) >> gf_extd())) + +#define gf_mul_fast(x, y) gf_zdo(y, gf_exp[_gf_modq_1(gf_log[x] + gf_log[y])]) +#define gf_mul(x, y) gf_zdo(x, gf_mul_fast(x, y)) +#define gf_square(x) gf_zdo(x, gf_exp[_gf_modq_1(gf_log[x] << 1)]) +#define gf_sqrt(x) gf_zdo(x, gf_exp[_gf_modq_1(gf_log[x] << (gf_extd() - 1))]) +#define gf_div(x, y) gf_zdo(x, gf_exp[_gf_modq_1(gf_log[x] - gf_log[y])]) +#define gf_inv(x) gf_exp[gf_ord() - gf_log[x]] + +extern void gf_init(int extdeg); +extern gf16_t gf_rand(int (*rnd_u8)(void)); +extern gf16_t gf_pow(gf16_t x, int i); + +#endif /* GF_H */ diff --git a/src/transsip/Makefile b/src/transsip/Makefile index f64ddd0..634de8a 100644 --- a/src/transsip/Makefile +++ b/src/transsip/Makefile @@ -7,6 +7,7 @@ CFLAGS += -DPROGNAME_STRING="\"transsip\"" -DVERSION_STRING="\"0.5.0\"" core-objs = transsip.o lib-objs = xmalloc.o \ + gf.o \ alsa.o \ engine.o \ notifier.o \ -- 2.11.4.GIT