Part I – General Knowledge (20 points total)

Directions: Provide 1 to 2 sentence answers to the following questions:

1)   Convert the following binary #: 1000001, into the following forms: ASCII: _____________

Hex: ______________

Decimal (if # is 8-bit unsigned): ______________

Decimal (if # is 8-bit signed): ________________

2)   What are the most positive and most negative #’s you can create using only 3-bits in 2C?

3)   How can one detect overflow in 2C binary addition?

4)   What does it mean for a CPU to be “single cycle”?

5)   A line from a Makefile reads:

clang program5_swap.c program5.o -o program5

6)   Draw the Von-Neumann model for a CPU

7)   Draw the model for an I/O controller for a generic device.  Briefly indicate what the various parts are meant to do.

8)   What is the difference between these two variables: my_array1 and my_array2? int my_array1 [2]

my_array1[0] = 1;

my_array1[1] = 2;

int *my_array2 = malloc (sizeof(int)*2) ;

my_array2[0] = 1 ;

my_array2[1] = 2 ;

free(my_array2) ;

9)   What is a hashtable in C?

10) What are the advantages/disadvantages of a linked list over an array in C?

Part II – CMOS and Logic

1)   (15 points) Given the following CMOS gate, answer the following questions:

 

a)   Using the inputs listed on the 4 instances of the above CMOS circuit below, replace the missing parts in the circuits below with either a wire or no wire and predict the output. Fill in the predicted output in the line next to the output Y.

b)   Create a truth table that lists all possible input combinations for the above CMOS circuit.

NOTE: your table inputs must be in binary and in ascending numeric order: 0,1,2,…

c)   Using your truth table from step (b), create a PLA that implements the truth table

d)   Write out the exact Boolean logic function expressed by your PLA.

e)   From steps (a)-(d), what logic function does this circuit actually perform?

Part III – Assembly/C

2)   (10 points) For the questions in this section, assume memory has the following contents:

Memory after code is run:
Address	Contents	Comment
X4000		x
X4001
X4002
X4003
X4004
…
X7FFC		a

In addition, this code is to be referenced in parts (a) and (b) below:

int* a = &x ;

while (*a != 0) {

a++ ;

*a=(*a)<<1 ;

}

a)   Using the code shown above and the contents of memory shown in the above table entitled: “Memory before code is run”, fill in the table labeled: “Memory after code is run.”

b)   Translate the C-code on the last page into LC4-Assembly.  You do not need to use the   stack; you may simply use R0-R7 in any way you’d like.  However, you MUST follow the algorithm exactly (while loops, shift operators, etc).  In addition, you must properly dereference pointers in Assembly (you may use the back of this page for more space).

Part IV – Strings in C

3)   (15 points) Write a C function named: “stringPig()” that takes as a parameter a C-string of     unknown length, containing a single word.  Your function should translate this string from    English into Pig Latin.  This translation is performed by removing the first letter of the string, appending it onto the end, and concatenating the letters ay.  You can assume that the array contains enough space for you to add the extra characters.

For example, if your function is passed the string “Hello” after your function returns, the string should have the value: “elloHay” .  The first character of the string should be “e” .

a)   Write the C-function with the following specifications:

•   You must determine if returning data is necessary

•   You may not call other string functions in C (like strlen or strcat as an example)

•   Your function should not crash if the string passed in is NULL.

•   You must comment your function so we can grade it!

•   You may not use malloc() or any form of dynamic memory

b)   Write a main() function that will test your stringPig() and print its output to the screen. You must ensure that your main() and stringPig() have no memory leaks upon return.

4)   (10 points) Write a C function named: “strShift()” that takes as a parameter a C-string of unknown length and an amount to shift the string by: n.  Your function should shift the  string n character’s to the left and return the result.

For example, if your function is passed the string “Hello” and n=1 after your function returns, the string should have the value: “ello” .  If n=2, after your function eturns the string should be: “llo” .

a)   Further specifications for writing the function:

•   YOU MUST USE POINTER NOTATION ONLY (no [ ] operators)

•   You must determine if returning data is necessary

•   You may not call other string functions in C (like strlen or strcat as an example)

•   Your function should not crash if the string passed in is NULL.

•   You must comment your function so we can grade it!

•   You may not use malloc() or any form of dynamic memory

b)   Write a main() function that will test your strShift () and print its output to the screen. You must ensure that your main() and strShift () have no memory leaks upon return.

Part V – Debugging in C

5)   (5 points) Assume printf() exists on the LC4 and this code is compiled using LC4’s C- Compiler:

#include <stdio.h>

int main() {

int apple ;

int *ptr ;

int **ind ;

ind = &ptr ;

*ind = &apple ;

**ind = 123 ;

ind++ ;

*ptr++;

apple++ ;

printf(“%p %p %d\n” ind, ptr, apple) ;

}

a)   Draw out the stack just after the apple++; executes.  You do not need to show the arguments, RV, RA, or FP in this listing of the stack.  You may start your stack at address: x7FFF.

