CRC16-CCITT — сравнение реализаций

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

Этой проблемной области уже не один десяток лет, и она очень хорошо изучена и изъезжена вдоль и поперек. Однако, не смотря на её изученность, у разработчиков всё ещё возникают и, я так думаю — будут и впредь возникать, вопросы применения программ (функций) для расчета контрольных сумм CRC при передаче массивов данных.

Один из первых вопросов это — какого размера должна быть CRC — одно- , двух- , четырех- или скольки-байтовая?

Второй вопрос — а сколько времени потребуется для вычисления CRC?

Следующий вопрос возникает уже у тех, кто погрузился в проблему ещё глубже, — какой алгоритм расчета CRC подойдет лучше: обычный (программный) или на основе таблицы?

Вот и мне выпала честь поупражняться на эту тему, и я решил поделиться с обществом результатами своих небольших «исследований».

Ответ на первый вопрос достаточно прост. Если последовательность байт (пакет), которую предполагается защитить от приема в искажённом виде, имеет крайне небольшую длину — не более 15 байт, то в принципе достаточно использовать CRC8 (то есть одно-байтовую контрольную сумму).

Для пакетов, размер которых не превышает 4 кБайт используется CRC16 (двубайтовая CRC). Для пакетов, размер которых от 4 кБ до 256 МБ нужно использовать CRC32. Для еще больших по объему массивов информации применяются уже не просто CRC- механизмы, а более мощные криптографические алгоритмы хэш-функций.

Все это можно почерпнуть из Википедии:

http://ru.wikipedia.org/wiki/Циклический_избыточный_код

Там же имеются примеры программ.

Алгоритмов придумано много. Так, например, имеется около пяти разных алгоритмов для расчета CRC16. Я говорю «примерно», потому что я не особо глубоко занимался этим вопросом. Но я заметил, что все эти 16-ти разрядные алгоритмы имеют примерно одинаковую «силу».

Они, конечно, отличаются друг от друга по некоторым параметрам. Один алгоритм лучше «держит» пропадание сигнала, другой — искажения связанные с инверсией битов, третий — лучше «секёт» взаимоисключающие искажения соседних битов и т.д.

Я так понял, что тут как-то сложно сделать абсолютно правильный выбор на основе теоретических знаний и умозрительных предположений. Нужно практически пробовать разные алгоритмы на конкретных линиях. А пока нет статистики — какой из них окажется лучше, то можно считать, что все они одинаковые, и брать в проект любой из них.

Второй вопрос был связан со скоростью работы алгоритмов. Если вы используете микроконтроллер, то очевидно вы задаетесь вопросом — а сколько времени ему понадобится чтобы вычислить CRC? А будет ли успевать МК считать контрольные суммы?

Сразу скажу, я не испытывал всех алгоритмов. Я только измерил время работы одного из них — CRC16-CCITT. У меня собрано изделие на базе ATMEGA328, которое работает на частоте 8 МГц. Мне нужно передавать в линию пакеты размером 814 байт.

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

Так вот, на программную реализацию алгоритма для подсчета CRC16 для 814 байт уходит времени 12.9 мс. Что в пересчете на один байт составляет 15.8 мкс/байт. Или примерно 127 тактов на байт информации.

Я также протестировал табличный алгоритм расчета CRC16. Согласно этому алгоритму имеется некая таблица, из которой берутся уже готовые двухбайтовые значения для каждого байта информации. Иначе говоря, процессор не тратит такты на вычисление CRC для каждого байта как это происходит в программной реализации, а берет их из таблицы.

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

Однако, хотелось бы также озвучить и бонусы, которые мы получаем при использовании табличного алгоритма. Понятно, что при его использовании время вычисления будет меньше. Вопрос в другом — на сколько меньше?

Практика показывает, что при тех же данных (тактовая частота процессора, размер пакета) время на табличное вычисление CRC16 уходит 2.76 мс. То есть скорость счета возрастает примерно в 4-5 раз.

Если пересчитать это время на байт и на такты, то получаются следующие значения: 3.39 мкс/байт и 27 тактов на байт.

Что касается объема кода, который размещается во флешь-памяти, то при табличной реализации потребуется больше на 512+14 байт.

Я специально отделил размер таблицы (512 байт) и разность кодов (14 байт). Ведь, таблица изначально в микроконтроллере размещается во флешь памяти. И только перед тем как будет вызвана функция main, таблица копируется из флеши в ОЗУ. (Бедное ОЗУ, его сразу становится меньше! Ах-ах!)

