Сравнение CRC и отличия похожих алгоритмов

Я читал о CRC и наткнулся на каталог CRC и эту статью о CRC-CCITT.

Я реализовал MyCrc16 (код см. ниже) на основе второй ссылки.

Который просто берет байты по порядку, биты в обратном порядке и сдвигает их один за другим в (начальный) CRC, а затем XOR с полиномом, чтобы получить остатки, плюс увеличение в конце.

Теперь... У меня также была некоторая ранее существовавшая реализация CRC16 (OtherCrc16), которая, согласно каталогу, является CRC-16/CCITT-FALSE.

Чего я не понимаю, так это почему OtherCrc16 работает? поскольку первый байт ввода и все остальные после него подвергаются операции XOR с (начальным) CRC, а не добавляются к нему, как в другой реализации. И когда он перебирает биты, он не принимает во внимание то, что первый алгоритм считает «сдвигом ввода в CRC», вместо этого он просто XOR с полиномом, если это необходимо.

Я пропустил какое-то свойство операции XOR? На мой взгляд, два алгоритма должны иметь одинаковый результат (конечно, не учитывая увеличение первого), но это не так.

#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


c algorithm crc16
person Paul    schedule 28.11.2016    source источник
comment
Прочтите руководство Росса Уильямса по CRC.   -  person Mark Adler    schedule 29.11.2016
comment
Я сделал, я до сих пор не понимаю, почему это отличается, когда сначала XOR вводит сообщение в CRC...   -  person Paul    schedule 29.11.2016
comment
Вы имеете в виду, что до сих пор не можете понять, почему это то же самое. Это очень хорошо и подробно объяснено в разделе 10. Слегка искаженная табличная реализация в учебнике CRC.   -  person Mark Adler    schedule 30.11.2016
comment
@MarkAdler - другое дело, если начальное значение CRC не равно 0x0000.   -  person rcgldr    schedule 27.07.2019

Ответы (1)


arrow_upward
2
arrow_downward

Если начальное значение CRC равно нулю, то оба метода производят один и тот же CRC. Однако, если начальное значение CRC не равно нулю, то MyCrc16 циклически повторяет это начальное значение 16 раз, прежде чем начнет включать любые биты данных, как если бы перед данными стояли 16 нулевых битов. Для ненулевого начального CRC, MyCrc16 требует, чтобы начальное значение перевернулось 16 раз, чтобы после того, как начальное значение было циклически перевернуто 16 раз, оно совпадало с начальным значением, используемым в OtherCrc16. Для начального значения 0xffff повторный цикл 16 раз приводит к 0x84cf. Следующее изменение, отмеченное в комментарии, приведет к тому, что два метода создадут один и тот же CRC:

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