Spring 2017: CS 211: Final Prof. Santosh Nagarakatte May 9th 2017: 8am-11am Full Name Here: RUID: NetID: Instructions: No electronic devices allowed. Show your ID to the TA before you submit your exam. Regular Credit: 100 points Question Max Points Points 1 20 2 20 3 20 4 20 5 20 Extra Credit: 30 points (7.5% towards the final grade) Question Max Points Points 1 15 2 15 1 Problem 1: C Programming (20 points) 1. (5 points) You are implementing a hash table using chaining with linked lists where each node is of the following type. struct node{ char* key; char* value; struct node * next; }; Given that the hash table is implemented as an array of pointers to hash table nodes, implement the following hash search function to search a key in the hash table. If the key is found, the search function returns the char* value associated with the key and returns NULL otherwise. The value MAX ENTRIES is the number of buckets in the hash table. Your code should carefully handle all corner cases, should compile, and should not experience segmentation faults on any input. You can assume that the hash function is already provided in the library and has the following prototype as shown below: int hash_function(char*); struct node * hash_table[MAX_ENTRIES]; char* hash_search(char* key){ 2 2. (5 points) Write a recursive program named reverse_list to reverse a singly linked list pointed by pointer list_ptr. The function should return the pointer to the head of the reversed list. struct node{ void* data; struct node * next; }; struct node* reverse_list(struct node * list_ptr) { 3 3. (5 points) You are given a binary search tree with each node having a left and a right child. If there are no children in the left or right branch, the respective pointers are NULL. Complete the lookup C function to look up a key in the binary search tree. The function returns 1 if the key is found and returns 0 if the key is not found. /* structure for the binary search tree */ struct node{ int value; struct node* left; struct node* right; }; /* initially curr points to the root of the tree */ int lookup(struct node* root, int key){ 4 4. (5 points) Write a C function to allocate a two-dimensional integer matrix with m rows and n columns. The use of the function is shown below. int ** matrix; … matrix = allocate(p, q); .. Your task is write a function that allocates the matrix and returns the appropriate pointer and fill the return type of the function. ……. allocate (int m, int n){ 5 Problem 2: Data Representation + basic assembly 1. (5 points) You are given a 10-bit floating point representation with 1-sign bit, 3 bits for the exponent, and 6-bits for the mantissa. Express 16.875 in this representation. Clearly show work. 2. (5 points) Complete a C function below which checks if the n-th bit is 1 in the binary representation of a 64-bit number (size t data type on a 64-bit machine) The function returns 1 if the n-th bit is 1 in the number and 0 otherwise. The argument specifying the n-th bit named nbit below ranges from 0 to 62. Hint: it is likely one line of code. Explain your intuition in 2 sentences. The datatype size t is an unsigned 64-bit integer on 64-bit machines. int check_bit(size_t number, int nbit){ int condition = …. return condition; } 3. (4 points) You are creating a 6-bit representation of an integer. (a) What is the maximum value in two’s complement 6-bit integer representation? 6 (b) What is the minimum value in two’s complement 6-bit integer representation? (c) What is the maximum value in one’s complement 6-bit integer representation? (d) What is the minimum value in one’s complement 6-bit integer representation? 4. (3 points) You are given an unsigned n-bit number with value x. What is the value of the unsigned number obtained when you take the one’s complement of number x? Show your work. Clearly state your intuition. 5. (3 points) Lets say we are designing a 7-bit floating point representation with 3-exponent bits, 1-sign bit and 3-mantissa bits. • What is the bias? • What is the largest normalized value? • What is the smallest normalized value? 7 Problem 3: Assembly (20 points) 1. (8 points) Write C code for the following assembly code. foo: pushl %ebp movl %esp, %ebp movl 12(%ebp), %ecx addl 8(%ebp), %ecx movl $1, %eax movl $1, %edx cmpl $1, %ecx jle .L7 testl %ecx, %ecx jle .L6 .L8: imull %edx, %eax addl $1, %edx cmpl %edx, %ecx jge .L8 jmp .L6 .L7: .L6: popl %ebp ret .LC0: .string “%d %d” test: pushl %ebp movl %esp, %ebp subl $40, %esp leal -16(%ebp), %eax movl %eax, 12(%esp) leal -12(%ebp), %eax movl %eax, 8(%esp) movl $.LC0, 4(%esp) movl 8(%ebp), %eax movl %eax, (%esp) call sscanf movl -16(%ebp), %eax movl %eax, 4(%esp) movl -12(%ebp), %eax movl %eax, (%esp) call foo leave ret 8 2. (2 points) What mathematical function does the above program compute? What is the result of the following function call? result = test(“5 1”); 9 3. (10 points) As with the bomblab you have to devise the input to this program. There are multiple inputs that solve this phase named foo. Identify all the inputs that would defuse this phase. The function explode bomb has the same behavior as in bomblab. The function scanf is the other function used in this program. This program can be diffused without using gdb. Read the question carefully. Each input to diffuse the bomb can require multiple integers. There are multiple distinct inputs that diffuse the bomb. Show your work. .LC0: .string “%d” .text .globl foo .type foo, @function foo: pushl %ebp movl %esp, %ebp subl $40, %esp leal -12(%ebp), %eax movl %eax, 4(%esp) movl $.LC0, (%esp) call scanf movl -12(%ebp), %eax leal 1(%eax), %eax cmpl $3, %eax je .L3 cmpl $5, %eax jne .L7 jmp .L8 .L3: leal -16(%ebp), %eax movl %eax, 4(%esp) movl $.LC0, (%esp) call scanf movl -16(%ebp), %ecx leal 1(, %ecx,2), %ecx cmpl $17, %ecx je .L6 call explode_bomb .L8: leal -16(%ebp), %eax movl %eax, 4(%esp) movl $.LC0, (%esp) call scanf cmpl $19, -16(%ebp) je .L6 .L7: call explode_bomb .L6: leave ret 10 00 01 10 11 0 11 B B 0 C D A Y 2:1 decoder 0 1 Figure 1: Logic Design Problem 1 Problem 4: Logic Design (20 points) 1. (5 points) Write the expression for the circuit in Figure 1. Subsequently simplify it using the K-map. 11 2. (5 points) Simplify the following boolean expression using Karnaugh maps. A¯B¯C¯D¯ + A¯BC¯D¯ + ABC¯D¯ + A¯B¯C¯D + A¯BC¯D + ABC¯D 3. (10 points) Design an FSM that detects 1 0 1 in consecutive digits and outputs a 1 in the input stream of 0’s and 1’s. Implement the FSM using a combination of sequential and combinational logic. Clearly show your work. Draw the truth table for inputs, outputs and your states. Draw the K-map for everything. Clearly indicate how many flip flops you are going to use. Draw the final circuit with the flip flops. INPUT : 0 1 0 1 0 1 1 0 1 0 0…. OUTPUT: 0 0 0 1 0 1 0 0 1 0 0…. 12 /* Extra page for work here */ 13 Problem 5: Caches (20 points) 1. Consider a machine with a direct mapped cache that has 8-sets and has a block size of 4-bytes. Memory addresses are 13-bits and each memory access from a processor requests a byte from the cache. The contents of the cache are as follows, with all numbers in hexadecimal. Cache Line Set Index Tag Valid Byte 0 Byte 1 Byte 2 Byte 3 0 09 1 30 F4 72 AB 1 38 1 78 3F 92 D4 2 6E 0 – – – – 3 06 0 1F DA 40 C5 4 C7 1 – – – – 5 71 1 D3 9A 0B 12 6 91 1 – – – – 7 46 0 5C 80 B3 59 (a) (2 points) Calculate the size of the cache in bytes. (b) (3 points) Indicate the number of bits used to determine • the block offset: • set index: • tag: (c) (10 points) A program running on this machine makes memory references at the addresses specified in the first column of the following table. For each memory reference indicate what is the block offset, set index and tag. Furthermore, indicate whether a cache hit occurs and the byte returned. The byte returned is – for a miss. Address Set index Block offset Tag Cache hit? (Y/N) Byte returned 0x0E35 0x0DD5 0x1FE4 0x0705 14 (d) (3 points) If we redesign the cache by increasing the associativity to 4 while keeping the total cache size exactly the same as above, how
many bits will you use for the following: • Tag: • Set index: • Block offset: (e) (2 points) What is spatial locality and temporal locality? 15 A B C A B C A B C Figure 2: Examples of cycles for a linked list with 3 nodes. Extra Credit Questions Extra Credit 1: C Programming (15 points) You are given a pointer to a singly linked list. The singly linked list has cycles due to a programming error. Write a C program to detect whether the linked list has cycles without storing all the pointers to the nodes. The function detect_cycles should return 1 when a cycle is found and 0 when there are no cycles. Your code should handle all corner cases carefully and should not cause segmentation fault. Figure shows various examples of cycles for a list with 3 nodes. The number of nodes in the input list can range from 0 to a billion nodes. struct node{ void* data; struct node* next; }; int detect_cycles(struct node* list){ 16 /* another page for work */ 17 Extra Credit 2: Assembly (15 points) You are charged with maintaining a large C program and you come across the following code. typedef struct{ int left; a_struct a[CNT]; int right; } b_struct; void test(int i, b_struct *bp){ int n = bp->left + bp->right; a_struct* ap = &bp->a[i]; ap->x[ap->idx] = n; } The declaration of the compile time constant CNT and the structure a struct are in a file for which you don’t have necessary access privilege. Fortunately you have a copy of the ’.o’ version of code, which you are able to disassemble with objdump program yielding the disassembly shown below. test: pushl %ebp movl %esp, %ebp pushl %ebx movl 8(%ebp), %edx movl 12(%ebp), %eax imull $28, %edx, %ecx leal (%eax,%ecx), %ecx leal 0(,%edx,8), %ebx subl %edx, %ebx movl %ebx, %edx addl 4(%ecx), %edx movl 312(%eax), %ebx addl (%eax), %ebx addl 8(%ecx), %ebx movl %ebx, 12(%eax,%edx,4) popl %ebx popl %ebp ret Clearly show your reasoning for your answers. Using your reverse engineering skills, deduce the following: 1. The value of CNT. 18 2. A complete declaration of structure a struct. 19 /* show work here */ 20
