15 ms·

Generic CRC algorithm generator, from Mark Adler

68 points by childintime 5y ago

compsciphd 5y ago
I think most CRC libraries should have a rolling implemenation built in (i.e. as you read bit by bit, or word by word, it calculates the crc for the last N bits (i.e. a rolling crc32 would allow you to read bit by bit and get the crc for the last 32 bits read). Its actually relatively straight forward to do, and surprisingly useful, but post libraries don't implement it. my practice code at implementing it for fun: https://github.com/sjpotter/window-crc32 https://github.com/sjpotter/window-crc32
xondono 5y ago
If you find yourself debugging the mysteries of hardware accelerated CRC (for instance in some poorly documented embedded device), this calculator saved me multiple times. It’s pure gold. https://ninja-calc.mbedded.ninja/calculators/software/crc-calculator https://ninja-calc.mbedded.ninja/calculators/software/crc-ca...
bxparks 5y ago
A similar code generator for CRC algorithms is https://pycrc.org/ https://pycrc.org/ . I don't know enough to compare the two, but one difference that I notice is that pycrc supports 4-bit lookup tables, where as crcany does not seem to. A 4-bit lookup table consumes only 16 elements instead of 256 elements, so for example, the CRC32 table consumes only 64 bytes instead of 1024 bytes. This can be very helpful in microcontroller environments with limited flash memory. On the 32-bit microcontrollers that I have tested (SAMD21, STM32, ESP8266, ESP32, Teensy 3.2), using the 4-bit lookup table is ~4X faster than the bit-by-bit algorithm, but only ~2X slower than the byte-by-byte algorithm, so it can be a good compromise between memory and speed.
- childintime 5y ago
  The 4-bit lookup is a nice compromise. Note pycrc has a fixed list of "supported models": crc-5, crc-8, dallas-1-wire, crc-12-3gpp, crc-15, crc-16, crc-16-usb, crc-16-modbus, crc-16-genibus, crc-16-ccitt, r-crc-16, kermit, x-25, xmodem, zmodem, crc-24, crc-32, crc-32c, crc-32-mpeg, crc-32-bzip2, posix, jam, xfer, crc-64, crc-64-jones, crc-64-xz.
vlovich123 5y ago
Generally, given the CPU acceleration available, one should generally prefer SHA1 or SHA256. CRC/MD5 is really only advisable if you're being forced into it for some legit backward compatibility reason. Most embedded CPUs these days can handle SHA variants just fine (I've used SHA256 on an M3 and even more crazily on the Kalimba of a CSR8605 which is a 48-bit DSP with a char size of 24 bits as well as its coprocessor which is a 32-bit CPU which a char size of 16 bits).
- zbjornson 5y ago
  CRCs have the awesome ability to be composed, and are many times faster to compute than SHAs with the best hardware acceleration.
  - nullc 5y ago
    And can also give guaranteed distance properties-- so you can e.g. guarantee all corruption of hamming distance <D within a message size of <W will be detected, -- which is a massive improvement in performance when that's what you need to catch.
    - CorrectHorseBat 5y ago
      SHA will detect corruption of any size, but it can't be used for correction.
      - nullc 5y ago
        It (and particularly truncated hashes made from it) is not _guaranteed_ to detect small corruptions. It will falsely admit 1 in 2^bits. A well matched CRC is can give guaranteed detection even with a very short hash.
        adrian_b 5y ago
        True, but one must not forget that the good error detection properties of CRCs are guaranteed only for limited data lengths. The CRCs of usual sizes, up to 32 bits, are perfectly fine for data sizes in the kilobyte range, but they become poor at megabyte sizes and completely useless at gigabyte sizes. The CRCs have their domain of application for which they are excellent, but some times they are misused, e.g. in various archive file formats, where the archive integrity is checked with a too short CRC instead of using a hash of appropriate length, e.g. SHA-1 or SHA-256. The longer hashes may be truncated, e.g. to 128 bit, which is likely enough for the current sizes of files and file systems, but 64-bit or less is not enough for the kind of files that are typically encountered now.
