tpircher-zz / pycrc Goto Github PK

Nice tool ! I needed to implement Zip CRC and it worked. Thanks

However, I found the generated main function not so useful.
I propose :

#include <stdio.h>
#include <string.h>
#include "crc.h"

#define BLOCK_SIZE 16384

int main(void) {
    char* buffer[BLOCK_SIZE];
    crc_t crc = crc_init();
    for(;;) {
        size_t bytes = fread(buffer,  sizeof(char),BLOCK_SIZE,stdin);
        crc = crc_update(crc, buffer, bytes);
        if (bytes < BLOCK_SIZE)
            if (feof(stdin))
                break;
    }
    crc = crc_finalize(crc);
    printf("%lx", (unsigned long)crc);
    return 0;
}

which prints crc of stdin to stdout.

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?

Hi,
I have experienced problem with using table driven algorithm on 8bit machine. It returns different crc values then bbf calculates. Same piece of code running on win32 platform returns correct (the same) crc.
What should i do to make it works? I'm using stm8 platform with Cosmic free compiler.
Thank you in advance
Krzysiek

So I generated the C source code using the following parameters.
python pycrc.py --width 8 --algorithm tbl --poly 0x31 --reflect-in true --reflect-out true --xor-in 0x10 --xor-out 0xF7 --generate c -o crc.c

I'm using http://www.sunshine2k.de/coding/javascript/crc/crc_js.html to confirm my output.
And I noticed that using 0x00 gives me a different value on the C source code than on the JS calculator.
With this parameters 0x00 should output 0x35 but on the C code it's outputting 0xFF.
Also note that using any chain that contains 0x00 also gives a different output.
Ex. {0xFE, 0x61, 0x01, 0x00, 0x16, 0x02, 0x00, 0x14, 0x8C} should be 0x24 but it's 0x6b on the C code.
Is there something I can do to make the C code match the JS calculator?

When generating code for this:

• Generated on Wed Feb 19 00:52:04 2020
• by pycrc v0.9.2, https://pycrc.org
• using the configuration:
• • Width = 16
• • Poly = 0x8005
• • XorIn = 0x0000
• • ReflectIn = True
• • XorOut = 0x0000
• • ReflectOut = True
• • Algorithm = table-driven
• • SliceBy = 8

the generated code contains this:
typedef uint_fast16_t crc_t;

If uint_fast16_t is actually 32 bits, this will make my tables twice as big as they need to be, so I substituted uint16_t for crc_t, but this is also a problem: In the following generated code (LE version shown)
crc_t d1 = *d32++ ^ crc;
crc_t d2 = *d32++;
the type of d1 and d2 should NOT be 16-bits. I changed the types here to uint32_t and everything seems to work fine.

Is the other project called pyCRC the python equivalent?

thx
mathias

I'm trying to use code generated by ./pycrc.py --model crc-32c --algorithm table-driven --generate c / ./pycrc.py --model crc-32c --algorithm table-driven --generate h to generate snappy-framed data, but the checksums don't match what other implementations expect.

Appendix B.4 of RFC 3720 includes some test vectors, so I threw together a quick program to verify pycrc's implementation and it fails:

#include "crc32.h"
#include <assert.h>
#include <stdio.h>

