Что является более быстрой альтернативой CRC?

27

Я делаю некоторую передачу данных от dsPIC к ПК, и я делаю 8-битный CRC для каждого блока 512 байтов, чтобы убедиться, что нет ошибок. При включенном коде CRC я получаю около 33 КБ / с, без него - 67 КБ / с.

Какие есть альтернативные алгоритмы обнаружения ошибок, чтобы проверить, что будет быстрее?

FigBug
источник
5
Как осуществляется сам CRC? Побитовое? Затем переключитесь на табличный метод. Побайтно? Рассмотрим пространство, сложность и время, необходимое для увеличения размера таблицы, скажем, до 16 бит (который будет работать с двумя байтами одновременно, но займет 64 КБ памяти таблицы).
Эйдан Калли
У меня только 16 КБ в ОЗУ и 128 КБ в ПЗУ, поэтому таблица размером 64 КБ не подходит.
FigBug
1
Итак, вы используете 256-байтовую таблицу? или побитовый CRC? Если вы делаете побитовый, побайтный (с 256-байтовой таблицей) будет в 8 раз быстрее.
Эйдан Калли
По битам сейчас попробую 256 таблиц
FigBug
1
67 кбит / с до 33 кбит / с? Я не уверен, что включает в себя ваша другая обработка, но это звучит немного накладно, даже для PIC. Может быть, есть другие проблемы, препятствующие вашей работе?
Рей Миясака

Ответы:

41

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

Сравнение CRC с другими вариантами приведено в превосходном ответе Мартина Томпсона .

Одним из способов помочь с этим является pycrc - инструмент (написанный на python 1 ), который может генерировать исходный код на C для десятков комбинаций модели и алгоритма crc . Это позволяет оптимизировать скорость и размер для вашего собственного приложения, выбирая и сравнивая различные комбинации. 1: требуется Python 2.6 или более поздняя версия.

Она поддерживает crc-8 модель , но и поддерживает crc-5, crc-16и crc-32среди других. Что касается алгоритмов , он поддерживает bit-by-bit, bit-by-bit-fastи table-driven.

Например (загрузка архива):

$ wget --quiet http://sourceforge.net/projects/pycrc/files/pycrc/pycrc-0.8/pycrc-0.8.tar.gz/download
$ tar -xf pycrc-0.8.tar.gz
$ cd pycrc-0.8
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit      --generate c -o crc8-byb.c
$ ./pycrc.py --model=crc-8 --algorithm=bit-by-bit-fast --generate c -o crc8-bybf.c
$ ./pycrc.py --model=crc-8 --algorithm=table-driven    --generate c -o crc8-table.c
$ ./pycrc.py --model=crc-16 --algorithm=table-driven   --generate c -o crc16-table.c
$ wc *.c
   72   256  1790 crc8-byb.c
   54   190  1392 crc8-bybf.c
   66   433  2966 crc8-table.c
  101   515  4094 crc16-table.c
  293  1394 10242 total

Вы можете даже делать такие вещи, как указание, используя двойной поиск (с 16-байтовой таблицей поиска), а не однобайтовый поиск с 256-байтовой таблицей поиска.

Например (клонирование репозитория git):

$ git clone http://github.com/tpircher/pycrc.git
$ cd pycrc
$ git branch
* master
$ git describe
v0.8-3-g7a041cd
$ ./pycrc.py --model=crc-8 --algorithm=table-driven --table-idx-width=4 --generate c -o crc8-table4.c
$ wc crc8-table4.c
  53  211 1562 crc8-table4.c

Учитывая ограничения памяти и скорости, эта опция может быть лучшим компромиссом между скоростью и размером кода. Единственный способ быть уверенным в том, чтобы проверить это, хотя.


Pycrc репозиторий на GitHub , как его отслеживания проблем , но он также может быть загружена с сайта SourceForge .

