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.

About these ads

Pages: 1 2

One Response to “Sum, Revisited”

  1. Jebb said
    #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 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 574 other followers

%d bloggers like this: