CS2200- Homework 2 Solved

Assembly Programming Introduction
In this problem, you will be introduced to the 16 bit LC (Little Computer) 2200 assembly language. You will learn the syntax and semantics that underlie each of the supported operations. Although our instruction set is not as extensive as MIPS (Microprocessor without Interlocked Pipeline Stages) or x86, it is still able to solve a multitude of problems. In a LC-2200 computer, the word size is two bytes (16 bits), and there are 16 registers. We restrict memory to be addressable by words.
Register Conventions
Although the registers are for general-purpose use, we shall place restrictions on their use for the sake of convention and all that is good on this earth. Here is a table of their names and uses:
Table 1: Registers and their Uses
 
Register Number Name Use Callee Save?
0 $zero Always Zero NA
1 $at Reserved for the Assembler NA
2 $v0 Return Value No
3 $a0 Argument 1 No
4 $a1 Argument 2 No
5 $a2 Argument 3 No
6 $t0 Temporary Variable No
7 $t1 Temporary Variable No
8 $t2 Temporary Variable No
9 $s0 Saved Register Yes
10 $s1 Saved Register Yes
11 $s2 Saved Register Yes
12 $k0 Reserved for OS and Traps NA
13 $sp Stack Pointer NA
14 $fp Frame Pointer Yes
15 $ra Return Address No
 
Register 0 This register is always read as zero. Any values written to it are discarded.
 
Register 1 is a general purpose register, you should not use it because the assembler will use it in processing pseudo-instructions.
 
Register 2 is where you should store any returned value from a subroutine call.
 
Registers 3 to 5 are used to pass arguments into subroutines.
 
Registers 6 to 8 are used to store temporary values. Note that registers 2 through 8 should be placed on the stack if the caller wants to retain those values. These registers are fair game for the callee (the subroutine) to trash.
 
Registers 9 to 11 are the saved registers. The caller may assume that these registers are never tampered with by the subroutine. If the subroutine needs these registers, then it should palce them on the stack and restore them before they jump back to the caller’s code.
 
Register 12 is used to handle interrupts (something we’ll get to in a few weeks).
 
Register 13 is your anchor on the stack. It keeps track of the top of the activation record for some subroutine.
 
Register 14 is used to point to the first address on the activation record for the currently executing process. You do not need to worry about using this register.
 
Register 15 is used to store the address a subroutine should return to when it is finished executing. It is only supposed to be used by the JALR (Jump And Link Register) command.
 
Instruction Formats
There are four types of instructions: R-Type (Register Type), I-Type (Immediate value Type), J-Type (Jump Type), and S-Type (Special Type).
Here is the instruction format for R-Type instructions (ADD, NAND):
Bits 15 - 13 12 - 9 8 - 5 4 - 1 0
Purpose opcode RX RY RZ Unused
Here is the instruction format for I-Type instructions (ADDI, LW, SW, BEQ):
Bits 15 - 13 12 - 9 8 - 5 4 - 0
Purpose opcode RX RY 2’s Complement Offset
Here is the instruction format for J-Type instructions (JALR):
Bits 15 - 13 12 - 9 8 - 5 4 - 0
Purpose opcode RX RY Unused (all 0s)
Here is the instruction format for S-Type instructions (HALT):
Bits 15 - 13 12 - 0
Purpose opcode Unused (all 0s)
Symbolic instructions follow the same layout. That is, the order of the registers and offset fields align with the order given in the instruction format, ie. instructions in assembly are written as:
instruction RX, RY, RZ or instruction RX, [optional offset](RY).
Table 2: Assembly Language Instruction Descriptions
 
Name Type Syntax Opcode Action
add R add RX, RY, RZ 000 Add contents of RY with the contents of RZ and store the result in RX.
nand R nand RX, RY, RZ 001 NAND contents of RY with the contents of RZ and store the result in RX.
addi I addi RX, RY, immval5 010 Add contents of RY to the contents of the immval5 field and store the result in RX.
lw I lw RX, offset5(RY) 011 Load RX from memory. The memory address is formed by adding the offset to the contents of RY.
sw I sw RX, offset5(RY) 100 Store RX into memory. The memory address is formed by adding the offset to the contents of RY.
beq I beq RX, RY, target 101 Compare the contents of RX and RY. If they are the same, then branch to address PC + 1 + offset, where PC is the address of the beq instruction. Memory is word addressed. Note that if you use a label in a BEQ instruction, it will jump to the relative offset of the label. If you specify a label, the assembler will calculate the offset for you.
jalr J jalr RX, RY 110 First store PC + 1 in RY, where PC is the address of the jalr instruciton. Then branch to the address in RX. If RX = RY, then the processor will store PC + 1 into RY and end up branching to PC + 1.
halt S halt 111 Halts the processor and discontinues executing further instructions.
LC 2200 provides a number of pseudo-instructions.
Table 3: Assembly Language Pseudo-Instructions
 
Name Example Action
la la $a0, MyLabel Loads the address of a label into a register.
noop noop No operation, does nothing. It actually does add $zero, $zero, $zero.
.word .word 32, .word MyLabel Fills the memory location it is located with a given value or the address of the label.
Play around with the simulator. Try writing some simple programs to copy values from one register to another or to load/store values from memory. You should get familiar with the syntax for the assembler.
When you extract the archive, you will have access to an assembler (assembler.py), a python file that defines the ISA for the assembler (lc2200hw1-isa.py), and a simulator (lc2200hw1-sim.py). The assembler and simulator run on any version of Python 2.6+. Here is the suggested workflow for writing and running your assembly programs on the simulator:
1. Edit and save your assembly file with your favorite text editor.
2. Assemble your code via the assembler. The command below will generate a file called myFile.bin by using a myFile.s assembly file and the ISA for this homework:
python assembler.py -i lc2200_16-isa --sym myFile.s
3. You can run your .bin file with the simulator by typing python lc2200_16-sim.py myFile.bin. Some useful commands are ‘r’ for run, ‘q’ for quit, ‘break [line # or label]’, and ‘help’. 
Exercise: Fibonacci Test Program
In this problem, you have to use the LC 2200 assembly language to write a simple program.
Write a function in LC-2200 to compute fibonacci(num). Your implementation must be recursive and follow the LC-2200 calling convention introduced in lecture. For a review of the calling convention, see the “LC-2200 Calling Convention” slides under Resources on T-Square.
You may find the following pseudocode helpful:
fibonacci(n) = fibonacci(n− 1) + fibonacci(n− 2) fibonacci(0) = 0 and fibonacci(1) = 1
Purely iterative implementations will receive no credit. Points will be deducted for not following the calling convention correctly.
NOTE: Your function should work for any n≥ 0. You do not have to handle detecting integer overflow. When your program exits, the result should be in the $v0 register.
Hints
• We recommend starting with a solution in a higher level language such as C, and then moving to assembly.
• Comment your code. Assembly is hard to read, and comments aid in debugging while providing clarity.
• When you make a recursive call, you will have to overwrite the current arguments stored in the $a0-$a2 registers. If you need to access those again, you can either (1) treat them like $t registers and push them to the stack, or (2) copy the arguments into local variables or $s registers.