Reflection of xor-in wrong for 32-bit CRC?

[schlatterbeck]

The "normal" crc32 (in python available in zlib or binascii) can do continuation of a crc, i.e. (python3):

>>> from zlib import crc32
>>> crc32(b'12345678')
2598427311
>>> crc32(b'12345678', 2598427311)
1808553911
>>> crc32(b'1234567812345678')
1808553911

pycrc doesn't seem to get this right (I've installed the pycrc.py as pycrc in my path, the prompt is designed to allow cutting/pasting the whole line):

: %; pycrc --version
pycrc v0.9.2

: %; pycrc --width=32 --poly=0x04c11db7 --xor-in=0 --xor-out=0 \
        --reflect-in=1 --reflect-out=1 --check-hexstring 12345678
0x6b4dd184
: %; pycrc --width=32 --poly=0x04c11db7 --xor-in=0x6b4dd184 --xor-out=0 \
        --reflect-in=1 --reflect-out=1 --check-hexstring 12345678
0x3ab64c61
: %; pycrc --width=32 --poly=0x04c11db7 --xor-in=0 --xor-out=0
        --reflect-in=1 --reflect-out=1 --check-hexstring 1234567812345678
0x1a8a2677

If I reverse the output value 0x6b4dd184 before using it in the second call above it works:

: %; ./rev 0x6b4dd184
0x218bb2d6
: %; pycrc --width=32 --poly=0x04c11db7 --xor-in=0x218bb2d6 --xor-out=0 \
        --reflect-in=1 --reflect-out=1 --check-hexstring 12345678
0x1a8a2677

So it looks like pycrc should reflect the xor-in value before xoring it into the register for reflected algos.
Note that I'm not sure why pycrc gets it wrong for 32 bit but seems to get it right for crc16, there is the 16-bit model 'crc-16-ccitt' which has an asymmetric xor-in value of 0x1d0f. This produces a check-value consistent with other crc implementation of the same algo (e.g. reveng which names it CRC-16/SPI-FUJITSU). And continuation works, too (the algo has a zero xor-out, so we don't need to compensate):

: %; pycrc --width=16 --poly=0x1021 --xor-in=0x1d0f --xor-out=0 \
           --reflect-in=0 --reflect-out=0 --check-string=1234567812345678
0x5b57
: %; pycrc --width=16 --poly=0x1021 --xor-in=0x1d0f --xor-out=0 \
           --reflect-in=0 --reflect-out=0 --check-string=12345678
0x712c
: %; pycrc --width=16 --poly=0x1021 --xor-in=0x712c --xor-out=0 \
           --reflect-in=0 --reflect-out=0 --check-string=12345678
0x5b57

Any ideas?

[schlatterbeck]

Probably related to this: The behaviour seems to be different for check-hexstring and check-file. In the following example the file rand1 is a file generated from reading some bytes from /dev/urandom. The r1.d file is the corresponding hex-dump (with all whitespace removed, a single hex string). When specifying an asymmetric xor-in value we get different results:

: %; pycrc --width=32 --poly=0x04c11db7 --xor-in=0x12345678 --xor-out=0xffffffff \
    --reflect-in=1 --reflect-out=1 --check-file ../novo/rand1
0x25371555
: %; pycrc --width=32 --poly=0x04c11db7 --xor-in=0x12345678 --xor-out=0xffffffff \
    --reflect-in=1 --reflect-out=1 --check-hexstring $(cat ../novo/r1.d)
0x6a9d7bdb

[schlatterbeck]

I wrote earlier that it doesn't happen with 16-bit algos. This is not true, here is an example:

: %; pycrc --poly=0x8005 --xor-in=0x4711 --xor-out=0xFFFF --reflect-in=1 --reflect-out=1 --width=16 --check-file 1234567  
0x1499
: %; pycrc --poly=0x8005 --xor-in=0x4711 --xor-out=0xFFFF --reflect-in=1 --reflect-out=1 --width=16 --check-string 1234567
0xe44b

The file 1234567 contains the content (produced with echo -n 1234567 > 1234567)

The difference to the earlier 16-bit example seems to have been the reflect-in=1 vs. 0.

[schlatterbeck]

For fix see pull-request #33

[tpircher-zz]

[Edit the message as I wrote some complete nonsense before...]

With the parameters of the crc-32 model, the CRC calculation goes like this:

1. Set the register with the initial value
2. Reflect the register
3. run the CRC update function
4. update the register by running Width zeroes through it
5. reflect the register
6. apply the XOR out value