Забавно отметить, когда я давным давно использовал Виндовые программы, такие как IAR и CodeVision, я каждый раз вздрагивал — а хватит ли мне памяти? Не надо ли мне  изменить размер стеков? Что нужно сделать — увеличить C-stack и уменьшить R-stack или сделать наоборот? Куда «тянуть одеяло»? В какую сторону? На сколько «перетянуть»? — В общем, одно шаманство и никакого научного подхода.

Да, да! Именно так — у этих компиляторов какая-то дурная модель — использовать два стека: один для адресов возврата, другой для данных. Зачем это было так сделано — не знаю. Единственное, что приходит на ум «Но ведь это же круто!».

Круто — да. Но зачем!? Ведь на том, что «это круто» положительные моменты заканчиваются и начинается война с ветряными мельницами.

В результате такого недальновидного подхода к организации стековой памяти в ОЗУ образовываются две дыры, которые будут заполнятся информацией непонятно как. Приходилось лавировать и материться — делать то одну дыру больше, то другую. А как предугадать заранее сколько понадобиться стековой памяти для адресов возврата, а сколько для автоматических переменных?

Был единый стек — была одна беда, которая худо-бедно была локализована и как-то решалась. Теперь  два стека.  Две беды. И что выиграли от такого «крутого» маневра?

При переходе на Линукс и, соответственно, переходе на GCC испытал чувство сродни тому, когда к вам возвращается украденный кошелек вместе с его содержимым. Вау! Внезапно всё стало просто и легко!

Один стек на всё про всё — и для данных, и для адресов возврата. Стек растет на встречу «куче» и глобальным статическим переменным. Когда стек «наезжает» на переменные, те, понятное дело, — портятся. Система падает. И это означает только одно: это — всё! Мир кончился. И никаких танцев с бубном не требуется! Оперативная память исчерпана до последнего байта, и никаких неиспользованных дыр в ней, чтобы что-нибудь куда-нибудь «пододвинуть», — нет. Нужно однозначно менять проц на более мощный. Всё предельно ясно, никаких ужимок и приседаний на тему — «а давайте изменим размер у R-стека? Вдруг поможет?»

Однако, я ушел от темы! Я хотел сказать, что ATMEGA — это хорошие микроконтроллеры. Но, с точки зрения передачи пакетных данных, в мире есть более лучшие. Я имею в виду STM32.

У них, помимо DMA, который разгружает процессор при пересылке данных, имеется еще и блок подсчета CRC32. Не говоря уже о том, что они 32-х разрядные, а тактовая частота у них в разы больше, чем у ATMEGA. А если еще сравнить  размеры памяти и цены у STM32 и MEGA, то становится ясно как божий день, какое ядро нужно закладывать в основу в новых изделиях.

Но самый писк состоит в том, что у них единое адресное пространство. Это означает, что если в программе используются константы (например, как здесь — таблицы значений, или просто текстовые строки), то загрузчик (который работает перед вызовом функции main) не занимается пересылкой этих данных из флеши в ОЗУ. Ему это незачем делать, так как разницы нет где лежат данные — в ОЗУ или во флеши. Таким образом, не тратится время и не расходуется дефицитная оперативная память. Одни удобства!

Update 08.07.2013

Вот несколько полезных ссылок на интернет-ресурсы, связанные с CRC.

1. www.lammertbies.nl/comm/info/crc-calculation.html — online-калькулятор контрольных сумм. Здесь же имеется кратенькое описание (на английском языке) на тему вычислений CRC.

2. http://embedded.ifmo.ru/embedded_old/ETC/REFERAT/crc/crc.htm — большая статья «CRC-алгоритмы обнаружения ошибок» (на русском)

3. http://www.zorc.breitbandkatze.de/crc.html — еще один калькулятор CRC. Более навороченный, чем в п.1. Внизу страницы приведено десятка два ссылок по теме на другие сайты.

4. Для микроконтроллеров с ядром AVR оказывается существует библиотека! (Надо же! Ведь знал об этой библиотеке. А когда подошла пора воспользоваться, успешно забыл.)

Хэдерный файл подключается в проект незатейливо — с помощью строки:

 #unclude <util/crc16.h>

Описание функций здесь — http://www.nongnu.org/avr-libc/user-manual/group__util__crc.html

Advertisements

