Понимание значения CRC32 как остатка от деления - PullRequest
Новая
       79

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

0 голосов
/ 05 октября 2018

Я борюсь с пониманием алгоритма 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, верно?Но оказывается, что результат должен выглядеть совершенно иначе.Видимо, я упускаю что-то очевидное.Что это?Как изменение наименее значимого числа в дивиденде может так сильно повлиять на результат?

1 Ответ

0 голосов
/ 06 октября 2018

Это пример 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 - это смещение вправо, обычно используемое для эмуляции аппаратного обеспечения, когда данные отправляются в байтах младшим значащим битом первым.

...