b)   What will this code print out to the screen?

6)   (10 points) In the following example, you may assume malloc() always succeeds.

typedef struct customer_s {

int id ;

char* name ;

struct customer_s* next ;

} customer ;

customer* add_to_list (customer* head, int id, char* name) { customer node = malloc(sizeof(customer));

node->id = id ;

node->name = name ;

node->next = head ;

return (node);

}

void delete_list (customer* head) {

customer node = NULL ;

while (head != NULL) {

node = head ;

head = node->next ;

free (node) ;

}

}

int main() {

customer head_node ;

add_to_list (&head_node, 123, “Tom”);

add_to_list (&head_node, 456, “Bob”);

delete_list (&head_node) ;

return 0 ;

}

a)   The above code compiles, but it segfaults whenever delete_list() is called.  Explain why the segfault occurs.

b)   While the above code compiles, before delete_list() is called, the linked list never has more than 1 node.  Explain why that is the case.

c)   Fix the errors in the above code to address the problems in parts (a) and (b)

Part VI – Stack/Heap/TRAPS

7)   (20 points) The following C function was compiled with the lcc compiler to run on PennSim.

10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20 21 22 23 24

#include <stdio.h> #include <stdlib.h> #include <string.h> char* my_strdup (char* dest, char* src) { dest = malloc (strlen(src) + 1) ; strcpy (dest, src) ; return (dest) ; } int main (int argc, char** argv) { char* source = “Tom” ; char* destination = NULL ; destination = my_strdup (destination, source) ; printf (“%s\n”, destination) ; return 0 ; }

For this question, a handy reference for you will be the following table that shows the calling convention in lcc for each function’s stack frame:

Temporaries, arguments to callees

Local variables

Caller’s frame pointer

Return address

Return value

Arguments

a)   Your job is to populate the table of the LC4’s memory on the next page for the program   shown above.  The table must show the addresses (in HEX) & contents (in appropriate      format) of the global/static, stack, heap regions of memory, as well as registers: R5, and R6 right before the call to printf().  The following information will aid you in your task:

•   Assume the program is called “a.out” and executed as follows: ./a.out

•   Assume when main() was called, R5 was 0 and R6=x7FFE

•   Assume main() was called by USER_START using a JSR on line x0006.

•   Assume the line #’s you see in the C-program are the locations in program memory where the corresponding assembly is loaded.  As an example:

[1E] char* destination = NULL ;

would be loaded into program memory at address:  x001E

•   Assume stdio.h, stdlib.h, and string.h libraries exist on the LC4 and that each call to malloc() will succeed for this program.

•   Any values that cannot be determined must be marked with an X.

LC4 – Global Memory:

Address	Contents	Comment

Register	Contents
R5
R6
R7 (e.c.)

b)  There is 1 error in main(), what is it?

8)   (3.5 points) The following code shows a TRAP, a TRAP_WRAPPER, and the C-Code that calls the wrapper.  The TRAP should print out a null terminated string to the ASCII display.  There are 7 missing instructions throughout the code below.  Fill in the missing instructions right  next to the missing instruction.

--------------------FILE: os.asm------------------------------------

OS_ADSR_ADDR .UCONST xFE04 ; status reg for ASCII display OS_ADDR_ADDR .UCONST xFE06 ; control reg for ASCII display

.CODE

TRAP_PUTS

Missing Instr. 1 = _____________________________________

LDR R1, R1, #0

BRzp TRAP_PUTS   ; check to see if ASCII display is available

Missing Instr. 2 = _____________________________________

LDR R2, R0, #0   ; load character from string into R2

BRz EXIT          ; if char is NULL, exit

STR R2, R1, #0   ; write character from R2 to display

ADD R0, R0, #1   ; advance pointer to next char in string

Missing Instr. 3 = _____________________________________

EXIT

RTI

--------------------FILE: lc4_stdio.asm-----------------------------

.FALIGN

lc4_puts

;; prologue

Missing Instr. 4 = _____________________________________ Missing Instr. 5 = _____________________________________ Missing Instr. 6 = _____________________________________

ADD R5, R6, #0  ; set R5 = R6 (the new frame pointer)

;; function body

LDR R0, R5, #3  ; get arguments to TRAP_PUTS

TRAP x03         ; assume TRAP_PUTS is at x03 on vector table

;; epilogue

ADD R6, R5, #0  ; reset stack to what it was before function body

ADD R6, R6, #3  ; reduce the size of the stack

STR R7, R6, #-1 ; store return value on stack

LDR R5, R6, #-3 ; restore base pointer

LDR R7, R6, #-2 ; restore return address

RET

----------------------FILE: main.c -----------------------

void lc4_puts (char* string) ; /* function declaration for lc4_puts */

int main()

{

char my_string [] = ____________________ ; (Missing Instr. 7)

lc4_puts (my_string) /* call lc4_puts() properly */

}