[esaulenka 5]

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

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

 

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

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

[uni 6]

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

[jcxz 181]

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

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

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

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-ах раз и навсегда!  

[uni 6]

Вот, проверил (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

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

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

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

Изменено 12 февраля, 2020 пользователем uni

[k155la3 26]

1 hour ago, uni said:

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

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

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

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

[uni 6]

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

[Arlleex 130]

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

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

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

[uni 6]

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

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

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

[aaarrr 61]

38 minutes ago, uni said:

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

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

[uni 6]

7 часов назад, aaarrr сказал:

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

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

[jcxz 181]

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. Если нужно.

[uni 6]

Интересная сопутствующая тема: ARM, 32bit - CRC32

[esaulenka 5]

15 hours ago, jcxz said:

IAR для ARM

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

 

15 hours ago, uni said:

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

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

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

GetCrc16Table = D641
GetCrc16Cycle = 4B37
GetCrc16Simple = 4B37

https://godbolt.org/z/urjyup

 

[uni 6]

Вот последний вариант: https://godbolt.org/z/9txEB2

[demiurg_spb 0]

В контексте 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

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