Sum, Revisited

October 21, 2011

Let’s begin by writing the two checksum algorithms; the System V algorithm is copied (with a small modification) from the previous exercise, the BSD algorithm follows the specification given above:

(define (sum-sysv)
  (let loop ((c (read-char)) (b 0) (s 0))
    (if (eof-object? c)
        (values s (ceiling (/ b 512)))
        (loop (read-char) (+ b 1)
              (modulo (+ s (char->integer c)) 65535)))))

(define (sum-bsd)
  (let loop ((c (read-char)) (b 0) (s 0))
    (if (eof-object? c)
        (values s (ceiling (/ b 1024)))
        (loop (read-char) (+ b 1)
              (modulo (+ (quotient s 2)
                         (if (even? s) 0 32768)
                         (char->integer c))
                      65536)))))

It is normal to use bit operations to specify these algorithms, but we used arithmetic operations to illustrate an alternative, for easy portability, and because versions of Scheme prior to R6RS did not provide a standard set of bit operations.

The main program first handles the options, then an if splits the processing depending on whether or not the user specified a list of input files:

(call-with-values
  (lambda () (getopt "rs" "usage: [-r | -s] [file ...]"
                     (cdr (command-line))))
  (lambda (opts files)
    (do ((opts opts (cdr opts))) ((null? opts))
      (case (caar opts)
        ((#\r) (set! sum sum-bsd))
        ((#\s) (set! sum sum-sysv))))
    (if (null? files)
        (call-with-values
          (lambda () (sum))
          (lambda (s b)
            (display s) (display " ")
            (display b) (newline)))
        (do ((files files (cdr files))) ((null? files))
          (with-input-from-file (car files)
            (lambda ()
              (call-with-values
                (lambda () (sum))
                (lambda (s b)
                  (display s) (display " ")
                  (display b) (display " ")
                  (display (car files)) (newline)))))))))

We used getopt from a previous exercise. You can see the program assembled at http://programmingpraxis.codepad.org/KwePb916, but of course you can’t run it there.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “Sum, Revisited”

  1. Jebb said
    November 11, 2011 at 6:03 PM 
    #include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

struct commandArgs {
	void (*sumFn)(FILE *);	/* Checksum function to be called */
	char **inputFiles;
	int numInputFiles;
};
static const char *optString = "rsh?";

void SysVsum(FILE *fp);
void BSDsum(FILE *fp);
void show_usage();

int main(int argc, char *argv[])
{
	int option = 0;
	struct commandArgs myArgs = {SysVsum, NULL, 0};
	FILE *fp;

	option = getopt(argc, argv, optString);
	while (option != -1) {
		switch(option) {
			case 'r':
				myArgs.sumFn = BSDsum;
				break;
			case 's':
				myArgs.sumFn = SysVsum;
				break;
			case 'h':
			case '?':
				show_usage();
				break;
			default:
				break;
		}
		option = getopt(argc, argv, optString);
	}
	myArgs.inputFiles = argv + optind;
	myArgs.numInputFiles = argc - optind;

	if (myArgs.numInputFiles == 0)
		myArgs.sumFn(stdin);
	else 
		while (myArgs.numInputFiles-- > 0) 
			if ((fp = fopen(*(myArgs.inputFiles), "r"))== NULL) {
				fprintf(stderr, 
				        "couldn't open file %s\n",
				        *(myArgs.inputFiles));
				exit(EXIT_FAILURE);
			}
			else {
				myArgs.sumFn(fp);
				fclose(fp);
				myArgs.inputFiles++;
			}
	return 0;
}

void show_usage()
{
	printf("jebb_sum [-r|-s] (<files>)\n");
	exit(EXIT_FAILURE);
}

void SysVsum(FILE *fp)
{
	unsigned int bytes_sum;
	unsigned int bytes_count;
	int next_byte;
	bytes_count = bytes_sum = 0;
	while ((next_byte = getc(fp)) != EOF) {
		bytes_sum = (bytes_sum + next_byte) % 65535;
		bytes_count++;
	}
	printf("%d %d\n", bytes_sum, 1 + bytes_count / 512); 
}

void BSDsum(FILE *fp)
{
	unsigned int bytes_sum;
	unsigned int bytes_count;
	int next_byte;
	bytes_count = bytes_sum = 0;
	while ((next_byte = getc(fp)) != EOF) {
		/* From the man page on Snow Leopard:
		 * 16-bit checksum with right rotation before each addition */
		bytes_sum = ((bytes_sum >> 1) + 0x8000 * (bytes_sum & 1));
		/* overflow is discarded */
		bytes_sum = (bytes_sum + next_byte) & 0xFFFF;
		bytes_count++;
	}
	/* block size is 1024 bits in the BSD sum */
	printf("%d %d\n", bytes_sum, 1 + bytes_count / 1024); 
}

Leave a comment