Search

0.12.3.2 CRC-16

CRC-16's numerator polynomial is based on sixteen bits of data unlike the CCIT's which is based on eight. The divisor polynomial for the CRC-16 is also different than the CCIT's, it is:

x¹⁶ + x⁵ + x² + 1

The CRC-16, like the CRC-CCIT, can be implemented with a table lookup strategy. However where the CCIT needed 256 distinct entries in the table (one for each possible numerator - 2⁸ total) the CRC-16 can work with a much smaller table. By examining the table value of each of the four nibbles (four bits) of data in the sixteen bit numerator polynomial the CRC-16 can arrive at a value for the upper part of the fraction. The denominator is, of course, a constant. So, the CRC-16 can operate quickly with a table size of only sixteen entries.

Because it can operate quickly with a small lookup table, the CRC-16 is often used in hardware devices such as disk controllers and the like.

/* 
 *  this source code is based on Rex and Binstock which, in turn,
 *  acknowledges William James Hunt.
 */

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

unsigned int crc_16_table[16] = {
  0x0000, 0xCC01, 0xD801, 0x1400, 0xF001, 0x3C00, 0x2800, 0xE401,
  0xA001, 0x6C00, 0x7800, 0xB401, 0x5000, 0x9C01, 0x8801, 0x4400 };

unsigned short int get_crc_16 (int start, char *p, int n) {
  unsigned short int crc = start;
  int r;

  /* while there is more data to process */
  while (n-- > 0) {

    /* compute checksum of lower four bits of *p */
    r = crc_16_table[crc & 0xF];
    crc = (crc >> 4) & 0x0FFF;
    crc = crc ^ r ^ crc_16_table[*p & 0xF];

    /* now compute checksum of upper four bits of *p */
    r = crc_16_table[crc & 0xF];
    crc = (crc >> 4) & 0x0FFF;
    crc = crc ^ r ^ crc_16_table[(*p >> 4) & 0xF];

    /* next... */
    p++;
  }
 
  return(crc);
}