2 responses to “CRC16-CCITT — сравнение реализаций

  1. Думал промолчать, но всё же отпишусь.
    Товарищу написавшему данный пост, хотелось бы посоветовать:
    1) разобраться в способах вызова функции и передачи в них параметров через регистры платформы. Разные компиляторы могут это делать по разному, и Вы сами привели тому пример когда пересели на GCC.
    2) если Вам нужен был единый стек, то в IAR-овский компилятор спокойно это делает, нужно только читать описание компилятора которым пользуетесь.
    3) сравнивать 8-ми и 32-ти битные архитектуры и упоминать о едином пространстве (почему у STM оно есть а у ATMega его нету) тоже считаю не коректным, так как это завязано по большему счёту именно на разрядность платформы и соответственно возможностях кодирования команд в ней.
    4) сравнивать относительно «старую» ATMega и «новый» STM32 на наличие в них ДМА каналов и модулей для расчёта CRC уж извините .. Возьмите уж тогда хотя бы более «свежую» ATxMega для сравнения в которых это есть.
    5) по поводу нехватки ОЗУ. Тут наверное более вопрос стоит в том, что Вам нужно быстродействие или место. В Вашем случае Вы делаете дубликат таблицы в RAM из FLASH, и дальше работаете с ней, тем самым на момент работы программы у Вас таблицей съето 1 кБ (512 байт FLASH + 512 байт RAM). Но ведь никто не мешает Вам получать табличные данные прямо из FLASH. Вы затратите 1 лишний такт на чтение байта, но будете экономить 512 Байт RAM.

    PS .. согласен, ATMega уже своё отжила 🙂

    • Спасибо за Ваш комментарий!

      А теперь, давайте по порядку.

      1. Предположим, что я не разбираюсь в этом вопросе. Так что, по Вашему, не так в статье при описании функций и передаче параметров?

      2. Сейчас мне IAR не нужен! Давным-давно, когда я его использовал, в то время у меня не стоял вопрос объединения стеков в один так остро. Просто я был удивлён таким решением, но не более. Лежащего на поверхности легкого решения по объединению обоих стеков один, что-то не припоминаю. Возможно его тогда и не было. А по большому счету — да, хрен на него! На IAR и на AVR. Зачем изучать то, что уже стало ненужным?

      3. Спасибо за Ваше мнение! А я считаю, что сравнивать 8-ми и 32-х разрядные платформы не только корректно, но и обязательно! Когда разработчик приступает к новому проекту, то он всегда сталкивается с вопросом выбора микроконтроллера. И вопрос, на чём реализовывать — на AVR или на STM32 — возникает почти всегда.

      Однако, поскольку я считаю — так, а Вы — иначе, то кто же из нас тогда прав?

      И AVR, и STM32 — это оба микроконтроллеры, которые позволяют реализовать задумки. В каких-то проектах один из них будет лучше другого. Так почему же некорректно их сравнивать с точки зрения эффективности выполнения ими тех или иных задач?

      4. Не извиню! Почему Вы считает возможным определять что можно делать, а что нельзя? Что можно сравнивать, а что нельзя?

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

      Что касается XMega — ну, как бы Вам сказать… После того, как уже выбрал себе жену и женился, в твоем окружении все равно будут появляться красивые женщины. Да, XMega лучше, чем просто-Mega. Возможно, она в каких-то узких проявлениях будет даже лучше, чем STM32. Но скажите мне по секрету, какой смысл перепрыгивать с платформы Cortex на платформу XMega? Вопрос нужно рассматривать в контексте того, что STM32 уже неплохо изучена, имеется опыт применения, имеется аппаратная и программная поддержка… Короче говоря, локомотив по применению STM32 уверенно движется. И тут вдруг входит проводник весь в белом и говорит:

      — Ребята! Сейчас все дружно на ходу спрыгиваем c «STM32» и бежим вон к тому паровозу «XMega». По дороге не забываем подбираем дрова, что бы растопить котёл! А пока котел разогревается, дружно укладываем недостающие рельсы. А через неделю, глядишь, уже сможем тронуться с места и проехать с десяток метров.

      Самое политкорректное в ответ будет:

      — Ты что — дурак?

      XMega запоздала с выходом на рынок. Более того, она применяется значительно реже, чем та же просто-Mega или STM32. А я в своей статье рассматривал те микроконтроллеры, которые я знаю (1) и который широко используются (2).

      5. >> Но ведь никто не мешает Вам получать табличные данные прямо из FLASH. Вы затратите 1 лишний такт на чтение байта, но будете экономить 512 Байт RAM.

      Никаких возражений — никто не мешает! Хотя на счет «одного лишнего такта» — это Вы слукавили. Вот, возьмите-ка и проверьте этот вариант. И отпишитесь, сколько тактов на байт или сколько времени у Вас занял подсчет CRC.

      Критиковать-то чужие работы, да реагировать на несправедливость в инете — мы все неплохо умеем. А что касается поработать на пользу для общества — так сразу уходим в несознанку.

      Так в чём состоит Ваша польза, немолчаливый Вы наш советчик?

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s