Checksum 和 CRC 位置的区别。为什么？

Question

我在学习CRC和校验和时遇到一个问题。

CRC位于尾部，而校验和位于头部。 我想是因为 CRC 和校验和的复杂性。 CRC 比较复杂，所以它定位到 header，但是 checksum 不太复杂，所以它定位到 tail。 是吗？

这是为什么？

Answer 1

在发送或接收数据的情况下，硬件实现通常会在发送数据时生成 CRC 或校验和，然后发送 CRC 或校验和（因此 CRC 或校验和将位于数据末尾）。这样就不需要缓冲比保存 CRC 或校验和以及传输单元（例如字节）更多的内容。

对于内存中的消息，CRC 奇偶校验字节或校验和可以位于消息内的任何位置。对于校验和，这是直接的，但对于 CRC，必须正常生成 CRC，然后向后循环并存储到它将位于消息中的位置。可以优化向后循环，如我答案的第二部分所示。

---

校验和可以位于消息中的任何位置，因为计算很容易。

英特尔十六进制格式是一种相当常见的格式，用于在文本文件中存储二进制数据，并且在文本文件的每一行数据末尾后都有校验和：

https://en.wikipedia.org/wiki/Intel_HEX#Record_struct

IPv4 标头将校验和放在 message_word[5] 上：

https://en.wikipedia.org/wiki/IPv4_header_checksum#Calculate_the_IPv4_header_checksum

---

消息中的任何位置都可以包含 CRC 奇偶校验。奇偶校验字节被清零，计算正常的 CRC，然后将 CRC“反向循环”到将存储它的位置。可以使用无进位乘法，而不是实际反转 CRC：

parity = (crc · (pow(2,-1-reverse_distance)%poly))%poly

-1代表CRC的循环周期。对于 CRC32，周期为 2^32-1 = 0xffffffff

32 字节消息的示例代码，包含 14 个数据字节、4 个奇偶校验字节、14 个数据字节。奇偶校验字节存储在消息中后，对消息进行正常的 CRC 计算将为零。

#include <stdio.h>

typedef unsigned char       uint8_t;
typedef unsigned int       uint32_t;

static uint32_t crctbl[256];

void GenTbl(void)                       /* generate crc table */
{
uint32_t crc;
uint32_t c;
uint32_t i;
    for(c = 0; c < 0x100; c++){
        crc = c<<24;
        for(i = 0; i < 8; i++)
            crc = (crc<<1)^((0-(crc>>31))&0x04c11db7);
        crctbl[c] = crc;
    }
}

uint32_t GenCrc(uint8_t * bfr, size_t size) /* generate crc */
{
uint32_t crc = 0u;
    while(size--)
        crc = (crc<<8)^crctbl[(crc>>24)^*bfr++];
    return(crc);
}

/* carryless multiply modulo crc */
uint32_t MpyModCrc(uint32_t a, uint32_t b) /* (a*b)%crc */
{
uint32_t pd = 0;
uint32_t i;
    for(i = 0; i < 32; i++){
        pd = (pd<<1)^((0-(pd>>31))&0x04c11db7u);
        pd ^= (0-(b>>31))&a;
        b <<= 1;
    }
    return pd;
}

/* exponentiate by repeated squaring modulo crc */
uint32_t PowModCrc(uint32_t p)          /* pow(2,p)%crc */
{
uint32_t prd = 0x1u;                    /* current product */
uint32_t sqr = 0x2u;                    /* current square */
    while(p){
        if(p&1)
            prd = MpyModCrc(prd, sqr);
        sqr = MpyModCrc(sqr, sqr);
        p >>= 1;
    }
    return prd;
}

/*  message 14 data, 4 parities, 14 data */
/*  parities = crc cycled backwards 18 bytes */

int main()
{
uint32_t pmr;
uint32_t crc;
uint32_t par;
uint8_t msg[32] = {0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,
                   0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x00,0x00,
                   0x00,0x00,0x13,0x14,0x15,0x16,0x17,0x18,
                   0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,0x20};

    GenTbl();                           /* generate crc table */
    pmr = PowModCrc(-1-(18*8));         /* pmr = pow(2,-1-18*8)%crc */
    crc = GenCrc(msg, 32);              /* generate crc */
    par = MpyModCrc(crc, pmr);          /* par = (crc*pmr)%crc */
    msg[14] = (uint8_t)(par>>24);       /* store parities in msg */
    msg[15] = (uint8_t)(par>>16);
    msg[16] = (uint8_t)(par>> 8);
    msg[17] = (uint8_t)(par>> 0);
    crc = GenCrc(msg, 32);              /* crc == 0 */
    printf("%08x\n", crc);

    return 0;
}

Answer 2

您能帮我在垃圾箱中找到校验和吗？