University of California at Berkeley College of Engineering Department of Electrical Engineering and Computer Sciences Computer Science Division CS 61c J Wawrzynek Spring 2006 Machine Structures Midterm I Your Name Fect Per ID Number 999 99 999 Left Neighbor ID Right Neighbor ID This is a open book exam You are allowed to use any books and notes that you wish No calculators or electronic devices of any kind please You have 2 hours Each question is marked with its number of points This exam booklet should have 11 printed pages plus 4 blank pages at the end Check to make sure that you have all the pages Put your student ID neatly on each page Show your answers in the space provided for them Write neatly and be well organized If you need extra space to work out your answers you may use the back of previous questions or the blank sheets attached to the back of your exam booklet However only the answers appearing in the proper answer space will be graded Good luck problem maximum score 1 7pts 2 5pts 3 5pts 4 10pts 5 10pts 6 10pts 7 13pts total 60pts 1 CS61c S06 Midterm I ID 2 1 8 points Which of these unsigned numbers is largest FeedFacehex 1 point FadedAbehex DeadBeefhex or 0xFeedFace What is B0Dhex in decimal 1 point 2829 What is 337ten in hexadecimal 1 point 0x151 What is the decimal equivalent of the 6 bit two s complement number 101010two 1 point 22 Put a T true or F false in each table cell 14 point each total is rounded up 4 points unsigned sign magnitude 1 s complement 2 s complement Can represent positive numbers T T T T Can represent negative numbers F T T T Has more than one representation for 0 F T T F Uses the same addition process as unsigned T F F T CS61c S06 Midterm I ID 3 2 5 points The following program is compiled and run on a MIPS computer 1 int main 2 int i 3 int four ints 4 4 char c 5 6 for i 0 i 4 i four ints i 2 7 8 c char four ints 9 for i 0 i 4 i c i 1 10 11 printf x n four ints 2 12 What does it print out The x in printf is used print out a word in hexadecimal format 3 points 2 If we change the 2 on line 11 to a 0 then recompile and run what would be printed 2 points 1010101 CS61c S06 Midterm I ID 4 3 5 points The program below is written using the MIPS instruction set It is loaded into memory at address 0xF000000C all instruction memory addresses are shown below F000000C addi 1 1 1 F0000010 beq 1 0 done 4 0 1 1 F0000014 j loop 2 3 F0000018 loop 8 1 1 1 done For each instruction in the program write down the values in decimal of each field in the machine language version of that instruction using the following notation value value With this notation the MIPS instruction add 3 2 1 instruction would be described as 0 2 1 3 0 32 Put your answers to the right of the s CS61c S06 Midterm I ID 5 4 10 points a The following function should allocate space for a new string copy the string from the passed argument into the new string and convert every lower case character in the new string into an upper case character Fill in the blanks and the body of the for loop 7 points char upcase char str char p char result result char malloc 1 strlen str strcpy result str for p result p 0 p if p a p z p A a return result Below is table for the ASCII character codes that you might need for part b The numbers along the left and top indicate the first and second hex digits of the codes respectively 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 9 A B C D E F NUL SOH STX ETX EOT ENQ ACK BEL BS HT LF VT FF CR SO SI DLE DC1 DC2 DC3 DC4 NAK SYN ETB CAN EM SUB ESC FS GS RS US SP 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z DEL CS61c S06 Midterm I ID 6 b Consider the code below The upcase name function should convert the ith name to upper case by calling upcase by ref which should in turn call upcase Complete the implementation of upcase by ref You may not change any part of upcase name 3 points void upcase by ref char n n upcase n void upcase name char names int i upcase by ref names i CS61c S06 Midterm I ID 7 5 10 points The original MIPS processor did not support multiplication compilers were expected to break down multiplication and division into simpler operations Even on newer MIPS processors that have the MUL instruction compilers sometimes still do this to improve performance Consider the following C function int foo int x return x 257 Write the corresponding MIPS assembly code below You may not use any form of MUL Your answer should use as few a number of instructions as possible 4 points foo sll v0 a0 8 add v0 v0 a0 a0 contains x return value should be in v0 jr ra Multiplication is more difficult when neither argument is known at compile time The general procedure for achieving multiplication of two unsigned numbers is to use a series of shift and add operations think about how long hand multiplication works The following assembly code multiplies two unsigned numbers a0 and a1 leaving the result in v0 Assume that the result is sufficiently small that it fits in a single register Fill in the missing lines 6 points addi v0 zero zero clear v0 beq andi beq a1 zero done t0 a1 1 t0 zero skip if a1 0 we are done check bottom bit of a1 if it is 0 skip over the next instruction add v0 v0 a0 fill me in skip srl a1 a1 1 shift a1 to the right a0 a0 loop ra 1 fill me in repeat done sll j jr loop CS61c S06 Midterm I ID 8 6 10 points Consider the design of a new type of 16 bit processor with the following characteristics One machine word equals 16 bits 16 16 bit registers Byte addressed memory of 216 memory locations 16 different instruction opcodes some defined below Single word instruction format The table below lists a subset of instructions for this machine Your job is to devise the machine language instruction encodings Each instruction will begin …
View Full Document
Unlocking...