cperciva 5y ago
Note that if you're actually using CRCs in any serious way, you probably want to use CPU intrinsics rather than generic C code.
- kevin_thibedeau 5y ago
  Hardware CRC peripherals are often limited to a single polynomial or are restricted in how they invert/reflect the data.
  - ajb 5y ago
    Modern processors often contain polynomial multiply instructions or similar, which can be used for arbitrary CRC polynomials.
    - deleted 5y ago
      [deleted]
- dragontamer 5y ago
  You probably should be more specific than that. The CRC is a polynomial / Galois field, and today's CPUs have polynomial multiply (aka: pmul on ARM), or carryless multiply (aka: PCLMULQDQ on x86). These instructions can implement the "tough" part of the CRC in just one clock tick.
  - cperciva 5y ago
    That's my point. Your CRCs will be much faster if you use the cpu-specific instructions rather than relying on generic C code.
- ggrrhh_ta 5y ago
  the C code looks really nice and very generic, and, it being a generator... would it be too difficult to make use of those CPU instructions during the code generation? (then it could even create architecture-specific code, which looks like a plus to me)
- 5y ago
junon 5y ago
For those unaware, Mark Adler of zlib fame is the author of this. You can be sure a relatively high amount of knowledge is packed in here.
- sydthrowaway 5y ago
  I have no idea how he can produce excellent OSS libraries whilst also having a pretty high position at JPL.
  - xxpor 5y ago
    A surprising (to me at least) amount of very good OSS comes out of national labs. Another example is ZFS-on-Linux, now just OpenZFS
- collegeburner 5y ago
  Lmao his github profile just links to his wikipedia page, what an absolute flex. Guess he earned it tho.
  - xxs 5y ago
    Dunno, Mark Adler is a name that needs no introduction or 'flex'. Fun fact about him: with his name (family) he comes on top of the list of authors of virtually any project that he'd have participated and ordered alphabetically.
    - jon_adler 5y ago
      As someone who shares the same surname, always being at the top of the list was somewhat less desirable during school.
childintime 5y ago
Worth a mention: there is also a Rust "crcany": https://github.com/magiclen/crc-any https://github.com/magiclen/crc-any I don't know if or how it's related.

68 points by childintime 5y ago

I think most CRC libraries should have a rolling implemenation built in (i.e. as you read bit by bit, or word by word, it calculates the crc for the last N bits (i.e. a rolling crc32 would allow you to read bit by bit and get the crc for the last 32 bits read). Its actually relatively straight forward to do, and surprisingly useful, but post libraries don't implement it. my practice code at implementing it for fun: https://github.com/sjpotter/window-crc32 https://github.com/sjpotter/window-crc32

xondono 5y ago

If you find yourself debugging the mysteries of hardware accelerated CRC (for instance in some poorly documented embedded device), this calculator saved me multiple times. It’s pure gold. https://ninja-calc.mbedded.ninja/calculators/software/crc-calculator https://ninja-calc.mbedded.ninja/calculators/software/crc-ca...

bxparks 5y ago

A similar code generator for CRC algorithms is https://pycrc.org/ https://pycrc.org/ . I don't know enough to compare the two, but one difference that I notice is that pycrc supports 4-bit lookup tables, where as crcany does not seem to. A 4-bit lookup table consumes only 16 elements instead of 256 elements, so for example, the CRC32 table consumes only 64 bytes instead of 1024 bytes. This can be very helpful in microcontroller environments with limited flash memory. On the 32-bit microcontrollers that I have tested (SAMD21, STM32, ESP8266, ESP32, Teensy 3.2), using the 4-bit lookup table is ~4X faster than the bit-by-bit algorithm, but only ~2X slower than the byte-by-byte algorithm, so it can be a good compromise between memory and speed.

childintime 5y ago
The 4-bit lookup is a nice compromise. Note pycrc has a fixed list of "supported models": crc-5, crc-8, dallas-1-wire, crc-12-3gpp, crc-15, crc-16, crc-16-usb, crc-16-modbus, crc-16-genibus, crc-16-ccitt, r-crc-16, kermit, x-25, xmodem, zmodem, crc-24, crc-32, crc-32c, crc-32-mpeg, crc-32-bzip2, posix, jam, xfer, crc-64, crc-64-jones, crc-64-xz.

vlovich123 5y ago

Generally, given the CPU acceleration available, one should generally prefer SHA1 or SHA256. CRC/MD5 is really only advisable if you're being forced into it for some legit backward compatibility reason. Most embedded CPUs these days can handle SHA variants just fine (I've used SHA256 on an M3 and even more crazily on the Kalimba of a CSR8605 which is a 48-bit DSP with a char size of 24 bits as well as its coprocessor which is a 32-bit CPU which a char size of 16 bits).

