Crc32

Crc32

[valerij zaporogeci]

Hi, all.
Yet another dumb question from me.
UEFI specification has Crc32 calculation service and uses Crc32 in
several places. but it only humbly mentions in the note somewhere in
the description of System Table about what exact one it wants. Namely
it states that the polynomial seed is 04c11db7. And that's all.
My question is - does really the specification means the 33-bit polynomial
104c11db7? And is the algorithm just a plain remainder calculation
without any additional pre/post processing of it? So that for example
Crc32 of the 4-byte sequence b16b00b5 would be
8c1f0a7c?
Thank you.

Re: Crc32

[Michael Zimmermann]

well as u already said, the spec says it uses 'a standard  CCITT32 CRC
algorithm with a seed polynomial value of 0x04c11db7'

this is the implementation which confirms it:
https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c

after testing it it indeed produces CCITT32 results like this online
generator:
http://g6auc.me.uk/CRC32/index.html

Thanks
Michael

On Tue, Aug 30, 2016 at 2:54 AM, valerij zaporogeci <vlrzprgts@gmail.com>
wrote:

> Hi, all.
> Yet another dumb question from me.
> UEFI specification has Crc32 calculation service and uses Crc32 in
> several places. but it only humbly mentions in the note somewhere in
> the description of System Table about what exact one it wants. Namely
> it states that the polynomial seed is 04c11db7. And that's all.
> My question is - does really the specification means the 33-bit polynomial
> 104c11db7? And is the algorithm just a plain remainder calculation
> without any additional pre/post processing of it? So that for example
> Crc32 of the 4-byte sequence b16b00b5 would be
> 8c1f0a7c?
> Thank you.
> _______________________________________________
> edk2-devel mailing list
> edk2-devel@lists.01.org
> https://lists.01.org/mailman/listinfo/edk2-devel
>

Re: Crc32

[valerij zaporogeci]

Thank you.
But the polynomial value for CCITT crc32 is 104c11db7, not its tail 04c11db7.
And this whole mess with all those online calculators was the exact
reson I asked here. Because they mostly give WRONG result. As your
example. It's easy to check it's wrong. Because for example leading
zeroes in the message MUST not change the Crc32.
Here we have:
for 01 -> CD39D477
for 00 01 -> D71E16AC
and so on.
Also,  it's obvious that Crc32(1) would be a polynomial without the
most significant non-zero bit, thus crc32 from 1 by the polynomial
104c11db7 would be 04c11b7.
The only online calculator so far giving right results is here:
https://ghsi.de/CRC/index.php?Polynom=100000100110000010001110110110111&Message=0104c11db7

I wrote function following the mathematics of the Crc and it gives
results exactly like in the above calculator.
It's fun to imagine what happens with such an incompatibilty for
example in case of GPT header.

2016-08-30 14:08 GMT+03:00, Michael Zimmermann <sigmaepsilon92@gmail.com>:
> well as u already said, the spec says it uses 'a standard  CCITT32 CRC
> algorithm with a seed polynomial value of 0x04c11db7'
>
> this is the implementation which confirms it:
> https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c
>
> after testing it it indeed produces CCITT32 results like this online
> generator:
> http://g6auc.me.uk/CRC32/index.html
>
> Thanks
> Michael
>
> On Tue, Aug 30, 2016 at 2:54 AM, valerij zaporogeci <vlrzprgts@gmail.com>
> wrote:
>
>> Hi, all.
>> Yet another dumb question from me.
>> UEFI specification has Crc32 calculation service and uses Crc32 in
>> several places. but it only humbly mentions in the note somewhere in
>> the description of System Table about what exact one it wants. Namely
>> it states that the polynomial seed is 04c11db7. And that's all.
>> My question is - does really the specification means the 33-bit
>> polynomial
>> 104c11db7? And is the algorithm just a plain remainder calculation
>> without any additional pre/post processing of it? So that for example
>> Crc32 of the 4-byte sequence b16b00b5 would be
>> 8c1f0a7c?
>> Thank you.
>> _______________________________________________
>> edk2-devel mailing list
>> edk2-devel@lists.01.org
>> https://lists.01.org/mailman/listinfo/edk2-devel
>>
>

