Princeton University
COS 217: Introduction to Programming Systems

Purpose

Background

File compression is a common computer application. Often it is necessary to compress files for convenient distribution to users, for fast communication across a network, or to save disk space. So computer scientists have developed many file compression algorithms.

Run-length compression is a simple, but often effective, compression algorithm for text files. The run-length compression algorithm designates some special character, typically the character with all bits on (that is, 255₁₀, alias FF₁₆, alias 377₈, alias 11111111₂) as the "escape" character. If a non-escape character occurs consecutively more than twice in the input steam, the algorithm compresses the occurrences of the character into a three-character "escape sequence" escapechar char count, where escapechar is the escape character, char is the character in the input, and count is the number of consecutive occurrences of the character. Thus the algorithm is effective at compressing files that contain many or long sequences of identical characters.

Your First Task

Your first task is to write a file compression program named squash. Your squash program should use the run-length compression algorithm to compress a given stream of characters.

Your squash program should be a UNIX filter. That is, your squash program should read from standard input and write to standard output. A typical command-line execution of your program might look like this:

squash < file1 > compressedfile

Your squash program should work correctly when an input character is escapechar itself. Hint: Use an escape sequence to encode escape characters.

Your program should work for standard input lines of any length.

Your Second Task

Your second task is to write a UNIX filter named unsquash.  Your unsquash program should be the inverse of your squash program. It should read from standard input a character stream that, presumably, has been compressed by your squash program. It should write the original character stream to standard output. A typical command-line execution of your unsquash program might look like this:

unsquash < comressedfile > file2

If your unsquash program detects that standard input contains a malformed squashed stream, then it should stop writing to standard output, write the message "Malformed squashed stream" to standard error, and exit. The stream is malformed if unsquash encounters an escapechar that is not followed by both a char and a count.

Design

You should design your squash program as a deterministic finite state automaton (FSA). The FSA concept will be described in lectures. The FSA concept also is described in Section 7.3 of the book "Introduction to Computer Science," by Drs. Sedgewick and Wayne. That book section is available through the web at http://www.cs.princeton.edu/introcs/73fsa/.

Generally, a program should not consist of one large main() function. Instead a program should consist of multiple small functions, each of which performs a single well-defined task. However, for this assignment properly splitting your programs into multiple functions would involve using call-by-reference -- a technique that we will not have covered completely prior to this assignment's due date. So, you need not split your squash and unsquash programs into multiple functions. (Nevertheless, we encourage you to do so.)

Generally, a (large) C program should consist of of multiple source code (.c) files.  For this assignment, you need not split your source code into multiple files. That is, you may place all source code that comprises the squash program in a single file (named squash.c), and all source code that comprises the unsquash program in a single file (named unsquash.c). Subsequent assignments will ask you to write programs which should consist of multiple source code files.

Limit line lengths in your source code to 78 characters. Doing so allows us to print your code in two columns, thus saving paper.

We suggest that your programs read characters from standard input using the standard C getchar() function, and write characters to standard output using the standard C putchar() function..

Logistics

Step 1: Create Source Code

Use xemacs to create source code in files named squash.c and unsquash.c.

Step 2: Preprocess, Compile, Assemble, and Link

Use the gcc command with the -Wall, -ansi, and -pedantic options to preprocess, compile, assemble, and link your programs.

Step 3: Execute

Execute your programs multiple times on various input files that test all logical paths through your code.

We have provided several files in hats directory /u/cos217/Assignment1:

• A file named samplesquash containing an executable version of a correct squash program. Your squash program should behave exactly the same as samplesquash.  That is, your squash program should write exactly (character for character) the same data to standard output as does samplesquash.
• A file named sampleunsquash containing an executable version of a correct unsquash program. Your unsquash program should behave exactly the same as sampleunsquash. That is, your unsquash program should write exactly (character for character) the same data to standard output and standard error as does samplesunquash.
• Many .txt files (that is, files whose names end with ".txt") that can serve as input files to your squash program.
• A few .err files (that is, files whose names end with ".err") that can serve as input files to test the error handling capabilities of your unsquash program.
• Files named grade1, grade1diff, and grade1differr. Those files are bash scripts that automate the testing process. Comments at the beginning of the files describe how to use them. After copying the scripts to your project directory, you may need to execute these commands:

chmod 700 grade1
chmod 700 grade1diff
chmod 700 grade1differr

to make the scripts executable.

You should copy those file to your project directory and use them to help you test your programs. You should create additional test files as you see fit.

Note: The bash scripts use the UNIX diff (file difference) command.  The command:

diff somefile1 somefile2

writes to standard output an indication of the differences, at the line level, between somefile1 and somefile2. If somefile1 and somefile2 are identical, then diff produces no output.

Note: The bash scripts also use the UNIX od (octal dump) command. The command:

od -vc somefile

writes to standard output the characters that comprise somefile. It writes non-printable characters as octal numbers.

Step 4: Create a readme File

Use xemacs to create a text file named "readme" that contains:

• Your name and the assignment number.
• A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course Policies web page.
• (Optionally) An indication of how much time you spent doing the assignment.
• (Optionally) Your assessment of the assignment: Did it help you to learn? What did it help you to learn? Do you have any suggestions for improvement? Etc.
• (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.

Descriptions of your code should not be in the readme file. Instead they should be integrated into your code as comments.

Step 5: Submit

Submit your work electronically on hats via the command:

/u/cos217/bin/i686/submit 1 squash.c unsquash.c readme

If the directory /u/cos217/bin/i686 is in your PATH environment variable, then you can abbreviate that command as:

submit 1 squash.c unsquash.c readme

If you are using the bash shell and have copied files .bashrc and .bash_profile from the /u/cos217 directory to your HOME directory, then directory /u/cos217/bin/i686 indeed is in your PATH environment variable. You can examine your PATH environment variable by executing the command "printenv PATH".

Grading

Program Understandability

• Uses a consistent and appropriate indentation scheme. All statements that are nested within a compound, if, switch, while, for, or do...while statement should be indented. Please use spaces instead of tabs to indent. Please use at least a 3-space indentation scheme. Note that the xemacs editor can apply a consistent indentation scheme to your program automatically.
• Contains descriptive identifiers. The names of variables, constants, structures, types, and functions should indicate their purpose. Remember that C can handle identifiers of any length, and the first 31 characters are significant. We encourage (but do not require) you to prefix each variable name with characters that indicate its type. For example, the prefix "c" might indicate that the variable is of type char, "i" might indicate int, "pc" might mean pointer to char, "ui" might mean unsigned int, etc. Give names to "magic numbers," as described in Kernighan & Pike Section 1.5.
• Contains carefully worded comments. Each source code file should begin with a comment that includes your name, the number of the assignment, and the name of the file. Each function -- especially the main() function -- should begin with a comment that describes what the computer does when it executes that function. It should do so by explicitly referring to the function's parameters and return value. The comment also should state what, if anything, the computer reads from standard input or any other stream, and what, if anything, the computer writes to standard output, standard error, or any other stream while executing the function. Finally, the function's comment should state which global variables the computer uses and affects when executing the function.