How to resolve the algorithm Priority queue step by step in the ARM Assembly programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Priority queue step by step in the ARM Assembly programming language
Table of Contents
Problem Statement
A priority queue is somewhat similar to a queue, with an important distinction: each item is added to a priority queue with a priority level, and will be later removed from the queue with the highest priority element first. That is, the items are (conceptually) stored in the queue in priority order instead of in insertion order.
Create a priority queue. The queue must support at least two operations:
Optionally, other operations may be defined, such as peeking (find what current top priority/top element is), merging (combining two priority queues into one), etc.
To test your implementation, insert a number of elements into the queue, each with some random priority. Then dequeue them sequentially; now the elements should be sorted by priority. You can use the following task/priority items as input data:
The implementation should try to be efficient. A typical implementation has O(log n) insertion and extraction time, where n is the number of items in the queue.
You may choose to impose certain limits such as small range of allowed priority levels, limited capacity, etc. If so, discuss the reasons behind it.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Priority queue step by step in the ARM Assembly programming language
Source code in the arm programming language
/* ARM assembly Raspberry PI */
/* program priorqueue.s */
/* Constantes */
.equ STDOUT, 1 @ Linux output console
.equ EXIT, 1 @ Linux syscall
.equ WRITE, 4 @ Linux syscall
.equ NBMAXIELEMENTS, 100
/*******************************************/
/* Structures */
/********************************************/
/* example structure item */
.struct 0
item_priority: @ priority
.struct item_priority + 4
item_address: @ string address
.struct item_address + 4
item_fin:
/* example structure heap */
.struct 0
heap_size: @ heap size
.struct heap_size + 4
heap_items: @ structure of items
.struct heap_items + (item_fin * NBMAXIELEMENTS)
heap_fin:
/*********************************/
/* Initialized data */
/*********************************/
.data
szMessEmpty: .asciz "Empty queue. \n"
szMessNotEmpty: .asciz "Not empty queue. \n"
szMessError: .asciz "Error detected !!!!. \n"
szMessResult: .ascii "Priority : " @ message result
sMessPriority: .fill 11, 1, ' '
.asciz " : "
szString1: .asciz "Clear drains"
szString2: .asciz "Feed cat"
szString3: .asciz "Make tea"
szString4: .asciz "Solve RC tasks"
szString5: .asciz "Tax return"
szCarriageReturn: .asciz "\n"
/*********************************/
/* UnInitialized data */
/*********************************/
.bss
.align 4
Queue1: .skip heap_fin @ queue memory place
/*********************************/
/* code section */
/*********************************/
.text
.global main
main: @ entry of program
ldr r0,iAdrQueue1 @ queue structure address
bl isEmpty
cmp r0,#0
beq 1f
ldr r0,iAdrszMessEmpty
bl affichageMess @ display message empty
b 2f
1:
ldr r0,iAdrszMessNotEmpty
bl affichageMess @ display message not empty
2:
@ init item 1
ldr r0,iAdrQueue1 @ queue structure address
mov r1,#3 @ priority
ldr r2,iAdrszString1
bl pushQueue @ add item in queue
cmp r0,#-1 @ error ?
beq 99f
ldr r0,iAdrQueue1 @ queue structure address
bl isEmpty
cmp r0,#0 @ not empty
beq 3f
ldr r0,iAdrszMessEmpty
bl affichageMess @ display message empty
b 4f
3:
ldr r0,iAdrszMessNotEmpty
bl affichageMess @ display message not empty
4:
@ init item 2
ldr r0,iAdrQueue1 @ queue structure address
mov r1,#4 @ priority
ldr r2,iAdrszString2
bl pushQueue @ add item in queue
cmp r0,#-1 @ error ?
beq 99f
@ init item 3
ldr r0,iAdrQueue1 @ queue structure address
mov r1,#5 @ priority
ldr r2,iAdrszString3
bl pushQueue @ add item in queue
cmp r0,#-1 @ error ?
beq 99f
@ init item 4
ldr r0,iAdrQueue1 @ queue structure address
mov r1,#1 @ priority
ldr r2,iAdrszString4
bl pushQueue @ add item in queue
cmp r0,#-1 @ error ?
beq 99f
@ init item 5
ldr r0,iAdrQueue1 @ queue structure address
mov r1,#2 @ priority
ldr r2,iAdrszString5
bl pushQueue @ add item in queue
cmp r0,#-1 @ error ?
beq 99f
5:
ldr r0,iAdrQueue1 @ queue structure address
bl popQueue @ return item
cmp r0,#-1 @ end ?
beq 100f
mov r2,r1 @ save string address
ldr r1,iAdrsMessPriority @ conversion priority
bl conversion10 @ decimal conversion
ldr r0,iAdrszMessResult
bl affichageMess @ display message
mov r0,r2 @ string address
bl affichageMess @ display message
ldr r0,iAdrszCarriageReturn
bl affichageMess
b 5b @ loop
99:
@ error
ldr r0,iAdrszMessError
bl affichageMess
100: @ standard end of the program
mov r0, #0 @ return code
mov r7, #EXIT @ request to exit program
svc #0 @ perform the system call
iAdrQueue1: .int Queue1
iAdrszString1: .int szString1
iAdrszString2: .int szString2
iAdrszString3: .int szString3
iAdrszString4: .int szString4
iAdrszString5: .int szString5
iAdrszMessError: .int szMessError
iAdrszMessEmpty: .int szMessEmpty
iAdrszMessNotEmpty: .int szMessNotEmpty
iAdrszMessResult: .int szMessResult
iAdrszCarriageReturn: .int szCarriageReturn
iAdrsMessPriority: .int sMessPriority
/******************************************************************/
/* test if queue empty */
/******************************************************************/
/* r0 contains the address of queue structure */
isEmpty:
push {r1,lr} @ save registres
ldr r1,[r0,#heap_size] @ heap size
cmp r1,#0
moveq r0,#1 @ empty queue
movne r0,#0 @ not empty
pop {r1,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* add item in queue */
/******************************************************************/
/* r0 contains the address of queue structure */
/* r1 contains the priority of item */
/* r2 contains the string address */
pushQueue:
push {r1-r9,lr} @ save registres
ldr r3,[r0,#heap_size] @ heap size
cmp r3,#0 @ heap empty ?
bne 1f
add r4,r0,#heap_items @ address of item structure
str r1,[r4,#item_priority] @ store in first item
str r2,[r4,#item_address]
mov r3,#1 @ heap size
str r3,[r0,#heap_size] @ new heap size
b 100f
1:
mov r4,r3 @ maxi index
lsr r5,r4,#1 @ current index = maxi / 2
mov r8,r1 @ save priority
mov r9,r2 @ save string address
2: @ insertion loop
cmp r4,#0 @ end loop ?
ble 3f
mov r6,#item_fin @ item size
mul r6,r5,r6 @ item shift
add r6,r0
add r6,#heap_items @ compute address item
ldr r7,[r6,#item_priority] @ load priority
cmp r7,r8 @ compare priority
ble 3f @ <= end loop
mov r1,r4 @ last index
mov r2,r5 @ current index
bl exchange
mov r4,r5 @ last index = current index
lsr r5,#1 @ current index / 2
b 2b
3: @ store item at last index find
mov r6,#item_fin @ item size
mul r6,r4,r6 @ item shift
add r6,r0
add r6,#heap_items @ item address
str r8,[r6,#item_priority]
str r9,[r6,#item_address]
add r3,#1 @ increment heap size
cmp r3,#NBMAXIELEMENTS @ maxi ?
movge r0,#-1 @ yes -> error
bge 100f
str r3,[r0,#heap_size] @ store new size
100:
pop {r1-r9,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* swap two elements of table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the first index */
/* r2 contains the second index */
exchange:
push {r3-r6,lr} @ save registers
add r5,r0,#heap_items @ address items begin
mov r3,#item_fin @ item size
mul r4,r1,r3 @ compute item 1 shift
add r4,r5 @ compute item 1 address
mul r6,r2,r3 @ compute item 2 shift
add r6,r5 @ compute item 2 address
ldr r5,[r4,#item_priority] @ exchange
ldr r3,[r6,#item_priority]
str r3,[r4,#item_priority]
str r5,[r6,#item_priority]
ldr r5,[r4,#item_address]
ldr r3,[r6,#item_address]
str r5,[r6,#item_address]
str r3,[r4,#item_address]
100:
pop {r3-r6,lr}
bx lr @ return
/******************************************************************/
/* move one element of table */
/******************************************************************/
/* r0 contains the address of table */
/* r1 contains the origin index */
/* r2 contains the destination index */
moveItem:
push {r3-r6,lr} @ save registers
add r5,r0,#heap_items @ address items begin
mov r3,#item_fin @ item size
mul r4,r1,r3 @ compute item 1 shift
add r4,r5 @ compute item 1 address
mul r6,r2,r3 @ compute item 2 shift
add r6,r5 @ compute item 2 address
ldr r5,[r4,#item_priority] @ exchange
str r5,[r6,#item_priority]
ldr r5,[r4,#item_address]
str r5,[r6,#item_address]
100:
pop {r3-r6,lr}
bx lr @ return
/******************************************************************/
/* pop queue */
/******************************************************************/
/* r0 contains the address of queue structure */
/* r0 return priority */
/* r1 return string address */
popQueue:
push {r2-r10,lr} @ save registres
mov r1,r0 @ save address queue
bl isEmpty @ control if empty queue
cmp r0,#1 @ yes -> error
moveq r0,#-1
beq 100f
@ save données à retourner
mov r0,r1 @ restaur address queue
add r4,r0,#heap_items @ address of item structure
ldr r8,[r4,#item_priority] @ save priority first item
ldr r9,[r4,#item_address] @ save address string first item
ldr r3,[r0,#heap_size] @ heap size
sub r7,r3,#1 @ last item
mov r1,r7
mov r2,#0 @ first item
bl moveItem @ move last item in first item
cmp r7,#1 @ one only item ?
beq 10f @ yes -> end
mov r4,#0 @ first index
1:
cmp r4,r7 @ = last index
bge 10f @ yes -> end
mov r5,r7 @ last index
cmp r4,#0 @ init current index
moveq r6,#1 @ = 1
lslne r6,r4,#1 @ else = first index * 2
cmp r6,r7 @ current index > last index
bgt 2f @ yes
@ no compar priority current item last item
mov r1,#item_fin
mul r1,r6,r1
add r1,r0
add r1,#heap_items @ address of current item structure
ldr r1,[r1,#item_priority]
mov r10,#item_fin
mul r10,r5,r10
add r10,r0
add r10,#heap_items @ address of last item structure
ldr r10,[r10,#item_priority]
cmp r1,r10
movlt r5,r6
2:
add r10,r6,#1 @ increment current index
cmp r10,r7 @ end ?
bgt 3f @ yes
mov r1,#item_fin @ no compare priority
mul r1,r10,r1
add r1,r0
add r1,#heap_items @ address of item structure
ldr r1,[r1,#item_priority]
mov r2,#item_fin
mul r2,r5,r2
add r2,r0
add r2,#heap_items @ address of item structure
ldr r2,[r2,#item_priority]
cmp r1,r2
movlt r5,r10
3:
mov r1,r5 @ move item
mov r2,r4
bl moveItem
mov r4,r5
b 1b @ and loop
10:
sub r3,#1
str r3,[r0,#heap_size] @ new heap size
mov r0,r8 @ return priority
mov r1,r9 @ return string address
100:
pop {r2-r10,lr} @ restaur registers
bx lr @ return
/******************************************************************/
/* display text with size calculation */
/******************************************************************/
/* r0 contains the address of the message */
affichageMess:
push {r0,r1,r2,r7,lr} @ save registres
mov r2,#0 @ counter length
1: @ loop length calculation
ldrb r1,[r0,r2] @ read octet start position + index
cmp r1,#0 @ if 0 its over
addne r2,r2,#1 @ else add 1 in the length
bne 1b @ and loop
@ so here r2 contains the length of the message
mov r1,r0 @ address message in r1
mov r0,#STDOUT @ code to write to the standard output Linux
mov r7, #WRITE @ code call system "write"
svc #0 @ call systeme
pop {r0,r1,r2,r7,lr} @ restaur registers */
bx lr @ return
/******************************************************************/
/* Converting a register to a decimal */
/******************************************************************/
/* r0 contains value and r1 address area */
.equ LGZONECAL, 10
conversion10:
push {r1-r4,lr} @ save registers
mov r3,r1
mov r2,#LGZONECAL
1: @ start loop
bl divisionpar10 @ r0 <- dividende. quotient ->r0 reste -> r1
add r1,#48 @ digit
strb r1,[r3,r2] @ store digit on area
cmp r0,#0 @ stop if quotient = 0
subne r2,#1 @ previous position
bne 1b @ else loop
@ end replaces digit in front of area
mov r4,#0
2:
ldrb r1,[r3,r2]
strb r1,[r3,r4] @ store in area begin
add r4,#1
add r2,#1 @ previous position
cmp r2,#LGZONECAL @ end
ble 2b @ loop
mov r1,#' '
3:
strb r1,[r3,r4]
add r4,#1
cmp r4,#LGZONECAL @ end
ble 3b
100:
pop {r1-r4,lr} @ restaur registres
bx lr @return
/***************************************************/
/* division par 10 signé */
/* Thanks to http://thinkingeek.com/arm-assembler-raspberry-pi/*
/* and http://www.hackersdelight.org/ */
/***************************************************/
/* r0 dividende */
/* r0 quotient */
/* r1 remainder */
divisionpar10:
/* r0 contains the argument to be divided by 10 */
push {r2-r4} @ save registers */
mov r4,r0
mov r3,#0x6667 @ r3 <- magic_number lower
movt r3,#0x6666 @ r3 <- magic_number upper
smull r1, r2, r3, r0 @ r1 <- Lower32Bits(r1*r0). r2 <- Upper32Bits(r1*r0)
mov r2, r2, ASR #2 @ r2 <- r2 >> 2
mov r1, r0, LSR #31 @ r1 <- r0 >> 31
add r0, r2, r1 @ r0 <- r2 + r1
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
pop {r2-r4}
bx lr @ return
You may also check:How to resolve the algorithm Terminal control/Unicode output step by step in the R programming language
You may also check:How to resolve the algorithm Simulate input/Keyboard step by step in the Scala programming language
You may also check:How to resolve the algorithm Read entire file step by step in the Phix programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the Haxe programming language
You may also check:How to resolve the algorithm Classes step by step in the Nemerle programming language