This course website is from a previous semester. If you are currently in the class, please make sure you are viewing the latest course website instead of this old one.
Everyone:
Next week, we will transition from high-level scripting languages such as Bourne Shell and Python to the ubiquitious C systems programming language. We shall descend down the software stack, away from user applications, and towards the lower level system calls that power our programs.
That is, rather than focusing on how to use or compose tools such as cat, grep, or sort, we will instead learn how to build these basic components, while adhering to the Unix philosophy.
The focus of this reading is to introduce you to programming the C programming language. In particular, you should become familiar with pointers, arrays, and strings.
The readings for this week are:
Most of this should be review from Fundamentals of Computing, so skim through Chapter 1 through Chapter 7. In particular, focus on Chapter 5. Pointers, Chapter 6. Arrays, and Chapter 7. Strings.
Again, most of this should be review from Fundamentals of Computing and Data Structures, so skim this document and make sure you understand how to write and use a Makefile.
#### Propaganda - [Learn C programming and the rest will come](https://www.zeroequalsfalse.press/2017/11/29/c/) - [The cost of forsaking C](https://blog.bradfieldcs.com/the-cost-of-forsaking-c-113986438784) - [The Unreasonable Effectiveness of C](http://damienkatz.net/2013/01/the_unreasonable_effectiveness_of_c.html) #### C Language - [A Little C Primer](https://en.wikibooks.org/wiki/A_Little_C_Primer) - [C Programming Language](https://www.geeksforgeeks.org/c-programming-language/) - [The Descent to C](http://www.chiark.greenend.org.uk/~sgtatham/cdescent/) | #### Pointers and Arrays - [The 5 Minute Guide to C Pointers](http://denniskubes.com/2017/01/24/the-5-minute-guide-to-c-pointers/) - [Basics of Pointers and Arrays in C](http://denniskubes.com/2012/08/19/pointers-and-arrays-in-c/) - [Basics of Memory Addresses in C](http://denniskubes.com/2012/08/17/basics-of-memory-addresses-in-c/) #### Makefiles - [GNU Make](https://www.gnu.org/software/make/manual/make.html) - [Make files not war](https://fabianstumpf.de/articles/makefiles.htm) - [Make](https://www.ploxiln.net/make.html) |
We will be using C99 version of the C programming language. This means that
when you compile your programs with gcc, you should include the -std=gnu99
compiler flag:
$ gcc -Wall -g -std=gnu99 -o program source.c
Note: The -Wall
flags enable most warnings while the -g
flags
enable debugging symbols, which will come in handy when we need to use tools
such as gdb and valgrind.
This week, the reading is split into two sections: the first part is a
dredd quiz, while the second part involves two C programs: sort.c
and
grep.c
.
To test the C program, you will need to download the Makefile and test scripts:
$ git checkout master # Make sure we are in master branch
$ git pull --rebase # Make sure we are up-to-date with GitHub
$ git checkout -b reading09 # Create reading09 branch and check it out
$ cd reading09 # Go into reading09 folder
# Download Reading 09 Makefile
$ curl -LO https://raw.githubusercontent.com/nd-cse-20289-sp22/cse-20289-sp22-assignments/master/reading09/Makefile
# Download, build, and execute tests
$ make test
Given the following C program, sum.c, which computes the sum of all the integers read from standard input:
/* sum.c */
#include <stdio.h>
#include <stdlib.h>
/* Constants */
#define MAX_NUMBERS (1<<10)
/* Functions */
size_t read_numbers(FILE *stream, int numbers[], size_t n) {
size_t i = 0;
while (i < n && scanf("%d", numbers[i]) != EOF) {
i++;
}
return i;
}
int sum_numbers(int numbers[]) {
int total = 0;
for (size_t i = 0; i < sizeof(numbers); i++) {
total += numbers[i];
}
return total;
}
/* Main Execution */
int main(int argc, char *argv[]) {
int numbers[MAX_NUMBERS];
int total;
size_t nsize;
nsize = read_numbers(stdin, numbers, MAX_NUMBERS);
total = sum_numbers(numbers);
printf("{}\n", total);
return EXIT_SUCCESS;
}
And the following C program, cat.c, which implements the cat command:
/* cat.c */
#include <errno.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* Globals */
char * PROGRAM_NAME = NULL;
/* Functions */
void usage(int status) {
____(stderr, "Usage: %s\n", PROGRAM_NAME); /* 1 */
____(status); /* 2 */
}
bool cat_stream(FILE *stream) {
char buffer[BUFSIZ];
while (____(buffer, BUFSIZ, stream)) { /* 3 */
____(buffer, stdout); /* 4 */
}
return true;
}
/* Main Execution */
int main(int argc, char *argv[]) {
int argind = 1;
/* Parse command line arguments */
PROGRAM_NAME = ____; /* 5 */
while (argind < argc && ____(argv[argind]) > 1 && argv[argind][0] == '-') { /* 6 */
char *arg = argv[argind++];
switch (arg[1]) {
case 'h':
usage(0);
break;
default:
usage(1);
break;
}
}
/* Process each file */
return !cat_stream(stdin);
}
/* vim: set sts=4 sw=4 ts=8 expandtab ft=c: */
For these types of questions, your first instinct should be to play with the code. As a computer scientist, your approach to any new body of code is to study and investigate it by taking it apart, modifying it, breaking it, and putting it back together.
As Peter Seibel writes, code is not literature:
We don’t read code, we decode it. We examine it. A piece of code is not literature; it is a specimen ... and we are naturalists.
If you truly want to understand something, simply looking up an answer on Google or StackOverflow is insufficient. For true mastery, you need to apply the principle of the Hands-On Imperative:
Hackers believe that essential lessons can be learned about the systems—about the world—from taking things apart, seeing how they work, and using this knowledge to create new and more interesting things.
TL;DR: Download the code. Compile it. Break it. Fix it. Happy Hacking.
Record the answers to the following Reading 09 Quiz questions in your
reading09
branch:
You are to write two simple C programs based on the examples above.
sort.c
¶Use sum.c
as the basis for a C program called sort.c
, which uses
qsort to implement a basic version of sort:
$ shuf -i 1-10 | ./sort
1
2
3
4
5
6
7
8
9
10
Note: You should use the provided read_numbers
function and simply call
qsort of numbers
and print out each element in the array.
Hint: Since you will be sorting int
s, you will need a custom
comparison function. To save you the trouble of searching
StackOverflow, you can use the following:
int compare_ints(const void *a, const void *b) {
int ia = *(const int *)a;
int ib = *(const int *)b;
return ia - ib;
}
This should be the last argument to qsort. You can also refer to the example in Beej's Guide to C Programming.
grep.c
¶Use cat.c
as the basis for a C program called grep.c
, which uses
strstr to implement a basic version of grep:
$ ./grep -h # Display Usage
Usage: ./grep PATTERN
$ ls | ./grep ep # Search stdin
grep
grep.c
test_grep.c
$ ls | ./grep NOPE ; echo $? # Exit code on failure
1
Note: Use the strstr function to search for strings (you do not need to support regular expressions).
Note: Make sure you return with an non-zero exit code if the
PATTERN
is not found in the input stream.
Makefile
¶To build your programs, you need to update the provided Makefile to include
rules or recipes for the sort
and grep
targets. Be sure to use the
CC
and CFLAGS
variables in your rules.
Once you have a working Makefile, you should be able to use the make command to run your recipes:
$ make clean # Remove targets
rm -f sort grep
$ make # Build targets
gcc -g -Wall -std=gnu99 -o sort sort.c
gcc -g -Wall -std=gnu99 -o grep grep.c
$ make test # Test programs
Checking reading09 sort ...
sort 1 ... Success
sort 1 10 ... Success
sort 1 100 ... Success
sort 1 1000 ... Success
sort 1 1000 (valgrind) ... Success
Score 1.00 / 1.00
Status Success
Checking reading09 grep ...
grep usage (-h) ... Success
grep usage (no arguments) ... Success
grep root /etc/passwd ... Success
grep root /etc/passwd (valgrind) ... Success
grep login /etc/passwd ... Success
grep login /etc/passwd (valgrind) ... Success
grep asdf /etc/passwd ... Success
grep asdf /etc/passwd (valgrind) ... Success
Score 1.00 / 1.00
Status Success
To submit you work, follow the same process outlined in Reading 01:
#--------------------------------------------------
# BE SURE TO DO THE PREPARATION STEPS ABOVE
#--------------------------------------------------
$ cd reading09 # Go into reading09 folder
$ $EDITOR answers.json # Edit your answers.json file
$ ../.scripts/check.py # Check reading09 quiz
Checking reading09 quiz ...
Q01 0.25
Q02 0.25
Q03 0.25
Q04 0.25
Q05 0.60
Q06 0.20
Q07 0.20
Score 2.00 / 2.00
Status Success
$ git add answers.json # Add answers.json to staging area
$ git commit -m "Reading 09: Quiz" # Commit work
$ $EDITOR Makefile # Edit source code
$ $EDITOR sort.c # Edit source code
$ $EDITOR grep.c # Edit source code
$ make # Build programs
$ make test # Run tests
$ git add Makefile # Add Makefile to staging area
$ git add sort.c grep.c # Add source code to staging area
$ git commit -m "Reading 09: Code" # Commit work
$ git push -u origin reading09 # Push branch to GitHub
Remember to create a Pull Request and assign the appropriate TA from the Reading 09 TA List.
DO NOT MERGE your own Pull Request. The TAs use open Pull Requests to keep track of which assignments to grade. Closing them yourself will cause a delay in grading and confuse the TAs.