Здравствуйте, netch80, Вы писали:

N>Здравствуйте, fk0, Вы писали:

fk0>> Пример ниже. Прекрасно видно, что на случайных данных, на совершенно разных последовательностях (случайных), даже на коротких (несколко байт) пакетах можно нарваться на ситуацию, когда CRC совпадает, а хвост пакета (а то и весь пакет!) испорчен нулём или FF. Позапускай программу несколько раз (./a.out | less). Что характерно -- CRC должен быть равен заполняющему (всё портящему) байту. Так вот в реальном приборе, где проблемы были, там, догадайся...

N>Во-первых, с самого начала: твой пример попросту с багом. Если его исправить как следует:
N>- ncrc=crc_byte(copy[n], crc);
N>+ ncrc=crc_byte(copy[n], ncrc);

N>то у меня получается в самом коротком случае 3 байта испорченных, иногда 4, обычно же оно не находит случаев короче чем 8 байт. Для CRC-8 это очень хороший результат. А твой пример умудряется находить даже последовательности с изменением одного последнего байта, что заведомо показывает на ошибочность твоего кода (собственно почему я и стал рыть).

Исправил. Так ведь получается. Вот пример для 1000 запусков:

$ (for x in `seq 1000`; do ./a.out | grep -m1 length; done) | sort -u
length=  4, tail=  2, fill=00, crc=88
length=  4, tail=  4, fill=FF, crc=DE
length=  5, tail=  2, fill=FF, crc=F0
length=  6, tail=  2, fill=FF, crc=82
length=  6, tail=  6, fill=00, crc=00
length=  7, tail=  3, fill=00, crc=52
length=  7, tail=  4, fill=00, crc=51
length=  7, tail=  5, fill=FF, crc=68
length=  7, tail=  6, fill=FF, crc=FA
length=  8, tail=  5, fill=FF, crc=61
length=  8, tail=  6, fill=FF, crc=4A
length=  8, tail=  7, fill=00, crc=5E
length=  9, tail=  7, fill=00, crc=5B
...

Как и ожидалось, ошибки не может быть только для однобайтовых пакетов. К слову, функция crc_byte здесь применена медленная (побитная) на всякий случай.


N>Далее по частям программы:

fk0>>/* compute CRC-8 for SMBUS (x^8 + x^2 + x + 1) */
fk0>>uint_fast8_t crc_byte(uint_fast8_t byte, uint_fast8_t crc)
fk0>>{
fk0>>uint_fast8_t b;
fk0>> b=byte^crc;
fk0>> if (b&(1<<0)) crc^=0x7;
fk0>> if (b&(1<<1)) crc^=0xe;
fk0>> if (b&(1<<2)) crc^=0x1c;
fk0>> if (b&(1<<3)) crc^=0x38;
fk0>> if (b&(1<<4)) crc^=0x70;
fk0>> if (b&(1<<5)) crc^=0xe0;
fk0>> if (b&(1<<6)) crc^=0xc7;
fk0>> if (b&(1<<7)) crc^=0x89;
fk0>> return crc;
fk0>>}
N>Не знаю, что ты здесь хотел нарисовать, но это никак не CRC в обычном понимании.

Это CRC с указанным полиномом и его результат для любых входных значений полностью совпадает с побитным алгоритмом CRC. Указанный полином на сайте smbus.org... Указанные коэффициенты для ксорки берутся из результатов вычисления таблицы CRC побитным алгоритмом и взятия каждого 2^N-го члена для N=0..7. Это оптимизированный алгоритм просто. И, кстати, на мелких контроллерах он может работать быстрее табличного (на гарвардских архитектурах доступ к данным в программной памяти -- медленный).

