Алгоритм CRC16 Опции

[athlon64]

Устройство на sam7x должно обмениваться по uart пакетами длинной 76 байт + 2 байта CRC16 с программой на компьютере.
Исходника программы компа нет, но есть исходник (в icc) предыдущей версии рабочего устройства (правильно рассчитываеющего CRC и успешно обменивающегося с программой), из которого был взят фрагмент рассчёта CRC. По какой то причине CRC рассчитывается неверно.

Фрагмент для IAR:

Код

// пакет лежит в uart1_buffer
// len - длина пакета, по которому считается CRC (76 байт)
void CRC16(unsigned int len)
{   unsigned char i;
    unsigned int k;
    unsigned int CRC;

    CRC=k=0;
    while(k<len){
        CRC=CRC^((unsigned int)uart1_buffer[k++]<<8);
        i=8;
        do{
            if(CRC & 0x8000) CRC=(CRC<<1)^0x1021;
            else CRC=CRC<<1;
        } while(--i);
    }
// дописываем в конец буфера CRC16
    uart1_buffer[76]=CRC & 0xff;
    uart1_buffer[77]=(CRC>>8) & 0xff;
}

Для пакета

Код

0A 90 00 00 00 00 00 00 00 00 4F 33 40 40 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

CRC16 должна быть равна A1 01, а рассчитывается 0B D1, перепробовал ещё кучу стандартных алгоритмов, все рассчитывают новые CRC, но ни одна не посчитала A1 01. Голову сломал на этом затыке. Буду благодарен за любые мысли по проблеме

[athlon64]

Видимо то устройство, что работало, было 16-битное?
Попробуйте заменить unsigned int на unsigned short.

Устройство было на меге2561

Если перед расчётом CRC проинициализировать 0x6DA5 (вместо 0), то получится как-раз "A1 01" . Просто брутфорс . Исходник один в один скопировали?

да, брал исходник как есть

Всё разобрался, рядом с этой функцией лежала такая же с постфиксом New в имени , в которой алгоритм гораздо проще, опробовал - считает правильно:

Код

void SumCRCNew(unsigned int len)
{   unsigned char i;
    unsigned int CRC;

    CRC=0;
    for(i=0;i<76;i++) CRC+=uart1_buffer[i];
    uart1_buffer[76]=CRC & 0xff;
    uart1_buffer[77]=(CRC>>8) & 0xff;
}

Видимо для обмена по uart прошлым разработчикам пришлось упростить контроль целостности пакета, а я эту функцию проморгал
Всем отписавшимся огромное спасибо

[ASN]

athlon64
Видимо, это стандартный CRC16 для обмена по стыку IRDA. В Linux есть исходники расчёта CRC на С.Считается табличным методом.
Замена на сложение принципиально ухудшает обнаруживающую ошибки способность.

[vallav]

athlon64
Видимо, это стандартный CRC16 для обмена по стыку IRDA. В Linux есть исходники расчёта CRC на С.Считается табличным методом.
Замена на сложение принципиально ухудшает обнаруживающую ошибки способность.

Всегда интересовало - почему "Замена на сложение принципиально ухудшает обнаруживающую ошибки способность"?
Одиночные ошибки - одинаково. Обнаруживаются всегда.
Двойные - от статистики зависит. Если они часто в одном разряде, CRC лучше, если они независимы, сложение лучше.

[ASN]

vallav
Теорию не помню.
По опыту. Работаем в очень сложной помеховой обстановке. Сложение ошибок не обнаруживало, CRC - обнаруживало.

[vallav]

vallav
Теорию не помню.
По опыту. Работаем в очень сложной помеховой обстановке. Сложение ошибок не обнаруживало, CRC - обнаруживало.

Не очень понятно. Может - сложение иногда многкратных ошибок не обнаруживало ( пропускало пакет с ошибками ).
CRC пропускало пакет с ошибками в несколько раз реже.
Такое может быть, если многократные ошибки сильно и специфически коррелированы.

