Jump to content

    
Sign in to follow this  
uni

Ещё один метод расчёта CRC16

Recommended Posts

Скажите, а код в пдф-ке выдаёт три одинаковых результата?

Я не умею в уме "переворачивать" полином, но какое-то подозрение, что код-таки разный.

 

Спасибо за идею.

Надо б допилить до макроса автовычисления констант, и можно смело применять там, где цикл по битам делать долго, а места под таблицу - жалко.

Share this post


Link to post
Share on other sites

В первой pdf выдаёт три одинаковых, во второй что-то сам сомневаюсь уже. Пытаюсь немного улучшить результат для последнего.

Share this post


Link to post
Share on other sites
4 часа назад, uni сказал:

Собрал тестовый пример на ATmega16@16МГц. Таблица во флеш, полином 0x1021. Чуда не произошло. Моя реализация для тестовой строки "123456789" дала 24 мкс против 13,9 мкс у табличного метода. В общем, тело цикла с чтением слова из флеш считает быстрее, чем побайтовый xor с условиями.

Я же говорю - ну очень громоздко! :wink:

CRC16 для 0x1021 я считаю так:

//Расчёт CRC16-CCITT полином == 0x1021
u32 CRC16(void const *buf, uint len, u32 crc)
{
  u8 const *p = (u8 const *)buf;
  while ((int)--len >= 0) {
    u32 c = crc << 16 >> 24 ^ *p++;
    c ^= c >> 4;
    crc = crc << 8 ^ c ^ c << 5 ^ c << 12;
  }
  return crc & 65535;
}

IAR для ARM компилит это в:

           B.N      ??CRC16_0
??CRC16_1: LDRB     R12,[R0], #+1
           LSLS     R3,R2,#+16
           EOR      R3,R12,R3, LSR #+24
           EOR      R3,R3,R3, LSR #+4
           EOR      R2,R3,R2, LSL #+8
           EOR      R2,R2,R3, LSL #+5
           EOR      R2,R2,R3, LSL #+12
??CRC16_0: SUBS     R1,R1,#+1
           BPL.N    ??CRC16_1
           UXTH     R0,R2
           BX       LR

Что вполне вменяемо. И ни одного перехода внутри тела цикла!

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

 

1 час назад, uni сказал:

Ассемблерный код функции. Не знаю можно ли тут что-то придумать.

Можно. Забыть уже наконец-то об AVR-ах раз и навсегда!  :yes3:

Share this post


Link to post
Share on other sites

Вот, проверил (ATmega16 @ 16 МГц, полином 0xA001 (modbus)):

 

Данные: "123456789"

Ключ: -O1
GetCrc16Table()  - 13.3 мкс
GetCrc16Simple() - 20.0 мкс
GetCrc16Cycle()  - 57.5 мкс

 

Данные: массив, размером 256 байт
Ключ: -O1
GetCrc16Table()  - 0.35 мсек
GetCrc16Simple() - 0.53 мсек
GetCrc16Cycle()  - 1.6 мсек

 

crc16test.pdf

2020-02-12_22-30-44.png

1 час назад, jcxz сказал:

Можно. Забыть уже наконец-то об AVR-ах раз и навсегда!

Я работаю и с двух-ядерными (ARM+DSP) процами, что не мешает мне баловаться avr.

Edited by uni

Share this post


Link to post
Share on other sites
1 hour ago, uni said:

. . . . Я работаю и с двух-ядерными (ARM+DSP) процами, что не мешает мне баловаться avr.

аааа, это как владелец спорт-кара выкатывает из гаража любимую телегу с дохленькой лошадкой, и начинает 

оптимизировать-улучшать ее скорость. Надо применить прецизионные японские подшипники, это повысит скорость девайса на 5 % !

Я Вас понимаю. Сам иногда прохаживаюсь по таким граблям :russian_ru:

Share this post


Link to post
Share on other sites

Некоторым людям нужно ехать, а не шашечки. Я же приводил пример из темы про DDS. Ну не нУжно ему arm'ов. В столе лежала ATmega8535 и девайс завёлся с полпинка от другой прошивки. Пусть пользуется на здоровье. Чем мог, тем помог. Я бы ещё туда вставил, как говорил, обновление таблицы сигналов через modbus-rtu, тем более, что это, похоже, можно сделать прямо из терминала скриптом. Если бы также arm лежал, то помог бы там другой товарищ.

Share this post


Link to post
Share on other sites

Вы лучше скажите, чего Вы хотите добиться? Скорости?

