CRC32, uint32_t Опции

[toweroff]

Добрый день!

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

Но из того, что я находил, даже табличная реализация считает по 1 байту

А хотелось бы найти подсчет сразу по 32 бита, не по 8. Благо мой массив данных всегда кратен 4 байтам, а аппаратного CRC на борту контроллера нет
По идее, это же должно увеличить производительность?

UPD
что-то нашел от Интела

черт... там используются 4 таблицы из uint32_t[256]
места в оперативке нет, во флеше тоже... придется побайтно считать

[adnega]

Типичный кусок кода для бестабличного вычисления:

Код

for (j = 0; j < 8; j++) ...;

Не вижу причин для ускорения даже если заменить 8 на 32. Расчет-то все равно побитный.
Считайте в лоб, без таблиц - минимум по расходу памяти.
Подсчет можно вести во время получения порции данных, а не когда весь образ будет готов - вряд ли канал обновления сравниться со скоростью вычисления CRC и записи во flash. Лучше вообще считать во время записи во flash. Финальная задержка порядка времени обработки одного блока.

[jcxz]

Типичный кусок кода для бестабличного вычисления:

Код

for (j = 0; j < 8; j++) ...;

Не вижу причин для ускорения даже если заменить 8 на 32. Расчет-то все равно побитный.

Кроме побитного и табличного есть и другие способы.
Например - табличный не по-байтный, а по-тетрадный: размер таблицы в 8 раз меньше, действий только чуть больше.
Также можно считать CRC за один проход для целого байта (без таблиц) по формуле. Но этот способ знаю только для CRC16.

кстати, может я сам себе придумал геморрой проблему?
размер блока 32К, сколько там достаточно бит в CRC? может и в 16 уложусь, тогда все вопросы сами собой пропадут

Неужто Ваш МК не может справиться с таким небольшим объёмом??
Я думал - Вы мегабайты считаете....
У нас бутлоадер тоже считает CRC32 (Cortex-M на 12МГц без PLL).
Таблично. CRC32. При каждом старте ПО. На глаз задержки старта не заметно. Даже PLL не стали включать.
Размер прошивки == почти 200кБ.

[Сергей Борщ]

Также можно считать CRC за один проход для целого байта (без таблиц) по формуле. Но этот способ знаю только для CRC16.

Я знаю для CCITT (полином 0x8408), XMODEM (полином 0x1021). Давайте меняться? В примере применения от первых scenix (виртуальная периферия IrDA) было вскользь упомянуто как они получили такую формулу для 0x8408, но тогда я эту методику не осилил, а сейчас то описание потерялось и не гуглится

Добавлено: нагуглил. Да, и тогда не понял, и сейчас не осиливаю.

[jcxz]

Я знаю для CCITT (полином 0x8408), XMODEM (полином 0x1021). Давайте меняться? В примере применения от первых scenix (виртуальная периферия IrDA) было вскользь упомянуто как они получили такую формулу для 0x8408, но тогда я эту методику не осилил, а сейчас то описание потерялось

Я как раз для 0x1021 и знаю только

Код

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

на вход crc - начальное значение (0 или ~0) или результат от CRC16() предыдущего региона в цепочке регионов

Вот-бы для CRC32 найти!

PS: Хотя нет - знаю ещё одну формулу для другого CRC16, но не знаю какой полином (данная CRC используется в наших устройствах работающих по нашему собственному протоколу).

[Сергей Борщ]

Я как раз для 0x1021 и знаю только

Ну да, у меня такая же:

Код

void crc::ccitt::calculate(uint8_t byte)
{
    base Current_tmp = Current ^ byte;

    uint_fast8_t Tmp= (Current_tmp ^ (Current_tmp << 4)) & 0xff;
    Current = (Current_tmp >> 8) ^ (Tmp << 8) ^ ( Tmp << 3) ^ ( Tmp >> 4);
}

void crc::xmodem::calculate(uint8_t byte)
{
    base Current_tmp = Current;
    uint_fast8_t Tmp = ((Current_tmp >> 8) ^ byte) & 0xFF;
    Tmp ^= Tmp >> 4;
    Current = (Current_tmp << 8) ^ (Tmp << 12) ^ (Tmp << 5) ^ Tmp;
}