Комментарии 23
а затем, последовательно проанализировав восемь бит старшего её байта,
Простите, а в чем преимущество?
При сдвиге вы получаете этот «анализ» автоматом — анализ старшего бита скорее всего скорее всего возможен, как анализ знака. А в вашем алгоритме — как вы будете анализировать произвольный бит? Чем анализ произвольных 8 бит лучше анализа старшего бита в цикле 8 раз подряд?
Только нужен не анализ старшего бита, а значение младшего перед сдвигом, что еще проще. Но тут, насколько я понимаю, приведен алгоритм для архитектур, не имеющих операции битового сдвига.
Именно. Программируемый логический контроллер, как и микроконтроллер, в части выполнения команд ведёт себя совсем иначе, нежели комп. Даже если архитектура такие команды поддерживает, их время выполнения многократно выше. Команды цикла также отнимают время: только блок команд FOR-NEXT отнимает втрое больше времени, по сравнению с командой WXOR.
Ну, тут вы по сути развернули цикл, избавившись от счетчика и 8 условных переходов. Если бы архитектурно поддерживался сдвиг, то точно также можно было развернуть исходный цикл.
Развернув цикл, получаете восемь команд побитового сдвига плюс восемь команд сложения по модулю два. В предложенном мной алгоритме остаются только восемь команд сложения по модулю два и одна команда переворота байт в слове. Как полагаете, есть ли разница во времени обработки байта посылки между первым и вторым алгоритмом?
Я всего лишь сказал, что отсутствие цикла — это восе не преимущество вашего подхода. Поэтому вот эта фраза завучит несколько странно:
Команды цикла также отнимают время: только блок команд FOR-NEXT отнимает втрое больше времени, по сравнению с командой WXOR.
Постарайтесь понять, что между ПК и ПЛК (или МК), большая разница. Тут биться следует вовсе не за уменьшение длины кода, хотя это тоже немаловажно, а за сокращение времени выполнения процедуры.
Постараюсь. А вы постарайтесь ответить на вопрос.
А ДО вашего предложения исходный алгоритм не позволял избавиться от вложенного цикла из восьми итераций?
предложенный алгоритм позволяет избавиться от команд вложенного цикла FOR-NEXT
А ДО вашего предложения исходный алгоритм не позволял избавиться от вложенного цикла из восьми итераций?
Избавиться-то было можно, расписав последовательность команд тела цикла. Только пользы от этого не было никакой — время выполнения это бы сократило на малую толику, зато привело бы к росту длины кода. С предложенным алгоритмом исчезла необходимость в побитовом сдвиге и в самих командах организации цикла, избавление от которых, на фоне оставшихся команд сложения по модулю 2, уже дает заметное сокращение времени выполнения процедуры.
Для наглядности:
— время выполнения процедуры обработки с побитовым сдвигом в цикле по максимуму занимает 77,22мкс;
— просто отказ от команд цикла с его развертыванием сокращает это время на 4,98мкс, или на 6,45%;
— время выполнения процедуры обработки по предложенному мной алгоритму по максимуму занимает 12,12мкс, что дает сокращение времени обработки на 84,3%.
— время выполнения процедуры обработки с побитовым сдвигом в цикле по максимуму занимает 77,22мкс;
— просто отказ от команд цикла с его развертыванием сокращает это время на 4,98мкс, или на 6,45%;
— время выполнения процедуры обработки по предложенному мной алгоритму по максимуму занимает 12,12мкс, что дает сокращение времени обработки на 84,3%.
Это — особенности архитектуры — стоило бы добавить в статью.
Об особенностях архитектуры сказано в первом абзаце статьи:
вследствие словной или байтовой организации аккумулятора арифметико-логического устройства, результирующие битовые операции со словами/байтами в нём выполняются гораздо дольше операций со словами/байтами целиком, а в отдельных устройствах эти операции и вовсе не поддерживаются, тогда как алгоритм подразумевает выполнение восьми циклов с такими операциями.
Верно, но меня смутила общая формулировка «результирующие битовые операции».
Также вы не ответили на вопрос про анализ произвольного бита — как он выполняется на вашей аппаратуре? Отсюда и возникли сомнения — как выполняется анализ произвольного бита, попадает ли это под «результирующие битовые операции». Входит ли сдвиг в это понятие и т.д.
Если вы выполняете анализ путем наложения маски, то все равно нужен условный переход, как и в случае со сдвигом (допустим, цикл уже развернут). Насколько маска быстрее, чем сдвиг — это не описано, и это я имел в виду под «стоило бы добавить». Не до конца ясно, какими командами вы обладаете и какие у них тайминги.
Также вы не ответили на вопрос про анализ произвольного бита — как он выполняется на вашей аппаратуре? Отсюда и возникли сомнения — как выполняется анализ произвольного бита, попадает ли это под «результирующие битовые операции». Входит ли сдвиг в это понятие и т.д.
Если вы выполняете анализ путем наложения маски, то все равно нужен условный переход, как и в случае со сдвигом (допустим, цикл уже развернут). Насколько маска быстрее, чем сдвиг — это не описано, и это я имел в виду под «стоило бы добавить». Не до конца ясно, какими командами вы обладаете и какие у них тайминги.
Теперь понятно, что Вас смущает) В программируемых логических контроллерах, ПЛК, имеется битовая память — т.н. меркеры. И все операции с вычислением CRC осуществляются в ней. В такой памяти, памяти меркеров, можно оперировать как отдельными битами, так и их группами (тетрадами, байтами, словами и т.д.). Команды анализа бита в такой памяти входят в пул основных команд ПЛК, т.к. функция ПЛК, прежде всего, обработка цепочек образованных сигналами с бинарными состояниями «истина/ложь».
Время выполнения команды анализа значения бита в том ПЛК, для которого прорабатывался алгоритм, составляет 0,21мкс. Команды сложения по модулю 2 для слова (или байта, или тетрады) — 1,24мкс. Тогда как команда сложения по модулю 2 для отдельных бит ПЛК не поддерживается и её реализация требует 6 команд со временем выполнения 0,21мкс каждая: 6*0,21=1,26мкс.
Время выполнения команды анализа значения бита в том ПЛК, для которого прорабатывался алгоритм, составляет 0,21мкс. Команды сложения по модулю 2 для слова (или байта, или тетрады) — 1,24мкс. Тогда как команда сложения по модулю 2 для отдельных бит ПЛК не поддерживается и её реализация требует 6 команд со временем выполнения 0,21мкс каждая: 6*0,21=1,26мкс.
P.S. Анализ бита под «результирующие битовые операции» со словами не подпадает, как и операции модифицирующие значение отдельного бита. Под «результирующими битовыми» мной имелись в виду именно операции побитового сдвига слова, так как операции с отдельно взятыми битами выполняются в битовом аккумуляторе — стеке логических операций, а операции со словами уже в другом аккумуляторе, с пословной организацией.
Вопросы по алгоритму
1. Шаги проверки по битам и последующего условного XOR выполняются на основании первой части действия (обмен байтов) или каждый следующий на основании результата предыдущего шага?
2. В итоге получается сколько вероятно ненулевых бит в сумме — 8, 9, 16?
1. Шаги проверки по битам и последующего условного XOR выполняются на основании первой части действия (обмен байтов) или каждый следующий на основании результата предыдущего шага?
2. В итоге получается сколько вероятно ненулевых бит в сумме — 8, 9, 16?
На c# код может выглядеть так:
public static byte[] Crc16( byte[] bytes )
{
int hi = 0xFF, lo = 0xFF;
foreach ( var t in bytes )
{
var b = ( byte ) ( lo ^ t );
lo = hi; hi = b;
if ( ( hi & 0x01 ) != 0 ) { hi ^= 0x02; lo ^= 0x40; }
if ( ( hi & 0x02 ) != 0 ) { hi ^= 0x04; lo ^= 0x80; }
if ( ( hi & 0x04 ) != 0 ) hi ^= 0x09;
if ( ( hi & 0x08 ) != 0 ) hi ^= 0x12;
if ( ( hi & 0x10 ) != 0 ) hi ^= 0x24;
if ( ( hi & 0x20 ) != 0 ) hi ^= 0x48;
if ( ( hi & 0x40 ) != 0 ) hi ^= 0x90;
if ( ( hi & 0x80 ) != 0 ) { hi ^= 0x20; lo ^= 0x01; }
}
return new [] { ( byte ) lo, ( byte ) hi };
}
Простой тест. Сохраните код в текстовом файле Crc16.cs.cmd и запустите этот скрипт.
Результат должен быть таким:
/*
@echo off && cls
set dotnet=%windir%\Microsoft.NET\Framework
for %%n in (2.0.50727,3.5,4.0.30319) do if exist "%dotnet%\v%%n\csc.exe" set csc="%dotnet%\v%%n\csc.exe"
( %csc% /nologo /out:"%~0.exe" %0 && "%~0.exe" ) && del "%~0.exe"
exit
*/
using System;
using System.Collections.Generic;
class Program
{
public static byte[] Crc16( byte[] bytes )
{
int hi = 0xFF, lo = 0xFF;
foreach ( var t in bytes )
{
var b = ( byte ) ( lo ^ t );
lo = hi; hi = b;
if ( ( hi & 0x01 ) != 0 ) { hi ^= 0x02; lo ^= 0x40; }
if ( ( hi & 0x02 ) != 0 ) { hi ^= 0x04; lo ^= 0x80; }
if ( ( hi & 0x04 ) != 0 ) hi ^= 0x09;
if ( ( hi & 0x08 ) != 0 ) hi ^= 0x12;
if ( ( hi & 0x10 ) != 0 ) hi ^= 0x24;
if ( ( hi & 0x20 ) != 0 ) hi ^= 0x48;
if ( ( hi & 0x40 ) != 0 ) hi ^= 0x90;
if ( ( hi & 0x80 ) != 0 ) { hi ^= 0x20; lo ^= 0x01; }
}
return new [] { ( byte ) lo, ( byte ) hi };
}
static void Main( string[] args )
{
var query = new List<byte> { 0x01, 0x03, 0x00, 0x02, 0x00, 0x01 };
query.AddRange( Crc16( query.ToArray() ) );
Console.WriteLine( BitConverter.ToString( query.ToArray() ) );
Console.ReadKey();
}
}
Результат должен быть таким:
01-03-00-02-00-01-25-CA
Версия из мира C99. nData — массив до 255 байт
uint16_t MODBUS_CRC16(const uint8_t *nData, uint16_t wLength){
union{
uint8_t u8[2];
uint16_t u16;
}val;
val.u16 = 0xFFFF;
for(uint_least8_t i=0;i<wLength;i++){ //до 255 элементов при подсчете CRC, иначе другой тип i
uint_least8_t b = val.u8[0] ^ nData[i];
val.u8[0] = val.u8[1]; val.u8[1] = b;
if ( ( val.u8[1] & 0x01 ) != 0 ) { val.u8[1] ^= 0x02; val.u8[0] ^= 0x40;}
if ( ( val.u8[1] & 0x02 ) != 0 ) { val.u8[1] ^= 0x04; val.u8[0] ^= 0x80; }
if ( ( val.u8[1] & 0x04 ) != 0 ) val.u8[1] ^= 0x09;
if ( ( val.u8[1] & 0x08 ) != 0 ) val.u8[1] ^= 0x12;
if ( ( val.u8[1] & 0x10 ) != 0 ) val.u8[1] ^= 0x24;
if ( ( val.u8[1] & 0x20 ) != 0 ) val.u8[1] ^= 0x48;
if ( ( val.u8[1] & 0x40 ) != 0 ) val.u8[1] ^= 0x90;
if ( ( val.u8[1] & 0x80 ) != 0 ) { val.u8[1] ^= 0x20; val.u8[0] ^= 0x01; }
}
return val.u16;
}Пример использования:
uint8_t nData[] = {0x01, 0x06, 0x03, 0xE9, 0x00, 0x10, 0x59, 0xB6};
uint8_t wLength = 8;
uint16_t myCRC = MODBUS_CRC16(nData,wLength);
printf("0x%04x\n", n);Вариант для CRC-16-CCITT (0x1021, c#):
/*
@echo off && cls
set dotnet=%windir%\Microsoft.NET\Framework
for %%n in (2.0.50727,3.5,4.0.30319) do if exist "%dotnet%\v%%n\csc.exe" set csc="%dotnet%\v%%n\csc.exe"
( %csc% /nologo /out:"%~0.exe" %0 && "%~0.exe" ) && del "%~0.exe"
exit
*/
using System;
using System.Collections.Generic;
class Program
{
public static byte[] Crc16( byte[] bytes )
{
int hi = 0xFF, lo = 0xFF;
foreach ( var b in bytes )
{
var t = ( byte ) ( lo ^ b );
lo = hi; hi = t;
// Место флага (старшего разряда) занимает появляющийся при сдвиге влево нулевой разряд.
// Его комбинация (XOR) с младшим разрядом полинома 0x1021 должна всегда давать единицу.
// Поскольку флаг всегда равен единице, то мы должны обнулить младший разряд полинома,
// чтобы получить результат итерации аналогичный другим методам.
// По-простому: мы двигаем на каждой из 8 итераций не текущее значение crc, а полином, но
// в обратную сторону. Причём сдвиг циклический, т.к. в оригинале при сдвиге влево каждый
// раз получается один нулевой битик. Мы суём его на место старшего разряда, который нас
// безвременно покидает.
// 0001000000100001 1021 - полином
// Расчёт констант:
// 0000 1000 0001 0000 (0x1021 >> 1) & 0x7FFF = 0x0810
// 0000 0100 0000 1000 (0x1021 >> 2) & 0xBFFF = 0x0408
// 0000 0010 0000 0100 (0x1021 >> 3) & 0xDFFF = 0x0204
// 0000 0001 0000 0010 (0x1021 >> 4) & 0xEFFF = 0x0102
// 0000 0000 1000 0001 (0x1021 >> 5) & 0xF7FF = 0x0081
// 1000 0000 0100 0000 (0x1021 >> 6) & 0xFBFF = 0x8040
// 0100 0000 0010 0000 (0x1021 >> 7) & 0xFDFF = 0x4020
// 0010 0000 0001 0000 (0x1021 >> 8) & 0xFEFF = 0x2010
if ( ( hi & 0x80 ) != 0 ) { hi ^= 0x08; lo ^= 0x10; }
if ( ( hi & 0x40 ) != 0 ) { hi ^= 0x04; lo ^= 0x08; }
if ( ( hi & 0x20 ) != 0 ) { hi ^= 0x02; lo ^= 0x04; }
if ( ( hi & 0x10 ) != 0 ) { hi ^= 0x01; lo ^= 0x02; }
if ( ( hi & 0x08 ) != 0 ) { hi ^= 0x00; lo ^= 0x81; }
if ( ( hi & 0x04 ) != 0 ) { hi ^= 0x80; lo ^= 0x40; }
if ( ( hi & 0x02 ) != 0 ) { hi ^= 0x40; lo ^= 0x20; }
if ( ( hi & 0x01 ) != 0 ) { hi ^= 0x20; lo ^= 0x10; }
}
return new [] { ( byte ) lo, ( byte ) hi };
}
static void Main( string[] args )
{
var query = new List<byte> { 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37, 0x38, 0x39 };
query.AddRange( Crc16( query.ToArray() ) );
// Вывод: 31-32-33-34-35-36-37-38-39-29-B1
Console.WriteLine( BitConverter.ToString( query.ToArray() ) );
Console.ReadKey();
}
}Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Простой и эффективный расчёт Modbus CRC16 в ПЛК и МК без побитового сдвига и таблиц