Citadel Forums
Home
Company Information
Information Request
Linux How-to Guides
ADSP 21xx
Digital Signal
Processing
Tutorials
SW Utilities
On-line Order Form
Server Support
Have you found this site useful? Did we save you time? Did we cure your head-ache? Is your hair growing back now?
Please make a donation to help with maintenance.
|
Objective Real-Time Software on the ADSP21XX
Checks and Balances
General
Communication is useless if all the messages become garbled during transmission.
Some kind or error detection and correction scheme usually forms an important
part of any protocol. Programmers usually think of complicated convolutional
codes when the topic of error coding rears its head and it is frequently
seen as a form of black magic. With good reason actually!
If one is not very careful, an error coder easily turns into a data
dependant encryption algorithm, with no known key...
Note that I mentioned error detection before error correction. In most
cases it is sufficient to determine whether a message is good or bad, based
on a simple checksum and then correct it by retransmitting the message
if it is in error. There are a few cases where this retransmission strategy
won't work and checksums alone, won't do the trick.
One case is when the channel is very slow, or acknowledgement of packets
is either impossible or impractical such as in a simplex radio network.
Another example is when a bunch of cards are connected together and information
is broadcasted to all of them at the same time, making an acknowledgement
scheme impractical or very complicated. It is also possible that the channel
is so bad, that a message always becomes corrupted, in which case retransmitting
it won't help. It may in these cases be better to transmit messages with
error coding, to ensure that errors picked up along the way can be corrected
by the receiver without the need for retransmissions. However, even when
error coding is used, checksums are frequently employed as a final check
to ensure that all errors were in fact corrected.
Checksum Algorithms
Which type of checksum should be used? Obviously one would not want to
use a complicated checksum when the probability of having an error is very
low, but without resorting to measurements, which type of code should be
used when?
Here are a few rules of thumb:
-
If data is saved in a very reliable medium such as an EPROM, or transmitted
over a local bus inside a metal enclosure, then a simple modulo 2 sum is
probably sufficient to detect a single bit error. What the heck is a
modulo 2 sum??? That is probably better known as an XOR operation.
It is just a nice way to add numbers together without getting carries.
Sometimes data is added together with the carry added in again at the low
end, or the two's compliment of the sum is used. Statistically, it does
not make any difference though. This type of checksum is so bad, that you
can just as well stick to a simple XOR!
-
If medium length messages up to 1 kilobyte or so have to be transmitted
between physically separated units, a cyclic redundancy check should be
used. In this case, the CRC16 algorithm is in order.
-
If medium to long messages in the order of several kilobytes in length
have to be transmitted over a bad channel, such as a radio link, the CRC32
algorithm should be used.
There is a major caveat with the CRC algorithms. That regards the way the
linear feedback shift register is initialized, that is, whether you start
with all zeroes, or all ones. The IEEE preferred way is to start with all
ones, but the IEEE and ITU (CCITT) seems to differ on this point. So be
warned that knowing which CRC algorithm is used is not enough, you also
need to know how to start!
Modulo 2 Sums
The modulo 2 sum is used very often, because it is simple, not because
it is good. Don't get me wrong though. Most PCs operate without any form
of error detection, except for the error coding algorithms used on the
disk drives themselves. The information passed between the disk drives
and the PC memory is not error checked at all and they nevertheless happen
to work just fine. In this kind of high reliability situation inside a
single metal enclosure, an XOR checksum will serve perfectly well to ensure
piece of mind in an embedded system.
In an embedded system, it is customary to save one or more checksums
in the EPROMs. During power up self test, the processor can recalculate
the checksums to determine whether the code stored is good and if not,
jump to a bootstrap loader and wait for a new download. The problem is
of course that if the code is really very bad, with multiple bit errors,
the processor will probably not be able to run properly and won't be able
to calculate the checksum to begin with! Remember that we are speaking
of a high reliability setup with at most one bit error to be detected.
The XOR sum is very handy for this type of application. If the checksum
is embedded in a block of code and everything is added up, including the
checksum itself, the result should be zero. This means that a bootstrap
loader program can check the integrity of the runtime code, without having
to know what the checksum is!
There are however a few things to watch out for. If an EPROM is erased,
all bits will be turned into ones and the XOR checksum will probably evaluate
to zero. An erased EPROM can even trip up the CRC16 algorithm, while it
is less likely with the CRC32, but can conceivably still happen...
When a checksum has to be added to an EPROM image, the first problem
is that the file should be exactly the right size, after which the checksum
could be calculated and inserted at the end of the file, ready for programming
into an EPROM. Aerospace Software created a few utilities to aid with these
tasks.
Padding the File
The utility PADFILE.EXE will take an EPROM image and pad it out
with FFH values, up to the exact length specified.
for example:
padfile filename.bin 4000
will expand the file to exactly 4000H bytes in size, ready for inserting
the checksum.
Summing it all
The utility ADDSUM.EXE will take an EPROM image, calculate the
modulo 2 sum thereof and replace the last byte of the file therewith. This
is important: It will actually overwrite the last byte of the file, so
first pad the file to the desired size.
for example:
will calculate the modulo 2 sum up to the last byte and then overwrite
the last byte therewith. If you would then modulo 2 add up all the bytes
in the file, the result would be zero.
In practice, I simply insert calls to these two utilities in the build
batch file. If the calculations are run repeatedly on a file, the file
will not change. Therefore, if you have a block of constant data such as
a PLD image, you can perform the padfile and addsum routines every time
you build the target code, the PLD image will stay the same after the first
time.
What is a CRC?
A cyclic redundancy check (CRC) is similar to our trusty modulo 2 sum above.
The difference is that the result is kept in something resembling a linear
feedback shift register (LFSR) and is shifted before an XOR operation is
performed. The result is that every data bit always influences every bit
in the sum in some way or another, thereby creating a better check. A CRC
is also usually quite wide (16 or 32 bits), which results in a smaller
likelyhood of multiple errors cancelling each other out and going undetected.
A CRC is usually described as a polynomial, which since its base is
2, reduces to a binary XOR mask. For example, the CRC16-ITU (formerly CCITT)
polynomial is:
x^16+x^12+x^5+x^0 = 11021H when x = 2
The most significant bit (MSB) denotes the last feedback point when
the LFSR is implemented in hardware and can be ignored for software purposes
(a common cause of confusion). Therefore the XOR mask for CRC16-ITU
is 1021H, when the LFSR is shifted to the left and data is fed in at
the LSB. It is also possible to do the whole thing backwards and work with
a bit reversed mask, while feeding the data in at the MSB of the LFSR.
It amounts to the same thing in the end. You can do it any which way you
find convenient, as long as the data is treated as a continuous stream
of bits in the order received over the transmission line, for compatibility
with hardware CRC generation logic. So be careful that you don't end up
bit reversing every byte of data!
CRC16
The CRC16 is problematic, since there are two commonly used polynomials
for this check, namely 1021 (ITU) or 8005 (standard), when ignoring the
MSBs. Furthermore, the initial value of the LFSR can be either FFFFH (ITU)
or 0000H (standard). The final value is usually inverted before being appended
to the message (not in X-modem though!). It is possible to run the calculation
forwards or backwards (MSB or LSB first). If you have to interface to somebody
elses program on the other end of a transmission line, you may have to
run a few experiments to figure out what is going on. It helps if you have
a short known message to experiment with!
CRC32
The CRC32 is commonly used as an Ethernet standard and is better defined,
but it also has a couple of funnies. First of all, the polynomial is 104C11DB7
or 04C11DB7H as a 32 bit XOR mask. The LFSR is started off with a value
of FFFFFFFFH and the final CRC is inverted before it is appended to the
message. The inversion can be performed as an additional XOR with FFFFFFFFH.
Error indication
When the whole message including the CRC is run through the calculation
on the receive side, the result should be zero, except that the final inversion
of the CRC changes the matter so the result will not be zero, it will be
another constant, though I have never bothered to find out what, since
it is less trouble to calculate the CRC on the message only and then compare
it with the CRC at the end.
Calculation of a CRC
I've gone through all this without showing you how to calculate a CRC.
There are two methods: the simple and slow method and the fast and incomprehensible
method. CRC16 is simple enough that the simple method is usually quite
fast, while the CRC32 can be problematic and usually needs to be performed
with the aid of a lookup table. When calculating a CRC, it is important
to shift the whole message all the way through the LFSR. Therefore, one
needs to add a bunch of zeros, equal to the width of the LFSR to the end
of the message. That is 2 bytes for a CRC16 and 4 bytes for CRC32. Then
you have to follow this algorithm as illustrated in table 1:
Table 1. CRC-16 Pseudo Code
Describing the LFSR as in a hardware implementation yields:
while not end of message
shift the LFSR left by 1
read the next data bit into the LFSR at b0
if a 1 popped out at the top of the LFSR
XOR LFSR with mask
end while
A more convenient way to describe it in software is to do the whole thing backwards,
by flipping the polynomial around and feeding the data in at the MSB then
while not end of message
XOR data bit with b0 of LFSR
if 1 then
XOR with mask
shift right feeding 1 into b15 (or b31)
else
shift right
end if
end while
Take your pick, either method works...
|
Although the two algorithms above do not look even remotely the same,
the results are the same. Confused? well this is nothing yet...
(The only way to understand these things is on block paper with a pencil
and a large eraser.)
Using a lookup table for speed
The trick behind a lookup table is the self similarity of the XOR operation.
If you perform a series of XORs on a data byte, then you can just as well
replace all those operations with a single XOR, provided that you know
what to XOR with. Therefore, if you perform the CRC calculation on a sequence
of bytes, you can use an 8 bit deep lookup table of XOR masks and shift
the LFSR 8 bits at a time, thereby speeding the calculation up tremendously.
In effect, the lookup table is simply a table of all possible LFSR values,
starting from 0, with a data stream of all 1s (if the data was all zero,
it won't be very interresting). So you can calculate this table at runtime,
by feeding a bunch of FFH data through the CRC calculator and saving the
LFSR after every bit shift.
The table driven CRC32 algorithm can be described as follows in table
2. Again, this one is done backwards, shifting left to right.
Table 2. CRC32 Algorithm
index = 0;
while (index < length)
{
crc = crctable[(int) ((crc ^ data[index++]) & 0xFF] ^ ((crc >> 8) & 0x00FFFFFFL);
}
|
If you can figure that one out, then you got it made! If you are strugling
with this stuff and is getting annoyed at me for not offering a better
explanation - well, it isn't simple and it is quite inexplicable. Please
do use pencil and paper to figure this out.
CRC code
Any explanation is quite useless without some real life code to compare
with, run and dissect. See table 3 for the C code for CRC-16. Note
that this is the backwards algorithm described above which allows for a
very compact loop and that the CRC is inverted before being appended to
the message.
Table 3. CRC-16 in C-flat
/*
* 16 12 5
* this is the CCITT CRC 16 polynomial X + X + X + 1.
* This is 0x1021 when x is 2, but the way the algorithm works
* we use 0x8408 (the reverse of the bit pattern). The high
* bit is always assumed to be set, thus we only use 16 bits to
* represent the 17 bit value.
*/
#define POLY 0x8408 /* 1021H bit reversed */
unsigned short crc16(char *data_p, unsigned short length)
{
unsigned char i;
unsigned int data;
unsigned int crc = 0xffff;
if (length == 0)
return (~crc);
do
{
for (i=0, data=(unsigned int)0xff & *data_p++;
i < 8;
i++, data >>= 1)
{
if ((crc & 0x0001) ^ (data & 0x0001))
crc = (crc >> 1) ^ POLY;
else crc >>= 1;
}
} while (--length);
crc = ~crc;
data = crc;
crc = (crc << 8) | (data >> 8 & 0xff);
return (crc);
}
|
Code Listing
Table 4 contains the CRC-16 assembly code listing.
| Table 4. CRC-16 Assembly Code Listing |
/*********************************************************************
*
* Name: crc16.dsp
*
* Description: CCITT CRC16
*
* Copyright (c) 1996 Aerospace Software Ltd
*
* Revisions:
* -------------------------------------------------------------------
* 1.0 May 96 Herman Oosthuysen
*
*********************************************************************/
.MODULE/RAM CRC16;
#define CC
#include "crc16.h"
#undef CC
#define CC_DEBUG_TESTS 0 /* 0 = normal, 1 = enable test code */
/********************************************************************
* Name: cc_calc_crc
* Description: Calculate CRC16 incrementally, a byte at a time
* Constraints: ar = data, ay0 = crc
* returns ar = crc
*
* Speed sacrifices:
* ALU contents is saved
* shifter contents is destroyed
* DAG 4 is destroyed
*
* The CCITT standard is usually defined for MSB first transmission, using
* the 1021 poly, with 29B1 test value generated by a "123456789" message
* and a F0B8 constant result when including the received (inverse) CRC in
* the check.
*
* This implementation is bit reversed, since the data is received
* LSB first. This requires the LFSR to be reversed:
* Start with FFFFH
* Poly is 8408H LSB first polynomial
* CRC is bit inverted when appended to message
* Result of message + crc is F0B8
* Test is 0282 for "123456789" test message
*
* Algorithm:
* shiftreg = int(shiftreg / 256) xor crc16table((shiftreg xor data) and 255)
*
* Tested in simulator and on ICE
********************************************************************/
cc_calc_crc:
MAC_QUICK_ENTER
ar = ar xor ay0; /* (shiftreg xor data) and 0x00FF */
ay1 = 0x00FF;
ar = ar and ay1;
l4 = 0; /* table lookup */
m4 = ar;
i4 = ^CC_CRC_TBL;
modify ( i4, m4 );
ay1 = pm ( i4, m4 );
sr0 = ay0;
sr1 = 0;
sr = LSHIFT sr0 by - 8 ( lo ); /* shiftreg >> 8 */
ar = sr0 xor ay1; /* ar = incremental CRC-16 */
MAC_QUICK_EXIT
rts;
#if CC_DEBUG_TESTS
/********************************************************************
* Name: cc_test
* Description: Receive a test message
* Constraints: none
* Tested in simulator and on ICE, with a real captured message.
********************************************************************/
cc_test:
MAC_ENTER
ay0 = CC_CRC16_INIT;
ar = 0x00E3;
call cc_calc_crc;
ay0 = ar;
ar = 0x0068;
call cc_calc_crc;
ay0 = ar;
ar = 0x00E3;
call cc_calc_crc;
ay0 = ar;
ar = 0x001B;
call cc_calc_crc;
ay0 = ar;
ar = 0x005B;
call cc_calc_crc;
ay0 = ar;
ar = 0x0003;
call cc_calc_crc;
ay0 = ar;
ar = 0x003B;
call cc_calc_crc;
ay0 = ar;
ar = 0x0004;
call cc_calc_crc;
ay0 = ar;
ar = 0x0048;
call cc_calc_crc;
ay0 = ar;
ar = 0x00D4;
call cc_calc_crc;
ay0 = ar;
ar = 0x00B8;
call cc_calc_crc; /* result in ar should be F0B8 */
MAC_EXIT
rts;
/********************************************************************
* Name: cc_crc_test
* Description: Verify the CRC16 using the standard LSB first "123456789"
* message.
* If the CRC16 is calculated correctly, the result must
* be 0282.
* The constant result when including the inverted checksum
* is F0B8.
* Constraints: none
* Tested in simulator
********************************************************************/
cc_crc_test:
MAC_ENTER
cc_crc_test_start:
ar = 0x0001;
ax0 = ar;
ay0 = 0xFFFF;
call cc_calc_crc;
ay0 = ar;
ar = 0x0002;
call cc_calc_crc;
ay0 = ar;
ar = 0x0003;
call cc_calc_crc;
ay0 = ar;
ar = 0x0004;
call cc_calc_crc;
ay0 = ar;
ar = 0x0005;
call cc_calc_crc;
ay0 = ar;
ar = 0x0006;
call cc_calc_crc;
ay0 = ar;
ar = 0x0007;
call cc_calc_crc;
ay0 = ar;
ar = 0x0008;
call cc_calc_crc;
ay0 = ar;
ar = 0x0009;
call cc_calc_crc;
/* test the standard checksum */
cc_crc_test_done:
ay0 = ar;
ax1 = 0x0282;
af = ax1 - ay0; /* Correct if af is zero */
/* include the inverted checksum */
cc_crc_test_const:
ar = 0x0082;
ar = not ar;
call cc_calc_crc;
ay0 = ar;
ar = 0x0002;
ar = not ar;
call cc_calc_crc;
/* test the constant result */
ay0 = ar;
ax1 = 0xf0b8;
af = ax1 - ay0; /* Correct if af is zero */
cc_crc_test_exit:
MAC_EXIT
rts;
#endif
.ENDMOD;
/**************************** EOF - crc16.DSP ***********************/
|
Table 5 contains the CRC-16 header file listing.
| Table 5. CRC-16 Header File Listing |
/*********************************************************************
*
* Name: crc16.h
*
* Description: CCITT CRC16
*
* Copyright (c) 1996 Aerospace Software Ltd
*
* Revisions:
* -------------------------------------------------------------------
* 1.0 May 96 Herman Oosthuysen
*
*
*********************************************************************/
/* Resolve public definitions */
#undef PUBLIC
#undef PROTOTYPE
#ifdef CC
#define PUBLIC GLOBAL
#define PROTOTYPE ENTRY
#else
#define PUBLIC EXTERNAL
#define PROTOTYPE EXTERNAL
#endif
/***************************** Literals *****************************/
#define LU_CRC16_POLY 0x8408 /* CCITT poly for right shifting */
#define LU_CRC16_INIT 0xFFFF /* start value */
#define LU_CRC16_CONST 0xF0B8 /* result of msg + byte swapped(~crc) */
#define LU_CRC16_TEST 0x0282 /* result of 123456789 test */
#define LU_CRC_TBL_SIZE 0x0100 /* lookup table size */
/***************************** Variables ****************************/
#ifdef CC
/* CCITT CRC16 Lookup Table */
.VAR/PM/RAM/SEG=INT_PM CC_CRC_TBL[LU_CRC_TBL_SIZE];
/* Table generated with Liberty BASIC */
.INIT CC_CRC_TBL:
0x000000, 0x118900, 0x231200, 0x329b00, 0x462400, 0x57ad00, 0x653600, 0x74bf00,
0x8c4800, 0x9dc100, 0xaf5a00, 0xbed300, 0xca6c00, 0xdbe500, 0xe97e00, 0xf8f700,
0x108100, 0x010800, 0x339300, 0x221a00, 0x56a500, 0x472c00, 0x75b700, 0x643e00,
0x9cc900, 0x8d4000, 0xbfdb00, 0xae5200, 0xdaed00, 0xcb6400, 0xf9ff00, 0xe87600,
0x210200, 0x308b00, 0x021000, 0x139900, 0x672600, 0x76af00, 0x443400, 0x55bd00,
0xad4a00, 0xbcc300, 0x8e5800, 0x9fd100, 0xeb6e00, 0xfae700, 0xc87c00, 0xd9f500,
0x318300, 0x200a00, 0x129100, 0x031800, 0x77a700, 0x662e00, 0x54b500, 0x453c00,
0xbdcb00, 0xac4200, 0x9ed900, 0x8f5000, 0xfbef00, 0xea6600, 0xd8fd00, 0xc97400,
0x420400, 0x538d00, 0x611600, 0x709f00, 0x042000, 0x15a900, 0x273200, 0x36bb00,
0xce4c00, 0xdfc500, 0xed5e00, 0xfcd700, 0x886800, 0x99e100, 0xab7a00, 0xbaf300,
0x528500, 0x430c00, 0x719700, 0x601e00, 0x14a100, 0x052800, 0x37b300, 0x263a00,
0xdecd00, 0xcf4400, 0xfddf00, 0xec5600, 0x98e900, 0x896000, 0xbbfb00, 0xaa7200,
0x630600, 0x728f00, 0x401400, 0x519d00, 0x252200, 0x34ab00, 0x063000, 0x17b900,
0xef4e00, 0xfec700, 0xcc5c00, 0xddd500, 0xa96a00, 0xb8e300, 0x8a7800, 0x9bf100,
0x738700, 0x620e00, 0x509500, 0x411c00, 0x35a300, 0x242a00, 0x16b100, 0x073800,
0xffcf00, 0xee4600, 0xdcdd00, 0xcd5400, 0xb9eb00, 0xa86200, 0x9af900, 0x8b7000,
0x840800, 0x958100, 0xa71a00, 0xb69300, 0xc22c00, 0xd3a500, 0xe13e00, 0xf0b700,
0x084000, 0x19c900, 0x2b5200, 0x3adb00, 0x4e6400, 0x5fed00, 0x6d7600, 0x7cff00,
0x948900, 0x850000, 0xb79b00, 0xa61200, 0xd2ad00, 0xc32400, 0xf1bf00, 0xe03600,
0x18c100, 0x094800, 0x3bd300, 0x2a5a00, 0x5ee500, 0x4f6c00, 0x7df700, 0x6c7e00,
0xa50a00, 0xb48300, 0x861800, 0x979100, 0xe32e00, 0xf2a700, 0xc03c00, 0xd1b500,
0x294200, 0x38cb00, 0x0a5000, 0x1bd900, 0x6f6600, 0x7eef00, 0x4c7400, 0x5dfd00,
0xb58b00, 0xa40200, 0x969900, 0x871000, 0xf3af00, 0xe22600, 0xd0bd00, 0xc13400,
0x39c300, 0x284a00, 0x1ad100, 0x0b5800, 0x7fe700, 0x6e6e00, 0x5cf500, 0x4d7c00,
0xc60c00, 0xd78500, 0xe51e00, 0xf49700, 0x802800, 0x91a100, 0xa33a00, 0xb2b300,
0x4a4400, 0x5bcd00, 0x695600, 0x78df00, 0x0c6000, 0x1de900, 0x2f7200, 0x3efb00,
0xd68d00, 0xc70400, 0xf59f00, 0xe41600, 0x90a900, 0x812000, 0xb3bb00, 0xa23200,
0x5ac500, 0x4b4c00, 0x79d700, 0x685e00, 0x1ce100, 0x0d6800, 0x3ff300, 0x2e7a00,
0xe70e00, 0xf68700, 0xc41c00, 0xd59500, 0xa12a00, 0xb0a300, 0x823800, 0x93b100,
0x6b4600, 0x7acf00, 0x485400, 0x59dd00, 0x2d6200, 0x3ceb00, 0x0e7000, 0x1ff900,
0xf78f00, 0xe60600, 0xd49d00, 0xc51400, 0xb1ab00, 0xa02200, 0x92b900, 0x833000,
0x7bc700, 0x6a4e00, 0x58d500, 0x495c00, 0x3de300, 0x2c6a00, 0x1ef100, 0x0f7800;
#endif
/****************************** Publics *****************************/
.PUBLIC
CC_CRC_TBL;
/***************************** Prototypes ***************************/
.PROTOTYPE
cc_calc_crc;
/**************************** EOF - crc16.H *************************/
|
The CRC32 can be calculated in a similar fashion or it can be done using
a lookup table of 256 bytes as below in table 6. In this case, the code
was developed for use on a TMS320C50 16bit fixed point DSP. The compiler
had a problem with the handling of 32bit words and the code was massaged
a bit to allow it compile correctly. This also makes it a bit easier to
understand, therefore I included this version. Note that according to the
ethernet standard, the CRC needs to be inverted before it is appended to
the message.
Table 6. CRC32 in C-flat
/********************************************************************
*
* File: crc32.c
*
* Description: 32bit implementation of the CRC32 LFSR.
*
* Copyright Aerospace Software Ltd. 1996.
* Tel.: (403) 547-6402, 607-4708
* Fax.: (403) 241-8773
* E-Mail: aerosoft@agt.net
*
********************************************************************/
#include "dos.h"
#include "stdio.h"
#include "string.h"
#define PUBLIC
typedef unsigned int UINT_2;
typedef unsigned long UINT_4;
/****************************************************
* CRC 32 Look-up Table
****************************************************/
const UINT_4 crc_32_tab[] =
{
0x00000000L, 0x77073096L, 0xee0e612cL, 0x990951baL, 0x076dc419L,
0x706af48fL, 0xe963a535L, 0x9e6495a3L, 0x0edb8832L, 0x79dcb8a4L,
0xe0d5e91eL, 0x97d2d988L, 0x09b64c2bL, 0x7eb17cbdL, 0xe7b82d07L,
0x90bf1d91L, 0x1db71064L, 0x6ab020f2L, 0xf3b97148L, 0x84be41deL,
0x1adad47dL, 0x6ddde4ebL, 0xf4d4b551L, 0x83d385c7L, 0x136c9856L,
0x646ba8c0L, 0xfd62f97aL, 0x8a65c9ecL, 0x14015c4fL, 0x63066cd9L,
0xfa0f3d63L, 0x8d080df5L, 0x3b6e20c8L, 0x4c69105eL, 0xd56041e4L,
0xa2677172L, 0x3c03e4d1L, 0x4b04d447L, 0xd20d85fdL, 0xa50ab56bL,
0x35b5a8faL, 0x42b2986cL, 0xdbbbc9d6L, 0xacbcf940L, 0x32d86ce3L,
0x45df5c75L, 0xdcd60dcfL, 0xabd13d59L, 0x26d930acL, 0x51de003aL,
0xc8d75180L, 0xbfd06116L, 0x21b4f4b5L, 0x56b3c423L, 0xcfba9599L,
0xb8bda50fL, 0x2802b89eL, 0x5f058808L, 0xc60cd9b2L, 0xb10be924L,
0x2f6f7c87L, 0x58684c11L, 0xc1611dabL, 0xb6662d3dL, 0x76dc4190L,
0x01db7106L, 0x98d220bcL, 0xefd5102aL, 0x71b18589L, 0x06b6b51fL,
0x9fbfe4a5L, 0xe8b8d433L, 0x7807c9a2L, 0x0f00f934L, 0x9609a88eL,
0xe10e9818L, 0x7f6a0dbbL, 0x086d3d2dL, 0x91646c97L, 0xe6635c01L,
0x6b6b51f4L, 0x1c6c6162L, 0x856530d8L, 0xf262004eL, 0x6c0695edL,
0x1b01a57bL, 0x8208f4c1L, 0xf50fc457L, 0x65b0d9c6L, 0x12b7e950L,
0x8bbeb8eaL, 0xfcb9887cL, 0x62dd1ddfL, 0x15da2d49L, 0x8cd37cf3L,
0xfbd44c65L, 0x4db26158L, 0x3ab551ceL, 0xa3bc0074L, 0xd4bb30e2L,
0x4adfa541L, 0x3dd895d7L, 0xa4d1c46dL, 0xd3d6f4fbL, 0x4369e96aL,
0x346ed9fcL, 0xad678846L, 0xda60b8d0L, 0x44042d73L, 0x33031de5L,
0xaa0a4c5fL, 0xdd0d7cc9L, 0x5005713cL, 0x270241aaL, 0xbe0b1010L,
0xc90c2086L, 0x5768b525L, 0x206f85b3L, 0xb966d409L, 0xce61e49fL,
0x5edef90eL, 0x29d9c998L, 0xb0d09822L, 0xc7d7a8b4L, 0x59b33d17L,
0x2eb40d81L, 0xb7bd5c3bL, 0xc0ba6cadL, 0xedb88320L, 0x9abfb3b6L,
0x03b6e20cL, 0x74b1d29aL, 0xead54739L, 0x9dd277afL, 0x04db2615L,
0x73dc1683L, 0xe3630b12L, 0x94643b84L, 0x0d6d6a3eL, 0x7a6a5aa8L,
0xe40ecf0bL, 0x9309ff9dL, 0x0a00ae27L, 0x7d079eb1L, 0xf00f9344L,
0x8708a3d2L, 0x1e01f268L, 0x6906c2feL, 0xf762575dL, 0x806567cbL,
0x196c3671L, 0x6e6b06e7L, 0xfed41b76L, 0x89d32be0L, 0x10da7a5aL,
0x67dd4accL, 0xf9b9df6fL, 0x8ebeeff9L, 0x17b7be43L, 0x60b08ed5L,
0xd6d6a3e8L, 0xa1d1937eL, 0x38d8c2c4L, 0x4fdff252L, 0xd1bb67f1L,
0xa6bc5767L, 0x3fb506ddL, 0x48b2364bL, 0xd80d2bdaL, 0xaf0a1b4cL,
0x36034af6L, 0x41047a60L, 0xdf60efc3L, 0xa867df55L, 0x316e8eefL,
0x4669be79L, 0xcb61b38cL, 0xbc66831aL, 0x256fd2a0L, 0x5268e236L,
0xcc0c7795L, 0xbb0b4703L, 0x220216b9L, 0x5505262fL, 0xc5ba3bbeL,
0xb2bd0b28L, 0x2bb45a92L, 0x5cb36a04L, 0xc2d7ffa7L, 0xb5d0cf31L,
0x2cd99e8bL, 0x5bdeae1dL, 0x9b64c2b0L, 0xec63f226L, 0x756aa39cL,
0x026d930aL, 0x9c0906a9L, 0xeb0e363fL, 0x72076785L, 0x05005713L,
0x95bf4a82L, 0xe2b87a14L, 0x7bb12baeL, 0x0cb61b38L, 0x92d28e9bL,
0xe5d5be0dL, 0x7cdcefb7L, 0x0bdbdf21L, 0x86d3d2d4L, 0xf1d4e242L,
0x68ddb3f8L, 0x1fda836eL, 0x81be16cdL, 0xf6b9265bL, 0x6fb077e1L,
0x18b74777L, 0x88085ae6L, 0xff0f6a70L, 0x66063bcaL, 0x11010b5cL,
0x8f659effL, 0xf862ae69L, 0x616bffd3L, 0x166ccf45L, 0xa00ae278L,
0xd70dd2eeL, 0x4e048354L, 0x3903b3c2L, 0xa7672661L, 0xd06016f7L,
0x4969474dL, 0x3e6e77dbL, 0xaed16a4aL, 0xd9d65adcL, 0x40df0b66L,
0x37d83bf0L, 0xa9bcae53L, 0xdebb9ec5L, 0x47b2cf7fL, 0x30b5ffe9L,
0xbdbdf21cL, 0xcabac28aL, 0x53b39330L, 0x24b4a3a6L, 0xbad03605L,
0xcdd70693L, 0x54de5729L, 0x23d967bfL, 0xb3667a2eL, 0xc4614ab8L,
0x5d681b02L, 0x2a6f2b94L, 0xb40bbe37L, 0xc30c8ea1L, 0x5a05df1bL,
0x2d02ef8dL
};
PUBLIC UINT_4 Enc_Get_CRC( UINT_2 *data, UINT_2 len );
void main(void)
{
UINT_4 crc;
UINT_2 cnt;
UINT_2 crchi;
UINT_2 crclo;
UINT_2 data[]=
{
0x002e, 0x0001, 0x8002, 0x0000, 0x2800, 0x6162, 0x6263, 0x6364,
0x6465, 0x6566, 0x6667, 0x6768, 0x6869, 0x696a, 0x6a6b, 0x6b6c,
0x6c6d, 0x6d6e, 0x6e6f, 0x6f70, 0x7071, 0x6162, 0x6263, 0x6364,
0x0000, 0x0000
};
cprintf("\n\rCrc32 ver. 1.0, 32bit CRC32 Demonstration Program.\n\n\r");
cprintf("Copyright Aerospace Software Ltd. 1996\n\r");
cprintf("Tel.: (403) 547-6402, 607-4708\n\r");
cprintf("Fax.: (403) 241-8773\n\r");
cprintf("E-Mail: aerosoft@agt.net\n\n\r");
cprintf("Input String:\n\r");
for(cnt = 0; cnt < sizeof(data); cnt++)
cprintf("%04x ", data[cnt]);
crc = Enc_Get_CRC(data, (data[0]-2));
crchi = (UINT_2)(crc >> 16);
crclo = (UINT_2)crc;
cprintf("\n\n\rCRC32 = %4x%4x\n\r", crchi, crclo);
}
/***************************************************************************
*
* Function: Enc_Get_CRC
*
* Purpose: Calculate the CRC32
*
* Args: UINT_2 *data - pointer to data string
* UINT_2 len - length in bytes
*
* Return Value: none
*
* Remarks:
* CRC32 Generator Polinomial:
* x^0+x^1+x^2+x^4+x^5+x^7+x^8+x^10+x^11+x^12+x^16+x^22+x^23+x^26+x^32
*
* The CRC 32 polinomial is a linear feedback shift register that will
* generate a Maximal Length Sequence, implemented here using a lookup
* table, to reduce the number of shift and XOR operations.
*
* Algorithm:
* crc32val = crc_32_tab[(int) ((crc32val) ^ (s[i])) & 0xff] ^
* (((crc32val) >> 8) & 0x00FFFFFFL);
*
* Notes:
* The DSP is a 16 bit machine, so the algorithm had to be modified.
* The C compiler consistently created bad code, due to the complexity
* of the algorithm. It was consequently broken up into many smaller
* steps, using intermediate variables. These steps were arranged in
* a logical order, to allow the compiler to optimize the code through
* the ellimination of temporary variables, without destroying the
* validity of the calculation. Finally, the output was compared to
* test code compiled with Borland Turbo C version 2.0.
*
*
*************************************************************************/
PUBLIC UINT_4 Enc_Get_CRC( UINT_2 *data, UINT_2 len )
{
UINT_4 crc = 0 ;
UINT_2 crc_low;
UINT_2 data_byte;
UINT_2 byte_cnt;
UINT_2 word_cnt;
UINT_2 table_index;
UINT_4 term1;
UINT_4 term2;
/****************************************************
* Calculate CRC32 on a word array
****************************************************/
for (byte_cnt = 0, word_cnt = 0; byte_cnt < len; byte_cnt ++)
{
/*************************************************
* Get the upper or lower byte of data from the
* word array
*************************************************/
if ( byte_cnt & 0x0001 )
{
/* Odd */
data_byte = data[word_cnt] >> 8;
word_cnt++;
}
else
{
/* Even */
data_byte = data[word_cnt];
}
/************************************************
* Calculate the first XOR term
* Limit the table index to 256
************************************************/
crc_low = (UINT_2)crc;
table_index = (crc_low ^ data_byte) & 0x00ff;
term1 = crc_32_tab[table_index];
/************************************************
* Calculate the second term
* then update the CRC Maximal Length Code Register
************************************************/
term2 = crc >> 8;
crc = term1 ^ term2;
}
return crc;
}
/*******************************************************************/
|
That's all folks; have fun!
|
|
