CRC16, CRC32, CRC64 Checksums

Introduction

The concept of error detection codes was first proposed by mathematician and computer scientist W. Wesley Peterson in his 1961 publication Cyclic Codes for Error Detection.

CRC in C

The following structure holds values relevant to generating a CRC and is based on code found on this site.

typedef struct _crc_param_t {
    char    *str;     // description
    uint64_t poly;    // polynomial
    uint64_t iv;      // initial value
    int      rin;     // reverse bits of input
    int      rout;    // reverse bits of output
    uint64_t xor;     // xor final value
    uint64_t tv;      // test vector for "123456789"
    uint64_t wordlen; // length of CRC in bits
} crc_param;

The following code will calculate a 16,32 or 64-bit CRC when provided with the correct parameters.

static uint64_t crc_table[256];

// reverse bits of x
static uint64_t rbit(uint64_t x, uint64_t wordlen) {
    uint64_t i, r = 0;
    
    for(i=0; i<wordlen; i++) {
      if((x & (1ULL << i)) != 0) {
        r |= ((1ULL << (wordlen - i - 1)));
      }
    }
    return r;
}
 
static void create_table(crc_param *p, uint64_t m) {
    int      j;
    uint64_t i, r;
    
    for(i=0; i<256; i++) {
      r = (p->rin) ? rbit(i, p->wordlen) : i << (p->wordlen - 8);

      for (j=0; j<8; j++) {
        if (r & (1ULL << (p->wordlen - 1))) {
          r = ((r << 1ULL) ^ p->poly);
        } else {
          r <<= 1ULL;
        }
      }
      r = (p->rout) ? rbit(r, p->wordlen) : r;
      crc_table[i] = (r & m);
    }
}

uint64_t crc(const void *input, size_t len, crc_param *p) {
    uint64_t crc, m=~0ULL;
    uint8_t  *data=(uint8_t*)input;
    int      i;
    
    if(p->wordlen<64) m = (1ULL << p->wordlen) - 1;

    create_table(p, m);
    
    crc = p->rin ? rbit(p->iv, p->wordlen) : p->iv;
    
    for(i=0; i<len; i++) {
      if (p->rout) {
        crc = (crc >> 8) ^ crc_table[(crc&0xFF)^data[i]];
      } else {
        crc = (crc << 8) ^ crc_table[(crc>>(p->wordlen-8))^data[i]];  
      }
      crc &= m;
    }
    return (crc ^ p->xor) & m;
}

Sources here.