====================================================== Assignment #08 - Little Man Computer Intermediate ====================================================== - Ian! D. Allen - idallen@idallen.ca - www.idallen.com 0. What is the date, time, and room of your Final Exam? Wednesday December 15 9am-11:30pm - Room P214 Basic hardware calculators *are* permitted but will not be necessary. Cell phones, PDAs, and multi-function devices are *NOT* permitted. 1. Code an LM-Assembler main program and two subroutines for the following pseudocode, using the subroutine calling conventions demonstrated in class and documented in LMC_sample7.txt - "LMC Sample Program #7 - subroutine call/return and linkage": input x input y input z output x output y output z dif = maxdif(x,y,z) output dif stop // a subroutine that uses another subroutine to // put its arguments in sorted order and then // returns the largest minus the smallest // subroutine maxdif(a,b,c){ sort(a,b,c) // arguments are call-return arguments return c-a // subtract smallest from largest } // a subroutine that puts its arguments in ascending order a<=b<=c subroutine sort(a,b,c){ // you write this pseudocode } The main program should input three numbers into local variables. Main should output the three numbers read in. Next, load the three numbers into MAXDIF subroutine argument variables (as was done in LMC_sample7), then call subroutine MAXDIF that returns in the Calculator the difference of the largest number minus the smallest number. Your code should not assume which numbers (larger or smaller) will be in which argument. Pass the three input values by copying them to argument/parameter mailboxes within the MAXDIF subroutine before you call the subroutine, as was done in LMC_sample7. Return the value from MAXDIF by putting it in the LMC Calculator. MAXDIF will use a SORT subroutine with call-return arguments that will be modified by SORT. Pass the three input values by copying them (again!) to argument/parameter mailboxes within the SORT subroutine before you call the subroutine. SORT will put the three arguments in ascending order a<=b<=c and then return. a) Give the complete detailed algorithm (pseudocode) for the sort subroutine. b) Code the full LMC program (main plus two subroutines) in LMC assembly language. Identify constants and variables. Use the pseudocode as comments to the right of the associated LMC assembly language, as done in LMC_sample6.txt and LMC_sample7.txt. (Reference: LMC_control.html) WARNING: This is one source file. Make sure that all labels are unique! You cannot have two labels with the same name and different memory locations. subroutine sort(a,b,c){ // move bigger of a,b up to b if ( a > b ) { tmp = a a = b b = tmp } // move bigger of b,c up to c - c is now LARGEST if ( b > c ) { tmp = b b = c c = tmp } // move smaller of a,b down to a - a is now SMALLEST if ( a > b ) { tmp = a a = b b = tmp } } ; all labels must be UNIQUE in this source file ; --- MAIN program ; IN ; input x STO X IN ; input y STO Y IN ; input z STO Z LDA X ; output x OUT LDA Y ; output y OUT LDA Z ; output z OUT LDA X ; dif = maxdif(x,y,z) STO A LDA Y STO B LDA Z STO C CALL MAXDIF STO DIF LDA DIF ; output dif OUT HLT ; stop X DAT ; variable Y DAT ; variable Z DAT ; variable DIF DAT ; variable ; --- MAXDIF(a,b,c) Subroutine --- A DAT ; first subroutine argument B DAT ; second subroutine argument C DAT ; third subroutine argument MAXRET DAT ; reserved for CALL return address MAXDIF LDA A ; sort(a,b,c) STO AA LDA B STO BB LDA C STO CC CALL SORT LDA CC ; return CC-AA SUB AA JMP MAXRET ; --- SORT(aa,bb,cc) Subroutine --- ; must use unique labels for three subroutine arguments AA DAT ; first subroutine argument BB DAT ; second subroutine argument CC DAT ; third subroutine argument SRTRET DAT ; reserved for CALL return address SORT LDA BB ; if ( aa > bb ) { SUB AA SKN JMP BC LDA AA ; tmp = aa STO TMP LDA BB ; aa = bb STO AA LDA TMP ; bb = tmp STO BB BC LDA CC ; if ( bb > cc ) { SUB BB SKN JMP AB LDA BB ; tmp = bb STO TMP LDA CC ; bb = cc STO BB LDA TMP ; cc = tmp STO CC AB LDA BB ; if ( aa > bb ) { SUB AA SKN JMP DONE LDA AA ; tmp = aa STO TMP LDA BB ; aa = bb STO AA LDA TMP ; bb = tmp STO BB DONE JMP SRTRET TMP DAT ; variable In the course notes you will find an LMC main program and two subroutines "Pause" and "Dble": LMC_link.html - Generation of Executable Code from Source Program Files Questions based on this web page: 2. Provide the contents of each of the three relocated external tables that would be associated with the object code for each of the three modules Main, Pause, and Dble. (That means 3 tables for each of the three modules: 9 tables in all; some of the tables may be empty.) The tables should reflect the relocated locations of the modules loaded in the given order: Main, Pause, Dble. Hint: All this information is already worked out in the web page. The whole link process involves three steps, summarized at the bottom of the above web page: 1. copying module code into memory 2. relocating the code and tables for the new memory locations 3. resolving external references using public symbols Looking at each of the three modules, we can build the nine tables using the existing tables and adding the load address offsets. MAIN loads at 00, PAUSE loads at 16, and DBLE loads at 25: MAIN (loads starting at 00, length: 16): Public Symbol Table: no public symbols given (an omission - MAIN should be defined) (if there were a "MAIN" public symbol, it would be at 00) External Reference Table: PAUSE 02 ARG 04 DBLE 05 Relocatable Instruction Table: 00, 03, 06, 07, 08, 09, 11 No changes needed to any of the tables, since MAIN loads at zero. PAUSE (loads starting at 16, length: 9): Public Symbol Table: PAUSE (01 + 16 =) 17 External Reference Table: no external references Relocatable Instruction Table: ([01, 02, 03, 05, 06] + 16 =) 17, 18, 19, 21, 22 Every location in each of the three tables has had 16 added to it. DBLE (loads starting at 25, length: 7): Public Symbol Table: ARG (00 + 25 =) 25 DBLE (02 + 25 =) 27 External Reference Table: PAUSE (05 + 25 =) 30 Relocatable Instruction Table: ([02, 03, 06] + 25 =) 27, 28, 31 Every location in each of the three tables has had 25 added to it. 3. Assuming the modules were loaded in the new order Pause, Main, Dble, (with the Pause module loading starting at location zero, followed by Main and then by the Dble module), generate the nine new relocated tables that would be associated with the object code for each of the three modules Pause, Main, and Dble. (That means 3 tables for each of the three modules: 9 tables in all; some of the tables may be empty.) The tables should reflect the relocated locations of the modules loaded in the given order: Pause, Main, Dble. (To execute the program loaded in this manner, the Little Man would have to start execution at the entry point for Main, not at zero as he usually does.) We load in the order PAUSE, MAIN, DBLE: PAUSE starts at 00 and is 9 instructions, which means MAIN loads at 09. MAIN starts at 09 and is 16 instructions, which means DBLE loads at 25. DBLE starts at 25 and is 7 instructions. Having loaded the modules in memory, the linker notes the actual memory address where each module was loaded and compares it with the memory address where the module was originally built to start. Here's a summary of where the modules were originally built to load, and where the linker actually loaded them in memory: MODULE NAME BUILT TO LOAD AT ACTUALLY LOADED STARTING AT ADDRESS ----------- ---------------- ----------------------------------- PAUSE 00 00 MAIN 00 09 DBLE 00 25 The difference is the amount by which the addresses in the module need to be relocated: Relocation Offsets for each module: PAUSE: built to start at "00", actually loaded at 00 - relocated by 00 - 00 = +00 MAIN: built to start at "00", actually loaded at 09 - relocated by 09 - 00 = +09 DBLE: built to start at "00", actually loaded at 25 - relocated by 25 - 00 = +25 Now that we have the relocation offset for each of the three modules, we can relocate all the addresses that need relocation for each module. Looking at each of the three modules, we can build the nine tables using the existing tables and adding the load address offsets. PAUSE loads at 00, MAIN loads at 09, and DBLE loads at 25: PAUSE (loads starting at 00, length: 9): Public Symbol Table: PAUSE (01 + 00 =) 01 External Reference Table: no external references Relocatable Instruction Table: ([01, 02, 03, 05, 06] + 00 =) 01, 02, 03, 05, 06 No changes needed to any of the tables, since PAUSE loads at zero. MAIN (loads starting at 09, length: 16): Public Symbol Table (after relocation): no public symbols given (an omission - MAIN should be defined) (if there were a "MAIN" public symbol, it would be at 00+09=09) External Reference Table (after relocation): PAUSE (02 + 09 =) 11 ARG (04 + 09 =) 13 DBLE (05 + 09 =) 14 Relocatable Instruction Table (after relocation): ([00, 03, 06, 07, 08, 09, 11] + 09 =) 09, 12, 15, 16, 17, 18, 20 Every location in each of the three tables has had 09 added to it. DBLE (loads starting at 25, length: 7): Public Symbol Table: ARG (00 + 25 =) 25 DBLE (02 + 25 =) 27 External Reference Table: PAUSE (05 + 25 =) 30 Relocatable Instruction Table: ([02, 03, 06] + 25 =) 27, 28, 31 Every location in each of the three tables has had 25 added to it. 4. Using the tables from the previous question, generate the relocated and linked object code for the Dble module loaded at its new address. Show the original object code of Dble (before any modifications), followed by the fully modified (relocated and linked) code for the Dble module in its new location in memory. Beside each location that has been modified, give the reason why the modification was made. Answer this question using a multi-column table: Column 1: original address Column 2: original object code before any modifications Column 3: new address in memory Column 4: new object code (fully relocated and linked) Column 5: reason for object code change (if any change) Example five-column table format for your answer: Original New Reason for change -------- ------- ------------------------------------------- 00: 107 20: 127 local reference relocated by +20 01: 000 21: 055 "CALL foo" external subroutine located at 55 02: 600 22: 600 no change ... This question usually appears on the Final Exam. We look at the three tables for DBLE (above) to know where to modify the code for DBLE. The tables tell us all we need to know. The three tables for DBLE (above) say DBLE has one External Reference to PAUSE at 30. We look up the symbol PAUSE in all the Public Symbol Tables and find it has value 01. We add 01 to location 30. The three tables for DBLE (above) say DBLE has three Relocatable Instructions at 27, 28, and 31. We add the load module offset 25 (DBLE loads at 25) to each of these three locations. Note that if we have the tables (as we would find in a pre-compiled object module) we don't need to refer to the source code. We summarize this way (as you would do on an exam): Original New Reason for change -------- ------- ------------------------------------------- 00: 000 25: 000 no change 01: 000 26: 000 no change 02: 100 27: 125 local reference relocated by +25 03: 300 28: 325 local reference relocated by +25 04: 600 29: 600 no change 05: 000 30: 001 "CALL Pause" external subroutine located at 01 06: 901 31: 926 local reference relocated by +25 -- | Ian! D. Allen - idallen@idallen.ca - Ottawa, Ontario, Canada | Home Page: http://idallen.com/ Contact Improv: http://contactimprov.ca/ | College professor (Free/Libre GNU+Linux) at: http://teaching.idallen.com/ | Defend digital freedom: http://eff.org/ and have fun: http://fools.ca/