Cksum

October 25, 2011

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)=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+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 x32 (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.

About these ads

Pages: 1 2 3

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 600 other followers

%d bloggers like this: