Part 6 - Extended Assembly Language
The assembler extends bare machine language. Registers have mnemonic names. Pseudoinstructions extend the bare hardware.
The Extended Assembler
The basic assembler creates a view of the processor one level above raw machine code. Machine code uses bit patterns to specify machine operations, registers, and addresses. In basic assembly, you can specify these with symbols. Each instruction for the basic assembler corresponds directly to one machine instruction.
The extended assembler creates a view that is at an even higher level. It implements an abstract machine that has a much richer instruction set than the actual MIPS hardware. Many of the statements accepted by the extended assembler correspond to several machine instructions.
Chapter Topics:
- Register mnemonic names
- Pseudoinstructions and the pseudocomputer
movepseudoinstructionlipseudoinstructionlapseudoinstructionlwpseudoinstructionswpseudoinstructionnoppseudoinstruction
SPIM can act as either a basic assembler or an extended assembler. Previous chapters explained the basic assembler so that you could see how actual hardware works. This chapter makes greater use of the extended assembler features.
Question 1
(Review:) What is a general purpose register?
Answer
A register is an electronic device that holds bit patterns. A general purpose register is a register that is visible to assembly language. The floating point registers, although visible to assembly language, are not regarded as general purpose registers.
Register mnemonics
Although the registers are called "general purpose", it is conventional in software to use specific registers for specific purposes. This is not required by hardware. It is just a way for programmers to avoid confusion by establishing conventions. The extended assembler uses mnemonic names for registers that show how they are used.
For example, registers $8 through $15 are conventionally used to hold temporary values. Mnemonic names for these registers are $t0 through $t7.
As far as hardware is concerned, only registers $0 and $31 are different from the rest ($0 is always full of zeros and $31 is automatically used by some subroutine linkage instructions to hold the return address). The remaining registers are electronically identical. It is a software convention to use different sets of registers for different purposes.
Question 2
Are programs written in extended assembly code executed on the same MIPS processor we have been looking at?
Answer
Yes. No matter what language it is written in, source code is ultimately translated into machine code that executes directly on the processor.
Extended assembler
The extended assembler allows you to use mnemonic register names in place of hardware register numbers. This helps you keep track of what you are doing with the registers. The assembler replaces register mnemonics with the usual register numbers. Of course, the assembly instructions are ultimately translated into machine code.
When acting as an extended assembler, SPIM implements many features that are not provided by MIPS hardware. The extended assembler accepts source code that uses extensions to basic assembly language. The extensions in the source code are replaced with basic assembly language, and then translated into machine code.
The picture shows how extended assembly code is translated into basic assembly code by the extended assembler. Then the basic assembly code is translated into machine code by the basic assembler. Although the picture is correct in concept, in actual practice the middle steps are combined and the extended assembler translates extended assembly directly to machine code.
By using the extended assembler the programmer may program in a more convenient language, but the underlying hardware remains unchanged. Of course high-level languages go even further: Rather than extending the assembly language of the machine, a completely different programming language is translated into the machine code for the underlying hardware.
Question 3
The programs in the previous chapters used registers $8 through $15. What are the mnemonic names for these registers?
Answer
$8 through $15 == $t0 through $t7
Subroutines and registers for temporary values
Most assembly programs, like most higher-level language programs, are collections of subroutines. The main program calls upon a sequence of subroutines to accomplish its task. And, of course, subroutines themselves may call other subroutines. (In Java, software is collected into objects, and the equivalent of a subroutine is a method.)
Subroutines use local variables, variables that are not used anywhere but in the subroutine. The temporary registers $t0-$t7,$t8, and $t9 and the saved registers $s0-$s7 are used for local variables (or for the same idea in assembly language).
When you write a program the temporary registers and saved registers are yours to use however you want. But, by software convention, the temporary registers may be changed by any subroutine you call. The saved registers are not changed by a subroutine call. Here is an example:
ori $t0,$0,32 # load 32 into a temp register
ori $s0,$0,13 # load 13 into a saved register
jal subrout # subroutine call (don't worry about
# the details of this, now).
sll $0,$0,0 # branch delay slot
back: addu $s0,$s0,$t0 # return from subroutine;
# temp register $t0 may have changed.
# saved register $s0 has not changed.
The statement at back is in error. The temporary register $t0 may have been changed by the subroutine subrout. It might not contain the value 32 that the first statement put in it.
If the programmer of subrout did not use $t0, it will not change. However, in the future, subrout might be changed to involve $t0, and that would break the above code.
Question 4
Is the following code fragment correct?
ori $s0,$0,13 # load 13 into a saved register
ori $s1,$0,45 # load 45 into a saved register
jal subrout # subroutine call (don't worry about
# the details of this, now).
sll $0,$0,0 # branch delay slot
back: addu $s0,$s0,$s1 # return from subroutine
Answer
Yes — the fragment makes no assumptions about what is in temp registers after the subroutine call.
Other registers
The registers are grouped into those used as variables and arguments in subroutines ($0, $v0-$v1, $a0-$a3, $t0-$t9, $s0-$s7), and those used for other purposes. Subroutines are discussed in a future chapter. The other uses are discussed as the topic arises.
The most fundamental part of an operating system is the kernel. The rest of the OS is mostly implemented using the functions provided by the kernel. Two registers, $k0 and $k1, are reserved for the kernel. Applications programs (and most OS subroutines) should not touch them.
SPIM does not come with an OS. But it loads a trap handler, if requested, which uses $k0 and $k1 as well as several of the temporary registers.
The registers $gp, $sp, and $fp are used as base registers to access to various parts of memory.
Question 5
What does the following assembly language instruction do?
addu $t5,$zero,$t7
It _____ the contents of register _____into register _____.
Answer
It copies the contents of register $t7 into register $t5.
Pseudoinstructions
The addu instruction, used as above with register $zero, copies a bit pattern from the source register into the destination register. This is usually called a move operation, although the source register does not change. It is often convenient to move a value from one register to another.
It is awkward to say "add" when you mean "move". The extended assembler allows you to use the mnemonic move instead of addu. This mnemonic does not correspond to a new machine instruction. It is just a way of asking for the same instruction by using a more intuitive mnemonic. It is a pseudoinstruction that the assembler translates into the appropriate basic assembly instruction.
A pseudoinstruction is an instruction that the extended assembler replaces with one or more basic assembly instructions.
The extended assembler implements many pseudoinstructions. Sometimes they are just convenient re-naming of basic assembly instructions. Other times they correspond to a small, convenient sequence of basic assembly instructions. Here is the move pseudoinstruction:
move d,s # copy the contents of
# the source register s
# to the destination register d
# (pseudoinstruction)
The registers d and s can be specified by using register mnemonic names (such as $t5 or $zero) or by using register numbers (such as $13 or $0). This is true for all instructions of the extended assembler.
Question 6
Write the instruction that moves (copies) the contents of register $t3 into register $s1.
_____ _____ , _____
Answer
move $s1,$t3
Assignment statement
It is easy to get confused about the order of operands. The move instruction is intended to be read like an assignment statement of a higher level language:
j = val;
The contents of val is copied into the variable j.
move $s1,$t3
The contents of $t3 is copied into the register $s1.
Question 7
(Review:) What is in register $t5 after the following instruction: ori $t5,$0,74
Answer
ori $t5,$0,74 puts the binary representation of 74_10 into register $t5.
Load immediate
The ori instruction, used as above, copies a bit pattern from the instruction into the destination register. (Recall that the 16 bit immediate operand is zero-extended into 32 bits.) This operation is usually called a load immediate operation — it loads a register with a value that is immediately available (without going to memory).
You might wish that there were a mnemonic for "load immediate". There is. The extended assembler includes the li mnemonic. The assembler translates this pseudoinstruction into the appropriate basic instruction.
li d,value # load register $d with the
# positive or negative integer
# "value". Value may be a
# 16 or a 32-bit integer.
# (pseudoinstruction)
Question 8
Translate the following pseudoinstruction into the corresponding basic assembly instruction (use mnemonic register names):
li $v0,12
ori _____ , _____ , _____
Answer
li $v0,12 == ori $v0,$zero,12
Several translations
The load immediate pseudoinstruction is useful for loading a register with an integer value. Here is another example:
li $t2,-156
This puts the two's complement representation of -156_10 into register $t2. However, this can not be done with ori because the immediate field of that instruction must be a 16-bit unsigned integer (which is zero-extended to 32 bits upon execution). Because the immediate value of the li is negative, a different translation is used:
li $v2,-156 == addiu $v2,$0,-156
(Remember that addiu sign-extends its immediate operand before performing the addition. Also remember that the u part of the mnemonic means that overflow will not cause a trap. The addiu instruction can be used with negative integers). The extended assembler translates li into different basic instructions depending on the sign of the immediate value.
Question 9
Can either basic instruction, ori or addiu, use an immediate value greater than 16 bits?
Answer
No. The machine instruction has a 16-bit field for the immediate value.
Two basic instructions
Machine instructions have fixed-sized fields. Immediate operands are always 16 bits. However, two machine instructions can be used to load a 32-bit register with the top half and bottom half of a 32-bit integer:
li $v1,0x12345678 == lui $v1,0x1234
ori $v1,$v1,0x5678
Here, li is translated into two basic instructions. The first loads the top half of $v1. The second uses the ori operation to load the bottom half. This is done for any integer (positive or negative) that requires more bits than an immediate operand can hold. So, the extended assembly language programmer has a very useful instruction:
li d,value # load register $d with the
# positive or negative integer
# "value". Value may be a
# any integer up to 32 bits.
# (pseudoinstruction)
The extended assembler automatically translates this pseudoinstruction into the most efficient sequence of actual instructions.
Question 10
Translate the following pseudoinstruction into basic assembly instructions:
li $t7,0xFF001234
==
lui $t7, _____
_____ $t7,$t7,0x1234
Answer
li $t7,0xFF001234
==
lui $t7,0xFF00
ori $t7,$t7,0x1234
The immediate operand of the above pseudoinstruction could represent a negative integer (notice that the "sign bit" is set). You don't have to use hex with li. You could have written: li $t7,-16772555.
Example program
Here is a tiny example program using load immediate. More practical examples follow in a few more pages.
## liEg.asm
##
.text
.globl main
main:
li $t0,43 # first value
li $t1,-96 # second value
li $t7,-16772555 # third value
addu $t0,$t0,$t1 # add the values
addu $t0,$t0,$t7 # leave result in $t0
Each li instruction in the above translates into a different basic instruction. To run the program in SPIM, first look in the settings menu. Put a check for "allow pseudo instructions" and remove the check from "bare machine".
Question 11
(Review: ) What is a symbolic address?
Answer
A symbolic address is the name used in source code for a location in memory.
Unknown addresses
A symbolic address stands for whatever location in memory a particular datum or instruction ends up at. Usually this is not known in advance. Often a program is built using several object modules, library modules, and assembler source files. (See Chapter One on separate assembly.) The various modules refer to locations in each other by using symbolic addresses. The actual addresses are determined by system software when all the modules are linked together and loaded into memory. It is very hard (and not necessary) for a programmer to determine what addresses various items will eventually have.
The assembler enables a programmer to refer to an address by a symbol, even when the address will not be known until much later in the process of building an executable. The assembler and subsequent systems software (linker and loader) keep track of the symbolic address until the address it represents is finally determined. Just before run time, everything is resolved. A machine language program and data can then be loaded into memory and executed.
Question 12
(Review:) The picture is a run-time snapshot of memory taken while a program is running. In the picture, what data is in the word starting at address 0x1000000C? _____
What is the address of the word containing 0x00000002? _____
Answer
What data is in the word starting at address 0x1000000C? 0x00000003
What is the address of the word containing 0x00000002? 0x10000008
Address and contents of an address
The contents of a word of memory may be any 32-bit pattern. The address of a word of memory is also a 32-bit pattern. Both types of data fit into a 32-bit register.
Sometimes you want the contents of word of memory to be loaded into a register. For example, you may wish to load the value 0x00000002. This is done with the lw instruction. Look at the picture. The value you wish to load is located in memory at address 0x10000008.
lw d,exp # Load register $d with the value at
# address "exp".
# "exp" is often a symbolic address.
# (pseudoinstruction)
Other times you want the address of a word in memory. For example, you may wish to load the address of the word in memory that holds the 0x00000002, This is done with the la instruction.
la d,exp # load register $d with the address
# described by the expression "exp".
# "exp" is often a symbolic address.
# (pseudoinstruction)
Usually the programmer does not know the exact addresses the linker and loader will use for things, so symbolic addresses are used with the lw and la instructions. If symbolic address val2 corresponded to the word that contains 0x00000002 in the above picture, then
lw $s0,val2
would load $s0 with 0x00000002, and
la $s1,val2
would load $s1 with 0x10000008.
Question 13
Have our previous programs put addresses in registers?
Answer
Yes: a base register contains an address. Also a pointer register (such as used with arrays and strings) contains an address.
Register with addresses
The previous chapters have put addresses into base registers. This was done with code similar to the following:
main: # Load the address of val2 into the base register
lui $10,0x1000 # top half
ori $10,$10,0x0008 # bottom half
lw $11,0($10) # Load contents of memory at the address
. . .
.data
val0: .word 0
val1: .word 1
val2: .word 2 # base register $10 points at "2"
val3: .word 3
val4: .word 4
val5: .word 5
Question 14
Is there something awkward about this code?
Answer
Yes: the programmer must know the address in advance.
Load address pseudoinstruction
It is not always possible to know the address in advance. Conveniently, symbolic addresses and systems software make this unnecessary. This happens by using the la mnemonic. This mnemonic does not correspond to a single machine instruction. It is a pseudoinstruction that the assembler translates into to several machine instructions.
la d,exp # load register $d with the address
# described by the expression "exp"
# "exp" is often a symbolic address
# (pseudoinstruction)
In this pseudoinstruction, exp is an expression that evaluates to a memory address. There are several possible forms for exp. Often it is a symbolic address. The la pseudoinstruction translates into different machine code instructions depending on exp.
Question 15
Does the la instruction access (look at) memory?
Answer
No.
LA example
At run time, la translates into one or several machine instructions that load the designated register with the required address. No memory access is done. (So there is no delay slot after this instruction.)
Here is the previous example code done using la:
main: # Load memory address:
la $10,val2 # load a 32-bit address into $10
lw $11,0($10) # Load contents of memory at the address into $11
. . .
.data
val0: .word 0
val1: .word 1
val2: .word 2 # base register $10 points at "2"
val3: .word 3
val4: .word 4
val5: .word 5
Question 16
This la instruction translates into two machine instructions. What two instructions does it translate into? (Answer with two instructions mnemonics.)
Answer
This la translates into a lui followed by a ori (just as we previously did by hand).
SPIM example
Here is a SPIM example using la. Execute the program by pushing F10 for each machine instruction. Look in the display of registers and observe that $t0 gets the address of val2. It now can be used as a base register for loading $t1 and $t2 with two words from memory.
## addEm.asm
## program to add two integers
##
.text
.globl main
main:
la $t0,val2 # put a 32-bit address into $t0
lw $t1,0($t0) # load value 2
lw $t2,4($t0) # load value 3
sll $0,$0,0 # load delay slot
addu $t1,$t1,$t2 # calc. sum
.data
val0: .word 0
val1: .word 1
val2: .word 2
val3: .word 3
val4: .word 4
val5: .word 5
Question 17
(Trick Question:) How many times will F10 be pushed?
Answer
Six! The la instruction is translated into two machine instructions, and F10 is pushed once for each.
SPIM run
Here is a run of the program. The SPIM listing shows the two machine instructions that the assembler used for the la pseudoinstruction in this context. (The assembler uses different machine instructions in different contexts.)
Look carefully at the two instructions that SPIM used for la. They both use register $1.
Question 18
In the register table. What is the mnemonic name for register $1?
Answer
$at, the assembler temporary register.
Assembler temporary register
The assembler temporary register is reserved for use in the machine instructions that pseudoinstructions are translated into. Often a pseudoinstruction is implemented as a short sequence of machine instructions that use $at. Here is how la was translated in the example:
la $t0,val2 == lui $1,4097
ori $8,$1,8
Sometimes a pseudoinstruction has the same mnemonic as a basic assembler instruction. For example, lw (load word) is a basic assembler instruction. As an assembler instruction, it is used like this:
lw $t1,8($t0) # load the word at address $t0+8
This instruction designates the address with a displacement (eight, in this case) to add to a base register ($t0, in this case). This corresponds exactly to one machine instruction. There is no other form for the non-extended assembler instruction. However, with the extended assembler, the following pseudoinstruction can be used:
lw $t1,exp # load value at address exp
The machine instruction lw uses a base register to form an address. The pseudoinstruction lw must be translated into instructions that also use a base register (since this is the only way MIPS instructions can address memory.)
Question 19
What base register is used?
Answer
The assembler temporary register, $at (which is also $1.)
Load word (pseudoinstruction)
The lw pseudoinstruction copies a word of data from memory into a register seemingly in one step:
lw d,exp # Load register $d with the value at
# address exp. exp can be any
# of several expression types
# that evaluate to an address
# (pseudoinstruction)
Here is a possible translation the pseudoinstruction lw. Say that the symbol data stands for the address 0x10000004.
lw $t0,data == lui $1,0x1000
lw $8,4($1)
The base address in $1 is 0x10000000 after the lui instruction executes. The lw instruction adds 4 to that address to form the desired address.
The extended assembler and its pseudoinstructions make it look like you are programming a pseudocomputer — a computer system that is richer in features and more convenient to program than the actual hardware. (Often this is called a "virtual computer"; but to avoid confusion I'll say that pseudoinstructions run on the pseudocomputer.) This idea of implementing a virtual machine on top of another machine (which may also be virtual) is very important in computer science.
The pseudocomputer built on top of the hardware is a layer of abstraction. When you write programs using the extended assembler and its pseudoinstructions you think in terms of the pseudocomputer and its capabilities. You can pretend that the pseudocomputer will directly execute your program.
Question 20
Should the lw pseudoinstruction be followed by a load delay slot? (Hint: look at its translation.)
Answer
Yes. The second instruction in its translation is a ordinary load instruction which requires a delay of one instruction before the loaded value can be used.
Store word (pseudoinstruction)
The nop pseudoinstruction translates into sll $0,$0,0. This is the "no operation" instruction we have been using all along.
nop # no operation.
# do nothing for one machine cycle.
# (pseudoinstruction)
The sw mnemonic is used both by the basic assembler and the extended assembler. As a pseudoinstruction it can store a register to memory in one instruction.
sw d,exp # Store register $d into the word at address exp.
# exp can be any of several expression types
# that evaluate to an address
# (pseudoinstruction)
Of course, this is implemented as several basic instructions.
Question 21
Play Pseudocomputer: translate the sw instruction into non-extended instructions:
sw $t0,someWord
translated as:
lui _____ , 0x1000
sw _____ , 12 ( _____ )
Answer
sw $t0,someWord == lui $1,0x1000
sw $8,12( $1 )
It would be OK to say $t0 for $8 and $at for $1.
Example program
Here is an example using the lw and sw instructions. The program starts out by loading data into several registers. Notice that the load delay slots of the load instructions are filled with useful instructions. This is possible because the data is not used until several instructions after each load. For example, the value for x is not used until four instructions later, so the lw that loads it has its load delay slot filled with a useful instruction.
The nop (no-operation) instructions are used to follow the rule that a mult instruction should not be started until two instructions after a mflo or mfhi instruction. (Usually our SPIM programs do not follow this rule because SPIM does not emulate that aspect of MIPS.)
## pseudoPoly.asm
## evaluate the polynomial ax2 + bx + c
##
.text
.globl main
main:
lw $t3,x # get x
lw $t0,a # get a
lw $t1,bb # get bb
lw $t2,c # get c
mult $t3,$t3 # x2
mflo $t4 # $t4 = x2
nop
nop
mult $t4,$t0 # low = ax2
mflo $t4 # $t4 = ax2
nop
nop
mult $t1,$t3 # low = bx
mflo $t5 # $t5 = bx
addu $t5,$t4,$t5 # $t5 = ax2 + bx
addu $t5,$t5,$t2 # $t5 = ax2 + bx + c
sw $t5,value # value = polynomial
.data
x: .word 4
value: .word 1
a: .word 20
bb: .word -2 # the SPIM assembler does not allow the label "b"
c: .word 5
This is a straightforward evaluation of the polynomial. By using Horner's method, and by cleverly filling some of the no-ops with instructions, the program could be greatly improved.
Question 22
What big assumption was made in writing this program?
Answer
The program assumes that all calculations fit into 32 bits.
Chapter quiz
Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.
Question 1
Register $8 is the first register conventionally used to hold temporary values. What is its mnemonic name?
- (A) $temp
- (B) $t0
- (C) $t1
- (D) $t8
Answer
B
Question 2
What is the mnemonic name of register $0?
- (A) zero
- (B) $zero
- (C) $z0
- (D) $t0
Answer
B
Question 3
Does the extended assembler translate assembly language into machine instructions not available to the basic assembler?
- (A) No. Extended assembly language is just an alternate syntax used to specify the same machine instructions.
- (B) No. The extended assembler uses many fewer of the actual machine instructions.
- (C) Yes. The extended assembler outputs instructions for the extended part of the processor.
- (D) Yes. The extended assembler is the only way to ask for floating-point operations.
Answer
A
Question 4
What is true just after the return from a call to a subroutine?
- (A) The temporary registers are the same as they were before the call, and the saved registers may have been altered.
- (B) The saved registers are the same as they were before the call, and the temporary registers have certainly been altered.
- (C) Values in the saved registers are safely stored in memory, but values in the temporary registers have not been saved.
- (D) The saved registers are the same as they were before the call, and the temporary registers may have been altered.
Answer
D
Question 5
What is the most fundamental part of an operating system?
- (A) The shell.
- (B) The peel.
- (C) The kernel.
- (D) The seed.
Answer
C
Question 6
Translate the following pseudoinstruction into basic assembly: move $t8,$t3
- (A)
addu $t3,$t8,$t3 - (B)
ori $t8,$0,$t3 - (C)
ori $t8,$t3 - (D)
addu $t8,$0,$t3
Answer
D
Question 7
Here is the load immediate pseudoinstruction: li d,value. What is true of value?
- (A) It may be any integer, positive or negative, that fits into 16 bits.
- (B) It may be any integer, positive or negative, that fits into 32 bits.
- (C) It may be any positive integer that fits into 32 bits.
- (D) It may be any positive integer that fits into 16 bits.
Answer
B
Question 8
How is the li d,value translated by the extended assembler?
- (A) It is always translated into the
addiubasic instruction. - (B) It is always translated into the one basic instruction.
- (C) How it is translated depends on the size and sign of the
value. - (D) It is always translated into two basic instructions.
Answer
C
Question 9
Inspect the following code:
.data
numa: .word 23
numb: .word 99
numc: .word -12
Which instruction puts the address of the word that contains 99 into register $s3?
- (A)
la $s3,numb - (B)
lw $s3,numb - (C)
lw $s3,99 - (D)
la $s3,4(numa)
Answer
A
Question 10
Inspect the following code (the same as above):
.data
numa: .word 23
numb: .word 99
numc: .word -12
Which instruction stores the contents of register $s3 into memory at numc?
- (A)
sa $s3,numc - (B)
sw $s3,numc - (C)
sw numc,$s3 - (D)
move $s3,numc
Answer
B
Programming exercises
For these programming exercises, use only those instructions that have been discussed so far in these notes:
Basic Instructions
add | div | mflo | slt, slti |
addi | divu | mult | sltu, sltiu |
addiu | j | multu | sra |
addu | lb | nor | srl |
and | lbu | or | sub |
andi | lh | ori | subu |
beq | lhu | sb | sw |
bgez | lui | sh | xor |
bltz | lw | sll | xori |
bne | mfhi |
PseudoInstructions
la | lw | nop |
li | move | sw |
In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File OFF, Delayed Branches ON, Delayed Loads ON, Mapped IO OFF, Quiet OFF.
In these programs do not set up a base register as has been done in previous chapters. Use the lw and sw instructions with symbolic addresses. Use mnemonic register names in your programs and use registers in their conventional ways.
Exercise 1 (*) - Horner's Method
(see Exercise 4 of chapter 15)
Evaluate the following polynomial using Horner's method: ax3 + bx2 + cx + d
Now the values for the coefficients a, b, c, d as well as for x come from the .data section of memory:
.data
x: .word 7
a: .word -3
bb: .word 3
c: .word 9
d: .word -24
result: .word 0
Use the pseudoinstruction lw to get the coefficients from memory, and sw to write the result back to memory.
(Recall that the symbolic address b cannot be used in SPIM.)
Exercise 2 (*) - pair-wise addition
Declare three arrays, each of the same size:
.data
size .word 7
array1: .word -30, -23, 56, -43, 72, -18, 71
array2: .word 45, 23, 21, -23, -82, 0, 69
result: .word 0, 0, 0, 0, 0, 0, 0
Initialize a base register for each array (use the la instruction.) Now implement a loop that adds corresponding elements in the first two arrays and stores the result in the corresponding element of the result array. Do this by moving each of the three base registers to its next array element after each addition.
Exercise 3 (***) - string comparison
Declare two null-terminated strings:
.data
result: .word 0
string1: .asciiz "puffin"
string2: .asciiz "puffins"
Initialize a base register for each string (use the la instruction.) Write a program that sets result to 1 if the two strings are equal and to 0 if the strings are not equal.
Two strings are equal if they are the same length and contain the same character in each location. Otherwise the strings are not equal.
Test your program for a variety of strings. You will have to edit the data section of your program for each pair of strings tested.
Extra: write the program so that it does case insensitive string comparison. Here, two strings are equal if they are the same length and have the same letter (disregarding case) in each location.
The SPIM Exception Handler
Up until now, your programs have been running with SPIM used as a "bare machine" — a computer with no machine code in it but your own. Most computer systems run under the control of an operating system. Application programs use the services of the operating system to do input and output and other system tasks.
SPIM does not have an operating system, but it includes a small exception handler that provides a set of services that is a great help in writing assembly programs.
Chapter Topics:
- The
syscallinstruction. - SPIM exception handler.
- Exception handler services:
- halt program
- print string
- read string
- print integer
- read integer
- Hello World example.
- Library Fine example.
Question 1
In an actual bare machine (real hardware) do you suppose that it is easy to write a character to the terminal?
Answer
No.
syscall
In even the simplest computer, putting a character on the screen involves many instructions and a detailed knowledge of the video card. Let's leave this topic until later (perhaps years later). SPIM includes an "exception handler" that simulates a tiny operating system that can do input from the keyboard and output to the monitor.
Assembly language programs request operating system services using the syscall instruction. The syscall instruction transfers control to the operating system which then performs the requested service. Then control (usually) returns to the program. (This description leaves out many details).
syscall # ask the operating system to perform a service
Different operating systems use this instruction in different ways. For the SPIM exception handler it is used like this:
li $v0,code # Load $v0 with the "code" number of an OS service.
....... # Put parameters for the service in
....... # registers $a0, $a1 or $f12 (see below).
syscall # Invoke the operating system.
# Return value (if any) is in $v0 or $f0
#
The syscall instruction causes an exception, which transfers control to an exception handler. An exception handler is a section of code, part of the operating system, that performs operating system services. Different services expect data in different registers, and not all services return values to the caller.
A system service works like a subroutine and may alter the temporary registers. Values in saved registers are preserved, however.
Question 2
Is syscall a basic instruction or a pseudoinstruction?
Answer
It is a basic assembly instruction that corresponds to a 32-bit machine instruction.
Exception handler services
Here are the services of the SPIM exception handler. The following pages explain how to use them. The print services write characters to the simulated monitor of SPIM. The read services read characters from the keyboard and (for numeric read services) convert character strings into the appropriate type.
Here is an example of how to use a service. Load register $v0 with the code for the exit service and then use the syscall instruction. The exit service stops the program. (Until now we have been single stepping the program or crashing into the bytes beyond the end of the program).
li $v0,10 # code 10 == exit
syscall # Return control to the
# operating system.
Question 3
What (do you think) the exit service does for a program running on a computer with a real operating system?
Answer
This is how the program returns control to the operating system without expecting to get control back.
Print string
The exit service is normally used when the program is finished. A real computer is always running, and control has to go somewhere, so this is how control is sent back to the OS. The OS then goes about its own tasks, possibly starting another user program. (On SPIM, the exit service stops all execution.)
The print string SPIM exception handler service prints a null terminated string to the simulated monitor. The address of the string is loaded into register $a0. Typically the string is in the data section of memory.
li $v0,4 # code 4 == print string
la $a0,string # $a0 == address of the string
syscall # Ask the operating system to
# perform the service.
. . . .
.data
string: .asciiz "Hello SPIM!\n"
The print string service sends bytes to the simulated monitor one by one starting with the byte pointed to by $a0. It continues until it hits a null byte. It does not check that the bytes are ASCII. You will print garbage if you point $a0 at the wrong location.
If you want to advance to a new line, use the newline character '\n' inside or at the end of the string.
Bug Alert: notice how the la instruction is used to load the address of the first byte of the string to be printed.
Bug Alert: values in t registers may be altered by the operating system service, for this and other services.
Question 4
Fill in the blanks.
____ $v0,4 # code 4 == print string
____ $a0,message # $a0 == address of the string
____ # Ask the operating system to
# perform the service.
. . . .
.data
message: .asciiz "Intruder Alert!\n"
Answer
li $v0,4 # code 4 == print string
la $a0,message # $a0 == address of the string
syscall # Ask the operating system to
# perform the service.
. . . .
.data
message: .asciiz "Intruder Alert!\n"
The traditional example
You are now ready to see the program you probably expected to see in Chapter One. The following program prints the string, then calls the exit service.
# hello.asm
#
.text
.globl main
main:
li $v0,4 # code 4 == print string
la $a0,string # $a0 == address of the string
syscall # Invoke the exception handler.
li $v0,10 # code 10 == exit
syscall # Halt the program.
.data
string: .asciiz "Hello SPIM!\n"
The string is printed to the monitor window of the simulator. The program is complete, and can be copied into a source file and run as is. But see the next page first.
Question 5
On a real (hardware) computer, what is the exception handler?
Answer
It is a machine language program in memory (possibly in ROM).
Starting SPIM
With SPIM, exceptions are handled by the simulator. On a real machine an exception handler might be permanently in ROM, might be loaded from a "boot sector" of the hard disk, or (in the good old days) might be entered into memory by hand.
To use the exception handler with SPIM do the following in the Simulator Settings panel. Set the options "Allow pseudoinstructions" and "Load trap file". Disable "Mapped I/O".
Bug Alert! Make sure that "Mapped I/O" is disabled! The memory mapped I/O option simulates the hardware implementation of I/O and interferes with these system calls.
Now to assemble and load your program go to File Open and select the source file (just as we have been doing). Your program is loaded along with some initialization code. The initialization code starts at address 0x00400000, the address that has until now been where your programs started.
To run the program click on Simulator Go and then OK in the pop-up panel.
Question 6
Can you single step starting at address 0x00400000 as before?
Answer
Yes, but since much of the code is not from your program single stepping is less interesting.
Example output
Here is SPIM with the example "hello.asm" program. When an exception file is loaded along with your program (when the Load exception file setting is checked), SPIM loads some initialization code starting at address 0x400000, and loads some data starting at 0x10000000. So now you no longer know exactly where your code and data are in memory, so you must use symbolic addresses in your code.
For example, in previous chapters you could set up a base register to point at your data by doing something like this: lui $10,0x1000. This will no longer work, since you data does not start at 0x10000000.
Instead, do something like this la $s0,mydata to use $s0 as a base.
Question 7
What happens if the program were slightly modified, as follows:
main:
li $v0,4 # code 4 == print string
la $a0,string # $a0 == address of the string
addiu $a0,1 # add one to the address
syscall # Invoke the operating system.
. . .
.data
string: .asciiz "Hello SPIM!\n"
Answer
The program prints "ello SPIM!"
Read integer, print integer
The read integer service reads an entire line of input from your keyboard—all the characters you type up to the newline character. These characters are expected to be ASCII digits '0', '1', .., '9' with an optional leading '-' or '+'. The characters are converted into a 32-bit two's complement representation of the integer which is returned in $v0.
li $v0,5 # code 5 == read integer
syscall # Invoke the operating system.
# Read in one line of ascii characters.
# Convert them into a 32-bit integer.
# $v0 <-- two's comp. int.
The print integer service prints the integer represented by the 32 bits in $a0 to the SPIM terminal. Of course, there are many ways that the integer can be placed in $a0, not just lw.
li $v0,1 # code 1 == print integer
lw $a0,int # $a0 == the integer
syscall # Invoke the operating system.
# Convert the 32-bit integer into characters.
# Print the character to the monitor.
Question 8
The print integer prints an integer on the simulated monitor. But what must it do first, before printing?
Answer
The exception handler service first converts the integer in $a0 from 32-bit two's complement representation into ASCII characters.
Example program
The following example program reads in an integer, presumed to be a number of ounces, then writes out the equivalent number of pounds and ounces.
# ounces.asm
#
# Convert ounces to pounds and ounces.
.text
.globl main
main: li $v0,4 # print prompt
la $a0,prompt #
syscall
li $v0,5 # read in ounces
syscall
li $t1,16 # 16 oz. per pound
divu $v0,$t1 # lo = pound; hi = oz.
mflo $a0
li $v0,1 # print
syscall # pounds
li $v0,4 # print "pounds"
la $a0,pout
syscall
mfhi $a0 # print
li $v0,1 # ounces
syscall #
li $v0,4 # print
la $a0,ozout # "ounces"
syscall
li $v0,10 # exit
syscall
.data
prompt: .asciiz "Enter ounces: "
pout: .asciiz " Pounds\n"
ozout: .asciiz " Ounces\n"
As is often the case, input and output dominate the program. The actual calculation is hard to find.
Question 9
The program prints "Pounds" and "Ounces" on separate lines. Change the program so that they are printed on one line.
Answer
Remove the "\n" from " Pounds\n".
Read string
The exception handler can also read in a string from the keyboard.
li $v0,8 # code 8 == read string
la $a0,buffer # $a0 == address of buffer
li $a1,16 # $a1 == buffer length
syscall # Invoke the operating system.
. . . .
.data
buffer: .space 16 # reserve 16 bytes
Details: Register $a1 contains the length (in bytes) of the input buffer. Up to ($a1)-1 characters are read from the keyboard and placed in buffer as a null terminated string.
The user ends the string by hitting "enter". The "enter" character appears in the buffer as the newline character '\n', 0x0a. This byte is followed by the null byte 0x00. If the user enters a string that is exactly ($a1)-1 characters long the newline character is omitted from the buffer. No matter what, there is a null at the end of data in the buffer.
Question 10
Is the string that is read in immediately suitable for output using the print string service?
Answer
Yes.
A fine example
Sometimes you will have to remove the null at the end of the input string, perhaps because it is intended to be part of a larger string. Other times, as in the following example, you can use two print string operations.
The example program asks the user to enter a person's name followed by comma and "enter". Then the program writes out a personalized letter using the name. The body of the letter is printed using only one syscall. The personalized greeting is printed first in a separate syscall because it is null terminated.
# overdue.asm
.text
.globl main
main:
# get patron name
li $v0,4 # print prompt
la $a0,prompt #
syscall
li $v0,8 # code 8 == read string
la $a0,name # $a0 == address of buffer
li $a1,24 # $a1 == buffer length
syscall # Invoke the operating system.
# print the letter
li $v0,4 # print greeting
la $a0,letter #
syscall
li $v0,4 # print body
la $a0,body #
syscall
li $v0,10 # exit
syscall
.data
prompt: .asciiz "enter name, followed by comma-enter: "
letter: .ascii "\n\nDear "
name: .space 24
body: .ascii "\nYour library books are way\n"
.ascii "overdue. Please return them\n"
.ascii "before we give your name\n"
.asciiz "to the enforcement squad.\n\n"
It is somewhat crude to make the user enter a comma at the end of the name. It would be nicer to have the program detect the end of the name and automatically put a comma after it. The program would be much longer.
Question 11
Can blank spaces be part of the name that the user enters?
Answer
Yes — it is ASCII code 0x20 and treated just like any character.
Operation of the program
Here is a picture that shows the normal operation of the program. The patron name followed by a comma, was entered by the user.
Question 12
Is "backspace" a character?
Answer
Yes — it is ASCII code 0x08
No line-buffer correction
The user might make a mistake in entering the name and try to correct it by hitting the "backspace" key to erase the mistake. But this does not work. The backspace character, 0x08, is included in the string just as is any character. Non-character byte values show up (in SPIM) as small black rectangles.
Most operating system user interfaces allow the user to edit a string (with BS, DEL, arrow and other keys) before it is sent to an application program. The application program asks for a string from the user, but the OS does the actual input, complete with user editing. (This is sometimes called "cooked" input mode).
The SPIM exception handler service does not do this. Characters are sent directly to the program as they were typed. If the user hits the backspace character, then that character is placed in the input string. (This is called "raw" input mode).
Question 13
What mode of input (raw or cooked) does a text editor use?
Answer
Raw. The text editor program itself will interpret the characters the user types. For example, it will (probably) interpret the arrow keys as commands to move the cursor through the text.
Chapter quiz
Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.
Question 1
What is the name for the small collection of services on SPIM that are invoked using a syscall instruction?
- (A) wolf trap
- (B) exception handler
- (C) BIOS
- (D) operating system
Answer
B
Question 2
Does the syscall instruction correspond to just one machine language instruction?
- (A) No — it is so complicated that it takes several machine instructions.
- (B) No — it is special and does not correspond to any machine instructions.
- (C) Yes — it is a fundamental operation of the hardware.
- (D) Yes — all assembly language statements correspond to one machine instruction.
Answer
C
Question 3
Which of the following fragments correctly writes "Hello" to the monitor?
(A)
lw $v0,4
lw $a0,hello
syscall
. . .
hello: .asciiz "Hello"(B)
li $v0,4
la $a0,hello
syscall
. . .
hello: .asciiz "Hello"(C)
li $v0,4
lw $a0,hello
syscall
. . .
hello: .ascii "Hello"(D)
li $v0,4
li $a0,"Hello"
syscall
. . .
Answer
B
Question 4
Where is the integer after the "read integer" service returns control?
- (A) In the input buffer.
- (B) In a register specified by the user.
- (C) In register
$v0. - (D) In register
$a0.
Answer
C
Question 5
What parameters are expected for the "read string" service?
- (A) The address of the input buffer.
- (B) The length of the input buffer.
- (C) The addresses of the input buffer and of the output buffer.
- (D) The length of the input buffer and the address of the input buffer.
Answer
D
Question 6
Are the code numbers for the various services determined by the MIPS hardware or by the software of the the exception handler?
- (A) This is a hardware feature of the MIPS chip.
- (B) This is a hardware feature of the various IO devices attached to the computer.
- (C) Software — the user program sets up the service codes before it starts execution.
- (D) Software — the exception handler software examines the code and branches to the indicated service.
Answer
D
Question 7
In an actual computer system with a full-scale operating system, what would the exit service do?
- (A) Return control to the operating system.
- (B) Halt the processor.
- (C) Halt the operating system.
- (D) Immediately start running another user program.
Answer
A
Question 8
Is "backspace" a character?
- (A) No — hitting backspace on a keyboard sends a command to the computer.
- (B) No — backspace corresponds to a control signal that affects the monitor.
- (C) Yes — the backspace sends the same character as the back arrow key.
- (D) Yes — as far as the hardware is concerned, backspace is just another ascii character.
Answer
D
Question 9
What does the "read integer" service do?
- (A) It reads two's complement integers directly from the keyboard.
- (B) It reads a single digit from the keyboard and returns it in
$v0. - (C) It reads the next number on the current line. If there is no next number it goes on to the next line.
- (D) It reads in a line of characters from the keyboard and then converts those characters to a two's complement integer.
Answer
D
Question 10
With a full-sized operating system, when a user enters a string of characters in response to a prompt, where are editing characters (like delete and backspace) interpretted?
- (A) In the user's program.
- (B) An operating system service is running as the user enters and edits text.
- (C) The keyboard device driver implements line editing.
- (D) The basic IO system is in charge of this.
Answer
B
Programming instructions
For these programming exercises, use only those instructions that have been discussed so far in these notes:
Basic Instructions
add | div | mflo | slt, slti |
addi | divu | mult | sltu, sltiu |
addiu | j | multu | sra |
addu | lb | nor | srl |
and | lbu | or | sub |
andi | lh | ori | subu |
beq | lhu | sb | sw |
bgez | lui | sh | xor |
bltz | lw | sll | xori |
bne | mfhi |
PseudoInstructions
la | lw | nop | syscall |
li | move | sw |
n the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches ON, Delayed Loads ON, Mapped IO ON, Quiet OFF.
Run the programs by loading the trap handler (as explained in the chapter) and clicking SimulatorGo and then OK in the pop-up panel.
Use the lw and sw with symbolic addresses for loading and storing registers. Use mnemonic register names and use registers in their conventional roles.
Exercise 1 (*) - miles per gallon
Write a program that repeatedly prompts the user for the number of miles traveled and the gallons of gasoline consumed, and then prints out the miles per gallon. Use integer math. Exit when the user enters 0 for the number of miles.
Exercise 2 (**) - miles per gallon, fixed-point math
As in Exercise1, write a program that repeatedly prompts the user for the number of miles traveled and the gallons of gasoline consumed, and then prints out the miles per gallon. Exit when the user enters 0 for the number of miles.
Use fixed-point arithmetic for this. Multiply input value of miles by 100. Divide miles by gallons to get miles per gallon. The answer will 100 times too large. So divide it by 100 to get whole miles per gallon in hi and hundredths in lo. Print out lo followed by "." followed by hi to get an output that looks like: "32.45 mpg".
Exercise 3 (***) - string to integer
Write a program that asks the user for a string of digits that represent a positive integer. Read in the string using service number 8, the "read string" service. Now convert the string of digits into an integer by the following algorithm:
value = 0;
for each digit starting with the left-most:
{
convert the digit into an integer D by subtracting 0x30
value = value*10 + D
}
You might recognize this as Horner's method. After converting the integer, check if it is correct by writing it out on the simulated monitor using service 1.
Notes: assume that the input is correct (that it contains only digits and can be converted to a 32-bit integer). Be sure to deal properly with the end-of-line character that is at the end of the user's input.
Exercise 4 (***) - Fahrenheit/Celsius converter
Write a program that repeatedly asks the user for a scale F or a C (for "Fahrenheit" or "Celsius") on one line followed by an integer temperature on the next line. It then converts the given temperature to the other scale. Use the formulas:
F = (9/5)C + 32
C = (5/9)(F - 32)
Exit the loop when the user types "Q". Assume that all input is correct. For example:
Enter Scale : F
Enter Temperature: 32
Celsius Temperature: 0C
Enter Scale : C
Enter Temperature: 100
Fahrenheit Temperature: 212F
Enter Scale : Q
done
Instructions for Bitwise Logic and Math
This chapter discusses additional pseudoinstructions. When you write a program using pseudoinstructions it looks to you as if the computer has a rich set of convenient machine instructions. In fact, these convenient instructions are each implemented by using basic instructions. The extended assembler replaces each pseudoinstruction with one or more basic instructions. The basic instructions are then translated into machine code.
Chapter Topics:
- Bitwise logic:
notpseudoinstruction
- Integer Arithmetic:
abspseudoinstructionaddupseudoinstructionsubupseudoinstructionnegupseudoinstructionmulpseudoinstructiondivpseudoinstructiondivupseudoinstructionremupseudoinstruction
- Rotate Instructions:
rolrotate left pseudoinstructionrorrotate right pseudoinstruction
Question 1
What is the bitwise not of this pattern:
0011 1001
_________
Answer
NOT( 0011 1001 ) == 1100 0110
not pseudoinstruction
The not pseudoinstruction changes each bit in a register. Each 1 is changed to a 0 and each 0 is changed to a 1. (This is sometimes called "flipping" each bit or "reflecting" each bit.)
not d,s # load register d with the
# bitwise not of register s
# (pseudoinstruction)
This is a pseudoinstruction. The assembler translates it into a single basic assembly instruction, a nor instruction. The nor operation is given in the table. The nor of two bits is equivalent to applying not to the or of the bits. The nor instruction uses two registers as operands and writes the result to a third register:
nor d,s,t # $d <— bitwise NOR $s with $t.
# (basic instruction)
Look at the first two columns of the table where the first operand is zero. The nor of the two operands is the not of the second operand.
Question 2
Translate the following:
not $s1,$t5
into a nor instruction:
nor _____ , _____ , _____
Hint
Consider using register $0.
Answer
not $s1,$t5 = nor $s1, $t5, $0
The order of $t5 and $0 could be reversed. (You could also say $zero rather than $0.)
Implicit immediate operand
Some pseudoinstructions translate into different basic instructions depending on the type of operands. A pseudoinstruction used with an immediate operand translates into different basic instructions than one used with all register operands.
Sometimes the same mnemonic is used for a basic instruction and also for a pseudoinstruction. For example, you can use the mnemonic or for an or with register operands and also for an or with an immediate operand:
or $s0,$s1,0x00ff translates into: ori $s0,$s1,0x00ff
Here, the extended assembler notices the immediate operand and translates the instruction into an ori basic instruction. The resulting machine code is a 32-bit or immediate. However, the following is a basic instruction:
or $s0,$s1,$t1
This assembly instruction is not changed. The resulting machine code is a 32-bit or instruction.
The mnemonic and is similar. It might call for the basic instruction and, or the basic instruction andi, or other basic instructions depending on the operands.
Question 3
Is there both a basic add instruction and an add immediate instruction?
Answer
Yes.
Arithmetic pseudoinstructions
With the non-extended assembler there is an addu d,s,t instruction where d, s, and t are registers, and an addiu d,s,imm instruction where imm is an immediate operand.
With the extended assembler the addu d,s,x instruction translates into different basic instructions depending on x. x can be a register, a 16-bit immediate operand, or a 32-bit immediate operand.
Examine the following instruction (for the extended assembler):
addu $t0,$s0,40000
The decimal value 40000 is too large to represent in 16 bits, (the range for 16 bits is -32768 to +32767) so the instruction cannot be translated into a basic addiu instruction. Two instructions must be used to add $s0 to 40000_10 and to place the result in $t0.
Question 4
Translate the following:
addu $s1,$s0,40000
into basic instructions. (Use mnemonic register names.)
li _____ , 40000 # use pseudoinstruction li
addu $s1,$s0, _____ # perform 32-bit addition
Hint
Consider using register $at.
Answer
addu $s1,$s0,40000
Translates into:
li $at,40000 # use pseudoinstruction li
addu $s1,$s0,$at # perform 32-bit addition
Subtraction
The li in the above is itself a pseudoinstruction. The extended assembler will translate it, also, into basic instructions.
There is also (with the extended assembler) a subu d,s,x instruction where the last operand can be a register, a 16-bit immediate, or a 32-bit immediate. This instruction translates into the pseudoinstruction addu d,s,-x (which is then translated into basic instructions).
The negu d,s pseudoinstruction calculates the two's complement negation of register $s and puts it in register $d.
negu d,s # d = -s
# (pseudoinstruction)
Question 5
Translate this instruction
negu $v2,$s3
into a basic instruction:
sub _____ , $0 , _____
Answer
negu $v2,$s3
Translates into:
sub $v2,$0,$s3
Multiplication
The mult and the multu instructions (which you have seen before) put the result into MIPS registers hi and lo. The results may be moved out of these registers using mfhi and mflo.
The three operand pseudoinstruction mul d,s,t uses those basic instructions. It is used when the product of registers $s and $t is a value that fits into the 32 bits of lo.
Question 6
Finish the translation:
mul $v2,$s3,$t0
Translates into:
mult _____ , _____
mflo _____
(Use mnemonic register names.)
Answer
mul $v2,$s3,$t0
Translates into:
mult $s3, $t0
mflo $v2
mul pseudoinstruction
The mul pseudoinstruction makes it look as if MIPS has a 32-bit multiply instruction that places its 32-bit result:
mul d,s,t # multiply $s by $t. put the
# result in $d
# (pseudoinstruction)
There is no overflow checking. The bits of hi are not examined nor saved. There are several other pseudoinstructions that examine hi and perform various actions on overflow. We won't use them.
There is a similar instruction for division. The basic instructions div s,t and divu s,t put their results in MIPS registers hi and lo. The 32-bit quotient goes in lo and the 32-bit remainder goes in hi. To move the quotient into a register, mflo is used.
Question 7
Finish the translation. The operand registers are $s1 and $s2, the destination register is $t0.
div $t0,$s1,$s2
Translates into:
div _____ , _____
mflo _____
Answer
div $t0,$s1,$s2
Translates into:
div $s1, $s2
mflo $t0
div and divu pseudoinstruction
The SPIM extended assembler includes these instructions:
div d,s,t # divide $s by $t. Put the
# quotient in $d. Operands are
# two's complement.
# (pseudoinstruction)
and
divu d,s,t # divide $s by $t. Put the
# quotient in $d. Operands are
# unsigned.
# (pseudoinstruction)
Question 8
Is the remainder of an integer division sometimes useful?
Answer
Of course.
remu (pseudoinstruction)
After a 32-bit integer division, the quotient is in the lo register and the remainder is in the hi register. The following pseudoinstruction uses several basic instructions to compute the remainder:
remu d,s,t # divide $s by $t. Put the
# remainder in $d. Operands are
# unsigned.
# (pseudoinstruction)
There is a pseudoinstruction for creating the absolute value of an integer:
abs d,s # d = |s|
# (pseudoinstruction)
Question 9
What total amount is given to a waiter if the bill is $25, the tax rate is 8%, and the tip is 15% ? (Use integer math).
Answer
total = 25 + (25*(8+15))/100 = 25 + (25*23)/100 = 25 + 575/100 = 30
If the waiter grumbles about getting $30 instead of $31, just explain that in integer math 575/100 = 5.
Example program
Write a program that calculates the total cost given the amount for the meal, plus 8% tax, plus 15% tip. The meal amount is input from the user. The tax and tip rates are fixed. Here is a run of the program:
Enter food cost: 25
Tax plus tip: 5
Total cost: 30
Here is a start on the program:
## rest.asm
##
## Total restaurant bill calculator
##
## Register Use:
##
## $s0 tip+tax
## $s1 tip rate
## $s2 tax rate
## $s3 meal cost
## $a0 tax+tip dollars
.globl main
# Get meal cost
main: li $v0,4 # print a prompt (code 4 put in $v0)
la $a0,prompt # address of prompt put in $a0
syscall
li $v0,5 # input an integer (code 5 put in $v0)
syscall # 32-bit result returned in $v0
move $s3,$v0 # save it in $s3
. . . . .
.data
tip: .word 15 # tip rate in percent
tax: .word 8 # tax rate in percent
prompt: .asciiz "Enter food cost: "
head1 : .asciiz " Tax plus tip: "
head2 : .asciiz " Total cost: "
The only information needed from the user is the cost of the food. This is prompted for and then read in (as text) and converted (by part of the exception handler) into a 32-bit two's complement integer. The SPIM exception handler expects the service code to be in register $v0. Arguments are passed into and returned from the services using various other registers.
Question 10
With your mental highlighter, mark the mnemonics in the code fragment (above) which are pseudoinstructions.
Answer
See below.
Calculation section
After reading the food cost, the program can do the calculations. It is convenient to do them all at once and then to print out the results.
Question 11
Fill in the blanks to complete the calculation section.
Answer
# Calculations
lw $s1,tip # get tip rate
lw $s2,tax # get tax rate
nop
addu $s3,$s1,$s2 # total rate
mul $s4,$s0,$s3 # mealcost*(total rate)
div $s4,$s4,100 # mealcost*(total rate)/100
addu $s5,$s0,$s4 # total bill
Writing out the results
The final section of the program writes the results to the monitor.
Fill in the blanks to complete the program
Question 12
tbdQuestion
Answer
See below.
Complete program
The program is complete and can be copied into your program editor for running and play. Remember in the SPIM settings to allow pseudoinstructions and to load the trap handler file.
## rest.asm
##
## Total restaurant bill calculator
##
## Register Use:
##
## $s0 meal cost
## $s1 tip rate
## $s2 tax rate
## $s3 total rate
## $s4 tax+tip dollars
## $s5 total bill
.globl main
# Get meal cost
main: li $v0,4 # print prompt
la $a0,prompt
syscall
li $v0,5 # input meal cost
syscall
move $s0,$v0 # save it in $s0
# Calculations
lw $s1,tip # get tip rate
lw $s2,tax # get tax rate
nop
addu $s3,$s1,$s2 # (tax + tip) in percent
mul $s4,$s0,$s3 # mealcost*(total rate)
div $s4,$s4,100 # mealcost*(total rate)/100
addu $s5,$s0,$s4 # total bill
# Output
li $v0,4 # print string
la $a0,head1 # "tax plus tip"
syscall
move $a0,$s4 # get tax+tip
li $v0,1 # print integer
syscall #
li $v0,4 # print string
la $a0,head2 # "total cost"
syscall
move $a0,$s5 # get total
li $v0,1 # print integer
syscall #
li $v0,10 # exit
syscall
.data
tip: .word 15 # tip rate in percent
tax: .word 8 # tax rate in percent
prompt: .asciiz "Enter food cost: "
head1 : .asciiz " Tax plus tip: "
head2 : .asciiz "\n Total cost: "
Question 13
What is the bit pattern in register $t1 after the following:
li $t0,0x12345678
sll $t1,$t0,8
Answer
Register $t1 will contain 0x34567800.
Bit pattern rotation
With a shift left instruction, the bits at the left end of the the register "fall off". The bits shifted into the right end are always zero bits.
With a rotate left instruction, the bits at the left end of the the register are fed into the right end of the register. The 32-bit register always contains the same 32-bit values it started with, but they are rotated into new positions.
In the illustration, after rotating left one bit the pattern changes from 10100111 to 01001111. One more left rotate would change the pattern to 10011110.
Of course, registers have 32 bits, not the eight bits shown in the illustration.
With a rotate right instruction, bit values in the register are moved right. Bits at the right end of the register are fed back into the left end of the register.
Question 14
Rotate right this pattern by two bit positions:
10001100
_____
Answer
00100011
Rotate instructions
The rotate instructions are both pseudoinstructions. Each one takes four basic instructions to implement. The shift amount is given in a register or as an immediate operand.
rol d,s,t # d <—s rotated left by t
# (pseudoinstruction)
ror d,s,t # d <— s rotated right by t
# (pseudoinstruction)
Negative immediate operands are not allowed. However, if the third operand is a register it may contain a negative integer. In that case the rotation is the opposite direction.
Question 15
Inspect the following:
li $t2,-2
li $t1,4
ror $t0,$t1,$t2
What does $t0 hold after the sequence has executed?
Answer
0000 0000 0000 0000 0000 0000 0001 0000
Because $t2 holds a negative amount, the rotation is done to the left.
Chapter quiz
Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.
Question 1
What is the bitwise not of 0110 1010?
- (A)
0000 0000 - (B)
1111 1111 - (C)
1001 0101 - (D)
1010 1011
Answer
C
Question 2
Translate the following pseudoinstruction into basic assembly language: not $t5,$s1
- (A)
not $t5,$s1,$0 - (B)
not $t5,$s1 - (C)
nor $t5,$s1 - (D)
nor $t5,$s1,$0
Answer
D
Question 3
Which of the following instructions will be translated by the extended assembler into one or more basic instructions?
- (A)
or $s0,$t6,$t7 - (B)
or $s0,$t0,0xffff - (C)
addiu $t0,$t5,32 - (D)
subu $s0,$t3,$t6
Answer
B
Question 4
Translate the following pseudoinstruction into basic assembly language: negu $s1,$t1
- (A)
addu $s1,$0,-$t1 - (B)
nor $s1,$0,$t1 - (C)
sub $s1,$t1,$0 - (D)
sub $s1,$0,$t1
Answer
D
Question 5
Write the pseudoinstruction that multiplies $t3 by $s0 and puts the result in $v0
- (A)
mul $v0,$s0,$t3 - (B)
mult $v0,$s0,$t3 - (C)
mulu $v0,$s0,$t3 - (D)
multi $v0,$s0,$t3
Answer
A
Question 6
Translate the following pseudoinstuction into basic instructions: div $s0,$t0,$t1
(A)
divu $s0,$t0,$t1(B)
div $t0,$t1
mflo $s0(C)
div $t0,$t1
mfhi $s0(D)
div $t1,$t0
mflo $s0
Answer
B
Question 7
Translate the following pseudoinstuction into basic instructions: remu $s0,$t0,$t1
(A)
divu $s0,$t0,$t1(B)
div $t0,$t1
mflo $s0(C)
div $t0,$t1
mfhi $s0(D)
div $t1,$t0
mflo $s0
Answer
C
Question 8
Rotate the following bit pattern two positions RIGHT: 10001101
- (A)
00110100 - (B)
01100011 - (C)
10001101 - (D)
10000001
Answer
B
Question 9
Rotate the following bit pattern two positions LEFT: 10001101
- (A)
00110110 - (B)
00110100 - (C)
10001101 - (D)
10000001
Answer
A
Question 10
Which sequence rotates the bits in $t0 two positions right?
(A)
li $t1,2
ror $t0,$t0,$t1(B)
li $t1,-2
ror $t0,$t0,$t1(C)
rol $t0,$t0,-2(D)
rol $t0,$t0,2
Answer
A
Programming exercises
In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches ON, Delayed Loads ON, Mapped IO ON, Quiet OFF.
Run the programs by loading the trap handler (as explained in the chapter) and clicking SimulatorGo and then OK in the pop-up panel.
Exercise 1 (**) - prime number tester
Write a program that asks the user for a positive integer. The program then tests if the integer is prime and writes out its result.
A number is prime if it cannot be divided evenly by any number other than 1 and itself. So you will need a counting loop that starts at two and divides the number for each value of the loop counter until the number is divided evenly or the limit is reached.
For the upper limit of the loop use the number divided by two. (A better upper limit would be the square root of the number, see below.)
Exercise 2 (**) - integer square root
Write a program that asks the user for an integer and then computes the square root of that integer. Use only integer arithmetic. The integer square root of N is the positive integer X who's square is exactly N, or who's square is less than N but as close to N as possible. Examples:
iSqrt(25) == 5 since 5*5 == 25.
iSqrt(29) == 5 since 5*5 == 25 and 6*6 == 36, so 6 is too big.
iSqrt(60) == 8 since 8*8 == 56 and 9*9 == 81, so 9 is too big.
iSqrt(0) == 0, iSqrt(1) == 1, iSqrt(2) == 1.
The integer square root is undefined for negative integers.
There are various fast ways of computing the integer square root (Newton's method is one). But for this program, use a counting loop that generates integers 0, 1, 2, 3, ... and their squares 0, 1, 4, 9, ... As soon as the square of an integer exceeds N, then the previous integer is the integer square root of N.
Exercise 6 (***) - lottery odds
To win a lottery you must correctly pick K out of N numbers. For example, you might need to pick 6 numbers out of the numbers 1 to 50. There are
(50 * 49 * 48 * 47 * 46 * 45 )/(1 * 2 * 3 * 4 * 5 * 6)
ways of picking 6 out of 50 numbers. So your odds of winning are 1 in that number of ways. If you must pick 6 out of 50 numbers, your odds of winning are 1 in 15,890,700. In general, there are
N * (N-1) * (N-2) * (N-3) * (N-4) * ... * (N-K+1)
-------------------------------------------------
1 * 2 * 3 * 4 * ... * K
ways of picking K out of N numbers.
Write a program that asks the user for integers N and K and writes out the odds of winning such a lottery.
Test that the program works for reasonable values of N and K.
Branch Instructions, Set Instructions, and Indexed Addressing
The MIPS hardware has several instructions for branching and looping. These fundamental instructions are used to create many pseudoinstructions that give the programmer added flexibility.
Chapter Topics:
- Branch instructions
- Immediate operands in branch instructions
- Set instructions
- Indexed Addressing
- Byte arrays
- Integer arrays
Note: for the example programs in this chapter, set the SPIM simulator so that pseudoinstructions are ON, delayed branches are OFF, and delayed loading is OFF.
Question 1
(Review:) What is a conditional branch?
Answer
A conditional branch tests a condition then changes the PC if the condition is true (for example, beq $t1,$t2,label).
Branch equal to zero
The extended assembler implements several conditional branch instructions beyond the basic ones. For example:
beqz s,label # branch to label if register s == 0
# (pseudoinstruction)
The hardware does not have a machine instruction for this operation. It does, however, have a zero register and the beq instruction (branch equal).
Question 2
Fill in the blanks so the branch is taken if $s1 is zero.
_____ $s1 , _____ , label # branch to label if register $s1 == 0
Answer
beq $s1,$0,label # branch to label if register $s1 == 0
Unconditional branch instruction
The pseudocomputer has an unconditional branch instruction that always causes a branch. The mnemonic for the instruction is b:
b label # branch to label
# (pseudoinstruction)
This instruction behaves like the jump instruction: it unconditionally loads the PC with the address specified by label. Unlike the jump instruction, the branch target label must be relatively close to the branch instruction, as is true with all branch instructions. The 32-bit address is computed using a 16 bit offset in the instruction and the current value of the PC.
Question 3
The extended assembler implements the b instruction using the beq instruction. Fill in the blanks to show what it does:
b label == beq _____ , _____ , offset
Offset is the 16-bit offset that is added to the PC to calculate label (if possible).
Answer
b label == beq $0,$0,offset
Table of branch instructions
Here is a table of branch instructions. There are additional branch instructions used for subroutine linkage that have been omitted. Some instructions assume 32-bit two's complement data; others assume 32-bit unsigned data. Some instructions don't assume any data format.
The first operand s must be a register. The second operand t may be a register or a immediate operand (the extended assembler will generate the correct basic instructions depending on which you choose). The label designates an address that can be reached by adding a 18-bit, sign-extended integer to the PC. The 18 bits come from an immediate operand (shifted left two positions) of the machine instruction. This means the branch target must be within plus or minus 128K from the current instruction.
Some of the pseudoinstructions use the assembler temporary register ($at, or register $1) in the one or two basic instructions they are translated into.
Question 4
What format of data is assumed for the bne (branch not equal) instruction?
Answer
No assumptions are necessary. It tests if two bit patterns are identical.
Natural if-else structure
When you use a branch instruction to implement an if-statement, the instructions that are executed when the condition is false immediately follow the branch instruction. This is the opposite of high-level languages. With them, an if-statement is immediately followed by the statements that correspond to "true". Watch out for this problem when you are coding. Careful documentation helps.
Here is a program fragment that is to add the value in register $t0 to register $t2 (if $t0 is even) and to $t1 (if $t0 is odd):
lw $t0,val # $t0 has the value
andi $t8,$t0,1 # one's place in $t8 is zero or one
____ $t8,odd # if even
# {
addu $t2,$t2,$t0 # add to even sum
b endif # }
odd: # else
addu $t1,$t1,$t0 # add to odd sum
endif:
An unconditional branch instruction is used at the bottom of the true branch to skip around the false branch.
(In this chapter, the SPIM simulator has been set so that delayed branches are OFF and delayed loading is OFF, so no-ops are not included in this program fragment.)
Question 5
Fill in the blank by choosing the correct branch instruction (refer to the previous table).
Answer
lw $t0,val # $t0 has the value
andi $t8,$t0,1 # one's place in $t8 is zero or one
bnez $t8,odd # if even
# {
addu $t2,$t2,$t0 # add to even sum
b endif # }
odd: # else
addu $t1,$t1,$t0 # add to odd sum
endif:
Immediate operand in branch
If a branch instruction has a second operand, it can be an immediate operand or a register. The extended assembler will implement this using several basic instructions. For example, from the table:
Here are examples:
bge $t1,$t2,spot # if ( $t1 >= $t2 ) goto spot
bge $t1,23,spot # if ( $t1 >= 23 ) goto spot
bge $t1,-98,spot # if ( $t1 >= -98 ) goto spot
bge 12,$t1,oops # WRONG: first op must be a register
bge $t1,value,oops # WRONG: second op can't be a symbolic address
Question 6
Is the following instruction correct?
bge $t1,-67,spot # if ( $t1 >= -67 ) goto spot
Answer
Yes.
Example program
Let us write a program that reads integers from the user and adds up those integers x that are in the range -32 <= x <= +32 and discards the rest. The user signals the end by entering -999 (which is not added to the sum). Here is the basic outline:
(For this chapter, load delays and branch delays have been turned off in the simulator.)
Question 7
Fill in the blanks.
Answer
See below.
Blanks filled
The outline is completed below. I/O is left out. Detecting the end of input by testing for a sentinel value, as we do here, is usually regarded as poor style. It is used here to simplify the example.
main:
li $v1,0 # zero the sum
loop:
. . . . # prompt the user for input
li $v0,5 # read the integer
syscall # into $v0
beq $v0,-999,done # while ( $v0 != -999 )
blt $v0,-32,out # less than -32
bgt $v0,32,out # greather than 32
addu $v1,$v1,$v0 # if in range add
# else skip
out: b loop
done: . . . . # write out result
Question 8
(Memory Test:) What do set instructions do on MIPS?
Answer
Set instructions set a register to 1 or clear it to 0 to show the outcome of a comparison between two values.
Set on less than
Think of the "1" and "0" that a set instruction puts in the flag register as "true" and "false". Here is the slt from chapter 18, but now made more useful by the extended assembler:
# $s and t contain
# two's comp. integers
# t can be a register
# or an immediate operand
#
slt d,s,t # if ( $s < t )
# d = 1
# else
# d = 0
#
# (pseudoinstruction)
With the extended assembler, the operand t can be an immediate operand.
Question 9
Is the following correct?
slt $t5,$v0,87 # if ( $v0 < 87 ) $t5 = 1
Answer
Yes.
Table of set instructions
Here is a table of set instructions. Most of them are pseudoinstructions. The t operand can be an immediate operand. The Imm operand must be an immediate operand.
The extended assembler outputs the correct basic instructions depending on the mnemonic and the operands. Sometimes there are several ways in which the same basic instructions can be specified.
Some of the instructions are intended for integers expressed in unsigned binary, other instructions are for integers in two's complement, and for others it makes no difference.
Question 10
Do you think that the following two pseudoinstructions translate into the same basic instructions?
sltu $t4,$v0,45
and
sltui $t4,$v0,45
Answer
Yes. The first translates into the second.
Indexed addressing
In addition to implementing new instructions, the extended assembler implements a new addressing mode. This is indexed addressing, a mode of addressing very useful for arrays. Here is an example:
li $t1,2 # index 2
lb $v0,data($t1) # $v0 = data[$t1]
. . .
data: .byte 6,34,12,-32, 90 # index zero is first
Think of data as an array of five bytes. Then the lb instruction loads the element of the array at index 2 (the byte that contains 12) into $v0.
The extended assembler does this the same way we have done in in past programs: basic instructions are used to add the index value in $t1 to the address symbolized by data. Here is what the assembler generates for the above code:
ori $t1,$0,2 # index 2
lui $at,4097 # $at register gets address "data"
addu $at,$at,$t1 # add index to $at
lb $v0,0($at) # $v0 = data[$t1]
. . .
data: .byte 6,34,12,-32, 90
The assembler generates code that uses register $at to calculate the address of the correct byte. Then, using that address, the byte is loaded into $v0.
Question 11
When does the actual address calculation take place?
Answer
When the code that the assembler generates is actually executing.
Four levels
This is a very "Computer Science"-like idea. It takes some careful thought to see what is going on. Here is a table:
Question 12
At what index do "C" and Java arrays begin?
Answer
Index zero.
Indexes start at zero
Experience has shown that indexing arrays starting at zero works best. The first element of an array is at a displacement of zero from the beginning of the array. To move through an array start the index at zero and increment it by the element size to move to the next element.
Here is a program fragment that adds up all the bytes in the array:
li $v1,0 # zero the sum
li $t1,0 # init index to 0
li $t2,0 # init loop counter
for: beq $t2,5,endfor # for ( i=0; i < 5 ;i++ )
lb $v0,data($t1)
addu $v1,$v1,$v0 # sum = sum+data[i]
addi $t1,$t1,1 # increment index
addi $t2,$t2,1 # increment counter
b for
endfor:
. . .
data: .byte 6,34,12,-32, 90
(Recall that branch delays and load delays have been turned off, for this chapter. To run this program on real hardware, several no-op instructions are needed.)
Question 13
When indexed addressing is used with an array of 32-bit integers, by how much should the index be incremented to move to the next array element?
Answer
By four.
Integer array
Here is nearly the same program as before, except that now the program adds up the integers in an array of full words (32 bits). The logic is the same as before.
Question 14
Just fill in the blanks and you have a working program!
Answer
See below.
Complete program
Here is a complete program. It is not too distant from what a "C" for loop might be compiled into. If you copy it to a file and run it with SPIM make sure that pseudoinstructions are allowed and that delayed load and delayed branches are turned off.
.globl main
main:
li $v1,0 # zero the sum
li $t1,0 # init index to 0
li $t2,0 # init loop counter
for: beq $t2,5,endfor # for ( i=0; i < 5 ;i++ )
lw $v0,array($t1)
addu $v1,$v1,$v0 # sum = sum+array[i]
addi $t1,$t1,4 # increment index
addi $t2,$t2,1 # increment counter
b for
endfor:
li $v0,10 # exit
syscall
.data
array: .word 1,2,3,-5,1
Question 15
Some languages (like Pascal) allow the first index of an array to be any integer. Can such a language be compiled for MIPS?
Answer
Of course. The compiler might not use the indexed addressing mode of the extended assembler, however.
Chapter quiz
Instructions: For each question, choose the single best answer. Make your choice by clicking on its button. You can change your answers at any time. When the quiz is graded, the correct answers will appear in the box after each question.
Question 1
Translate the following pseudoinstruction into basic instructions: beqz $t0,spot
- (A)
beqz $t0,$0,spot - (B)
beqz $t0,$t0,spot - (C)
beq $t0,spot - (D)
beq $t0,$0,spot
Answer
D
Question 2
With what addresses may the b instruction be used with?
- (A) Any address in memory.
- (B) Any address in the first 64K of memory.
- (C) Any address within 32K of the current address.
- (D) Any address within the current program.
Answer
C
Question 3
What format of data do the branch instructions assume?
- (A) unsigned integers only
- (B) two's complement integers only
- (C) Depending on the instruction, unsigned integers or two's complement integers.
- (D) Depending on the instruction, unsigned integers, two's complement integers, or abstract bit patterns.
Answer
D
Question 4
Which of the following instruction sequences computes the absolute value of the integer in $t0? (Branch delays are turned off.)
(A)
bgez $t0,pos
subi $t0,$0,$t0
pos:(B)
bgez $t0,pos
subu $t0,$0,$t0
pos:(C)
blez $t0,pos
subu $t0,$0,$t0
pos:(D)
bnez $t0,pos
subu $t0,$0,$t0
pos:
Answer
B
Question 5
What register do some of the branch instructions use when they are translated into basic instructions?
- (A)
$t0 - (B)
$a0 - (C)
$at - (D)
hi
Answer
C
Question 6
Pick the syntactically incorrect instruction from the following:
- (A)
bge $t1,$t3,lbl - (B)
bge $t1,-98,lbl - (C)
bge $t1,value,lbl - (D)
bge $t1,124034,lbl
Answer
C
Question 7
Pick the syntactically incorrect instruction from the following:
- (A)
slt $v0,$s1,123 - (B)
slt $v0,$s1,$s3 - (C)
slt $v0,$s1,0x123 - (D)
slt $t1,$s1,lbl
Answer
D
Question 8
Is it possible that a given pseudoinstruction could be translated into several different sequences of basic instructions?
- (A) No. There is only one possible translation of any given pseudoinstruction.
- (B) Yes. Each pseudoinstruction asks for a little program of basic instructions, and many little programs do the same thing.
Answer
B
Question 9
Here is a fragment of code:
.data
array: .byte 12,23,45,12,-5,72
Which of the following pseudoinstructions loads register $s1 with the 45?
(A)
li $t0,2
lw $s1,array($t0)(B)
li $t0,8
lw $s1,array($t0)(C)
li $t0,2
lb $s1,array($t0)(D)
li $t0,2
lw $s1,$t0(array)
Answer
C
Question 10
Here is a fragment of code. (Note the subtle change from the previous question.)
.data
array: .word 12,23,45,12,-5,72
Which of the following pseudoinstructions loads register $s1 with the 45?
(A)
li $t0,2
lw $s1,array($t0)(B)
li $t0,8
lw $s1,array($t0)(C)
li $t0,2
lb $s1,array($t0)(D)
li $t0,2
lw $s1,$t0(array)
Answer
B
Question 11
Here is a fragment of code.
.data
string: .asciiz "Hello Virtual World!"
Which of the following pseudoinstructions loads register $s1 with the 'V'?
(A)
li $t0,5
lw $s1,string($t0)(B)
li $t0,6
lb $s1,string($t0)(C)
li $t0,7
lb $s1,string($t0)(D)
li $t0,12
lw $s1,$t0(string)
Answer
B
Question 12
Where do indexes begin for arrays in C or Java?
- (A) 0
- (B) 1
- (C) at any index the programmer picks
- (D) at any multiple of four
Answer
A
Programming exercises
In the Settings menu of SPIM set Bare Machine OFF, Allow Pseudo Instructions ON, Load Trap File ON, Delayed Branches OFF, Delayed Loads OFF, Mapped IO ON, Quiet OFF.
Run the programs by loading the trap handler (as explained in the chapter) and clicking SimulatorGo and then OK in the pop-up panel.
Exercise 1 (*) - string length
Write a program that repeatedly asks the user for a string and then calculates and prints out the string length. Stop the program when the string is empty (when the user hits "enter" without anything else on the line.)
Be sure to reserve enough memory in the .data for the string. Use indexed addressing to scan through the string. Strings read in with the trap handler service include a '\n' character at the end, followed by the null termination. Don't count the '\n' or the null as part of the string length.
Exercise 2 (***) - string reversal
Write a program that asks the user for a string. After reading the string into a buffer, copy it in reversed order to a second buffer. Write out the reversed string. End the program when the first string entered is empty (when it consists only of the end of line character.)
The input strings will be terminated with "\n\0". Don't include these characters in the middle of the concatenated string.
Exercise 3 (***) - string concatenation
Write a program that repeatedly asks the user for two strings. The strings are placed in separate buffers in memory. Now, in a third buffer, create a string that is the concatenation of the two strings. Print out the new string.
Exercise 4 (***) - triangle of stars
Write a program that writes the following pattern to the simulated terminal:
*
***
*****
*******
*********
The last row starts in column one. Use a counting loop to print the five lines. The body of the counting loop contains two other loops which, in sequence, fill the line buffer with the right number of spaces and stars for the current line.
Exercise 5 (**) - dot product
Compute the dot product of two vectors. A vector is an array of integers. Both vectors are the same length. Ask the user for the length of the vectors. Then prompt for and read in the value of each element of each vector. Reserve space in memory for vectors of up to 10 elements, but allow vectors of any size one through 10.
.data
length: .word 0
vectorA: .space 40 # space for 10 integers
vectorB: .space 40 # space for 10 integers
The dot product of two vectors is the sum of the product of the corresponding elements. For example, (1, 2, 3) dot (4, 5, 6) is 1*4 + 2*5 + 3*6.
After computing it, write out the dot product to the monitor.
Exercise 6 (***) - linear search
Declare an array of integers:
.data
size: .word 12
array: .word 50,12,52,-78,03,12,99,32,53,77,47,00
Write a program that repeatedly asks the user for an integer to search for. After the user enters the integer, the program scans through the array element by element looking for the integer. When it finds a match it writes a message and reports the index where the integer was found. If the integer is not in the array it writes a failure message.
Exercise 7 (***) - averaging filter
Write a program that processes an array by applying an averaging filter to it. An averaging filter works like this: create a new array where each element at index J is the average of the three elements from the old array at indexes J-1, J, and J+1
.data
size: .word 12
array: .word 50,53,52,49,48,51,99,45,53,47,47,50
result: .word 0,0,0,0,0,0,0,0,0,0,0,0
In the above, the second element of the result is the average of 50, 53, and 52. The first and last elements of the new array are copies of the corresponding first and last elements of the old array.
After processing, write the old and new arrays to the monitor.
Exercise 8 (****) - selection sort
Perform selection sort on an array in memory:
.data
size: .word 20
array: .word 99,23,45,82,09,34,71,64,88,42,12,87,33,36,83,18,17,04,52,46
The selection sort algorithm looks like this:
int out, in, min, temp;
// each time the outer loop is
// executed, replace the element
// at out with the minimum of the
// elements to its right.
for ( out=0; out<size-1; out++ )
{
min = out;
// find the location of the minimum
// in the remaining elements
for ( in=out+1; in<size; in++ )
if ( array[in] < array[min] )
min = in;
// swap the element at out with
// the minimun of the remaining elements
temp = array[out];
array[out] = array[min];
array[min] = temp;
}
Write out the array after it has been sorted.