CRC计算：带有字节消息XOR-ing的多项式划分？

Question

试图从以下Wikipedia页面中的“代码片段3”中了解这一点的伪代码中的含义：

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
}

文章指出：

在软件中，很方便地注意到，虽然可以将每个位的XOR延迟到最后一刻，但也可以更早地进行。通常，即使在这样的时间实现中，一次执行XOR A字节也很方便：

好的，这听起来很棒。我需要在微控制器上实现CRC-16-IBM，并且不愿使用查找表方法（尽管性能缺点）。探索字节XOR计算的这种可能性，而不是咬合会很有趣。但是，我不太了解它们的意思。

虽然代码将写在汇编器中，但我正在使用Python来探索想法并了解所有细节。据我所知，这是CRC-16代码，据我所知，返回正确的值：

# Flip the bits of an integer
# It will only flip the lower <bits> bits
def flip(x:int, bits:int=16):
    result = 0
    for i in range(bits):  # Reflect reg
        result <<= 1
        temp = x & (0x0001 << i)
        if temp:
            result |= 0x0001
    return result

def test_flip():
    n = 0b1100_1000

    bits = 8
    print(f"\nin: {n:0{bits}b}")
    print(f"out:{flip(n, bits):0{bits}b}")

    bits = 16
    print(f"\nin: {n:0{bits}b}")
    print(f"out:{flip(n,bits):0{bits}b}")

# test_flip()


def crc16(data:bytearray,
            poly:int=0x8005,
            init:int=0x0000,
            ref_in:bool=True,
            ref_out:bool=True,
            xor_out:int=-0x0000,
            debug:bool=False,
            disable_poly_xor:bool=False):
    reg = init                        # Initial CRC value
    for byte in data:                 # For each byte..
        if not ref_in:                # Reflect the input if necessary
            byte = flip(byte, 8)

        for i in range(8):            # Process all 8 bits one at a time
            reg <<= 1                 # Shift register left by one bit

            reg |= byte & 0x01      # Shift data each bit into the register on at a time
                                    # LSB first, unless input is NOT reflected

            if not disable_poly_xor:
                if reg & 0x010000:    # If a 1 shifts out of the 16 bit register,
                    reg ^= poly       # xor with polynomial

            byte >>= 1                # Prepare next bit to shift into register

            if debug:
                reg_str = f"{reg:032b}"
                print(f"{reg_str[-17:-16]} {reg_str[-16:-12]} {reg_str[-12:-8]} {reg_str[-8:-4]} {reg_str[-4:]} < {byte:08b}")

        if debug: print()
        reg &= 0xFFFF                 # This isn't a 16 bit hardware register, get rid of the excess

    if ref_out:
        return flip(reg, 16) ^ xor_out
    else:
        return reg ^ xor_out


# Checking implementations
check_data = bytearray(b"123456789\x00\x00")
check_result_should_be = 0xBB3D

print(f"\ndata: {[hex(n) for n in check_data]}")
print(f"expected CRC: {check_result_should_be: 04x}")

print()

print(f"crc16: {crc16(check_data, ref_in=False, ref_out=False): 04x}")
print(f"crc16: {crc16(check_data, ref_in=False, ref_out=True): 04x}")
print(f"crc16: {crc16(check_data, ref_in=True,  ref_out=False): 04x}")
print(f"crc16: {crc16(check_data, ref_in=True,  ref_out=True): 04x}")

我遵循此参考文档以产生您在上面看到的实现：

https://zlib.net/crc_v3.txt

我已经浏览了许多语言中的许多CRC实现（包括此处的许多语言）。我还没有看到一个将零附加到数据上的单个，因为论文似乎表明是必要的。我上面的测试数据是 bytearray（b“ 123456789”），但我用16位零填充了它。没有那个，我将无法获得正确的CRC输出值。

根据该论文，我正在实现的CRC-16-IBM版本应输出 0xbb3d ，这正是我在ref_in和ref_out设置为true时得到的。

这将我带到了Wikipedia Bytewise Xor pseudocode。这是我解释伪代码的方式：

def crc16_1(data:bytearray,
            poly:int=0x8005,
            init:int=0x0000,
            ref_in:bool=True,
            ref_out:bool=True,
            xor_out:int=-0x0000,
            debug:bool=False,
            disable_poly_xor:bool=False):
    reg = init                        # Initial CRC value
    for byte in data:                 # For each byte..
        if not ref_in:                # Reflect the input if necessary
            byte = flip(byte, 8)

        reg ^= byte

        for i in range(8):            # Process all 8 bits one at a time
            if not disable_poly_xor:
                if reg & 0x8000:    # If a 1 is going to shift out of the 16 bit register,
                    reg <<= 1
                    reg ^= poly     # xor with polynomial
                else:
                    reg <<= 1       # Shift register left by one bit

            if debug:
                reg_str = f"{reg:032b}"
                print(f"{reg_str[-17:-16]} {reg_str[-16:-12]} {reg_str[-12:-8]} {reg_str[-8:-4]} {reg_str[-4:]} < {byte:08b}")

        if debug: print()
        reg &= 0xFFFF                 # This isn't a 16 bit hardware register, get rid of the excess

    if ref_out:
        return flip(reg, 16) ^ xor_out
    else:
        return reg ^ xor_out

将其添加到我的测试中：

# Checking implementations
check_data = bytearray(b"123456789\x00\x00")
check_result_should_be = 0xBB3D

print(f"\ndata: {[hex(n) for n in check_data]}")
print(f"expected CRC: {check_result_should_be: 04x}")

print()

print(f"crc16: {crc16(check_data, ref_in=False, ref_out=False): 04x}")
print(f"crc16: {crc16(check_data, ref_in=False, ref_out=True): 04x}")
print(f"crc16: {crc16(check_data, ref_in=True,  ref_out=False): 04x}")
print(f"crc16: {crc16(check_data, ref_in=True,  ref_out=True): 04x}")

