You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@nuttx.apache.org by Karel Kočí <cy...@email.cz> on 2022/07/15 12:09:44 UTC

CRC32 what gives?

Hi

I hit an issue with crc32 implementation in NuttX's LibC and it took me some 
time to figure out that crc32 is implemented differently in NuttX than I was 
expecting. Let me explain...

Common implementations are using same precomputed table as there is in the 
NuttX, but the initial value is all ones and not zero as in case of the NuttX 
(0xffffffff vs 0x0) and the result is negated while that is not true in the 
NuttX.
In other words the call `crc32(msg, msgsiz)` gives "unexpected" result while 
`~crc32part(msg, msgsiz, 0xffffffff)` gives the "correct" one.

I can see the idea behind not performing negation twice (`crc32part` would have 
to negate `crc32val` at the start and then return it negated again) but using 
the same precomputed table gives then different results.

I am not sure if this weakens the crc32 in some way or just has no side effect 
except of not matching with common implementations. Either way this discrepancy 
should be at least documented with suggestion to use `~crc32part(msg, msgsiz, 
0xffffffff)`. What do you think?

With regards
Karel Kočí

Re: CRC32 what gives?

Posted by Nimish Telang <ni...@telang.net.INVALID>.

https://github.com/madler/crcany is what I have been using to make one off CRC implementations. Consolidating the various ones into a single library might be useful.

From: Alan Carvalho de Assis <ac...@gmail.com>
Date: Friday, July 15, 2022 at 7:31 PM
To: dev@nuttx.apache.org <de...@nuttx.apache.org>
Subject: Re: CRC32 what gives?
We also have CRC4 used by MS5611 barometer sensor. It should be nice to
have all available in the kernel

On Friday, July 15, 2022, Nimish Telang <ni...@telang.net.invalid> wrote:

> Whichever one is chosen, there should be a table-free implementation for
> code size reasons. FWIW there are more crc implementations in the zmodem
> app: https://github.com/apache/incubator-nuttx-apps/blob/
> master/system/zmodem/host/crc16.c
>
>
>
> From: Sebastien Lorquet <se...@lorquet.fr>
> Date: Friday, July 15, 2022 at 4:13 PM
> To: dev@nuttx.apache.org <de...@nuttx.apache.org>
> Subject: Re: CRC32 what gives?
> @Nathan:
>
> Yes, of course.
>
> @Alan:
>
> Of course not, the structure passed to init can be set up to describe
> the required algorithm.
>
> But the partial update situation can be useful for protocols where the
> message is fragmented (eg radio transceivers with short FIFOs), or where
> only some fields enter the crc (I have seen this happen several times).
> you cant call the global crc() function on several buffers in sequence
> if bits are inverted on crc output.
>
> Sebastien
>
> On 7/15/22 20:21, Nathan Hartman wrote:
> > On Fri, Jul 15, 2022 at 1:40 PM Alan Carvalho de Assis
> > <ac...@gmail.com> wrote:
> >> Hi Sebastien, I think we don't need these three functions for each
> >> CRC, just one like in the Linux kernel is enough:
> >>
> >> https://www.kernel.org/doc/htmldocs/kernel-api/API-crc-ccitt.html
> >>
> >> BR,
> >>
> >> Alan
> >
> > Could have one generic function and then thin wrappers that call it
> > with the correct parameters for different uses.
> >
> > Cheers,
> > Nathan
>

Re: CRC32 what gives?

Posted by Alan Carvalho de Assis <ac...@gmail.com>.

We also have CRC4 used by MS5611 barometer sensor. It should be nice to
have all available in the kernel

On Friday, July 15, 2022, Nimish Telang <ni...@telang.net.invalid> wrote:

> Whichever one is chosen, there should be a table-free implementation for
> code size reasons. FWIW there are more crc implementations in the zmodem
> app: https://github.com/apache/incubator-nuttx-apps/blob/
> master/system/zmodem/host/crc16.c
>
>
>
> From: Sebastien Lorquet <se...@lorquet.fr>
> Date: Friday, July 15, 2022 at 4:13 PM
> To: dev@nuttx.apache.org <de...@nuttx.apache.org>
> Subject: Re: CRC32 what gives?
> @Nathan:
>
> Yes, of course.
>
> @Alan:
>
> Of course not, the structure passed to init can be set up to describe
> the required algorithm.
>
> But the partial update situation can be useful for protocols where the
> message is fragmented (eg radio transceivers with short FIFOs), or where
> only some fields enter the crc (I have seen this happen several times).
> you cant call the global crc() function on several buffers in sequence
> if bits are inverted on crc output.
>
> Sebastien
>
> On 7/15/22 20:21, Nathan Hartman wrote:
> > On Fri, Jul 15, 2022 at 1:40 PM Alan Carvalho de Assis
> > <ac...@gmail.com> wrote:
> >> Hi Sebastien, I think we don't need these three functions for each
> >> CRC, just one like in the Linux kernel is enough:
> >>
> >> https://www.kernel.org/doc/htmldocs/kernel-api/API-crc-ccitt.html
> >>
> >> BR,
> >>
> >> Alan
> >
> > Could have one generic function and then thin wrappers that call it
> > with the correct parameters for different uses.
> >
> > Cheers,
> > Nathan
>

Re: CRC32 what gives?