Re: Crc32

[Andrew Fish]

> On Aug 30, 2016, at 6:32 AM, valerij zaporogeci <vlrzprgts@gmail.com> wrote:
> 
> Thank you.
> But the polynomial value for CCITT crc32 is 104c11db7, not its tail 04c11db7.

The spec does not say it is a CCITT, it states it uses the CCITT algorithm with a seed polynomial of 0x04c11db7.


> And this whole mess with all those online calculators was the exact
> reson I asked here. Because they mostly give WRONG result. As your
> example. It's easy to check it's wrong. Because for example leading
> zeroes in the message MUST not change the Crc32.
> Here we have:
> for 01 -> CD39D477
> for 00 01 -> D71E16AC
> and so on.
> Also,  it's obvious that Crc32(1) would be a polynomial without the
> most significant non-zero bit, thus crc32 from 1 by the polynomial
> 104c11db7 would be 04c11b7.
> The only online calculator so far giving right results is here:
> https://ghsi.de/CRC/index.php?Polynom=100000100110000010001110110110111&Message=0104c11db7
> 
> I wrote function following the mathematics of the Crc and it gives
> results exactly like in the above calculator.
> It's fun to imagine what happens with such an incompatibilty for
> example in case of GPT header.
> 

As far as I can tell this is used in a lot of real world things: HDLC, ANSI X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG,[36] many others[1]

I think Ken added this to the spec in the last millennium. Ken's background was networking and Windows X86 HAL so I'm assuming he picked the same CRC as Ethernet?

It is always possible we could have botched the math some place along the way and not noticed as we are self consistent so everything appears to work.

Thanks,

Andrew Fish

[1] https://en.wikipedia.org/wiki/Cyclic_redundancy_check


> 2016-08-30 14:08 GMT+03:00, Michael Zimmermann <sigmaepsilon92@gmail.com>:
>> well as u already said, the spec says it uses 'a standard  CCITT32 CRC
>> algorithm with a seed polynomial value of 0x04c11db7'
>> 
>> this is the implementation which confirms it:
>> https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c
>> 
>> after testing it it indeed produces CCITT32 results like this online
>> generator:
>> http://g6auc.me.uk/CRC32/index.html
>> 
>> Thanks
>> Michael
>> 
>> On Tue, Aug 30, 2016 at 2:54 AM, valerij zaporogeci <vlrzprgts@gmail.com>
>> wrote:
>> 
>>> Hi, all.
>>> Yet another dumb question from me.
>>> UEFI specification has Crc32 calculation service and uses Crc32 in
>>> several places. but it only humbly mentions in the note somewhere in
>>> the description of System Table about what exact one it wants. Namely
>>> it states that the polynomial seed is 04c11db7. And that's all.
>>> My question is - does really the specification means the 33-bit
>>> polynomial
>>> 104c11db7? And is the algorithm just a plain remainder calculation
>>> without any additional pre/post processing of it? So that for example
>>> Crc32 of the 4-byte sequence b16b00b5 would be
>>> 8c1f0a7c?
>>> Thank you.
>>> _______________________________________________
>>> edk2-devel mailing list
>>> edk2-devel@lists.01.org
>>> https://lists.01.org/mailman/listinfo/edk2-devel
>>> 
>> 
> _______________________________________________
> edk2-devel mailing list
> edk2-devel@lists.01.org
> https://lists.01.org/mailman/listinfo/edk2-devel

Re: Crc32

[valerij zaporogeci]

