高速CRCアルゴリズム？

Question

ASCII文字列のうち32ビットの数値を作成したいとします。 CRC32アルゴリズムはまさに私が探しているものですが、必要なテーブルが非常に巨大なので（ressourcesが非常にまれな組み込みシステム用です）、使用できません。

So：高速でスリムなCRCアルゴリズムの提案はありますか？コリジョンが元のCRC32よりも多少発生する可能性はありません。

ありがとうございます！

Answer 1

CRC実装では、速度のためにテーブルが使用されます。それらは必須ではありません。

Castagnoli多項式（Intel crc32命令で使用されているものと同じもの）またはイーサネット多項式（zip、gzipなどで使用されるものと同じもの）を使用する短いCRC32があります。

#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を更新するためにデータのチャンクで連続的に呼び出すことができます。あなたのコンパイラはあなたのためにそれを行うかもしれませんが、スピードのために内部ループを展開することができます。

Answer 2

明らかに最大のルックアップテーブルが最高のパフォーマンスを発揮しますが、16,8または4ビットルックアップには任意の（より小さい）テーブルを使用できます。

ので、テーブルのサイズは、CRC32のためのものです：

16bit-lookup: 4*2^16=256k 
8bit-lookup: 4*2^8=1k 
4bit-lookup: 4*2^4=64byte 

4ビットテーブルは、16ビットのテーブルよりも4倍遅いです。
使用する必要があるのは、速度要件によって異なります。

Luka Rahneは、フラッシュメモリにテーブルを置くことをお勧めしますが、多くのプラットフォームではconstキーワードを使用するだけでは十分ではありません。
ほとんどの場合、リンカーコマンドファイルを変更して、フラッシュに配置されたセクションにテーブルを配置する必要があります。