C[omp]ute

From: andrew cooke <andrew@...>

Date: Fri, 11 Apr 2014 04:14:00 -0300

I recently wrote a CRC library in Julia -
https://github.com/andrewcooke/CRC.jl - which works fine, but is ~2.5x slower
than an optimized C implementation (for CRC32, using zlib).

Looking at the zlib code, they use four lookup tables so that they can process
32 bits at a time.  In case it's not obvious how that works - each table has a
different number of "echoes".  So the final byte (of 4) is processed with a
normal table, but the first byte is taken from a table that "echoes" the
result through three zero bytes, and so gives a contriibution that can be
combined (xored) directly with the result from the final byte.

Now it's not clear to me that this saves much time at all (never mind a factor
of 2.5).  But the only way to be sure is to include it in the code.

Unfortunately, the current code is already quite ungainly.  So what to do?

Much of the complexity of the current code comes from supporting lookup tables
that have an index of a different size from the input data.  This is pretty
esoteric - who really wants to calculate a hash over 64bit words?  If that was
removed then the code would support indices that matched data chunk size.  And
since reasonable indices are 8 or 16bits, we could simply restrict things to
bytes.

So the plan is, at some point, to restrict the API to bytes only and then
support multi[ple tables.

Andrew