well, that bit in the 32th (bit 33) term of the polynomial is
"implied", but it should be used, otherwise it would not give a 32 bit
remainder (crc). if to count 04c11db7 as a polynomial, its non-zero
msbit is bit 26, so with it, it would be crc25.
Why results don't match, I suspect it's becuase that pre- and post-
processing involved. Tianocore algorithm inverses bits at the
beginning and in the end.
Pure definition of CRC doesn't require this. It would be good to know
the exact specification on the algorithm and its nuances.
And of course in the pure case, calculating CRC on the polynomial
itself should give 0 (since polynomial itself is multiple of itself).
It's the easiest way to check. So CRC of 104c11db7 = 0
In the the above calculator (in the Michael's response), neither
CRC(104c11db7) nor CRC(04c11db7) gives 0. (4E24FFBE and B79B7E7A
respectively).
So if it is a right CRC32, then it's not a pure CRC mathematically.
and additionally processed. How? and where it is possible to learn
that?


2016-08-30 17:09 GMT+03:00, Andrew Fish <afish@apple.com>:
>
>> On Aug 30, 2016, at 6:32 AM, valerij zaporogeci <vlrzprgts@gmail.com>
>> wrote:
>>
>> Thank you.
>> But the polynomial value for CCITT crc32 is 104c11db7, not its tail
>> 04c11db7.
>
> The spec does not say it is a CCITT, it states it uses the CCITT algorithm
> with a seed polynomial of 0x04c11db7.
>
>
>> And this whole mess with all those online calculators was the exact
>> reson I asked here. Because they mostly give WRONG result. As your
>> example. It's easy to check it's wrong. Because for example leading
>> zeroes in the message MUST not change the Crc32.
>> Here we have:
>> for 01 -> CD39D477
>> for 00 01 -> D71E16AC
>> and so on.
>> Also,  it's obvious that Crc32(1) would be a polynomial without the
>> most significant non-zero bit, thus crc32 from 1 by the polynomial
>> 104c11db7 would be 04c11b7.
>> The only online calculator so far giving right results is here:
>> https://ghsi.de/CRC/index.php?Polynom=100000100110000010001110110110111&Message=0104c11db7
>>
>> I wrote function following the mathematics of the Crc and it gives
>> results exactly like in the above calculator.
>> It's fun to imagine what happens with such an incompatibilty for
>> example in case of GPT header.
>>
>
> As far as I can tell this is used in a lot of real world things: HDLC, ANSI
> X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2,
> PNG,[36] many others[1]
>
> I think Ken added this to the spec in the last millennium. Ken's background
> was networking and Windows X86 HAL so I'm assuming he picked the same CRC as
> Ethernet?
>
> It is always possible we could have botched the math some place along the
> way and not noticed as we are self consistent so everything appears to
> work.
>
> Thanks,
>
> Andrew Fish
>
> [1] https://en.wikipedia.org/wiki/Cyclic_redundancy_check
>
>
>> 2016-08-30 14:08 GMT+03:00, Michael Zimmermann
>> <sigmaepsilon92@gmail.com>:
>>> well as u already said, the spec says it uses 'a standard  CCITT32 CRC
>>> algorithm with a seed polynomial value of 0x04c11db7'
>>>
>>> this is the implementation which confirms it:
>>> https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c
>>>
>>> after testing it it indeed produces CCITT32 results like this online
>>> generator:
>>> http://g6auc.me.uk/CRC32/index.html
>>>
>>> Thanks
>>> Michael
>>>
>>> On Tue, Aug 30, 2016 at 2:54 AM, valerij zaporogeci
>>> <vlrzprgts@gmail.com>
>>> wrote:
>>>
>>>> Hi, all.
>>>> Yet another dumb question from me.
>>>> UEFI specification has Crc32 calculation service and uses Crc32 in
>>>> several places. but it only humbly mentions in the note somewhere in
>>>> the description of System Table about what exact one it wants. Namely
>>>> it states that the polynomial seed is 04c11db7. And that's all.
>>>> My question is - does really the specification means the 33-bit
>>>> polynomial
>>>> 104c11db7? And is the algorithm just a plain remainder calculation
>>>> without any additional pre/post processing of it? So that for example
>>>> Crc32 of the 4-byte sequence b16b00b5 would be
>>>> 8c1f0a7c?
>>>> Thank you.
>>>> _______________________________________________
>>>> edk2-devel mailing list
>>>> edk2-devel@lists.01.org
>>>> https://lists.01.org/mailman/listinfo/edk2-devel
>>>>
>>>
>> _______________________________________________
>> edk2-devel mailing list
>> edk2-devel@lists.01.org
>> https://lists.01.org/mailman/listinfo/edk2-devel
>
>

Re: Crc32

[Andrew Fish]

> On Aug 30, 2016, at 8:17 AM, valerij zaporogeci <vlrzprgts@gmail.com> wrote:
> 
> well, that bit in the 32th (bit 33) term of the polynomial is
> "implied", but it should be used, otherwise it would not give a 32 bit
> remainder (crc). if to count 04c11db7 as a polynomial, its non-zero
> msbit is bit 26, so with it, it would be crc25.
> Why results don't match, I suspect it's becuase that pre- and post-
> processing involved. Tianocore algorithm inverses bits at the
> beginning and in the end.
> Pure definition of CRC doesn't require this. It would be good to know
> the exact specification on the algorithm and its nuances.
> And of course in the pure case, calculating CRC on the polynomial
> itself should give 0 (since polynomial itself is multiple of itself).
> It's the easiest way to check. So CRC of 104c11db7 = 0
> In the the above calculator (in the Michael's response), neither
> CRC(104c11db7) nor CRC(04c11db7) gives 0. (4E24FFBE and B79B7E7A
> respectively).
> So if it is a right CRC32, then it's not a pure CRC mathematically.
> and additionally processed. How? and where it is possible to learn
> that?
> 

I don't know the math here as well as you do so I will not comment on that.  My guess is this is an old algorithm that was optimized for 32-bit hardware. 64-bit math would require a lot software math libraries and it would be much slower than doing 32-bit math on a processors ALU. 

If you want to research the history of this algorithm your best bet it to research the CRC32 used in old school Ethernet. The CRC got added to the (U)EFI spec about 17 years ago and it was probably copying something that was 25-30 years old, but that is just my best guess as Ken called in rich a long time ago and does not work on things EFI at this point. 

Thanks,

Andrew Fish

> 
> 2016-08-30 17:09 GMT+03:00, Andrew Fish <afish@apple.com>:
>> 
>>> On Aug 30, 2016, at 6:32 AM, valerij zaporogeci <vlrzprgts@gmail.com>
>>> wrote:
>>> 
>>> Thank you.
>>> But the polynomial value for CCITT crc32 is 104c11db7, not its tail
>>> 04c11db7.
>> 
>> The spec does not say it is a CCITT, it states it uses the CCITT algorithm
>> with a seed polynomial of 0x04c11db7.
>> 
>> 
>>> And this whole mess with all those online calculators was the exact
>>> reson I asked here. Because they mostly give WRONG result. As your
>>> example. It's easy to check it's wrong. Because for example leading
>>> zeroes in the message MUST not change the Crc32.
>>> Here we have:
>>> for 01 -> CD39D477
>>> for 00 01 -> D71E16AC
>>> and so on.
>>> Also,  it's obvious that Crc32(1) would be a polynomial without the
>>> most significant non-zero bit, thus crc32 from 1 by the polynomial
>>> 104c11db7 would be 04c11b7.
>>> The only online calculator so far giving right results is here:
>>> https://ghsi.de/CRC/index.php?Polynom=100000100110000010001110110110111&Message=0104c11db7
>>> 
>>> I wrote function following the mathematics of the Crc and it gives
>>> results exactly like in the above calculator.
>>> It's fun to imagine what happens with such an incompatibilty for
>>> example in case of GPT header.
>>> 
>> 
>> As far as I can tell this is used in a lot of real world things: HDLC, ANSI
>> X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2,
>> PNG,[36] many others[1]
>> 
>> I think Ken added this to the spec in the last millennium. Ken's background
>> was networking and Windows X86 HAL so I'm assuming he picked the same CRC as
>> Ethernet?
>> 
>> It is always possible we could have botched the math some place along the
>> way and not noticed as we are self consistent so everything appears to
>> work.
>> 
>> Thanks,
>> 
>> Andrew Fish
>> 
>> [1] https://en.wikipedia.org/wiki/Cyclic_redundancy_check
>> 
>> 
>>> 2016-08-30 14:08 GMT+03:00, Michael Zimmermann
>>> <sigmaepsilon92@gmail.com>:
>>>> well as u already said, the spec says it uses 'a standard  CCITT32 CRC
>>>> algorithm with a seed polynomial value of 0x04c11db7'
>>>> 
>>>> this is the implementation which confirms it:
>>>> https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c
>>>> 
>>>> after testing it it indeed produces CCITT32 results like this online
>>>> generator:
>>>> http://g6auc.me.uk/CRC32/index.html
>>>> 
>>>> Thanks
>>>> Michael
>>>> 
>>>> On Tue, Aug 30, 2016 at 2:54 AM, valerij zaporogeci
>>>> <vlrzprgts@gmail.com>
>>>> wrote:
>>>> 
>>>>> Hi, all.
>>>>> Yet another dumb question from me.
>>>>> UEFI specification has Crc32 calculation service and uses Crc32 in
>>>>> several places. but it only humbly mentions in the note somewhere in
>>>>> the description of System Table about what exact one it wants. Namely
>>>>> it states that the polynomial seed is 04c11db7. And that's all.
>>>>> My question is - does really the specification means the 33-bit
>>>>> polynomial
>>>>> 104c11db7? And is the algorithm just a plain remainder calculation
>>>>> without any additional pre/post processing of it? So that for example
>>>>> Crc32 of the 4-byte sequence b16b00b5 would be
>>>>> 8c1f0a7c?
>>>>> Thank you.
>>>>> _______________________________________________
>>>>> edk2-devel mailing list
>>>>> edk2-devel@lists.01.org
>>>>> https://lists.01.org/mailman/listinfo/edk2-devel
>>>>> 
>>>> 
>>> _______________________________________________
>>> edk2-devel mailing list
>>> edk2-devel@lists.01.org
>>> https://lists.01.org/mailman/listinfo/edk2-devel
>> 
>> 
> _______________________________________________
> edk2-devel mailing list
> edk2-devel@lists.01.org
> https://lists.01.org/mailman/listinfo/edk2-devel

Re: Crc32

[valerij zaporogeci]

>> after testing it it indeed produces CCITT32 results like this online generator:
>> http://g6auc.me.uk/CRC32/index.html

I only now noticed that this  "calculator", gives DIFFERENT values on
the same input, no matter hex or text based.
Interestingly, how it could produce the same results as the Tianocore
implementation?

I was thinking that all the difference in the Tianocore impl. from the
pure crc is appending 32 1's at the beginning of the (input) message
and then negating the Crc itself in the end.

I see, the only way to check is to pull off the Tianocore function and check.)

Re: Crc32

[Michael Zimmermann]

it doesn't. it just seems that if the crc text field is not empty it
calculates the crc of the crc, so you have to hit the "Reset CRC" button
before reprocessing the text.

On Wed, Aug 31, 2016 at 3:11 AM, valerij zaporogeci <vlrzprgts@gmail.com>
wrote:

> >> after testing it it indeed produces CCITT32 results like this online
> generator:
> >> http://g6auc.me.uk/CRC32/index.html
>
> I only now noticed that this  "calculator", gives DIFFERENT values on
> the same input, no matter hex or text based.
> Interestingly, how it could produce the same results as the Tianocore
> implementation?
>
> I was thinking that all the difference in the Tianocore impl. from the
> pure crc is appending 32 1's at the beginning of the (input) message
> and then negating the Crc itself in the end.
>
> I see, the only way to check is to pull off the Tianocore function and
> check.)
> _______________________________________________
> edk2-devel mailing list
> edk2-devel@lists.01.org
> https://lists.01.org/mailman/listinfo/edk2-devel
>

