Понимание значения CRC32 как остатка от деления

Question

Я борюсь с пониманием алгоритма CRC. Я читал этот учебник, и если я понял его правильно, значение CRC является просто остатком от деления, где сообщение служит делителем, а делитель является предопределенным значением - выполняется в особом виде полиномиальной арифметики. Это выглядело просто, поэтому я попытался реализовать CRC-32:

public static uint Crc32Naive(byte[] bytes)
{
    uint poly = 0x04c11db7; // (Poly)
    uint crc = 0xffffffff; // (Init)

    foreach (var it in bytes)
    {
        var b = (uint)it;
        for (var i = 0; i < 8; ++i)
        {
            var prevcrc = crc;

            // load LSB from current byte into LSB of crc (RefIn)
            crc = (crc << 1) | (b & 1); 
            b >>= 1;

            // subtract polynomial if we've just popped out 1 
            if ((prevcrc & 0x80000000) != 0) 
                crc ^= poly;
        }
    }

    return Reverse(crc ^ 0xffffffff); // (XorOut) (RefOut)
}

(где Reverese функция меняет порядок бит)

Предполагается, что он аналогичен следующему методу деления (с некоторыми дополнительными корректировками):

            1100001010
       _______________
10011 ) 11010110110000
        10011,,.,,....
        -----,,.,,....
         10011,.,,....
         10011,.,,....
         -----,.,,....
          00001.,,....
          00000.,,....
          -----.,,....
           00010,,....
           00000,,....
           -----,,....
            00101,....
            00000,....
            -----,....
             01011....
             00000....
             -----....
              10110...
              10011...
              -----...
               01010..
               00000..
               -----..
                10100.
                10011.
                -----.
                 01110
                 00000
                 -----
                  1110 = Remainder

За: 0x00 функция возвращает 0xd202ef8d что правильно, но для 0x01 - 0xd302ef8d вместо 0xa505df1b (Я использовал эту страницу, чтобы проверить свои результаты).

Решение от моей реализации имеет больше смысла для меня: увеличение дивиденда на 1 должно только изменить напоминание на 1, верно? Но оказывается, что результат должен выглядеть совершенно иначе. Видимо, я упускаю что-то очевидное. Что это? Как изменение наименее значимого числа в дивиденде может так сильно повлиять на результат?

Answer 1

Это пример CRC со сдвигом влево, который эмулирует деление, с инициализированным CRC = 0 и без дополнения или изменения CRC. Пример кода эмулирует деление, где к байту добавляется 4 байта с нулями [] ({bytes[],0,0,0,0} - дивиденд, делитель 0x104c11db7, частное не используется, а остаток это CRC).

public static uint Crc32Naive(byte[] bytes)
{
    uint poly = 0x04c11db7; // (Poly is actually 0x104c11db7)
    uint crc = 0;           // (Init)

    foreach (var it in bytes)
    {
        crc ^= (((int)it)<<24);     // xor next byte to upper 8 bits of crc
        for (var i = 0; i < 8; ++i) // cycle the crc 8 times
        {
            var prevcrc = crc;
            crc = (crc << 1); 
            // subtract polynomial if we've just popped out 1 
            if ((prevcrc & 0x80000000) != 0) 
                crc ^= poly;
        }
    }
    return crc;
}

Обычно инициализируют CRC чем-то отличным от нуля, но это не так часто после посткомплементации CRC, и я не знаю ни одного CRC, который делает пост-битное обращение CRC.

Другой вариант CRC - это тот, который сдвигается вправо, обычно используемый для эмуляции аппаратного обеспечения, когда данные отправляются в младшем значащем байте в первую очередь.