CS107 Handout 19 Spring 2008 April 28, 2008 Assignment 5: Raw Memory Brought to you by Julie Zelenski and Jerry Cain. Bits and Bytes The first several weeks of CS107 are all about solidifying your understanding of memory: arrays, pointers, typecasts, parameter-passing, etc. and then supplementing it with a better understanding of compile-time language implementation: the layout and organization of memory, what kind of code is generated from a compiler, how the runtime memory structures (stack and heap) are managed, and so on. The implementation problem set is a break from the hard-core C coding. It’s your chance to try your hand at generating machine code, to do some in-depth experimentation with the compiler and the debugger in order to dissect your programs. Recall that you’re not expected to hand anything in for this assignment. You’re to work on the problems independently, compare your solutions to the answer key (to be provided on Friday), and ask questions where needed. To Be Completed By: May 7th at 7:00 p.m. How to compile a program without a Makefile You may want to write little test programs for the lab problems. You're used to relying on the provided Makefiles we wrote to build multi-module programs, but it is possible to just directly invoke the compiler at the shell. Refer to the big UNIX handout for lots of details— here is just a brief summary: To compile and link one file into an executable, you use: % gcc binky.c -o binky which says to compile the file binky.cc, link it, and name the resulting executable binky. To compile multiple files into one executable, you first compile each file separately: % gcc -c streamtokenizer.c -o stremtokenizer.o % gcc -c wordgames.c -o wordgames.o This compiles the file streamtokenizer.c into the output file streamtokenizer.o and stops without linking it. (same for wordgames.c). And then you invoke gcc again to link like this: % gcc streamtokenizer.o wordgames.o -o word-games that takes the two compiled object files and links them together into one executable called word-games. You can also add other flags for compiling after the gcc such as -Wall (to generate all warnings), -g (to include debugging information, and -O (for optimization). Please note that some of the resources used in this assignment require a Stanford Network Account and therefore may not be accessible.2 Problem 1: Binary numbers and bit operations Since computers work entirely in binary, learning how to manipulate numbers in the base two system can sometimes come in handy. Here are a few suggestions of some exercises to test out your understanding of binary numbers. Try converting a few decimal numbers into binary form, do some binary arithmetic with them (add, subtract, maybe even a multiply), and convert the result back to decimal to verify you have it correct. This lets you know you are on top of the basic workings and know how to do all that tedious carrying. Write a test program to find out what happens when you overflow the range of a variable, such as adding two shorts that are both very large. Is any error reported on the overflow? How is the result related to what the desired answer would have been? What happens when you do the same thing with unsigned shorts instead of signed? Write a program that assigns values between different-sized integer types. What happens when you go from a smaller-sized type to a larger? What about the other direction? How is the result related to the original number? Does this match your understanding of the binary representation? In addition to the usual logical AND, OR, and NOT connectives, there are bitwise versions of these operations available in C. The bitwise AND (expressed with single &) compares its two operands bit-by-bit and reports which bits were 1 in both, 0 otherwise. For example: unsigned char a = 12, b = 5, c; c = a & b; Doing a bitwise AND on 00001100 (12 in binary) and 00000101 (5 in binary) gives the result 00000100, since the two patterns have only one bit in common. There is a bitwise OR operator (single |) that works similarly to logical OR, but operates at the bit level. There is also a bitwise exclusive OR (^) that reports which bits are on in one operand, but not both. The bitwise NOT (~) is a unary operator that just inverts all of the bits in its operand. Bit manipulations are used in a variety of situations (graphics, robotics, cryptography, etc.) especially when you need to work with a form of packed data. How could you use bit operations to determine the remainder of a number when divided by 4 (or any power of two for that matter?) How could use a bit approach to determine if an integer would lose data when assigned to a short or a char? How can you use bit operations to convert a number from negative to positive or vice versa? (Refer back to the “two’s complement” representation for negative numbers we showed in class and try to work through what the patterns are in terms of bits.) One neat feature of the bitwise XOR operation is that it is completely invertible. If you XOR a with b and then XOR the result with b again, you get back a (trace this out for yourself). This makes this operation useful for encryption and decryption. How3 could you construct a simple program that encrypts a file using XOR and a specified “key”? What would happen if you run the program twice in a row using the same key? Probelm 2: ASCII and extended ASCII In lecture, we showed the binary polynomial representation used for the integer-derived types. Characters belong to the integer family and although computers agree on the bit pattern used to represent the number 10 or 250, the mapping from number to character is where things break down. The ASCII character set establishes mappings for 0 to 127 that are used by all computers, but the extended ASCII characters, from 128 to 255, varies from system to system. In /usr/class/cs107/assignments/assn-5-raw-memory, there is a file called ascii.txt that contains a table of all possible characters. Try viewing this file on UNIX and then again on Macintosh or a PC (either by using ftp to transfer the file or viewing the file with a Web browser) and observe how the exact same bit pattern can be interpreted as different characters on different systems. Which number-to-character mappings seem to be reliable? Which are not? What implications does this have for using extended ASCII