Re: Crc32

[valerij zaporogeci]

yes. it does as you said. very confusing in fact.

2016-08-31 6:54 GMT+03:00, Michael Zimmermann <sigmaepsilon92@gmail.com>:
> it doesn't. it just seems that if the crc text field is not empty it
> calculates the crc of the crc, so you have to hit the "Reset CRC" button
> before reprocessing the text.
>
> On Wed, Aug 31, 2016 at 3:11 AM, valerij zaporogeci <vlrzprgts@gmail.com>
> wrote:
>
>> >> after testing it it indeed produces CCITT32 results like this online
>> generator:
>> >> http://g6auc.me.uk/CRC32/index.html
>>
>> I only now noticed that this  "calculator", gives DIFFERENT values on
>> the same input, no matter hex or text based.
>> Interestingly, how it could produce the same results as the Tianocore
>> implementation?
>>
>> I was thinking that all the difference in the Tianocore impl. from the
>> pure crc is appending 32 1's at the beginning of the (input) message
>> and then negating the Crc itself in the end.
>>
>> I see, the only way to check is to pull off the Tianocore function and
>> check.)
>> _______________________________________________
>> edk2-devel mailing list
>> edk2-devel@lists.01.org
>> https://lists.01.org/mailman/listinfo/edk2-devel
>>
>

