Re: Adding slice-by-4 and slice-by-8 to CRC32

[Sam Russell]

IANAL but it appears the source (paper, not code) for both implementations in coreutils is free, I'm happy to write from scratch based off the papers:

Slice-by-8: "Novel Table Lookup-Based Algorithms for High-Performance CRC Generation"

PCLMUL: "Fast CRC Computation for Numeric Polynomials Using PCLMULQDQ Instruction"

I'm happy to leave the licensing decision to other people.

The current coreutils implemention would need modifying as it has the polynomial constants hardcoded, and I'm not sure what impact endianness has on a bit-reversed polynomial. If we want gnulib to have a generic implementation with CRC32 and CRC32-C with both normal and bit-reversed polynomials with big/little endian support then we'd need a proper test suite. What would you like the gnulib implementation to offer? My primary goal is to improve the speed for gzip, so I would want to simply add the new algorithms with hard-coded gzip parameters and get that shipped, and then as a next step we could make gnulib the generic performant reference CRC32 implementation shipping with standard polynomials but also having the option to work with any given polynomial.

What are your thoughts? What would you want to see the gnulib implementation look like?

On Tue, 15 Oct 2024 at 09:07, Simon Josefsson <simon@josefsson.org> wrote:

The coreutils code is GPL and the crc module in gnulib is LGPL.  I'm
using the gnulib crc module in some LGPL projects.  Is it wortwhile to
keep the optimization GPL?  I would prefer a LGPL crc module that is
performant, with #ifdef-varianted support for 1) no tables at all, 2)
small table like today, and 3) your bigger tables, together with support
for the SSE instruction.  If that makes sense and would work.  Thoughts?
Otherwise another approach is to keep a simple LGPL crc module and
performant crc-gpl module that uses the coreutils code.

/Simon

Sam Russell <sam.h.russell@gmail.com> writes:

> That sounds good. It looks like there some subtle differences anyway, the
> gzip version does everything bit reversed, and while the intel paper has
> constants for that there are some logic things that would have to change
> (take hiword then loword instead of loword then hiword etc)
>
> On Mon, Oct 14, 2024, 19:05 Pádraig Brady <P@draigbrady.com> wrote:
>
>> On 14/10/2024 15:53, Sam Russell wrote:
>> >  > For reference, coreutils' cksum uses slice by 8 unconditionally since:
>> >  > https://github.com/coreutils/coreutils/commit/a7533917e <
>> https://github.com/coreutils/coreutils/commit/a7533917e>
>> >
>> > perfect, we could just copy this across then? is there a reason gnulib
>> wouldn't just include coreutils as a dependency?
>>
>> It might be best to copy/adjust the coreutils code across to gnulib,
>> then coreutils could be adjusted to use the gnulib routines.
>> The crc code is under the same licence in gnulib and coreutils, so there
>> should be no issue.
>>
>> cheers,
>> Pádraig
>>
>>