CPSC 213 – Assignment 8 Dynamic Control Flow solved

$35.00

Category: You will receive a download link of the .ZIP file upon Payment

Description

5/5 - (1 vote)

Learning Objectives Here are the learning objectives of this assignment, which will be examined in this week’s quiz. They are a subset of the unit learning objectives listed on Slide 2 of Unit 1c. After completing this assignment you should be able to: 1. write C programs that use function pointers; 2. explain why switch statements in C (and Java until version 1.7) restrict case labels to cardinal types (i.e, things that map to natural numbers); 3. convert C switch statement into equivalent C statement using gotos and an array of label pointers (a gcc extension to C); 4. convert C switch statement into equivalent assembly language that uses a jump table; and 5. determine whether a given switch statement would be better implemented using if statements or a jump table and explain the tradeoffs involved. Goal This week you continue from where you left off last week with poly.c to look at the use of function pointers as parameters to the Dr. Racketish list primitives and as a way to implement switch statements. First you will create a small portion of Dr. Racket in C. You will start with a provided implementation of a dynamically expandable list that knows its length. It’s like a list in Dr. Racket (or Java), and unlike arrays in C that are fixed size and do not know how big they are intrinsically. You will implement several functions that operate on lists using abstractionfunctions (i.e., C function pointers). You will test your program using a provided test file. Finally, you will implement your own program that uses this list code. Then you will move to switch statements. First you will examine the snippet we looked at in class that gives you an example of a switch statement that is implemented by a jump table. Next, you will examine a mystery assembly program to determine what it does. Finally you will convert a C program that contains switch statements into one that uses only goto’s and a jump table, instead of switch statements. Funny enough, this program is a C version of the Java Simple Machine simulator that you used in Assignments 1-7, perhaps a fitting way to bid a fond adieu to assembly language (for now). Question 1: Using Function Pointers on Lists [45%] In www.ugrad.cs.ubc.ca/~cs213/cur/assignments/a8/code.zip in the q1 subdirectory you will find the following files: list.[ch], test.c, and Makefile. Part 1: Implement the List Iterator Functions The file list.c contain the skeleton implementation of several list operators adapted from Dr. Racket: map1, map2, foldl, filter, and foreach. The two map functions are variations on Dr. Racket’s map: map1 operates on one list and map2 on two. Here’s a brief summary of what these functions do (google Dr. Racket for more): • map takes a function and a set of lists (in our case one or two lists) and generates a new list by applying the function to each element of the list; (map + ‘(1,2,3) ‘(1 1 1)) => ‘(2 3 4) • foldl takes a function, an initial value, and a set of lists (in our case just one list) and generates the value that results from iterating over the list, calling the function on an accumulated value, which starts at the specified initial value, and each element of the list in turn, updating the accumulated value as it goes; (fold + 0 ‘(1,2,3) => 6 • filter takes a function and a set of lists (in our case just one) and generates a new list that contains the elements of the original list for which the function returns true; (filter positive? ‘(-2,3,-8,5)) => (3,5) • foreach takes a function and a list of lists (in out case just one) and calls the function for each item in the list. It produces no value. (Note that the actual name of this function in Dr. Racket is for-each, but we are going to call it foreach since you can’t have dashing is C names. (foreach print ‘(1 2 3)) => # printing the values 1, 2 and 3 Implement the TODO portions of list.c and use test.c, which uses these functions, to test your code. Note that if you did Part 1 you already have two of these completed. Your code must pass valgrind with no memory leaks. Be sure to run it with a variety of inputs, include one with a long list of strings and integers (i.e., longer than 10 each). Part 2: Implement a Program that Uses the List Iterator Functions Finally, implement a program with no loops of any kind, other than an initial loop to read the values of argv in Step 1 below, that uses list.[ch] to do the following, placing the implementation in the file trunc.c. The input to this program is a list of numbers and strings presented on the command line; e.g.,: ./trunc 4 apple 3 peach 5 banana 2 3 grape plum The program uses the numbers to truncate the strings and prints the resulting strings, one per line and, then the string concatenated (and separated by spaces), and finally the maximum string length. So in this case the output would be. appl pea banan gr plu appl pea banan gr plu 5 Notice that the numbers are pared with strings based on their order in the string not their proximity to each other and so the following would produce the same output. ./trunc 4 3 5 2 3 apple peach banana grape plum Here is an outline of the program. You need to follow the steps listed. Take each step one at a time. Implement a step and then test it by using list_foreach to print the list you create (be sure to remove these extra prints, however, before you handin your solution; the only prints allowed in the final version are those specified in Steps 7 and 8). 1. Read a list of strings from the command line and add them to a list. Note that argv is an array of the command line arguments and argc is the length of that array. Ignore argv[0] since that is the path to the program itself. 2. Iterate over the list to produce a new list of numbers (the list must actually be a list of pointers to integers) that processes each string to determine if it is a number. If it is, the corresponding value in this new list should be that number, otherwise it should be a -1. Use the standard-C library procedure strtol to convert strings to numbers. See its man page for details. 3. Iterate over the new list of numbers and the original list of strings together to produce a new list of strings with a NULL value for every string that is a number (i.e., where the number list is not -1). 4. Filter the number list to produce a new list with all negative values removed. The list may thus be shorter than the original list. 5. Filter the string list to produce a new list with all NULLs removed. 6. Produce yet another list of strings that uses these two new lists of numbers and strings to truncate strings, on a pairwise basis, taking the values in the number list to be the maximum length of the entry in the string list. Recall that strings end with a null (i.e., 0) character. For example if you had these two lists l0 = [4,3,5,2,3] l1 = [“apple”, “peach”, “banana”, “grape”, “plum”] The new list of strings would be l3 = [“appl”, “pea”, “banan”, “gr”, “plu”] 7. Print this revised list of strings, one string per line. Print nothing else on each line. 8. Then join this list into a single array, separated by spaces and print it on the next line. If there are no input strings (or if all of the lengths are zero) then print the empty string (i.e., a blank line). s = “appl pea banan gr plu”; 9. Compute the maximum value in the numbers list and print it. Again; just print this number. 10. Now rid your program of memory leaks by ensuring that everything that was malloced in previous steps is freed. You must perform this step using one of the second-class list functions in list.h. Ensure that you program prints nothing other than what is specified in Steps 7-9. Question 2: Switch Statements in Assembly [10%] Examine the code for SB-switch, which you will find in the q2 subdirectory of www.ugrad.cs.ubc.ca/~cs213/cur/assignments/a8/code.zip. Carefully read the three different implementations in the C file. Run the assembly version in the simulator and observe what happens. This part is not for marks, but it will help you with the next step. The file q2.s contains uncommented assembly code that corresponds to a single C procedure starting at address 0x300 and another procedure that sets up the stack and calls the first procedure. Read this code and run it in the simulator. If you see a jump table, you might want to add labels for the addresses it stores to make the code easier to read. Comment every line and write an equivalent C program that is a likely candidate for the program the compiler used to generate this assembly file (with the exception of the stack-setup code, which is only for the .s file). Call this program q2.c. For your solution to pass the handin tests it must declare a procedure named q2 that encapsulates the code starting at address 0x300, that has the appropriate number of arguments (in the correct order), and that returns the appropriate value. To test your code, you can include a main procedure and any other procedures you like. Question 3: Jump Tables in C [45%] The file sm.c, found in the q3 subdirectory of www.ugrad.cs.ubc.ca/~cs213/cur/assignments/ a8/code.zip, is a C implementation of CPU.java; i.e., it is a sm213 virtual machine. It executes sm213 machine code, but it doesn’t include an assembler and it doesn’t have a gui. As a result, its a small C program that you should be able to read and understand. Since the C version doesn’t contain an assembler, we’ll need to use the Java version to convert assembly into machine code. To do this, run the simulator from the command line using the “- d” option. For example, to convert foo.s into machine code type the following at the UNIX command line. java -jar SimpleMachine213.jar -d foo.s The simulator places the resulting machine code in the file foo.m. The provided code.zip file contains the following programs that have already been converted to machine code; i.e., you have “.s” and “.m” versions of each of these programs. When you run the C simulator you specify which file to execute and provide zero or more of the following command line options. For example, to run foo.m and print out the registers and memory locations 0x2000-0x2007, type the following at the command line. ./sm -r -m 2000:2 foo.m Lets start by reading sm.c, seeing how cool this is, and then making a small change. simple-test A very simple test that includes only two instructions. test A test that uses every instruction (except the double-indirect jumps). a2-test The test.s file from Assignment 2 that tests ALU and memory instructions. max Compute maximum value of a list of integers. a6-q3 The Assignment 6 solution that finds the student with the median grade. -p a Set the starting pc to address a (assumed to be in hex); default is first instruction. -r Print the ending values of the register file. -m a:c Print the ending value of memory at address a, continuing for c lines (4 bytes per line). This option can be repeated to print multiple non-contiguous memory regions. Read, Understand and Modify the C Simulator [10%] Examine the fetch() and exec() procedures in sm.c. These are equivalent to the two functions in CPU.java. They execute in sequence each clock tick to fetch an instruction from memory and execute it. Read exec() carefully. Note what mem[] and reg[] are. Pause to reflect on how simple and cool this all is. This right here is all that a computer needs to do. Now, you’ll notice two TODO comments in exec(), for the two double-indirect jump instructions that you implemented in Java in Assignment 7. Implement them again, this time in C. Use the implementations of the two load instructions and the indirect jump instruction as a guide. Test your implementation by creating a small assembly test file. You might want to first test the test file in the Java version of the simulator. Make sure that your test program changes either memory or the register file in a recognizable way when the two instructions execute correctly. Then, convert this file to machine code (see above) and run it in your modified C simulator, having it print whatever memory or registers you need to confirm correctness (see above). You might need to add print statements or otherwise debug sm.c. Replace Switch Statements with Jump Tables [35%] Finally, to see how the compiler implements switch statements like those found in sm.c, copy this file to the file sm-jt.c and then modify sm-jt.c to remove all switch statements in the exec() procedure and replace them with jump tables and goto’s as described in class. Note that there are two switch statements and so you will need two jump tables. Label pointers (e.g., &&L0) and double-indirect goto’s (e.g., goto *jt[i]) are gnu-C extensions and so some compilers may not support them (all versions of gcc and llvm (the Mac compiler) do support these extension). So, you may need to move to a lab computer to test this your program. Now, test your program. Start with simple-test.m. This test uses one instruction from each of the switch statements and so if it works you’ll likely have got this mostly right. You’ll also want to use test.m to ensure that you are dispatching to the correct case block for every instruction. The easiest way to do this is to place a print statement in every case block and then run the test to ensure that every print statement executes, and the execute in the correct order. What to Hand In Use the handin program. The assignment directory is ~/cs213/a8, it should contain the following plain-text files. 1. PARTNER.txt containing your partner’s CS login id and nothing else (i.e., the 4- or 5- digit id in the form a0z1). Your partner should not submit anything. 2. For Question 1: list.c and trunc.c. 3. For Question 2: q2.s and q2.c. 4. For Question 3: sm.c and sm-jt.c.