Re: Crc32

[valerij zaporogeci]

>> I was thinking that all the difference in the Tianocore impl. from the
>> pure crc is appending 32 1's at the beginning of the (input) message
>> and then negating the Crc itself in the end.

Thank you, Michael and Andrew for your help. I figured out what causes
the difference.
Apart from initializing crc with ffffffff at the beginning and
negating the resulting crc at the end, the difference is that
Tianocore impl. reverses bits in the byte sequence (of the input),
thus bit 7 of every byte becomes bit 0 and bit 0 - bit 7. And also in
the end, resulting Crc is also reverted bitwise (bit 31->0, 0->31).
Not that I understood everything, but applying these inversions into
the pure remainder calculation, gives matching with the Tianocore
function results.

Re: Crc32

[valerij zaporogeci]

Please read this, don't discard hastily, it might be intesting for the project.
I have a suggestion about the implementation of Crc32 found in this place:
https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Core/RuntimeDxe/Crc32.c

Figuring out why proper mathematical crc calculation differs from
results returned by this function, I found it's because the function
reverts bits in bytes. It's all clear, this is a need rooting from
some hardware protocol requirements and specifics (ethernet?), where
it was needed and here it is repeated as it became a de facto
standard.
But looking at the implementation, I found that it is possible to get
THE SAME results with much less processing. Namely, instead of
reverting every byte in the sequnece (moreover, please note, that the
implementation in fact casts every byte to UINT32 and only then
reverts it - yet 4 times more of a wasting job), so, instead of
reverting every byte of the entire message (which might be of any
size), we might statically revert bits ONLY in the Polynomial
representation itself. And that's all! It's absolutely identical
mathematically. It returns identical results on every input. But it is
a significant performance improvement. The interface and semantics
would not change, they remain the same for any caller. Internal
ReverseBits() function is not needed any more and doesn't get called
anywhere. The implementation remains the same table driven, but the
table initializes now MUCH more faster (without reverting).
If you have interest in this suggestion, I have prepared (and tested)
the changed file in question, and might send it if there would be
interest.
Thank you.
PS. It is NOT changing a polynomial. It's improvement of the internal
implementation which takes into account (strange) treatment of bit
ordering of this particular case.