Кратного увеличения получите табличным методом, расположив таблицу все-таки в ОЗУ.

Все остальное для AVR - пустые надежды.

Share this post


Link to post
Share on other sites

Вы не знакомы с архитектурой avr, как я вижу, иначе не предлагали бы засунуть таблицу в ОЗУ. Это мелкий камень и ОЗУ там на вес золота. Я специально привёл пример для ATmega16, т.к. это "отъест" 50% от общего объёма. Лично я занялся этой темой с avr, т.к. хочу сделать на базе arduino простую плату для демонстрации возможностей среды SimInTech в плане генерации кода. Там есть пример для Миландра, но в здравом уме никто в этом разбираться не будет. Порог вхождения гораздо больше. SimInTech - это что-то вроде нашего Simulink'а.
Если я сделаю то, что хочу, то смогу "рисовать" алгоритмы и загружать их в целевую систему мимо стадии программирования. Это вот то к чему всё идёт. Программист - он для этих целей вообще лишний. Нарисовал схему автоматизации, залил в железку, отлаживаешь на уровне сигналов и понятия не имеешь об архитектуре железа. Проект в этом случае получается портируемым под другую железку без переписывания схемы и документации. Нужно сделать только так называемую "адаптацию", где и нужны программисты.

Arduino для этих целей вообще замечательная простая штука. Я бы хотел только, чтобы не только Mega2560 вариант работал, но и меньшие собратья, а для этого нужно экономно сделать "адаптацию". Там применяется расчёт crc16 табличным способом, а меня это не устроило. Вот и появилась эта тема.

Если хотите предложить arm'ы для этих целей :) - флаг в руки, адаптируйте по аналогии с Миландром. Я не говорю, что они не подойдут, просто этого уже на коленке не сделать, как я балуюсь.

Share this post


Link to post
Share on other sites
38 minutes ago, uni said:

Я специально привёл пример для ATmega16, т.к. это "отъест" 50% от общего объёма.

Можно полубайтами оперировать, тогда общий объем табличных данных составит 64 байта для CRC16.

Share this post


Link to post
Share on other sites
7 часов назад, aaarrr сказал:

Можно полубайтами оперировать, тогда общий объем табличных данных составит 64 байта для CRC16.

Покажите пример псевдокода или кода на каком-нибудь c-подобном языке. Чем больше примеров, тем лучше.

Share this post


Link to post
Share on other sites
8 минут назад, uni сказал:

Покажите пример псевдокода или кода на каком-нибудь c-подобном языке. Чем больше примеров, тем лучше.

Примера для CRC16 с вычислением по тетрадным таблицам под рукой нет, но для CRC32 делаю так:

//Расчёт CRC32 полином == 0xEDB88320L
u32 CRC32(void const *buf, uint len, u32 crc)
{
  static u32 const t[] = {
    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
    0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
    0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
    0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91,
    0x00000000, 0x1DB71064, 0x3B6E20C8, 0x26D930AC,
    0x76DC4190, 0x6B6B51F4, 0x4DB26158, 0x5005713C,
    0xEDB88320, 0xF00F9344, 0xD6D6A3E8, 0xCB61B38C,
    0x9B64C2B0, 0x86D3D2D4, 0xA00AE278, 0xBDBDF21C};
  u8 const *p = (u8 const *)buf;
  while ((int)--len >= 0) {
    u32 c = crc ^ *p++;
    crc = t[c & 15] ^ t[(c >> 4 & 15) + 16] ^ crc >> 8;
  }
  return crc;
}

По аналогии можете сделать для CRC16. Если нужно.

Share this post


Link to post
Share on other sites
15 hours ago, jcxz said:

IAR для ARM

Если бы у рыб была шерсть, то там обязательно были бы блохи.

 

15 hours ago, uni said:

В первой pdf выдаёт три одинаковых, во второй что-то сам сомневаюсь уже.

Не сомневайтесь :-)

код из сообщения "Вот теперь больше на правду похоже. Переписал немного" выдаёт следующее:

GetCrc16Table = D641
GetCrc16Cycle = 4B37
GetCrc16Simple = 4B37

https://godbolt.org/z/urjyup

 

Share this post


Link to post
Share on other sites

В контексте AVR.

Тут на асме есть не табличная реализация.

https://www.nongnu.org/avr-libc/user-manual/group__util__crc.html

https://www.nongnu.org/avr-libc/user-manual/crc16_8h_source.html

Интересно было бы сравнить с Вашим решением по скорости и по объёму кода.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this