[uni 6]

Статья на хабре: Простой и эффективный расчёт Modbus CRC16 в ПЛК и МК без побитового сдвига и таблиц

Я добавил в комментариях к статье реализацию на c# для полинома 0xA001, который используется в Modbus.

Тема на форуме dxdy: Ещё один способ расчёта CRC16

Там я добавил исходник на c# для полинома 0x1021. Для него алгоритм расчёта немного отличается. Есть небольшие комментарии с описанием как это работает.

Думается, что здесь более подходящее место для этой темы.

Без таблицы, без сдвигов (для 0x1021, c#):

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;

        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 };
}

 

Изменено 11 февраля, 2020 пользователем uni
Сделал акценты :)

[Arlleex 131]

А результаты сравнения по скорости на какой-нибудь архитектуре типа Cortex-Mx будут?

На мой взгляд, этот способ не быстрее табличного. И, возможно, даже не быстрее алгоритма на сдвигах.

[k155la3 26]

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

Да и что за фобия по сдвигам, этож не порт (морской) и контейнеры.

  if ( ( hi & 0x80 ) != 0 ) { hi ^= 0x08; lo ^= 0x10; }

если уж работаем с битами, то более оптимальная запись будет

  if ( hi & 0x80 ) { hi ^= 0x08; lo ^= 0x10; }

 

[uni 6]

Это я для c# в таком виде написал. На C там короче можно сделать, думается. Я просто следовал описанию автора в статье на хабре, чтобы код был узнаваем. Сравнить можно, табличные есть в сети. Я себе для avr8 архитектуры хотел. Для неё сделаю сравнение.

[k155la3 26]

1 minute ago, uni said:

Это я для c# в таком виде написал. На C там короче можно сделать, думается. Я просто следовал описанию автора в статье на хабре, чтобы код был узнаваем. Сравнить можно, табличные есть в сети. Я себе для avr8 архитектуры хотел. Для неё сделаю сравнение.

 здесь для узнавамости лучше использовать C(++) & ASM

В большинстве микроконтроллеров присутствует аппаратный узел расчета CRC, в различных вариантах настроек/полиномов.

[uni 6]

Ну, в Arduino я аппаратного crc не нашёл. А так, люблю перфекционизм :) Кому-то может пригодится, пусть не для мк современного.

[k155la3 26]

2 minutes ago, uni said:

Ну, в Arduino я аппаратного crc не нашёл. А так, люблю перфекционизм :) Кому-то может пригодится, пусть не для мк современного.

Ну, да, алгоритм интересный, хотя за многие годы у меня CRC ни разу не оказалась "виновной" в снижении/затыке по быстродействию. Время просчета объема данных всегда жестко определено. С перфекционизмом сложно. Ему надо искать правильное применение. Например если уж надо считать CRC из C# - вызывать готовые системные вызовы API или низкоуровневый оптимизированный код из своего DLL (на C/ASM).

[blackfin 16]

47 minutes ago, uni said:

Статья на хабре

Этот алгоритм приводили здесь на форуме ещё десять лет назад: OutputLogic.

Он описан на Verilog'е, но сути это не меняет..

[uni 6]

Смешно. Не удивительно, что тут этот алгоритм не описан. Там, правда, есть варианты под названием "оптимизированный". А то, что ноги из железа растут, это и так понятно.
Себе для avr такты посчитаю, если таблицу победит, то вырежу её нафик :) глаза мозолит.

[blackfin 16]

15 minutes ago, uni said:

Себе для avr такты посчитаю, если таблицу победит, то вырежу её нафик :) глаза мозолит.

Операция if() крайне затратна для процессоров с длинным конвейером. Но для avr это, конечно, не проблема.. ;)

[Forger 17]

1 hour ago, k155la3 said:

если уж работаем с битами, то более оптимальная запись будет

  if ( hi & 0x80 ) { hi ^= 0x08; lo ^= 0x10; }

 

"более оптимальная"?

Так это кому как удобнее читать свои исходиники, для компилятора без разницы ;)

[uni 6]

Я там c# подчеркнул на всякий случай, т.к. народ начал ошибки выдавать за оптимизацию. В c# такая "оптимизация" не катит, поэтому так и написано. Мне быстрее код на c# проверить, чем под C собирать.

[Arlleex 131]

36 минут назад, blackfin сказал:

Операция if() крайне затратна для процессоров с длинным конвейером. Но для avr это, конечно, не проблема.. ;)

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

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

[Forger 17]

Вот все говорят о некой оптимальности этого архаичного CRC16, однако, никто не уточняет о каком потоке данных идет речь? Сколько кБ в сек?

 

 

[uni 6]

Почему же не уточняет? Нужно лишь пройти по первой ссылке. Там ясно написано: для ПЛК и МК. Если заглянуть в статью, то указывается конкретно 0xA001 полином, который используется в Modbus протоколе. Всё ясно как день :)
Мне лично хочется посмотреть ассемблерный листинг для архитектуры AVR8 в 4-х случаях: для полиномов 0xA001 и 0x1021 в случае нахождения таблицы во флеш или в ОЗУ. Думается разница будет :)
Применение: avr и modbus, avr и simintech (0x1021 используется там в отладочном протоколе).