MOVEA.L START,A0
MOVEA.L N,A1
ADDA.L A0,A1
MOVEA.L A0,A2
MOVE.B (A0)+,D0
LOOP CMP.B (A0)+,D0
BLE NXT
LEA -1(A0),A2
MOVE.B (A2),D0
NXT CMPA.L A0,A1
BGT LOOP
MOVE.L A2,DESIRED
- What does this program do? (Your answer must describe the program
at a high level, such as ``It's C's strlen().'' Answers which
state, ``It moves this and adds that,'' merely cause the instructor to
pull out his hair and earn you no credit.)
The program scans the string starting at the address in memory location START. The number of characters to be scanned is read from memory location N. The address of the smallest character in the string is stored at memory location DESIRED.
- How many 16-bit words are needed to store this program in memory?
16:
1: MOVEA.L START,A0 # 2 words, 2 data accesses. 2: MOVEA.L N,A1 # 2 words, 2 data accesses. 3: ADDA.L A0,A1 # 1 word. 4: MOVEA.L A0,A2 # 1 word. 5: MOVE.B (A0)+,D0 # 1 word, 1 data access. 6:LOOP CMP.B (A0)+,D0 # 1 word, 1 data access. 7: BLE NXT # 1 word. 8: LEA -1(A0),A2 # 2 words. 9: MOVE.B (A2),D0 # 1 word, 1 data access. 10:NXT CMPA.L A0,A1 # 1 word. 11: BGT LOOP # 1 word. 12: MOVE.L A2,DESIRED # 2 words, 2 data accesses.
Instructions 1, 2, and 12 utilize short direct addressing, requiring one extension word for the 16-bit direct address. Those instructions move a long word (32 bits) between memory and a register, requiring 2 data accesses. Instruction 8 uses indexed addressing, requiring one extension word for the offset. Interestingly, the two branch instructions can store the offset within the instruction itself. The three byte movement ( .B instructions) each perform one memory access to transfer data.
- If the data is stored in memory like this:
how many memory accesses (counting both data and instruction accesses) are performed in executing the program? Note that the characters are stored in memory using an ASCII encoding.
Note that the original figure was wrong, but no one's answer seemed to hinge on it. The smallest character in the string is D, so the branch to NXT is always taken; instructions 8 and 9 are never executed. 46 memory accesses are performed in executing the program.
What is the value stored in DESIRED?
1008, the address of D.
All calculations should be done in registers.
# Pseudo code:
#
# print prompt;
# read n;
# if (n < 1)
# return;
# else if (n == 1)
# print "0";
# return;
# eif
#
# print "0\n1\n";
# oldest = 0;
# old = 1;
# n -= 2;
#
# for ( ; n > 0; --n)
# current = old + oldest;
# print current;
# oldest = old;
# old = current;
# efor
#
# return;
.data
prompt: .asciiz "Enter n: "
nl: .asciiz "\n"
ans1: .asciiz "0\n"
ans2: .asciiz "0\n1\n"
.text
.globl main
main: li $v0, 4 # Print prompt.
la $a0, prompt
syscall
li $v0, 5 # Read n.
syscall
move $t0, $v0 # n in $t0.
bge $t0, 1, elif # n < 1.
li $v0, 10 # Exit.
syscall
elif: bne $t0, 1, eif # n == 1.
li $v0, 4
la $a0, ans1
syscall
li $v0, 10 # Exit.
syscall
eif: li $v0, 4 # n > 1.
la $a0, ans2
syscall
li $t1, 0 # oldest in $t1.
li $t2, 1 # old in $t2.
addi $t0, $t0, -2 # Decrease n by 2.
for: beqz $t0, efor
add $t3, $t2, $t1 # current is old + oldest.
li $v0, 1 # Print current.
move $a0, $t3
syscall
li $v0, 4 # Print newline.
la $a0, nl
syscall
move $t1, $t2 # Update old, oldest.
move $t2, $t3
addi $t0, $t0, -1
b for
efor: li $v0, 10 # Exit.
syscall
What is the largest value of n that your program can handle?
47.
Use a subroutine which prompts the user to enter a string and then reads the string. This subroutine will be called twice by your main program and should take two parameters: the starting address of the array into which the string is placed, and the length of the array. Use registers $a0 and $a1 for passing the parameters.
Use the jal instruction to call your subroutine. The return address will be stored in register $31. If you don't make any nested subroutine calls (there's no need to) and you don't modify $31 (you shouldn't), you can just leave the return address there. To return to the instruction following the subroutine call use this instruction:
jr $31
Here's a hint as to how to structure your program:
.data # Declarations, constants for main.
...
.text
.globl main
main: ...
jal gets # Call subroutine.
...
li $v0, 10
syscall
.data # Declarations, constants for gets.
...
.text
gets: ...
jr $31
# Pseudo code:
#
#
# main:
#
# gets(str1, 80);
# gets(str2, 80);
#
# ps1 = str1;
# ps2 = str2;
#
# // Spim's read string syscall includes the newline as part of the
# // string read into an array. So, '\n' terminates the string.
# while (*ps1 != '\n' && *ps2 != '\n' && *ps1 == *ps2)
# ++ps1;
# ++ps2;
# ewhile
#
# print str1;
#
# if (*ps1 < *ps2)
# print "less than\n";
# else if (*ps1 == *ps2)
# print "equal to\n";
# else
# print "greater than\n"
# eif
#
# print str2;
#
# return;
#
#
# gets(s, l):
#
# print prompt;
# read string into s;
# return;
.data
str1: .space 80
str2: .space 80
less: .asciiz "less than\n"
equal: .asciiz "equal to\n"
greater: .asciiz "greater than\n"
.text
.globl main
main: la $a0, str1 # Read str1.
li $a1, 80
jal gets
la $a0, str2 # Read str2.
li $a1, 80
jal gets
la $s0, str1 # $s0 is pointer into str1.
la $s1, str2 # $s1 is pointer into str2.
lb $s2, 0($s0) # $s2 is current character of str1.
lb $s3, 0($s1) # $s3 is current character of str2.
while: beq $s2, 10, ewhile # 10 is ASCII for newline.
beq $s3, 10, ewhile
bne $s2, $s3, ewhile # Found difference in strings.
addi $s0, $s0, 1 # Increment pointers.
addi $s1, $s1, 1
lb $s2, 0($s0) # Get next characters.
lb $s3, 0($s1)
b while
ewhile: li $v0, 4 # Print str1.
la $a0, str1
syscall
li $v0, 4 # Compare and print comparison.
bge $s2, $s3, elif # str1 < str2.
la $a0, less
b eif
elif: bgt $s2, $s3, else # str1 == str2.
la $a0, equal
b eif
else: la $a0, greater # str1 > str2.
eif: syscall
li $v0, 4 # Print str2.
la $a0, str2
syscall
li $v0, 10 # Exit.
syscall
######################################################################
# gets
######################################################################
.data
prompt: .asciiz "Enter a string: "
.text
gets: move $t0, $a0 # Save argument.
li $v0, 4 # Print prompt.
la $a0, prompt
syscall
li $v0, 8 # Read string.
move $a0, $t0 # Restore argument.
syscall
jr $31 # Return.