## CRC - Next Steps

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

### Multiple Word Sizes

From: andrew cooke <andrew@...>

Date: Fri, 11 Apr 2014 09:33:01 -0300

No, not quite.

The multiple table "trick" is effectively support for large words (in that
case 32bits).

So what we want is:

1 - The usual no table routine (to cross-check and for short data)

2 - Support for 8bit index tables (only), with multiple data sizes
(multiples of 8bits).

3 - Something that builds on the above to handle 8bit bytes in larger
sized chunks (perhaps calling the standard routine at the end to
clean up the last few bytes).

Andrew