CRC循环冗余校验【实现篇】

在之前的文章当中，我简单介绍了一下有关于CRC的原理，这次呢，我们从开发的角度来看一下CRC的具体实现，因为CRC的种类实在是太多了，如果咱们一个一个实现，那就太费劲了，所以直接来看通用的实现方法。

参数

对于如何确定一个CRC校验，可以通过如下的参数来确定，

• 「多项式(Poly)」: 它是一个二进制数，表示用于生成CRC码的多项式，多项式长度取决于数据位的位数。
• **初始值(Initial Value)**： 一个二进制数，表示在计算CRC码之前，应该在数据字节流的开头添加的字节，通常情况是全0或者全1。
• **终止值(Final Xor Value)**：一个二进制数，表示在计算CRC码之后，应该对CRC码进行执行异或操作的字节，通常情况是全0或者全1。
• **反转输入(Reflect Input)**：对输入的字节是否进行反转。
• 「反转输出(Reflect Input)」: 对输出的字节是否进行反转。

有关于第一个参数的含义，可以参考下我之前写过的文章，https://mp.weixin.qq.com/s/VwT__b-1cjaLcK0o7D-Vjw。

代码实现

再次相应读者们的选择，这次还是用C++来写，比较容易写出来一个比较通用的代码，当然我这代码就仅仅支持到crc64的任意多项式，再多其实也有，目前就先不支持了，实际上用的也不多。

#include <iostream>
#include <vector>
#include <iomanip>

template<typename T>
T reverse_bits(T value, int num_bits) {
  T result = 0;
  for (int i = 0; i < num_bits; i++) {
    result = (result << 1) | (value & 1);
    value >>= 1;
  }
  return result;
}

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wshift-count-overflow"
template<typename T>
std::vector<uint8_t> calculate_crc(const std::vector<uint8_t> &data,
                                   T polynomial,
                                   T initial_value,
                                   bool reflect_input,
                                   bool reflect_output,
                                   T final_xor_value) {
  std::vector<uint8_t> crc_bytes;
  T crc = initial_value;
  int num_bits = sizeof(T) * 8;
  T top_bit = (T) 1 << (num_bits - 1);

  for (uint8_t b : data) {
    if (reflect_input) {
      b = reverse_bits(b, 8);
      crc ^= ((T) b << (num_bits - 8));
      for (int i = 0; i < 8; i++) {
        T msb = crc & top_bit;
        crc <<= 1;
        if (msb != 0) {
          crc ^= polynomial;
        }
      }
    } else {
      crc ^= ((T) b << (num_bits - 8));
      for (int i = 0; i < 8; i++) {
        T msb = crc & top_bit;
        crc <<= 1;
        if (msb != 0) {
          crc ^= polynomial;
        }
      }
    }
  }

  if (reflect_output) {
    for (int i = 0; i < num_bits / 8; i++) {
      if (reflect_input) {
        crc_bytes.push_back(static_cast<uint8_t>(reverse_bits((crc >> (8 * i)) & 0xff, 8)));
      } else {
        crc_bytes.push_back((crc >> (8 * i)) & 0xff);
      }
    }
  } else {
    for (int i = (num_bits - 8); i >= 0; i -= 8) {
      crc_bytes.push_back((crc >> i) & 0xff);
    }
  }

  for (unsigned char &crc_byte : crc_bytes) {
    crc_byte ^= (final_xor_value & 0xff);
    final_xor_value >>= 8;
  }

  return crc_bytes;
}
#pragma clang diagnostic pop

std::vector<uint8_t> crc8(const std::vector<uint8_t> &data,
                          uint8_t polynomial,
                          uint8_t initial_value,
                          bool reflect_input,
                          bool reflect_output,
                          uint8_t final_xor_value) {
  return calculate_crc<uint8_t>(data, polynomial, initial_value, reflect_input, reflect_output, final_xor_value);
}

std::vector<uint8_t> crc16(const std::vector<uint8_t> &data,
                           uint16_t polynomial,
                           uint16_t initial_value,
                           bool reflect_input,
                           bool reflect_output,
                           uint16_t final_xor_value) {
  return calculate_crc<uint16_t>(data, polynomial, initial_value, reflect_input, reflect_output, final_xor_value);
}

std::vector<uint8_t> crc32(const std::vector<uint8_t> &data,
                           uint32_t polynomial,
                           uint32_t initial_value,
                           bool reflect_input,
                           bool reflect_output,
                           uint32_t final_xor_value) {
  return calculate_crc<uint32_t>(data, polynomial, initial_value, reflect_input, reflect_output, final_xor_value);
}

std::vector<uint8_t> crc64(const std::vector<uint8_t> &data,
                           uint64_t polynomial,
                           uint64_t initial_value,
                           bool reflect_input,
                           bool reflect_output,
                           uint64_t final_xor_value) {
  return calculate_crc<uint64_t>(data, polynomial, initial_value, reflect_input, reflect_output, final_xor_value);
}

void print_vector_as_hex_string(const std::string &tag, const std::vector<uint8_t> &vec) {
  std::cout << tag << ":";
  for (const uint8_t &value : vec) {
    std::cout << std::hex << std::setw(2) << std::setfill('0') << (int) value << " ";
  }
  std::cout << std::endl;
}

int main() {

  std::vector<uint8_t> data = {0x01, 0x02, 0x03, 0x04, 0x05};

  print_vector_as_hex_string("CRC16:(CRC-16/ARC)", crc16(data, 0x8005, 0x0000, true, true, 0x0000));
  print_vector_as_hex_string("CRC8:(CRC-8/DARC)", crc8(data, 0x39, 0x00, true, true, 0x00));

  return 0;
}

我们具体使用一个例子来看一下这个代码，首先我们选取CRC8这个来作为例子来看一下，至于为啥选他，看着他简单而已，那下面我们先根据上面我们选取的参数，来看一下CRC8。

• 「多项式(Poly)」:  0x07
• **初始值(Initial Value)**： 0x00
• **终止值(Final Xor Value)**：0x00
• **反转输入(Reflect Input)**：false
• 「反转输出(Reflect Input)」: false

假设我们的输入是0x02，为啥不选0x01,因为1是一个常量，乘了和没乘是一样的，所以我们换一个数字。

对应输入的多项式为 ，对应生成多项式为，然后我们可以得到`r=8`，然后计算下，我们可以得到：

也就是最终得到CRC8的校验值0x0E，然后我们运行下我们写的程序看一下。

int main() {

  std::vector<uint8_t> data = {0x02};
  print_vector_as_hex_string("CRC8:(CRC-8)", crc8(data, 0x07, 0x00, false, false, 0x00));
  return 0;
}

发现输出结果和我们写的程序是一样的，至于这个值，我这是怎么算出来的，读者可以自己尝试一下手动计算，我这里当然是选择科技与狠活了，如果大家对于这个我怎么算的感兴趣，我可以单独写一篇有关怎么计算多项式的文章，咳咳，不要吐槽我水文章哈。

好了，到这里有关于通用版本的CRC计算方案，到这里就给大家讲完了，然后呢，这里我找了下有关于CRC计算的常见多项式，和一些参数，以下资料来自互联网。

常见CRC方案

里面内容来自于参考资料2，我只是个搬运工。

参考资料

• https://zlib.net/crc_v3.txt
• https://reveng.sourceforge.io/crc-catalogue/
• https://crccalc.com/