Anonymous user
Priority queue: Difference between revisions
Add task to ARM assembly Raspberry pi
(Add task to ARM assembly Raspberry pi) |
|||
Line 67:
{{out}}
<pre></pre>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<lang ARM Assembly>
/* 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
</lang>
{{out}}
<pre>
Empty queue.
Not empty queue.
Priority : 1 : Solve RC tasks
Priority : 2 : Tax return
Priority : 3 : Clear drains
Priority : 4 : Feed cat
Priority : 5 : Make tea
</pre>
=={{header|AutoHotkey}}==
<lang AutoHotkey>;-----------------------------------
| |||