CRC逐字节异或多项式除法实现CRC-16-IBM结果错误排查

伪代码核心逻辑拆解 #

维基百科给出的是MSB优先、无反射、无初始/最终异或的基础CRC逐字节实现，原始代码如下：

function crc(byte array string[1..len], int len) {
    remainderPolynomial := 0
    // A popular variant complements remainderPolynomial here; see § Preset to −1 below
    for i from 1 to len {
        remainderPolynomial := remainderPolynomial xor polynomialForm(string[i]) * xn−8
        for j from 1 to 8 {    // Assuming 8 bits per byte
            if coefficient of xn−1 of remainderPolynomial = 1 {
                remainderPolynomial := (remainderPolynomial * x) xor generatorPolynomial
            } else {
                remainderPolynomial := (remainderPolynomial * x)
            }
        }
    }
    // A popular variant complements remainderPolynomial here; see § Post-invert below
    return remainderPolynomial
}

逐行对应逻辑说明：

• remainderPolynomial := 0：初始化CRC寄存器，值对应CRC参数中的Init字段，CRC-16-IBM该值为0x0000
• 外层字节遍历：remainderPolynomial xor polynomialForm(string[i]) * x^(n-8)：n为CRC位宽（16），即把当前输入字节左移8位对齐到CRC寄存器高8位后做异或，实现逐字节提前异或，无需逐位移动输入比特
• 内层比特遍历：每次将寄存器左移1位（对应多项式乘x），如果移出的最高位（16位CRC对应第15位，值0x8000）为1，就和生成多项式做异或，完成模2除法
• 两处注释位置：第一处对应初始值取反（适配Init为全1的CRC变种），第二处对应结果最终异或（适配XorOut参数）

注：你之前需要手动给输入补16位零才能得到正确结果，本质是未适配反射配置、且误将多项式除法的理论步骤（输入末尾补width位0再做除法）直接实装到了输入处理中，常规CRC实现会将这一步骤整合到寄存器迭代逻辑内，不需要修改原始输入数组。

实现校验失败的核心原因 #

按照伪代码直接编写的版本无法得到0xBB3D校验值，是因为遗漏了CRC-16-IBM要求的反射配置：

• RefIn=True：所有输入字节需要按位反转后再参与计算，即按LSB优先顺序处理比特，而非伪代码默认的MSB优先
• RefOut=True：最终计算得到的16位寄存器值需要整体按位反转后输出
• 左移/右移逻辑需要和反射配置匹配，无反射用左移迭代，反射实现可选择左移+位反转，或直接用右移迭代搭配反转后的多项式

适配CRC-16-IBM的无查表可运行实现 #

以下Python代码完全对齐维基百科伪代码逻辑，无查表、实现极简，可直接移植到微控制器汇编，传入原始字节数组即可得到正确校验值：

def reverse_bits(val: int, bits: int) -> int:
    """按位反转数值，适配RefIn/RefOut配置"""
    res = 0
    for _ in range(bits):
        res = (res << 1) | (val & 1)
        val >>= 1
    return res

def crc16_ibm(data: bytearray) -> int:
    # CRC-16-IBM标准参数
    width = 16
    poly = 0x8005
    init = 0x0000
    ref_in = True
    ref_out = True
    xor_out = 0x0000
    mask = (1 << width) - 1   # 16位寄存器掩码，防止移位溢出
    msb_flag = 1 << (width-1) # 最高位判断标志

    crc_reg = init
    for byte in data:
        # 处理输入反射
        if ref_in:
            byte = reverse_bits(byte, 8)
        # 逐字节异或到寄存器高8位
        crc_reg ^= (byte << (width - 8))
        # 逐位处理8个比特
        for _ in range(8):
            if crc_reg & msb_flag:
                crc_reg = ((crc_reg << 1) ^ poly) & mask
            else:
                crc_reg = (crc_reg << 1) & mask
    # 处理输出反射
    if ref_out:
        crc_reg = reverse_bits(crc_reg, width)
    # 处理最终异或
    return crc_reg ^ xor_out

# 标准校验测试
if __name__ == "__main__":
    test_data = bytearray(b"123456789")
    calc_result = crc16_ibm(test_data)
    print(f"计算得到CRC值：0x{calc_result:04X}")
    assert calc_result == 0xBB3D, "校验值不匹配"
    print("标准校验通过")

移植与扩展说明 #

• 汇编移植仅需2字节RAM存储CRC寄存器，不需要额外空间存储查表，代码量极小，适合资源受限的微控制器场景
• 如果偏好右移实现（汇编中判断进位标志更方便），可将多项式替换为位反转后的0xA001，循环中改为右移操作、判断最低位决定是否异或多项式，可省略最终输出反转步骤，执行效率与左移版本完全一致
• 该实现框架可适配所有标准CRC，仅需修改顶部的位宽、多项式、初始值、反射开关、最终异或值参数即可

内容的提问来源于stack exchange，提问作者martin's