Марк Бут
источник
Я не верю, что большинство людей, пишущих вещи для PIC, используют C, но это может сработать, если так.
Билли ОНил
4
@ Билли - Правда? Я не думаю, что я встречал кого-то, кто коммерчески разрабатывал для PIC, кто не использовал C. У меня, конечно, нет терпения для ассемблера в наши дни, и хорошо структурированный C может оказаться довольно компактным.
Марк Бут
Я использую dsPIC и использую C.
FigBug
@FigBug - Спасибо, рад, что вам понравился мой ответ. Если вы запустили несколько тестов производительности, не стесняйтесь редактировать мой ответ с вашими результатами Мне бы хотелось знать, насколько сильно каждый из этих алгоритмов влияет на пропускную способность вашего приложения и объем памяти.
Марк Бут
1
Еще один голос за pyCrc здесь. использовать его в различных проектах с разными ограничениями, и это просто здорово.
Вики
11

Простая однобитовая четность (в основном, XOR данных поверх себя снова и снова) - это почти так быстро, как только можно. Вы теряете много ошибок при проверке CRC.

В псевдокоде:

char checksum = 0;
for each (char c in buffer)
{
    checksum ^= c;
    SendToPC(c);
}
SendToPc(checksum);
Билли ОНил
источник
1
Я изучил это некоторое время назад. Я считаю, что суммирование вместо xor на самом деле работает немного лучше. (обычно суммируйте все, а затем передайте 2-е дополнение к сумме в качестве контрольной суммы. На получателе суммируйте все, включая полученную контрольную сумму. Результатом будет 0, если все хорошо, и не 0 в противном случае.)
быстро_ теперь
1
@ quickly: я не думаю, что есть существенная разница между этими двумя - ни один из этих методов не дает такой хорошей гарантии, что вещи не были испорчены. Если добавление выполняется быстрее в целевой архитектуре, во всех случаях используйте это.
Билли ОНил
7
Я вспомнил: главное различие между ADD и XOR заключается в том, что обнаружение множественных битовых ошибок меньше. В случае потока байтов ошибки в одной и той же битовой позиции устраняются с помощью XOR. При использовании ADD распространение битов вверх через байт контрольной суммы означает, что этот случай более обнаружим. (Однако множественные битовые ошибки в разных битах, распределенных по потоку байтов, вероятно, будут менее детектируемыми - в зависимости от обстоятельств в данный момент). Любое расположение контрольной суммы, подобное этому, УЖАСНО для многобитовых ошибок, поэтому это довольно незначительный аргумент.
quick_now
XOR намного менее полезен, чем CRC.
3
@ Thorbjørn: я считаю, что признал это в своем ответе. :)
Билли ONEAL
10

Действительно хорошая статья, сравнивающая производительность различных контрольных сумм и CRC во встроенном контексте:

Эффективность контрольных сумм для встраиваемых сетей

Некоторые цитаты из выводов (на основе их исследований вероятностей необнаруженных ошибок):

Когда доминируют пакетные ошибки

XOR, добавление двух дополнений и контрольные суммы CRC обеспечивают лучшую производительность обнаружения ошибок, чем добавление дополнения, контрольные суммы Fletcher и Adler.

В других приложениях

«хороший» полином CRC, по возможности, должен использоваться для целей обнаружения ошибок

Если стоимость вычислений очень ограничена

(как в вашем случае) используйте (в порядке эффективности):

Другие цитаты:

Контрольная сумма Флетчера имеет более низкую вычислительную стоимость, чем контрольная сумма Адлера, и, вопреки распространенному мнению, также более эффективна в большинстве ситуаций.

а также

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

Мартин Томпсон
источник
1
В качестве бонуса очень легко реализовать контрольную сумму Флетчера.
RubberDuck
6

Контрольная сумма Адлера должна быть достаточной для проверки искажений при передаче. Он используется библиотекой сжатия Zlib и принят стандартом мобильной графики 3D Java для быстрой, но эффективной проверки целостности данных.

