Programming Praxis

We did versions of the sum command for computing file checksums in two previous exercises, one for System V and one for Berkeley systems. Although the BSD version of the command fixes many of the problems of the SysV version, having two different versions of the sum command is inconvenient, and the solution has been to create a third (incompatible) checksum program with a new name: cksum. The algorithm used in cksum is given by the Open Group:

The cksum utility shall calculate and write to standard output a cyclic redundancy check (CRC) for each input file, and also write to standard output the number of octets in each file. The CRC used is based on the polynomial used for CRC error checking in the ISO/IEC 8802-3:1996 standard (Ethernet).

The encoding for the CRC checksum is defined by the generating polynomial:

G(x)=x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1

Mathematically, the CRC value corresponding to a given file shall be defined by the following procedure:

1. The n bits to be evaluated are considered to be the coefficients of a mod 2 polynomial M(x) of degree n−1. These n bits are the bits from the file, with the most significant bit being the most significant bit of the first octet of the file and the last bit being the least significant bit of the last octet, padded with zero bits (if necessary) to achieve an integral number of octets, followed by one or more octets representing the length of the file as a binary value, least significant octet first. The smallest number of octets capable of representing this integer shall be used.
2. M(x) is multiplied by x³² (that is, shifted left 32 bits) and divided by G(x) using mod 2 division, producing a remainder R(x) of degree ≤ 31.
3. The coefficients of R(x) are considered to be a 32-bit sequence.
4. The bit sequence is complemented and the result is the CRC.

The reference implementation from the Open Group is shown on the next page.

Your task is to implement the cksum algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2 3