int main(int argc, char *argv[]) {
  const uint8_t test_vectors[][32] = {
    { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
    { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff },
    { 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
      0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
      0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
      0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f },
    { 0x1f, 0x1e, 0x1d, 0x1c, 0x1b, 0x1a, 0x19, 0x18,
      0x17, 0x16, 0x15, 0x14, 0x13, 0x12, 0x11, 0x10,
      0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
      0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 }
  };

  assert (0xaa36918a == crc_finalize (crc_update(crc_init (), test_vectors[0], sizeof(test_vectors[0]))));
  assert (0x43aba862 == crc_finalize (crc_update(crc_init (), test_vectors[1], sizeof(test_vectors[1]))));
  assert (0x4e79dd46 == crc_finalize (crc_update(crc_init (), test_vectors[2], sizeof(test_vectors[2]))));
  assert (0x5cdb3f11 == crc_finalize (crc_update(crc_init (), test_vectors[3], sizeof(test_vectors[3]))));

  return 0;
}

Due to hardware constraints, attempting to generate an 8-bit CRC using a 16-bit CRC.
pycrc gives different answers for its separate algorithms.

> python --version
Python 2.7.10
>python pycrc.py --width=8 --poly=0x105 --reflect-in=False --xor-in=0xfe --reflect-out=False --xor-out=0x00
0x91
> python pycrc.py --width=16 --poly=0x10500 --reflect-in=False --xor-in=0xfe00 --reflect-out=False --xor-out=0x00
pycrc.py: error: different checksums!
       bit-by-bit:        0x100
       bit-by-bit-fast:   0x9100
       table_driven:      0x9100

Please add support to generate C code for big-endian targets like Arduino.

Qualcomm CRC-24Q as used with RTCMv3. Similar to the other crc-24 but with xor_in = 0.

models.append({
    'name':         'crc-24q',
    'width':         24,
    'poly':          0x864cfb,
    'reflect_in':    False,
    'xor_in':        0x0,
    'reflect_out':   False,
    'xor_out':       0x0,
    'check':         0xcde703,
})

Generated code was verified on real RTCM data, 'check' was produced by --check-string "123456789". Checking with another RTCMv3 string should show this, matching the checksum on the wire 0xa8f72a:

python3 pycrc.py --width=24 --poly=0x864CFB --reflect-in=false --xor-in=0 --reflect-out=false --xor-out=0 --check-hexstring "d300084ce0008a00000000"
0xa8f72a

When I run this:
./pycrc.py --verbose --width 10 --poly 0x633 --reflect-in False --xor-in 0 --reflect-out False --xor-out 0 --algorithm table-driven --generate c -o crc10.c
it gives this:
Width = 10
Poly = 0x233
ReflectIn = False
XorIn = 0x000
ReflectOut = False
XorOut = 0x000
Algorithm = table-driven

The poly is not the one I input, but the crc10.c is same when poly is 0x633 and 0x233, and the same in the c code。
I am not read the code deeply, but I've tried other numbers, and I find, it seems that it missed the leading "1" more than 10 bits. But I think this is a bug, the poly output should be just the one which is from input.

When generating code for a "reflected" CRC, a function is used to reflect each input byte. This is inefficient—it would be preferable to use an alternative core CRC algorithm that is a "reflected" algorithm. See Chapter 11 "Reflected" Table-Driven Implementations of A Painless Guide to CRC Error Detection Algorithms by Ross Williams. That describes a reflected table-driven algorithm; there would similarly be a reflected bit-by-bit algorithm.

When the CRC width is less than 8 then the bit-by-bit algorithm needs to apply the CRC mask to the final value.

Thanks to Steve Geo for reporting.

I'ld be interested in the actual speed of the generated compiled code. Guess quite some other people looking at this project might also be wondering about this.

It would be nice if one could generate a main() function that computes a crc over a specific, given amount of data and measures the time needed for that. Like 1MB of 0x42 or so.

So one could easily compare the different crc algorithms implemented by your code to existing crc implementations to find out what's fastest.

In my case, I am esp. interested in:

• a function fully compatible to python3's zlib.crc32, but (significantly) faster
• any function somehow comparable to crc32, but significantly faster

The crc-16-modbus model is backwards for example it says: "0xA762" when is "0x62A7".

EDIT: My mistake! it works fine.

There is some confusion about the "correct" initial value of the 16-bit CCITT CRC. See CRC-CCITT -- 16-bit (other source) which explains it.

It has to do with the question of "augmented" zero bits at the end of the message, and an algorithm that can avoid the need for it, but needs a modification to the initial value. See Chapter 10, "A Slightly Mangled Table-Driven Implementation", of A Painless Guide to CRC Error Detection Algorithms for an explanation.

In short, perhaps pycrc's ccitt model should have an --xor-in initial value of 0x1D0F instead of 0xFFFF.

See also:

• CRC-16/AUG-CCITT versus CRC-16/CCITT-FALSE in the Catalogue of parametrised CRC algorithms
• Online CRC calculator which allows calculating with "nondirect" and "direct" algorithms, and converting the initial values between these two algorithms.

Please add "Fork me on GitHub" Ribbon on https://pycrc.org/ for easy access to GitHub.
https://github.blog/2008-12-19-github-ribbons/

When using pycrc with C++ code you need to use a lot of reinterpret_cast<const unsigned char*>(...) when calling crc_update() with anything other than unsigned char, because C++ doesn't allow implicit conversion between such types. The only implicit conversion that is allowed is "anything" -> "const void*", so I'd propose to change prototype of crc_update() to:

crc_t crc_update(crc_t crc, const void *data, size_t data_len);

There is special support for crc computation in intel/AMD CPUs since quite some years:

http://www.drdobbs.com/parallel/fast-parallelized-crc-computation-using/229401411

https://en.wikipedia.org/wiki/SSE4#Supporting_CPUs

The drdobbs article says that this yields performance of about 1.17 cycles per 64bits word (for a measurement done with a loop, repeatedly computing over a small amount of data, so I guess one can assume they sit in L1 or L2 cache of cpu).

At 2.4GHz, this could mean up to 16GB/s (or whatever your RAM bandwidth is limiting this value to).

My binary file starts with 0xff - and when I run:

$ python2.7 ~/git/pycrc/pycrc.py --model=crc-16 --check-file forthboot.bin --xor-in=0xffff --reflect-out=0 --xor-out=0xffff
Traceback (most recent call last):
  File "/Users/jamesb/git/pycrc/pycrc.py", line 269, in <module>
    sys.exit(main())
  File "/Users/jamesb/git/pycrc/pycrc.py", line 240, in main
    crc = check_file(opt)
  File "/Users/jamesb/git/pycrc/pycrc.py", line 198, in check_file
    register = crc_file_update(alg, register, check_bytes)
  File "/Users/jamesb/git/pycrc/pycrc.py", line 152, in crc_file_update
    check_bytes = bytearray(check_bytes, 'utf-8')

Works fine with python3.5

Traceback (most recent call last):
  File "/usr/bin/pycrc", line 26, in <module>
    from pycrc.main import main
  File "/usr/lib/python3.10/site-packages/pycrc/main.py", line 46, in <module>
    import pycrc.codegen as cg
  File "/usr/lib/python3.10/site-packages/pycrc/codegen.py", line 37, in <module>
    import pycrc.symtable
  File "/usr/lib/python3.10/site-packages/pycrc/symtable.py", line 49, in <module>
    class SymbolTable(collections.MutableMapping):
AttributeError: module 'collections' has no attribute 'MutableMapping'

Looks like collections.MutableMapping was deprecated at some point ?

Thanks for pycrc!

For table driven algorithms with --table-idx-width greater than 1, it would be nice to generate code that ensures aligned access.

Currently, any trailing unaligned bytes are handled individually (i.e. anything after the Remaining bytes with the standard algorithm comment), but it would be great to handle leading unaligned bytes individually as well, to ensure that the main loop is using aligned loads.

Hi
Is it any way to generate c code (or two versions of code) which will support both big and little endian CPUs?
Kris

pycrc could be even faster if it supported the slicing-by-8 or slicing-by-4 algorithms, which would just require additional tables to be generated:

https://matt.sh/redis-crcspeed
http://create.stephan-brumme.com/crc32/

Is this something you would want pycrc to support?

Please consider adding this verbiage to the Frequently Asked Questions list for pycrc :

Problem :
Error ": No such file or directory" when trying to run pycrc.py on Linux

Solution :
After extracting pycrc-0.8.3.zip with the linux 'unzip' command, run the command "dos2unix /path/to/pycrc-0.8.3/pycrc.py" to convert the file from MS-DOS format to Unix format.

Failure to do this can result in the error ": No such file or directory" when running the command "pycrc.py --help"

Thank you for your attention on this matter.

I do not get any code beside the header comment when I call it as follows
./pycrc.py --width=8 --poly=0x07 --xor-in=0 --xor-out=0x55 --reflect-in=false --reflect-out=False --table-idx-width=4 --algorithm=table-driven --generate=table

I ecpected some kind of hex number sequence to be included in my static table (at least v0.7.8 worked this way).

Currently the Crc class in algorithms.py can only feed a single string into algo. This should be changed to separate initialization (xor-in), feeding and finalization (xor-out). This has the following advantages:

• The File input can use the same mechanism, the current file-feeding implementation is sort of a workaround
• We can run through the algorithm one feed-unit at a time. This is nice, e.g., when searching for a given initial state when running a CRC backwards (with reflected poly and reflected input) until a start-state is reached
• We could feed bit-wise for the bitwise variants

To make this work I'd separate the single Crc class into three classes, each one implementing the given variant, e.g. CrcBitByBit, CrcTableDriven, ... because the feeding is probably not compatible across the variants.

This would also allow bitwise feeding for the bitwise algos: My use-case here is finding the number of excess bits at the end of a message described in the section "Clearing Up some Puzzles" of Gregory Ewings "Reverse-.Engineering a CRC Algorithm": Here we're running a CRC with only the polynomial known over a XOR of two different messages that differ by only one bit (Greg calls this a difference-message). This is used to discover how far to go (over how much data the original CRC was computed, if it included additional data after the contents we know about). The Algo is initialized with the poly in the register and run until the known CRC is reached (the CRC of two XORed messages is the XOR of both CRC values)
If the 1-bit difference is not on a byte boundary this fails. So we need a way to bitwise feed the algorithm (with zeros in this use-case).

Do we have a regression test? In that case I'd do a stab at this and propose a code-change.

https://pycrc.org/models.html states that the model name for CCITT is ccitt, but from 78d3056 the model name is in fact crc-16-ccitt.

The generated function crc_update has a parameter data_len which sets the number of data bytes. Sometimes there are algorithms (e.g.: https://datasheets.maximintegrated.com/en/ds/MAX14917.pdf) which use nonstandard messages, for example, 11 bits. It would be nice if pycrc supported these algorithms.

When using the following command line:

/pycrc.py --model crc-5 --algorithm table-driven --std=c89 --generate c -o source.c

a source.c is generated with following crc_update:

 crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len)
 {
     unsigned int tbl_idx;

     while (data_len--) {
         tbl_idx = ((crc >> 3) ^ *data) & 0xff;
         crc = (crc_table[tbl_idx] ^ (crc >> 8)) & (0x1f << 3);

         data++;
     }
     return crc & (0x1f << 3);

with crc_t typedef'ed to unsigned char.

This means that the crc >> 8 is always 0. Is this intended?

pycrc.py --version
pycrc v0.8.2

Take http://zorc.breitbandkatze.de/crc.html for reference. This is just for completeness and for studying purposes rather than for real world usage though.

Hi,

I calculated CRC-16/X-25. and Now I want to generate a C-file for that. I am writing the following command.

pycrc.py --model x-25 --generate c -o crc

//crc is the file name
And I am getting the following error:

pycrc: error: select an algorithm to be used in the generated file

I am not able to decode this error. Can you please help me with it. Thank you.

In http://reveng.sourceforge.net/crc-catalogue/, the CRCs described within utilize a residue value as part of their calculations. In the case of CRC8 (or at least the implementation pycrc uses), it uses a residue value of 0x00, however other CRC algorithms use different residue values. Do you think that residue values can be reasonably implemented into pycrc, @tpircher?

Hello,
I was using PyCRC in my project (https://libraries.io/pypi/PyCRC / https://github.com/alexbutirskiy/PyCRC, which is not maintained any more and has nothing to do with https://github.com/tpircher/pycrc) and my nightly builds started failing, because the python package index removed "PyCRC 1.21" and added "pycrc version 0.9.2" instead (https://pypi.org/project/pycrc/#history shows the release was done on January 24), therefore I started getting those error messages:

ERROR: Could not find a version that satisfies the requirement PyCRC==1.21 (from -r requirements.txt (line 3)) (from versions: 0.9.2)
ERROR: No matching distribution found for PyCRC==1.21 (from -r requirements.txt (line 3))

I just wanted to document the issue there in case it affects other people. It is quite confusing that the python package index just replaced one package with another even though they are not related, and kept the same package name with a different case, knowing that pip is case insensitive.