Search

0.12.3.1 CRC-CCIT

The CRC-CCIT is used by the Xmodem-CRC telecommunication protocol and   takes its name from the CCIT worldwide standards organization. This     flavor of CRC is used on single bytes of data. The divisor polynomial for this CRC flavor is:

x¹⁶ + x¹² + x⁵ + 1

The CRC-CCIT value, for an 8-bit number, is the remainder of the division of the CRC polynomial by the above divisor polynomial. For instance, for the previously examined bit pattern 10011011 the CRC-CCIT fraction would look like this:

CRC-CCIT = remainder of $\frac{x^7 + x^4 + x^3 + x^1 + 1} {x^{16} + x^{12} + x^5 + 1}$

This may look like a difficult expression to simplify, especially with the speed demanded by limited buffer size and high bandwidth communications. However, by carefully choosing the value of x so as to make division possible using only bitwise operations, the value can be computed very rapidly. This value is 0x1021.

An even faster alternative to calculating the remainder of the above division is to create a lookup table of values. Since the denominator   of the division is a constant and the numerator can have only 256 possible values (one for each possible bit combination), a table of 256 remainders can provide instant access to the CRC-CCIT value of a particular byte. Such a table can be generated easily by repeatedly calling the get_crc_ccit function below in a loop with values ranging from zero to 255 and a crc seed value of zero.

unsigned short table[256];

for (i = 0; i < 256; i++) {

  /* the implementation of get_crc_ccit is given below */
  table[i] = get_crc_ccit(i, 0);
}

Here's the table (all CRC values are hexadecimal):

(0)	0x0000	0x1021	0x2042	0x3063	0x4084	0x50a5	0x60c6	0x70e7
(8)	0x8108	0x9129	0xa14a	0xb16b	0xc18c	0xd1ad	0xe1ce	0xf1ef
(16)	0x1231	0x0210	0x3273	0x2252	0x52b5	0x4294	0x72f7	0x62d6
(24)	0x9339	0x8318	0xb37b	0xa35a	0xd3bd	0xc39c	0xf3ff	0xe3de
(32)	0x2462	0x3443	0x0420	0x1401	0x64e6	0x74c7	0x44a4	0x5485
(40)	0xa56a	0xb54b	0x8528	0x9509	0xe5ee	0xf5cf	0xc5ac	0xd58d
(48)	0x3653	0x2672	0x1611	0x0630	0x76d7	0x66f6	0x5695	0x46b4
(56)	0xb75b	0xa77a	0x9719	0x8738	0xf7df	0xe7fe	0xd79d	0xc7bc
(64)	0x48c4	0x58e5	0x6886	0x78a7	0x0840	0x1861	0x2802	0x3823
(72)	0xc9cc	0xd9ed	0xe98e	0xf9af	0x8948	0x9969	0xa90a	0xb92b
(80)	0x5af5	0x4ad4	0x7ab7	0x6a96	0x1a71	0x0a50	0x3a33	0x2a12
(88)	0xdbfd	0xcbdc	0xfbbf	0xeb9e	0x9b79	0x8b58	0xbb3b	0xab1a
(96)	0x6ca6	0x7c87	0x4ce4	0x5cc5	0x2c22	0x3c03	0x0c60	0x1c41
(104)	0xedae	0xfd8f	0xcdec	0xddcd	0xad2a	0xbd0b	0x8d68	0x9d49
(112)	0x7e97	0x6eb6	0x5ed5	0x4ef4	0x3e13	0x2e32	0x1e51	0x0e70
(120)	0xff9f	0xefbe	0xdfdd	0xcffc	0xbf1b	0xaf3a	0x9f59	0x8f78
(128)	0x9188	0x81a9	0xb1ca	0xa1eb	0xd10c	0xc12d	0xf14e	0xe16f
(136)	0x1080	0x00a1	0x30c2	0x20e3	0x5004	0x4025	0x7046	0x6067
(144)	0x83b9	0x9398	0xa3fb	0xb3da	0xc33d	0xd31c	0xe37f	0xf35e
(152)	0x02b1	0x1290	0x22f3	0x32d2	0x4235	0x5214	0x6277	0x7256
(160)	0xb5ea	0xa5cb	0x95a8	0x8589	0xf56e	0xe54f	0xd52c	0xc50d
(168)	0x34e2	0x24c3	0x14a0	0x0481	0x7466	0x6447	0x5424	0x4405
(176)	0xa7db	0xb7fa	0x8799	0x97b8	0xe75f	0xf77e	0xc71d	0xd73c
(184)	0x26d3	0x36f2	0x0691	0x16b0	0x6657	0x7676	0x4615	0x5634
(192)	0xd94c	0xc96d	0xf90e	0xe92f	0x99c8	0x89e9	0xb98a	0xa9ab
(200)	0x5844	0x4865	0x7806	0x6827	0x18c0	0x08e1	0x3882	0x28a3
(208)	0xcb7d	0xdb5c	0xeb3f	0xfb1e	0x8bf9	0x9bd8	0xabbb	0xbb9a
(216)	0x4a75	0x5a54	0x6a37	0x7a16	0x0af1	0x1ad0	0x2ab3	0x3a92
(224)	0xfd2e	0xed0f	0xdd6c	0xcd4d	0xbdaa	0xad8b	0x9de8	0x8dc9
(232)	0x7c26	0x6c07	0x5c64	0x4c45	0x3ca2	0x2c83	0x1ce0	0x0cc1
(240)	0xef1f	0xff3e	0xcf5d	0xdf7c	0xaf9b	0xbfba	0x8fd9	0x9ff8
(248)	0x6e17	0x7e36	0x4e55	0x5e74	0x2e93	0x3eb2	0x0ed1	0x1ef0

In order to arrive at a CRC for the entire range of data to be verified, a running CRC value is used. This is to say, the CRC of the first byte of data is used to somehow affect the CRC value of the second byte, and so on...

for (i = 0; i < data_size; i++) {
  crc = get_crc_ccit(crc, buffer[i]);
}

Here is the code to calculate the CRC of a byte, based on source from Rex and Binstock. The initial value of crc should be zero on the first call to this routine.

#include <stdio.h>
#include <stdlib.h>

unsigned short get_crc_ccit (unsigned short crc, unsigned short data) {
  static unsigned int i;

  /* move to most significant bit */
  data <<= 8;

  /* for each bit in the character... */
  for (i = 8; i > 0; i--) {

    /* calculate */
    if ((data ^ crc) & 0x8000) crc = (crc << 1) ^ 0x1021;
    else crc <<= 1;

    /* next bit please */
    data <<= 1;
  }
  return(crc)
}