The CRC update function can be chained, but the first two steps and the last three steps must be run only once. I haven't looked at the Python crc32 implementation, but I guess they must do some compensation to counteract the finalisation step from the previous loop.

Does this make sense?

[schlatterbeck]

First: Thanks for taking the time to look into this.
Have you noticed that the file-based CRC and the check-string/check-hexstring do different things for the same input? So there is clearly a bug and I think the problem is in the check-string.

In particular:

• You reflect the register (after loading the initial value into it) when reflect-in is set. This should be reflect-out. This is wrong in the file-based implementation (probably undiscovered because in almost all cases reflect-in/reflect-out go together) and my patch fixed this, too
• The reflection of the register doesn't seem to be done for the check-string/check-hexstring case
• This manifests only if you have
  • reflect-out set
  • An xor-in value that is asymmetric

Example, see the second set of calls where I compare the behaviour of check-file and check-string:

: %; echo -n 12345678 > 12345678
: %; cat 12345678 12345678 > 1234567812345678
: %; pycrc --model crc-32 --check-file=12345678            
0x9ae0daaf
: %; pycrc --model crc-32 --check-string=12345678
0x9ae0daaf
: %; tools/xor.py 0x9ae0daaf 0xffffffff
651F2550
: %; pycrc --model crc-32 --xor-in=0x651F2550 --check-file=12345678
0x6bcc57b7
: %; pycrc --model crc-32 --xor-in=0x651F2550 --check-string=12345678
0xf3b32bd5
: %; pycrc --model crc-32 --check-file=1234567812345678          
0x6bcc57b7
: %; pycrc --model crc-32 --check-string=1234567812345678 
0x6bcc57b7

[schlatterbeck]

Concerning your other message:
The python/zlib crc32 implementation takes two parameters, the string to check and an optional crc-in parameter. The xor-in is applied to the crc-in before using the result as the initial value of the crc. That's why it chains.

From your 1. -- 6.: It seems you're missing step 2. (Reflect the register) for the check-string and check-hexstring cases, see example in previous comment.
The reflection should only happen if reflect-out is True. Not if reflect-in is True. The reflect-in deals solely with the byte-reflection when reading input.

I'll try to dig up some other general crc implementations and back up my claims with examples.

Also note: I wasn't able to reproduce your failing tests. For me with or without patch I'm getting:

: %; python test/test.py
Test OK

[schlatterbeck]

Ok, I've discovered the -a option to test.py (from your comment on my other issue :-)
There is just one test failing (or does it stop on the first failed test?). This is due to the reflect-in vs. reflect-out correction I made: Reflection of the xor-in should happen if reflect-out is set not reflect-in. I'll check this against another crc-implementation and will update my pull-request accordingly.

[schlatterbeck]

OK, tested this:

• Seems the xor-in should never be reflected
• I've verified against crchack and the original rocksoft reference implementation
  https://github.com/resilar/crchack
  http://www.ross.net/crc/download/crc_v3.txt
• All agree to your check-string and check-hexstring implementations: The xor-in is never reflected
• This means your file-feeding implementation is wrong, I've updated my pull request, see No reflection of xor-in #35

This all means that for an algorithm with reflect-out=True when we want to feed multiple values and have the same effect as a single feed of the whole string we must do the following with the result from the previous feed:

• Undo the effect of xor-out
• Reflect
• use the result as the xor-in for the next feed

Note that the following example works with my patch applied, otherwise the check-file version in the second pair of pycrc calls will fail.
So for crc-32 we do (my previous example adapted for an additional reflect step):

: %; echo -n 12345678 > 12345678
: %; cat 12345678 12345678 > 1234567812345678
: %; pycrc --model crc-32 --check-file=12345678            
0x9ae0daaf
: %; pycrc --model crc-32 --check-string=12345678
0x9ae0daaf
: %; tools/xor.py 0x9ae0daaf 0xffffffff
651F2550
: %; tools/reflect.py 651F2550
0xaa4f8a6
: %; pycrc --model crc-32 --xor-in=0xaa4f8a6 --check-file=12345678
0x6bcc57b7
: %; pycrc --model crc-32 --xor-in=0xaa4f8a6 --check-string=12345678
0x6bcc57b7
: %; pycrc --model crc-32 --check-file=1234567812345678          
0x6bcc57b7
: %; pycrc --model crc-32 --check-string=1234567812345678 
0x6bcc57b7