Тут закралась действительно ошибка и CRC считается неправильно:

 uint_fast8_t crc_byte(uint_fast8_t byte, uint_fast8_t crc)
 {
 uint_fast8_t b;
         b=byte^crc;
+        crc=0;
         if (b&(1<<0)) crc^=0x7;

Это патч какбы.

N>В обычном было бы примерно так:

Вот он, гарантированно работающий, но медленный (к слову, в приборе был он, не оптимизированный):

uint_fast8_t smbus_crc_byte(uint_fast8_t byte, uint_fast8_t crc)
{
uint_fast8_t y=8;
        do {
                if ((byte^crc)&0x80) crc<<=1, crc^=0x7;
                        else crc<<=1;
                byte<<=1;
        } while (--y);
        return crc;
}

Результаты вычислений совпадают (после исправления crc=0).

N>Может, твой код преобразуется в то, что делается по классике, но тут получается как минимум смещение на байт, и я с ходу не берусь предсказать результаты этого смещения и степень устойчивости результата.

См. выше, моя ошибка. Алгоритм переделывался с другого, для Maxim (бывший Dallas) 1-Wire, там биты в другую сторону сдвигаются, оттого и...

N>Откуда код? Ты это взял из спецификации SMBus? Кстати, там точно передача начинается со старшего бита?

Там точно (в I2C вообще) передача 7-м битом вперёд. Вот в 1-Wire -- наоборот, начиная с младшего.
IMHO начиная со старшего правильнее. Их удобнее на осциллографе разглядывать -- сразу можно в голове байт сложить...

fk0>> Вообще-то CRC считается и бестабличными методами достаточно быстро, если такая задача стоит. Опять же смотри пример. Все возражения "почему не 16-32 бита" -- потому что блоки не по 4 килобайта, а по десятку байт. А 16 бит принципиально ситуацию тут не изменит вообще.
N>Думаю, таки изменит. Не зря на Ethernet при типичном размере пакета в пару сотен байт уже применялся CRC-32.

N>Но твоя ситуация вообще-то показывает контекст не для CRC. CRC предназначен для случаев именно одиночных независимых искажений потока (изменения битов, выпадения/добавления целых байт).

Увы и ах. Именно так, именно для того он и предназначен. И в RS-232 будет замечательно работать. А где пакетная передача с обрывами посереди пакета и заполнением конца пакета одинаковым битом -- не канает CRC.

N> Причём на SMBus, аналогично RS-232, невозможно держать AFAIK линию данных всё время на одном уровне — потому что тогда не будут видны границы байтов. Ситуация, когда хвост пакета целиком становится битами одного значения, означает сбой уже в кодере или декодере протокола, а не помеху/сбой на линии. Такие вещи должны отлавливаться на другом уровне и обвинять CRC в их неотлове — нелепость.

Ничего подобного. Ситуация там такая: приём данных мастером, слейв отвалился по электрическим причинам (стоп-сигнал увидел и т.п.) На шине соответственно единица (обеспечивается резистором подтяжки) всё время. А мастер так уверенно читает все биты до конца пакета и *никак* не может знать, что слейв уже обмен закончил. Между байтами разделения в I2C нет, как и границ байтов в данном случае. В случае когда мастер записывал бы -- да, разделение есть, слейв должен на каждый байт ACKnowledge нулевым битом давать. А тут мастер должен ACK давать -- ну вот он и даёт, и читает дальше... Это в значительной степени проблема шины и протокола SMBUS (обязательный нулевой бит в конце пакета кардинально решал бы проблему).

N>Если ты хочешь проверить CRC на корректность детекта в условиях, в которых он предназначен работать — меняй произвольно 1 из ~100 байтов не обязательно в хвосте.

Если я поменяю 1 байт -- CRC-8 это всегда обнаружит. Надо 2 менять.

Кстати ещё пример неправильного применения CRC -- контрольный код записи в FLASH-памяти. Догадываешься уже почему? Ровно та же проблема. Массовое FF-чивание отдельных блоков. Контрольная сумма подходящей разрядности (весьма небольшой) опять же справляется гарантировано и это очевидно математически. Хотя и не справляется так хорошо с единичными сбоями, как CRC.