zbjornson 5y ago
CRCs have the awesome ability to be composed, and are many times faster to compute than SHAs with the best hardware acceleration.
- nullc 5y ago
  And can also give guaranteed distance properties-- so you can e.g. guarantee all corruption of hamming distance <D within a message size of <W will be detected, -- which is a massive improvement in performance when that's what you need to catch.
  - CorrectHorseBat 5y ago
    SHA will detect corruption of any size, but it can't be used for correction.
    - nullc 5y ago
      It (and particularly truncated hashes made from it) is not _guaranteed_ to detect small corruptions. It will falsely admit 1 in 2^bits. A well matched CRC is can give guaranteed detection even with a very short hash.
      - adrian_b 5y ago
        True, but one must not forget that the good error detection properties of CRCs are guaranteed only for limited data lengths. The CRCs of usual sizes, up to 32 bits, are perfectly fine for data sizes in the kilobyte range, but they become poor at megabyte sizes and completely useless at gigabyte sizes. The CRCs have their domain of application for which they are excellent, but some times they are misused, e.g. in various archive file formats, where the archive integrity is checked with a too short CRC instead of using a hash of appropriate length, e.g. SHA-1 or SHA-256. The longer hashes may be truncated, e.g. to 128 bit, which is likely enough for the current sizes of files and file systems, but 64-bit or less is not enough for the kind of files that are typically encountered now.

cperciva 5y ago

Note that if you're actually using CRCs in any serious way, you probably want to use CPU intrinsics rather than generic C code.

kevin_thibedeau 5y ago
Hardware CRC peripherals are often limited to a single polynomial or are restricted in how they invert/reflect the data.
- ajb 5y ago
  Modern processors often contain polynomial multiply instructions or similar, which can be used for arbitrary CRC polynomials.
  - deleted 5y ago
    [deleted]
dragontamer 5y ago
You probably should be more specific than that. The CRC is a polynomial / Galois field, and today's CPUs have polynomial multiply (aka: pmul on ARM), or carryless multiply (aka: PCLMULQDQ on x86). These instructions can implement the "tough" part of the CRC in just one clock tick.
- cperciva 5y ago
  That's my point. Your CRCs will be much faster if you use the cpu-specific instructions rather than relying on generic C code.
ggrrhh_ta 5y ago
the C code looks really nice and very generic, and, it being a generator... would it be too difficult to make use of those CPU instructions during the code generation? (then it could even create architecture-specific code, which looks like a plus to me)
5y ago

junon 5y ago

For those unaware, Mark Adler of zlib fame is the author of this. You can be sure a relatively high amount of knowledge is packed in here.

sydthrowaway 5y ago
I have no idea how he can produce excellent OSS libraries whilst also having a pretty high position at JPL.
- xxpor 5y ago
  A surprising (to me at least) amount of very good OSS comes out of national labs. Another example is ZFS-on-Linux, now just OpenZFS
collegeburner 5y ago
Lmao his github profile just links to his wikipedia page, what an absolute flex. Guess he earned it tho.
- xxs 5y ago
  Dunno, Mark Adler is a name that needs no introduction or 'flex'. Fun fact about him: with his name (family) he comes on top of the list of authors of virtually any project that he'd have participated and ordered alphabetically.
  - jon_adler 5y ago
    As someone who shares the same surname, always being at the top of the list was somewhat less desirable during school.

childintime 5y ago

Worth a mention: there is also a Rust "crcany": https://github.com/magiclen/crc-any https://github.com/magiclen/crc-any I don't know if or how it's related.