CRC相似算法的比较与差异

Question

我在读关于CRCs，我偶然发现了CRC目录和这篇关于CRC-CCITT的文章。

我基于第二个链接实现了mycrc16（参见下面的代码）。

我是不是遗漏了异或运算的一些属性？在我看来，这两个算法应该有相同的输出（当然不考虑第一个算法的增强），但它们没有。

#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

uint16_t MyCrc16(const unsigned char *data, int length, uint16_t poly, uint16_t crc)
{
        for(int byte=0; byte<length; ++byte)
        {
                for(int bit=7; bit>=0; --bit)
                {
                        bool doXor = false;
                        if(crc & 0x8000)
                        {
                                doXor = true;
                        }
                        crc <<= 1;
                        if(data[byte] & (1 << bit))
                        {
                                crc += 1;
                        }
                        if(doXor)
                        {
                                crc ^= poly;
                        }
                }
        }

        //augument the crc with 0s
        for(int i=0; i<16; i++)
        {
                bool doXor = false;
                if(crc & 0x8000)
                {
                        doXor = true;
                }

                crc = crc << 1;
                if(doXor)
                {
                        crc ^= poly;
                }
        }

        return crc;
}

uint16_t OtherCrc16(const unsigned char *data, int length, uint16_t poly, uint16_t crc)
{
        for(int i=0; i<length; i++)
        {
                crc = crc ^ (data[i] << 8);
                for (int bit = 0; bit< 8; bit++)
                {
                        bool doXor = false;
                        if(crc & 0x8000)
                        {
                                doXor = true;
                        }
                        crc <<=1;

                        if(doXor)
                        {
                                crc ^= poly;
                        }
                }
        }
        return crc;
}


int main(void) {
    // your code goes here
    uint16_t poly = 0x1021;

    unsigned char c[] = "123456789";
    printf("My CRC = %04x\n", MyCrc16(c, 9, poly, 0xffff));
    printf("Other CRC = %04x\n", OtherCrc16(c, 9, poly, 0xffff));
    return 0;
}

PS：可执行代码：http://ideone.com/mkuqqq

Answer 1

如果CRC的初始值为零，则两种方法产生相同的CRC。但是，如果CRC的初始值是非零，那么MyCrc16在开始包括任何数据位之前循环该初始值16次，就像它用16个零位作为数据前缀一样。对于一个非零的初始CRC，MyCrc16需要将初始值反转16次，因此在将初始值向前循环16次后，它与其他CRC16中使用的初始值相同。对于初始值为0xFFFF，反向循环16次得到0x84CF。评论中指出的以下变化将导致两种方法产生相同的儿童权利公约：

    printf("My CRC = %04x\n", MyCrc16(c, 9, poly, 0x84cf));  /* change to 0x84cf */
    printf("Other CRC = %04x\n", OtherCrc16(c, 9, poly, 0xffff));