CS/ECE 252: Introduction to Computer EngineeringComputer Sciences DepartmentUniversity of Wisconsin, MadisonMidterm IIIProfessor David WoodFriday, April 10th 2009This exam is closed book. There is to be nothing used during the exam.There are 7 pages in this exam not counting this cover sheet. See the backpage for the LC-3 instruction set.Last Name:First Name:Section:Student ID:Question Points Score1 102 103 124 205 246 24Total: 1001. (10 points) Machine Language to Pseudo Code:Translate the binary value to pseudo code to and give the value of R3 in binary afterexecution of the code fragment. The first line is filled in for you.Binary Value Pseudo Code0101 0100 1010 0000 R2 ← R2 AND 00001 0100 1000 00101001 0110 1011 11110010 0010 0000 00001100 0000 0100 0000R3 =Solution:Binary Value Pseudo Code0101 0100 1010 0000 R2 ← R2 AND 00001 0100 1000 0010 R2 ← R2 AND R21001 0110 1011 1111 R3 ← NOT R20010 0010 0000 0000 R1 ← MEM[PC + 0]1100 0000 0100 0000 PC ← R1R3 = 1111 1111 1111 11112. (10 points) Ps eudo Code to Machine Language:Translate the pseudo co de to binary machine language and give the value of R4 in binaryafter execution of the code fragment. The first line is filled in for you.Binary Value Pseudo Code0101011011100000 R3 ← R3 AND 0R4 ← R3 + 11R5 ← PC + -1MEM[PC + 5] ← R4R4 ← R4 + R3R4 =Page 1 of 7Solution:Binary Value Pseudo Code0101011011100000 R3 ← R3 AND 00001100011101011 R4 ← R3 + 111110101111111111 R5 ← PC + -10011100000000101 MEM[PC + 5] ← R40001100011000100 R4 ← R4 + R3R4 = 0000 0000 0000 1011Page 2 of 73. (12 points) Note that there is no OR instruction in the LC-3 ISA. Complete the code sothat the following 4 instruction sequence stores the result of R1 OR R2 in the registerR3.(1):(2): 1001 1000 0111 1111(3): 0101 1101 0000 0101(4):Solution:(1): 1001 1010 1011 1111; R5 ← NOT R2(2): 1001 1000 0111 1111; R4 ← NOT R1(3): 0101 1101 0000 0101; R6 ← R4 AND R5(4): 1001 0111 1011 1111; R3 ← NOT R6Page 3 of 74. (20 points) Address ing:Let R0,R1,R2, and R3 be initialized to 0. The PC initially has value x3000. What arethe values of R0,R1,R2, and R3 when we terminate.Address Value Translationx3000 x2009 R0 ← MEM[PC + 9]x3001 xA20B R1 ← MEM[MEM[PC + 11]]x3002 xC000 PC ← R0x3003 x6448 R2 ← MEM[R1 + 8]x3004 x6647 R3 ← MEM[R1 + 7]x3005 xF025 HALTx3006 x3000 MEM[PC + 0] ← R0x3007 x3001 MEM[PC + 1] ← R0x3008 x3002 MEM[PC + 2] ← R0x3009 x3003 MEM[PC + 3] ← R0x300A x3004 MEM[PC + 4] ← R0x300B x3005 MEM[PC + 5] ← R0x300C x3006 MEM[PC + 6] ← R0x300D x3007 MEM[PC + 7] ← R0x300E x3008 MEM[PC + 8] ← R0x300F x3009 MEM[PC + 9] ← R0Solution: x3000 LD R0, #9; R0 ← MEM[x3000 + 1 + 9] = x3004x3001 LDI R1, #11; R1 ← MEM[MEM[x3001 + 1 + B]] = MEM[x3007] = x3001x3002 JMP R0x3003 LDR R2, R1, #8; R2 ← MEM[R1 + 8] = x3003 (never run)x3004 LDR R3, R1, #7; R3 ← MEM[R1 + 7] = x3002x3005 HALTx3006 x3000x3007 x3001x3008 x3002x3009 x3003x300A x3004x300B x3005x300C x3006x300D x3007x300E x3008x300F x3009Therefore R0=x3004, R1=x3000, R2 = 0, R3 = x3003Page 4 of 75. (24 points) Iteration:Everytime a register is written write the new value update the table. Updating the tableconsists of finding the registers row, and writing in hex the value that is written. Thefirst 3 entries to the table have been written for you corresponding the the first 3 lines ofthe program. Complete the partially filled table to match the execution of the program.Address Value Translationx3000 0101 0110 1110 0000 R3 ← R3 AND 0x3001 0001 0110 1110 0010 R3 ← R3 + 2x3002 0101 1011 0110 0000 R5 ← R5 AND 0x3003 0101 1001 0010 0000 R4 ← R4 AND 0x3004 0001 1001 0010 0010 R4 ← R4 + 2x3005 0001 1011 0110 0011 R5 ← R5 + 3x3006 0001 1011 0100 0011 R5 ← R5 + R3x3007 0001 1001 0011 1111 R4 ← R4 + -1x3008 0000 0011 1111 1101 BRp -3x3009 0001 0110 1111 1111 R3 ← R3 + -1x300A 0000 0011 1111 1000 BRp -8x300B 0001 1101 0110 0101 R6 ← R5 + 5x300C 1111 0000 0010 0101 HALTRegister 1st Val 2nd Val 3rd Val 4th Val 5th Val 6th Val 7th Val 8th ValR0R1R2R3 0000 0002R4R5 0000R6R7Solution:Register 1st Val 2nd Val 3rd Val 4th Val 5th Val 6th Val 7th Val 8th ValR0R1R2R3 0 2 1 0R4 0 2 1 0 0 2 1 0R5 0 3 5 7 A B CR6 17R7Page 5 of 76. (24 points) Debugging:Recall that in homework 6 we wrote a program to compare 2 numbers. The followingprogram does something similar but instead of comparing 2 numbers we compare 2strings. The two strings are stored at memory locations x4000 and x5000 and are nullterminated, that is end with x0000. You may assume that the strings are of the samelength. The program was intended to have R1 be 0 if the two strings are equal and 1otherwise. However, the program has 4 errors and does not behave as expected. Identifyand correct the errors in the code, give the address for each error and the correction inHex, and the pseudo code.Memory:Address Hex Value Translationx3000 x5260 R1 ← R1 AND 0x3001 x240C R2 ← MEM[PC + 12]x3002 x260C R3 ← MEM[PC + 12]x3003 x6880 R4 ← MEM[R2 + 0]x3004 x6A80 R5 ← MEM[R2 + 0]x3005 x0406 BRz 6x3006 x14A1 R2 ← R2 + 1x3007 x16E1 R3 ← R3 + 1x3008 x993F R4 ← NOT R4x3009 x1922 R4 ← R4 + 2x300A x1905 R4 ← R4 + R5x300B x0BF7 BRnp -9x300C x1261 R1 ← R1 + 1x300D xF025 HALTx300E x4000 JSRR R0x300F x5000 R0 ← R0 AND R0Solution:Address Hex Value Translationx3000 x5260 R1 ← R1 AND 0x3001 x240C R2 ← MEM[PC + 12]x3002 x260C R3 ← MEM[PC + 12]x3003 x6880 R4 ← MEM[R2 + 0]x3004 x6AC0 R5 ← MEM[R3 + 0]x3005 x0407 BRz 7x3006 x14A1 R2 ← R2 + 1x3007 x16E1 R3 ← R3 + 1x3008 x993F R4 ← NOT R4x3009 x1921 R4 ← R4 + 1x300A x1905 R4 ← R4 + R5x300B x05F7 BRz -9x300C x1261 R1 ← R1 + 1x300D xF025 HALTx300E x4000 JSRR R0x300F x5000 R0 ← R0 AND R0Page 6 of 7Figure 1: Instruction Set from ItCS 2nd editionA.3 The Instruction Set 525BaseR 000000DRDR SR 111111000000000000SRBaseR offset60000 trapvect80 0 0 BaseR 0000001 PCoffset11PCoffset9PCoffset9PCoffset9PCoffset9STISTRTRAP+++++++++reserved15 12 110176543210981314zn pDR SR1 1imm501010000000DR SR1 0 0 0 SR201010001 DR SR1 1imm50001 DR SR1 0 0 0 SR2DRDR11001010011011101001110010000011BaseR offset6000111 000000SR1011011111111101SR0100DR00100100PCoffset9PCoffset9BRANDADDADDANDJMPLDLDILDRLEANOTRETRTISTJSRRJSRFigure A.2Format of the entire LC-3 instruction set. Note: + indicates instructions thatmodify condition codesPage 7 of