* zfec -- fast forward error correction library with Python interface
*/
+#include "fec.h"
+
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
-#include "fec.h"
-
-
-/*
- * If you get a error returned (negative value) from a fec_* function,
- * look in here for the error message.
- */
-
-#define FEC_ERROR_SIZE 1025
-char fec_error[FEC_ERROR_SIZE+1];
-
-#define ERR(...) (snprintf(fec_error, FEC_ERROR_SIZE, __VA_ARGS__))
-
/*
* Primitive polynomials - see Lin & Costello, Appendix A,
* and Lee & Messerschmitt, p. 453.
* modnn(x) computes x % GF_SIZE, where GF_SIZE is 2**GF_BITS - 1,
* without a slow divide.
*/
-static inline gf
+static gf
modnn(int x) {
while (x >= 255) {
x -= 255;
#define gf_mul(x,y) gf_mul_table[x][y]
#define USE_GF_MULC register gf * __gf_mulc_
+
#define GF_MULC0(c) __gf_mulc_ = gf_mul_table[c]
#define GF_ADDMULC(dst, x) dst ^= __gf_mulc_[x]
gf_mul_table[0][j] = gf_mul_table[j][0] = 0;
}
-/*
- * i use malloc so many times, it is easier to put checks all in
- * one place.
- */
-static void *
-my_malloc (int sz, char *err_string) {
- void *p = malloc (sz);
- if (p == NULL) {
- ERR("Malloc failure allocating %s\n", err_string);
- exit (1);
- }
- return p;
-}
-
#define NEW_GF_MATRIX(rows, cols) \
- (gf*)my_malloc(rows * cols, " ## __LINE__ ## " )
+ (gf*)malloc(rows * cols)
/*
* initialize the data structures used for computations in GF.
unsigned icol = 0;
unsigned row, col, i, ix;
- unsigned* indxc = (unsigned*) my_malloc (k * sizeof(unsigned), "indxc");
- unsigned* indxr = (unsigned*) my_malloc (k * sizeof(unsigned), "indxr");
- unsigned* ipiv = (unsigned*) my_malloc (k * sizeof(unsigned), "ipiv");
+ unsigned* indxc = (unsigned*) malloc (k * sizeof(unsigned));
+ unsigned* indxr = (unsigned*) malloc (k * sizeof(unsigned));
+ unsigned* ipiv = (unsigned*) malloc (k * sizeof(unsigned));
gf *id_row = NEW_GF_MATRIX (1, k);
- gf *temp_row = NEW_GF_MATRIX (1, k);
memset (id_row, '\0', k * sizeof (gf));
/*
icol = ix;
goto found_piv;
}
- } else if (ipiv[ix] > 1) {
- ERR("singular matrix");
- goto fail;
- }
+ } else
+ assert (ipiv[ix] <= 1);
}
}
}
indxc[col] = icol;
pivot_row = &src[icol * k];
c = pivot_row[icol];
- if (c == 0) {
- ERR("singular matrix 2");
- goto fail;
- }
+ assert (c != 0);
if (c != 1) { /* otherwhise this is a NOP */
/*
* this is done often , but optimizing is not so
if (indxr[col-1] != indxc[col-1])
for (row = 0; row < k; row++)
SWAP (src[row * k + indxr[col-1]], src[row * k + indxc[col-1]], gf);
- fail:
- free (indxc);
- free (indxr);
- free (ipiv);
- free (id_row);
- free (temp_row);
- return;
}
/*
void
fec_free (fec_t *p) {
- if (p == NULL ||
- p->magic != (((FEC_MAGIC ^ p->k) ^ p->n) ^ (unsigned long) (p->enc_matrix))) {
- ERR("bad parameters to fec_free");
- return;
- }
+ assert (p != NULL && p->magic == (((FEC_MAGIC ^ p->k) ^ p->n) ^ (unsigned long) (p->enc_matrix)));
free (p->enc_matrix);
free (p);
}
fec_t *
-fec_new(unsigned k, unsigned n) {
+fec_new(unsigned short k, unsigned short n) {
unsigned row, col;
gf *p, *tmp_m;
fec_t *retval;
- fec_error[FEC_ERROR_SIZE] = '\0';
-
if (fec_initialized == 0)
init_fec ();
- retval = (fec_t *) my_malloc (sizeof (fec_t), "new_code");
+ retval = (fec_t *) malloc (sizeof (fec_t));
retval->k = k;
retval->n = n;
retval->enc_matrix = NEW_GF_MATRIX (n, k);
return retval;
}
+/* To make sure that we stay within cache in the inner loops of fec_encode(). (It would
+ probably help to also do this for fec_decode(). */
+#ifndef STRIDE
+#define STRIDE 8192
+#endif
+
void
fec_encode(const fec_t* code, const gf*restrict const*restrict const src, gf*restrict const*restrict const fecs, const unsigned*restrict const block_nums, size_t num_block_nums, size_t sz) {
unsigned char i, j;
+ size_t k;
unsigned fecnum;
- gf* p;
-
- for (i=0; i<num_block_nums; i++) {
- fecnum=block_nums[i];
- assert (fecnum >= code->k);
- memset(fecs[i], 0, sz);
- p = &(code->enc_matrix[fecnum * code->k]);
- for (j = 0; j < code->k; j++)
- addmul(fecs[i], src[j], p[j], sz);
+ const gf* p;
+
+ for (k = 0; k < sz; k += STRIDE) {
+ size_t stride = ((sz-k) < STRIDE)?(sz-k):STRIDE;
+ for (i=0; i<num_block_nums; i++) {
+ fecnum=block_nums[i];
+ assert (fecnum >= code->k);
+ memset(fecs[i]+k, 0, stride);
+ p = &(code->enc_matrix[fecnum * code->k]);
+ for (j = 0; j < code->k; j++)
+ addmul(fecs[i]+k, src[j]+k, p[j], stride);
+ }
}
}
void
fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*restrict const*restrict const outpkts, const unsigned*restrict const index, size_t sz) {
- gf m_dec[code->k * code->k];
+ gf* m_dec = (gf*)alloca(code->k * code->k);
+ unsigned char outix=0;
+ unsigned char row=0;
+ unsigned char col=0;
build_decode_matrix_into_space(code, index, code->k, m_dec);
- unsigned char outix=0;
- for (unsigned char row=0; row<code->k; row++) {
+ for (row=0; row<code->k; row++) {
+ assert ((index[row] >= code->k) || (index[row] == row)); /* If the block whose number is i is present, then it is required to be in the i'th element. */
if (index[row] >= code->k) {
memset(outpkts[outix], 0, sz);
- for (unsigned char col=0; col < code->k; col++)
+ for (col=0; col < code->k; col++)
addmul(outpkts[outix], inpkts[col], m_dec[row * code->k + col], sz);
outix++;
}
/**
* zfec -- fast forward error correction library with Python interface
- *
+ *
* Copyright (C) 2007 Allmydata, Inc.
* Author: Zooko Wilcox-O'Hearn
- * mailto:zooko@zooko.com
- *
+ *
* This file is part of zfec.
*
- * This program is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License as published by the Free
- * Software Foundation; either version 2 of the License, or (at your option)
- * any later version. This license also comes with the added permission that,
- * if you become obligated to release a derived work under this licence (as
- * per section 2.b of the GPL), you may delay the fulfillment of this
- * obligation for up to 12 months.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- * GNU General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ * See README.txt for licensing information.
*/
/*
- * Much of this work is derived from the "fec" software by Luigi Rizzo, et
- * al., the copyright notice and licence terms of which are included below
- * for reference.
- * fec.c -- forward error correction based on Vandermonde matrices
- * 980624
- * (C) 1997-98 Luigi Rizzo (luigi@iet.unipi.it)
+ * This work is derived from the "fec" software by Luigi Rizzo, et al., the
+ * copyright notice and licence terms of which are included below for reference.
+ * fec.c -- forward error correction based on Vandermonde matrices 980624 (C)
+ * 1997-98 Luigi Rizzo (luigi@iet.unipi.it)
*
* Portions derived from code by Phil Karn (karn@ka9q.ampr.org),
* Robert Morelos-Zaragoza (robert@spectra.eng.hawaii.edu) and Hari
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY
* OF SUCH DAMAGE.
*/
-
projects / tahoe-lafs / zfec.git / blobdiff