MIPS Assembly Language Programming: Lesson #1

MIPS Assembly Language
Programming
Bob Britton, Instructor
Lesson #1
Required Background
Preparation
Two semesters of programming experience
Benefits of Studying Assembly
Language Programming
Obtain Insights into writing more efficient code
Will become familiar with what compilers do
Acquire an understanding of how computers are built
Open new opportunities in the field of embedded

processors
Course Description
Basic computer organization concepts such as
registers, the ALU, data path, and random
access memory (RAM).
The use of pseudocode to develop and
document algorithms at the register level.
Number systems and the rules for arithmetic.
Passing parameter to functions using the stack.
Assemblers and linking editors.
Modular program design and development.
Introduction
• Basic Computer Organization
• Machine Language
• Assembly Language
MIPS
MIPS
PowerPC
MIPS Computer Organization
• Datapath Diagram
• Control Logic
DataPath Diagram
Program Counter (PC)
Cache Memory
Instruction Register
Out ALU
Control
Rs
Address Logic
Rt
Rd
Data In 4
Register File
Number Value Name
Register
0 $zero
1 $at
2 $v0 Return values
File 3
5
$v1
$a0
$a1
from functions
Pass parameters
6 $a2
to functions
7 $a3
8 $t0
9 $t1
Caller Saved
10 $t2
Registers –
11 $t3
Use these registers
12 $t4
in functions
13 $t5
14 $t6
15 $t7
16 $s0
17 $s1 Callee-Saved
18 $s2 Registers –
19 $s3 Use these registers for values
20 $s4 that must be maintained
21 $s5 across function calls.
22 $s6
23 $s7
24 $t8
An Example MIPS Assembly
Language Program
Label Op-Code Dest. S1, S2 Comments
move $a0, $0 # $a0 = 0
li $t0, 99 # $t0 = 99
loop:
add $a0, $a0, $t0 # $a0 = $a0 + $t0
addi $t0, $t0, -1 # $t0 = $t0 - 1
bnez $t0, loop # if ($t0 != zero) branch to loop
li $v0, 1 # Print the value in $a0
syscall
li $v0, 10 # Terminate Program Run
syscall
Three Instruction Word Formats
• Register Format
Op-Code
Op-Code Rs
Rs Rt
Rt Rd
Rd Code
Code
6 5 5 5 6
• Immediate Format
Op-Code
Op-Code Rs
Rs Rt
Rt 16--Bit
16 Bit Immediate
ImmediateValue
Value
6 5 5 16
• Jump Format
Op-Code
Op-Code 26Bit
26 BitCurrent
CurrentSegment
SegmentAddress
Address
6 26
Main Memory Program Counter (PC)
4
Address Instruction Register (IR)

0 13 0 4 0 0 Op-Code Rs Rt Rd Immediate
4 13 0 8 0 9 13 0 8 0 9
8 0 4 8 4 32
12 5 8 0 0 -1 Address name
16 5 8 0 0 -3 0 0 $zero
20 13 0 2 0 1 1 60 $at
24 0 0 0 0 12 2 8 $v0
28 0 0 0 0 0 3 0 $v1
32 3 4 5 4 0 Control 4 17 $a0 ALU
Logic
36 6 3 7 1 2 5 0 $a1
40 0 0 0 0 0 6 8890 $a2
44 0 0 0 0 0 7 349 $a3 Rs
48 0 0 0 0 0 8 7 $t0 0
52 0 0 0 0 0 9 1 $t1
56 6 9 5 3 0 10 -1 $t2
60 0 0 0 0 456 11 0 $t3
64 0 0 0 0 2345 12 777 $t4
68 0 0 0 0 890 13 -777 $t5
72 0 0 0 0 -234 14 21 $t6
76 0 0 0 0 67 15 17 $t7
80 0 0 0 0 -111 16 -349 $s0
84 0 0 0 0 6612 17 66 $s1
88 0 0 0 0 4563 18 78 $s2
92 0 0 0 0 0 19 98 $s3
96 0 0 0 0 -1 20 34 $s4
100 0 0 0 0 -223 21 12 $s5
104 0 0 0 0 4567 22 56 $s6 Rt
108 0 0 0 0 -36 23 123456 $s7 7
112 0 0 0 0 1 24 89999 $t8 4
116 0 0 0 0 3 25 -345678 $t9
120 0 0 0 0 2 26 $k0
124 0 0 0 0 -36 26 $k1
128 0 0 0 0 23 28 $gp
132 0 0 0 0 -99 29 400000 $sp
……… 0 0 0 0 0 30 $fp
1,087,418,233 0 0 0 0 0 31 48 $ra
ALU-OUT
7
Reg. File
A Register Transfer Description
of the Control Logic
IR = Mem[PC]
PC = PC + 4
Decode Instruction
lw or sw beqz
Read from Reg. File
Address = Rs + Offset
R-Type
If (Rs == 0 ) then
sw PC = PC + Offset
Memory[Address] = Rt
lw
Reg. File[Rt] = Memory[Address]

Reg. File[Rd] = Rs operation Rt
MIPS Instruction Set
See Appendix C in the textbook for a detailed
description of every instruction.
• Arithmetic, Logic, and Shifting Instructions

• Conditional Branch Instructions
• Load and Store Instructions
• Function Call Instructions
Pseudo Instructions †
• Load Address la $s0, table
• Load Immediate li $v0, 10
• Move move $t8, $sp
• Multiply mul $t2, $a0, $a1
• Divide div $s1, $v1, $t7
• Remainder rem $s2, $v1, $t7
• Negate neg $s0, $s0
MIPS Register File
Register Naming Convention
(See Figure 1.2 on Page 4)
$0 : Constant Zero
$v0 : Returned values from functions
$a0 : Arguments passed to functions
$t0 : Temporary registers (functions)
$s0 : Saved registers (main program)
$sp : Stack Pointer
$ra : Return address
Programming
Lesson #2
Exercises – Chapter 1
1.1 Explain the difference between a register and the ALU.
1.2 Explain the difference between Assembly Language and Machine Language.
1.3 Explain the difference between Cache Memory and the Register File.
1.4 Explain the difference between the Instruction Register and the Program Counter.
1.5 Explain the difference between a Buss and a control line.
1.6 Identify a kitchen appliance that contains a finite state machine.
1.7 If a 500 MHz machine takes one-clock cycle to fetch and execute an instruction, then
what is the instruction execution rate of the machine?
1.8 How many instructions could the above machine execute in one minute?
1.9 Let’s suppose we have a 40-year-old computer that has an instruction execution rate
of one thousand instructions per second. How long would it take in days, hours, and
minutes, to execute the same number of instructions that you derived for the 500 MHz
machine?
1.10 What is an algorithm?
Programming
Lesson #3
Pseudocode
Using Pseudocode to Document a MIPS Assembly Language Program
When documenting an algorithm in a language
such as Pascal or C, programmers use descriptive
variable names such as: speed, volume, size,
count, amount, etc. After the program is compiled,
these variable names correspond to memory
locations. To efficiently execute code, a compiler
will attempt to keep the variables that are
referenced most often in processor registers
because access to a variable in a processor
register is much faster than access to memory.
MIPS has 32 processor registers. The names used
to reference these registers are defined in Figure
2.1 on page 4 in the textbook.
As an assembly language programmer you must take
maximum advantage of the processor registers.
For example, you may have a value in register $s0
corresponding to speed, a value in register $s1
corresponding to volume, a value in register $s2
corresponding to size, and a value in register $t3
corresponding to count.
When using pseudocode to document an assembly

language program, you will be expected to use the
names of the registers you intend to use in the
assembly language code. It is advisable to create a
cross reference
table between the processor register name and what
it is being used for in the program .
We use register names in pseudocode because
the purpose of the pseudocode is to document an
assembly language program.
Unless you identify the registers being used, the
pseudocode is quite limited in terms of having any
correspondence to the assembly language code.
You will also find that as soon as you are able to
develop the pseudocode in this format it is a very
simple process to translate pseudocode into
assembly language code.
Pseudocode for assembly language programs will
have the appearance of Pascal or C in terms of
control structures and arithmetic expressions, but
descriptive variable names will usually only
appear in the LOAD ADDRESS (la) instruction
where there is a reference to a symbolic memory
address. In assembly language you define and
allocate space for variables in the data segment
of memory using assembler directives such as
.word and .space. You will find that all of the
MIPS instructions require the use of processor
registers. When writing pseudocode you should
specify the processor registers you are planning
to use to accomplish the task.
Now for an example, let us suppose that we want to write an assembly
language program to find the sum of the integers from 1 to N.
In other words do the following: 1 + 2 + 3 + 4 + 5 + 6 + 7 + ....+ N,
where “N” is an input value.
On the next slide you will see a pseudocode description of the algorithm
and following that the corresponding assembly language program, where
processor register $t0 is used to accumulate the sum, and processor
register $v0 is used as a loop counter.
Use a word processor to create the following program file.

Be sure to save as text only.
Next, load the program into SPIM. Run the program and experiment with
the different features of the MIPS simulator. ( For example: Single Step)
Read the help file for a description of how to use the simulator.
An Example MIPS Program
# Program #1 : (descriptive name) Programmer: YOUR NAME
# Due Date : Sep. 13, 2001 Course: CSCI 51A
# Last Modified: Sep. 12, 2001 Section: 2
#########################################################
# Functional Description: Find the sum of the integers from 1 to N where
# N is a value input from the keyboard.
#########################################################
# Algorithmic Description in Pseudocode:
# main: v0 << value read from the keyboard (syscall 4)
# if (v0 < = 0 ) stop
# t0 = 0; # t0 is used to accumulate the sum
# While (v0 >= 0) { t0 = t0 + v0; v0 = v0 - 1}
# Output to monitor syscall(1) << t0; goto main
##########################################################
# Register Usage: $t0 is used to accumulate the sum
# $v0 the loop counter, counts down to zero
##########################################################
.data
prompt: .asciiz "\n\n Please Input a value for N = "
result: .asciiz " The sum of the integers from 1 to N is "
bye: .asciiz "\n **** Adios Amigo - Have a good day **** "
.globl main
.text
main: li $v0, 4 # system call code for print_str
la $a0, prompt # load address of prompt into a0
syscall # print the prompt message
li $v0, 5 # system call code for read_int
syscall # reads a value of N into v0
blez $v0, done # if ( v0 < = 0 ) go to done
li $t0, 0 # clear $t0 to zero
loop: add $t0, $t0, $v0 # sum of integers in register $t0
addi $v0, $v0, -1 # summing in reverse order
bnez $v0, loop # branch to loop if $v0 is !=
zero
li $v0, 4 # system call code for print_str
la $a0, result # load address of message into $a0
syscall # print the string
li $v0, 1 # system call code for print_int
move $a0, $t0 # a0 = $t0
syscall # prints the value in register $a0
b main
done: li $v0, 4 # system call code for print_str
la $a0, bye # load address of msg. into $a0
li $v0, 10 # terminate program

syscall # return control to
system
MUST HAVE A BLANK LINE AT THE END OF THE TEXT FILE

Input/Output System Calls
See Appendix A
$v0
Service Call Code Arguments Results
Print_integer 1 $a0 = integer
Print_ string 4 $a0 = &string
Read_integer 5 $v0= integer
Read_string 8 $a0 = &buffer
$a1 = Length of buffer
Exit 10
Translation of “if – then -- else”
if ($t8 < 0) then
{$s0 = 0 - $t8;
$t1 = $t1 +1}
else
{$s0 = $t8;
$t2 = $t2 + 1}

