注意:我不想使用SuperFastHash,也不希望它给出与CRC32相同的输出值。
我正在编写一个简单的LZSS压缩/解压例程,以提供非常快速的解压和在解压时没有内存开销。输入数据被分成4096字节长度的块,并按顺序压缩。
我的问题是:我想为每个压缩块(块大小<= 4096字节)添加一些错误检测。时间限制很严格,因此校验和例程必须非常快。我避免了加密算法(MD5、SHA1),因为它们涉及大量计算,而选择了CRC32(一个更简单和明显的算法)。
经过一些测试,我发现在我的项目约束下CRC32太慢了。我使用了来自这里的enwik9(维基百科的10^9字节文本转储)。我使用我的LZSS例程对其进行了压缩,并获得了一个570Mb的文件。 我测量了以下持续时间(单线程,磁盘IO排除在外,在处理之前将所有数据加载到内存中,平均进行10次试验):
我的问题是:
在压缩数据块中,我能否使用哈希替代循环冗余校验值以执行错误检测?据我所知(并记得从我的电子课程中学到的),CRC算法设计用于在数据通过嘈杂的信道传输时出现突发错误的情况下非常高效,而这并不适用于从硬盘读取的数据。如果我理解有误,请纠正我。
谢谢任何建议!
我正在编写一个简单的LZSS压缩/解压例程,以提供非常快速的解压和在解压时没有内存开销。输入数据被分成4096字节长度的块,并按顺序压缩。
我的问题是:我想为每个压缩块(块大小<= 4096字节)添加一些错误检测。时间限制很严格,因此校验和例程必须非常快。我避免了加密算法(MD5、SHA1),因为它们涉及大量计算,而选择了CRC32(一个更简单和明显的算法)。
经过一些测试,我发现在我的项目约束下CRC32太慢了。我使用了来自这里的enwik9(维基百科的10^9字节文本转储)。我使用我的LZSS例程对其进行了压缩,并获得了一个570Mb的文件。 我测量了以下持续时间(单线程,磁盘IO排除在外,在处理之前将所有数据加载到内存中,平均进行10次试验):
| 操作 | 时间 (GCC4.4.5/Linux) | 时间 (MSVC2010/Win7) | |-------------------------------+--------------------------+------------------------| | 解压 | 6.8 秒 | 6.95 秒 | | 在解压后的结果上执行CRC32 | 4.9 秒 | 4.62 秒 | | 在压缩后的结果上执行CRC32 | 2.8 秒 | 2.69 秒 |
然后我只是出于好奇测试了SuperFastHash:
| 操作 | 时间 (GCC4.4.5/Linux) | 时间 (MSVC2010/Win7) | |-------------------------------+--------------------------+------------------------| | 对解压缩结果进行SFH计算 | 1.1秒 | 1.33秒 | | 对压缩结果进行SFH计算 | 0.7秒 | 0.75秒 |
这是我的CRC32实现(我遵循了以下文档的描述: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 ;
}
我的问题是:
在压缩数据块中,我能否使用哈希替代循环冗余校验值以执行错误检测?据我所知(并记得从我的电子课程中学到的),CRC算法设计用于在数据通过嘈杂的信道传输时出现突发错误的情况下非常高效,而这并不适用于从硬盘读取的数据。如果我理解有误,请纠正我。
谢谢任何建议!