Aerospace Software Ltd.

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:

addsum filename.bin

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!