Со страницы википедии :

Контрольная сумма Adler-32 получается путем вычисления двух 16-битных контрольных сумм A и B и объединения их битов в 32-битное целое число. A - сумма всех байтов в строке плюс один, а B - сумма отдельных значений A для каждого шага.

В начале прогона Adler-32 A инициализируется равным 1, B - 0. Суммы делаются по модулю 65521 (наибольшее простое число меньше 2 ^ 16 или 65536). Байты хранятся в сетевом порядке (с прямым порядком байтов), B занимает два старших байта.

Функция может быть выражена как

 A = 1 + D1 + D2 + ... + Dn (mod 65521)
 B = (1 + D1) + (1 + D1 + D2) + ... + (1 + D1 + D2 + ... + Dn) (mod 65521)
   = n×D1 + (n-1)×D2 + (n-2)×D3 + ... + Dn + n (mod 65521)

 Adler-32(D) = B × 65536 + A

где D - строка байтов, для которой должна быть рассчитана контрольная сумма, а n - длина D.

Gnawme
источник
Обратите внимание, что Adler32 практически бесполезен для коротких прогонов данных. Приблизительно до 180 байтов, это производит многочисленные столкновения.
Greyfade
+1 - разумная золотая середина между CRC и простым контролем четности.
Билли ОНил
@greyfade - в FigBug упоминаются блоки по 512 байт, так что это не должно быть проблемой для OP. Хорошо, что это отметили для людей с другими требованиями, хотя.
Марк Бут
5

Я не знаю ничего, что было бы столь же эффективно при обнаружении ошибок, как CRC и быстрее - если бы оно было, люди использовали бы его вместо этого.

Вы можете попробовать простую контрольную сумму, но вероятность обнаружения ошибок гораздо ниже.

Боб Мерфи
источник
2
Я готов отказаться от эффективности ради скорости.
FigBug
3

Ну, сама логика контрольной суммы хороша, и люди могут помочь с более быстрыми алгоритмами.

Если вы хотите повысить скорость работы вашего компонента, вам может потребоваться изменить общую технику, чтобы отделить компонент передачи от компонента проверки.

Если у вас есть эти два независимых элемента (в разных потоках), вы можете получить полную скорость передачи и пересылать только ошибочные пакеты.

Алгоритм будет выглядеть примерно так:

  • Сервер распадается на пакеты известных размеров (скажем, порции по 1 КБ). Ставит их в очередь «быть отправленным».
  • Каждый пакет отправляется с 16 или 32-битным идентификатором и его контрольной суммой.
  • Клиент получает каждый пакет и помещает его в очередь для обработки.
  • В отдельном потоке клиент получает пакет за раз, выполняет проверку.
    • В случае успеха он добавляет его к окончательному набору пакетов (в порядке идентификации)
    • При сбое он сообщает о сбойном ID обратно на сервер, который ставит в очередь этот пакет для повторной отправки.
  • После того как вы получили и проверили пакеты и у вас есть идентификаторы в правильной последовательности (начиная с 1), вы можете начать записывать их на диск (или делать то, что требуется).

Это позволит вам передавать с максимально возможной скоростью, а если вы играете с размером пакета, вы можете определить оптимальную частоту отказов VS, а также скорость проверки / повторной отправки.

Робин Весси
источник
2

Контрольные суммы традиционные

(уменьшить # '+ поток)

XOR, как указано выше, будет также работать

(уменьшить # 'поток XOR)

Немного более сложной (более медленной) схемой является стандартная проверка четности для последовательных соединений.

На этом уровне вы торгуете правильно для скорости. Они иногда терпят неудачу.

На следующем, более сложном уровне вы можете использовать некоторые вещи типа crc / hash.

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

У вас должна быть оценка фактической частоты ошибок, чтобы настроить ваш алгоритм выбора и параметры для размера блока.

Пол Натан
источник