D. J. Bernstein
Data structures and program structures
MCS 275, Spring 1999

What I did in class

19990111: Summary of course topics: more about the C language; the standard C library; programming tools. Summary of student goals: power; literacy; understanding. Advanced topics: code portability; code efficiency; code reliability; code security. Overview of monitoring tools: input/output recording tools; low-level tracing tools; interactive debuggers. Using script. Introduction to gdb. Homework assignment #0: print a variable in a program under gdb and script.

19990113: [Course announcement handout. Syllabus handout.] The memory picture. How variables are stored in memory. Portability warning about size of int. What variable assignment does to the memory picture. Finding the location of a variable. Finding the variable at a location. Defining a ``pointer to int'' location variable. Examples of reading and writing variables through pointers. Code to swap two integers. Incorrect swap function. Call-by-value. Memory picture for the incorrect swap function. Correct swap function using pointers. Memory picture for the correct swap function.

19990115: Homework assignment #1. Converting call-by-value into call-by-reference. Example: biglittle function. Using call-by-reference for return values. Comments on the 0 pointer and NULL. When arrays are useful. Defining array variables. Accessing array elements. Accessing array elements with a variable subscript. Example: storing values in an array.

19990118: No class.

19990120: Example: printing values from an array. Example: printing input in reverse order using a partially filled array. Common code for dealing with a partially filled array. Reliability/security warning about buffer overflows. Array initializers. Portability warning about initializing arrays inside functions. Array initializers using []. Array initializers with zero-filling. Warning about uninitialized arrays. Using sizeof to count the number of elements in an array.

19990122: Conversion of an array name into a pointer to the first element. Accessing an array through a pointer to the first element. Effect of pointer arithmetic in terms of bytes. Example: sum() function. Using array notation for pointers. Consistency of array notation for pointers and for arrays. Abbreviating the sum() function with array notation. Abbreviating the sum() function further with -- and ++. Warning that arrays are not first-class. Using [] in function parameters.

19990125: Defining a multidimensional array. Memory picture of a 2x2 array. Memory picture of a 3x2 array. Function to add two 2x2 arrays elementwise. Memory picture for accessing 2x2 array through pointer to first row. Initializing a multidimensional array. When structs are useful. Defining a struct type. Creating a struct variable. Differences between struct and array: struct components are not necessarily consecutive in memory; struct components don't have to all be the same type; it's easy to create arbitrarily large arrays; structs are first-class.

19990127: Struct initializers. Struct initializers with zero-filling. Portability warning about initializing structs inside functions. Example of printing year, month, day variables: using three separate ints; using array of three ints; using struct containing three separate ints. Copying structs. Not allowed to compare structs. struct div_t and the div() function. Memory picture of calling the div() function. Putting an array inside a struct to make it first-class. Merging a struct type definition with a variable definition. The arrow notation.

19990129: Unions. What unions look like in memory. General comments about choosing data structures to implement objects. Linear lists. Common operations on linear lists. Features of arrays and of linked lists.

19990201: Definition of linked list in two arrays: list is data[next[0]], data[next[next[0]]], etc., stopping before data[0]; unused are data[avail], data[next[avail]], etc., until data[0]. Example of a linked list in memory. Code to print a linked list. Code to remove an element from a linked list. Example: removing first element. Example: removing last element.

19990203: Homework assignment #2. Code to insert an element into a linked list. Code to initialize a linked list to empty. Example: inserting element at beginning of list. Linked list in array of structs. Memory picture. Linked list in array of structs with pointers.

19990205: Code to delete an element from a linked list in an array of structs with pointers. Code to insert an element. Examples. Code to print the list in order. Example. What's different about dynamic linked lists. How to use malloc().

19990208: Code to define a dynamic linked list. Code to insert into a dynamic linked list. Examples: inserting 31 at beginning of empty list; inserting 41 at beginning; inserting 59 after 41. Code to print a dynamic linked list. Example. Code to remove an element from a dynamic linked list; how to use free(). Further comments on malloc() and free().

19990210: Guarantees provided by malloc(). The return type for malloc(). Comments on managing large projects. How to compile several .c files into one program in one step. Another way: compile each .c separately into .o; then link the .o files into one program. Recording a single-step compilation in Makefile. Warning about tabs in Makefile. Running a single-step compilation with make. Dependency checking, part 1: make skips commands for targets newer than all dependencies. Recording separate compilation in Makefile. Warning about completely blank lines in Makefile. Dependency checking, part 2: make creates dependencies before creating target. What happens when one .c file changes.

19990212: Order of operations in Makefile; first target is the default. Using Makefile macros. Common compiler options. What happens when a dependency is missing. Problem with splitting up program into several files: have to add declarations. General concept of declarations. General concept of definitions. Using extern to declare a variable without defining it. Examples of programs in two files with extern declarations. Example of a function declaration. General rule for each variable: exactly one definition, any number of declarations.

