Forum Rule: Always post complete source code & details to reproduce any issue!
Page 1 of 4 1 2 3 ... LastLast
Results 1 to 25 of 96

Thread: Fast CRC library (uses the built-in crc-module in Teensy3)

  1. #1
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203

    Fast CRC library (uses the built-in crc-module in Teensy3)

    EDIT: Now AVR-compatible.
    EDIT: Added very fast table crc-algorithms in pure c++ for all supported CRCs. The lib is now compatible to all MCUs. For Teensy 3.0 or 3.1, the fast on-chip-hardware is used (because it's still faster!).

    For 32BIT, there are two variants with different table-sizes.
    The default uses really big tables with a size of 4KB, but it can be switched to smaller tables with 1KB (but a bit slower)
    Code:
    // Set this to 0 for smaller 32BIT-CRC-Tables:
    #define CRC_BIGTABLES 1
    Link:http://https://github.com/FrankBoesing/FastCRC

    Currently supported CRCs:
    8 BIT: SMBUS MAXIM (Table size 256 Bytes)
    16 BIT: KERMIT (Alias CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-CCITT) CCITT-FALSE MCRF4XX MODBUS XMODEM (Alias ZMODEM, CRC-16/ACORN) X25 (Alias CRC-16/IBM-SDLC, CRC-16/ISO-HDLC, CRC-B) and all from _avr_libc (Table size 2KB)
    32 BIT: CRC32, CRC-32/ADCCP, PKZIP, ETHERNET, 802.3 CKSUM, CRC-32/POSIX (Table size 4KB or 1KB)

    Edit: There was a bug in "SMBUS", the nibbles where reversed. I fixed that.

    Old Post:

    Hi,

    i'm developing a FastCRC Library for Cortex M4 (Teensy3).
    (see link above)

    Since i've never done that before for Arduino, and the Arduino-world is still new for me, iwould like to ask if somebody could have a look at it
    and tell me, if the naming of functions and so on (is there a "style guide" ?) is ok.

    Tests, tips and comments are welcome.

    Thank you,
    Frank.
    Last edited by Frank B; 03-02-2015 at 08:32 PM. Reason: Change Link

  2. #2
    Senior Member
    Join Date
    Jun 2013
    Location
    So. Calif
    Posts
    2,828
    Thanks for the work!
    Code looks great to me.
    recommendations:
    Add comments just above each class method in the cpp file, saying what the purpose is, input, output, parameters, and anything non-obvious like an initialization then multiple calls.
    And somewhere, maybe explain how this is using K20 hardware acceleration and the gist of that, and a pointer into a K20 document for more detail.

    Serial.flush() - not normally used. Are you doing it to assure the output is finished before starting the timed code loops?

    Optional: I tend to use Serial.printf() to simplify, control, and reduce typing!

    No style guide. The best work I've seen on docs that are Teensy relevant are at
    http://www.airspayce.com/mikem/arduino/RadioHead/

    where he spent the time to get doxygen coded. Maybe an overkill for your simpler case.

  3. #3
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    21,314
    Thanks for making this nice library. Lots of projects need CRC checks.

    If you have time for a few quick edits, here are a couple ideas...

    I'd recommend using a consistent name, including capitalization, like "FastCRC.cpp" and "FastCRC" for the repository name, and "FastCRC" for the class name. As much as I like seeing Teensy3 promoted, it's probably best to mention Teensy's special CRC hardware in the readme file and any web page that gets created. Long-term, a short and descriptive name for your library will help people find and understand it, especially when looking at a long list of libraries.

    The Arduino IDE uses a case sensitive match between the .h file and library's directory name to resolve ambiguous includes, which can happen if another library happens to have any file named FastCRC.h. As a library grows in popularity, that situation can occur if someone tries to copy the files into another directory for a variety of reasons (usually confusion about which copy Arduino is really using).

    You'll almost certainly get requests for compatibility with non-Teensy boards. You might use a #else in the main file to compile the non-Teensy code. Many more people are likely to use your library in publicly shared projects if it always works on every board, even if it's only highly optimized on some. It's possible to use a much faster algorithm with lookup tables for the software-only version.

    Most libraries have a keywords.txt file to cause Arduino to highlight their keywords. It's simple to just copy another library's file and edit the words. Beware of converting the tab character to multiple spaces, which look the same in most text editors, but Arduino doesn't recognize multiple spaces in keywords.txt.

  4. #4
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Hi,
    thank you both very much !

    Today i changed some things, and did the first and (hopefully) last API-Change.

    It was very tricky because there is a minor bug in the Kinetis-silicon (Errata ID 2776) which makes it not easier to make a fast API. Finally i found a way, and surprisingly, this gave an additional huge speedup.
    Now, all CRC (including 8-bit) are calculated as 32 bit. This means 3/4 less writes to the dataregister.
    It is split into 3 classes for 8, 16, and 32 bit.
    The link in the first post is changed because a change of the name.

    In the next days, i'll do some more documentation (+keywords) and eventually add more CRC Routines.

    It would be great if somebody could test it with other ARMs with built-in CRC - if you want to, comment out the defines for teensy at the beginning of the files.
    I believe, the crc device is the same on all M4.

    Currently, there are 2 8-bit, 5 16-bit and one 32-bit (Ethernet) algos.

    For 32 bit, I want to read the manual again to find a way to feed the CRC with DMA.


    Thank you,
    Frank.

  5. #5
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Current List of supported CRC calculations:

    8 BIT

    SMBUS
    MAXIM

    16 BIT


    CCITT-FALSE
    KERMIT (Alias CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-CCITT)
    MCRF4XX
    MODBUS
    XMODEM (Alias ZMODEM, CRC-16/ACORN)
    X25 (Alias CRC-16/IBM-SDLC, CRC-16/ISO-HDLC, CRC-B)

    32 BIT


    CRC32 (Alias CRC-32/ADCCP, PKZIP, ETHERNET, 802.3)
    CKSUM (Alias CRC-32/POSIX)

    Up to 30 times faster than equivalent functions from Arduino/avr_libc.
    All tested with "check"-values from RevEng and should work "out of the box".
    If you miss a special CRC, feel free to ask...
    Last edited by Frank B; 05-02-2014 at 10:22 PM.

  6. #6
    Senior Member
    Join Date
    Nov 2012
    Posts
    1,217
    A very nice library Frank, thanks.
    One suggestion though. Can you organize your git repo directory structure in the same way as I have made in this zip file (below) so that it unpacks in such a way that the examples will compile "out of the box"? Then they will also show up in the IDE examples menu.
    http://members.shaw.ca/el_supremo/FastCRC.zip

    Pete

  7. #7
    Senior Member
    Join Date
    Nov 2012
    Posts
    1,217
    Could the defines of CRC_FLAG_NOREFLECT etc. be placed in FastCRC.h so that a user can call generic() properly?

    Pete

  8. #8
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Hi,


    I changed the structure, added some more documentation, and moved the #defines.

    Thank you,
    Frank.
    Last edited by Frank B; 03-01-2015 at 12:24 AM.

  9. #9
    Senior Member xxxajk's Avatar
    Join Date
    Nov 2013
    Location
    Buffalo, NY USA
    Posts
    532
    I too have been looking for something like this for my IP stack on the teensy 3.x. This looks like it is something I can totally use. thank you very much.

  10. #10
    Senior Member sumotoy's Avatar
    Join Date
    Nov 2012
    Location
    Venezia, Italia
    Posts
    421
    simply GREAT!

  11. #11
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Added very fast table crc-algorithms in pure c++ for all supported CRCs. The lib should now be compatible to all Arduino-MCUs. For Teensy 3.0 or 3.1, the fast on-chip-hardware is used (automatically).
    Link in the first post.

  12. #12
    Senior Member
    Join Date
    Jun 2013
    Location
    So. Calif
    Posts
    2,828
    polynomial/coefficients definitions I found used in Arduino was vague and ambiguous as to which if any standard it complied with.
    Risky if you put their CRC code in flash and ship thousands and they change the definition.
    So for my work, I put the CRC generator/checker in the project source and don't use Arduino's as it might change.

  13. #13
    Senior Member
    Join Date
    Jun 2013
    Location
    So. Calif
    Posts
    2,828
    polynomial/coefficients definitions I found used in Arduino was ambiguous as to which if any standard it complied with.
    Risky if you put their CRC-16 code in flash and ship thousands and they change the definition.
    So for my work, I put the CRC generator/checker in the project source and don't use Arduino's as it might change.

  14. #14
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Since i'm using the "official" polynoms and params, they will not change, never.
    They are identical to the ones from "Catalogue of parametrised CRC algorithms, CRC RevEng" (http://reveng.sourceforge.net/crc-catalogue/)
    This lib is not using anything from arduino, it's "standalone".

  15. #15
    Senior Member PaulStoffregen's Avatar
    Join Date
    Nov 2012
    Posts
    21,314
    Very nice work Frank!

    One issue that's probably going to come up when people try to use this on AVR is the size of the tables in RAM. After using ARM so much, I know the AVR PROGMEM and pgm_read_byte are so very painful.... but eventually it's going to come up. Might be worth putting those in?

  16. #16
    Quote Originally Posted by Frank B View Post
    Hi,
    It would be great if somebody could test it with other ARMs with built-in CRC - if you want to, comment out the defines for teensy at the beginning of the files.
    I believe, the crc device is the same on all M4.
    Not sure why you believe that, the CRC block might be the same within the Freescale range, other manufacturers are quite different.

    By coincidence I was implementing hardware CRC at work last week for a Freescale DSP, it uses exactly the same CRC block as the Kinetis chips. Your mention of errata had me quickly checking the datasheet!

    Nice job with the library. In the perhaps unlikely event a user calls a CRC function from an interrupt, it's worth noting that the hardware CRC is inherently not thread safe.

  17. #17
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Quote Originally Posted by PaulStoffregen View Post
    I know the AVR PROGMEM and pgm_read_byte are so very painful....
    Yes...
    But you're right, i'll add it.
    I could add some smaller tables for crc8+crc16 too.. maybe in a later version, on request.

  18. #18
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Quote Originally Posted by bobc View Post
    Not sure why you believe that, the CRC block might be the same within the Freescale range, other manufacturers are quite different.
    This was a year ago.. pls forgive me :-)

  19. #19
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    ooops.. and I should'nt use asm REV for other MCUs :-)

    Edit: Done
    Last edited by Frank B; 03-01-2015 at 10:16 PM.

  20. #20
    Senior Member
    Join Date
    Jun 2013
    Location
    So. Calif
    Posts
    2,828
    Quote Originally Posted by Frank B View Post
    Since i'm using the "official" polynoms and params, they will not change, never.
    They are identical to the ones from "Catalogue of parametrised CRC algorithms, CRC RevEng" (http://reveng.sourceforge.net/crc-catalogue/)
    This lib is not using anything from arduino, it's "standalone".
    The best solution is to comply with ISO - and state exactly what constants in ISO are being used:
    Initial value
    coefficients
    polynomial


    It is a large concern when one replicates that Arduino library code in volumes of devices in the field then some Arduino-ite changes it, e.g., to correct the ambiguity.
    Last edited by stevech; 03-01-2015 at 08:11 PM.

  21. #21
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Quote Originally Posted by stevech View Post
    The proper solution is to comply with ISO.
    These are fixed algorithms, a fixed input gives the same (correct!) output every time.
    There's no guessing or interpretation involved. The parameters are clearly defined. If one gives the wrong results, please tell me - that would be a bug.

    If there's an important ISO-algorithm missing, please tell me its polynom & parameters and I'm happy to implement it.


    EDIT: in fact, some of them are ISO :-)
    Last edited by Frank B; 03-01-2015 at 08:40 PM.

  22. #22
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    You added:
    Quote Originally Posted by stevech View Post
    The best solution is to comply with ISO - and state exactly what constants in ISO are being used:
    Initial value
    coefficients
    polynomial
    pls look at the sourcecode.

    Example:
    Code:
    /** CRC32
     * Alias CRC-32/ADCCP, PKZIP, Ethernet, 802.3
     * @param data Pointer to Data
     * @param datalen Length of Data
     * @return CRC value
     */
    uint32_t FastCRC32::crc32(const uint8_t *data, const uint16_t datalen)
    {
      // poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926 <- params
      return generic(0x04C11DB7L, 0XFFFFFFFFL, CRC_FLAG_REFLECT | CRC_FLAG_XOR, data, datalen);
    }
    Last edited by Frank B; 03-01-2015 at 08:25 PM.

  23. #23
    Senior Member
    Join Date
    Jun 2013
    Location
    So. Calif
    Posts
    2,828
    But in the code - there's no reference to the ISO standard for CRC16 where the constants are defined. That's my point. It should cite ISO and that the code complies. So that any OTHER CRC16 per the same ISO standard should interoperate.

  24. #24
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    Added:

    https://github.com/FrankBoesing/Fast...ster/README.md
    Code:
    8 BIT:
    
    SMBUS
     (poly=0x07 init=0x00 refin=false refout=false xorout=0x00 check=0xf4)
     
    MAXIM
     (poly=0x31 init=0x00 refin=true refout=true xorout=0x00  check=0xa1)
     
     
    16 BIT:
    
    KERMIT (Alias CRC-16/CCITT, CRC-16/CCITT-TRUE, CRC-CCITT)
     (poly=0x1021 init=0x0000 refin=true refout=true xorout=0x0000 check=0x2189
      Attention: sometimes you'll find byteswapped presentation of result in other implementations)
     
    CCITT-FALSE
     (poly=0x1021 init=0xffff refin=false refout=false xorout=0x0000 check=0x29b1)
     
    MCRF4XX
     (poly=0x1021 init=0xffff refin=true refout=true xorout=0x0000 check=0x6f91)
     
    MODBUS
     (poly=0x8005 init=0xffff refin=true refout=true xorout=0x0000 check=0x4b37)
     
    XMODEM (Alias ZMODEM, CRC-16/ACORN)
     (poly=0x1021 init=0x0000 refin=false refout=false xorout=0x0000 check=0x31c3)
     
    X25 (Alias CRC-16/IBM-SDLC, CRC-16/ISO-HDLC, CRC-B)
     (poly=0x1021 init=0xffff refin=true refout=true xorout=0xffff check=0x906e)
    
     
    32 BIT:
    
    CRC32, CRC-32/ADCCP, PKZIP, ETHERNET, 802.3
      (poly=0x04c11db7 init=0xffffffff refin=true refout=true xorout=0xffffffff check=0xcbf43926)
      
    CKSUM, CRC-32/POSIX
      (poly=0x04c11db7 init=0x00000000 refin=false refout=false xorout=0xffffffff check=0x765e7680)

  25. #25
    Senior Member+ Frank B's Avatar
    Join Date
    Apr 2014
    Location
    Germany NRW
    Posts
    6,203
    @Paul,
    what do you think, can i use the "new" __flash attribute instead of PROGMEM ?
    What's the current AVR GCC version of arduino ?

    argh..i really dislike PROGMEM from the bottom of my heart..
    Last edited by Frank B; 03-01-2015 at 11:12 PM.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •