c - 使用 SuperFastHash 而不是 CRC32？

Question

注意:我没有尝试使用 SuperFastHash并期望它给出与 CRC32 相同的输出值。

我正在写一个简单的 LZSS压缩/解压缩例程以提供非常快速的解压缩并且在解压缩时没有内存开销。输入数据被分成 4096 字节长的 block ，并按顺序压缩。

我的问题:我想为每个压缩 block ( block 大小 <= 4096 字节)添加一些错误检测。时间限制非常严格，因此校验和例程必须非常快。我避免使用密码算法(MD5、SHA1)，因为它们涉及大量计算，我选择了 CRC32(一种更简单、明显的算法)。

经过一些测试后，我发现 CRC32 对于我的项目限制来说太慢了。我使用了来自 here 的 enwik9(维基百科的 10^9 字节文本转储) .我使用我的 LZSS 例程压缩它并获得了一个 570Mb 的文件。我测量了以下持续时间(单线程、磁盘 IO 除外、所有数据在处理前加载到内存中、10 次试验的平均值):

|          Operation            |  Time (GCC4.4.5/Linux)   |  Time (MSVC2010/Win7)  ||-------------------------------+--------------------------+------------------------||        Decompression          |        6.8 seconds       |      6.95 seconds      ||  CRC32 on decompressed result |        4.9 seconds       |      4.62 seconds      ||   CRC32 on compressed result  |        2.8 seconds       |      2.69 seconds      |

Then I tested SuperFastHash, just by curiosity :

|          Operation            |  Time (GCC4.4.5/Linux)   |  Time (MSVC2010/Win7)  ||-------------------------------+--------------------------+------------------------||  SFH on decompressed result   |        1.1 seconds       |      1.33 seconds      ||   SFH on compressed result    |        0.7 seconds       |      0.75 seconds      |

And here is my CRC32 implementation (I followed the descriptions from the following document : http://www.ross.net/crc/download/crc_v3.txt) :

# include <stdint.h>

// CRC32 lookup table (corresponding to the polynom 0x04C11DB7)
static const uint32_t  crc32_lookup_table[256] =
{
    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
    0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
    0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
    // many lines skipped
    // ...
    0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
} ;

uint32_t crc32_hash(const uint8_t * data, size_t len)
{
    uint32_t crc32_register = 0xFFFFFFFF ;
    while( len-- )
    {
        crc32_register = (crc32_register >> 8)
                       ^ crc32_lookup_table[(crc32_register & 0x000000FF) ^ *data++] ;
    }
    return crc32_register ^ 0xFFFFFFFF ;
}

我的问题是:

我可以使用散列而不是循环冗余校验值来对压缩数据 block 进行错误检测吗？据我所知(我从我的电子类(class)中记得)，CRC 算法被设计为当数据通过嘈杂的 channel 传输时突发错误时非常有效，这不是从硬盘读取数据的情况。如果我错了，请纠正我。

谢谢你的建议!

Answer 1

已发现 SuperFastHash 以及其他快速散列函数 murmur2 存在一些问题。如果您正在寻找适合更大数据 block 且冲突更少的东西，您可以尝试使用 128 位的 google 城市哈希 (http://code.google.com/p/cityhash/) 变体或 murmur3。还有一些更离谱的函数，如 crap8 和 crapwow，它们声称提供几乎完美的位雪崩和漏斗，因此碰撞几乎为零，您可以在此处阅读它和其他非加密哈希函数:http://www.team5150.com/~andrew/noncryptohashzoo/