19990215: Example of several files with many declarations. Problem of maintaining declarations that are copied into many files. Example of #include. The .h convention. Doing #include of the .h file in the corresponding .c file so that compiler can check consistency. What #include "file" means. What #include <file> means. Defining a static variable. The concept of variable scope. Example of scope: definition. Example of scope: declaration before definition. Example of scope: local variable overriding global variable. Example of scope: static variables.

19990217: Complete program using random.c, random.h, main.c. Distinction between the static int x in random.c and the int x in main.c. What happens when random() is called. How to fix a multiple definition of x: use extern if there is supposed to be a shared x variable; use static if there are supposed to be two separate x variables. Portability notes on how compilers handle multiple definitions. Using static inside functions. The general concept of lifetime. Table of scope and lifetime for int x outside {}, static int x outside {}, int x inside {}, static int x inside {}.

19990219: Examples of random() using int x outside {}, static int x outside {}, int x inside {}, static int x inside {}. Warning about uninitialized variables. Automatic 0 initialization for static variables. The general concept of a string. Example. C name for a byte: char. Distinction between byte and character; references to Unicode, ISO 10646, UTF-8. Printable names in '' for various bytes. Octal codes in ''. Abbreviated octal codes in ''. Special names: '\n', '\r', '\b', '\f', '\t', '\\', '\'', '\"'. Syntax of "".

19990222: Midterm review.

19990224: Midterm #1.

19990226: The C string convention: pointer p to char, representing p[0], p[1], p[2], etc. until p[n] == 0. Example of C string in char array. Inability to use 0 inside C strings. Initializing a char array with separate chars. Initializing a char array with "". Examples. String constants: what "" means outside of array initializers. Portability warning about string constants being unwritable. Printing a string. Using pointers instead of array indices.

19990301: Homework assignment #3. printstring() code moving pointer. Memory picture for printstring("Hi"). Further abbreviation of printstring() code. strlen() code using integer index. strlen() code using pointer subtraction. Memory picture for strlen("Hi"). What getchar() does. Warning about storing getchar() return value in char. Code for reading entire input into an array. Memory picture for reading "a\nb\n". Reliability warning: byte 0 can legitimately appear in input. Reliability/security warning: input buffer overflow.

19990303: Example of command-line arguments. First two parameters to main(): usually called argc and argv. Code for main() with parameters. Memory picture for argv. What argc means. Using argv[1] as a string. Printing first few characters of argv[1]. Dynamically allocated strings. Example of allocating 1000 bytes and using a few bytes. Code for strdup(). Example: memory picture for strdup("Hi").

19990305: Example of input and output of rev program. Assumptions for rev: lines are short; input ends with newline. Code for rev. Memory picture for rev. General idea of splitting input into lines. What happens if input does not end with newline; ``partial final line.'' Benefits of the standard C library. Code for strequal(). What strequal() does. What the standard strcmp() function does. What ``string prefix'' means.

19990308: Comments on midterm. Code for strprefix(). What ``string suffix'' means. Code for strsuffix().

19990310: Comments on efficiency of strsuffix(). Some basic string-inspection functions in the standard library: atoi(); atof(); strlen(); strcmp(); strncmp(); strchr(); strrchr(); strcspn(). Some string functions that change the string: strtok(); strcpy(); strcat(); strncat(). Example of code using strtok().

19990312: Code for program to print command-line arguments in alphabetical order. Example. Basic features of stdio: file I/O; formatted I/O. Concept of a file in stdio: any device that reads or writes a stream of characters. Concept of a randomly accessible file. Files available for reading: stdin; files explicitly opened. Sample code to open, read, and close file. Warning about fopen() failures. Using stdin as a file. Warning about limits on number of files opened simultaneously. Good practice to close file immediately after using it. What stdin normally means. How to run a program with stdin reading from a file.

19990315: No class.

19990317: No class.

19990319: No class.

19990322: I/O errors in fgetc(); feof() and ferror(). Printing strerror(errno) to explain error. Sample code to open, read, and close file, checking for errors. Files available for writing: stdout; stderr; files explicitly opened. What stdout and stderr normally mean. How to run a program with stdout writing to a file. Pipelines: feeding stdout of one program through stdin of another. General procedure to open a file for writing. The concept of an output buffer. Warning that fclose() can fail. Using fflush(). Warning about synchronization of multiple programs handling one file.

19990324: Advantages of randomly accessible file over memory. Disadvantages of randomly accessible file over memory. Automatic newline conversions under some operating systems. Opening a file for binary reads. Opening a file for binary writes. Sample code for peek() function. Arguments to fseek(). Sample code for poke() function. Efficiency notes on fopen(). Opening a file for update. Requirement to fseek() between reading and writing. Differences between printf(), fprintf(), sprintf(). Differences between scanf(), fscanf(), sscanf(). Arguments and %s. Return value of sscanf().

