Здравствуйте, fk0, Вы писали:
N>>то у меня получается в самом коротком случае 3 байта испорченных, иногда 4, обычно же оно не находит случаев короче чем 8 байт. Для CRC-8 это очень хороший результат. А твой пример умудряется находить даже последовательности с изменением одного последнего байта, что заведомо показывает на ошибочность твоего кода (собственно почему я и стал рыть). fk0> Исправил. Так ведь получается. Вот пример для 1000 запусков:
Ничего неожиданного. Естественно, можно подобрать такие данные, что на них с подобной стандартной заменой получится "немного" не то, но с той же суммой.
Но для таких ситуаций надо вообще что-то принципиально другое придумывать, чем суммы. Я взял твой код и попытался сделать следующие варианты замен:
1) вместо CRC — младшие 8 бит суммы байт
2) то же но с переносом старшего бита в конец (не XOR, а добавлением) (в стиле IP?)
Результат удручает — ни одна сумма такой ситуации не ловит. Статистически лучше всего, похоже, просто младший байт суммы всех байт потока, но тоже качество обнаружения отвратительное.
Так что я бы тут не ругался на авторов идеи применить CRC. Чтобы ловить подобный клин приёмника или чужое вмешательство, нужно просто другое построение протокола. Например, фиксированный последний байт ответа, в котором и нули и единицы (типа 0x5a).
fk0> Это CRC с указанным полиномом и его результат для любых входных значений полностью совпадает с побитным алгоритмом CRC. Указанный полином на сайте smbus.org... Указанные коэффициенты для ксорки берутся из результатов вычисления таблицы CRC побитным алгоритмом и взятия каждого 2^N-го члена для N=0..7. Это оптимизированный алгоритм просто. И, кстати, на мелких контроллерах он может работать быстрее табличного (на гарвардских архитектурах доступ к данным в программной памяти -- медленный).
Я не про способ вычисления — понятно, что он подбирается под реализацию. А про собственно алгоритм. Впрочем, я уже нашёл как его логически описать: он эквивалентен классическому, но с добавлением ещё одного нулевого байта в конце входной последовательности.
fk0> Увы и ах. Именно так, именно для того он и предназначен. И в RS-232 будет замечательно работать. А где пакетная передача с обрывами посереди пакета и заполнением конца пакета одинаковым битом -- не канает CRC.
Как уже сказал — там никакая сумма "не канает" пока нет подтверждения собственно целостности канала.
fk0> Ничего подобного. Ситуация там такая: приём данных мастером, слейв отвалился по электрическим причинам (стоп-сигнал увидел и т.п.) На шине соответственно единица (обеспечивается резистором подтяжки) всё время. А мастер так уверенно читает все биты до конца пакета и *никак* не может знать, что слейв уже обмен закончил. Между байтами разделения в I2C нет, как и границ байтов в данном случае. В случае когда мастер записывал бы -- да, разделение есть, слейв должен на каждый байт ACKnowledge нулевым битом давать. А тут мастер должен ACK давать -- ну вот он и даёт, и читает дальше... Это в значительной степени проблема шины и протокола SMBUS (обязательный нулевой бит в конце пакета кардинально решал бы проблему).
Вот именно, что шины.
fk0> Кстати ещё пример неправильного применения CRC -- контрольный код записи в FLASH-памяти. Догадываешься уже почему? Ровно та же проблема. Массовое FF-чивание отдельных блоков. Контрольная сумма подходящей разрядности (весьма небольшой) опять же справляется гарантировано и это очевидно математически.
Нет. Модифицируй свою программу и проверь: точно так же не справляется.
Здравствуйте, netch80, Вы писали:
N>>>то у меня получается в самом коротком случае 3 байта испорченных, иногда 4, обычно же оно не находит случаев короче чем 8 байт. Для CRC-8 это очень хороший результат. А твой пример умудряется находить даже последовательности с изменением одного последнего байта, что заведомо показывает на ошибочность твоего кода (собственно почему я и стал рыть). fk0>> Исправил. Так ведь получается. Вот пример для 1000 запусков: N>Ничего неожиданного. Естественно, можно подобрать такие данные, что на них с подобной стандартной заменой получится "немного" не то, но с той же суммой. N>Но для таких ситуаций надо вообще что-то принципиально другое придумывать, чем суммы. Я взял твой код и попытался сделать следующие варианты замен: N>1) вместо CRC — младшие 8 бит суммы байт N>2) то же но с переносом старшего бита в конец (не XOR, а добавлением) (в стиле IP?)
N>Результат удручает — ни одна сумма такой ситуации не ловит. Статистически лучше всего, похоже, просто младший байт суммы всех байт потока, но тоже качество обнаружения отвратительное.
16-битная сумма в 256-байтном пакете (и более коротких) гарантированно ловит такие ситуации. Вроде ж очевидно. 16-битный CRC тоже их ловить не будет, хотя и с меньшей вероятностью.
fk0>> Это CRC с указанным полиномом и его результат для любых входных значений полностью совпадает с побитным алгоритмом CRC. Указанный полином на сайте smbus.org... Указанные коэффициенты для ксорки берутся из результатов вычисления таблицы CRC побитным алгоритмом и взятия каждого 2^N-го члена для N=0..7. Это оптимизированный алгоритм просто. И, кстати, на мелких контроллерах он может работать быстрее табличного (на гарвардских архитектурах доступ к данным в программной памяти -- медленный). N>Я не про способ вычисления — понятно, что он подбирается под реализацию. А про собственно алгоритм. Впрочем, я уже нашёл как его логически описать: он эквивалентен классическому, но с добавлением ещё одного нулевого байта в конце входной последовательности.
Да он полностью эквиэвалентен. Я ж написал -- я налажал в коде. И написал как исправить.
fk0>> Увы и ах. Именно так, именно для того он и предназначен. И в RS-232 будет замечательно работать. А где пакетная передача с обрывами посереди пакета и заполнением конца пакета одинаковым битом -- не канает CRC. N>Как уже сказал — там никакая сумма "не канает" пока нет подтверждения собственно целостности канала.
Когда в канале не произвольные искажения, а исключительно об 00-вание или об FF-чивание, то сумма соответствующей разрядности просто гарантирует.
fk0>> Кстати ещё пример неправильного применения CRC -- контрольный код записи в FLASH-памяти. Догадываешься уже почему? Ровно та же проблема. Массовое FF-чивание отдельных блоков. Контрольная сумма подходящей разрядности (весьма небольшой) опять же справляется гарантировано и это очевидно математически. N>Нет. Модифицируй свою программу и проверь: точно так же не справляется.
Это ж очевидно, что если в последовательности единиц и нулей часть последовательности заменить на единицы или нули, то сумма станет соответственно такой же или большей, или такой же (когда 0 заменяется на 0) или меньшей. Для одного разряда это так (проверь). И для каждого N+1 тоже (доказано). Если в сумме нет переполнений -- поэтому разрядность должна быть больше, чем log2(sum(все единицы)).
Здравствуйте, fk0, Вы писали:
N>>Результат удручает — ни одна сумма такой ситуации не ловит. Статистически лучше всего, похоже, просто младший байт суммы всех байт потока, но тоже качество обнаружения отвратительное. fk0> 16-битная сумма в 256-байтном пакете (и более коротких) гарантированно ловит такие ситуации. Вроде ж очевидно.
Ах, 16-битная при байтах... ну это уже приём за гранью допустимого. До сих пор контекстом были или IP пакеты (тогда и 16-битная не справится, надо 32), или SMBus (тогда шла речь про 8-битные). А если у тебя будут передачи длиннее 256 байт — что делать, до 32 расширять? Боюсь, обидятся на оверхед.
fk0>>> Кстати ещё пример неправильного применения CRC -- контрольный код записи в FLASH-памяти. Догадываешься уже почему? Ровно та же проблема. Массовое FF-чивание отдельных блоков. Контрольная сумма подходящей разрядности (весьма небольшой) опять же справляется гарантировано и это очевидно математически. N>>Нет. Модифицируй свою программу и проверь: точно так же не справляется.
fk0> Это ж очевидно, что если в последовательности единиц и нулей часть последовательности заменить на единицы или нули, то сумма станет соответственно такой же или большей, или такой же (когда 0 заменяется на 0) или меньшей. Для одного разряда это так (проверь). И для каждого N+1 тоже (доказано). Если в сумме нет переполнений -- поэтому разрядность должна быть больше, чем log2(sum(все единицы)).
И опять-таки у тебя должна быть очень большая контрольная сумма. Например, при записи порциями по 32 бита (чтобы было достаточно эффективно) в ней должно быть 40-48 бит. К тому же добавляется проблема проверки суммированием... боюсь, на сейчас выгоднее другие примеры применить. Например, RC при тех же недостатках с необходимостью последовательной обработки умеет корректировать данные, что явно важнее.
В общем, твой подход показателен как крайний вариант, но слабоприменим на практике — его можно сравнить с шифрованием с помощью шифроблокнота: надёжность абсолютная, но сопроводительного геморроя слишком много.
Как говорится: "для нас чужие проблемы только в радость."
Что сказать, неправильно сделали.
Протокол доделал. гоняет, правда медленно. работаю над менеджером пакетов. стараюсь учесть опыт tcp.
Основная же проблема в куче вариантов реализаций. Но в принципе, все логически просчитывается и достаточно легко создается простой вариант tcp.
Римское правило. Тот, кто говорит, что Это не может быть сделано, никогда не должен мешать тому, кто Это делает.
Осень, ну вы поняли.
Зачем еще один код? А человек?
Здравствуйте, LuciferSaratov, Вы писали:
LS>Эх, твою бы энергию да в мирных целях.
А вы еще не заметили, что цели мирные?
Римское правило. Тот, кто говорит, что Это не может быть сделано, никогда не должен мешать тому, кто Это делает.
Осень, ну вы поняли.
Зачем еще один код? А человек?
Здравствуйте, MikelSV, Вы писали:
MSV>Здравствуйте, LuciferSaratov, Вы писали:
LS>>Эх, твою бы энергию да в мирных целях. MSV>А вы еще не заметили, что цели мирные?
Какие уж там мирные. Скорее, бессмысленные и беспощадные.
