How to generate a CCITT-16 CRC checksum?
Sadien Ferguson
result of 0x1D0F (hex) 0b0001101100001111 (bin) as specified by TIA/EIA
466-A(Group3 fax protocols).
I want to use software generated CRCs and check sequences via Atmels
AT90S8515 embedded uC. Atmel's application note (AVR235) on CRC generation
does work, however it's based on a "return of zero" no error result.
I've tried presetting the generator registers to all 1's with the one's
complement as specified for CCITT-16. I even fiddled with bit/byte
reflections. Still I cant get this !@#%$$% . . . '0x1D0F' (hex)
remainder.
I understand that this is complicated CRC (modulo2) stuff and I understand
the concept. But, if anyone has ever tried to figured out the explanation of
the Frame Check Sequence (CRC-16) given in TIA/EIA 466-A (Group3 fax
protocols) you would understand my dilemma . . .OK frustration.
By the way, here is a truly informative paper on 'CRC' explained with the
programmer in mind.
A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS INDEX V3.00
http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
Code for ""AVR235: CRC check of Program Memory
http://www.atmel.com/atmel/products/prod180.htm#avr235.asm
Any help is greatly appreciated.
Sadien Ferguson, a AVR lover :)
sy...@mediaone.net
Sadien Ferguson
John Larkin
Hi,
I have a PowerBasic subroutine to generate the CRC-16 of a list of
16-bit integers. It may help(?). I'd post it here, but by newsreader
trashes the alignment so much that it becomes unreadable.
I can mail it to you.
John
jjlarkin (at) highlandtechnology (dot) com
-----------------
"If anybody ever marries you, it will be for the pleasure
of hearing you talk piffle," said Harriet, severely.
Iain McCracken
>
> I'm trying to figure out exactly how one derives a CCITT-16
> checksum result of 0x1D0F (hex) 0b0001101100001111 (bin) as specified
> by TIA/EIA 466-A(Group3 fax protocols).
>
> sy...@mediaone.net
This is the same as PPP in HDLC framing.
To generate the checksum:
- You initialize the CRC to 0xFFFF, then calculate it for the data.
Take the one's complement of the result and append it to the data.
To check the checksum in incoming frames:
- As when generating it, initialize to 0xFFFF, and calculate the CRC of
the data *and* the appended FCS. The resulting calculated CRC should be
0x1D0F or 0xF0B8, depending on which way around you calculated it.
Check out Internet RFC 1549 for some source code (in C) for exactly what
you want to do. (I think).
http://www.isi.edu/in-notes/rfc-retrieval.txt for a list of FTP/Web
sites that you can download the document from (it's a 36Kb text file).
Hope this helps.
--Iain.
Rich Webb
>I'm trying to figure out exactly how one derives a CCITT-16 checksum
>result of 0x1D0F (hex) 0b0001101100001111 (bin) as specified by TIA/EIA
>466-A(Group3 fax protocols).
*THE* reference site for programmers looking to understand and write CRC
algorithms is:
http://www.ross.net/crc/crcpaper.html
Look for the paper "A Painless Guide to CRC Error Detection Algorithms"
by Ross Williams. It explains how they work, gives operating parameters
for several standard CRCs, and includes working portable C source for a
model CRC implementation.
The model code is slow since it's not hard-wired for a particular
endian-ness or CRC flavor and is not table-driven, but this enables it
to be used with many different CRC divisors and reflection options. VERY
handy to be able to check the results of that tight assembly code
against a known good result.
The paper does include a table generation function and guidance on how
to implement a tight, fast table-driven CRC engine.
--
Rich Webb Norfolk, VA
raw...@erols.com
David Empson
> I'm trying to figure out exactly how one derives a CCITT-16 checksum
> result of 0x1D0F (hex) 0b0001101100001111 (bin) as specified by TIA/EIA
> 466-A(Group3 fax protocols).
>
> I want to use software generated CRCs and check sequences via Atmels
> AT90S8515 embedded uC. Atmel's application note (AVR235) on CRC generation
> does work, however it's based on a "return of zero" no error result.
This is just a case of different initialization and transmission rules.
If you preset the CRC generator to 0xFFFF and complement it before
transmission, then include the FCS bytes in the CRC calculation at the
receive end, you should get a result of 0x1D0F.
This assumes you are looking at the bits in the correct order. Taking
SDLC/HDLC as an example: the CRC is calculated on each bit of the frame
in transmission order (ignoring inserted "stuff bits"), then the
remainder is transmitted MSB first.
You can vary the algorithm, e.g. by shifting the CRC generator in the
opposite direction, and end up with different results. For example,
some variations will produce a result of 0xF0B8, which is the mirror
image of 0x1D0F.
Here is a simple example: transmit a frame containing two data bytes
which match your initial CRC value. This always results in a reaminder
of zero, which is complemented and transmitted as one bits. The
transmitted frame looks like this (omitting stuff bits):
FLAG 11111111 11111111 11111111 11111111 FLAG
------data------- -------FCS-------
MSB LSB
The receiving end includes the FCS in its calculation. Stepping
through:
Data CRC
11111111 11111111 (Initial value)
1 11111111 11111110
1 11111111 11111100
(repeat for 13 bits)
1 00000000 00000000 (last data bit)
1 00010000 00100001 (FCS bit 15)
1 00110000 01100011
1 01110000 11100111
1 11110001 11101111
1 11100011 11011110
1 11000111 10111100
1 10001111 01111000
1 00011110 11110000
1 00101101 11000001 (FCS bit 7)
1 01001011 10100011
1 10000111 01100111
1 00001110 11001110
1 00001101 10111101
1 00001011 01011011
1 00000110 10010111
1 00011101 00001111 (FCS bit 0)
Bingo: the result is 0x1D0F.
The key points (for HDLC):
1. The CRC is preset to 0xFFFF before calculation at both transmitter
and receiver.
2. The generator polynomial is 0x1021 (with an implied 16th bit of 1).
3. Data bits are processed in order of transmission.
4. Extraneous data link framing bits (FLAG, bit stuffing, start/stop
bits, parity, etc.) are not included in the CRC calculation.
5. The CRC is calculated by shifting left for each bit.
6. The CRC remainder (FCS) is complemented and transmitted MSB first.
7. The receiver includes the FCS in its CRC calculation.
8. The receiver should calculate a remainder of 0x1D0F.
For other protocols, there may be minor variations. For example, XModem
and YModem use the same generator polynomial, but the data bytes are
processed MSB first, and the CRC is transmitted high byte first. The
remainder is still 0x1D0F.
The following function is a commonly used "parallel" version of the CRC
calculation as performed by XModem/YModem. This is usually faster than
doing a bit-at-a-time calculation. It isn't as fast as a table lookup,
but saves a lot of space in an embedded processor. It is
straightforward to derive an optimised version of this in assembly
language. (I've implemented this on several processors, including the
6502, Z-80, 6301 and ST9.)
unsigned short docrc_xmodem(unsigned short crc, unsigned char data)
{
crc = ((crc & 0xFF00) >> 8) | ((crc & 0x00FF) << 8);
crc ^= data;
crc ^= (crc & 0x00F0) >> 4;
crc ^= (crc & 0x000F) << 12;
crc ^= (crc & 0x00FF) << 5;
return crc;
}
Another variation is Async HDLC. If you are calculating the CRC in
software and transmitting through a normal UART, then you need to vary
the algorithm slightly so that the FCS bits are transmitted in the
correct order (unless you want to reverse all 16 bits of the FCS before
transmission). The UART always transmits LSB first, so you simply
reverse the entire CRC algorithm: reverse the polynomial (0x8408), shift
right instead of left, transmit the CRC LSB first, and check for a
remainder of 0xF0B8. The data bytes are still processed LSB first.
Here is the "parallel" version of the algorithm for the reversed
CRC-CCITT calculation. As you can see, it just reverses all the
operations from the previous function.
unsigned short docrc_hdlc(unsigned short crc, unsigned char data)
{
crc ^= data;
crc = ((crc & 0xFF00) >> 8) | ((crc & 0x00FF) << 8);
crc ^= (crc & 0x0F00) << 4;
crc ^= (crc & 0xF000) >> 12;
crc ^= (crc & 0xFF00) >> 5;
return crc;
}
Some protocols specify that the CRC be preset to zero and transmitted
without inversion. In this case, the receiver should get a remainder of
zero.
--
David Empson
dem...@actrix.gen.nz
Snail mail: P O Box 27-103, Wellington, New Zealand
mi...@rrrmove.mycal.net
> I'm trying to figure out exactly how one derives a CCITT-16 checksum
> result of 0x1D0F (hex) 0b0001101100001111 (bin) as specified by TIA/EIA
> 466-A(Group3 fax protocols).
> I want to use software generated CRCs and check sequences via Atmels
> AT90S8515 embedded uC. Atmel's application note (AVR235) on CRC generation
> does work, however it's based on a "return of zero" no error result.
> I've tried presetting the generator registers to all 1's with the one's
> complement as specified for CCITT-16. I even fiddled with bit/byte
> reflections. Still I cant get this !@#%$$% . . . '0x1D0F' (hex)
> remainder.
Here is a CRC routine. It is part of my PPP implementation that I did
on the AVR. Set Z to the 16 bit crc value and R16 to the char to crc
before each call.
mike
;------------------------------------------------------------------------------
; CRC16 routine R16 is char in. Z = crc_l
;
; Distroys R17,R18,R19, preserves R16
;
; data = data ^ (byte) crc
; data = data ^ (data << 4)
; crc = (crc >> 8) ^ (data << 8) ^ (data <<3) ^ (data >> 4)
;------------------------------------------------------------------------------
crcadd:
push R16
ld R17,Z ; crc_l = Z
eor R16,R17 ; data = data ^ (byte) crc
mov R17,R16 ; data = data ^ (data << 4)
swap R17
mov R18,R17
andi R17,0xf0
eor R16,R17
mov R17,R16
swap R17
mov R18,R17
andi R17, 0x0f ; data >> 4
andi R18, 0xf0 ; data << 4
mov R19,R17
lsr R17 ; = <<3 h
ror R18 ; = <<3 l
eor R16,R17 ; (data << 8) ^ ((data << 3)h)
eor R19,R18 ; (data >> 4) ^ ((data << 3)l) ^
ldd R18,Z+1 ; load crc_h
eor R19,R18 ; (crc >> 8)
st Z,R19 ; store crc_l
std Z+1,R16 ; store crc_h
pop R16
ret
Donald Gillies
>The paper does include a table generation function and guidance on how
>to implement a tight, fast table-driven CRC engine.
I take issue with the idea that "CRC-16" is *ever* a FAST algorithm.
CCITT CRC-16 was intended for hardware implementation. In software,
if you look at the fundamental operations of this algorithm, it takes
at least 5 memory fetches to CRC a 32-bit word. There is absolutely
no parallelism in this algorithm, because each operator is lock-step
sequential with the other operators, especially the byte-table memory
fetches. CCITTT CRC-16 is a recipe for disaster on a superscalar
processor.
You should avoid this CRC if you have the design freedom to do so. I
have hand-tuned table-lookup versions of this algorithm for both SPARC
and 68060, and the net result was always : the algorithm is severely
limited by the memory bus and random-access to the table algorithm.
If you cut 3 instructions off the CRC-16 algorithm and shorten the
code by 25%, in the end the algorithm runs NO FASTER because the table
lookups are such a pig with the memory bus.
You'd be far better off with fletcher's checksum or perhaps even the
IP checksum than with CRC-16. See Internet RFC-1146 for the
definition of fletcher's checksum. These other checksums run 2x-4x
faster than CCITT CRC-16, and they always will, in software.
- Don
David Brown
single-cycle instructions and very fast. But it is hardly in the league of
68060 and SPARC cpus, and does not suffer from the same sorts of
inefficiencies (I don't mean that the 68060 or the SPARC are, in general,
inefficient - just that a CRC-16 does not utilise the power of these chips).
A CRC-16 check can be implemented very effectively on the AVR. As a
compromise between speed and lookup-table space, when I implemented CRC
algorithms (both 8-bit and 16-bit, and the same would apply to 32-bit), I
used nibble-wide lookups. This way I ran the CRC on 4 bits at a time, but
the lookup table was only 16 bytes/words long - a full 256 word lookup table
is a hefty burden on the AVR's embedded Flash, but faster if you have the
space. I would strongly recommend using assembly rather than C - code using
bit manipulations, shifts and rotations is often far smaller and faster when
hand coded as you have complete control over the carry bit and the types of
shifts, and can use instructions like swap for working with nibbles.
Donald Gillies wrote in message <84thjl$k97$1...@cascade.cs.ubc.ca>...
Donald Gillies
"David Brown" <david....@westcontrol.com> writes:
> I would strongly recommend using assembly rather than C - code using
> bit manipulations, shifts and rotations is often far smaller and
> faster when hand coded as you have complete control over the carry bit
> and the types of shifts, and can use instructions like swap for
> working with nibbles.
I wasn't really criticizing your work on Atmel, which seemed to be
first class. I was criticizing CCITT-16, which is a second class
checksum for computer software implementation.
After hand tuning the C code, and reading many assembly listings
output from the compiler, I got my 68060 checksum loop to be about 11
instructions in the main loop (8-bit lookups). This is only 1 or 2
instructions more than the number of operators in the optimal table
lookup algorithm. For this reduction (of about 3 instructions) there
was *ZERO* reduction in runtime. The problem is the CPU fetch units
from 68060 cache and the fact that about 4 arithmetic operators must
complete sequentially for every table lookup fetch. The sparc
checksum was similar. Cut off 2 instructions, and your net speedup is
zero because the memory bus is saturated by the Von Neumann bottleneck.
The problem is not the computer, nor the lookup table, but the
checksum algorithm itself. The CCITT-16 checksum is simply a rotten
choice for a software protocol checksum. Fancy assembly algorithms or
table lookups can improve it from a rotten choice to a poor choice,
but no computer architecture will ever make it a *good* choice for an
efficient software checksum. CCITT was always intended for hardware
implementation, which is expalins why it is a rotten checksum for
software. IMHO a good software checksum uses 1 bus fetch per word (be
it 8-bit, 16-bit, or 32-bit) on any native hardware.
- Don
Knut Roll-Lund
Yes,
to you microcontroller/processor designers,
give us a CRC instruction...
or an instruction which would help in the CRC algorithm...
It would be greatly appreciated.
Knut Roll-Lund
PS remove 'nospam.' from the reply address
Steve Holle
<sy...@mediaone.net> wrote:
>I'm trying to figure out exactly how one derives a CCITT-16 checksum
>result of 0x1D0F (hex) 0b0001101100001111 (bin) as specified by TIA/EIA
>466-A(Group3 fax protocols).
The January 2000 Issue of Embedded Systems Programming has a good
article on CRC generation in the article "Slow and Steady Never Lost
the Race." The source is available on the www.embedded.com/code.htm
page.