19990326: Example of "%+-6.4ld" in printf. Flags, minimum width, precision, conversion. Effect of minimum width: pad on left with spaces if necessary. Flag -: pad on right with spaces if necessary. Flag 0: pad on left with zeros if necessary. Normal signs for positive and negative numbers; flags + and " ". Precision for integers. Precision for floating-point numbers. Precision for strings. Example of "%*6d" in scanf. Flag *: skip the assignment. Maximum width. Conversions %d, %ld, %u, %lu, %o, %x. Conversions %e, %f, %g, %le, %lf, %lg; differences between float and double. Conversions %p, %n, %%. Conversions %c and %s for printf. Conversions %c, %s, and %[ for scanf.

19990329: More scanf and printf examples: %100[blah], %4d%2d%2d, %-8.8s, %6.1f, %06d. Data flow in the C preprocessor and compiler. Basic C preprocessor commands: #include, #define, #undef, #ifdef, #ifndef, #else, #endif. General concept of macros. The EOF macro in stdio.h. What happens to code using EOF. Why parentheses are necessary in the EOF definition. A simple macro with parameters. What happens to code using the macro. Extra flexibility of macro over function. Constant variable instead of EOF. Efficiency notes on macros. Typical array-size macro. Benefit of modularizing code that may change later. Example of a macro that doesn't behave like a function.

19990331: The uppercase convention for names of macros that don't behave like functions. Violations of the convention: putc(), getc(). Other stdio macros: putchar(), getchar(). How to see the C preprocessor output under UNIX. Advantages of functions over macros. Example of callback functions: qsort(). The __LINE__ and __FILE__ macros. Sample ERR macro using __LINE__, __FILE__, and strerror. Example of what preprocessor does with ERR. #ifdef, #endif. #ifndef, #endif. #ifdef, #else, #endif. UNIX cc options for defining macros.

19990402: Example of #ifdef to select among two pieces of code for efficiency reasons. Example of nested #ifdef to select among several pieces of code. Using #ifdef for debugging code; assert(). Nested #include files. Example of datetime.h not compiling without date.h. Solution #1: Whoever includes datetime.h must include date.h first. Inconvenience of solution #1. Solution #2: Have datetime.h include date.h itself. Scaling problems of nested #include files. Solution #3: Have datetime.h include date.h, and protect date.h. Code for protected date.h. What preprocessor does with protected date.h. Scaling of protected include files. Introduction to memory segments: stack, bss, data, heap. Example of stack for main() calling add().

19990405: Why stacks typically grow from right to left; traditional memory picture. Return addresses on a stack. How function calls are implemented using the stack. How function returns are implemented using the stack. Example of stack for main() calling add() and sub(). Concept of recursive functions. Code for factorial(n). Stack picture for factorial(3). Example of code that allows stack smashing.

19990407: #undef. Midterm review.

19990409: Midterm #2.

19990412: Review of how function calls interact with stacks. Example of code that allows stack smashing. Results of stack smashing. What happened to the stack. Stack smashing with small buffers by writing past the return address. Stack smashing with small buffers by using other parts of memory. Working around byte restrictions in a buffer overflow. Using asm code. Reference to bugtraq. Standard C library routines prone to buffer overflows. The general concept of privileges. Why privileges are useful: minimize the amount of security-critical code.

19990414: Easy operations in transistors: and, or, not, xor. Building any function as a circuit using those operations. Minimalism: can build any function from nand. Using bit operations in C: &, |, ~, ^. Warning to always use unsigned for bit operations. Parallel bit operations. Integers as sums of powers of 2. Memory pictures of numbers in base 2. Examples of bit operations. Difference between ~ and !. Common applications of bit operations: saving space; saving time; cryptography. Example of code handling 1000000 bits stored in separate ints. Example of code handling 1000000 bits packed into unsigned chars.

19990416: Example of setting bits inside packed bit array. Left-shifting 1 to compute powers of 2. Numbering of bits inside packed bit array. General code to set bit inside packed bit array. General code to clear bit inside packed bit array. General code to read bit inside packed bit array. Example: setting two bits, reading a bit, clearing a bit. Saving time in checking whether any bit is zero. Saving time in componentwise multiplication of one bit array by another.

19990419: Comments on midterm.

19990421: Left shifts as multiplication. Examples in base 2. Right shifts as division. Examples in base 2. Comments on signed shifts. Examples of rotation. Expressing rotation in terms of shift. Notation for rotation in some compilers. Use of rotation in cryptography. Inline functions.

19990423: Code for sqrtint() using left shifts. Example: square root of 10. General notes on efficiency. Real time versus process CPU time. Notes on time(), gettimeofday(), RDTSC, UNIX time program, getrusage(). Function profiles, self and cumulative. How to use gprof under UNIX. Picture of a graphics screen; concept of a pixel. How an 800x600, 256-color graphics screen is normally organized in memory. Variant: unused bytes at the end of each row. The concept of a palette.

19990426: Colors as combinations of red, green, blue. Examples of simple operations on a graphics screen. Anti-aliasing and motion blur.

19990428: Coming up. Planned: Review for final.

19990430: Coming up. Planned: Review for final.

19990503: Final, 1-3, LC D1.