CPS 214 Computer Networks & Distributed SystemsFall 1996Prof. Thomas NartenProgram 0 (10 pts)Assigned: Wednesday, September 4Due: Thursday, Sept 12

Introduction

This assignment is intended as 1) an introduction to using the C programming language within the Unix operating system; and 2) to help you learn about the use of checksums in data transmission. You will write a routine that computes the checksum of a buffer of bytes. The checksum routine you create will be used in subsequent assignments.

How to Start

You should first read Section 3.2 on ``Error Detection and Correction'' in Tanenbaum's book (Subsection 3.2.2 in particular) before starting this project. You will be implementing the CRC-CCITT checksum algorithm, which uses the generator polynomial:

Problem

You are to write a routine int Checksum(char *buf, int len) that takes a pointer to a buffer and its length as arguments. The Checksum function returns the calculated checksum value.

To test your routine, write a program that reads (and echoes) lines from standard input, computes their checksums, and prints out the checksum value in hexadecimal (use printf's ``%x'' conversion). Your program should ignore the newline character (i.e., not include it in the checksum calculation), blank lines, and lines that start with a ``#'' character. Your program should work for input lines up to 128 characters.

One problem with the above approach is that the ascii strings you enter at the keyboard will not generate all the possible test cases your checksum program needs to exercise (i.e., 7-bit ascii characters never have the high order bit set). To better test your routine, have your program create a buffer containing random data. Fill your buffer with the 16-bit words returned by random to generate better testing data. The library routine random(3) returns random 16-bit integer values.

Important! When turning in your program, place the Checksum routine in a file by itself. Your main program that calls Checksum should reside in a different file. When we grade your program, we will compile and link your Checksum routine directly with our grading program.

Helpful Hints

The following hints might be useful in constructing your program.

1. Be sure and use unsigned variables when working with checksums. Why?

2. Use the Unix library routine fgets(3) to obtain the contents of an input line. (Be sure to check that the input data doesn't overflow the buffer!)

3. To test that your computed checksum is correct:
   1. Calculate the checksum as normal and store its value in the two bytes just after the end of the message being checksummed. (Note that you may have to pad the end of the message with a NULL byte to make the original message an even number of bytes.)
   2. Call Checksum again, this time computing the checksum over the entire buffer, including the extra two bytes. If the recalculated checksum is non-zero, there is a bug in your algorithm. Note, however, that if your checksum does come back as zero, that is no guarantee that your checksum is being computed correctly.
4. Review C's bit manipulation facilities, including the shift operators ``<<'' and ``>>'', the ``''exclusive operator and the bit negation operator ``''.
5. Warning: modern RISC machines (including the sun4) have the feature that fetches and stores of word quantities can only be made to addresses that are aligned properly. For example, fetches and stores of 2-byte word quantities (i.e., shorts) can only be made to addresses that are multiples of two. Attempts to access short words at an odd address produce a segmentation fault. One way of avoiding the problem is to access quantities one byte at a time using something like the following: #define STOREWORD(pch,w) (*pch=(w>>8); *(pch+1) = (w&))

   Note that this is not a very efficient solution and should only be used when there is no alternative.

Unix Help

To get help information about library routines, use the Unix command man. For instance, entering ``man fgets'' will display the manual page entry for fgets on the terminal. Note also the number given in parenthesis (e.g., ``3'' in fgets(3)). Unix organizes manual pages into sections, and the number given in parenthesis refers to the section in which the man page can be found. Section 1 contains commands users invoke from the shell. Section 2 documents all system calls, while section 3 documents routines in the standard C library, etc. Usually, man automatically finds which section a command or routine resides in. In cases where a program and procedure happen to have the same name, however, man may find the ``wrong'' entry. In such cases, specify the particular section as an option to man (e.g., ``man 3 sort''). Hint: Your first use of the man command should be to find out about what man does, and what options it supports!

Individual manual pages are also divided into sections that describe the particular command. The NAME section gives the precise name of the program(s), system call(s), or library function(s) the man page documents. Sometimes, a set of related routines or programs are documented in a single man page. For example, the string comparison routine strcmp(3) is documented under the manual entry string(3), which describes a set of string manipulation routines.

The SYNOPSIS section describes how one invokes the routine. For programs (Section 1), the SYNOPSIS gives a concise listing of the command's options. For system calls and other procedures invoked directly from C programs, the SYNOPSIS section describes any arguments (parameters), return values, their types, etc. The SYNOPSIS section may also indicate that certain header files (those having a .h extension) must be included if one intends to call a particular routine. These header files usually declare the types of the arguments used by the command. There is nothing special about header files. They reside in the directory /usr/include, and can be inspected using standard Unix utilities such as more(1). For instance, the SYNOPSIS section of the man page for printf(3) states that the file stdio.h should be included. The file itself resides in /usr/include/stdio.h.

The DESCRIPTION section articulates what the command or routine does. The RETURN VALUES section discusses possible return values, and the EXAMPLES section often provides examples on how to use a command or routine. Finally, the SEE ALSO section contains pointers to other man pages that may contain helpful information related to the current man page. Note also the BUGS section. It frequently points out the limitations of a command or routine.

About this document ...

This document was generated using the LaTeX2HTML translator Version 0.6.4 (Tues Aug 30 1994) Copyright © 1993, 1994, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 p0.tex.

The translation was initiated by Thomas Narten on Sun Sep 15 17:22:16 EDT 1996