Быстрый алгоритм CRC?
Я хочу создать 32-битное число из ASCII-строки. Алгоритм CRC32 — это именно то, что я ищу, но я не могу его использовать, потому что таблица, которую он требует, слишком велика (для встроенных систем, где ресурсы ОЧЕНЬ редки).
Итак: какие-либо предложения для быстрого и тонкого алгоритма CRC? Не имеет значения, когда столкновения немного более вероятны, чем с оригинальным CRC32.
Спасибо!
Решение
Реализации CRC используют таблицы для скорости. Они не обязательны.
Вот краткий CRC32, использующий полином Кастаньоли (тот же, который используется в инструкции Intel crc32), или полином Ethernet (тот же, что используется в zip, gzip и т. Д.).
#include <stddef.h>
#include <stdint.h>
/* CRC-32C (iSCSI) polynomial in reversed bit order. */
#define POLY 0x82f63b78
/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */
/* #define POLY 0xedb88320 */
uint32_t crc32c(uint32_t crc, const unsigned char *buf, size_t len)
{
int k;
crc = ~crc;
while (len--) {
crc ^= *buf++;
for (k = 0; k < 8; k++)
crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
}
return ~crc;
}
Начальный crc значение должно быть ноль. Процедура может быть вызвана последовательно с порциями данных для обновления CRC. Вы можете развернуть внутренний цикл для скорости, хотя ваш компилятор может сделать это для вас в любом случае.
Другие решения
Очевидно, что самая большая таблица поиска принесет наилучшую производительность, но вы можете использовать любую (меньшую) таблицу для поиска в 16,8 или 4 бита.
Итак, размеры таблицы для crc32:
16bit-lookup: 4*2^16=256k
8bit-lookup: 4*2^8=1k
4bit-lookup: 4*2^4=64byte
4-битная таблица в четыре раза медленнее 16-битной.
Что вы должны использовать, зависит от ваших требований к скорости.
Как упоминает Лука Ране, неплохо было бы поместить таблицу во флэш-память, но на многих платформах недостаточно использовать const ключевое слово.
Чаще всего вам нужно поместить таблицу в раздел, помещенный во flash, изменив командный файл компоновщика.
detector