[ Disclaimer | Appendix A | Appendix B | Appendix C | Appendix D | Appendix E | Appendix F | Appendix G | Appendix H | Appendix J | Appendix K | Home ]
Conforming to the Rocksoft™ Model CRC Algorithm Greg Cook, 4/Jun/2008
For an explanation of the format of each record, please consult "A Painless Guide" (reference below.)
Name : "CRC-5/USB" Width : 5 Poly : 05 Init : 1F RefIn : True RefOut : True XorOut : 1F Check : 19 Identified in an anonymous draft document, available from the USB Implementers Forum, Inc. Used in USB token packets. The resulting CRC is appended to the packet. When receiving, the packet and CRC are processed together to leave a remainder of 0x0C. (By coincidence the check string "123456789" leaves the same remainder, which is transmitted as 0x19.) Name : "CRC-8" Width : 8 Poly : 07 Init : 00 RefIn : False RefOut : False XorOut : 00 Check : F4 Confirmed by an example in this tutorial. Used in the SMBus protocol. The resulting CRC is appended to the frame. When receiving, the frame and CRC are processed together to leave a remainder of 0x00. The polynomial is also used in Asynchronous Transfer Mode cells. Name : "CRC-8/I-CODE" Width : 8 Poly : 1D Init : FD RefIn : False RefOut : False XorOut : 00 Check : 7E Confirmed by an example in the SL2 ICS11 specification. The resulting CRC is appended to the message. When receiving, the message and CRC are processed to leave a remainder of 0x00. Name : "CRC-11" Width : 11 Poly : 385 Init : 01A RefIn : False RefOut : False XorOut : 000 Check : 5A3 Confirmed by at least two samples embedded in E-Ray Application Note 002. (Researched by Vivek Rajan.) See Appendix H. Record derived from code in the FlexRay Protocol specification. Used for FlexRay frame headers. Name : "CRC-15" Width : 15 Poly : 4599 Init : 0000 RefIn : False RefOut : False XorOut : 0000 Check : 059E Record drawn up from code in this post. Used in the Bosch CAN 2.0 specification. Name : "ARC" Alias : "CRC-16" Alias : "CRC-16/ARC" Alias : "CRC-16/LHA" Width : 16 Poly : 8005 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : BB3D Tested in ARC, LHA and ZOO archivers. Implemented by Lammert Bies. Quoted with Check value in the crc MegaCore datasheet. Name : "CRC-16/ATOM" Width : 16 Poly : 002D Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : 4287 ACheck : 5333 Based on code and examples from "Splitting the Atom", a book on the Acorn Atom microcomputer. See Appendix J. This algorithm does not appear in the Atom kernel. Name : "CRC-16/AUG-2-CITT" Alias : "CRC-16/SPI-FUJITSU" Width : 16 Poly : 1021 Init : 84C0 RefIn : False RefOut : False XorOut : 0000 Check : 19CF Tested against two unpublished examples by Vivek Rajan. Used by the Fujitsu FlexRay controller. The User's Manual gives the polynomial and an initial value of 0x1d0f but the algorithm needs explicit augmentation, hence the initial value above. Name : "CRC-16/AUG-CITT" Width : 16 Poly : 1021 Init : 1D0F RefIn : False RefOut : False XorOut : 0000 Check : E5CC Confirmed with a worked example and Check value by Joe Geluso. Implemented by Lammert Bies and Joe Geluso. This is Joe Geluso's "Good CRC". Not the true X.25-CCITT algorithm. Name : "CRC-16/BT-CHIP" Width : 16 Poly : 1021 Init : FFFF RefIn : True RefOut : False XorOut : 0000 Check : 89F6 Confirmed with two examples reported by user "Nathan" on Lammert Bies' forum. Used to talk to an unidentified Bluetooth transceiver. Not necessarily the algorithm used in Bluetooth communications. For implementations that take a single Reflect parameter, specify True and manually reflect the result. Name : "CRC-16/BUYPASS" Width : 16 Poly : 8005 Init : 0000 RefIn : False RefOut : False XorOut : 0000 Check : FEE8 Reported for the multi-threaded portion of the Buypass transaction processing network. Name : "CRC-16/CITT" Alias : "CRC-16/CCITT" Width : 16 Poly : 1021 Init : FFFF RefIn : False RefOut : False XorOut : 0000 Check : 29B1 Implemented by Lammert Bies and Joe Geluso. Quoted with Check value in the crc MegaCore datasheet. This is Joe Geluso's "Bad CRC" and previously mentioned in many places in the literature. Not the true X.25-CCITT algorithm. Name : "CRC-16/DNP" Width : 16 Poly : 3D65 Init : 0000 RefIn : True RefOut : True XorOut : FFFF Check : EA82 XCheck : 82EA Implemented by Lammert Bies. Name : "CRC-16/I-CODE" Width : 16 Poly : 1021 Init : FFFF RefIn : False RefOut : False XorOut : FFFF Check : D64E Confirmed by an example in the SL2 ICS11 specification. The resulting CRC is appended to the message, MSB first. When receiving, the message and CRC are processed to leave a remainder of 0x1d0f. Name : "CRC-16/MCRF4XX" Width : 16 Poly : 1021 Init : FFFF RefIn : True RefOut : True XorOut : 0000 Check : 6F91 Confirmed by an example in the MCRF45X Application Note. In that document the bits are grouped by nibble rather than by byte, and so the nibbles in each byte must be swapped for Rocksoft™ model algorithms. The given example data, "8552F189", must be processed as the string of bytes 58 25 1F 98, to return the stated CRC "07F1". The application note states however that "the hex string to be sent will be: 981F25581F70". Also matches the algorithm demonstrated by Pierre Desrochers in this guide. Name : "CRC-16/USB" Width : 16 Poly : 8005 Init : FFFF RefIn : True RefOut : True XorOut : FFFF Check : B4C8 Identified in an anonymous draft document, available from the USB Implementers Forum, Inc. Used in USB data packets. The resulting CRC is appended to the packet, LSB first. When receiving, the packet and CRC are processed together to leave a remainder of 0x800D. Name : "KERMIT" Alias : "CRC-16/CCITT-TRUE" Width : 16 Poly : 1021 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : 2189 XCheck : 8921 Confirmed with two examples in "Numerical Recipes". Record derived from code in the Kermit Protocol Manual. According to "Numerical Recipes", the resulting CRC is appended to the message, LSB first. When receiving, the message and CRC are processed to leave a remainder of 0x0000. Name : "MODBUS" Width : 16 Poly : 8005 Init : FFFF RefIn : True RefOut : True XorOut : 0000 Check : 4B37 Implemented by Lammert Bies. Record derived from code [1] [2]. That it uses the ARC polynomial was confirmed by examples from Viktor Gottschald. There may be variants with Init = 0x5a5a. Name : "X-25" Alias : "CRC-16/IBM-SDLC" Alias : "CRC-16/ISO-HDLC" Width : 16 Poly : 1021 Init : FFFF RefIn : True RefOut : True XorOut : FFFF Check : 906E XCheck : 6E90 Listed in "Numerical Recipes" with two examples in the positive. Record deduced from sample frames in several forum posts. [1] [2] [3] Used by the HDLC protocol. According to "Numerical Recipes", the resulting CRC is appended to the message, bit complemented and LSB first. When receiving, the message and CRC are processed to leave a remainder of 0xf0b8. Name : "X-KERMIT" Alias : "X-XMODEM" Width : 16 Poly : 8408 Init : 0000 RefIn : True RefOut : True XorOut : 0000 Check : 0C73 Deprecated. Quoted with Check value in the crc MegaCore datasheet. Name : "ZMODEM" Alias : "XMODEM" Alias : "CRC-16/ACORN" Width : 16 Poly : 1021 Init : 0000 RefIn : False RefOut : False XorOut : 0000 Check : 31C3 Tested against files in the Acorn Cassette format used on the BBC Micro. Quoted with Check value, as "ZMODEM", in the crc MegaCore datasheet. Quoted with two examples, as "XMODEM", in "Numerical Recipes". Implemented by Lammert Bies. The CRC is appended to the header or data, MSB first. When loading, the block and the CRC are processed to leave a remainder of 0x0000. Name : "CRC-24" Alias : "CRC-24/OPENPGP" Width : 24 Poly : 864CFB Init : B704CE RefIn : False RefOut : False XorOut : 000000 Check : 21CF02 Quoted with Check value in "Crypto - Codes". Name : "CRC-24/FLEXRAY-A" Width : 24 Poly : 5D6DCB Init : FEDCBA RefIn : False RefOut : False XorOut : 000000 Check : 7979BD Name : "CRC-24/FLEXRAY-B" Width : 24 Poly : 5D6DCB Init : ABCDEF RefIn : False RefOut : False XorOut : 000000 Check : 1F23B8 Records derived from code in the FlexRay Protocol specification. Used for FlexRay frame payloads. Channels A and B have different initial vectors to prevent frames crossing channels. Name : "CRC-32" Alias : "CRC-32/ADCCP" Alias : "PKZIP" Width : 32 Poly : 04C11DB7 Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF Check : CBF43926 Tested against PKZIP 2.04g. Implemented by Lammert Bies. Quoted with Check value in the crc MegaCore datasheet. Name : "CRC-32C" Alias : "CRC-32/ISCSI" Alias : "CRC-32/CASTAGNOLI" Width : 32 Poly : 1EDC6F41 Init : FFFFFFFF RefIn : True RefOut : True XorOut : FFFFFFFF Check : E3069283 Quoted with Check value in this post about iSCSI. Name : "CRC-32/POSIX" Alias : "CKSUM" Width : 32 Poly : 04C11DB7 Init : 00000000 RefIn : False RefOut : False XorOut : FFFFFFFF Check : 765E7680 LCheck : 377A6011 Tested against the POSIX "cksum" implementation. Name : "JAMCRC" Width : 32 Poly : 04C11DB7 Init : FFFFFFFF RefIn : True RefOut : True XorOut : 00000000 Check : 340BC6D9 Quoted with Check value in the crc MegaCore datasheet. Name : "XFER" Width : 32 Poly : 000000AF Init : 00000000 RefIn : False RefOut : False XorOut : 00000000 Check : BD0BE338 Tested against the Xfer in C implementation by Mark de Weger et al.
Alias : Alternative name(s) for algorithm
Check : CRC result for ASCII string "123456789"
[31 32 33 34 35 36 37 38 39]
LCheck : CRC result for ASCII string "123456789" plus binary 9
[31 32 33 34 35 36 37 38 39 09]
XCheck : CRC result for ASCII string "123456789",
high and low byte swapped
ACheck : CRC result for ASCII string "123456789",
according the Atom checksum algorithm. See Appendix J.
Notes: Being based on the Rocksoft™ model ("Model"), these algorithms implicitly augment processed messages. Williams deals with augmentation in Section 10 of the "Painless Guide", showing that an implicitly augmenting algorithm, with a revised initial value, is equivalent to one that requires an augmented message.
In particular, one explicit-augmentation variant of "CRC-16/CITT" generates a Check value of 0xE5CC. As implicit or explicit augmentation is not a parameter in the Model, the difference can only be expressed through the above equivalence. Fortunately this algorithm is easily catered for in the Model by specifying "CRC-16/CITT" parameters but with an initial value of 0x1D0F. This value is derived from the shift register contents after the whole 'original' initial value, 0xFFFF, has been processed once. An example Model record is given here under "CRC-16/AUG-CITT".
Even so there is a class of implementations that the Rocksoft™ model cannot directly cover; those that use the explicit-augmentation form but do not augment the message. The last few bytes of the message are left 'in plain text', so to speak, XORed in the result. An example is the algorithm published in an unofficial guide to the Acorn Atom. A Rocksoft™-type implementation can emulate such routines by processing a 'diminished' message and then XORing the last bytes of the message into the result.
The POSIX utility "cksum" considers the length of the file as well as its content.
If the file is empty then it returns Init ^ XorOut as the result.
Otherwise after the content it processes each byte of the integer representing the length, LSB first, until all set bits have been
processed.
The DNP and HDLC algorithms require the result of a Rocksoft™ Model implementation to have the high and low bytes swapped, for example the true HDLC CRC of "123456789" is 0x6E90. A Rocksoft™ algorithm would return 0x906E.
The algorithm labelled "X-KERMIT" is deprecated. Often identified as KERMIT in the literature, it has a 16 bit shift register but only 13 bits participate in the CRC. Its transformation matrix indicates 79 bits to be XORed per byte of input, making the algorithm difficult to optimise in software. No references have been found to a 13 bit CRC limitation as a shortcoming in the Kermit protocol, so the specification in Numerical Recipes is more likely to be the correct one; this has been included under the name "KERMIT".
Numerical Recipes and "Crypto - Codes" claim that the "KERMIT" algorithm and CRC-CCITT are identical; this is probably true but for the moment, the algorithm listed here under "CRC-16/CITT" conforms to the implementation most often seen in code samples under this designator.
Devices made by Sick use a non-standard 16 bit algorithm that is not represented by the Rocksoft™ model.
Ross N. Williams "A Painless Guide to CRC Error Detection Algorithms" http://www.ross.net/crc/download/crc_v3.txt Altera Corporation "crc MegaCore Function Parameterized CRC Generator/Checker Data Sheet" http://www.msc.rl.ac.uk/europractice/vendors/dscrc.pdf Tom Torfs IOCCC winning entry, 1998, CRC generator http://www.ioccc.org/years.html#1998_tomtorfs Joe Geluso "CRC16-CCITT". A discussion of augmentation and its effects, and how neglecting them can cause an algorithm to be wrong. http://www.joegeluso.com/software/articles/ccitt.htm Philips Semiconductors SL2 ICS11 Product Specification (via NXP) http://www.nxp.com/acrobat_download/other/identification/SL092030.pdf B.M.Gammel "Crypto - Codes". Information, tables and code for the most popular algorithms. http://users.physik.tu-muenchen.de/gammel/matpack/html/LibDoc/Crypto/MpCRC.html Robert Bosch GmbH CAN 2.0 Specification http://www.semiconductors.bosch.de/pdf/can2spec.pdf E-Ray FlexRay IP Module Documentation and Application Notes http://www.semiconductors.bosch.de/en/20/flexray/flexray.asp http://www.semiconductors.bosch.de/pdf/ERay_Users_Manual_1_2_5.pdf http://www.semiconductors.bosch.de/pdf/070601_AN002_1R01.pdf Fujitsu Semiconductor Flexray ASSP MB88121B User's Manual http://edevice.fujitsu.com/fj/MANUAL/MANUALp/en-pdf/AM15-11201-1E.pdf Flexray Consortium Flexray Communications System Protocol Specification Version 2.1 http://www.softwareresearch.net/site/teaching/SS2007/ds/FlexRay%20-%20Protocol%20Specification_V2.1.rev%20A.pdf Frank da Cruz Kermit Protocol Manual, Sixth Edition http://www.columbia.edu/kermit/ftp/e/kproto.doc (plain text) Anonymous "Cyclic Redundancy Checks in USB" (Draft) Courtesy of USB Implementers Forum, Inc. http://www.usb.org/developers/whitepapers/crcdes.pdf Youbok Lee, PhD Microchip Technology Inc. "CRC Algorithm for MCRF45X Read/Write Device" http://ww1.microchip.com/downloads/en/AppNotes/00752a.pdf William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling Numerical recipes in C: The art of scientific computing. 2nd ed. Cambridge: Cambridge University Press; 1992. ISBN 0-521-43108-5
Lammert Bies "On-line CRC calculation and free library" http://www.lammertbies.nl/comm/info/crc-calculation.html "Error detection and correction" Web forum http://www.lammertbies.nl/forum/viewforum.php?f=11 Cyclic Redundancy Check at the Massmind (PicList) http://www.piclist.com/techref/method/error/crc.htm
Every effort has been made to ensure accuracy, however there may be occasional errors or omissions. "Rocksoft" is a trademark of Rocksoft Pty Ltd., Australia. The code and documentation included in this document (including, but not limited to, Appendices A to E) are supplied without warranty, not even the implied warranties of merchantability or fitness for a particular purpose. In no event shall the author or his suppliers be liable for any loss, damage, injury or death, of any nature and howsoever caused, arising from the use of, or failure, inability or unwillingness to use, this software or documentation.
[ Top of page ]
Map of the 16-bit CRC algorithms found so far.
| "123456789" (ASCII) |
Polynomial | 1021 | 8005 | ||
|---|---|---|---|---|---|
| Reflected? | False | True | False | ||
| Initial value | Final XOR | ||||
| 0000 | 0000 | 31C3 (ZMODEM) |
2189 (KERMIT) |
BB3D (ARC) |
FEE8 (BUYPASS) |
| FFFF | CE3C (–) |
DE76 (–) |
44C2 (–) |
0117 (–) |
|
| FFFF | D64E (I-CODE) |
906E (X.25) |
B4C8 (USB) |
5118 (–) |
|
| 0000 | 29B1 (CITT) |
6F91 (MCRF4XX) |
4B37 (MODBUS) |
AEE7 (–) |
|
| 6502 code | Appendix B | Appendix B | Appendix B | – | |
| ARM code | Appendix F | Appendix F | Appendix F | – | |
| 8080 / Z80 code | Appendix K | Appendix K | Appendix K | – | |
tomtorfs CHECK 16 1021 0 1D0F 0000 E5CC CRC-16/AUG-CITT tomtorfs CHECK 16 1021 0 84C0 0000 19CF CRC-16/AUG-2-CITT tomtorfs CHECK 16 3D65 1 0000 FFFF EA82 CRC-16/DNP tomtorfs CHECK 16 8408 1 0000 0000 0C73 X-KERMIT
[ Top of page ]
Merged with Appendix C
Sample 6502 assembly code to implement the nine major 16-bit algorithms in constant time, without the use of lookup tables.
*= $0070 crclo: .DB $FF crchi: .DB $FF *= $1900 .START * test: CLD LDY #$FF ; "CRC-16/CITT" init value = $FFFF ; LDY #$00 ; "ZMODEM" init value = $0000 STY crclo ; store init value STY crchi LDY #$00 byloop: LDA data,Y JSR crc16_citt_f INY CPY #lendata BMI byloop ; LDA crclo ; complement result ; EOR #$FF ; for I-CODE, X.25 or USB ; STA crclo ; LDA crchi ; EOR #$FF ; STA crchi BRK ; result is in $0070 and $0071 ; Add byte to CCITT or ZMODEM-style CRC ; On entry: ; A = byte to add ; crclo = low byte of CCITT CRC ; crchi = high byte of CCITT CRC ; (on the first call, crclo and crchi should be set ; according to the algorithm in use) ; On exit: ; crclo,crchi = New CCITT CRC with byte added ; On exit, when using alternative ending 1: ; S,V,B,D,I = preserved (subject to interrupts) ; A,X,Y,N,Z,C = undefined ; On exit, when using alternative ending 2: ; Y,S,V,B,D,I = preserved (subject to interrupts) ; A,X,N,Z,C = undefined ; Relocatable, non-re-entrant crc16_citt_f: ; add byte to CCITT CRC EOR crchi ; A contained the data STA crchi ; XOR it into high byte LSR ; right shift A 4 bits LSR ; to make top of x^12 term LSR ; ($1...) LSR TAX ; save it ASL ; then make top of x^5 term EOR crclo ; and XOR that with low byte STA crclo ; and save TXA ; restore partial term EOR crchi ; and update high byte STA crchi ; and save ASL ; left shift three ASL ; the rest of the terms ASL ; have feedback from x^12 TAX ; save bottom of x^12 ASL ; left shift two more ASL ; watch the carry flag EOR crchi ; bottom of x^5 ($..2.) ; ; alternative ending 1 ; TAY ; save high byte ; TXA ; fetch temp value ; ROL ; bottom of x^12, middle of x^5! ; EOR crclo ; finally update low byte ; STA crchi ; then swap high and low bytes ; STY crclo ; RTS ; 37 bytes, 68 cycles, AXYP undefined ; alternative ending 2 STA crchi ; save high byte TXA ; fetch temp value ROL ; bottom of x^12, middle of x^5! EOR crclo ; finally update low byte LDX crchi ; then swap high and low bytes STA crchi STX crclo RTS ; 40 bytes, 72 cycles, AXP undefined ; Add byte to KERMIT or X.25-style CRC ; This is a straightforward reflection of the CCITT algorithm ; On entry: ; A = byte to add ; crclo = low byte of KERMIT CRC ; crchi = high byte of KERMIT CRC ; (on the first call, crclo and crchi should be set ; according to the algorithm in use) ; On exit: ; crclo,crchi = New KERMIT CRC with byte added ; On exit, when using alternative ending 1: ; S,V,B,D,I = preserved (subject to interrupts) ; A,X,Y,N,Z,C = undefined ; On exit, when using alternative ending 2: ; Y,S,V,B,D,I = preserved (subject to interrupts) ; A,X,N,Z,C = undefined ; Relocatable, non-re-entrant kermit_f: ; add byte to KERMIT CRC EOR crclo ; A contained the data STA crclo ; XOR into low byte ASL ; create top of x^12 term ASL ASL ASL TAX ; save it LSR ; then make top of x^5 term EOR crchi ; XOR into high byte STA crchi TXA ; restore x^12 EOR crclo ; apply it to low byte EOR crclo LSR ; create bottom of x^12 LSR ; (with feedback from top) LSR ; watch the carry flag TAX ; save it LSR ; make bottom of x^5 LSR EOR crclo ; apply to low byte ; ; alternative ending 1 ; TAY ; save in Y ; TXA ; restore bottom of x^12 ; ROR ; rotate in middle of x^5 ; EOR crchi ; apply to high byte ; STA crclo ; and swap bytes ; STY crchi ; RTS ; 37 bytes, 68 cycles, AXYP undefined ; alternative ending 2 STA crclo ; save low byte TXA ; restore bottom of x^12 ROR ; rotate in middle of x^5 EOR crchi ; apply to high byte LDX crclo ; pick up low byte STA crclo ; and swap bytes STX crchi RTS ; 40 bytes, 72 cycles, AXP undefined ; Add byte to ARC or MODBUS-style CRC ; On entry: ; A = byte to add ; crclo = low byte of ARC-style CRC ; crchi = high byte of ARC-style CRC ; (on the first call, crclo and crchi should = $00, $00) ; temp = unused byte of memory ; On exit: ; crclo,crchi = New ARC-style CRC with byte added ; Y,S,V,B,D,I = preserved (subject to interrupts) ; A,X,N,Z,C,temp = undefined ; Relocatable, non-re-entrant crc16_arc_f: ; add byte to ARC-style CRC EOR crclo STA crclo ; parity_adc (thanks bogax at 6502.org) ASL EOR crclo AND #$AA ADC #$66 ; C has no effect AND #$88 ADC #$78 ASL ; C contains even parity LDA #0 ROR crclo ; push parity in b7 ROR STA temp ; save crclo B0 LDA crclo LSR ROR temp ; save crclo B1 EOR crclo ; 'blur' crclo TAX ; keep final crchi ASL ; C contains parity again LDA temp ; reload mask ROL ; parity in b0, B0 in b7 EOR temp ; add B0 in b6, B1 in b7 EOR crchi ; apply completed mask STA crclo ; and store, swapping bytes STX crchi RTS ; 44 bytes, 73 cycles, AXP undefined ; other parity algorithms can be used ; their speed and size vary greatly data: .DB $31,$32,$33,$34,$35,$36,$37,$38 .DB $39 lendata = *-data .END
[ Top of page ]
This appendix contained parity calculators for the ARC algorithm, and has been removed.
[ Top of page ]
Sample 6502 assembly code to implement the "CRC-8" algorithm in constant
time, without the use of lookup tables.
*= $0070 crc: .DB $00 *= $1900 .START * test: CLD LDY #$00 ; init value STY crc byloop: LDA data,Y JSR crc8_f INY CPY #lendata BMI byloop BRK ; result is in $0070 ; Add byte to CRC-8 ; On entry: ; A = byte to add ; crc = CRC-8 value ; (on the first call, crc should = $00) ; On exit: ; crc = New CRC-8 value with byte added ; X,Y,S,V,B,D,I = preserved (subject to interrupts) ; A,N,Z,C,temp = undefined ; Relocatable, non-re-entrant crc8_f: ; add byte to CRC-8 EOR crc ; A contained the data STA crc ; XOR it with the byte ASL ; current contents of A will become x^2 term BCC crc8_f_apply_1 ; if b7 = 1 EOR #$07 ; then apply polynomial with feedback crc8_f_apply_1: BCC *+2 ; ballast to ensure constant time EOR crc ; apply x^1 ASL ; C contains b7 ^ b6 BCC crc8_f_apply_2 EOR #$07 crc8_f_apply_2: BCC *+2 ; ballast to ensure constant time EOR crc ; apply unity term STA crc ; save result RTS ; 25 bytes, 37 cycles, AP undefined data: .DB $31,$32,$33,$34,$35,$36,$37,$38 .DB $39 lendata = *-data .END
[ Top of page ]
Sample ARM assembly code to implement the nine major 16-bit algorithms in constant time, without the use of lookup tables. Thanks to Viktor Gottschald for correspondence and a 15-instruction routine for ARC/Modbus, leading to this updated version.
.crc16_arc_test
STMDB (sp)!,{R1-R4,R8,R9,lr} \preserve registers
ADR R8,data \set pointer to string
MOV R9,#dataend - data \set counter to string length
MOV R0,#0 \set Init = 0 (ZMODEM, KERMIT, ARC)
\ MOV R0,#&FF00 \or set Init = 0xffff (others)
\ ORR R0,R0,#&FF
MOV R2,#&FF000000 \R2 = 0xff0000ff
ORR R2,R2,#&FF
MOV R3,#&A000000A \R3 = 0xa006000a
ORR R3,R3,#&60000
MVN R4,#&2D00 \R4 = 0x2d00d2ff
EOR R4,R4,R4,LSL #16
.crc16_arc_test_loop
LDRB R1,[R8],#1 \get character from string
BL crc16_citt_f \update CRC using CITT
SUBS R9,R9,#1 \decrement counter
BNE crc16_arc_test_loop \loop until end of string
AND R0,R0,R2,ROR #24 \clear high bytes of result
\ EOR R0,R0,R2,ROR #24 \complement it for I-CODE/X.25/USB
ADDS R0,R0,#0 \BASIC V/RISC OS needs flags clear
LDMIA (sp)!,{R1-R4,R8,R9,pc} \at end restore regs and return CRC
\fast CITT / ZMODEM engine
\on entry R0=old CRC, R1=data byte,
\R2 = 0xff0000ff
\on exit R0=new CRC (bits 0..15),
\R0 bits 16..31 undefined,
\R1 undefined
.crc16_citt_f
EOR R0,R0,R1,LSL #8 \merge new byte into top byte
AND R0,R2,R0,ROR #8 \old CRC to top and bottom byte
EOR R1,R0,R0,LSR #4 \'blur' low byte in new register
EOR R0,R0,R1,LSL #21 \apply feedback to polynomial
EOR R0,R0,R1,LSL #12 \and again
EOR R0,R0,R0,LSR #16 \fold top half of word to bottom
MOV pc,lr \return; 6 (7) instructions
\fast KERMIT / X.25 engine
\on entry R0=old CRC, R1=data byte,
\R2 = 0xff0000ff
\on exit R0=new CRC (bits 0..15),
\R0 bits 16..31 undefined,
\R1 undefined
.kermit_f
AND R0,R2,R0,ROR #8 \merge new byte into bottom byte
EOR R0,R0,R1,LSL #24 \old CRC to top and bottom byte
EOR R1,R0,R0,LSL #4 \'blur' low byte in new register
EOR R0,R0,R1,LSR #21 \apply feedback to polynomial
EOR R0,R0,R1,LSR #12 \and again
EOR R0,R0,R0,LSR #16 \fold top half of word to bottom
MOV pc,lr \return; 6 (7) instructions
\fast ARC / MODBUS engine
\on entry R0=old CRC, R1=data byte,
\R2 = 0xff0000ff, R3 = 0xa006000a,
\R4 & 0x7f807f80 = 0x2d005280
\on exit R0=new CRC (bits 0..15),
\R0 bits 16..31 undefined,
\R1 undefined
.crc16_arc_f
AND R0,R2,R0,ROR #8 \old CRC to top and bottom byte
EOR R0,R0,R1,LSL #24 \merge new byte into top byte
EOR R1,R0,R0,LSR #1 \'blur' top byte in new register
EOR R0,R0,R1,LSR #17 \merge blurred byte into new top
ORR R1,R3,R1,ROR #26 \and rotate it and mask with 1s
ADDS R1,R1,R4,ROR R1 \put parity into N using table
EORMI R0,R0,R3,LSR #3 \if odd parity invert three bits
MOV pc,lr \return; 7 (8) instructions
.data
EQUS "123456789"
.dataend
ALIGN
[ Top of page ]
A demonstration of selected 16-bit algorithms in Python. Reproduced by kind permission of James Luscher.
#!/usr/bin/env Python
def CharToBinary(char):
n = ord(char)
bits = ''
for y in range(8):
if ((n & (1 << y)) == 0):
bits = '0' + bits
else:
bits = '1' + bits
return bits
def StringToBinary(message, reflect):
bytes = ''
print 'message = "' + message + '"'
if reflect:
print ' binary hex reflected'
else:
print ' binary hex'
for x in range(len(message)):
char = message[x:x+1]
bits = CharToBinary(char)
rbits = Reflect(bits)
if reflect:
print "char = '"+char+"' -> "+bits+" (0x"+BinaryToHex(bits)+') <=> '+rbits+' (0x'+BinaryToHex(rbits)+')'
bits = rbits
else:
print "char = '"+char+"' -> "+bits+" (0x"+BinaryToHex(bits)+')'
if bytes == '':
bytes = bytes + '{' + bits
else:
bytes = bytes + ',' + bits
bytes = bytes + '}'
if len(bytes) > 57:
print "bytes = "+bytes[0:57]+' ...'
else:
print "bytes = " + bytes
return bytes
def XOR(s1,s2):
if len(s1) != len(s2):
print "XOR(): ERROR, unequal length strings: ["+s1+"]["+s2+"]"
return
r = ''
for i in range(len(s1)):
if (s1[i:i+1] == '1' and s2[i:i+1] == '1'):
r = r + '0'
elif(s1[i:i+1] == '0' and s2[i:i+1] == '0'):
r = r + '0'
else:
r = r + '1'
return r
def Reflect(s):
r = ''
for i in range(len(s)):
r = s[i:i+1] + r
return r
def NOT(s):
r = ''
for i in range(len(s)):
if (s[i:i+1] == '1'):
r = r + '0'
else:
r = r + '1'
return r
def HexToBinary(n):
h = ''
for inx in range(16):
if n & 0x1 == 0x1:
h = '1' + h
else:
h = '0' + h
n = n / 2
return h
def BinaryToHex(s):
h = ''
for x in range(len(s)/4):
n = 0
for y in range(4):
n = (n * 2)
if s[0:1] == '1':
n = n + 1
s = s[1:]
if n <= 9:
h = h + (chr(ord('0') + n ))
else:
h = h + (chr(ord('a') + (n - 10)))
return h
def MessageStrip(M):
while len(M) > 0 and M[0:1] != '0' and M[0:1] != '1':
M = M[1:]
return M
#============================================
# author: James Luscher (owns all errors ;-)
# <jluscher-gmail-com>
# corrections: Greg Cook (thanks Greg!)
# copyright: 2007 James Luscher
# licensed under: GNU General Public License
# details at http://www.gnu.org/copyleft/
#
# This program was written for self-education.
# I hope others may find it informative also.
#=============================================
def crc(poly, register, reflect, message, invert):
#-----------------------------------
# CRC-16 polynomial is 0x8005
# CRC-16/CCITT polynomial is 0x1021
P = HexToBinary(poly)
#-----------------------------------
# register (initial value)
R = HexToBinary(register)
#-----------------------------------
# reflect in/out ??
if reflect != 0:
print "reflect = True"
else:
print "reflect = False"
#-----------------------------------
# M -> message (ASCII string)
M = StringToBinary(message, reflect)
length = len(M)
print
if len(M) > 53:
print "message = "+M[0:53]+' ...'
else:
print "message = "+M
#-----------------------------------
print "register = "+R
print "polynomial= "+P+" (0x" + BinaryToHex(P) + ')'
print
M = MessageStrip(M)
print " register message..."
print " ---------------- -------..."
if len(M) > 40:
print " "+R+' '+M[0:40]+' ...'
elif len(M) > 0:
print " "+R+' '+M
else:
print " "+R
while len(M)>0:
Rc = R[0:1]
Mc = M[0:1]
C = XOR(Rc,Mc)
R = R[1:]+'0'
M = M[1:]
M = MessageStrip(M)
if len(M) > 40:
print " ("+Rc+") < "+R+' ('+Mc+') < '+M[0:40]+' ...'
else:
print " ("+Rc+") < "+R+' ('+Mc+') < '+M
if C == '1':
print "["+Rc+'^'+Mc+"]=> "+P+" (xor by 0x" + BinaryToHex(P) + ')'
print " "+('-' * 16 )
R = XOR(R, P)
print " "+R+" (0x" + BinaryToHex(R) + ')'
print
print
if reflect:
R = Reflect(R)
print " reflected"
print "<=> => " + R
if invert != 0:
R = NOT(R)
print "NOT => " + R
print " " + R + " = CRC" + " (0x" + BinaryToHex(R) + ")"
def d1():
crcdemo(0x1021, 0x0000, 1, 0)
print
print "demo: example: poly reg r i expect"
print "----- -------------- ----------------------------- ------"
print "d1() KERMIT: crcdemo(0x1021, 0x0000, 1, 0) // 0x2189"
print "=============================================================="
crcdemo_help()
def d2():
crcdemo(0x8408, 0x0000, 1, 0)
print
print "demo: example: poly reg r i expect"
print "----- -------------- ----------------------------- ------"
print "d2() X-KERMIT: crcdemo(0x8408, 0x0000, 1, 0) // 0x0c73"
print "=============================================================="
crcdemo_help()
def d3():
crcdemo(0x1021, 0xffff, 1, 1)
print
print "demo: example: poly reg r i expect"
print "----- -------------- ----------------------------- ------"
print "d3() X-25: crcdemo(0x1021, 0xffff, 1, 1) // 0x906e"
print "=============================================================="
crcdemo_help()
def d4():
crcdemo(0x8005, 0x0000, 1, 0)
print
print "demo: example: poly reg r i expect"
print "----- -------------- ----------------------------- ------"
print "d4() CRC-16/ARC: crcdemo(0x8005, 0x0000, 1, 0) // 0xbb3d"
print "=============================================================="
crcdemo_help()
def d5():
crcdemo(0x1021, 0xffff, 0, 0)
print
print "demo: example: poly reg r i expect"
print "----- -------------- ----------------------------- ------"
print "d5() CRC-16/CCITT: crcdemo(0x1021, 0xffff, 0, 0) // 0x29b1"
print "=============================================================="
crcdemo_help()
def d6():
crcdemo(0x1021, 0x0000, 0, 0)
print
print "demo: example: poly reg r i expect"
print "----- -------------- ----------------------------- ------"
print "d6() CRC-16/XMODEM: crcdemo(0x1021, 0x0000, 0, 0) // 0x31c3"
print "=============================================================="
crcdemo_help()
def crcdemo_help():
print """
crcdemo()
- show the detailed calculation for various kinds of 16 bit CRCs
- ALL demo examples applied to the canonical message "123456789"
- use function 'crc()' to apply to your own message string.
crcdemo(poly, register, reflect, append, invert)
poly <- hex value for (truncated) generator polynomial
register <- hex initial value for remainder register
reflect <- 0 == don't reflect message bytes & output CRC
invert <- 0 == don't invert remainder after calculation
demo: examples: poly reg r i expect
----- -------------- ----------------------------- ------
d1() KERMIT: crcdemo(0x1021, 0x0000, 1, 0) // 0x2189
d2() X-KERMIT: crcdemo(0x8408, 0x0000, 1, 0) // 0x0c73
d3() X-25: crcdemo(0x1021, 0xffff, 1, 1) // 0x906e
d4() CRC-16/ARC: crcdemo(0x8005, 0x0000, 1, 0) // 0xbb3d
d5() CRC-16/CCITT: crcdemo(0x1021, 0xffff, 0, 0) // 0x29b1
d6() CRC-16/XMODEM: crcdemo(0x1021, 0x0000, 0, 0) // 0x31c3
"""
def crcdemo(poly, register, reflect, invert):
crc(poly, register, reflect, '123456789', invert)
return
crcdemo_help()
// To run a demonstration of each algorithm, uncomment any of the next 6 lines. - GJC
// d1()
// d2()
// d3()
// d4()
// d5()
// d6()
// End of crc16demo.py
[ Top of page ]
Based on research by Vivek Rajan
Interpretation of the three CRC-11 samples in the Bosch E-Ray Application Note 002.
See Section 4 of the FlexRay Protocol Specification for a definition of the FlexRay frame format and the Header CRC Covered Area.
In section 4.4.3.1 (pp. 26-7) of the Application Note is code for "Configuration of Coldstart Node A". It includes the lines
write32bit(WRHS1, 0x27000001); // transmit buffer, frame ID = 1 write32bit(WRHS2, 0x0008011B); // payload length = 8 two-byte words
As a coldstart node, according to section 4.4.3.1 (p.15) the Sync and Startup frame indicators are set. This corresponds to a Header CRC Covered Area of 11 00000000001 0001000 (0xc0088) and a Header CRC of 001 0001 1011 (0x11b).
In section 4.4.3.2 (pp. 28-9) of the Application Note is code for "Configuration of Coldstart Node B". It includes the lines
write32bit(WRHS1, 0x27000002); // transmit buffer, frame ID = 2 write32bit(WRHS2, 0x00080304); // payload length = 8 two-byte words
As a coldstart node, according to section 4.4.3.1 (p.15) the Sync and Startup frame indicators are set. This corresponds to a Header CRC Covered Area of 11 00000000010 0001000 (0xc0108) and a Header CRC of 011 0000 0100 (0x304).
In section 4.4.3.3 (pp. 30-1) of the Application Note is code for "Configuration of Integrating Node C". It includes the lines
write32bit(WRHS1, 0x27000003); // transmit buffer, frame ID = 3 write32bit(WRHS2, 0x000805D2); // payload length = 8 two-byte words
A cursory inspection does not reveal proof of whether the Sync or Startup frame indicators are set. This corresponds to a Header CRC Covered Area of ?? 00000000011 0001000 (0x?0188) and a Header CRC of 101 1101 0010 (0x5d2).
By exhaustive search the bit string 00 00000000011 0001000 (0x00188) is found to match the reported CRC. This gives us 511/512 confidence in Example 3, compared to 2047/2048 for the first two examples.
[ Top of page ]
Performing the Atom checksum algorithm with a Rocksoft™ Model implementation.
$ wc -c afloat.rom 4096 afloat.rom $ dd if=afloat.rom of=afloat.rom.diminished bs=1 count=4094 4094+0 records in 4094+0 records out $ dd if=afloat.rom bs=1 skip=4094 | hexdump -x 2+0 records in 2+0 records out 00000000 605f 00000002Note: hexdump prints little-endian words. The second-to-last byte of this file is
0x5F and the last byte is 0x60.
$ tomtorfs afloat.rom.diminished 16 002D 1 0000 0000 E50A
0xE50A ^ 0x605F == 0x85550x8555 == %1000010101010101 ==> %1010101010100001 == 0xAAA1This matches the 'signature' given for Atom Floating Basic in Splitting the Atom. For the Rocksoft™ check string:
$ echo -en '1234567' | tomtorfs /dev/stdin 16 002D 1 0000 0000 F5F2
0xF5F2 ^ 0x3938 == 0xCCCA0xCCCA == %1100110011001010 ==> %0101001100110011 == 0x5333[ Top of page ]
Sample 8080/Z80 assembly code to implement the nine major 16-bit algorithms in constant time, without the use of lookup tables. One of the routines is for faster calculation on a Z80 only.
; Main loop, for 8080/Z80 ORG 100H Start: LD SP,1000H LD HL,0 ; for ZMODEM, KERMIT and ARC ; LD HL,FFFFH ; for CCITT, X.25 and USB LD DE,data ; set pointer to test string LD C,dataend-data ; set counter to string length tloop: LD A,(DE) ; get character of string INC DE ; increment pointer PUSH BC ; save counter CALL crc16_citt_f ; do CRC on character POP BC ; restore counter DEC C ; decrement it JP NZ,tloop ; and loop until string done ; LD A,H ; complement result ; CPL ; for CCITT, X.25 and USB ; LD H,A ; LD A,L ; CPL ; LD L,A HALT data: DEFB "123456789" ; test string dataend:NOP ; label for calculating length ; CRC-16/CITT for 8080/Z80 ; On entry HL = old CRC, A = byte ; On exit HL = new CRC, A,B,C undefined ; Ts M/code 8080 assembly crc16_citt_f: XOR H ; 4 AC XRA H LD B,A ; 4 47 MOV B,A LD C,L ; 4 4D MOV C,L RRCA ; 4 0F RRC RRCA ; 4 0F RRC RRCA ; 4 0F RRC RRCA ; 4 0F RRC LD L,A ; 4 6F MOV L,A AND 0FH ; 7 E6 0F ANI 0FH LD H,A ; 4 67 MOV H,A XOR B ; 4 A8 XRA B LD B,A ; 4 47 MOV B,A XOR L ; 4 AD XRA L AND F0H ; 7 E6 F0 ANI F0H LD L,A ; 4 6F MOV L,A XOR C ; 4 A9 XRA C ADD HL,HL ; 11 29 DAD H XOR H ; 4 AC XRA H LD H,A ; 4 67 MOV H,A LD A,L ; 4 7D MOV A,L XOR B ; 4 A8 XRA B LD L,A ; 4 6F MOV L,A RET ; 10 C9 RET ; 115 T-states, 25 bytes ; CRC-16/CITT for 8080/Z80 ; On entry HL = old CRC, A = byte ; On exit HL = new CRC, A,B undefined ; Ts M/code 8080 assembly crc16_citt_c_f XOR H ; 4 AC XRA H LD H,A ; 4 67 MOV H,A AND F0H ; 7 E6 F0 ANI F0H RRCA ; 4 0F RRC RRCA ; 4 0F RRC RRCA ; 4 0F RRC RRCA ; 4 0F RRC XOR H ; 4 AC XRA H LD H,A ; 4 67 MOV H,A RRCA ; 4 0F RRC RRCA ; 4 0F RRC RRCA ; 4 0F RRC LD B,A ; 4 47 MOV B,A AND E0H ; 7 E6 E0 ANI E0H XOR H ; 4 AC XRA H LD H,A ; 4 67 MOV H,A LD A,B ; 4 78 MOV A,B AND 1FH ; 7 E6 1F ANI 1FH XOR L ; 4 AD XRA L LD L,A ; 4 6F MOV L,A LD A,B ; 4 78 MOV A,B RRCA ; 4 0F RRC AND F0H ; 7 E6 F0 ANI F0H XOR L ; 4 AD XRA L LD L,H ; 4 6C MOV L,H LD H,A ; 4 67 MOV H,A RET ; 10 C9 RET ; 126 T-states, 31 bytes ; KERMIT for 8080/Z80 ; On entry HL = old CRC, A = byte ; On exit HL = new CRC, A,B undefined ; Ts M/code 8080 assembly kermit_f: XOR L ; 4 AD XRA L LD L,A ; 4 6F MOV L,A ADD A,A ; 4 87 ADD A ADD A,A ; 4 87 ADD A ADD A,A ; 4 87 ADD A ADD A,A ; 4 87 ADD A XOR L ; 4 AD XRA L LD L,A ; 4 6F MOV L,A RLCA ; 4 07 RLC RLCA ; 4 07 RLC RLCA ; 4 07 RLC LD B,A ; 4 47 MOV B,A AND 07H ; 7 E6 07 ANI 07H XOR L ; 4 AD XRA L LD L,A ; 4 6F MOV L,A LD A,B ; 4 78 MOV A,B AND F8H ; 7 E6 F8 ANI F8H XOR H ; 4 AC XRA H LD H,A ; 4 67 MOV H,A LD A,B ; 4 78 MOV A,B RLCA ; 4 07 RLC AND 0FH ; 7 E6 0F ANI 0FH XOR H ; 4 AC XRA H LD H,L ; 4 65 MOV H,L LD L,A ; 4 6F MOV L,A RET ; 10 C9 RET ; 119 T-states, 29 bytes ; CRC-16/ARC for 8080/Z80 ; On entry HL = old CRC, A = byte ; On exit HL = new CRC, A,B undefined ; Ts M/code 8080 assembly crc16_arc_f: XOR L ; 4 AD XRA L LD L,A ; 4 6F MOV L,A RRCA ; 4 0F RRC RRCA ; 4 0F RRC ;AND A ; needed if running in ZINT / no ballast JP PE,blur ; 10 EA nn nn JPE blur SCF ; 0 37 STC blur: JP PO,blur1 ; 10 E2 nn nn JPO blur1 AND A ; 4 A7 ANA A blur1: RRA ; 4 1F RAR AND E0H ; 7 E6 E0 ANI E0H RLA ; 4 17 RAL LD B,A ; 4 47 MOV B,A RLA ; 4 17 RAL XOR B ; 4 A8 XRA B XOR H ; 4 AC XRA H LD B,A ; 4 47 MOV B,A XOR H ; 4 AC XRA H RRA ; 4 1F RAR LD A,L ; 4 7D MOV A,L RRA ; 4 1F RAR LD L,A ; 4 6F MOV L,A AND A ; 4 A7 ANA A RRA ; 4 1F RAR XOR L ; 4 AD XRA L LD L,B ; 4 68 MOV L,B LD H,A ; 4 67 MOV H,A RET ; 10 C9 RET ; 125 T-states, 31 bytes ; CRC-16/ARC for Z80 only ; On entry HL = old CRC, A = byte ; On exit HL = new CRC, A,B undefined ; Ts M/code crc16_arc_z80_f: LD B,0 ; 7 06 00 XOR L ; 4 AD ;AND A ; needed if running in ZINT JP PE,blur80 ; 10 EA nn nn SCF ; 0 37 blur80: JP PO,blur81 ; 10 E2 nn nn NOP ; 4 00 blur81: RRA ; 4 1F RR B ; 8 CB 18 LD L,A ; 4 6F SRL A ; 8 CB 3F RR B ; 8 CB 18 XOR L ; 4 AD LD L,A ; 4 6F ADD A,A ; 4 87 LD A,B ; 4 78 RLA ; 4 17 XOR B ; 4 A8 XOR H ; 4 AC LD H,L ; 4 65 LD L,A ; 4 6F RET ; 10 C9 ; 113 T-states, 29 bytes ENDGreg Cook, debounce@yahoo.co.uk
[ Top of page ]