faster initialization

[zooko]

Jack Lloyd contributed this patch:

Mon May  4 17:32:23 MDT 2009  Jack Lloyd
  * initialize fec_new() faster
  Basically the idea is invert_vdm only looks at a few values - the ones
  it copies into p[] from src[] (specifically the 2nd column). In turn
  src[] was created in fec_new from values from gf_exp. src[i] (besides
  first row special case) is equal to gf_exp[((i % k) * (i / k) % 255].
  Since the inversion only uses the second column (thus we only
  care about the case i = x*(k+1)), the gf_exp lookup simplifies to
  gfp_exp[i%255] (though an offset is required in the code to handle the
  first row).
  
  So p[] is not required (removing one malloc/free pair), and since src
  is now longer examined in invert_vdm, it does not need to be
  initialized. So only the final (n-k) rows of the matrix need to be
  written to in fec_new - _invert_vdm will write the first k rows
  without caring what (if anything) is in src when it is provided
  (making src a poor name, perhaps).
  
  All in all this is not huge stuff - one malloc/free of <=255 bytes,
  and perhaps a few thousands cycles in the loops creating and writing
  values that were just overwritten later on without being read, and
  only during code init. The difference is probably not really
  detectable outside of a tight loop of fec_free(fec_new()).
  
diff -rN -u old-zfec-pristine/zfec/zfec/fec.c new-zfec-pristine/zfec/zfec/fec.c
--- old-zfec-pristine/zfec/zfec/fec.c	2009-05-04 17:34:10.000000000 -0600
+++ new-zfec-pristine/zfec/zfec/fec.c	2009-05-04 17:34:10.000000000 -0600
@@ -336,11 +336,15 @@
 void
 _invert_vdm (gf* src, unsigned k) {
     unsigned i, j, row, col;
-    gf *b, *c, *p;
+    gf *b, *c;
     gf t, xx;
 
     if (k == 1)                   /* degenerate case, matrix must be p^0 = 1 */
-        return;
+       {
+       src[0] = 1;
+       return;
+       }
+
     /*
      * c holds the coefficient of P(x) = Prod (x - p_i), i=0..k-1
      * b holds the coefficient for the matrix inversion
@@ -348,21 +352,19 @@
     c = NEW_GF_MATRIX (1, k);
     b = NEW_GF_MATRIX (1, k);
 
-    p = NEW_GF_MATRIX (1, k);
-
     for (j = 1, i = 0; i < k; i++, j += k) {
         c[i] = 0;
-        p[i] = src[j];            /* p[i] */
     }
+
     /*
      * construct coeffs. recursively. We know c[k] = 1 (implicit)
      * and start P_0 = x - p_0, then at each stage multiply by
      * x - p_i generating P_i = x P_{i-1} - p_i P_{i-1}
      * After k steps we are done.
      */
-    c[k - 1] = p[0];              /* really -p(0), but x = -x in GF(2^m) */
+    c[k - 1] = 0;              /* really -p(0), but x = -x in GF(2^m) */
     for (i = 1; i < k; i++) {
-        gf p_i = p[i];            /* see above comment */
+        gf p_i = gf_exp[(i-1) % 255];            /* see above comment */
         for (j = k - 1 - (i - 1); j < k - 1; j++)
             c[j] ^= gf_mul (p_i, c[j + 1]);
         c[k - 1] ^= p_i;
@@ -372,7 +374,7 @@
         /*
          * synthetic division etc.
          */
-        xx = p[row];
+        xx = (row == 0) ? 0 : gf_exp[row-1];
         t = 1;
         b[k - 1] = 1;             /* this is in fact c[k] */
         for (i = k - 1; i > 0; i--) {
@@ -384,7 +386,6 @@
     }
     free (c);
     free (b);
-    free (p);
     return;
 }
 
@@ -431,10 +432,8 @@
      * fill the matrix with powers of field elements, starting from 0.
      * The first row is special, cannot be computed with exp. table.
      */
-    tmp_m[0] = 1;
-    for (col = 1; col < k; col++)
-        tmp_m[col] = 0;
-    for (p = tmp_m + k, row = 0; row < n - 1; row++, p += k)
+
+    for (p = tmp_m + k*k, row = k-1; row < n - 1; row++, p += k)
         for (col = 0; col < k; col++)
             p[col] = gf_exp[modnn (row * col)];
 

[davidsarah]

The comment "/* really -p(0), but x = -x in GF(2^{m) */" is stale. If -p_0 = 0, it should say that. Also, some comment above that should define what p_i is, since it is now not explicit in the code.}