优化变种CRC算法

2019/04/20 algorithm

CRC算法

循环冗余校验-CRC是常用的一种校验数据一致性的算法。关于其原理与发展可以参考其维基百科。

关于该算法的优化也经常是大家关心的一个方向,现在最常用的实现基本都是查表法,下图是别人总结的相关算法的优化历史1:

可以看出,当因特尔提出了slice-by-x的优化后,其速度得到的飞跃。

然而CRC算法的变种数量非常之多,但是已经被实现的那些优化只是少数的几种,比如ISOECMA等。同时这些优化后的代码已经丢失的大量中间过程,是的其难以被移植到其他变种之上。

优化变种算法

经过一番研究考证,CRC64变种采用slice-by-x优化的主要步骤为:

  • 将原始查询表转化为8重表格
    // table[0] 是原始查询表, table[1...7] 是生成的8重表格
    for (n = 0; n < 256; n++) {
      crc = table[0][n];
    
      for (k = 1; k < 8; k++) {
          crc = table[0][crc & 0xff] ^ (crc >> 8);
          table[k][n] = crc;
      }
    }
    
  • 优化CRC算法,每个循环计算8个字节
    while (len >= 8) {
      crc ^= *(uint64_t *)byte; // 小端计算方式
      crc = table[7][crc & 0xff] ^
            table[6][(crc >> 8) & 0xff] ^
            table[5][(crc >> 16) & 0xff] ^
            table[4][(crc >> 24) & 0xff] ^
            table[3][(crc >> 32) & 0xff] ^
            table[2][(crc >> 40) & 0xff] ^
            table[1][(crc >> 48) & 0xff] ^
            table[0][crc >> 56];
      byte += 8;
      len -= 8;
    }
    while (len) {
      crc = table[0][(crc ^ *byte++) & 0xff] ^ (crc >> 8);
      len--;
    

实现

github.com/lrita/crc64采用上述方法,优化了redis使用的 CRC64 变种算法,使其速度从381.29 MB/s提升到1474.16 MB/s.

参考

Search

    Table of Contents