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

Ответ 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

Ответ 2

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

Ответ 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;
        }
    }
}