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

[Sam Russell]

Sounds good, I've just sent a patch with a test to cover alignment issues we might run into in the optimised implementation, and I emailed assign@fsf.org and asked to kick off the copyright assignment process. Anything else I should be starting now to make things run more smoothly?

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

I suggest to focus on the immediate use-case and see if we can complete
that, to not get overwhelmed with the variety of ideas.  Just getting
your bigger table speedup into a LGPL'd crc.c in gnulib, and to get gzip
to use that module, seems like a good improvement.  You should start on
the copyright assignment paper process first.

/Simon

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

> 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
>> >>
>> >>
>>