17

我使用这个简单的函数来计算给定文件的 CRC 校验和:

long i, j = 0;
int k = 0;
uint crc = 0xFFFFFFFF;
FileInfo file_info = new FileInfo(file);
byte[] file_buffer = new byte[32768];

FileStream file_stream = new FileStream(@file, FileMode.Open);
while ((i = file_stream.Read(file_buffer, 0, file_buffer.Count())) > 0)
{
    for (j = 0; j < i; j++)
    {
        uint before = crc;
        k = (int)((crc ^ file_buffer[j]) & 0x000000FFL);
        uint after = (uint)((crc >> 8) & 0x00FFFFFFL) ^ crc32_table[k];
        crc = after;
        uint test = (uint)((crc << 8) & 0x00FFFFFFL) ^ crc32_table[k];
        MessageBox.Show((~crc).ToString("X"));
    }
}
file_stream.Close();
return ~crc;

我的问题是:假设我有一个大文件,比如说 100MB。前 50MB 和后 50MB 的 CRC-32 计算与 100MB 文件的 CRC-32 计算之间是否有任何联系?

我要问的原因是我有一些非常大的文件(约 10GB 给予或接受)需要一些时间来生成,但是在生成它们时,大多数部分保持静态,但是,中间部分(已知点) 并在开头(标题,也称为部分/长度)。计算 10GB 文件的 CRC-32 校验和需要相当长的时间,所以我想知道是否有任何方法可以分块进行?

4

4 回答 4

6

是的。请参阅zlibcrc32_combine_()中的示例。

于 2014-01-19T02:08:34.327 回答
5

这个等式是关键:

CRC(a XOR b) == CRC(a) XOR CRC(b)

假设您要计算以下消息的 CRC:

"Always desire to learn something useful."

存在计算 CRC 的函数:

crc_join(crc_part1("Always desire to lea"),
         crc_part2("rn something useful."))

如果crc_part1crc_part2零填充(\0)它们的参数如图所示,crc_join只是异或。

crc_part1 = crc("Always desire to lea\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0")
crc_part2 = crc("\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0rn something useful.")

crc_part1可以使用查找表来解释尾随零。中的前导零可以忽略crc_part2

参考:


  1. 基于软件的 CRC Youngju的高速并行架构。做,成禄。尹,太急。金,光义。Pyun和Sin-Chong。公园
  2. https://en.wikipedia.org/wiki/Cyclic_redundancy_check
于 2013-03-01T07:52:11.960 回答
4

确实可以并行化 CRC-32 计算,但是细节很混乱,我需要花大约一天的时间来编写代码。

让我们看一下基本的 CRC 算法,其中没有取反,也没有位反转。

对于要计算其 CRC 的字节串,我们将其称为消息。基本思想是将消息视为GF(2)中的多项式,并以 CRC 多项式为模计算其余数。

基本的 CRC 算法是加法/线性的。如果您有两条长度相同的消息 a 和 b,则 CRC(a XOR b) = CRC(a) XOR CRC(b)。

此外,如果您在右侧用 n 个零填充消息,则新的 CRC 将是旧的 CRC 乘以 x^n mod CRC 多项式。

 

尽管如此,解决问题的唯一方法是真正理解 CRC 算法背后的数学原理并编写自己的自定义代码。这是对 CRC 的一个很长但非常完整的解释:http ://www.ross.net/crc/download/crc_v3.txt

于 2011-07-11T21:57:41.477 回答
2

我知道这是一个老问题,但这是我用来“分块”CRC计算的,以防这对任何人都有帮助:

public static class Crc32Checksum
{
    private static readonly uint[] Table = GenerateTable();

    /// <summary>
    /// Calculates a CRC32 value for the data given.
    /// </summary>
    /// <param name="data">Data contents</param>
    /// <param name="offset">Byte offset to start reading</param>
    /// <param name="count">Number of bytes to read</param>
    /// <returns>The computed CRC32 value.</returns>
    public static int Calculate(byte[] data, int offset, int count) 
        => Calculate(0, data, offset, count);

    /// <summary>
    /// Calculates a new CRC32 value given additional data for the current CRC value.
    /// </summary>
    /// <param name="currentCrc">The current CRC value to start with</param>
    /// <param name="data">Additional data contents</param>
    /// <param name="offset">Byte offset to start reading</param>
    /// <param name="count">Number of bytes to read</param>
    /// <returns>The computed CRC32 value.</returns>
    public static int Calculate(int currentCrc, byte[] data, int offset, int count)
    {
        unchecked
        {
            uint crc = ~(uint)currentCrc;

            for (int i = offset, end = offset + count; i < end; i++)
                crc = (crc >> 8) ^ Table[(crc ^ data[i]) & 0xFF];

            return (int)~crc;
        }
    }

    private static uint[] GenerateTable()
    {
        unchecked
        {
            var table = new uint[256];

            const uint poly = 0xEDB88320;

            for (uint i = 0; i < table.Length; i++)
            {
                uint crc = i;

                for (int j = 8; j > 0; j--)
                {
                    if ((crc & 1) == 1)
                        crc = (crc >> 1) ^ poly;
                    else
                        crc >>= 1;
                }

                table[i] = crc;
            }

            return table;
        }
    }
}
于 2018-10-27T02:33:03.563 回答