А вот чтобы - сложение всех ошибок не обнаруживало а CRC все ошибки обнаруживало - такое вряд ли.

[demiurg_spb]

Не очень понятно...

crcguide.pdf

[vallav]

crcguide.pdf

Вы к чему эту ссылку привели?
Там есть - как считать CRC, но там нет - чем CRC лучше простой суммы с той же разрядностью.
Кроме одного случая - в случае, когда двойные ошибки в одном разряде, CRC лучше.
А разве с этим кто либо спорил?

[demiurg_spb]

Там есть - как считать CRC, но там нет - чем CRC лучше простой суммы с той же разрядностью.

Вы что смеётесь? Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32, а для простой суммы на ПОРЯДКИ больше!!!
Вы что ещё до сих пор верите в благотворительность? То что просто заXORить массив намного менее затратно чем посчитать CRC я не спорю, но что-то мне подсказывает, что и вероятность пропуска ошибки примерно (прюс-минус трамвайная остановка, конечно) во столько же раз больше.
За всё надо платить - закон сохранения энергии, однако!

По крайней мере можно так:

Код

if (crc & 1)  
    crc = (crc >> 1) ^ 0xA001;
else
    crc = (crc >> 1);

Не, не моё это:-) Я либо в строку форматирую, либо уж по полной программе со скобочками.
К полумерам не привык! Два по сто в одной посуде!:)

[vallav]

Вы что смеётесь? Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32, а для простой суммы на ПОРЯДКИ больше!!!
Вы что ещё до сих пор верите в благотворительность? То что просто заXORить массив намного менее затратно чем посчитать CRC я не спорю, но что-то мне подсказывает, что и вероятность пропуска ошибки примерно (прюс-минус трамвайная остановка, конечно) во столько же раз больше.
За всё надо платить - закон сохранения энергии, однако!

Вы полагаете, это аргумент - все так делают, поэтому так делать - правильно?

Закон сохранения энергия вроде не гласит - чем больше энергии затрачено, тем лучше вещь получается...

Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32 - знаете, как считается?
Всего разных значений у 16 битного числа 2^16, если ошибка равновероятно порождает одно из значений, то вероятность, что она
породит нужное, равна 1 к 2^16.
Это справедливо для многобитной ошибки ( например, от мощной импульсной помехи ), но справедливо как для CRC, так и для прямой суммы.

Исторически CRC появилась по простой причине - в механических телетайпах основной ошибкой были сбои в одном из реле, что порождало
многократные ошибки в одном из разрядов. СRC тут намного лучше прямой суммы.
Но времена те ушли, а CRC осталось...

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

[Палыч]

Всего разных значений у 16 битного числа 2^16, если ошибка равновероятно порождает одно из значений, то вероятность, что она
породит нужное, равна 1 к 2^16.
Это справедливо для многобитной ошибки ( например, от мощной импульсной помехи ), но справедливо как для CRC, так и для прямой суммы.

Забыли добавить, что для простой суммы равновероятность пораждения одного из значений CRC имеет место при очень больших размерах блока

[vallav]

Забыли добавить, что для простой суммы равновероятность пораждения одного из значений CRC имеет место при очень больших размерах блока

Вы хотели сказать, при размерах поражения порядка длины контрольного слова?
То есть когда поражено несколько бит?

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

[Палыч]

Повторюсь - CRC лучше для двойных регулярных ошибок ( когда они в одном разряде ).

Интуитивно понятно, и - спору нет.

В остальных случаях - надо специально разбираться.

При длине блока даже в 256 байт простая сумма будет менее 2^16. Даже при бОльшей длине блока не будет выполняться равновероятность пораждения одного из значений CRC (ситуацию нЕсколько спасёт циклическая сумма). Для суммы: только при очень большой длине блока (строго говоря - бесконечной) это условие выполнится.

[vallav]

Интуитивно понятно, и - спору нет.
При длине блока даже в 256 байт простая сумма будет менее 2^16. Даже при бОльшей длине блока не будет выполняться равновероятность пораждения одного из значений CRC (ситуацию нЕсколько спасёт циклическая сумма). Для суммы: только при очень большой длине блока (строго говоря - бесконечной) это условие выполнится.

