Возможно ли вычисление CRC-32 в расколах?

Я использую эту тривиальную функцию для вычисления контрольной суммы 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;

Мой вопрос: Скажем, у меня большой файл, скажем, 100 МБ. Существует ли связь между вычислением CRC-32 первых 50 МБ и последними 50 МБ и вычислением CRC-32 файла в 100 МБ?

Причина, по которой я спрашиваю, есть у меня очень большие файлы (~ 10 ГБ дают или берут), которые занимают некоторое время, чтобы сгенерировать, но пока они генерируются, большинство частей остаются статичными, однако части в середине (известная точка) и справа в начале (заголовок, также известная часть/длина). Вычисление контрольной суммы CRC-32 файла 10 ГБ занимает довольно много времени, поэтому мне было интересно, есть ли способ сделать это в кусках?

Ответы

Ответ 1

Действительно, можно распараллелить вычисления CRC-32, но детали беспорядочны, и мне нужно потратить около дня, чтобы придумать код.

Посмотрим на базовый алгоритм CRC, где нет никакого отрицания и нет разворота бит.

Для строки байтов, которую вы хотите вычислить CRC, позвоните на это сообщение. Основная идея заключается в том, что вы обрабатываете сообщение как многочлен в GF (2), и вы вычисляете его остаток по модулю CRC-полинома.

Основной алгоритм CRC является аддитивным/линейным. Если у вас есть два сообщения a и b одной длины, то CRC (XOR b) = CRC (a) XOR CRC (b).

Кроме того, если вы поместите сообщение с правой стороны с n нулями, новый CRC будет старым CRC-временем x ^ n mod polyomial CRC.

 

При всем том, что единственный способ решить вашу проблему - это понять математику алгоритма CRC и написать собственный код. Здесь длинное, но очень полное объяснение CRC: http://www.ross.net/crc/download/crc_v3.txt

Ответ 3

Это уравнение является ключевым:

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_part1 и crc_part2 zeros pad (\0) их аргументы, как показано, crc_join - это просто XOR.

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.

Литература:

  • Высокоскоростная параллельная архитектура для программного обеспечения CRC
    Youngju. Сделай, Сун-Рок. Yoon, Taekyu. Ким, Кван Юй. Пюн и Син-Чонг. Парк
  • https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Ответ 4

Я знаю, что это старый вопрос, но это то, что я использую для "чанкования" вычислений 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;
        }
    }
}