1

What is the polynomial used for crc32? The ANSI X3.66 CRC-32 is 0x104C11DB7. The man page for crc32 does not indicate the polynomial it uses.

muru
  • 197,895
  • 55
  • 485
  • 740
Luke Perkins
  • 81
  • Can you clarify how this is about Ubuntu? What are you trying to do? – kos Nov 23 '15 at 19:47
  • Yes, this is an application included in the libarchive-zip-perl package. There is a man page on "crc32". The man page does not indicate the polynomial that it uses to calculate the CRC-32. It also does not indicate the Endean-ness of the bytes as they are read from a file. – Luke Perkins Nov 23 '15 at 20:42
  • Sorry, but even though the crc32 program is included in Ubuntu, I don't believe that the mathematical background of the standardized CRC32 algorithm is on topic on AskUbuntu. – David Foerster Nov 26 '15 at 12:24
  • The math, no, this is well documented in numerous college text books. The polynomial, yes. There are multiple polynomials that are associated with a 32-bit CRC calculation. The polynomial identifies the specific polynomial used in the calculation which is essential to verify the utilities results. – Luke Perkins Nov 28 '15 at 16:39

1 Answers1

6

The question as is phrased is off-topic, however I'll try to make it on-topic by addressing how to search for documentation on tools that rely on Perl modules in a general way; in order:

  1. man <tool>;

    From man crc32:

           This utility is supplied with the Archive::Zip module for Perl.

  2. perldoc <module>;

    From 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.

    Apply recursively until something avails or the "root" module is reached; in this case the recursion ends with perldoc Compress::Raw::Zlib, which doesn't avail;

  3. Dig the source code of the "root" module:

    Generate tables for a byte-wise 32-bit CRC calculation on the polynomial: x^32+x^26+x^23+x^22+x^16+x^12+x^11+x^10+x^8+x^7+x^5+x^4+x^2+x+1.

    Polynomials over GF(2) are represented in binary, one bit per coefficient, with the lowest powers in the most significant bit. Then adding polynomials is just exclusive-or, and multiplying a polynomial by x is a right shift by one. If we call the above polynomial p, and represent a byte as the polynomial q, also with the lowest power in the most significant bit (so the byte 0xb1 is the polynomial x^7+x^3+x+1), then the CRC is (q*x^32) mod p, where a mod b means the remainder after dividing a by b.

    This calculation is done using the shift-register method of multiplying and taking the remainder. The register is initialized to zero, and for each incoming bit, x^32 is added mod p to the register if the bit is a one (where x^32 mod p is p+x^32 = x^26+...+1), and the register is multiplied mod p by x (which is shifting right by one and adding x^32 mod p if the bit shifted out is a one). We start with the highest power (least significant bit) of q and repeat for all eight bits of q.

    The first table is simply the CRC of all possible eight bit values. This is all the information needed to generate CRCs on data a byte at a time for all combinations of CRC register values and incoming bytes. The remaining tables allow for word-at-a-time CRC calculation for both big-endian and little- endian machines, where a word is four bytes.

kos
  • 35,891