Простой и эффективный расчёт Modbus CRC16 в ПЛК и МК без побитового сдвига и таблиц
Сакральный алгоритм расчёта CRC16, описанный в литературе и связанный с побитовым сдвигом, плохо вписывается в формат вычислительных возможностей ПЛК и МК.
Во-первых, постольку, поскольку его реализация отнимает изрядный объем вычислительных ресурсов вышеозначенных устройств, во-вторых, потому что в ходе такого расчета существенно растягивается время скана программы. Рост скана программы обусловлен тем, что, вследствие словной или байтовой организации аккумулятора арифметико-логического устройства, результирующие битовые операции со словами/байтами в нём выполняются гораздо дольше операций со словами/байтами целиком. В отдельных устройствах операции побитового сдвига и вовсе не поддерживаются, тогда как алгоритм подразумевает выполнение восьми циклов с такими операциями. В целях сокращения объема вычислений и, как следствие, времени сканирования при обработке CRC, часто применяется иной алгоритм — табличный, когда таблица масок рассчитывается и заполняется единожды в первом скане программы. Тем не менее, и этот способ не лишён недостатка, ибо также потребляет ресурсы. 512 байт (или 256 двухбайтных слов), порою, отнюдь не лишние.А можно ли видоизменить алгоритм расчёта CRC таким образом, чтобы отказаться от применения побитовых сдвигов и таблиц? Безусловно, да. Достаточно лишь внимательно приглядеться к алгоритму с побитовым сдвигом.
Напомню его суть:
- осуществляется сложение по модулю 2 очередного байта массива посылки с младшим байтом двухбайтной CRC;
- осуществляется ациклический сдвиг CRC на один бит от старшего 15-го разряда к младшему, нулевому, с выдвижением младшего бита, при этом старший разряд обнуляется;
- если значение выдвинутого бита единичное, выполняется сложение CRC по модулю 2 c полиномом 16#A001.
- шаги 2 и 3 повторяются ещё 7 раз.
Почему это реализовано так, а не иначе? Да потому, что такая алгоритмизация представлялась наиболее подходящей для реализации посредством аппаратной логики.
Внимательно взглянув на этот алгоритм, нетрудно обнаружить, что фактически мы имеем дело с циклическим побитовым сдвигом слова.
За его цикличность отвечает старший бит полинома. В результате, значение старшего битового разряда CRC после каждого сдвига идентично значению выдвинутого младшего. Таким образом, при осуществлении циклического побитового сдвига, полином, с которым затем необходимо производить сложение по модулю 2, трансформируется в 16#2001.
Подобных сдвигов выполняется восемь… Проще говоря, в глобальном плане речь идёт о перемене местами младшего байта CRC со старшим её байтом. А это наводит на мысль, что, после сложения по модулю 2 очередного байта массива посылки с младшим байтом CRC, достаточно поменять местами младший и старший байт CRC, а затем, последовательно проанализировав восемь бит старшего её байта, начав с младшего его разряда, восьмого, произвести сложение СRC по модулю 2 c известными константами, предопределёнными значением полинома, значение которого для Modbus CRC16, как уже указано выше, эквивалентно 16#2001.
Итоговый алгоритм для учёта в CRC очередного байта массива посылки выглядит следующим образом:
Осуществляется сложение по модулю 2 очередного байта массива посылки с младшим байтом двухбайтовой CRC, после чего младший и старший байт CRC меняются местами;
- Если значение 8-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#0240;
- Если значение 9-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#0480;
- Если значение 10-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#0900;
- Если значение 11-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#1200;
- Если значение 12-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#2400;
- Если значение 13-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#4800;
- Если значение 14-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#9000;
- Если значение 15-го бита СRC единичное, выполняется её сложение по модулю 2 с константой 16#2001, расчёт окончен.
Преимущества такого способа расчёта:
1) По сравнению с алгоритмом побитового сдвига:
а) предложенный алгоритм позволяет избавиться от команд вложенного цикла FOR-NEXT и команд побитового сдвига в таком цикле, при том, число количество исполняемых команд сложения по модулю 2 сохраняется неизменным;
б) в контроллерах c поддержкой команды SWAP, восьмикратный побитовый сдвиг CRC заменяется единственной командой, а в контроллерах, такую команду не поддерживающих, — одной или двумя командами пересылки, входящими в число базовых команд контроллера и отнимающими минимальное время;
2) По сравнению с табличным методом расчёта, этот метод не нуждается в выделении места в памяти данных под таблицу, в её предварительном заполнении, в выборке соответствующей маски из таблицы с последующим ее наложением на байт CRC.
Проработка предложенного алгоритма расчёта СRC16 изначально велась для ПЛК Mitsubishi моделей FX3S/3G, не поддерживающих инструкций расчёта СRC и перемены местами байт в слове, между тем, предельное суммарное время расчета СRC с применением указанного алгоритма для массива посылки, состоящего из 128 байт, не превышает 2,4мс.
Прямой табличный алгоритм crc16
Необходимость дополнения исходной строки завершающими нулевыми байтами представляет большое неудобство при реализации общей схемы табличного алгоритма. Поэтому на практике используют другую схему вычисления CRC, не требующую завершения исходного сообщения нулевыми байтами. В этой схеме очередной байт исходной строки объединяется операцией XOR со старшим байтом регистра, выдвинутым с левой стороны этого регистра.
Полученное в результате
объединения значение используется в
качестве индекса для доступа к CRC-таблице.
Извлекаемое из CRC-таблицы значение
объединяется операцией XOR с
содержимым регистра.
Описанный алгоритм
называют прямым табличным алгоритмом.
Рис. 12.6. Схема вычислений CRC с использованием прямого табличного алгоритма
На схеме вычислений CRC с использованием прямого табличного алгоритма цифрами обозначена последовательность шагов вычисления CRC.
Выдвижение старшего байта регистра АХ в байтовую ячейку.
Выполнение операции XOR над выдвинутым на шаге 1 в байтовую ячейку старшим байтом регистра АХ и очередным байтом исходной строки.
Полученное на шаге 2 значение используется в качестве индекса для доступа к элементу CRC-таблицы.
Извлеченное из CRC-таблицы значение объединяется по XOR со значением в регистре АХ.
Результат выполнения на шаге 4 операции XOR помещается обратно в регистр АХ.
После обработки последнего байта исходной строки регистр АХ содержит значение CRC.
Все существующие алгоритмы вычисления CRC являются, по сути, различными модификациями описанного выше табличного алгоритма. Эти модификации преследуют разные цели, перечислим некоторые из них:
переход от цикла по всем битам к циклу по большим порциям данных – байтам, словам и т. д.;
повышение разрядности порождающего полинома;
отражение особенностей функционирования аппаратуры передачи данных (наличие этой цели обусловлено тем, что микросхемы, поддерживающие работу последовательного порта компьютера, передачу байта начинают с его младших битов, поэтому описанные ниже алгоритмы расчета CRC, учитывающие эту особенность, называются зеркальными).
Алгоритмы вычисления CRC получили свое закрепление в некоторых стандартах. Перечислим отличительные особенности основных алгоритмов вычисления CRC. Итак, основные алгоритмы вычисления CRC различаются:
по значению и степени порождающего полинома, при этом значение полинома обычно указывается без ведущей единицы в старшем разряде;
по начальному содержимому регистра, в котором формируется значение CRC;
по тому, производится ли обращение битов каждого байта перед его обработкой;
по способу прохода байтов через регистр – способ может быть косвенным или прямым;
по тому, производится ли обращение конечного результата;
по конечному значению, с которым производится объединение по XOR результата вычисления CRC.
После появления 32-разрядных микропроцессоров наибольшей популярностью стали пользоваться 32-разрядные алгоритмы вычисления CRC. В различных источниках рассматривают два типа таких алгоритмов – прямой и зеркальный. Рассмотрим их конкретные реализации, рекомендуемые стандартами.
Как и любой табличный алгоритм, табличный алгоритм вычисления CRC32 требует задания CRC-таблицы. Ее можно задать в программе статически, явно прописав значения элементов таблицы в сегменте кода, или динамически, вычислив значения элементов таблицы перед началом расчета CRC.
В заключение обсудим «зеркальный» вариант табличного алгоритма – алгоритм CRC32 (V.42 МККТТ). Этот вариант вычисления CRC обязан своим возникновением существованию последовательного интерфейса, который посылает биты, начиная с наименее значимого (бит 0) и заканчивая самым старшим (бит 7), то есть в обратном порядке. В «зеркальном» регистре все биты отражены относительно центра. Например, 10111011001 есть отражение значения 10011011101.
Вместо того чтобы менять местами биты перед их обработкой, можно зеркально отразить все значения и действия, участвующие в прямом алгоритме. При этом направление расчетов поменяется – байты теперь будут сдвигаться вправо, полином 04clldb7h зеркально отразится относительно его центра, в результате получится значение 0edb88320h. СRС32-таблица будет зеркальным отражением аналогичной таблицы для прямого алгоритма (рис. 12.7).
Рис. 12.7. Схема «Зеркального» табличного алгоритма
Для зеркального алгоритма вычисления CRC32 процесс вычисления такой же, за исключением порядка – сдвиги и заполнение регистра осуществляются вправо.
Этот вариант работы алгоритма вычисления
CRC32 удобен тем, что не нужно знать длину
собственно исходной последовательности
(без значения CRC). Достаточно просто
обработать весь входной поток, не
различая в строке завершающую ее
подстроку с CRC.
Далее необходимо сравнить
содержимое регистра ЕАХ с 6b202ca2h. Если
эти значения равны, значит, исходная
последовательность нарушена не была.
Для получения собственно строки
достаточно отбросить последние 4 байта
сообщения, полученного приемником.
Что является более быстрой альтернативой CRC?
Хотя могут быть более быстрые варианты, чем 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. 0xffff ))
0xffff ))
This will cause variables to be expanded and whitespace not to blow things up.
In general you should also pass -r to read, see help read for what it does.
Why make an extra copy of $1 before processing it into an array? Using
while read -d "" -n 1 ; do astring+=( "$REPLY" ) ; done <<< "$1"
is sufficient.
It’s probably not necessary to turn your input into an array before processing. Instead you can slice characters out of the string in your loop, which is closer to what the C++ version is doing. Replace
char="${astring[$x]}"
with
char="${1:$x:1}"
This is operating directly on the function paramter; since we’re no longer making a copy of that we also need to get $cnt a different way
cnt=${#1}
But you really have even bigger problems than this, like the fact that a character isn’t an integer in bash. To convert you must use the following syntax:
printf '%d' \'a
where a is the character to convert. Inserting this into the context of the script it would be
char=$(printf '%d' \'"${1:$x:1}")
Now we’re getting somewhere, but I really must ask you to consider whether all of this is really worth it. Even if you can make it work, what do you gain?
Алгоритмы безопасной работы с flash памятью датчика ZETSENSOR
Процедура записи данных от внешнего устройства в память датчика является очень ответственной задачей. Так как при некорректной записи данных в память, датчик перестанет корректно работать.
Причины некорректной записи данных:
1. В сети находится 2 датчика с одинаковыми нодами. При попытке записи данных в один датчик, те же самые данные запишутся и на другой датчик, что приведёт к порче настроек датчика.
2.
Внешнее устройство начало записывать данные на датчик. Но ввиду каких либо причин, связь случайно оборвалась (отсоединили устройство, пропало питание и т.д.). Таким образом, в память датчика могут быть записаны некорректные данные.
Возникает задача, построить алгоритм безопасной записи данных на датчик. Алгоритм должен решить следующие проблемы:
1) Датчик должен принимать только те данные, которые предназначены для него. Для идентификации принимаемых данных можно использовать 64 битный серийный номер датчика.
2) Использование принятых данных разрешено только после принятия всех данных и проверки корректности этих данных.
Первая задача решается путём добавления контрольной суммы CRC16 в каждую из подструктур основной структуры датчика. Благодаря этой контрольной суммы мы всегда можем проверить корректность текущих данных и принадлежность этих данных конкретно этому устройству.
Для решения второй задачи необходимо организовать целостность передаваемых данных. Для этого мы будем использовать младшую часть поля write_enable. Когда данные в структуре корректны это поле имеет статус “Корректные данные”. Перед записью данных мы должны выставить статус “Начало передачи данных”, обозначающий то, что значения данной структуры будут изменены. Далее записать данные. (После получения первого пакета, состояние структуры изменяется в состояние “Активная передача данных” данный статус пока не используется). После окончания записи данных выставить поле write_enable в состояние “Передача данных завершена”. Как только выставлен статус “Передача данных завершена”, датчик начинает проверять корректность полученных данных и в случае успеха записывает их в flash память. Далее выставляется статус “Корректные данные”.
| Статус структуры (значение поля write_enable) | Определение данного статуса |
| 0 – “Корректные данные” | Структура содержит полностью корректные данные, эти данные можно использовать и обрабатывать датчиком. |
| 1 – “Начало передачи данных” | В данном состоянии запрещается использовать данные находящиеся в структуре датчика. Только в этом состоянии можно начинать передавать данные датчику. |
| 2 – “Активная передача данных” | В данном состоянии запрещается использовать данные находящиеся в структуре датчика. (Данный статус не обрабатывается в действующем алгоритме). |
| 3 – “Конец передачи данных” | В данном состоянии датчик должен проверить все переданные ему данные. И сбросить своё состояние в состояние “Корректные данные”. |
Изменения статусов возможно только в следующем порядке:
“Корректные данные” → “Начало передачи данных” → “Активная передача данных” → “Конец передачи данных” → “Корректные данные”
Примечания
- Необходимость выставления статуса “Начало передачи данных” заключается в обозначении того, что данные изменяются извне, а не самим датчиком.
- Необходимость выставления статуса “Конец передачи данных” заключается в том, чтобы датчик обработал полученную информацию, а не сразу перешёл в состояние “Корректные данные”. Статус “Корректные данные” выставляет только датчик (Выставление данного статуса извне запрещено прошивкой устройства).
- Возможен вариант выставления статуса “Начало передачи данных” но сами данные не были переданы (в связи с обрывом соединения или каких-либо других причин). В данном случае статус не сможет сброситься в состояние “Корректные данные”. Данную ситуацию должен обрабатывать компьютер. Так как датчик по определению не может определить были переданы все данные или нет, обрыв соединения это или задержки передачи данных. Поэтому для однозначности эту ситуацию будем обрабатывать компьютером.
- Возможен вариант что статус “Начало передачи данных” не выставился по каким-либо причинам. В данном случае все последующие данные будут игнорироваться
- Компьютеру разрешается выставлять только статусы “Начало передачи данных” или “Конец передачи данных”. CRCHi[TableIdx];
Lo = CRCLo[TableIdx];
}
return (Hi Алгоритм записи данных на датчик- Выставить статус “Начало передачи данных”, в структуре, данные которой изменяются.
- Начать передачу данных. Для оптимальности передачи данных, передавать нужно не всю структуру, а только изменённые поля.
- Передать пересчитанное значение CRC для передаваемой структуры.
- Выставить статус “Конец передачи данных”, в структуре, данные которой изменяются.
Алгоритм записи данных на flash
- Проверяется вся структура датчика на наличие подструктур с статусом не равным “Корректные данные”. Если такой структуры не найдено, переходим на следующий шаг, в противном случае повторяем текущий шаг.
- Проверяется вся структура на изменение данных (сравниваются значения находящиеся в flash и значения находящиеся в структуре в текущий момент времени). Структура проверяется по 2 байта за каждый проход глобального цикла. Если изменения присутствуют, переписывается вся структура находящаяся в flash. Возвращаемся к шагу 1.
Алгоритм приёма и проверки данных датчиком
- При приёме статуса “Начало передачи данных” в одну из подструктур основной структуры датчика чистим 19 сектор flash памяти и переходим на следующий шаг, в противном случае повторяем текущий шаг.
- Все получаемые данные записываются в flash память. (19 сектор).
- При приёме статуса “Конец передачи данных”, проверяется текущее значение статуса, если оно не равно статусу “Корректные данные” проверяем корректность данных, в противном случае ничего не делаем.Проверка корректности данных: Запись текущих значений подструктуры в 20 сектор. Вносим изменения из 19 сектора. Проверяем CRC в заголовке структуры. Если CRC совпало, оставляем всё как есть. Если не совпало, копируем данные из 20 сектора.
- Выставляем статус “Корректные данные”.
CRC FAQ.
Что, зачем и как — radiohlam.ru- Глава 1. Что такое CRC и зачем он нужен
- Глава 2. Базовая теория, необходимая для вычисления CRC
- Глава 3. Модификация алгоритма для практического применения
- Глава 4. Резюме
Глава 1. Что такое CRC и зачем он нужен
CRC (cyclic redundancy code) — циклический избыточный код, иногда называемый также контрольным кодом. По своей сути — это просто вычисленное на основе исходного передаваемого сообщения число (или можно сказать код), которое передаётся вместе с самим сообщением (дописывается в конец информационной части) и служит для контроля его безошибочной передачи.
Число это вычисляется по определённым правилам и всегда имеет строго определённое заранее количество разрядов. Очень удобно заранее знать, сколько разрядов занимает контрольное число, потому что иначе станет заранее неизвестной длина сообщения целиком, вместе с CRC, даже при условии, что мы точно знаем длину информационной части. Кроме того, это позволяет заранее выделить для вычисления CRC регистр нужного размера.
Никакой дополнительной информационной нагрузки это число не несёт, поэтому с точки зрения передачи полезной информации оно избыточно. Однако, как я уже сказал, его наличие позволяет диагностировать некоторое количество ошибок, если такие возникают при передаче.
Глава 2. Базовая теория, необходимая для вычисления CRC
По большому счёту, вся теория нахождения CRC базируется на двух вещах.
Первое. Любое сообщение можно представить в виде одного большого двоичного числа и считать что значения разрядов этого числа кодируют коэффициенты некоторого полинома.
Например, возьмём сообщение «15». В шестнадцатиричном виде оно кодируется так: 0x31,0x35. Если перевести эту запись в двоичную форму и записать всё в одну строку, то получим: 00110001 00110101. Если считать, что каждый разряд полученного числа — это коэффициент полинома, то этот полином будет иметь вид:
0*x15+0*x14+1*x13+1*x12+0*x11+0*x10+0*x9+ 1*x8+0*x7+0*x6+1*x5+1*x4+0*x3+1*x2+ 0*x1+1*x0
Кратко его можно записать так: x13+x12+x8+x5+x4+x2+1По большому счёту, мы можем оставить и двоичную запись (чаще всего так и делают, иксы писать неудобно), но будем помнить, что теперь это не просто число, а вектор, составленный из коэффициентов полинома (можно даже продолжать называть такие вектора полиномами).
Причём нулевые коэффициенты при старших степенях можно опустить (в дальнейшем вы увидите, что нулевые коэффициенты при старших степенях ни на что не влияют) и написать его в виде 11000100110101.Второе. Количество разрядов любого двоичного сообщения — это вполне конкретные, конечные числа. Соответственно, множества всех возможных N-разрядных сообщений (где N-любое целое положительное число), составленных по описанному выше способу, — это конечные множества. При использовании особой алгебры такие конечные множества можно считать конечными полями, являющимися расширением простого конечного поля GF(2). Соответственно, любые полиномы, коэффициенты которых составлены из значений разрядов двоичных чисел, можно рассматривать как многочлены над конечным полем.
Подробно многочлены над конечными полями изучаются в отдельном разделе математики, в который мы не будем сильно углубляться в рамках этой статьи. Если кто-то хочет узнать больше — вектор поисков для самостоятельного изучения, я считаю, вполне определён. Нам же интересно, что это за особая алгебра и как это связано с вычислением CRC.
Так вот, отличия этой алгебры от обычной заключаются в следующем:
— операции сложения и вычитания в ней тождественны и выполняются как сложение по модулю 2 (XOR),
— вместо понятий «меньше»/»больше» используются понятия «старше»/»младше». Старшим считается многочлен с большей степенью (наибольшая степень, у которой коэффициент при x равен единице). Например x3+1 старше, чем x2+x, потому что 3>2.Нахождение CRC заключается в делении с остатком информационного полинома (тот который составлен из информационного сообщения) на некоторый специальный полином. Делим мы как обычно — столбиком, но вместо операции «вычитания» используем «сложение по модулю 2» и продолжаем деление до тех пор, пока оставшийся в делимом полином не окажется младше полинома делителя. Полученный остаток — это и есть CRC.
Для примера разделим рассмотренный выше полином, составленный из сообщения «15», на полином x4+x+1, для чего сначала запишем последний полином со всеми коэффициентами в явном виде (1*x4+0*x3+0*x2+1*x1+1*x0), а потом запишем эти коэффициенты в виде вектора (10011).
Деление будет выглядеть так, как на рисунке справа.Нули в самом начале делимого, как я и обещал, нам не пригодились, точно также, как они не пригодились бы нам и при обычном делении.
Идём далее. Что это за специальный полином, на который мы делим наше представленное в виде полинома сообщение?
А это как раз один из основных параметров CRC-алгоритма, называемый также порождающим многочленом или порождающим полиномом. В качестве порождающего многочлена обычно берут какой-либо неприводимый многочлен.
Деление с остатком на полином степени N позволяет получить 2N различных остатков от деления, причем все эти остатки можно описать N-1 разрядными векторами.
Описанные выше действия — это то, что мы по сути всегда делаем при нахождении CRC. Такое описание алгоритма удобно теоретикам и неудобно инженерам. Поэтому теперь перейдём к частностям, которые приближают нас к практической действительности.
Глава 3. Модификация алгоритма для практического применения.
Посмотрим ещё раз внимательно на наш пример деления столбиком и обратим внимание вот на что — при вычислениях мы фактически всегда оперируем только пятью битами, а могли бы оперировать и четырьмя, поскольку во всех операциях XOR у нас самый старший бит равен единице и он всегда сокращается. То есть, если считать, что вычисления происходят в каком-то выделенном четырёхбитном регистре, то всё деление будет выглядеть так, как будто мы просто на каждом шаге сдвигаем биты в регистре влево, загружая новое значение младшего бита, а старший бит просто выкидываем, если он равен нулю, или, если он равен единице, выполняем XOR регистра и младших четырёх битов порождающего полинома.
То есть теперь можно описать наш алгоритм так: побитно загружаем наше информационное сообщение в регистр нужного размера (на единицу меньше степени порождающего полинома), каждый раз сдвигая регистр влево и помещая новый бит в младший разряд. При этом, если вытесняемый из регистра старший бит равен единице, то выполняем XOR регистра со всеми битами порождающего полинома, кроме старшего.
Значение регистра после обработки всего сообщения — это и есть CRC.На картинке слева тот же самый пример, который мы рассматривали выше, но оформленный в соответствии с новым (инженерным) описанием алгоритма вычисления CRC (хотя по сути, это то же самое деление, что и выше).
Одно отличие в нашем инженерном алгоритме от рассматриваемого выше деления столбиком всё же есть. Отличие это заключается в начальном значении регистра. Мы инициализировали регистр нулями. В итоге наше сообщение стало несколько длиннее первоначального. Как мы знаем, нули в начале сообщения не влияют на результат вычислений, их там можно хоть сколько написать. Но ведь можно инициализировать регистр и не нулями.
Что изменится? Да особенно ничего, просто мы тогда будем искать CRC для несколько модифицированного исходного сообщения (с приписанными в начале битами). Если тот, кто будет определять правильность передачи сообщения, знает об этом и знает какое значение для инициализации регистра нужно выбирать, то он сможет правильно посчитать CRC. Надо сказать, что на практике чаще всего используется инициализация всего регистра нулями или инициализация всего регистра единицами.
Ещё одна особенность практической реализации основана на таком свойстве деления с остатком: если C — это остаток от деления A на B, то остаток от деления (A-C) на B будет равен нулю, а остаток от деления (A-C+D) на B будет равен D (если D < B). Это свойство прекрасно работает как с обычной алгеброй, так и с модифицированной, поэтому на практике, при вычислении CRC, на стороне передатчика дописывают дополнительные биты к исходному сообщению не только спереди, но и сзади, однако приёмнику эти дописанные сзади биты не передают, а вместо них передают вычисленный CRC.
Что нам это даёт? Это упрощает реализацию вычисления CRC на стороне приёмника. Например, если сообщение, для которого мы ищем CRC, оканчивается нулями, то сообщение без этих нулей, но с записанным вместо них CRC можно считать разностью исходного сообщения и вычисленного остатка.
Значит если посчитать CRC для этой разности — он будет равен нулю.То есть, если передатчик, при вычислении CRC, сзади к сообщению дописал нули, а приёмнику передал сообщение с записанным вместо нулей CRC, то приёмник, вместо того, чтобы сначала вычислять CRC для сообщения без контрольного кода, потом принимать CRC в отдельную ячейку памяти, а потом сравнивать вычисленный CRC с принятым, может просто вычислить CRC для всего входящего потока бит (вместе с передаваемым в конце сообщения CRC) и сравнить результат с нулём, сэкономив таким образом пару регистров.
По описаным выше причинам (возможность экономить регистры), обычно в конце исходного сообщения дописывают нули или единицы.
Не знаю, понятно я объяснил или нет, если нет — смотрим на картинку справа (там всё, о чём говорилось выше, показано на нашем любимом примере).
Глава 4. Резюме
Подведём краткий итог. Вычисление CRC заключается в нахождении остатка от деления полинома, составленного по определённым правилам на основе исходного сообщения, на порождающий полином. Полиномы при этом записываются просто битовыми последовательностями коэффициентов. Полученный остаток, разрядность которого всегда на единицу меньше степени порождающего полинома — это и есть CRC.
Для полного описания алгоритма недостаточно просто указать разрядность контрольного кода (например CRC8 или CRC16), для этого необходимо, во-первых, задать параметры формирования на основе исходного сообщения битовой последовательности, для которой вычисляется CRC, и, во-вторых, описать используемый для вычисления CRC порождающий полином. Ну или хотя бы дополнительно сослаться на название интерфейса, в котором этот алгоритм используется, чтобы полное описание можно было посмотреть в соответствующей спецификации (например, CRC8-1Wire, CRC8-SAE J1850, CRC16-USB, CRC16-Bluetooth и так далее).
Порождающий полином может быть приведён в явном виде (с иксами), в виде двоичного числа (коэффициенты полинома) или в виде соответствующего шестнадцатиричного числа.
Кроме того, поскольку коэффициенты при старшей и младшей степенях порождающего полинома всегда равны 1, то один из этих коэффициентов могут опускать. Например, полином, рассматриваемый нами в примерах, может быть записан следующими способами:- в виде полинома: x4+x+1
- в виде двоичного (шестнадцатиричного) числа (коэффициенты полинома): 10011 ( 0x0B )
- в виде двоичного (шестнадцатиричного) числа без старшего бита (самый распространённый вариант): 0011 ( 0x03 )
- в виде двоичного (шестнадцатиричного) числа без младшего бита 1001 ( 0x09 )
Параметры, определяющие формирование битовой последовательности должны описывать:
- начальное значение регистра, в котором вычисляется CRC.
- битовую последовательность, которая дописывается в конце сообщения.
- порядок записи бит в байтах и байтов в словах исходного сообщения.
Наличие последнего параметра связано с тем, что сообщения как правило передаются побайтно и при этом возможны два варианта передачи: старшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в нормальном порядке) или младшим битом вперёд (в этом случае биты исходного сообщения располагаются в битовой последовательности, для которой вычисляется CRC, в обратном порядке). Причём, иногда переворачивают не только биты в байтах, но и, например, байты в словах. Кстати говоря, во всех примерах, которые приводятся в этой статье, рассматривался только нормальный порядок бит (старшим битом вперёд).
Кроме того, иногда полученный в результате деления остаток дополнительно инвертируют и в качестве CRC используют не сам остаток, а это инвертированное значение.
Помимо описанного в этой статье прямого способа вычисления, существует, так называемый, табличный или быстрый способ расчёта CRC, но об этом как-нибудь в другой раз. А на сегодня, пожалуй, всё.
P.S. Пример вычисления CRC-8 для 1-Wire можно посмотреть, скажем, в программе для программирования микросхем памяти DS2430, исходники которой можно найти в этой статье.
CRC16 (ModBus) — алгоритм вычисления
Я использую ModBus RTU и пытаюсь понять, как вычислить CRC16. Мне не нужен пример кода. Мне просто интересно узнать о механизме. Я узнал, что базовая CRC — это полиномиальное деление слова данных, которое дополняется нулями в зависимости от длины полинома. Следующий тестовый пример должен проверить правильность моего базового понимания:
- слово данных: 0100 1011
- полином: 1001 (x 3 +1)
- дополнено 3 битами из-за наивысшего показателя степени x 3
- расчет: 0100 1011 000/1001 -> остаток: 011
Расчет.
01001011000 1001 0000011000 1001 01010 1001 0011Edit1: Пока проверено Марком Адлером в предыдущих комментариях / ответах.
В поисках ответа я видел много разных подходов с реверсированием, зависимостью от прямого или большого порядка байтов и т. Д., Которые меняют результат по сравнению с данным
011.Modbus RTU CRC16
Конечно, мне бы хотелось понять, как работают разные версии CRC, но мой главный интерес — просто понять, какой механизм здесь применяется.Пока знаю:
- x 16 + x 15 + x 2 +1 — многочлен: 0x18005 или 0b11000000000000101
- начальное значение 0xFFFF
- пример сообщения в шестнадцатеричном формате: 01 10 C0 03 00 01
- CRC16 вышеприведенного сообщения в шестнадцатеричном формате: C9CD
Я вычислил это вручную, как в примере выше, но я бы не стал записывать это в двоичном формате в этом вопросе. Я полагаю, что мое преобразование в двоичное правильное. Чего я не знаю, так это того, как включить начальное значение — используется ли оно для дополнения слова данных им вместо нулей? Или мне нужно изменить ответ? Что-то другое?
1-я попытка: заполнение нулями на 16 бит.
Вычисленный остаток в двоичном формате будет 1111 1111 1001 1011, что соответствуетFF9Bв шестнадцатеричном формате и неверно для CrC16 / Modbus, но верно для CRC16 / Bypass2-я попытка: заполнение единицами на 16 бит из-за начального значения. Вычисленный остаток в двоичном формате будет
0000 0000 0110 0100, что соответствует0064в шестнадцатеричном формате и является неверным.
Было бы здорово, если бы кто-нибудь мог объяснить или прояснить мои предположения. Честно говоря, я потратил много часов на поиск ответа, но каждое объяснение основано на примерах кода на C / C ++ или других языках, которых я не понимаю.Заранее спасибо.
EDIT1: Согласно этому сайту, «1-я попытка» указывает на другой CRC16-метод с таким же полиномом, но с другим начальным значением (0x0000), что говорит мне, что расчет должен быть правильным. Как мне ввести начальное значение?
EDIT2: Ответ Марка Адлерса делает свое дело. Однако теперь, когда я могу вычислить CRC16 / Modbus, осталось несколько вопросов для прояснения. Не нужно, но ценится.
A) Порядок вычисления будет следующим: …?
- 1-е применение RefIn для полного ввода (включая дополненные биты)
- 2-й
xorInitValue с (в CRC16) для первых 16 бит - Третье применение RefOut для полного вывода / остатка (максимум 16 бит в CRC16)
B) Относительно RefIn и RefOut: всегда ли он отражает 8 бит для ввода и все биты для вывода, тем не менее, я использую CRC8, CRC16 или CRC32?
C) Что означают 3-й (проверка) и 8-й (XorOut) столбцы на веб-сайте, о котором я говорю? Последнее кажется довольно простым, я предполагаю, что его можно применить, вычислив значение
xorпосле RefOut точно так же, как InitValue?c ++ — реализация CRC-CCITT — qaru
статическая константа беззнаковая короткая CRC_CCITT_TABLE [256] = { 0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7, 0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF, 0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6, 0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE, 0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485, 0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D, 0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4, 0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC, 0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823, 0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B, 0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12, 0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A, 0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41, 0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49, 0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70, 0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78, 0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F, 0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067, 0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E, 0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256, 0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D, 0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405, 0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C, 0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634, 0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB, 0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3, 0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A, 0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92, 0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9, 0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1, 0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8, 0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0 };Я использую следующий код для вычисления CRC-CCITT (0xFFFF):
беззнаковый короткий Calculate_CRC_CCITT (const unsigned char * buffer, int size) { беззнаковый короткий tmp; беззнаковый короткий crc = 0xffff; для (int i = 0; iкрк16 · уп.
go.dev Просмотреть источниквар ( CRC16_ARC = Params {0x8005, 0x0000, true, true, 0x0000, 0xBB3D, "CRC-16 / ARC"} CRC16_AUG_CCITT = Params {0x1021, 0x1D0F, false, false, 0x0000, 0xE5CC, "CRC-16 / AUG-CCITT"} CRC16_BUYPASS = Params {0x8005, 0x0000, false, false, 0x0000, 0xFEE8, "CRC-16 / BUYPASS"} CRC16_CCITT_FALSE = Params {0x1021, 0xFFFF, false, false, 0x0000, 0x29B1, "CRC-16 / CCITT-FALSE"} CRC16_CDMA2000 = Params {0xC867, 0xFFFF, false, false, 0x0000, 0x4C06, "CRC-16 / CDMA2000"} CRC16_DDS_110 = Параметры {0x8005, 0x800D, false, false, 0x0000, 0x9ECF, "CRC-16 / DDS-110"} CRC16_DECT_R = Params {0x0589, 0x0000, false, false, 0x0001, 0x007E, "CRC-16 / DECT-R"} CRC16_DECT_X = Params {0x0589, 0x0000, false, false, 0x0000, 0x007F, "CRC-16 / DECT-X"} CRC16_DNP = Params {0x3D65, 0x0000, true, true, 0xFFFF, 0xEA82, "CRC-16 / DNP"} CRC16_EN_13757 = Params {0x3D65, 0x0000, false, false, 0xFFFF, 0xC2B7, "CRC-16 / EN-13757"} CRC16_GENIBUS = Params {0x1021, 0xFFFF, false, false, 0xFFFF, 0xD64E, "CRC-16 / GENIBUS"} CRC16_MAXIM = Params {0x8005, 0x0000, true, true, 0xFFFF, 0x44C2, "CRC-16 / MAXIM"} CRC16_MCRF4XX = Params {0x1021, 0xFFFF, true, true, 0x0000, 0x6F91, "CRC-16 / MCRF4XX"} CRC16_RIELLO = Params {0x1021, 0xB2AA, true, true, 0x0000, 0x63D0, "CRC-16 / RIELLO"} CRC16_T10_DIF = Params {0x8BB7, 0x0000, false, false, 0x0000, 0xD0DB, "CRC-16 / T10-DIF"} CRC16_TELEDISK = Params {0xA097, 0x0000, false, false, 0x0000, 0x0FB3, "CRC-16 / TELEDISK"} CRC16_TMS37157 = Параметры {0x1021, 0x89EC, true, true, 0x0000, 0x26B1, "CRC-16 / TMS37157"} CRC16_USB = Параметры {0x8005, 0xFFFF, true, true, 0xFFFF, 0xB4C8, "CRC-16 / USB"} CRC16_CRC_A = Params {0x1021, 0xC6C6, true, true, 0x0000, 0xBF05, "CRC-16 / CRC-A"} CRC16_KERMIT = Params {0x1021, 0x0000, true, true, 0x0000, 0x2189, "CRC-16 / KERMIT"} CRC16_MODBUS = Параметры {0x8005, 0xFFFF, true, true, 0x0000, 0x4B37, "CRC-16 / MODBUS"} CRC16_X_25 = Параметры {0x1021, 0xFFFF, true, true, 0xFFFF, 0x906E, "CRC-16 / X-25"} CRC16_XMODEM = Params {0x1021, 0x0000, false, false, 0x0000, 0x31C3, "CRC-16 / XMODEM"} )Переменные можно использовать для создания таблицы для выбранного алгоритма.
polyеще: crc >> = 1 cur_byte >> = 1 crc = (~ crc & 0xFFFF) crc = (crc << 8) | ((crc >> 8) & 0xFF) возврат crc и 0xFFFF crc16 / crc16.go на главном сервере · sigurn / crc16 · GitHub
// Пакет crc16 реализует 16-битный контроль циклическим избыточным кодом или контрольную сумму CRC-16. // // Он предоставляет параметры для большинства известных алгоритмов CRC-16. пакет crc16 импорт "github.com/sigurn/utils" // Params представляет параметры алгоритмов CRC-16. // Подробнее о параметризации алгоритмов и описаниях параметров // можно найти здесь - http: // www. zlib.net/crc_v3.txtтип Params struct { Поли uint16 Инициализация uint16 Ссылка bool RefOut bool XorOut uint16 Чек uint16 Строка имени } // Предопределенные алгоритмы CRC-16. // Список алгоритмов с параметрами, заимствованными отсюда - http://reveng.sourceforge.net/crc-catalogue/16.htm // // Переменные можно использовать для создания таблицы для выбранного алгоритма. вар ( CRC16_ARC = Params {0x8005, 0x0000, true, true, 0x0000, 0xBB3D, "CRC-16 / ARC"} CRC16_AUG_CCITT = Params {0x1021, 0x1D0F, false, false, 0x0000, 0xE5CC, "CRC-16 / AUG-CCITT"} CRC16_BUYPASS = Params {0x8005, 0x0000, false, false, 0x0000, 0xFEE8, "CRC-16 / BUYPASS"} CRC16_CCITT_FALSE = Params {0x1021, 0xFFFF, false, false, 0x0000, 0x29B1, "CRC-16 / CCITT-FALSE"} CRC16_CDMA2000 = Params {0xC867, 0xFFFF, false, false, 0x0000, 0x4C06, "CRC-16 / CDMA2000"} CRC16_DDS_110 = Params {0x8005, 0x800D, false, false, 0x0000, 0x9ECF, "CRC-16 / DDS-110"} CRC16_DECT_R = Params {0x0589, 0x0000, false, false, 0x0001, 0x007E, "CRC-16 / DECT-R"} CRC16_DECT_X = Params {0x0589, 0x0000, false, false, 0x0000, 0x007F, "CRC-16 / DECT-X"} CRC16_DNP = Params {0x3D65, 0x0000, true, true, 0xFFFF, 0xEA82, "CRC-16 / DNP"} CRC16_EN_13757 = Params {0x3D65, 0x0000, false, false, 0xFFFF, 0xC2B7, "CRC-16 / EN-13757"} CRC16_GENIBUS = Params {0x1021, 0xFFFF, false, false, 0xFFFF, 0xD64E, "CRC-16 / GENIBUS"} CRC16_MAXIM = Params {0x8005, 0x0000, true, true, 0xFFFF, 0x44C2, "CRC-16 / MAXIM"} CRC16_MCRF4XX = Params {0x1021, 0xFFFF, true, true, 0x0000, 0x6F91, "CRC-16 / MCRF4XX"} CRC16_RIELLO = Params {0x1021, 0xB2AA, true, true, 0x0000, 0x63D0, "CRC-16 / RIELLO"} CRC16_T10_DIF = Params {0x8BB7, 0x0000, false, false, 0x0000, 0xD0DB, "CRC-16 / T10-DIF"} CRC16_TELEDISK = Params {0xA097, 0x0000, false, false, 0x0000, 0x0FB3, "CRC-16 / TELEDISK"} CRC16_TMS37157 = Params {0x1021, 0x89EC, true, true, 0x0000, 0x26B1, "CRC-16 / TMS37157"} CRC16_USB = Params {0x8005, 0xFFFF, true, true, 0xFFFF, 0xB4C8, "CRC-16 / USB"} CRC16_CRC_A = Params {0x1021, 0xC6C6, true, true, 0x0000, 0xBF05, "CRC-16 / CRC-A"} CRC16_KERMIT = Params {0x1021, 0x0000, true, true, 0x0000, 0x2189, "CRC-16 / KERMIT"} CRC16_MODBUS = Params {0x8005, 0xFFFF, true, true, 0x0000, 0x4B37, "CRC-16 / MODBUS"} CRC16_X_25 = Params {0x1021, 0xFFFF, true, true, 0xFFFF, 0x906E, "CRC-16 / X-25"} CRC16_XMODEM = Params {0x1021, 0x0000, false, false, 0x0000, 0x31C3, "CRC-16 / XMODEM"} ) // Таблица - это таблица из 256 слов, представляющая параметры полинома и алгоритма для эффективной обработки. = params.Поли} } table.data [n] = crc } стол возврата } // Init возвращает начальное значение для регистра CRC, соответствующее указанному алгоритму. func Init (таблица * таблица) uint16 { return table.params.Init } // Обновление возвращает результат добавления байтов данных в crc. func Update (crc uint16, data [] byte, table * Table) uint16 { для _, d: = данные диапазона { , если таблица.г] } возврат crc } // Complete возвращает результат вычисления CRC и поствычисления обработки CRC. func Complete (crc uint16, table * Table) uint16 { , если таблица. table.params.XorOut} // Checksum возвращает контрольную сумму CRC данных с использованием указанного алгоритма, представленного таблицей. func Контрольная сумма (байт данных [], таблица * таблица) uint16 { crc: = Init (таблица) crc = Update (crc, data, table) возврат завершен (crc, table) } узел-crc16 - npm
MODBUS - это протокол обмена сообщениями прикладного уровня, расположенный на уровне 7 модели OSI.Он обеспечивает связь клиент / сервер между устройствами, подключенными к разным типам шин или сетей.
CRC(Cyclic Redundancy Check) часть протокола, например MODBUS по последовательной линии (Страница 42) и Modbus-RTU (Страница 75), использовать один и тот же алгоритм.node-crc16реализует версию этого алгоритма для C ++ путем просмотра таблицы, а также предоставляет собственный надстройку узла и оболочку версии nodejs.Этот модуль был хорошо протестирован и задокументирован.
Версии
Если ваша версия node.js ниже, чем
v8.xx, используйте последнюю версиюv1.xxэтого модуля, или вы должны выбратьv2.xx, который используетNAPIдля изящной реализации собственного аддона. и совместимо.Использование
Советы: наиболее интуитивно понятное описание этого модуля - это комментарий в src и код в модульном тесте :).
Установить
npm install node-crc16генерирует сумму по
crc16. checkSum checkSumпринимает три параметра, первые два параметра(ввод, [кодировка])создаютбуферcrc16.checkSum ('строка utf8', 'utf8')
по умолчанию
кодировка-шестнадцатеричныйvar sum = crc16.checkSum ('a031ffb7');
sum.should.equal ('726d');
третий параметр -
вариант， тип -Объект-
опция.retTypeустанавливает формат возвращаемой суммы- по умолчанию
шестнадцатеричный， двухбайтная шестнадцатеричная строка BigEndian,726d -
массив, два беззнаковых символа возвращаемой суммы 21[114, 109] -
int， одно беззнаковое короткое число возвращаемой суммы ，29293 -
буфер， Тип буфера возвращаемой суммы ，
- по умолчанию
var sum = crc16.checkSum ('a031ffb7', {retType: 'массив'});
sum.should.eql ([114, 109]);
проверить сумму по
crc16.verifySumПараметры
verifySumтакие же, какcheckSum, первые два параметра используются для созданияBuffer, который содержит суммуvar stream = 'a031ffb7',
sum = '726d';
var isValid = crc16.verifySum (поток + сумма);
действительно.should.equal (правда);
Вклад
получить исходный код
git clone [email protected]: imnemo / crc16.git
cd crc16
структура кода
├── lib // Реализация алгоритма CRC16 в c ++ ├── util // Служебные функции ├── src // Нативный аддон Node ├── test // Модульное тестирование JS ├── test_cpp // Модульное тестирование C ++ ├── index.js // Основная запись модуля NodeJSустановить зависимости
npm установитьМодульное тестирование C ++
Реализация алгоритма проверки и подтверждения
CRC16в C ++ является автономной в.. Если вы хотите его изменить, напишите подходящие примеры unittest. Вы можете сослаться на Catch, а затем запустить: /lib/crc16.cc Убедитесь, что все случаи модульного тестирования пройдены после внесения изменений.
Модульное тестирование JS
npm testили./node_modules/.bin/mocha --reporter specТест
используйте benchmark.js
>>> npm запустить тест
> [email protected] Benchmark / Users / nemo / code / imnemo / crc16
> node benchmark / benchmark.js
CEC16 # checkSum x
1 ops / sec ± 2,00% (выбрано 83 прогона) CRC16 # verifySum x 1540940 ops / сек ± 19,92% (отобрано 65 прогонов)
Самый быстрый - CRC16 # verifySum
использовать nanobench
>>> npm run nanobench
> [email protected] nanobench / Users / nemo / code / imnemo / crc16
> node benchmark / nanobench.js
NANOBENCH версия 2
> /Users/nemo/.nvm/versions/node/v8.1.2/bin/node benchmark / nanobench.js
ok ~ 3,17 с (3 с + 166422442 нс)
ок ~ 2,85 с (2 с + 848059820 нс)
все тесты выполнены
ок ~ 6,01 с (6 с + 14482262 нс)
запрос на вытягивание
Вы можете получить запрос, выполнив все шаги, указанные выше.
TODO
twitter: @imoncoding
Добро пожаловать, чтобы подписаться на мой WeChat!
Лицензия
crc16.tcl
crc16.tclпакет требует Tcl 8.2; пространство имен eval :: crc { экспорт пространства имен crc16 crc-ccitt crc-32 переменная crc16_version 1.1.1 переменный многочлен установить полином (crc16) [expr {(1 << 16) | (1 << 15) | (1 << 2) | 1}] установить полином (ccitt) [expr {(1 << 16) | (1 << 12) | (1 << 5) | 1}] установить полином (crc32) [expr {(1 << 32) | (1 << 26) | (1 << 23) | (1 << 22) | (1 << 16) | (1 << 12) | (1 << 11) | (1 << 10) | (1 << 8) | (1 << 7) | (1 << 5) | (1 << 4) | (1 << 2) | (1 << 1) | 1}] таблица переменных if {! [информация существует таблица]} {таблица набора массивов {}} переменная signbit if {! [информация существует signbit]} { переменная v for {set v 1} {int ($ v)! = 0} {установить signbit $ v; установить v [выражение {$ v << 1}]} {} снять v } } proc :: crc :: Crc_table {отраженная ширина поли} { установить tbl {} if {$ width <32} { установить маску [выражение {(1 << $ width) - 1}] установить верхний бит [выражение {1 << ($ width - 1)}] } еще { установить маску 0xffffffff установить topbit 0x80000000 } для {set i 0} {$ i <256} {incr i} { если {$ отражено} { установить r [отразить $ i 8] } еще { установить r $ i } установить r [выражение {$ r << ($ width - 8)}] для {set k 0} {$ k <8} {incr k} { если {[выражение {$ r & $ topbit}]! = 0} { установить r [выражение {($ r << 1) ^ $ poly}] } еще { установить r [выражение {$ r << 1}] } } если {$ отражено} { установить r [отразить ширину $ r $] } Lappend tbl [выражение {$ r & $ mask}] } вернуть $ tbl } proc :: crc :: Crc {s width table {init 0} {xorout 0} {отражено 0}} { upvar $ table tbl переменная signbit установить маску знака [выражение {~ $ знакбит >> 7}] if {$ width <32} { установить маску [выражение {(1 << $ width) - 1}] установить rot [выражение {$ width - 8}] } еще { установить маску 0xffffffff установить гниль 24 } установить crc $ init двоичное сканирование $ s c * data foreach {datum} $ data { если {$ отражено} { установить ndx [выражение {($ crc ^ $ datum) & 0xFF}] установить lkp [lindex $ tbl $ ndx] установить crc [выражение {($ lkp ^ ($ crc >> 8 & $ signmask)) & $ mask}] } еще { установить ndx [выражение {(($ crc >> $ rot) ^ $ datum) & 0xFF}] установить lkp [lindex $ tbl $ ndx] установить crc [выражение {($ lkp ^ ($ crc << 8 & $ signmask)) & $ mask}] } } возврат [выражение {$ crc ^ $ xorout}] } proc :: crc :: reflection {v b} { установить t $ v для {set i 0} {$ i <$ b} {incr i} { установить v [выражение {($ t & 1)? ($ v | (1 << (($ b-1) - $ i))): ($ v & ~ (1 << (($ b-1) - $ i)))}] установить t [выражение {$ t >> 1}] } вернуть $ v } proc :: crc :: Pop {varname {nth 0}} { upvar $ varname args установить r [lindex $ args $ nth] установить аргументы [lreplace $ args $ nth $ nth] вернуть $ r } proc :: crc :: CRC16 {s {seed 0}} { таблица переменных if {! [информация существует таблица (crc16)]} { переменный многочлен установить таблицу (crc16) [Crc_table 16 $ polynomial (crc16) 1] } return [Crc $ s 16 [текущее пространство имен] :: table (crc16) $ seed 0 1] } proc :: crc :: CRC-CCITT {s {seed 0} {xor 0}} { таблица переменных if {! [информация существует таблица (ccitt)]} { переменный многочлен установить таблицу (ccitt) [Crc_table 16 $ polynomial (ccitt) 0] } return [Crc $ s 16 [текущее пространство имен] :: table (ccitt) $ seed $ xor 0] } proc :: crc :: CRC-32 {s {seed 0xFFFFFFFF}} { таблица переменных if {! [информация существует таблица (crc32)]} { переменный многочлен установить таблицу (crc32) [Crc_table 32 $ polynomial (crc32) 1] } return [Crc $ s 32 [текущее пространство имен] :: table (crc32) $ seed 0xFFFFFFFF 1] } proc :: crc :: crc {args} { набор массивов opts [list filename {} channel {} chunksize 4096 \ формат% u seed 0 \ impl [CRC16 происхождения пространства имен]] while {[совпадение строки - * [установить параметр [lindex $ args 0]]]} { switch -glob - $ option { -fi * {set opts (имя файла) [Pop args 1]} -cha * {set opts (канал) [Pop args 1]} -chu * {set opts (chunksize) [Pop args 1]} -fo * {set opts (формат) [Pop args 1]} -i * {set opts (impl) [источник пространства имен верхнего уровня 1 [Pop args 1]]} -s * {set opts (seed) [Pop args 1]} - {Pop args; перерыв } дефолт { установить параметры [join [lsort [выбор имен массивов]] ", -"] ошибка кода возврата "плохой вариант $ option: \ должен быть одним из - $ options " } } Всплывающие аргументы } if {$ opts (filename)! = {}} { установить opts (канал) [открыть $ opts (имя файла) r] fconfigure $ opts (канал) -трансляция двоичного файла } if {$ opts (channel)! = {}} { установить r $ opts (начальное число) установить trans [fconfigure $ opts (channel) -translation] fconfigure $ opts (канал) -трансляция двоичного файла а {! [eof $ opts (канал)]} { установить блок [читать $ opts (канал) $ opts (размер блока)] установить r [$ opts (impl) $ chunk $ r] } fconfigure $ opts (канал) -translation $ trans if {$ opts (filename)! = {}} { закрыть $ opts (канал) } } еще { if {[llength $ args]! = 1} { ошибка кода возврата "неверный \ # аргументы: должно быть \ \ "crc16? -format string?? -seed value?? -impl procname? \ имя файла | данные\"" } установить r [$ opts (impl) [lindex $ args 0] $ opts (seed)] } return [формат $ opts (формат) $ r] } proc :: crc :: crc16 {args} { return [eval [list crc -impl [CRC16 происхождения пространства имен]] $ args] } proc :: crc :: crc-ccitt {args} { return [eval [list crc -impl [CRC-CCITT происхождения пространства имен] -seed 0xFFFF] \ $ args] } proc :: crc :: xmodem {args} { return [eval [list crc -impl [источник CRC-CCITT пространства имен] -seed 0] $ args] } proc :: crc :: crc-32 {args} { return [eval [list crc -impl [CRC-32 происхождения пространства имен] -seed 0xFFFFFFFF] \ $ args] } пакет предоставляет crc16 $ crc :: crc16_version
.
CRCHi[TableIdx];
Что, зачем и как — radiohlam.ru
Причём нулевые коэффициенты при старших степенях можно опустить (в дальнейшем вы увидите, что нулевые коэффициенты при старших степенях ни на что не влияют) и написать его в виде 11000100110101.
Деление будет выглядеть так, как на рисунке справа.
Значение регистра после обработки всего сообщения — это и есть CRC.
Значит если посчитать CRC для этой разности — он будет равен нулю.
Кроме того, поскольку коэффициенты при старшей и младшей степенях порождающего полинома всегда равны 1, то один из этих коэффициентов могут опускать. Например, полином, рассматриваемый нами в примерах, может быть записан следующими способами:
Вычисленный остаток в двоичном формате будет 
poly
zlib.net/crc_v3.txt
= params.Поли
table.params.XorOut
checkSum 
/lib/crc16.cc 