narrow types of k and m from unsigned to unsigned short

[tahoe-lafs/zfec.git] / zfec / zfec / fec.c

diff --git a/zfec/zfec/fec.c b/zfec/zfec/fec.c
index 796425e5b7060feb93893c0036a4dc2203f3ed0c..637498d02aa01244f175f41eedc621f8ad4fc650 100644 (file)
--- a/zfec/zfec/fec.c
+++ b/zfec/zfec/fec.c
@@ -9,21 +9,6 @@
 #include <string.h>
 #include <assert.h>
 
-#if defined(_MSC_VER)
-// actually, some of the flavors (i.e. Enterprise) do support restrict
-//#define restrict __restrict
-#define restrict
-#define inline __inline
-#define alloca _alloca
-#else
-#ifdef __GNUC__
-#define alloca(x) __builtin_alloca(x)
-#else
-#include <alloca.h>
-#endif
-#endif
-
-
 /*
  * Primitive polynomials - see Lin & Costello, Appendix A,
  * and  Lee & Messerschmitt, p. 453.
@@ -49,7 +34,7 @@ static gf inverse[256]; /* inverse of field elem.               */
  * 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;
@@ -75,6 +60,7 @@ static gf gf_mul_table[256][256];
 #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]
 
@@ -426,7 +412,7 @@ fec_free (fec_t *p) {
 }
 
 fec_t *
-fec_new(unsigned k, unsigned n) {
+fec_new(unsigned short k, unsigned short n) {
     unsigned row, col;
     gf *p, *tmp_m;
 
@@ -470,19 +456,29 @@ fec_new(unsigned k, unsigned n) {
     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);
+        }
     }
 }
 
@@ -515,6 +511,7 @@ fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*
     build_decode_matrix_into_space(code, index, code->k, m_dec);
 
     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 (col=0; col < code->k; col++)
@@ -532,26 +529,14 @@ fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*
  * 
  * 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, with the added permission that, if you become obligated
- * to release a derived work under this licence (as per section 2.b), you may
- * delay the fulfillment of this obligation for up to 12 months.  See the file
- * COPYING for details.
- *
- * If you would like to inquire about a commercial relationship with Allmydata,
- * Inc., please contact partnerships@allmydata.com and visit
- * http://allmydata.com/.
+ * 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