print()

print(f"crc16_1: {crc16_1(check_data, ref_in=False, ref_out=False): 04x}")
print(f"crc16_1: {crc16_1(check_data, ref_in=False, ref_out=True): 04x}")
print(f"crc16_1: {crc16_1(check_data, ref_in=True,  ref_out=False): 04x}")
print(f"crc16_1: {crc16_1(check_data, ref_in=True,  ref_out=True): 04x}")

我得到：

data: ['0x31', '0x32', '0x33', '0x34', '0x35', '0x36', '0x37', '0x38', '0x39', '0x0', '0x0']
expected CRC:  bb3d

crc16:  fee8
crc16:  177f
crc16:  bcdd
crc16:  bb3d

crc16_1:  5e8b
crc16_1:  d17a
crc16_1:  6a07
crc16_1:  e056

这是不正确的。

我希望有人可以帮助我了解如何从伪代码到可以超过此或任何其他CRC配置的简单测试的真实代码。我要实现的CRC算法的定义是（也是从链接的纸张中）：

Name   : "CRC-16"
Width  : 16
Poly   : 8005
Init   : 0000
RefIn  : True
RefOut : True
XorOut : 0000
Check  : BB3D

底部的检查值是我用来确保我的代码正常工作的方法。

我还看一下本文档的第40页的Modbus CRC实现：

这是我的实现：

def crc16_2(data:bytearray,
            poly:int=0x8005,
            init:int=0x0000,
            ref_in:bool=True,
            ref_out:bool=True,
            xor_out:int=-0x0000,
            debug:bool=False,
            disable_poly_xor:bool=False):
    reg = init                        # Initial CRC value
    for byte in data:                 # For each byte..
        if not ref_in:                # Reflect the input if necessary
            byte = flip(byte, 8)

        reg ^= byte

        for i in range(8):            # Process all 8 bits one at a time
            if not disable_poly_xor:
                if reg & 0x0001:    # If a 1 is going to shift out of the 16 bit register,
                    reg >>= 1
                    reg ^= poly     # xor with polynomial
                else:
                    reg >>= 1       # Shift register left by one bit

            if debug:
                reg_str = f"{reg:032b}"
                print(f"{reg_str[-17:-16]} {reg_str[-16:-12]} {reg_str[-12:-8]} {reg_str[-8:-4]} {reg_str[-4:]} < {byte:08b}")

        if debug: print()
        reg &= 0xFFFF                 # This isn't a 16 bit hardware register, get rid of the excess

    if ref_out:
        return flip(reg, 16) ^ xor_out
    else:
        return reg ^ xor_out

请注意，它们可以翻转多项式并向右移动，而不是向左移动。他们一次做一个字节，这很有趣。

再一次，没有配置会产生预期的CRC值：

data: ['0x31', '0x32', '0x33', '0x34', '0x35', '0x36', '0x37', '0x38', '0x39', '0x0', '0x0']
expected CRC:  bb3d

crc16:  fee8 < correct
crc16:  177f < correct
crc16:  bcdd < correct
crc16:  bb3d < correct

crc16_1:  5e8b
crc16_1:  d17a
crc16_1:  6a07
crc16_1:  e056

crc16_2:  295
crc16_2:  a940
crc16_2:  44ad
crc16_2:  b522

编辑：

这是Mark Adler贡献的非常好的资源：

https://github.com/madler/crcany

Answer 1

我只有Python 2.7。这似乎有效。

    def flip(x=0, bits=16):
        result = 0
        for i in range(bits):  # Reflect reg
            result <<= 1
            temp = x & (0x0001 << i)
            if temp:
                result |= 0x0001
        return result
    
    def crc16(bytearray,
                poly=0x8005,
                init=0x0000,
                ref_in=True,
                ref_out=True,
                xor_out=0x0000):
        reg = init
        for byte in data:
            if ref_in:
                byte = flip(byte, 8)
            reg ^= byte << 8
            for i in range(8):
                if reg & 0x08000:
                    reg = (reg << 1) ^ poly
                else:
                    reg = (reg << 1)
                reg &= 0xffff
        if ref_out:
            return flip(reg, 16) ^ xor_out
        else:
            return reg ^ xor_out
    
    data = [0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39]
    
    print('0x%04x' % crc16(data, 0x8005, 0x0000, True, True, 0x0000))

---

由于此处的目标是反射的CRC16，因此这是一个更简单的右移动CRC函数，它消除了钻头的需要。这意味着正确的大多数数据和CRC寄存器是逻辑上最重要的位。多项式也从0x8005到0xA001反映。

def crc16r(bytearray,
            poly=0xa001,
            init=0x0000,
            xor_out=0x0000):
    reg = init
    for byte in data:
        reg ^= byte
        for i in range(8):
            if reg & 0x0001:
                reg = (reg >> 1) ^ poly
            else:
                reg = (reg >> 1)
    return reg ^ xor_out

data = [0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39]

print('0x%04x' % crc16r(data, 0xa001, 0x0000, 0x0000))

Answer 2

在您链接的论文中，这一切都很好。我不确定您阅读了整个内容，因为它可以解释为什么以及如何与零在实施中使用零。它还解释了整个字节中的专有性以及如何专用于CRC的工作，而不是一次。

无论如何，您的问题是您没有反映反射CRC的多项式。 0x8005 变为 0a001 。

def crc16(data):
    crc = 0
    for byte in data:
        crc ^= byte
        for _ in range(8):
            crc = (crc >> 1) ^ 0xa001 if crc & 1 else crc >> 1
    return crc

print(hex(crc16(b'123456789')))

印刷：

0xbb3d