Что такое полином crc32?

Какой полином используется для crc32? ANSI X3.66 CRC-32 - 0x104C11DB7. Страница man для crc32 не указывает используемый полином.

1 ответ

Вопрос в том виде, как он сформулирован, не по теме, однако я постараюсь сделать его по теме, обращаясь к тому, как искать документацию по инструментам, которые в целом полагаются на модули Perl; с целью:

  1. man <tool>;

    От man crc32:

           This utility is supplied with the Archive::Zip module for Perl.
    
  2. perldoc <module>;

    От perldoc Archive::Zip:

        Archive::Zip::computeCRC32( $string [, $crc] )
        Archive::Zip::computeCRC32( { string => $string [, checksum => $crc ] } )
            This is a utility function that uses the Compress::Raw::Zlib CRC
            routine to compute a CRC-32.
    

    Применять рекурсивно, пока что-то не поможет или пока не будет достигнут "корневой" модуль; в этом случае рекурсия заканчивается perldoc Compress::Raw::Zlib, который не помогает;

  3. Копайте исходный код модуля "root":

    Создание таблиц для побайтного 32-разрядного вычисления CRC для полинома: x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+ х ^7+ х ^5+ х ^4+ х ^2+ х +1.

    Полиномы над GF(2) представлены в двоичном формате, один бит на коэффициент, с наименьшими степенями в старшем значащем бите. Тогда добавление полиномов - это просто исключение или, а умножение полинома на x - это сдвиг вправо на единицу. Если мы назовем вышеприведенный полином p и представим байт в качестве полинома q, также с наименьшей степенью в старшем значащем бите (поэтому байт 0xb1 является полиномом x^7+x^3+x+1), то CRC - это (q*x^32) mod p, где mod b означает остаток после деления a на b.

    Это вычисление выполняется с использованием метода сдвигового регистра умножения и взятия остатка. Регистр инициализируется нулем, и для каждого входящего бита x ^ 32 добавляет mod p в регистр, если бит равен единице (где x^32 mod p равно p+x^32 = x^26+...+1), и регистр умножается mod p на x (который сдвигается вправо на единицу и добавляет x^32 mod p, если сдвинутый бит равен единице). Мы начинаем с наивысшей мощности (младший значащий бит) q и повторяем для всех восьми бит q.

    Первая таблица - это просто CRC всех возможных восьмибитных значений. Это вся информация, необходимая для генерации CRC для данных по байту за раз для всех комбинаций значений регистра CRC и входящих байтов. В остальных таблицах учитывается пословное вычисление CRC как для машин с прямым порядком байтов, так и для машин с прямым порядком байтов, где слово составляет четыре байта.

Другие вопросы по тегам