【考研408】CRC算法详解，并用SIMD SSE4.2实现CRC32

模二运算

CRC算法核心是模二运算，模二运算加法不进位，减法不借位，可看作异或运算

//不进位
1101 + 0001 = 1100
//不借位
1100 - 0001 = 1101

CRC算法

数据链路层广泛使用循环冗余码（CRC）检错技术

CRC算法步骤：

设原始数据为D，除数为P，多项式的阶为r，余数为R，实际发送的数据为T

1.收发双方约定生成多项式G(x)（最高位和最低位必须为1）。k位位串可视为阶数为k-1的多项式的系数序列。例如，1101用多项式表示就是 $1 \cdot x^{3} + 1 \cdot x^{2} + 0 \cdot x^{1} + 1 \cdot x^{0}$

2.发送方基于数据和G(x)，计算出冗余码，将冗余码附加到数据最后一起发送

加0：G(x)有几阶就加几个0，可看作左移<<运算

计算冗余码： $R = (2^{r}D) mod P$

附加冗余码： $T = (2^{r}D) ⨁ R$

3.接收方收到数据和冗余码后，通过G(x)检错

如果$T mod P = 0$则无差错

通俗一点解释就是：选择一个数，用数据模二除这个数，得到的余数就是冗余码，附加到数据最后。接收方将收到的数据模二除选择的数，余数为0则无差错

做个题加深理解（笑

【2023统考真题】甲向乙发送数据，使用CRC算法，生成多项式为 $G(x) = x^{4} + x + 1$，则乙方接收到比特串( D )时，可以断定无错误

A.101110000

B.101110100

C.101111000

D.101111100

解析：

注意到：ABCD前5位都是10111，所以可断定数据部分为10111

如果没有注意到：多项式的阶为4，所以冗余码占4位，那么数据就有5位，为10111

根据所给多项式，可知除数为10011，算出冗余码为1100，故选D

SIMD SSE4.2实现CRC32

SSE4.2指令集提供了四个指令用于计算CRC32，生成多项式为0x1EDC6F41

第一个操作数提供初始值，累计第二个操作数的CRC32值，返回结果

#include <cstdint>
#include <intrin.h>

static uint32_t crc32(const uint8_t* data, size_t size, uint32_t init_crc = 0xffffffff) {
    for (size_t offset = 0; offset < size;) {
        size_t remaining = size - offset;
        if (remaining >= 8) {
            init_crc = _mm_crc32_u64(init_crc, *(uint64_t*)(data + offset));
            offset += 8;
        }
        else if (remaining >= 4) {
            init_crc = _mm_crc32_u32(init_crc, *(uint32_t*)(data + offset));
            offset += 4;
        }
        else if (remaining >= 2) {
            init_crc = _mm_crc32_u16(init_crc, *(uint16_t*)(data + offset));
            offset += 2;
        }
        else if (remaining >= 1) {
            init_crc = _mm_crc32_u8(init_crc, *(data + offset));
            offset += 1;
        }
    }
    return init_crc ^ 0xffffffff;
}

int main() {
    uint8_t data[] = {"test"};
    uint32_t crc = crc32(data, 4); //0x86a072c0
}