При длине блока в 4 байта простая сумма может быть больше, чем 2^16.
Или Вы хотите суммировать байты для получения 16 разрядной контрольной суммы?
Какой смысл - складывать в старший байт переносы?
Вроде при этом надо суммировать 16 разрядные слова.

Кстати, простая сумма не пропустит ни одного едеичного поражения длиной менее 17 бит.
CRC может пропустить ( от конкретного способа перемешивания бит зависит ).

[Палыч]

Или Вы хотите суммировать байты для получения 16 разрядной контрольной суммы?

Извините, но Вы так и делаете: получаете сумму значений 76 байт, а не 38 слов (см. функцию void SumCRCNew(unsigned int len) ).

P.S.Поправка: делает это athlon64, но Вы его решения защищаете

[vallav]

Извините, но Вы так и делаете: получаете сумму значений 76 байт, а не 38 слов (см. функцию void SumCRCNew(unsigned int len) ).

P.S.Поправка: делает это athlon64, но Вы его решения защищаете

С чего Вы взяли, что я настаиваю именно на таком вычислении контрольной суммы?
Я просто спросил - почему CRC лучше прямой суммы.
Вы согласны, что посчитать 16 битную сумму столь же просто, как и 8 битную?
И намного проще и быстрее, чем правильное 16 битное CRC?

Так что скажите для случая 16 битной суммы?

[ASN]

vallav
А вот с тем, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC несогласен.
На аппаратной логике практически любая CRC считается (и проверяется) "влёт". Не факт, что 16 битное сложение (и выше) будет легче.
Для быстрого расчёта на ЭВМ есть эффективные табличные методы вообще без арифметических операций (кроме XOR).

[Палыч]

А вот с тем, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC несогласен.

Действительно - есть методы ускоряющие расчет CRC... Но, имхо, скорость их работы не превысит скорости выполнения операции типа: Sum+=Data[i];
Впрочем, могу изменить своё мнение, если Вы приведете исходный текст и временные характеристики программ подсчета CRC, и программы подсчета простой суммы.

[ASN]

Палыч
Пример на аппаратной логике расчёта обсуждаемой CRC16 для однобитного входного потока:

Код

function nextCRC16
    (Data: std_logic;
       crc:  std_logic_vector(15 downto 0))
return std_logic_vector is

    variable d:      std_logic_vector(0 downto 0);
    variable c:      std_logic_vector(15 downto 0);
    variable newcrc: std_logic_vector(15 downto 0);

  begin
    d(0) := Data;
    c      := crc;
    newcrc(0) := d(0) xor c(15);
    newcrc(1) := c(0);
    newcrc(2) := c(1);
    newcrc(3) := c(2);
    newcrc(4) := c(3);
    newcrc(5) := d(0) xor c(4) xor c(15);
    newcrc(6) := c(5);
    newcrc(7) := c(6);
    newcrc(8) := c(7);
    newcrc(9) := c(8);
    newcrc(10) := c(9);
    newcrc(11) := c(10);
    newcrc(12) := d(0) xor c(11) xor c(15);
    newcrc(13) := c(12);
    newcrc(14) := c(13);
    newcrc(15) := c(14);
    return newcrc;
  end nextCRC16;

Требуется 16 триггеров. Не больше чем для простой суммы.

Расчёт для 8-ми битной ЭВМ табличным способом:

Код

void set_fcs(uint16 fcs_init, uint8 *buff, uint16 len)
{
while(len--)
     fcs_init = (fcs_init >> 8) ^ fcs_table[(fcs_init ^ *buff++)];
fcs_init ^= 0xFFFF;
*buff++ = (uint8)fcs_init;
*buff     = (uint8)(fcs_init>>8);}

Сложение 8 битного числа с 16 битным Sum+=*Data++ чуть быстрее.
Именно поэтому и не согласен, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC.
Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.