On 10 May 2008 at 8:02, Ian Collins wrote:
> This assumes the limit is a multiple of N. Something like (untested)
>
> for (k=1; k<=(1<<j)-1; k += 2)
> {
> TABLE [i][((1<<j)+k)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k]);
> TABLE [i][((1<<j)+k+1)] = (TABLE[i][(1<<j)]) ^ (TABLE[i][k+1]);
> }

This fails when j=1.

The problem is that the number of iterations is variable, and ranges
between 1 and 127. Finding common divisors of (powers of 2 minus 1) as
an unrolling factor is problematic... (Since the number of iterations is
growing exponentially, even just unrolling the last loop is attractive,
but 127 is prime, so there'll be some fiddling needed.

Just unpacking what on earth the table looks like is an effort. The
outer index i is irrelevant, as there's no interaction between these
outer "layers". The inner 256-long arrays are arranged like this:

j
-1 | 0 |
0 | 1 |
1 | 2 | 3 |
2 | 4 | 5 | 6 | 7 |
3 | 8 | 9 |10 |11 |12 |13 |14 |15 |
4 ...
5 ...
6 ...
7 |128|129| ... |255|

The left-hand column is an input column. To fill in a given row, look at
the value in the left-hand column and xor it in turn with the elements
earlier in the array, in the order 0,1,2,3,...

Given the way these dependencies work, it is also possible to fill in
columns in turn from the left, rather than working row-wise. This
offers some potential for unrolling, but would still be complicated and
the resulting code would be large.