+/** \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)
*
* OF SUCH DAMAGE.
*/
+#include <regex.h>
+
#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;
static unsigned char *alloc_matrix(int rows, int cols)
{
- return para_malloc(rows * cols);
+ return arr_alloc(rows, cols);
}
/*
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]];
}
}
+/** 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)
{
int irow, icol, row, col, ix, error;
- int *indxc = para_malloc(k * sizeof(int));
- int *indxr = para_malloc(k * sizeof(int));
- int *ipiv = para_malloc(k * sizeof(int)); /* elements used as pivots */
+ int *indxc = arr_alloc(k, sizeof(int));
+ int *indxr = arr_alloc(k, sizeof(int));
+ int *ipiv = arr_alloc(k, sizeof(int)); /* elements used as pivots */
unsigned char c, *p, *id_row = alloc_matrix(1, k),
*temp_row = alloc_matrix(1, k);
* c holds the coefficient of P(x) = Prod (x - p_i), i=0..k-1
* b holds the coefficient for the matrix inversion
*/
- c = para_malloc(k);
- b = para_malloc(k);
- p = para_malloc(k);
+ c = alloc(k);
+ b = alloc(k);
+ p = alloc(k);
for (j = 1, i = 0; i < k; i++, j += k) {
c[i] = 0;
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;
};
if (k < 1 || k > GF_SIZE + 1 || n > GF_SIZE + 1 || k > n)
return -E_FEC_PARMS;
- parms = para_malloc(sizeof(struct fec_parms));
+ parms = alloc(sizeof(struct fec_parms));
parms->k = k;
parms->n = n;
parms->enc_matrix = alloc_matrix(n, k);
if (ret < 0)
return ret;
/* do the actual decoding */
- slice = para_malloc(k * sizeof(unsigned char *));
+ slice = arr_alloc(k, sizeof(unsigned char *));
for (row = 0; row < k; row++) {
if (idx[row] >= k) {
- slice[row] = para_calloc(sz);
+ slice[row] = zalloc(sz);
for (col = 0; col < k; col++)
addmul(slice[row], data[col],
m_dec[row * k + col], sz);
projects / paraslash.git / blobdiff