Re: CRC32C Parallel Computation Optimization on ARM

I wrote:
>
> 1. I looked at a couple implementations of this idea, and found that
> the constants used in the carryless multiply are tied to the length of
> the blocks. With a lookup table we can do the 3-way algorithm on any
> portion of a full block length, rather than immediately fall to doing
> CRC serially. That would be faster on average. See for example
> https://github.com/komrad36/CRC/tree/master , but I don't think we
> actually have to fully unroll the loop like they do there.
>
> 2. With the above, we can use a larger full block size, and so on
> average less time would be spent in the carryless multiply. With that,
> we could possibly get away with an open coded loop in normal C rather
> than a new intrinsic (also found in the above repo). That would be
> more portable.

I added a port to x86 and poked at it, with the intent to have an easy
on-ramp to that at least accelerates computation of CRCs on FPIs.

The 0008 patch only worked on chunks of 1024 at a time. At that size,
the presence of hardware carryless multiplication is not that
important. I removed the hard-coded constants in favor of a lookup
table, so now it can handle anything up to 8400 bytes in a single
pass.

There are still some "taste" issues, but I like the overall shape here
and how light it was. With more hardware support, we can go much lower
than 1024 bytes, but that can be left for future work.
--
John Naylor
Amazon Web Services