Tölvuhögun
Assignment 3: Queue
Valdemar Örn Erlingsson
a)Pseudo-code( Pseudo-C … more like Java tonight… :)
// Global variables
int[10] values;
int min //minimum allowed address = values[0]
int max //maximum allowed address = values[9]
int length;
int* low;// Low is a pointer, pointing to the back of the circular register
int* high;// High is a pointer, pointing to the front of the circular register
void main()
{
length = 0; //length of queue = 0
low = values; //point to the start of queue
high = values;
min = values;// Set numerical values for min & max
max = values + 9;
print("\n\n"); //empty first line, for looks
while(true)
{
print("\n\n");
printQueue(); //Queue contains: ......
doMenu();
}
}
void printQueue()
{
print("Queue contains: ");
int pointer = low;// Set starting point
for(int count=0; count<length; count++)
{
print(*pointer + " ");// Print the value in the pointer
pointer++;
if (pointer > max) pointer = min; //Go around, in a circle
}
print("\n");
}
void doMenu()
{
print("Select an operation \n\n");
print("\t (1) Add new value \n");
print("\t (2) Remove oldest value \n");
print("\t (3) Clear the queue \n");
print("\t (4) Quit program \n\n");
input <- (input from user);
(Clear the screen)
if(input == 1)
add();
elseif(input == 2)
remove();
elseif(input == 3)
clear();
elseif(input == 4)
quit();
else
return
// back to main
}
void add()
{
if (length < 10)
{
print("Insert value: ")
input <- (input from user);
*high = input;// insert the new value into the queue
high++;// increment the front pointer
if (high > max) high = min; // Go in a circle
length++;
print("The number " + input + " was added, queue now contains " + length + " items ");
}
else
{
print("The queue is already full!\n");
}
}
void remove()
{
if(length > 0)
{
print("The number " + *low + " has been removed");
low++;// increment the back pointer
if (low > max) low = min; // Go in a circle
length--;
}
else
{
print("The queue is already empty!\n");
}
}
void clear()
{
low = min;
high = min;
length = 0;
print("The queue is now empty");
}
void quit()
{
(invoke Trap task #9)
}
b)Assembly code
*------
* Program :Queue
* Written by :Valdemar Erlingsson
* Date :26.11.2008
* Description:
*------
STARTORG$1000
BRAMAIN
valueDS.w10* Reserve space 10 numbers
minDS.w1
maxDS.w1
lowDS.w1
highDS.w1
lengthDS.w1
incrDS.b1
NOP
MAIN * ------
LEAvalue,A1* Get address of value[0]
MOVEA1,min* Store address in min
MOVEA1,low* Set low to min
MOVEA1,high* Set high to min
MOVEA1,D0
ADDI#18,D0* add 18 (9 words) to address
MOVED0,max* store address in max
MOVEQ#0,D0
MOVED0,length* set length = 0
MOVEQ#2,D0
MOVED0,incr* set length = 0
LEASPACE,A1* Make empty line
MOVE.B#13,D0
TRAP #15
LOOP
LEASPACE,A1* Make empty line
MOVE.B#13,D0
TRAP #15
BSRPRINTQ* Print the Queue
BSRDOMENU* Run the menu function
BRALOOP* Not needed, but just in case...
SPACEDC.B' ',0
NOP
PRINTQ * ------
LEAPRNTQTX,A1* 'Queue contains: '
MOVE.B#14,D0
TRAP #15
MOVElow,A2* A2 = pointer
MOVEQ#0,D5* D5 = count
PRINTLOOP
CMPlength,D5* count<length ?
BGEENDPRNTQ
MOVE(A2),D1* Ready *pointer for printing
MOVE.B#3,D0* Print *pointer
TRAP #15
LEASPACE,A1* Make space
MOVE.B#14,D0
TRAP #15
ADDI#1,D5* Increment count
ADDAincr,A2* pointer points to next value
MOVEA2,D6* D6 placeholder for high
CMPmax,D6* is pointer > max?
BLENOTOVERPRINT
MOVEAmin,A2* pointer > max, set pointer to min
NOTOVERPRINT
BRAPRINTLOOP
ENDPRNTQ
LEASPACE,A1* Make empty line
MOVE.B#13,D0
TRAP #15
RTS
PRNTQTXDC.B'Queue contains: ',0
NOP
DOMENU * ------
LEAMENTXT,A1* Print the menu
MOVE.B#13,D0
TRAP #15
MOVE.B#4,D0* Query for input
TRAP #15* input in D1
MOVED1,D5* Store input in D5
MOVEQ#0,D1* Clear the screen
ADDI#65280,D1* Special Clear command
MOVE.B#11,D0
TRAP#15
CMPI#1,D5
BEQADD
CMPI#2,D5
BEQREMOVE
CMPI#3,D5
BEQCLEAR
CMPI#4,D5
BEQQUIT
LEASPACE,A1* Make empty line
MOVE.B#13,D0
TRAP #15
BRALOOP* Options did not fit, query again
MENTXTDC.B'Select an operation',$0D,$0A
MENTXT2DC.B$09,'(1) Add new value',$0D,$0A
MENTXT3DC.B$09,'(2) Remove oldest value',$0D,$0A
MENTXT4DC.B$09,'(3) Clear the queue',$0D,$0A
MENTXT5DC.B$09,'(4) Quit the program',$0D,$0A,0
NOP
ADD * ------
CMP#10,length
BGEFULL
* Not full
LEAQVACANT,A1* input request
MOVE.B#14,D0
TRAP #15
MOVE.B#4,D0* Query for input
TRAP #15* input in D1
MOVEhigh,A1
MOVE.WD1,(A1)* Move input to high
ADDI#2,high* increment high by 1 word
MOVEhigh,D6* D6 placeholder for high
CMPmax,D6* is high > max?
BLENOTOVERADD
MOVEmin,high* high > max, set high to min
NOTOVERADD
ADDI#1,length* increase length by 1
BRALOOP* Go back to menu
FULL
LEAQISFULL,A1* Print warning
MOVE.B#14,D0
TRAP #15
BRALOOP* Go back to menu
QVACANTDC.B'Enter the value you wish to add: ',0
QISFULLDC.B'The queue is already full!',$0D,$0A,0
BRALOOP
REMOVE * ------
CMP#0,length
BEQEMPTY
* Not empty
MOVEAlow,A2
MOVE(A2),D1* Move *low to D1
LEAQREMOVD,A1* Print 'This value was removed: '
MOVE.B#14,D0
TRAP #15
MOVE.B#3,D0* Print actual value
TRAP #15
LEASPACE,A1* Print carrier return
MOVE.B#13,D0
TRAP #15
ADDI#2,low* increment low by 1 word
MOVElow,D6* D6 placeholder for high
CMPmax,D6* is low > max?
BLENOTOVERREM
MOVEmin,low* low > max, set low to min
NOTOVERREM
ADDI#-1,length* increase length by 1
BRALOOP* Go back to menu
EMPTY
LEAQISEMPT,A1* Print warning
MOVE.B#13,D0
TRAP #15
BRALOOP* Go back to menu
QREMOVDDC.B'This value was removed: ',0
QISEMPT DC.B'The queue is empty!',$0D,$0A,0
BRALOOP
NOP
CLEAR * ------
MOVEmin,low
MOVEmin,high
MOVEQ#0,D2
MOVED2,length
LEACLEARED,A1* Print warning
MOVE.B#13,D0
TRAP #15
BRALOOP* Go back to menu
CLEAREDDC.B'All values have been removed',0
NOP
QUIT * ------
MOVE.B#9,D0
TRAP#15Halt Simulator
ENDSTART
This was definitely not easy to implement in assembly. Thes code is not highly readable and branching is awkward.
I had to add NOP command after some of the define constant blocks, the reason why this was needed is unknown to me, I only know that it didn't work without them.
I left the pseudo-code mostly un-commented, however the assembly code is heavily commented wherever major (or non-trivial) operations are performed. It can still be a pain to follow the program flow.