X-Git-Url: http://git.tuebingen.mpg.de/?p=paraslash.git;a=blobdiff_plain;f=fec.c;h=2301cc8d2d4653b8bc82a8bcc46b5867b5d7af14;hp=e543aedcfc7078d81e4c3165f2e379fa77571502;hb=0cbd0ac87ebe208b0d47df28e86c16886bdb687d;hpb=7565af270650435630bf212592286a8c6555d749 diff --git a/fec.c b/fec.c index e543aedc..2301cc8d 100644 --- a/fec.c +++ b/fec.c @@ -1,5 +1,6 @@ +/** \file fec.c Forward error correction based on Vandermonde matrices. */ + /* - * fec.c -- forward error correction based on Vandermonde matrices * 980624 * (C) 1997-98 Luigi Rizzo (luigi@iet.unipi.it) * @@ -32,30 +33,48 @@ * OF SUCH DAMAGE. */ +#include + #include "para.h" #include "error.h" #include "portable_io.h" #include "string.h" #include "fec.h" -#define GF_BITS 8 /* code over GF(256) */ +/** Code over GF(256). */ +#define GF_BITS 8 +/** The largest number in GF(256) */ #define GF_SIZE ((1 << GF_BITS) - 1) /* * To speed up computations, we have tables for logarithm, exponent and inverse - * of a number. We use a table for multiplication as well (it takes 64K, no big - * deal even on a PDA, especially because it can be pre-initialized an put into - * a ROM!). The macro gf_mul(x,y) takes care of multiplications. + * of a number. + */ + +/** Index->poly form conversion table. */ +static unsigned char gf_exp[2 * GF_SIZE]; + +/** Poly->index form conversion table. */ +static int gf_log[GF_SIZE + 1]; + +/** Inverse of a field element. */ +static unsigned char inverse[GF_SIZE + 1]; + +/** + * The multiplication table. + * + * We use a table for multiplication as well. It takes 64K, no big deal even on + * a PDA, especially because it can be pre-initialized and put into a ROM. + * + * \sa \ref gf_mul. */ -static unsigned char gf_exp[2 * GF_SIZE]; /* index->poly form conversion table */ -static int gf_log[GF_SIZE + 1]; /* Poly->index form conversion table */ -static unsigned char inverse[GF_SIZE + 1]; /* inverse of field elem. */ static unsigned char gf_mul_table[GF_SIZE + 1][GF_SIZE + 1]; -/* Multiply two numbers. */ + +/** Multiply two GF numbers. */ #define gf_mul(x,y) gf_mul_table[x][y] /* Compute x % GF_SIZE without a slow divide. */ -static inline unsigned char modnn(int x) +__a_const static inline unsigned char modnn(int x) { while (x >= GF_SIZE) { x -= GF_SIZE; @@ -151,21 +170,27 @@ static void generate_gf(void) inverse[i] = gf_exp[GF_SIZE - gf_log[i]]; } +/** How often the loop is unrolled. */ +#define UNROLL 16 + /* * Compute dst[] = dst[] + c * src[] * * This is used often, so better optimize it! Currently the loop is unrolled 16 * times. The case c=0 is also optimized, whereas c=1 is not. */ -#define UNROLL 16 -static void addmul(unsigned char *dst1, const unsigned char const *src1, +static void addmul(unsigned char *dst1, const unsigned char *src1, unsigned char c, int sz) { + unsigned char *dst, *lim, *col; + const unsigned char *src = src1; + if (c == 0) return; - unsigned char *dst = dst1, *lim = &dst[sz - UNROLL + 1], - *col = gf_mul_table[c]; - const unsigned char const *src = src1; + + dst = dst1; + lim = &dst[sz - UNROLL + 1]; + col = gf_mul_table[c]; for (; dst < lim; dst += UNROLL, src += UNROLL) { dst[0] ^= col[src[0]]; @@ -208,13 +233,14 @@ static void matmul(unsigned char *a, unsigned char *b, unsigned char *c, } } +/** Swap two numbers. */ #define FEC_SWAP(a,b) {typeof(a) tmp = a; a = b; b = tmp;} /* * Compute the inverse of a matrix. * * k is the size of the matrix 'src' (Gauss-Jordan, adapted from Numerical - * Recipes in C). Returns -1 if 'src' is singular. + * Recipes in C). Returns negative on errors. */ static int invert_mat(unsigned char *src, int k) { @@ -394,8 +420,13 @@ static void init_fec(void) fec_initialized = 1; } +/** Internal FEC parameters. */ struct fec_parms { - int k, n; /* parameters of the code */ + /** Number of data slices. */ + int k; + /** Number of slices (including redundant slices). */ + int n; + /** The encoding matrix, computed by init_fec(). */ unsigned char *enc_matrix; }; @@ -480,7 +511,7 @@ int fec_new(int k, int n, struct fec_parms **result) * \param sz The size of the input data packets. * * Encode the \a k slices of size \a sz given by \a src and store the output - * slice number \a idx in \dst. + * slice number \a idx in \a dst. */ void fec_encode(struct fec_parms *parms, const unsigned char * const *src, unsigned char *dst, int idx, int sz) @@ -553,7 +584,7 @@ err: /** * Decode one slice from the group of received slices. * - * \param code Pointer to fec params structure. + * \param parms Pointer to fec params structure. * \param data Pointers to received packets. * \param idx Pointer to packet indices (gets modified). * \param sz Size of each packet.