Сакральный алгоритм расчёта CRC16, описанный в литературе и связанный с побитовым сдвигом, плохо вписывается в формат вычислительных возможностей ПЛК и МК. Во-первых, постольку, поскольку его реализация отнимает изрядный объем вычислительных ресурсов вышеозначенных устройств, во-вторых, потому что в ходе такого расчета существенно растягивается время скана программы. Рост скана программы обусловлен тем, что, вследствие словной или байтовой организации аккумулятора арифметико-логического устройства, результирующие битовые операции со словами/байтами в нём выполняются гораздо дольше операций со словами/байтами целиком. В отдельных устройствах операции побитового сдвига и вовсе не поддерживаются, тогда как алгоритм подразумевает выполнение восьми циклов с такими операциями.
В целях сокращения объема вычислений и, как следствие, времени сканирования при обработке CRC, часто применяется иной алгоритм — табличный, когда таблица масок рассчитывается и заполняется единожды в первом скане программы. Тем не менее, и этот способ не лишён недостатка, ибо также потребляет ресурсы. 512 байт (или 256 двухбайтных слов), порою, отнюдь не лишние.
А можно ли видоизменить алгоритм расчёта CRC таким образом, чтобы отказаться от применения побитовых сдвигов и таблиц? Безусловно, да. Достаточно лишь внимательно приглядеться к алгоритму с побитовым сдвигом.
Напомню его суть:
Почему это реализовано так, а не иначе? Да потому, что такая алгоритмизация представлялась наиболее подходящей для реализации посредством аппаратной логики.
Внимательно взглянув на этот алгоритм, нетрудно обнаружить, что фактически мы имеем дело с циклическим побитовым сдвигом слова. За его цикличность отвечает старший бит полинома. В результате, значение старшего битового разряда CRC после каждого сдвига идентично значению выдвинутого младшего. Таким образом, при осуществлении циклического побитового сдвига, полином, с которым затем необходимо производить сложение по модулю 2, трансформируется в 16#2001.
Подобных сдвигов выполняется восемь… Проще говоря, в глобальном плане речь идёт о перемене местами младшего байта CRC со старшим её байтом. А это наводит на мысль, что, после сложения по модулю 2 очередного байта массива посылки с младшим байтом CRC, достаточно поменять местами младший и старший байт CRC, а затем, последовательно проанализировав восемь бит старшего её байта, начав с младшего его разряда, восьмого, произвести сложение СRC по модулю 2 c известными константами, предопределёнными значением полинома, значение которого для Modbus CRC16, как уже указано выше, эквивалентно 16#2001.
Итоговый алгоритм для учёта в CRC очередного байта массива посылки выглядит следующим образом:
Осуществляется сложение по модулю 2 очередного байта массива посылки с младшим байтом двухбайтовой CRC, после чего младший и старший байт CRC меняются местами;
Преимущества такого способа расчёта:
1) По сравнению с алгоритмом побитового сдвига:
а) предложенный алгоритм позволяет избавиться от команд вложенного цикла FOR-NEXT и команд побитового сдвига в таком цикле, при том, число количество исполняемых команд сложения по модулю 2 сохраняется неизменным;
б) в контроллерах c поддержкой команды SWAP, восьмикратный побитовый сдвиг CRC заменяется единственной командой, а в контроллерах, такую команду не поддерживающих, — одной или двумя командами пересылки, входящими в число базовых команд контроллера и отнимающими минимальное время;
2) По сравнению с табличным методом расчёта, этот метод не нуждается в выделении места в памяти данных под таблицу, в её предварительном заполнении, в выборке соответствующей маски из таблицы с последующим ее наложением на байт CRC.
Проработка предложенного алгоритма расчёта СRC16 изначально велась для ПЛК Mitsubishi моделей FX3S/3G, не поддерживающих инструкций расчёта СRC и перемены местами байт в слове, между тем, предельное суммарное время расчета СRC с применением указанного алгоритма для массива посылки, состоящего из 128 байт, не превышает 2,4мс.
В целях сокращения объема вычислений и, как следствие, времени сканирования при обработке 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мс.
Комментарии (17)
netch80
24.05.2018 18:52Вопросы по алгоритму
1. Шаги проверки по битам и последующего условного XOR выполняются на основании первой части действия (обмен байтов) или каждый следующий на основании результата предыдущего шага?
2. В итоге получается сколько вероятно ненулевых бит в сумме — 8, 9, 16?AssemblerKing Автор
24.05.2018 20:05По первому вопросу: каждый последующий на основании результата предыдущего.
Существо второго заданного Вами вопроса мне не понятно.
MacIn
Простите, а в чем преимущество?
При сдвиге вы получаете этот «анализ» автоматом — анализ старшего бита скорее всего скорее всего возможен, как анализ знака. А в вашем алгоритме — как вы будете анализировать произвольный бит? Чем анализ произвольных 8 бит лучше анализа старшего бита в цикле 8 раз подряд?
rafuck
Только нужен не анализ старшего бита, а значение младшего перед сдвигом, что еще проще. Но тут, насколько я понимаю, приведен алгоритм для архитектур, не имеющих операции битового сдвига.
AssemblerKing Автор
Именно. Программируемый логический контроллер, как и микроконтроллер, в части выполнения команд ведёт себя совсем иначе, нежели комп. Даже если архитектура такие команды поддерживает, их время выполнения многократно выше. Команды цикла также отнимают время: только блок команд FOR-NEXT отнимает втрое больше времени, по сравнению с командой WXOR.
rafuck
Ну, тут вы по сути развернули цикл, избавившись от счетчика и 8 условных переходов. Если бы архитектурно поддерживался сдвиг, то точно также можно было развернуть исходный цикл.
AssemblerKing Автор
Развернув цикл, получаете восемь команд побитового сдвига плюс восемь команд сложения по модулю два. В предложенном мной алгоритме остаются только восемь команд сложения по модулю два и одна команда переворота байт в слове. Как полагаете, есть ли разница во времени обработки байта посылки между первым и вторым алгоритмом?
rafuck
Я всего лишь сказал, что отсутствие цикла — это восе не преимущество вашего подхода. Поэтому вот эта фраза завучит несколько странно:
AssemblerKing Автор
Постарайтесь понять, что между ПК и ПЛК (или МК), большая разница. Тут биться следует вовсе не за уменьшение длины кода, хотя это тоже немаловажно, а за сокращение времени выполнения процедуры.
rafuck
Постараюсь. А вы постарайтесь ответить на вопрос.
А ДО вашего предложения исходный алгоритм не позволял избавиться от вложенного цикла из восьми итераций?
AssemblerKing Автор
Избавиться-то было можно, расписав последовательность команд тела цикла. Только пользы от этого не было никакой — время выполнения это бы сократило на малую толику, зато привело бы к росту длины кода. С предложенным алгоритмом исчезла необходимость в побитовом сдвиге и в самих командах организации цикла, избавление от которых, на фоне оставшихся команд сложения по модулю 2, уже дает заметное сокращение времени выполнения процедуры.
AssemblerKing Автор
Для наглядности:
— время выполнения процедуры обработки с побитовым сдвигом в цикле по максимуму занимает 77,22мкс;
— просто отказ от команд цикла с его развертыванием сокращает это время на 4,98мкс, или на 6,45%;
— время выполнения процедуры обработки по предложенному мной алгоритму по максимуму занимает 12,12мкс, что дает сокращение времени обработки на 84,3%.
MacIn
Это — особенности архитектуры — стоило бы добавить в статью.
AssemblerKing Автор
Об особенностях архитектуры сказано в первом абзаце статьи:
MacIn
Верно, но меня смутила общая формулировка «результирующие битовые операции».
Также вы не ответили на вопрос про анализ произвольного бита — как он выполняется на вашей аппаратуре? Отсюда и возникли сомнения — как выполняется анализ произвольного бита, попадает ли это под «результирующие битовые операции». Входит ли сдвиг в это понятие и т.д.
Если вы выполняете анализ путем наложения маски, то все равно нужен условный переход, как и в случае со сдвигом (допустим, цикл уже развернут). Насколько маска быстрее, чем сдвиг — это не описано, и это я имел в виду под «стоило бы добавить». Не до конца ясно, какими командами вы обладаете и какие у них тайминги.
AssemblerKing Автор
Теперь понятно, что Вас смущает) В программируемых логических контроллерах, ПЛК, имеется битовая память — т.н. меркеры. И все операции с вычислением CRC осуществляются в ней. В такой памяти, памяти меркеров, можно оперировать как отдельными битами, так и их группами (тетрадами, байтами, словами и т.д.). Команды анализа бита в такой памяти входят в пул основных команд ПЛК, т.к. функция ПЛК, прежде всего, обработка цепочек образованных сигналами с бинарными состояниями «истина/ложь».
Время выполнения команды анализа значения бита в том ПЛК, для которого прорабатывался алгоритм, составляет 0,21мкс. Команды сложения по модулю 2 для слова (или байта, или тетрады) — 1,24мкс. Тогда как команда сложения по модулю 2 для отдельных бит ПЛК не поддерживается и её реализация требует 6 команд со временем выполнения 0,21мкс каждая: 6*0,21=1,26мкс.
AssemblerKing Автор
P.S. Анализ бита под «результирующие битовые операции» со словами не подпадает, как и операции модифицирующие значение отдельного бита. Под «результирующими битовыми» мной имелись в виду именно операции побитового сдвига слова, так как операции с отдельно взятыми битами выполняются в битовом аккумуляторе — стеке логических операций, а операции со словами уже в другом аккумуляторе, с пословной организацией.