Posted by Nimish Telang <ni...@telang.net.INVALID>.

Whichever one is chosen, there should be a table-free implementation for code size reasons. FWIW there are more crc implementations in the zmodem app: https://github.com/apache/incubator-nuttx-apps/blob/master/system/zmodem/host/crc16.c

From: Sebastien Lorquet <se...@lorquet.fr>
Date: Friday, July 15, 2022 at 4:13 PM
To: dev@nuttx.apache.org <de...@nuttx.apache.org>
Subject: Re: CRC32 what gives?
@Nathan:

Yes, of course.

@Alan:

Of course not, the structure passed to init can be set up to describe
the required algorithm.

But the partial update situation can be useful for protocols where the
message is fragmented (eg radio transceivers with short FIFOs), or where
only some fields enter the crc (I have seen this happen several times).
you cant call the global crc() function on several buffers in sequence
if bits are inverted on crc output.

Sebastien

On 7/15/22 20:21, Nathan Hartman wrote:
> On Fri, Jul 15, 2022 at 1:40 PM Alan Carvalho de Assis
> <ac...@gmail.com> wrote:
>> Hi Sebastien, I think we don't need these three functions for each
>> CRC, just one like in the Linux kernel is enough:
>>
>> https://www.kernel.org/doc/htmldocs/kernel-api/API-crc-ccitt.html
>>
>> BR,
>>
>> Alan
>
> Could have one generic function and then thin wrappers that call it
> with the correct parameters for different uses.
>
> Cheers,
> Nathan

Re: CRC32 what gives?

Posted by Sebastien Lorquet <se...@lorquet.fr>.

@Nathan:

Yes, of course.

@Alan:

Of course not, the structure passed to init can be set up to describe 
the required algorithm.

But the partial update situation can be useful for protocols where the 
message is fragmented (eg radio transceivers with short FIFOs), or where 
only some fields enter the crc (I have seen this happen several times). 
you cant call the global crc() function on several buffers in sequence 
if bits are inverted on crc output.

Sebastien

On 7/15/22 20:21, Nathan Hartman wrote:
> On Fri, Jul 15, 2022 at 1:40 PM Alan Carvalho de Assis
> <ac...@gmail.com> wrote:
>> Hi Sebastien, I think we don't need these three functions for each
>> CRC, just one like in the Linux kernel is enough:
>>
>> https://www.kernel.org/doc/htmldocs/kernel-api/API-crc-ccitt.html
>>
>> BR,
>>
>> Alan
>
> Could have one generic function and then thin wrappers that call it
> with the correct parameters for different uses.
>
> Cheers,
> Nathan

Re: CRC32 what gives?

Posted by Nathan Hartman <ha...@gmail.com>.

On Fri, Jul 15, 2022 at 1:40 PM Alan Carvalho de Assis
<ac...@gmail.com> wrote:
>
> Hi Sebastien, I think we don't need these three functions for each
> CRC, just one like in the Linux kernel is enough:
>
> https://www.kernel.org/doc/htmldocs/kernel-api/API-crc-ccitt.html
>
> BR,
>
> Alan


Could have one generic function and then thin wrappers that call it
with the correct parameters for different uses.

Cheers,
Nathan

Re: CRC32 what gives?

Posted by Alan Carvalho de Assis <ac...@gmail.com>.

Hi Sebastien, I think we don't need these three functions for each
CRC, just one like in the Linux kernel is enough:

https://www.kernel.org/doc/htmldocs/kernel-api/API-crc-ccitt.html

BR,

Alan

On 7/15/22, Sebastien Lorquet <se...@lorquet.fr> wrote:
> Hi,
>
> Sorry to throw a rock in the pond but having a single function named
> "crc32" is very wrong and is not sufficient.
>
> As you have discussed the polynomial length is just not enough to
> describe a crc, the initial value, bit orders of input and output, and
> bit inversion on input and output are all used to derive actual crc
> functions.
>
> A proper API for an evolved project like nuttx should have a set of
> functions like crc_init, crc_update and crc_final, all acting on a crc
> context, just like sha and md5.
>
> This would also allow specific implementations to use the hardware crc
> resources provided by specific circuits.
>
> This would allow each use of the crc routines to define and use its own
> version of the crc, without interfering on other uses.
>
> For example I agree it would be very unwise to change the CRC kind used
> by file systems as it would break so many systems.
>
> Sebastien
>
> On 7/15/22 18:54, Karel Kočí wrote:
>> Excerpts from Nathan Hartman's message of July 15, 2022 6:47 pm:
>>> On Fri, Jul 15, 2022 at 12:45 PM Karel Kočí <cy...@email.cz> wrote:
>>>> The impact might be pretty significant from my search and that is also
>>>> why I
>>>> rather discuss instead of suggesting changes.
>>>>
>>>> The significant place where the current crc32 implementation is used is
>>>> in
>>>> file systems (such as smartfs or nxffs). The change would break any
>>>> existing
>>>> formating of those FSs. Thus I also do not think it should be done.
>>>
>>> Are these file systems readable by other operating systems besides
>>> NuttX?
>> Those are NuttX only up to my knowledge. The change would break old
>> formated
>> device on NuttX version update which sounds bad to me and "fix" (or rather
>> let's
>> say change to some other crc32 algorithm) won't fix compatibility with
>> some
>> other systems...
>