Можно ли сделать расчет CRC-32 в сплитах? - PullRequest
Новая
       14

Можно ли сделать расчет CRC-32 в сплитах?

15 голосов
/ 27 июня 2011

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

Ответы [ 4 ]

5 голосов
/ 19 января 2014

Да. См. crc32_combine_() в zlib для примера.

2 голосов
/ 01 марта 2013

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

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 заполнены нулями (\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.

Ссылки:

  1. Высокоскоростная параллельная архитектура для программной CRC
    Youngju.До, Сунг-Рок.Юн, Таэкю.Ким, Кванг Юи.Пюн и Син-Чонг.Парк
  2. https://en.wikipedia.org/wiki/Cyclic_redundancy_check
2 голосов
/ 12 июля 2011

Это - действительно действительно возможно распараллелить вычисления 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

1 голос
/ 27 октября 2018

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