====================================================== Assignment #07 - 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. What is the difference between a Symbol and a Label? (trick question) No difference. They are synonyms. A "Label Table" is often called a "Symbol Table". 2. What is the difference between a Public Symbol and a Global Symbol? (trick question) No difference. A Global Label is available to the linker to resolve External References, just as a Public Symbol is. 3. What is the purpose of the LMC mnemonic pseudo-instruction ORG? See the LMC_bootstrap.html example. ORG: Tell the assembler program to start putting values into the given mailbox address, starting with the next instruction or data item in the source file. 4. What is the purpose of the LMC mnemonic pseudo-instruction PUB? See the LMC_link.html example. PUB: This symbol and its memory location should be put into the Public Label Table when the module is assembled into an object file. This symbol and its address are available to other modules. 5. What is the purpose of the LMC mnemonic pseudo-instruction EXT? See the LMC_link.html example. EXT: This symbol refers to a memory address in some other module. The symbol and its location should be put into the External References Table in the object file. The linker must satisfy this reference with some Public Label address when the program is linked. 6. Code the pseudocode below 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) int x = 10 while ( x != 0 ) { output --x } LDA TEN ; x = 10 STO X WHILE LDA X ; while ( x != 0 ) SUB ZERO SKNZ JMP ENDWH LDA X ; --x SUB ONE STO X LDA X ; output x OUT JMP WHILE ENDWH HLT ZERO DAT 000 ; constant ONE DAT 001 ; constant TEN DAT 010 ; constant X DAT ; variable 7. Code the pseudocode below 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) int x input x if ( x <= 5 ) { output x } else { output 10-x } IN ; input x STO X LDA FIVE ; if ( x <= 5 ) SUB X SKP ; skip *into* body of if when positive JMP ELSE LDA X OUT JMP ENDIF ; jump around ELSE clause ELSE LDA TEN SUB X OUT ENDIF HLT FIVE DAT 005 ; constant TEN DAT 010 ; constant X DAT ; variable 8. Develop an algorithm and then code a program using LMC mnemonic code ("LM-Assembly Language") that inputs two numbers and outputs the smaller number followed by the larger number followed by the sum. Your program should not assume which number (larger or smaller) will be input first. 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) Give the algorithm (pseudocode) followed by the LMC program here: int num1 int num2 input num1 input num2 if ( num1 > num2 ) { output num2 output num1 } else { output num1 output num2 } output num1+num2 stop IN ; input n1 STO NUM1 IN ; input n2 STO NUM2 LDA NUM2 ; if ( n1 > n2 ) { SUB NUM1 SKN JMP ELSE LDA NUM2 ; output n2 OUT LDA NUM1 ; output n1 OUT JMP ENDIF ; } else { ELSE LDA NUM1 ; output n1 OUT LDA NUM2 ; output n2 OUT ENDIF LDA NUM1 ; output n1+n2 ADD NUM2 OUT HLT ; stop NUM1 DAT ; variable NUM2 DAT ; variable Subtract a mark if the code for n1+n2 appears in more than one place. 9. Develop an algorithm and then code a program using LMC mnemonic code ("LM-Assembly Language") that reads in ten input numbers (from the input slot) and produces two half-sums as output, SUMA and SUMB: SUMA - a sum of input numbers 1,3,5,7,9 SUMB - a sum of input numbers 2,4,6,8,10 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). Give the algorithm (pseudocode) followed by the LMC program here: int suma = 0 int sumb = 0 int count = 1 int limit = 10 while( count <= limit ) { input num suma = suma + num input num sumb = sumb + num count += 2 } output suma output sumb stop LDA ZERO ; suma = 0 STO SUMA LDA ZERO ; sumb = 0 STO SUMB LDA ONE ; count = 1 STO COUNT LDA TEN ; limit = 10 STO LIMIT WHILE LDA LIMIT ; while ( count <= limit ) { SUB COUNT SKP JMP ENDWH IN ; input num ADD SUMA ; suma += num STO SUMA IN ; input num ADD SUMB ; sumb += num STO SUMB LDA COUNT ; count += 2 ADD TWO STO COUNT JMP WHILE ENDWH LDA SUMA ; output suma OUT LDA SUMB ; output sumb OUT HLT ; stop ZERO DAT 000 ; constant ONE DAT 001 ; constant TWO DAT 002 ; constant TEN DAT 010 ; constant SUMA DAT ; variable SUMB DAT ; variable COUNT DAT ; variable LIMIT DAT ; variable 10. Identify the four components of an "Object" file and describe the purpose of each component in your own words. From 370_LMC_link.html "Object File Format": 0. machine code instructions (the program itself) 1. a Public label table containing a list of all Public Labels defined within the module, and their corresponding mailbox (memory) addresses. "Public" labels are labels that should be made available to other modules. All other labels are private, local labels that are not visible to other modules. 2. an External Reference table containing a list of all memory addresses that make references to "public" labels defined in other modules, plus the name of the actual label being referenced. 3. a Relocation Address table containing a list of all the addresses containing instructions that include address references to addresses within the module (based on the false assumption that the module would be loaded starting at address 00). All relocatable memory address references will need to be adjusted to reflect the true memory address values once the true starting address of the module has been established by the linker. Read these explanations. Put them away. Now, write your own words. 11. In your own words, explain how a "linker" program uses the relocatable address list, the public (or "global") label definition table, and the external reference table (all from within a collection of object files) to generate an "executable" version of a program. Version 1 (Ian!): The linker reads the object files and places all the machine code for all the modules into memory, one after the other, noting the start location of each module in memory. This start location is the "relocation offset" that has to be used to relocate addresses within the module. The linker "relocates" the addresses in all the tables that accompany all the modules loaded - three tables for each module. Now, all three tables correctly refer to address locations within the relocated modules in memory. The linker matches up all External References with the Public Label tables, plugging in the actual (relocated) addresses of the external modules into the machine code at the location specified by the External Reference table. Any External Reference that can't find a corresponding Public Label causes a link-time error. The linker uses the Relocation Address tables in all the modules to relocate all the relocatable addresses in the code within each module. Now, the code refers to the correct memory locations. The resulting "linked" code is saved as an executable binary program. Version 2 (Alan Pinck): All addresses in the relocatable address list contain instructions or data which refers to addresses within the object file (assuming the object file were to be loaded at address 0000); all such address references must be adjusted by the actual address where the object file will be loaded. The public/global definition table provides a list of labels which may be referenced by instructions in other object files, plus the address (within this object file) which corresponds to this label. The linker uses this information to replace references in other object files with the correct address within this object file. The external reference table provides a list of labels which are not defined within the current object file plus the location where the reference occurs (the same label may occur more than once in this table). The linker uses this table to determine which locations need to be modified with addresses from the public/global table. Read these explanations. Put them away. Now, write your own words. -- | 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/