Translation of pseudocode to MIPS assembly language. In MIPS assembly language, anything
on a line following the number sign (#) is a comment. Notice how the comments in the code
below help to make the connection back to the original pseudocode.
bgez $t8, else # if ($t8 is > or = zero) branch to else
sub $s0, $zero, $t8 # $s0 gets the negative of $t8
addi $t1, $t1, 1 # increment $t1 by 1
b next # branch around the else code
else:
ori $s0, $t8, 0 # $s0 gets a copy of $t8
addi $t2, $t2, 1 # increment $t2 by 1
next:
Translation of a “While” statement
$v0 = 1
While ($a1 < $a2) do
{$t1 = mem[$a1];
$t2 = mem[$a2];
If ($t1 != $t2) go to break;
$a1 = $a1 +1;
$a2 = $a2 –1;}
return
break: $v0 = 0
return
Here is a translation of the above “while” pseudocode into MIPS assembly language code.
li $v0, 1 # Load $v0 with the value 1
loop:
bgeu $a1, $a2, done # If( $a1 >= $a2) Branch to done
lb $t1, 0($a1) # Load a Byte: $t1 = mem[$a1 + 0]
lb $t2, 0($a2) # Load a Byte: $t2 = mem[$a2 + 0]
bne $t1, $t2, break # If ($t1 != $t2) Branch to break
addi $a1, $a1, 1 # $a1 = $a1 + 1
addi $a2, $a2, -1 # $a2 = $a2 - 1
b loop # Branch to loop
break:
li $v0, 0 # Load $v0 with the value 0
done:
Translation of a “for loop”
$a0 = 0;
For ( $t0 =10; $t0 > 0; $t0 = $t0 -1) do {$a0 = $a0 + $t0}
The following is a translation of the above “for-loop” pseudocode
to MIPS assembly language code.
li $a0, 0 # $a0 = 0
li $t0, 10 # Initialize loop counter to 10
loop:
add $a0, $a0, $t0
addi $t0, $t0, -1 # Decrement loop counter
bgtz $t0, loop # If ($t0 >0) Branch to loop
Programming
Lesson #4
Translation of a “switch statement”
Pseudocode Description:
$s0 = 32;
top: cout << “Input a value from 1 to 3”
cin >> $v0
switch($v0)
{
case(1): { $s0 = $s0 << 1; break}
case(2): { $s0 = $s0 << 2; break}
case(3): { $s0 = $s0 << 3; break}
default: goto top ;
}
cout <<$s0
“switch statement” continued
.data
.align 2
jumptable: .word top, case1, case2, case3
prompt: .asciiz "\n\n Input a value N from 1 to 3: "
result: .asciiz " The value 32 shifted left by N bits is now = "
.text
main:
li $s0, 32
top:
li $v0, 4 # Code to print a string
la $a0, prompt
syscall
li $v0, 5 # Code to read an integer
syscall
bltz $v0, exit
beqz $v0, top # Default for less than one
li $t3, 3
bgt $v0, $t3, top # Default for greater than 3
la $a1, jumptable
sll $t0, $v0, 2 # Create a word offset
add $t1, $a1, $t0 # Form a pointer into jumptable
lw $t2, 0($t1) # Load an address from jumptable
jr $t2 # Go to specific case
“switch statement”
continued
case1:
sll $s0, $s0, 1
b done
case2:
sll $s0, $s0, 2
b done
case3:
sll $s0, $s0, 3
done:
li $v0, 4 # Code to print a string
la $a0, result
syscall
li $v0, 1 # Code to print a value
move $a0, $s0
syscall
bgez $s1, main
exit:
li $v0, 10
syscall

2.1 Using Appendix A, translate each of the following pseudocode expressions

into MIPS assembly language:
(a) t3 = t4 + t5 – t6;
(b) s3 = t2 / (s1 – 54321);
(c) sp = sp – 16;
(d) cout << t3;
(e) cin >> t0;
(f) a0 = &array;
(g) t8 = Mem(a0);
(h) Mem(a0+ 16) = 32768;
(i) cout << “Hello World”;
(j) If (t0 < 0) then t7 = 0 – t0 else t7 = t0;
(k) while ( t0 != 0) { s1 = s1 + t0; t2 = t2 + 4; t0 = Mem(t2) };
(l) for ( t1 = 99; t1 > 0; t1=t1 -1) v0 = v0 + t1;
Solutions to Chap 2 Exercises
label op-code Rd, Rs, Rt
E1a: add $t3, $t4, $t5
sub $t3, $t3, $t6
E1b: addi $s3, $s1, 54321
div $t2, $s3
mflo $s3
E1c: addi $sp, $sp, -16
E1d: move $a0, $t3
li $v0, 1
syscall
E1e: li $v0, 5
syscall
move $t0, $v0
Solutions to Chap 2 Exercises
label op-code Rd, Rs, Rt
E1f: la $t0, array
lw $a0, 0($t0)
E1g:
E1h:
E1i:
E1j:
(m) t0 = 2147483647 - 2147483648;
(n) s0 = -1 * s0;
(o) s1 = s1 * a0;
(p) s2 = srt(s02 + 56) / a3;
(q) s3 = s1 - s2 / s3;
(r) s4 = s4 * 8;
(s) s5 =  * s5;
2.2 Analyze the assembly language code that you developed for each of the
above pseudocode expressions and calculate the number of clock cycles
required to fetch and execute the code corresponding to each expression. (Assume it
takes one clock cycle to fetch and execute every instruction except multiply and
divide, which require 32 clock cycles and 38 clock cycles respectively.)
2.3 Show how the following expression can be evaluated in MIPS assembly
language, without modifying the contents of the “s” registers:
$t0 = ( $s1 - $s0 / $s2) * $s4 ;
Exercises Continued
2.2 Analyze the assembly language code that you developed for each of the
above pseudocode expressions and calculate the number of clock cycles
required to fetch and execute the code corresponding to each expression.
(Assume it takes one clock cycle to fetch and execute every instruction
except multiply and divide, which require 32 clock cycles and 38 clock
cycles respectively.)
$t0 = ( $s1 - $s0 / $s2) * $s4 ;
Programming
Lesson #5
MIPS
MIPS
Three Instruction Word Formats
• Register Format
Op-Code
Op-Code Rs
Rs Rt
Rt Rd
Rd Code
Code
6 5 5 5 6
• Immediate Format
Op-Code
Op-Code Rs
Rs Rt
Rt 16--Bit
16 Bit Immediate
ImmediateValue
Value
6 5 5 16
• Jump Format
Op-Code
Op-Code 26Bit
26 BitCurrent
CurrentSegment
SegmentAddress
Address
6 26
A Register Transfer Description
of the Control Logic
IR = Mem[PC]
PC = PC + 4
Decode Instruction
lw or sw beqz
Read from Reg. File
Address = Rs + Offset
R-Type
If (Rs == 0 ) then
sw PC = PC + Offset
Memory[Address] = Rt
lw
Reg. File[Rt] = Memory[Address]

Reg. File[Rd] = Rs operation Rt
An Example MIPS Assembly
Language Program
move $a0, $0 # $a0 = 0
li $t0, 99 # $t0 = 99
loop:
add $a0, $a0, $t0 # $a0 = $a0 + $t0
addi $t0, $t0, -1 # $t0 = $t0 - 1
bnez $t0, loop # if ($t0 != zero) branch to loop
li $v0, 1 # Print the value in $a0
syscall
li $v0, 10 # Terminate Program Run
syscall
Number Systems
• Introduction
• Polynomial Expansion
• Binary Numbers
• Hexadecimal Numbers
• Two’s Complement Number System
• Arithmetic & Overflow Detection
• American Standard Code for Information
Interchange (ASCII)
Polynomial Expansion of a Decimal Number (Base 10)
2 1 0
496 = 4 x 10 + 9 x 10 + 6 x 10
10
Polynomial Expansion of a Binary Number (Base 2)

5 4 3 2 1 0
00101101 = 1 x 2 + 0 x 2 + 1 x 2 + 1 x 2 + 0 x 2 + 1x 2
2
A Faster Method ------ Double and Add
00101101 = 45 (1, 2, 5, 11, 22, 45)

Conversion of Decimal Numbers to Binary
Divide by 2 and record the remainder
45 Remainder 101101
22 1
11 0
5 1
2 1
1 0
0 1
Practice - Convert 25 to Binary
Divide by 2 and record the remainder
25 Remainder
12
To represent binary values in the positive
and negative domains we use the
Two’s Complement Number System
Here is the polynomial expansion of a two’s
complement number 8-bit binary number N:
N= - d7x2 + d6x2 + d5x2 + d4x2 + d3x2 + d2x2 + d1x2 +d0x2

7 6 5 4 3 2 1 0
Notice the Minus sign
*** You need to memorize powers of 2 ***

The Two’s Complement Operation
When we take the two’s complement of a binary number,
the result will be the negative of the value we started with.
For example, the binary value 00011010 is 26 in decimal.
To find the value minus 26 in binary we perform the

two’s complement operation on 00011010.
Scan the binary number from right to left leaving all least significant
zeros (0) and the first one (1) unchanged, and then complementing the
remaining digits to the left: 11100110
The result is the value minus 26 in binary.

Binary Arithmetic & Overflow Detection
in the Two’s Complement Number System
Here is an addition example where we assume we
are limited to 8 binary digits.
01000100 = 68
+ 00111100 = 60
10000000 = -128 Overflow Occurred
Overflow
0000
1111 0001
0
1110 -1 1 0010
-2 2
0011
1101 3
-3
1100 -4 4 0100
-5
1011 5
-6 0101
6
1010 -7 7
-8 0110
0111
1001
1000
Binary Arithmetic
in the Two’s Complement Number System
Here is a subtraction example where we assume
we are limited to 8 binary digits. To subtract in
binary we always add the two’s complement of the
subtrahend.
01000100 = 01000100 68
-00111100 = +11000100 60
00001000 = 00001000 = 8
The Rule for
Detection of Overflow
#################################################
Adding numbers of opposite signs, overflow is impossible.
When adding numbers of the same sign, if the result is not the
same as the operands then overflow occurred.
#################################################
Here is an example:
You are given the following two numbers in two’s complement representation.
Perform the binary subtraction and indicate if there is signed overflow.
______
Explain Why: 11101000 = -24
11101000 +11101101 = -19
-00010011 11010101 Correct
Result = -43
Sign Extension
The value –43 as an 8-bit binary number is: 11010101
The value –43 as an 32-bit binary number is:
11111111111111111111111111010101
In Hexadecimal –43 appears as: 0xFFFFFFD5
###############################################
The value 68 as an 8-bit binary number is: 01000100

The value 68 as an 32-bit binary number is:
00000000000000000000000001000100
In Hexadecimal 68 appears as: 0x00000044
The Hexadecimal Number System
Decimal Hex Binary
0 0 0000
1 1 0001
2 2 0010
Here is an example of how we
3 3 0011 compactly represent binary
4 4 0100 numbers in hexadecimal:
5 5 0101 | | | | |
6 6 0110
001111001000111101111110
7 7 0111
8
9
8
9
1000
1001
0x 3 C 8 F 7 E
10 A 1010
11 B 1011
12 C 1100
13 D 1101
14 E 1110
15 F 1111
Programming
Lesson #6
Chapter 2 Exercises Continued
$t0 = ( $s1 - $s0 / $s2) * $s4 ;
2.4 The datapath diagram for the MIPS architecture shown in figure 1.1
with only one memory module is referred to as a von Neumann architecture.
Most implementations of the MIPS architecture use a Harvard Architecture,
where there are two separate memory modules, one for instructions and
the the other for data. Draw such a datapath diagram.
2.5 Show how the following pseudocode expression can be efficiently evaluated
in MIPS assembly language, without modifying the contents of the “s”
registers:
$t0 = ( $s0 / 8 - 2 * $s1 + $s2 ;
Solution to Exercises 2.3 & 2.5
Clock Cycles
E2.3 div $s0, $s2 38
mflo $t0 1
sub $t0, $s1, $t0 1
mult $t0, $s4 32
mflo $t0 1
Total= 73
E2.5 sra $t0, $s0, 3 1

sll $t1, $s1, 1 1
sub $t0, $t0, $t1 1
add $t0, $t0, $s2 1
Total= 4
Exercises
3.1 Convert the decimal number 35 to an 8-bit binary number.
00100011
3.2 Convert the decimal number 32 to an 8-bit binary number.
00100000
3.3 Using the double and add method convert 00010101 to a decimal number.
21
3.4 Using the double and add method convert 00011001 to a decimal number.
25
3.5 Explain why the Least Significant digit of a binary number indicates
if the number is odd or even.
LSD is a 1
3.6 Convert the binary number 00010101 to a hexadecimal number.
0x15
3.7 Convert the binary number 00011001 to a hexadecimal number.
0x19
3.8 Convert the hexadecimal number 0x15 to a decimal number.
21
3.9 Convert the hexadecimal number 0x19 to a decimal number.
25
3.10 Convert the decimal number -35 to an 8-bit two’s complement binary
number. 11011101
Exercises
3.11 Convert the decimal number -32 to an 8-bit
two’s complement binary number.
11100000
3.12 Assuming the use of the two’s complement
number system find the equivalent
decimal values for the following 8-bit
binary numbers:
(a) 10000001 -127
(b) 11111111 -1
(c) 01010000 80
(d) 11100000 -32
(e) 10000011 -125
3.13 Convert the base 8 number 204 to decimal

132
102
76
54
3.17 Convert the base 10 number 81 to a base 9 number.
100
3.18 For each row of the table below convert the given 16 bit number to eachExercises
of the other two bases, assuming the two’s complement number system is used.

16 Bit Binary Hexadecimal Decimal
1111111100111100
0xFF88
-128
1111111111111010
0x0011
-25

3.19 You are given the following two numbers in two’s complement representation.
Perform the binary addition and indicate if there is signed overflow. __
Explain Why:
01101110
00011010
10001000 Yes overflow occurred – Sign of the result is different
from the operands
Exercises
3.20 You are given the following two numbers in two’s complement representation.
Perform the binary subtraction and indicate if there is signed overflow. ______
Explain Why:
11101000 11101000
-00010011 + 11101101
11010101 No Overflow
3.21 FF88
Sign extend the 8 bit hex number 0x88 to a 16 bit number. 0x_________

3.22 The following subtract instruction is located at address 0x00012344.

What are the two possible values for the contents of the PC after the
00012340
branch instruction executed? 0x_____________ 0001234C
0x ____________
This branch instruction is described in Appendix C.
loop: addi $t4, $t4, -8
sub $t2, $t2, $t0
bne $t4, $t2,loop

Exercises
3.23 You are given the following two 8-bit binary numbers in the two’s complement number
system. What values do they represent in decimal?
-108
X = 10010100 = __________ 44
Y = 00101100 = __________
2 10 2 10
Perform the following arithmetic operations on X and Y. Show your answers as

8-bit binary numbers in the two’s complement number system.
To subtract Y from X, find the two’s complement of Y and add it to X.
Indicate if overflow occurs in performing any of these operations.
X+Y X-Y Y-X
10010100 10010100 00101100

00101100 +11010100 +01101100
11000000 01101000 10011000
Exercise 3.24
The following code segment is stored in memory starting

at memory location 0x00012344.
What are the two possible values for the contents of the PC after the
branch instruction has executed? 0x__________
00012344 0x ____________
00012354
Add in line pseudocode to describe each instruction.
loop: lw $t0, 0($a0) # t0 = Mem[a0]

addi $a0, $a0, 4 # a0 = a0 +4
andi $t1, $t0, 1 # t1 = t1 & 1 “Extract LSD”
beqz $t1, loop # if t0 is an even # go to loop
Programming
Lesson #7
SPIM - The MIPS Simulator,
Register Window
Text Window
Data Window
Message Window
Console
Text Segment
[0x00400020] 0x34020004 ori $2, $0, 4 ; 34: li $v0, 4
[0x00400024] 0x3c041001 lui $4, 4097 [prompt] ; 35: la $a0, prompt
[0x00400028] 0x0000000c syscall ; 36: syscall
[0x0040002c] 0x34020005 ori $2, $0, 5 ; 38: li $v0, 5
[0x00400034] 0x1840000d blez $2 52 [end-0x00400034] ; 41: blez $v0, end
[0x00400038] 0x34080000 ori $8, $0, 0 ; 42: li $t0, 0
[0x0040003c] 0x01024020 add $8, $8, $2 ; 44: add $t0, $t0, $v0
[0x00400040] 0x2042ffff addi $2, $2, -1 ; 45: addi $v0, $v0, -1
[0x00400044] 0x14403ffe bne $2, $0, -8 [loop-0x00400044]; 46: bnez $v0, loop
[0x00400048] 0x34020004 ori $2, $0, 4 ; 47: li $v0, 4
[0x0040004c] 0x3c011001 lui $1, 4097 [result] ; 48: la $a0, result
[0x00400050] 0x34240022 ori $4, $1, 34 [result]
Analyzing the Data Segment
.data
prompt: .asciiz “\n Please Input a value for N = ”
result: .asciiz “ The sum of the integers from 1 to N is ”
bye: .asciiz “ **** Adios Amigo – Have a good day ****”
a e l P e s
[0x10010000] 0x2020200a 0x61656c50 0x49206573 0x7475706e
[0x10010010] 0x76206120 0x65756c61 0x726f6620 0x3d204e20
[0x10010020] 0x20200020 0x65685420 0x6d757320 0x20666f20
[0x10010030] 0x20656874 0x65746e69 0x73726567 0x6f726620
[0x10010040] 0x2031206d 0x4e206f74 0x20736920 0x20200a00
This is an example of an addressing structure called Little Indian

where the right most byte in a word has the smaller address.
Translating Assembly Language to Machine language
Use the information in Appendix C to verify that 0x3402000A

is the correct machine language encoding of the instruction
ori $2, $0, 10 li $v0, 10
In Appendix C we are shown how this instruction is encoded in
binary
ori Rt, Rs, Imm # RF[Rt] = RF[Rs] OR Imm
Op-Code Rs Rt Imm
001101ssssstttttiiiiiiiiiiiiiiii
00110100000000100000000000001010
0x 3 4 0 2 0 0 0 A
Translating Assembly Language to Machine language
R-Type Instruction
Use the information in Appendix C to verify that 0x01024020
is the correct machine language encoding of the instruction
add $8, $8, $2 add $t0, $t0, $v0
In Appendix C we are shown how this instruction is encoded in
binary
add Rd, Rs, Rt # RF[Rd] = RF[Rs] + RF[Rt]
Op-Code Rs Rt Rd Function Code
000000ssssstttttddddd00000100000
00000001000000100100000000100000
0x 0 1 0 2 4 0 2 0
Programming
Lesson #8
Exercise 4.1
Translate the following assembly language instructions to their
corresponding machine language codes as they would be
represented in hexadecimal. (Hint – Refer to Appendix C and
Appendix D.)
loop: addu $a0, $0, $t0 # 0x00082021

ori $v0, $0, 4 # 0x34020004
syscall # 0x0000000C
addi $t0, $t0, -1 # 0x2108FFFF
bnez $t0, loop # 0x1500FFFB
andi $s0, $s7, 0xffc0 # 0x32F0FFC0
or $a0, $t7, $s0 # 0x01F02025
sb $a0, 4($s6) # 0xA2C40004
srl $s7, $s7, 4 # 0x0017B902
Translating Assembly Language Store Byte to Machine Language
In Appendix C we are shown how Store Byte is encoded in binary

sb Rt, offset(Rs) # Mem[RF[Rs] + Offset] = RF[Rt]
Op-Code Rs Rt Offset
101000ssssstttttiiiiiiiiiiiiiiii
sb $4, 4($22) sb $a0, 4($s6)
10100010110001000000000000000100
0xA 2 C 4 0 0 0 4
Translating Assembly Language Shift Instruction to Machine Language
In Appendix C we are shown how Shift Right Logical is encoded in binary

srl Rd, Rs, sa # Rs = Rt << sa
Op-Code Rt Rd sa
00000000000tttttdddddvvvvv000010
srl $23, $23, 4 srl $s7, $s7, 4
00000000000101111011100100000010
0x0 0 1 7 B 9 0 2
PCSpim Translation
[0x00082021 addu $4, $0, $8 ; 3: addu $a0, $0, $t0

[0x34020004 ori $2, $0, 4 ; 4: ori $v0, $0, 4
[0x0000000c syscall ; 5: syscall
[0x2108ffff addi $8, $8, -1 ; 6: addi $t0, $t0, -1
[0x1500fffc bne $8, $0, -16 [main-0x00400030]; 7: bnez $t0, main
[0x32f0ffc0 andi $16, $23, -64 ; 8: andi $s0, $s7, 0xffc0
[0x01f02025 or $4, $15, $16 ; 9: or $a0, $t7, $s0
[0xa2c40004 sb $4, 4($22) ; 10: sb $a0, 4($s6)
[0x0017b902 srl $23, $23, 4 ; 11: srl $S7, $s7, 4
Exercises 4.2
What is the character string corresponding to the following ASCII codes?
Remember that for simulations running on Intel–based platforms,
the characters are stored in reverse order within each word.)
0x2a2a2a2a 0x69644120 0x4120736f 0x6f67696d 0x48202d20 0x20657661
**** i d A A s o ogim H - eva
**** Adios Amigo – Have

A Function to Print a Binary Value as a Hexadecimal
Number
For example suppose the following value is in $a0:
00000100101010111111010101001101
In Hexadecimal it is printed out as: 0x04ABF54D

Algorithm:
t2 = &buffer + 11; mem(t2) = 0; t2 = t2 – 1;
for (t0 = 8; t0 > 0; t0 = t0 -1)
{t1 = a0 & 15; t1 = t1 + 0x30; a0 = a0 >> 4;
if (t1> 57) t1 = t1+7;
mem(t2) = t1; t2 = t2-1}
mem(t2) = “x”; mem(t2-1) = “0”; mem(t2-2) = 0x20;
print the ASCII string in the buffer
Beginning of the PrintHex Function
########################################
# Algorithmic Description in Pseudo Code:
#
#########################################
.globl PrintHex
.data
buffer: .asciiz " 0x "
.text
PrintHex:
la $a1, buffer
addi $a1, $a1, 10 # Set pointer to end of buffer
...
...
... # Body of the Algorithm
...
jr $ra
Programming
Lesson #9
An Example Exam Question
Write a program that will compute the sum of the even positive values,
minus the odd negative values in an array of words. Stop when a value
of zero is found in the array. For Example:
array: .word -29, -30, 75, 34, -2, 90, -11, 98, 1, 0, 76
Pseudo Code for the Algorithm:

$a1 = &array;
$a0 = 0;
loop:
$t0= Mem($a1);
if ($t0 == 0) go to done
$a1 = $a1 + 4;
$t3 = $t0 & 1;
if ($t0 >= 0 & $t3 == 0) $a0 = $a0 + $t0;
else
if ($t0 < 0 & $t3 != 0) $a0= $a0 - $t0;
go to loop
done:
syscall(1) << $a0;
exit
Example Exam MIPS Code
Label Op-Code Dest. S1,S2 Comments
.data
array: .word -29, -30, 75, 34, -2, 90, -11, 98, 1, 0, 76
.text
main:
la $a1,array # $a1 = &array
li $a0, 0 # $a0 = 0
loop:
lw $t0,0($a1) # $t0 = Mem($a1)
beqz $t0, done
addi $a1, $a1, 4 # $a1 = $a1 + 4
andi $t3, $t0, 1 # $t3 = LSB of $t0
bnez $t3, odd # branch if odd
bltz $t0, loop
add $a0, $a0, $t0 # $t2 = $t2 + $t0
b loop
odd:
bgtz $t0, loop
sub $a0, $a0, $t0 # $a0 = $a0 - $t0
b loop
done:
li $v0, 1 # Print result syscall(1)
syscall
li $v0, 10 # exit
syscall
Example Exam Questions
2. You are given the following two numbers in two’s complement representation.
Perform the binary subtraction and indicate if there is signed overflow ? ______
Explain Why:
10101100
- 00001100 10101100

11110100
10100000
3. You are given the following two numbers in two’s complement representation.
Perform the binary addition and indicate if there is signed overflow ? ______
Explain Why:
10100100
+ 11101100
Example Exam Questions
Sign extend the 2-digit hex number 0x90 to a 4-digit hex number. 0x_______
how how the following PSEUDOCODE expression can be efficiently

mplemented in MIPS assembly language :$t0 = $s0 / 8 - 2 * $s1 + $s2 ;
sra $t0, $s0, 3

sll $t1, $s1, 1
sub $t0, $t0, $t1
add $t0, $t0, $s2
Performance Evaluation
Time and Space Tradeoff
The Figure of Merit (FM) we will use is:
Total clock cycles required to execute the
code plus total number of memory locations
required to store the code.
Assume:
• Multiplication requires 32 clock cycles
• Division requires 38 clock cycles
• System Calls
Read or Write an integer: assume 200 clock cycles
Read or Write a string: assume 20 clock cycles
.data A Complete
array: .word -4, 5, 8, -1 Program
msg1: .asciiz "\n The sum of the positive values = " Example
msg2: .asciiz "\n The sum of the negative values = "
.globl main
.text
main:
la $a0, msg1 # load address of msg1. into $a0
la $a0, array # Initialize address Parameter
li $a1, 4 # Initialize length Parameter
jal sum # Call sum
move $a0, $v0 # move value to be printed to $a0

syscall # print sum of positive values
la $a0, msg2 # load address of msg2. into $a0
move $a0, $v1 # move value to be printed to $a0
syscall # print sum of negative values
li $v0, 10 # terminate program run and
syscall # return control to system
An Example Function
sum: li $v0, 0
li $v1, 0 # Initialize v0 and v1 to zero
loop:
blez $a1, retzz # If (a1 <= 0) Branch to Return
addi $a1, $a1, -1 # Decrement loop count
lw $t0, 0($a0) # Get a value from the array
addi $a0, $a0, 4 # Increment array pointer to next word
bltz $t0, negg # If value is negative Branch to negg
add $v0, $v0, $t0 # Add to the positive sum
b loop # Branch around the next two instructions
negg:
add $v1, $v1, $t0 # Add to the negative sum
b loop # Branch to loop
retzz: jr $ra # Return
Classroom Exercises to Strengthen Your Mental Muscle
The class is presented with a challenging assembly language
programming exercise.
Everyone individually develops a pseudocode solution to the

exercise.
(5 minutes)
Groups compare their pseudo-code and refine their algorithms.

(5 minutes)
Everyone individually develops an assembly language solution to the

problem, and calculates a Figure of Merit (FM) for their solution.
Groups review and compare each others code, looking for the
most efficient code in terms of the Figure of Merit (FM):
FM = The number of words of assembly language code plus the

number of clock ticks required to execute the algorithm.
Exercise 5.1
Write a MIPS assembly language program to
find the Sum of the first 100 words of data in
the memory data segment with the label “chico”.
Store the resulting sum in the next memory
location beyond the end of the array chico.
Exercise 5.1 (Pseudo Code)
$a0 = &chico; # “&” means “Address of”
$t0 = 0;
For ($t1= 100; $t1 > 0; $t1= $t1- 1)
{
$t0 = $t0 + Mem($a0);
$a0 = $a0 + 4;
}
Mem($a0) = $t0;
Exercise 5.1 (MIPS Assembly Language)
.data
chico: .space 400
result: .word
.globl main
.text
main:
la $a0, chico # Load address pointer
li $t0, 0 # Clear sum
li $t1, 100 # Initialize loop count
loop:
lw $t2, 0($a0) # $t2 = Mem(a0)
add $t0, $t0, $t2 # $t0 = $t0 + $t2
addi $a0, $a0, 4 # Inc. address pointer
addi $t1, $t1, -1 # Dec. loop count
bgtz $t1, loop # if ($t1 > 0) branch
sw $t0, 0($a0) # Store the result
li $v0, 10 # End of program
syscall
Exam Question #4
The following code segment is stored in memory starting at memory
location 0x00067890. What are the two possible values for the
contents of the PC after the branch instruction has executed?
0x________ 0x
andi $t3, $t1, 1 #

bnez $t3, test #
add $t1, $s1, $s0 #
test:
Solution to Exam#1 - Pseudocode
###### Solution to Exam# 1 ########
# a0 = 0
# t0 = &M
# t1 = Mem(t0)
# t2 = Mem(t0 + 4)
# t3 = t1 & 1
# if (t3 == 0) t1 = t1 +1
# do {a0 = a0 + t1
# t1 = t1 + 2
# } while ( t1 <= t2)
# syscall(1) << a0
# exit
################################
MIPS Assembly Language Code
.data
M: .word 4
N: .word 10
.text
main:
li $a0, 0
la $t0, M
lw $t1, 0($t0)
lw $t2, 4($t0)
andi $t3, $t1, 1
bnez $t3, test
addi $t1, $t1, 1
b test
loop:
add $a0, $a0, $t1
addi $t1, $t1, 2
test:
ble $t1, $t2, loop
li $v0, 1
syscall
li $v0, 10
syscall
Programming
Lesson #10
Exercise 5.2
Write an efficient segment of MIPS assembly
language code to transfer a block of 100 words
starting at memory location “SRC” to another area
of memory beginning at memory location “DEST”.
$a1= &SRC; # “&” means “Address of”
$a2= &DEST;
for ($t0 = 100; $t0 > 0; $t0 =$t0 -1)
{$t1 = Mem($a1);
Mem($a2) = $t1;
$a1= $a1 + 4;
$a2= $a2 + 4;
}
.data
SRC: .space 400
DEST: .space 400
.globl main
.text
main:
la $a1, SRC # $a1 = &SRC
la $a2, DEST #$a2 = &DEST
li $t0, 100 #$t0 = 100
loop: lw $t1, 0($a1) #$t1= Mem($a1)
sw $t1, 0($a2) #Mem($a2) = $t1
addi $a1, $a1,4 #$a1 = $a1+4
addi $a2, $a2,4 #$a2 = $a2+4
addi $t0, $t0, -1 # $t0 = $t0 - 1
bgtz $t0, loop #Branch if $t0 > 0
li $v0, 10
syscall
Exercise 5.3
Write a MIPS function which accepts an integer
word in register $a0 and returns its absolute
value in $a0.
Also show an example code segment that calls

the ABS function twice, to test the function.
Function ABS($a0);
if ($a0 < 0) $a0 = $0 - $a0;
return;
.text
ABS: bgez $a0, return # If ($a0 >= 0) done
sub $a0, $0, $a0 # $a0 = 0 - $a0
return: jr $ra #Return
########################################
.globl main
.text
main: li $a0, -9876
jal ABS
li $v0, 1 # Output result
syscall
li $a0, 9876
jal ABS
li $v0, 1 # Output result
syscall
li $v0,10 # End of program
syscall
Programming
Lesson #11
Exercise 5.4
Write a function PENO (&X, N, SP, SN) that will
find the sum of the positive and negative values
in an array X of length “N”.
"X" the address of an array, passed through $a0.
"N" is the length of the array, passed through $a1.
The procedure should return two values:
(1) The sum of all the positive elements in
the array, passed back through $v0.
(2) The sum of all the negative elements in
the array, passed back through $v1.
$v0 = 0;
$v1 = 0;
for ( ; $a1 > 0; $a1 = $a1-1)
{$t0 = Mem($a0);
$t1 = $t0 & 1;
$a0 = $a0 + 4;
if ($t0 > 0 & $t1 = 0) $v0 = $v0 +
$t0;
if ($t0 < 0 & $t1 != 0) $v1= $v1+
$t0;
}
return;
.globl SUM
.text
PENO:
li $v0, 0
li $v1, 0
LOOP:
lw $t0, 0($a0)
andi $t2, $t0, 1
addi $a0, $a0, 4
bltz $t0, NEG
bnez $t2, CHK
add $v0, $v0, $t0
b CHK
NEG:
beqz $t2, CHK
add $v1, $v1, $t0
CHK:
addi $a1, $a1, -1
bgtz $a1, LOOP
jr $ra
A Function that takes a Binary Value and prints the
equivalent Decimal Representation, Right Justified
This function is similar to the PrintHex function

Except you Divide by 10 instead of 16
Differences:
Negative values must be preceded by a Minus.
Need to place Leading space spaces (ASCII 20)
into the print buffer.
Exercise 5.5
Write a function SUM(N) to find the sum of the
integers from 1 to N, making use the multiplication
and shifting operations. The value N will be passed to
the procedure in $a0 and the result will be returned in
the $v0 register.
Write a MIPS assembly language main program that will

call the Sum function five times each time passing a
different value to the function for N, and printing the results.
The values for N are defined below:
.data
N: .word 9, 10, 32666, 32777, 654321
Function SUM (a0: input value, $v0: output
value)
$v0 = $a0 + 1;
$v0 = $v0 * $a0;
$v0 = $v0 >> 1 #$v0 / 2;
return;
.text
SUM:
addi $v0, $a0, 1 # $v0 = $a0 + 1
mult $v0, $a0 # $v0 = $v0 * $a0
mflo $v0
sra $v0, $v0, 1 # Shift right arithmetic
# is the quick way to
# divide by 2
jr $ra
The Main Program
.data
N: .word 9, 10, 32666, 32777, 654321
.text
main: li $s0, 5
la $s1, N
loop:
lw $a0, 0($s1)
addiu $s1, $s1, 4
jal SUM
move $a0, $v0
li $v0, 1
syscall
addi $s0, $s0, -1
bnez $s0, loop
li $v0, 10
syscall
Programming
Lesson #12
Exercise 5.6
Write a function FIB(N, &array) to store the
First N elements of the Fibonacci sequence
into an array in memory. The value N is
passed in $a0, and the address of the array
is passed in register $a1.
The first few numbers of the Fibonacci sequence
are: 1, 1, 2, 3, 5, 8, 13, ............
Mem($a1) = 1;
Mem($a1 + 4) = 1;
for ($a0 = $a0 - 2; $a0 > 0; $a0 = $a0-1)
{
Mem($a1+8) = Mem($a1) + Mem($a1+4);
$a1 = $a1 + 4;}
return;
fib: li $t0, 1
sw $t0, 0($a1)
sw $t0, 4($a1)
addi $a0, $a0, -2
loop:
lw $t0, 0($a1)
lw $t1, 4($a1)
add $t0, $t0, $t1
sw $t0, 8($a1)
addi $a1, $a1, 4
addi $a0, $a0, -1
bgtz $a0, loop
jr $ra
Exercise 5.7
Write a function that receives 3 integer words in

registers $a0, $a1, & $a2, and returns them in ordered
form with the minimum value in $a0 and the maximum
value in $a2.
Function Order($a0,$a1,$a2);
If ($a0 > $a1) exchange $a0 and $a1;
if ($a1 > $a2) exchange $a1 and $a2
else return;
If ($a0 > $a1) exchange $a0 and $a1;
return;.
.text
order:
ble $a0, $a1, next
move $t0, $a1
move $a1, $a0
move $a0, $t0
next:
ble $a1, $a2, done
move $t0, $a2
move $a2, $a1
move $a1, $t0
ble $a0, $a1, done

move $t0, $a1
move $a1, $a0
move $a0, $t0
done: jr $ra
Exercise 5.8
Write the complete assembly language program,including
data declarations, that corresponds to the following C
code fragment.
Make use of the fact that multiplication and division by
powers of 2 can be performed most efficiently by shifting.
int main()
{ int K, Y ;
int Z[50] ;
Y = 56 ;
K = 20 ;
Z[K] = Y - 16 * ( K / 4 + 210) ;
}
.globl main
.data
K: .space 4
Y: .space 1
Z: .space 50
.text
main: la t3, K
li $t0, 56
sw $t0, 4($t3) # Y= 56
li $t1, 20
sw $t1, 0($t3) # K= 20
sra $t1, $t1, 2 # K/4
addi $t1, $t1, 210 # K/4 + 210
sll $t1, $t1, 4 # --- x 16
sub $t2, $t0, $t1 # t2= Y – 16 * (K / 4 + 210)
lw $t1, 0($t3) # t1=K
sll $t1, $t1, 2 # scale K
addu $t1, $t1, $t3 # t1= & Z[k] - 8
sw $t2, 8($t1) # Z[K]= Y-16*(k/4+210)
Programming
Lesson #13
Functional Descriptions of Code Modules
A functional description will provide the information
anyone needs to know if they are searching for a function
that would be useful is solving some larger programming
assignment. The functional description only describes
what the function does, not how it is done.
The functional description must explain how arguments
are passed to the function and how results are returned.
The following is an example functional description:

Hexout($a0: value)
A 32-bit binary value is passed to the function in register $a0
and the hexadecimal equivalent is printed out right justified.
Exercise 5.9
Write a function to search through an array “X” of
“N” words to find the minimum and maximum
values. The address of the array will be passed to
the function using register $a0, and the number of
words in the array will be passed in register $a1.
The minimum and maximum values are returned
in registers $v0, & $v1.
MaxMin ($a0: address, $a1: number of words)
$v0 = Mem($a0);
$v1 = $v0;
$a1 = $a1 - 1;
While ($a1 > 0)
{$a0 = $a0 + 4;
$t0 = Mem($a0);
if ($t0 < $v0) $v0 = $t0;
else if ($t0 > $v1) $v1 = $t0;
$a1= $a1 - 1;
}
return;
MaxMin:
lw $v0, 0($a0)
move $v1, $v0
addi $a1, $a1, -1
blez $a1, ret
loop:
addi $a0, $a0, 4
lw $t0, 0($a0)
bge $t0, $v0, next
move $v0, $t0
b chk
next:
ble $t0, $v1, chk
move $v1, $t0
chk:
addi $a1, $a1, -1
bgtz $a1, loop
ret:
jr $ra
Exercise 5.10
Write a function to find the sum of the main
diagonal elements in a two dimensional N by N
array of 32 bit words. The address of the array
and the size N are passed to the procedure in
registers $a0 and $a1 respectively.
The result is returned in $v0.
The values in registers $a0 and $a1 should not be

modified by this procedure.
Calculate the number of clock cycles required to
execute your algorithm, assuming N=4
Exercise 5.10 (Pseudocode)
$v0 = Mem($a0);
$t1 = $a0;
$t3=($a1+1) * 4;
for ($t0 = $a1-1; $t0 > 0, $t0= $t0-1)
{$t1= $t1+ $t3;
$v0= $v0 + Mem($t1) }
return
.text
mdsum:
lw $v0, 0($a0) # v0 = first element
move $t1, $a0
addi $t3, $a1, 1 # compute offset
sll $t3, $t3, 2 # multiply by 4
addi $t0, $a1, -1 # init. loop count
blez $t0, return
loop: add $t1, $t1, $t3 # calc. next address
lw $t2, 0($t1) # t2=Mem(t1)
add $v0, $v0, $t2 # add to sum
addi $t0, $t0, -1 # decrement loop count
bgtz $t0, loop
return: jr $ra
Exercise 5.11
Write a function to find the determinant of a two
by two matrix (array). The address of the array is
passed to the function in registers $a0 and the
result is returned in $v0. The value in register $a0
should not be modified by this function.
Calculate the number of clock ticks required to

execute your algorithm.
$v0 = Mem($a0) * Mem($a0+12) -
Mem($a0+4) * Mem($a0+8);
Return
.globl determ2
.text
determ2:
lw $t0, 0($a0)
lw $t1, 12($a0)
mult $t1, $t0
mflo $v0
lw $t0, 4($a0)
lw $t1, 8($a0)
mult $t1, $t0
mflo $t0
sub $v0, $v0, $t0
return:
jr $ra
Programming
Lesson #14
Exercise 5.12
Write a MIPS assembly language function that
accepts a binary number in register $a0 and
returns a value corresponding to the number of
one’s in the binary number.
Exercise 5.12(Pseudocode)
$v0 = 0;
while ($a0 = !0)
{
$t0 = $a0 & 1;
$a0 = $a0 >> 1;
$v0 = $v0 + $t0;
}
Return
.globl count
.text
count:
li $v0, 0
while:
andi $t0, $a0, 1
srl $a0, $a0, 1
add $v0, $v0, $t0
bnez $a0, while
jr $ra
Exercise 5.13
Translate the following pseudocode expression to MIPS assembly
language code. Include code to insure that there is no array
bounds violation when the store word (sw) instruction is executed.
Note that the array “zap” is an array containing 50 words, thus the
value in register $a0 must be in the range from 0 to 196. Include
code to insure that the value in register $a0 is a word address
offset into the array “zap.” If an array bounds violation is detected
or the value in register $a0 is not a word address offset then
branch to the label “Error.”
.data
zap: .space 200
.text
...
zap[$a0] = $s0
$t0 = $a0 & 3;
If ($t0 != 0 ) go to Error;
if ($a0 < 0) go to Error
if ($a0 > 196) go to Error
$t0 = &zap
$a0 = $a0 + $t0
Mem($a0) = $s0;
.data
zap: .space 200
.text
andi $t0, $a0, 3
bnez $t0, Error
bltz$a0, Error
li $t0, 196
bgt $a0, $t0, Error
la $t0, zap
add $a0, $a0, $t0
sw $s0, 0($a0)
Programming
Lesson #15
Exercise 5.14
Write a function to search through an array “X” of
“N” words to find how many of the values are
evenly divisible by four. The address of the array
will be passed to the function using register $a0,
and the number of words in the array will be
passed in register $a1. Return the results in
register $v0.
$v0 = 0;
$t3 = 3;
For ( ; $a1 > 0; $a1= $a1- 1)
{ $t2 = Mem ($a0);
$a0 = $a0 + 4;
$t0 = $t2 & t3;
If ($t0 == 0 ) $v0 = $v0 + 1;
}
return
Label Op-Code Dest. S1, S2
Comments
Div4:
li $v0, 0
li $t3, 3
b skip
loop:
lw $t2, 0($a0)
addi $a0, $a0, 4
and $t0, $t2, $t3
bnez$t0, skip
addi $v0, $v0, 1
skip:
addi $a1, $a1, -1
bgez$a1, loop
jr $ra
Chapter 6
Passing Arguments on the Stack
Program Counter (PC)
Cache Memory
Instruction Register
Out ALU
Control
Rs
Address Logic
Rt
Rd
Data In 4
Register File
The Stack is in Memory and Register $sp
Points to the Top of Stack
Chapter 6
Passing Arguments on the Stack
An Example of Jack calling Jill(A, B, C, D, E)
addiu $sp, $sp, -24 # Allocate Space on the Stack

sw $t1, 0($sp) # First In Parameter “A” at Mem[Sp]
sw $t2, 4($sp) # Second In Parameter “B” at Mem[Sp+ 4]
sw $t3, 8($sp) # Third In Parameter “C” at Mem[Sp+ 8]
sw $ra, 20($sp) # Save Return address
jal JILL # Call the Function
lw $ra, 20($sp) # Restore Return Address to Main Program
lw $t4, 12($sp) # Get First Out Parameter “D” at Mem[Sp+12]
lw $t5, 16($sp) # Get Second Out Parameter “E” at
Mem[Sp+16]
addiu $sp, $sp, 24 # De-allocate Space on the Stack
Example of Jill accessing the Stack
JILL:
lw $a0, 0($sp) # Get First In Parameter “A” at Mem[Sp]
lw $a1, 4($sp) # Get Second In Parameter “B” at Mem[Sp+4]
lw $a2, 8($sp) # Get Third In Parameter “C” at Mem[Sp+8]
...
... <Body of Function>
...
sw $v0, 12($sp) # First Out Parameter “D” at Mem[Sp+12]
sw $v1, 16($sp) # Second Out Parameter “E” at Mem[Sp+16]
jr $ra # Return to JACK
Example of Jack Saving
Important Temporary Registers
addiu $sp, $sp, -32 # Allocate More Space on the Stack <####
sw $t1, 0($sp) # First In Parameter “A” at Mem[Sp]
sw $t2, 4($sp) # Second In Parameter “B” at Mem[Sp+ 4]
sw $t3, 8($sp) # Third In Parameter “C” at Mem[Sp+ 8]
sw $ra, 20($sp) # Save Return address
sw $t8, 24($sp) # Save $t8 on the stack <####
sw $t9, 28($sp) # Save $t9 on the stack <####
jal JILL # call the Function
lw $t8, 24($sp) # Restore $t8 from the stack <####
lw $t9, 28($sp) # Restore $t9 from the stack <####
lw $ra, 20($sp) # Restore Return Address to Main Program
lw $t4, 12($sp) # Get First Out Parameter “D” at Mem[Sp+12]
lw $t5, 16($sp) # Get Second Out Parameter “E” at Mem[Sp+16]
addiu $sp, $sp, 32 # De-allocate Space on the Stack <####
What if Jill Needs Additional Local Variables?
addiu $sp, $sp, -16 # Allocate Space for a Temporary array
move $a0, $sp # Initialize a pointer in $a0 to the array
<Use the array on the stack>
addiu $sp, $sp, 16 # Deallocate Temporary Space
$sp
$a0
Programming
Lesson #16
Exercise 6.1
MinMax (&X, N, Min, Max)
Write a function to search through an array 'X' of 'N'

words to find the minimum and maximum values.
The parameters &X and N are passed to the function
on the stack, and the minimum and maximum values
are returned on the stack. (Show how MinMax is called)
MinMax(&X:$t1, N:$t2, min:$t8, max:$t9)
$t1 = Mem($sp);
$t2 = Mem($sp+4);
$t8 = Mem($t1);
$t9 = $t8;
$t2 = $t2 - 1;
While ($t2 > 0)
{$t1 = $t1 + 4;
$t0 = Mem($t1);
if ($t0 < $t8) $t8 = $t0;
else if ($t0 > $t9) $t9 = $t0;
$t2= $t2 - 1;
}
Mem($sp+8) = $t8;
Mem($sp+12) = $t9;
##### An Example of calling the function #####
.data
array .space 400
.text
addiu $sp, $sp, -16
la $t0, array
sw $t0, 0($sp)
li $t0, 100
sw $t0, 4($sp)
jal MinMax
lw $t0, 8($sp)
lw $t1, 12($sp)
addiu $sp, $sp, 16
Exercise 6.1 MinMax(&X:$t1, N:$t2, min:$t8, max:$t9)
.text
MinMax:
lw $t1, 0($sp) # get &X
lw $t2, 4($sp) # get N
lw $t8, 0($t1) # Init. min
move $t9, $t8 # Init. max
addi $t2, $t2, -1
blez $t2, ret
loop:
addiu $t1, $t1, 4
lw $t0, 0($t1)
bge $t0, $t8, next
move $t8, $t0
b chk
next:
ble $t0, $t9, chk
move $t9, $t0
chk:
addi $t2, $t2, -1
bgtz $t2, loop
ret:
sw $t8, 8($sp) # put min
sw $t9, 12($sp) # put max
jr $ra
Programming
Lesson #17
Memory Layout
0x00000000
Reserved
0x00400000
Text Segment
0x10000000
Data Segment
Stack Segment
0x70000000
Operating System
0xFFFFFFFF
Exercise 6.2
Search(&X, N, V, L)
Write a function to sequentially search an array X of N
bytes for the relative location L of a value V.
The parameters &X, N, and V are passed to the
procedure on the stack, and the relative location L
(a number ranging from 1 to N) is returned on the
stack.
If the value V is not found the value -1 is returned for
L.
$t3= Mem(sp); # get &X
$t1= Mem($sp + 4); # get N
$t0= Mem($sp + 8); # get V
$t2=$t1;
for ($t2 = $t2 - 1; $t2 >= 0; $t2= $t2 - 1)
{ $t4 = mem($t3);
$t3=$t3 + 1;
if ( $t4 == $t0) go to found;
}
Mem(sp + 12) = -1;
go to exit;
found:
Mem(sp + 12) = $t1- $t2;
exit: return;
.text
search:
lw $t3, 0($sp) # get &X
lw $t1, 4($sp) # get N
lw $t0, 8($sp) # get V
move $t2, $t1
addi $t2, $t2, -1 # t2 = N - 1
loop:
lbu $t4, 0($t3) # get a character
addiu $t3, $t3, 1 # increment pointer
beq $t4, $t0, found
addi $t2, $t2, -1 # decrement loop counter
bgez $t2, loop
li $t4, -1
sw $t4, 12($sp)
b exit
found:
sub $t1, $t1, $t2
sw $t1, 12($sp)
exit: jr $ra
Exercise 6.3
Scan(&X, N, U, L, D)
Write a function to scan an array 'X' of 'N' bytes counting how many
bytes are ASCII codes for:
a. upper case letters - U
b. lower case letters - L
c. decimal digits - D

Return the counts on the stack. The address of the array and the number of bytes N
will be passed to the function on the stack.
Write a short main program to test this function.

A Main Program to Test the Scan Function
.data
string: .asciiz “The Quick Fox 0123456789”
.text
main: -----
-----
addiu $sp, $sp, -20 # Allocate
la $t0, string
sw $t0, 0($sp)
li $t0, 24
sw $t0, 4($sp)

jal Scan
lw $t0, 8($sp)
lw $t1, 12($sp)
lw $t2, 16($sp)
addi $sp, $sp, 20 # Deallocate
----
Scan(&X:$t6, N:$t2, U:$t3, L:$t4, D:$t5)
$t6 = Mem(sp) # &X
$t2 = Mem(sp+4) # N
$t3=$t4=$t5=0;
For ( ; $t2> 0; $t2=$t2-1)
{
$t1 = mem($t6) # get a byte
$t6 = $t6 + 1
if ( $t1 >= 65 && $t1 <= 90 ) $t3 = $t3+1;
else if ( $t1 >= 97 && $t1 <= 122) $t4=$t4+1;
else if ( $t1 >= 48 && $t1 <= 57 ) $t5=$t5+1;
}
Mem(sp + 8 ) = $t3;
Mem(sp + 12 ) = $t4;
Mem(sp + 16 ) = $t5;
return;
Exercise 6.3 (Assembly Language Initialize)
Scan(&X:$t6, N:$t2, U:$t3, L:$t4, D:$t5)
scan:
lw $t6, 0($sp) # Get &X
lw $t2, 4($sp) # Get Value N
li $t3, 0 # Count of Upper Case
li $t4, 0 # Count of Lower Case
li $t5, 0 # Count of Decimal Digits
blez $t2, done
li $t0, 48 # ASCII “0”
li $t9, 57 # ASCII “9”
li $t7, 97 # ASCII “a”
li $t8, 122 # ASCII “z”
addiu $sp, $sp, -8 # Allocate Temp Space
sw $s6, 0($sp) # Save s6
sw $s7, 4($sp) # Save s7
li $s6, 65 # ASCII “A”
li $s7, 90 # ASCII “Z”
Exercise 6.3 (Assembly Language Body)
loop: lbu $t1, 0($t6)
addi $t6, $t6, 1
blt $t1, $s6, num # “A”
bgt $t1, $s7, lowc # “Z”
addi $t3, $t3, 1
b check
lowc:
blt $t1, $t7, check # “a”
bgt $t1, $t8, check # “z”
addi $t4, $t4, 1
b check
num:
blt $t1, $t0, check # “0”
bgt $t1, $t9, check # “9”
addi $t5, $t5, 1
check:
addi $t2, $t2, -1
bgtz $t2, loop
Exercise 6.3 (Assembly Language Continued)
lw $s6, 0($sp) # Restore s6

lw $s7, 4($sp) # Restore s7
addiu $sp, $sp, -8 # Deallocate Temp Space
sw $t3, 8($sp)
sw $t4, 12($sp)
sw $t5, 16($sp)
jr $ra
Programming
Lesson #18
Exercise 6.4
Hypotenuse(A, B, H)
This is an exercise in calling nested functions and passing
parameters on the stack.
Write a function to find the length of the hypotenuse of a right

triangle whose sides are of length A and B. Assume that a math
library function “sqr (V, R)” is available, which will compute the
square root of any positive value V, and return the square root
result R.
Write a main program to test this function.

A Main Program to test hypotenuse
main:
addi $sp, $sp, -12 # allocate
li $t0, 3
sw $t0, 0($sp)
li $t0, 4
sw $t0, 4($sp)
jal hypotenuse
lw $a0, 8($sp) # get result

addi $sp, $sp, 12 # deallocate
li $v0, 1 # print result
syscall
li $v0, 10
syscall
t0 = Mem(sp);
t1 = Mem(sp+4);
Mem(sp+8) = sqr ( t0*t0 + t1*t1 ) ;
return
Exercise 6.4 (Assembly Language)
hypotenuse:
lw $t0, 0($sp) # Get A
lw $t1, 4($sp) # Get B
mult $t0, $t0
mflo $t0
mult $t1, $t1
mflo $t1
add $t0, $t0, $t1
addi $sp,$sp, -12 # Allocate
sw $t0, 0($sp) # Pass Value to sqr
sw $ra, 8($sp) # Save ra
jal sqr # Call sqr
lw $t0, 4($sp) # Get sqr Result
lw $ra, 8($sp) # Restore ra
sw $t0, 8($sp) # Return Hypotenuse
jr $ra
Programming
Lesson #19
Exercise 6.5
AVA (&X, &Y, &Z, N, status)
Write a function to perform an absolute value vector addition.
Use the stack to pass parameters. The parameters are:
the starting address of three different word arrays (vectors) : X, Y, Z,
and an integer value N specifying the size of the vectors.
If overflow ever occurs when executing this function,

an error status of “1” should be returned and the function aborts
any further processing. Otherwise, return the value “0” for status.
The function will perform the vector addition:

Xi = | Yi | + | Zi | ; with i going from 0 to N - 1.
Also write a main program to test this function.

Example code for testing the AVA function
`.data
zig: .space 20
zag: .word 345, 765, -234567, 2345, 999
zonk: .word -38645, 765987, 67, 3215, 444
msg: .asciiz “Overflow Occurred”
.text
main: addi $sp, $sp, -20 # Allocate
la $s0, zig
sw $s0, 0($sp)
la $s0, zag
sw $s0, 4($sp)
la $s0, zonk
sw $s0, 8($sp)
li $s0, 5
sw $s0, 12($sp)
jal AVA
lw $s0, 16($sp)
beqz $s0, done
li $v0, 4
la $a0, msg
syscall
done: li $v0, 10
syscall
AVA(&X:$t6, &Y:$t7, &Z:$t8, N:$t0, status)
$t6 = Mem($sp);
$t7 = Mem($sp+4);
$t8 = Mem($sp+8);
$t0= Mem ($sp+12);
for ( ; $t0 > 0 ; $t0 = $t0 - 1)
{ $t1= Mem($t7);
$t7 = $t7 + 4;
if ($t1 < 0) $t1 = 0 - $t1;
$t2= Mem($t8);
$t8 = $t8 + 4;
if ($t2 < 0) $t2 = 0 - $t2;
$t1 = $t1 + $t2;
if ($t1< 0) go to ovf;
Mem($t6) = $t1;
$t6 = $t6 + 4;
}
Mem($sp+16) = 0;
return
ovf: Mem($sp+16) = 1; return
Label Op-Code Dest. S1, S2 Comments Exercise 6.5 (Assembly Language)
.text
AVA: lw $t6, 0($sp) # Get &X
lw $t7, 4($sp) # Get &Y
lw $t8, 8($sp) # Get &Z
lw $t0, 12($sp) # Get N
loop: lw $t1, 0($t7)
addiu $t7, $t7, 4
bgez $t1, next
sub $t1, $0, $t1
next: lw $t2, 0($t8)
addiu $t8, $t8, 4
bgez $t2, sum
sub $t2, $0, $t2
sum: add $t1, $t1, $t2
bltz $t1, ovf
sw $t1, 0($t6)
addiu $t6, $t6, 4
addi $t0, $t0, -1
bgtz $t0, loop
sw $0, 16($sp)
jr $ra
ovf:
li $t0, 1
sw $t0, 16($sp)
jr $ra
Programming
Lesson #20
Exercise 6.6
Fibonacci (N, E)
Write an function to return the Nth element in the Fibonacci sequence.
A value N is passed to the function on the stack, and the Nth Fibonacci
number E is returned on the stack.
If N is greater than 46 overflow will occur, so return a value of 0 if N

is greater than 46. Also show an example of calling this function to return
the 10th element in the sequence.
The first few numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5 . . . .

Example Code to Test Fibonacci
.data
msg: .asciiz “Can not Compute Correct Result”
.text
main: addi $sp, $sp, -8 # Allocate
li $t0, 10 # Pass argument to Fib
sw $t0, 0($sp)
jal Fib # Call Fibonacci
lw $a0, 4($sp) # Get result back
bgtz $a0, done
li $v0, 4
la $a0, msg
syscall
done: li $v0, 1 # Print result
syscall
li $v0, 10
syscall
$t0 = Mem($sp);
if ($t0 > 46) {Mem($sp+4) = 0; Return;}
If ($t0 > 1)
{$t1 = 0; $t2 = 1;
For ($t0 = $t0 - 1; $t0 > 0; $t0 = $t0 - 1)
{
$t3 = $t2 + $t1;
$t1= $t2;
$t2 = $t3
}
}
else $t3= $t0;
Mem($sp+4) = $t3;
Return
Exercise 6.6 (Fibonacci Assembly Language)
Fib:
lw $t0, 0($sp) # Get N
bltz $t0, error
addi $t1, $t0, -46
bgtz $t1, error
li $t1, 0
li $t2, 1
move $t3, $t0
addi $t0, $t0, -1
blez $t0, done
loop:
add $t3, $t2, $t1
move $t1, $t2,
move $t2, $t3
addi $t0, $t0, -1
bgtz $t0, loop
done:
sw $t3, 4($sp) # Return Nth Fibonacci number
jr $ra
error:
sw $0, 4($sp)
jr $ra
Fibonacci (A Very Efficient Method)
.data
fibnum: .word 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,
.word 6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,
.word 832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,
.word 39088169,63245986,102334155,165580141,267914296,
.word 433494437,701408733,1134903170,1836311903
.text
fib:
lw $t0, 0($sp)
bltz $t0, error
addi $t1, $t0, -46
bgtz $t1, error
sll $t0, $t0, 2
la $t1, fibnum
addu $t0, $t1, $t0
lw $t0, 0($t0)
sw $t0, 4($sp)
jr $ra
error:
sw $0, 4($sp)
jr $ra
Exercise 6.7
BubSort (&X, N)
Write a function to sort an array ‘“ X ” of ‘“N” words into ascending order
using the bubble sort algorithm.
The address of the array and the value N will be passed to the function
on the stack.
Show how the sort function is called.
Example Assembly Language Code to Call Sort(&Z, 1000)

addi $sp, $sp, -8
la $t0, z
sw $t0, 0($sp)
li $t0, 1000
sw $t0, 4($sp)
jal sort
addi $sp, $sp, 8
BubSort (&X:$t3, N:$t0)
$t0 = Mem($sp+4);
Again:
$t0 = $t0 - 1;
$t2=0;
$t3= Mem($sp);
For ($t1= $t0; $t1 > 0; $t1 = $t1-1)
{If ( Mem($t3) > Mem($t3+4) ) then
{exchange Mem($t3) & Mem($t3+4)
$t2=1}
$t3= $t3 +4;
}
If ($t2 == 1) go to Again
else
return
BubSort:
again:
addi $t0, $t0, -1
li $t2, 0 # Clear flag
lw $t3, 0($sp) # Get pointer to array
move $t1, $t0, # Init. loop count
loop:
lw $t8, 0($t3)
lw $t9, 4($t3)
ble $t8, $t9, next
sw $t8, 4($t3) # Swap values
sw $t9, 0($t3)
li $t2, 1 # Set Flag
next:
addi $t3, $t3, 4 # Inc. pointer
addi $t1, $t1, -1 # Dec. loop count
bgtz $t1, loop
bnez $t2, again

jr $ra
Exercise 6.8
RipSort (&X, N)
Write a function to sort an array “X” of “N” words into
ascending order using the ripple sort algorithm.
The address of the array and the value N will be passed

to the function on the stack.
Function Ripsort (&X:$t3, N:$t0);
$t0= Mem($sp+4);
$t3= Mem($sp);
For ($t0 = $t0 - 1; $t0 > 0; $t0 = $t0 -1)
{$t8 = Mem($t3);
$t3 = $t3 + 4;
$t4 = $t3;
For ($t5 = $t0; $t5 > 0; $t5 = $t5 -1)
{$t9 = Mem($t4);
$t4 = $t4 + 4;
if ($t8 > $t9)
{Mem($t3 - 4) = $t9;
Mem($t4 - 4) = $t8;}
}
}
return
Ripsort:
lw $t3, 0($sp) # Get &X
addi $t0, $t0, -1
loop1:
lw $t8, 0($t3)
addi $t3, $t3, 4
move $t4, $t3
loop2:
move $t5, $t0
lw $t9, 0($t4)
addi $t4, $t4, 4
ble $t8, $t9, check
sw $t9, -4($t3)
sw $t8, -4($t4)
check:
addi $t5, $t5, -1
bgtz $t5 , loop2
next:
addi $t0, $t0, -1
bgtz $t0, loop1
jr $ra
Exercise 6.9
Roots(a, b, c, Status, R1, R2)
This is an exercise in nested function calls and passing parameters
on the stack.
Write a procedure to calculate the roots of any quadratic equation

of the form y = a*x2 + b*x + c where the integer values a, b, and c
are passed to the function on the stack.
Status should indicate the nature of the results returned as
indicated below:
0 : 2 real roots R1 & R2
1 : 1 real root in R1= -a/b
2 : 2 complex roots of the form (R1 + i R2)
3 : no roots computed (error)
Assume that a math library function “sqr” is available,
that will compute the square root of a positive argument.
Exercise 6.9 (Roots Pseudocode)
$t0 = Mem($sp);
$t1 = Mem($sp+ 4);
$t2 = Mem($sp+8);
if ($t2 = 0) {Mem($sp+12)=1; Mem($sp+16)= -$t0/$t1}
else
{$t4 = $t1;
$t4 = $t1*$t4; b2
$t3 = $t2*$t1; a*c
shift $t3 left by 2;
$t4 =$t4-$t3 b2 - 4ac
if ($t4 > 0) {Mem($sp+16)=0;
$t4 = sqr($t4);
Mem($sp+16) = sra[(- $t1+ $t4)/ $t0]
Mem($sp+20) = sra[(- $t1- $t4)/ $t0] }
else {Mem($sp+12)= 2;
Mem($sp+16) =
Mem($sp+20) =
Programming
Lesson #21
Reentrant Functions
It is important that all shared operating system functions

and library functions running on a multi-tasking computer
system be reentrant. (Examples: text-editor or compiler)
Rules for Writing Reentrant Code:

•All local variables are dynamically allocated on the stack.
•No read/write data in the global data segment.
Reentrant I/O Functions
System services to perform I/O should be reentrant.
In Chapter Five we discussed the algorithms to perform I/O in decimal
and hexadecimal representation. To make these functions reentrant,
allocation of space for character buffers must be removed from the global
data segment and code must be inserted into the functions
to dynamically allocate space on the stack for character buffers.
Lets suppose you want to allocate space on the stack for
an input buffer of 32 characters, initialize a pointer in $a0
to point to the first character in this buffer, and then read
in a string of characters from the keyboard.
This can be accomplished with the following instructions.

addiu $sp, $sp, -32 # Allocate Space on top of stack
move $a0, $sp # Initialize $a0 as a pointer to the buffer
li $a1, 32 # Specify length of buffer
li $v0, 8 # System call code for Read String
syscall
Exercise 7.1 Reverse
Write a reentrant function that will read in a string of characters
(60 Characters Maximum) and will print out string in reverse.
For Example the input string “July is Hot”

will be printed out as “toH si yluJ”.
See Appendix A
Read String has the same semantics as the Unix library routine fgets.
It reads up to n – 1 characters into a buffer and terminates the string
with a null byte. If fewer than n – 1 characters are on the current line,
Read String reads up to and including the newline and again
null-terminates the string
J u l y i s Ho t
sp = sp – 128; # Allocate space for 2 buffers 64 bytes each
a0 = sp; # Initialize pointer to input buffer
a1 = 61;
v0 = 8;
syscall; # Read a string
a1= sp + 127; # Initialize pointer to end out output buffer
mem(a1) = 0; # null terminator
loop:
t1 = mem(a0);
a0 = a0 +1;
if (t1 == 10) go to print;
a1 = a1 –1;
mem(a1) = t1;
go to loop;
print:
a0 = a1;
v0 = 4;
syscall;
sp = sp + 128; # Allocate space
return
rev: addi $sp, $sp, – 128 # Allocate buffer space ######
move $a0, $sp # Initialize pointer
li $a1 , 61
li $v0, 8
li $t4, 10
syscall # Read a string
addi $a1, $sp, 127 # Initialize pointer to end
sb $0, 0($a1) # null terminator
loop:
lb $t1, 0($a0)
addi $a0, $a0, 1
beq $t1, $t4, print
addi $a1, $a1, –1
sb $t1, 0($a1)
b loop
print:
li $a0, $a1
li $v0, 4
syscall
addi $sp, $sp, 128 # De-allocate buffer space ####
jr $ra
Programming
Lesson #22
Exercise 7.2
Palindrome (b)
Write a reentrant function that will determine if a string is a palindrome.
The function should read in a string (14 characters max)
placing them in a buffer on the stack.
This procedure should call a “Search” function to determine

the exact number of actual alphabetic characters in the string.
A Boolean value of true or false (1 or 0) will be returned on the stack

to indicate if the string is a palindrome.
Exercise 7.2 (Palindrome Pseudocode)
sp = sp - 16 # allocate buffer on stack #######

a0 = sp # address of buffer
a1 = 16 # length of buffer
syscall (8) # read a string
sp = sp - 20 # allocate parameter space *******
Mem(sp) = a0 # address of string
Mem(sp+4) = 16 # length N
Mem(sp+8)=10 # new line char
Mem(sp+16) = $ra # save return address
call srch
$ra = Mem(sp+16) # restore return address
t8 = Mem(sp+12) # location of \n
sp = sp + 20 # deallocate parameters space *****
Exercise 7.2 Palindrome Continued
t 7 = sp # address of buffer
t8 = t7 + t8 - 2 # address of string end
t2 = 1 # set Boolean value to true
loop:
if (t7 >= t8) go to end
t0 = mem(t7)
t1 = mem(t8)
t7 = t7 + 1
t8 = t8 -1
if (t0 == t1) go to loop
t2=0
end:
sp = sp + 16 # deallocate string buffer space ####
Mem(sp) = t2
return
Exercise 7.2 (Palindrome Assembly Language)
pal:
addi $sp, $sp, -16 #@@@@@@@@@
move $a0, $sp # Init. buffer address
li $a1, 16
li $v0, 8
syscall
addi $sp, $sp, -20 #<<<<<<<<<<<<<<<
sw $t7, 0($sp)
li $t0, 16
sw $t0, 4($sp)
li $t0, 10
sw $t0, 8($sp)
sw $ra, 16($sp)
jal srch # Call Search(&X, N, V, L)
lw $ra, 16($sp)
lw $t8, 12($sp)
addi $sp, $sp, 20 #<<<<<<<<<<<<<<<<
Exercise 7.2 (Palindrome Assembly Language)
move $t 7, $sp # address of buffer
add $t8, $t8, $t7
addi $t8, $t8, -2 # init right pointer
li $t2, 1
loop:
bge $t7, $t8, end
lbu $t0, 0($t7)
lbu $t1, 0($t8)
addi $t7, $t7, 1
addi $t8, $t8, -1
beq $t0, $t1, loop
li $t2, 0
end:
addi $sp, $sp, 16 #@@@@@@@@@@
sw $t2, 0($sp)
jr $ra
Programming
Lesson #23
Exercise 7.6
Write an efficient MIPS assembly language function Scan(&X, Num)
that will scan through a string of characters with the objective of locating where
all the lower case vowels appear in the string, as well as counting how many total
lower case vowels appeared in a string. Vowels are the letters a, e, i, o, u.
The address of the string "X" is passed to the function on the stack, and the
number of vowels found “NUM” is returned on the stack. A null character
terminates the string. Within this function, you must include code to call any
student’s “PrintDecimal” function to print, right justified, the relative position
within the string where each vowel was found. Notice this will be a nested
function call. Here is an example string: “The quick brown fox.”
For the above example string the output of your program would be

A Vowel was Found at Relative Position : 3

Analyze your Scan function. Is it a reentrant function? ___(yes/no) Explain why.
Exercise 7.6 (Scan Assembly Language Code)
.text
scan:
lw $t5, 0($sp) # get &X
li $t6, 0 # Num
li $t8, 0 # Relative Position
again:
li $t0, 0x61 # "a"
li $t1, 0x65 # "e"
li $t2, 0x69 # "i"
li $t3, 0x6f # "o"
li $t4, 0x75 # "u"
loops:
lbu $t7,0($t5) # Get a character
beqz $t7, ends
addi $t5, $t5, 1 # Inc. string pointer
addi $t8, $t8, 1 # Inc. relative position
beq $t7, $t0, print
beq $t7, $t1, print
beq $t7, $t2, print
beq $t7, $t3, print
beq $t7, $t4, print
b loops
Exercise 7.6 (Scan Assembly Language Code)
print:
li $v0, 4 # System call code for print_str
la $a0, msg # Load address of msg. into $a0
syscall # Print the string
addi $t6, $t6, 1
# <<<<<<<<<<<<<<<<
addi $sp, $sp, -16
sw $t8, 0($sp) # Relative Position
sw $t5, 4($sp) # String pointer
sw $t6, 8($sp) # Num
sw $ra, 12($sp)
jal PrintDecimal # Call PrintDecimal
lw $t8, 0($sp)
lw $t5, 4($sp)
lw $t6, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
# <<<<<<<<<<<<<<<<
b again
ends:
sw $t6, 4($sp)
jr $ra
.data
msg: .asciiz "\n A Vowel was Found at Relative Position: "
Programming
Lesson #24
Exercise 7.3 Iterative N Factorial
Write an iterative function to to compute N Factorial “N!”
Calculate the number of clock cycles to compute 10!
$v0 = Mem($sp);
For (a0 = $v0 –1; $a0 > 0 ; $a0 = $a0 – 1)
$v0 = $v0 * $a0; Label Op-Code Dest. S1, S2 Comments
Mem($sp+4) = $v0; Fac:
lw $v0, 0($sp)
Return
addi $a0, $v0, -1
loopf:
blez $a0, return
mult $v0, $a0
mflo $v0
addi $a0, $a0. -1
b loopf
return:
sw $v0, 4($sp)
jr $ra
Exercise 7.3 Recursive N Factorial
Write a recursive function to to compute N Factorial “N!”
Calculate the number of clock cycles to compute 10!
$a0 = Mem($sp);
Mem($sp+4) = $a0 * Fac($a0 - 1);
Return
Exercise 7.3 Recursive N Factorial
FacR:
lw $a0, 0($sp)
bltz $a0, Prob
addi $t1, $a0, -13
bgtz $t1, Prob
addiu $sp, $sp, -16 #<<<<<
sw $ra, 12($sp)
sw $a0, 8($sp)
slti $t0, $a0, 2
beqz $t0, Go
li $v0, 1
b facret
Go:
addi $a0, $a0, -1
sw $a0, 0($sp)
jal FacR # Recursive Call
lw $v0, 4($sp)
lw $ra, 12($sp) facret:
lw $a0, 8($sp) addiu $sp, $sp, 16 #<<<<
mult $v0, $a0 sw $v0, 4($sp)
mflo $v0 jr $ra
Prob:
sw $0, 4($sp)
jr $ra
Exercise 7.4 Recursive Fibonacci
Fib(N, E)
If (N > 1)
E = Fib(N - 1) + Fib( N - 2)
else E = N
#########################
Fibrec:
addi $sp, $sp, -12
sw $a0, 0($sp) # Save Registers
sw $t0, 4($sp)
sw $ra, 8($sp)
lw $a0, 12($sp) # Get N
li $t2, 1
bgt $a0, $t2, deep
sw $a0, 16($sp) # Return N!
addi $sp, $sp 12
jr $ra
Exercise 7.4 Recursive Fibonacci
deep:
addi $a0, $a0, -1
addi $sp, $sp, -8 # <<<< Allocate Space
sw $a0, 0($sp)
jal Fibrec # Recursive Call
lw $t0, 4($sp) # $t0 = Fib (N-1)
addi $a0, $a0, -1
sw $a0, 0($sp)
jal Fibrec # Recursive Call
lw $a0, 4($sp) # $a0 = Fib (N-2)
addi $sp, $sp, 8 # <<<< De-allocate Space
add $a0, $a0, $t0 # Fib (N-1) + Fib (N-2)
sw $a0, 16($sp)
return:
lw $a0, 0($sp) # Restore Registers
lw $t0, 4($sp)
lw $ra, 8($sp)
addi $sp, $sp 12
jr $ra
Exercise 7.5
Write a recursive function to find the determinant of a N x N
matrix (array). The address of the array M and the size N
are passed to the function on the stack, and the result R is
returned on the stack: det (&M, N, R)
5 8 0 2 3
1 6 1 9 5
4 7 8 1 2
2 1 1 2 0
6 8 4 1 1
Recursive Pseudo Code for the Determinant (&M , N , R )
$t9 = Mem(sp+4); # get size N
if ( $t9 < 2) { Mem(sp+8) = 0; return}
If ( $t9 == 2) Mem(sp+8) = Det2
else
{t5 = t9 -1 # Size of cofac matrix
t4 = (t5 * t5) *4 # Dynamic storage alloc.
sp = sp - t4 - 12 # Allocate space for cofac
matrix + arg
Mem(sp + 4) = t5 # Pass size (N-1)
Mem(sp) = sp + 16 # Pass addr. cofac matrix
t3=0 # accumulator
for (t6 = 0; t6 < t9; t6 = t6+1)
{ Put col t6 cofac matrix on stack
push t3,t4,t5,t6,t9 registers on stack
call det(&m, n, r)
restore t3,t4,t5,t6,t9 registers from the stack
t5=Mem(sp+ 8) #result
If (t6 && 1== 0) t3= t3 + t5 else t3= t3 - t5
}
sp = sp + t4 + 12 #clean up stack
return
Programming
Lesson #25
Exercise 8.1
Write your most efficient MIPS assembly language code translation
for the following function and main line calling program.
Note, all communication with the function must use a stack frame.
Make use of the fact that multiplication and division by powers of 2
can be performed most efficiently by shifting.
void chico (int *X, int Y, int Z )

{*X = Y/ 4 - Z * 10 + *X * 8 ;}
int main()
{int J, K, L , M ;
cin >> J, K, L;
chico ( &J, K, L);
M = J - ( K + L);
cout << M;
return 0
}
Exercise 8.1 (Assembly Language Function)
void chico (int *X, int Y, int Z ) {*X = Y/ 4 - Z * 10 + *X *
8 ;}
chico: lw $t0, 0($sp) # Get &X
lw $t1, 4($sp) # Get value of Y
lw $t2, 8($sp) # Get value of Z
asr $t1, $t1, 2 #Y/ 4
sll $t3, $t2, 1
sll $t2, $t2, 3
add $t2, $t2, $t3 # Z * 10
sub $t1, $t1, $t2 # $t1 gets partial result
lw $t3, 0($t0) # $t3 gets value of X
sll $t3, $t3, 3 #X *8
add $t3, $t1, $t3 # $t3 gets result
sw $t3, 0($t0) # J is assigned the result
jr $ra
Exercise 8.1 Main Program
main:
addiu $sp, $sp, -16 # Allocate for 4 Local Main Var J,K,L,M
<<<<1
li $v0, 5
syscall
sw $v0, 0($sp) # Put value for J : $s0
move $s0, $v0
li $v0, 5
syscall
sw $v0, 4($sp) # Put value for K : $s1
move $s1, $v0
li $v0, 5
syscall
sw $v0, 8($sp) # Put value for L :$s2
move $s2, $v0
addi $sp, $sp, -12 # Allocate for 3 Par. <<<<<<<<<2
addi $s3, $sp, 12 # Calc. address of J <
sw $s3, 0(sp) # Put address of J on stack <
sw $s1, 4($sp) # Put value of K on stack <
sw $s2, 8($sp) # Put value of L on stack <
jal chico <
addiu $sp, $sp, 12 # Deallocate <<<<<<<<<<<<<<<2
Exercise 8.1 Main Program Continued
M = J - ( K + L);
lw $s0, 0($sp) # Get the latest value for J

add $s1, $s1, $s2 #K+L
sub $a0, $s0, $s1 # M = J - (K+L)
li $v0, 1
syscall # Print M
addiu $sp, $sp, 16 # De-allocate 4 Local Main Var

<<<<<<<<<<1
li $v0, 10
syscall
Programming
Lesson #26
Exercise 8.2
MUL32 ( m, n, p, f)
Write a function MUL32( m, n, p, f) that will find the 32-bit product “p”
of two arguments m and n. If the two’s complement representation of
the product cannot be represented with 32 bits, then the error flag “f”
should be set to 1 otherwise the error flag is set to 0.
Pass all arguments on the stack.
Mul32:
lw $t3, 0($sp) # Get m
lw $t4, 4($sp) # Get n
mult $t3, $t4
xor $t5, $t3, $t4 # Get correct sign for prod
mflo $t6 # $t6 = 32 bit product
xor $t7, $t5, $t6 # compare signs
bltz $t7, ovf
mfhi $t8 # $t8 = Upper 32-bits of prod
bgez $t5, pos
addui $t8, $t8, 1 # Check if all upper bits are 1
pos: bnez $t8, ovf
sw $t6, 8($sp) # product
sw $0, 12($sp) # ok
jr $ra
ovf:
li $t8, 1 # overflow
sw $t8, 12($sp) # occurred
jr $ra
Exercise 8.3
Adduovf ( x, y, s)
Write a function Adduovf( x, y, s) that will find the 32-bit sum “s”
of two unsigned arguments “x” and “y”.
An exception should be generated if the unsigned representation

of the sum results in overflow.
Perform all communication on the stack.

Hint:
A carry out at the most Significant Digit (MSD)

is Overflow for unsigned numbers.
Adduovf ( x, y, s)
Adduovf:
lw $t3, 0($sp) # Get x
lw $t4, 4($sp) # Get y
addu $t5, $t4, $t3 # Get sum
sw $t5, 8($sp) # Put sum on stack
xor $t6, $t3, $t4 # Checking MSD of x and y
bltz $t6, diff
bgez $t3, ok
overflow:
lui $t3, 0x7FFF
ori $t3, $t3, 0xFFFF
addi $t3, $t3, 1
ok: jr $ra
diff: bgez $t5, overflow # Checking MSD of sum

jr $ra
Exercise 8.4
Write a function Add64 that will perform a 64-bit addition: x = y + z,
where the values for x, y, and z are stored as two 32-bit words each:
Add64(x1: $t1, x0: $t0, y1: $t3, y0: $t2, z1: $t5, z0: $t4)
All six parameters are passed on the stack. If the 64-bit sum results in
overflow an exception should be generated.

After writing your code, calculate the performance indexes:
Space:_________________(Words of code)
Time: _________________(Maximum number of clock cycles to execute)
$t3 $t2
$t5 $t4
$t1 $t0
x1 Sum x0

Add64:
lw $t3, 8($sp) # Get y upper
lw $t2, 12($sp) # Get y lower
lw $t5, 16($sp) # Get z upper
lw $t4, 20($sp) # Get z lower
addu $t0, $t2, $t4 # add lower half
add $t1, $t3, $t5 # add upper half
xor $t6, $t2, $t4 # Checking for a carry to upper half
bltz $t6, diff
same: bgez $t2, fini
carry addi $t1, $t1, 1 # Generate carry to upper
fini: sw $t1, 0($sp) # Return x upper
sw $t0, 4($sp) # Return x lower
jr $ra
diff:
bgez $t0, carry
b fini
Exercise 8.5
When the MIPS mult instruction is executed, a 64-bit product is produced.
Many programs doing numerical calculations are designed to process only 32-bit results.
For applications written to perform 32-bit precision arithmetic, it is extremely important
to detect when the product of two numbers can not be represented with 32 bits, so that some
alternative procedures may be invoked.
Write a reentrant library function anyone could use, called MUL32(m, n, p).
All function parameters will be passed on the stack. This function should provide the
following features:
1. If the product of the two input arguments m and n cannot be represented with 32 bits
(assuming the two’s complement number system), then an exception should be generated.
2. This function should also provide the following optimization features:
(a) Check if m or n is zero, and return zero without taking 32 clock cycles to execute
the mult instruction.
(b) Check if m or n is plus one (1) or minus one (-1), and return the correct result
without taking 32 clock cycles to execute the mult instruction.
(c) Check if m or n is plus two (2) or minus two (-2), and return the correct result
without taking 32 clock cycles to execute the mult instruction.
If the product cannot be represented with 32-bits, then an exception should be generated.
Exercise 8.5 Continued
Provide inline comments and write a paragraph in English to describe all of the
conditions that your code tests for to detect overflow.
(HINT—The XOR instruction can be useful when writing this function.)

With this function you will demonstrate how to write MIPS assembly language code
involving nested function calls. Write a function to perform a vector product.
vectorprod (&X, &Y, &Z, N, status). Vectorprod will call the MUL32 function.
Use the stack to pass arguments. The in parameters are the starting address of three
different word arrays (vectors) : X, Y, Z, and an integer value N specifying the size
of the vectors. Status is an out parameter to indicate if overflow ever occurred while
executing this function. The procedure will perform the vector product:
Xi = Yi * Zi ; with i going from 0 to N – 1
Write a MIPS assembly language main program that could be used to test the
vectorprod function.
Programming
Lesson #27
A Pipelined Implementation of the MIPS Architecture
PC
Data Cache
Rs ALU
IR Result
Address
=
Data
Rd In
Register Rt
File
Instruction
Cache
Write Back
The True Branch Instructions
Branch if Equal: beq Rs, Rt, Label
Branch if Greater Than or Equal to Zero: bgez Rs, Label
Branch if Greater Than or Equal to Zero and Link: bgezalRs, Label
Branch if Greater Than Zero: bgtz Rs, Label
Branch if Less Than or Equal to Zero: blez Rs, Label
Branch if Less Than Zero and Link: bltzal Rs, Label
Branch if Less Than Zero: bltz Rs, Label
Branch if Not Equal: bne Rs, Rt, Label
Exercise 9.1
Taking into consideration delayed branches and delayed loads,
write a MIPS function to search through an array “X” of “N” words
to find how many of the values are evenly divisible by four.
The address of the array will be passed to the function using
register $a0, and the number of words in the array will be passed
in register $a1. Return the results in register $v0.
Original Code - Modified Code
Div4:
Div4:
li $v0, 0
li $v0, 0
b skip
li $t3, 3
li $t3, 3
b skip
loop:
loop:
nop
lw $t2, 0($a0)
and $t0, $t2, $t3
addi $a0, $a0, 4
bnez $t0, skip
and $t0, $t2, $t3
addi $a0, $a0, 4
bnez $t0, skip
addi $v0, $v0, 1
addi $v0, $v0, 1
skip:
skip:
addi $a1, $a1, -1
addi $a1, $a1, -1
bgez $a1, loop
bgez $a1, loop
lw $t2, 0($a0)
jr $ra
jr $ra
nop
Exercise 9.2
Taking into consideration delayed branches and delayed
loads,
Write a MIPS function to sort an array ‘“ Z ” of ‘“N” words into ascending
order using the bubble sort algorithm.
The address of the array and the value N will be passed to the function
on the stack. Show how the sort function is called.
Original Code to Call Sort(&Z, 1000) Modified Code to Call Sort(&Z, 1000)
addi $sp, $sp, -8 addi $sp, $sp, -8
la $t0, z la $t0, z
sw $t0, 0($sp) sw $t0, 0($sp)
li $t0, 1000 li $t0, 1000
sw $t0, 4($sp) jal sort
jal sort sw $t0, 4($sp)
addi $sp, $sp, 8 addi $sp, $sp, 8
BubSort: BubSort:
lw $t0, 4($sp) lw $t0, 4($sp) #N
again: li $t2, 0
addi $t0, $t0, -1 again:
li $t2, 0 addi $t0, $t0, -1
lw $t3, 0($sp) lw $t3, 0($sp) &Z
move $t1, $t0, move $t1, $t0,
loop: loop:
lw $t8, 0($t3) lw $t8, 0($t3)
lw $t9, 4($t3) lw $t9, 4($t3)
ble $t8, $t9, next addi $t1, $t1, -1
sw $t8, 4($t3) ble $t8, $t9, next
sw $t9, 0($t3) nop
li $t2, 1 sw $t8, 4($t3)
next: sw $t9, 0($t3)
addi $t3, $t3, 4 li $t2, 1
next:
addi $t1, $t1, -1 bgtz $t1, loop
bgtz $t1, loop addi $t3, $t3, 4
bnez $t2, again
bnez $t2, again li $t2, 0
jr $ra jr $ra
nop
Programming
Lesson #28
Exercise 9.3
Write a function Adduovf( x, y, s) that will find the 32-bit sum “s”
of two unsigned arguments “x” and “y”.
An exception should be generated if the unsigned representation

of the sum results in overflow.
Label Op-Code Dest. S1, S2 Label Op-Code Dest. S1, S2
adduovf: adduovf:
lw $t3, 0($sp) lw $t3, 0($sp)
lw $t4, 4($sp) lw $t4, 4($sp)
addu $t5, $t4, $t3 nop
sw $t5, 8($sp) addu $t5, $t4, $t3
xor $t6, $t3, $t4 xor $t6, $t3, $t4
bltz $t6, diff bltz $t6, diff
bgez $t3, ok nop
overflow: bgez $t3, ok #ok
lui $t3, 0x7FFF overflow:
ori $t3, $t3, 0xFFFF ori $t3, $t3, 0xFFFF
addi $t3, $t3, 1 addi $t3, $t3, 1
ok: jr $ra ok: jr $ra
sw $t5, 8($sp)
diff: bgez $t5, overflow
jr $ra diff: bgez $t5, overflow
lui $t3, 0x7FFF
jr $ra
nop
Exercise 9.4
write a MIPS, function to return the Nth element in the
Fibonacci sequence.
The value N is passed to the function on the stack, and the

Nth Fibonacci number E is returned on the stack.
If N is greater than 46 overflow will occur, so return a value of 0

if N is greater than 46. Also show an example of calling this function
to return the 10th element in the sequence. The first few numbers
in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5 . . . .
Fib: FibD:
lw $t0, 0($sp) lw $t0, 0($sp)
bltz $t0, error li $t2, 1
addi $t1, $t0, -46 bltz $t0, Herror
bgtz $t1, error addi $t1, $t0, -46
li $t1, 0 bgtz $t1, Herror
li $t2, 1 move $t3, $t0
move $t3, $t0 addi $t0, $t0, -1
addi $t0, $t0, -1 blez $t0, Hdone
blez $t0, done li $t1, 0
loop: Hloop:
add $t3, $t2, $t1 add $t3, $t2, $t1
move $t1, $t2 addi $t0, $t0, -1
move $t2, $t3 move $t1, $t2,
addi $t0, $t0, -1 bgtz $t0, Hloop
bgtz $t0, loop move $t2, $t3
done: Hdone:
sw $t3, 4($sp) jr $ra
jr $ra sw $t3, 4($sp)
error: Herror:
sw $0, 4($sp) jr $ra
jr $ra sw $0, 4($sp)
Embedded Processors
Memory Mapped I/O

Exercise 10.1
Random(&X, N)
Write a function that will generate and store “N” random numbers
into an array “X”. Use the value in register $ra as the initial seed value.
A possible algorithm for generating random numbers appears below:

$a0 = Mem($sp)
$a1 = Mem($sp+4)
$t0 = $ra
for ( ; a1> 0; a1 = a1 –1)
{$t0 = $t0 * 2743 + 5923
Mem($a0) = t0
$a0 = $a0 + 4
}
return
random:
$t0 = $ra
$t1 = 2743
ranloop:
t0 = $t0 * $t1
$t0 = $t0 + 5923
Mem($a0) = $t0
$a0 = $a0 + 4
$a1 = $a1, -1
if ($a1 > 0) go to ranloop
return
.globl random
.text
random:
move $t0, $ra
li $t1, 2743
ranloop:
mult $t0, $t1
mflo $t0
addiu $t0, $t0, 5923
sw $t0, 0($a0)
addi $a0, $a0, 4
addi $a1, $a1, -1
bgtz $a1, ranloop
jr $ra
Testing the Random function
.data
x: .space 512
nl: .asciiz "\n"
.text
main:
li $a1, 128
la $a0, x
jal random
la $s7, x
li $s6, 128
addi $sp, $sp, -8
sw $s7, 4($sp)
sw $s6, 8($sp)
jal sort #call Sort(&x, N)
addi $sp, $sp, 8
Printing results of test
loop:
li $s0, 7
inside:
lw $a0, 0($s7)
addi $s7, $s7, 4
jal hexout
addi $s0, $s0, -1
bgez $s0, inside
li $v0, 4
la $a0, nl
syscall # new line
addi $s6, $s6, -8
bgtz $s6, loop
li $v0, 10
syscall

MIPS Assembly Language Programming: Lesson #1

Uploaded by

Copyright:

Available Formats

MIPS Assembly Language Programming: Lesson #1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MIPS Assembly Language Programming: Lesson #1

Uploaded by

Copyright:

Available Formats

MIPS Assembly Language

Will become familiar with what compilers do

Acquire an understanding of how computers are built

Open new opportunities in the field of embedded

• Basic Computer Organization

2 $v0 Return values

Address Instruction Register (IR)

Reg. File[Rt] = Memory[Address]

• Arithmetic, Logic, and Shifting Instructions

When using pseudocode to document an assembly

Use a word processor to create the following program file.

li $v0, 10 # terminate program

MUST HAVE A BLANK LINE AT THE END OF THE TEXT FILE

2.1 Using Appendix A, translate each of the following pseudocode expressions

Reg. File[Rt] = Memory[Address]

Polynomial Expansion of a Binary Number (Base 2)

00101101 = 45 (1, 2, 5, 11, 22, 45)

N= - d7x2 + d6x2 + d5x2 + d4x2 + d3x2 + d2x2 + d1x2 +d0x2

Notice the Minus sign

*** You need to memorize powers of 2 ***

For example, the binary value 00011010 is 26 in decimal.

To find the value minus 26 in binary we perform the

The result is the value minus 26 in binary.

The value 68 as an 8-bit binary number is: 01000100

E2.5 sra $t0, $s0, 3 1

3.13 Convert the base 8 number 204 to decimal

3.22 The following subtract instruction is located at address 0x00012344.

loop: addi $t4, $t4, -8

sub $t2, $t2, $t0

bne $t4, $t2,loop

Perform the following arithmetic operations on X and Y. Show your answers as

X+Y X-Y Y-X

10010100 10010100 00101100

The following code segment is stored in memory starting

loop: lw $t0, 0($a0) # t0 = Mem[a0]

This is an example of an addressing structure called Little Indian

Use the information in Appendix C to verify that 0x3402000A

Op-Code Rs Rt Rd Function Code

loop: addu $a0, $0, $t0 # 0x00082021

In Appendix C we are shown how Store Byte is encoded in binary

sb $4, 4($22) sb $a0, 4($s6)

In Appendix C we are shown how Shift Right Logical is encoded in binary

srl $23, $23, 4 srl $s7, $s7, 4

[0x00082021 addu $4, $0, $8 ; 3: addu $a0, $0, $t0

0x2a2a2a2a 0x69644120 0x4120736f 0x6f67696d 0x48202d20 0x20657661

**** i d A A s o ogim H - eva

**** Adios Amigo – Have

In Hexadecimal it is printed out as: 0x04ABF54D

Pseudo Code for the Algorithm:

how how the following PSEUDOCODE expression can be efficiently

sra $t0, $s0, 3

jal sum # Call sum

move $a0, $v0 # move value to be printed to $a0

Everyone individually develops a pseudo- code solution to the

Groups compare their pseudo-code and refine their algorithms.

Everyone individually develops an assembly language solution to the

FM = The number of words of assembly language code plus the

andi $t3, $t1, 1 #

Also show an example code segment that calls

* You need to memorize powers of 2 *