435 lines
16 KiB
Plaintext
435 lines
16 KiB
Plaintext
/* ARM assembly Raspberry PI */
|
|
/* program deftree2.s */
|
|
|
|
/* Constantes */
|
|
.equ STDOUT, 1 @ Linux output console
|
|
.equ EXIT, 1 @ Linux syscall
|
|
.equ READ, 3
|
|
.equ WRITE, 4
|
|
|
|
.equ NBVAL, 9
|
|
|
|
/*******************************************/
|
|
/* Structures */
|
|
/********************************************/
|
|
/* structure tree */
|
|
.struct 0
|
|
tree_root: @ root pointer
|
|
.struct tree_root + 4
|
|
tree_size: @ number of element of tree
|
|
.struct tree_size + 4
|
|
tree_fin:
|
|
/* structure node tree */
|
|
.struct 0
|
|
node_left: @ left pointer
|
|
.struct node_left + 4
|
|
node_right: @ right pointer
|
|
.struct node_right + 4
|
|
node_value: @ element value
|
|
.struct node_value + 4
|
|
node_fin:
|
|
/* structure queue*/
|
|
.struct 0
|
|
queue_begin: @ next pointer
|
|
.struct queue_begin + 4
|
|
queue_end: @ element value
|
|
.struct queue_end + 4
|
|
queue_fin:
|
|
/* structure node queue */
|
|
.struct 0
|
|
queue_node_next: @ next pointer
|
|
.struct queue_node_next + 4
|
|
queue_node_value: @ element value
|
|
.struct queue_node_value + 4
|
|
queue_node_fin:
|
|
/* Initialized data */
|
|
.data
|
|
szMessInOrder: .asciz "inOrder :\n"
|
|
szMessPreOrder: .asciz "PreOrder :\n"
|
|
szMessPostOrder: .asciz "PostOrder :\n"
|
|
szMessLevelOrder: .asciz "LevelOrder :\n"
|
|
szCarriageReturn: .asciz "\n"
|
|
/* datas error display */
|
|
szMessErreur: .asciz "Error detected.\n"
|
|
/* datas message display */
|
|
szMessResult: .ascii "Element value :"
|
|
sValue: .space 12,' '
|
|
.asciz "\n"
|
|
|
|
/* UnInitialized data */
|
|
.bss
|
|
stTree: .skip tree_fin @ place to structure tree
|
|
stQueue: .skip queue_fin @ place to structure queue
|
|
/* code section */
|
|
.text
|
|
.global main
|
|
main:
|
|
mov r1,#1 @ node tree value
|
|
1:
|
|
ldr r0,iAdrstTree @ structure tree address
|
|
bl insertElement @ add element value r1
|
|
cmp r0,#-1
|
|
beq 99f
|
|
add r1,#1 @ increment value
|
|
cmp r1,#NBVAL @ end ?
|
|
ble 1b @ no -> loop
|
|
|
|
ldr r0,iAdrszMessPreOrder
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree @ tree root address (begin structure)
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl preOrder
|
|
|
|
ldr r0,iAdrszMessInOrder
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl inOrder
|
|
|
|
ldr r0,iAdrszMessPostOrder
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl postOrder
|
|
|
|
ldr r0,iAdrszMessLevelOrder
|
|
bl affichageMess
|
|
ldr r3,iAdrstTree
|
|
ldr r0,[r3,#tree_root]
|
|
ldr r1,iAdrdisplayElement @ function to execute
|
|
bl levelOrder
|
|
b 100f
|
|
99: @ display error
|
|
ldr r0,iAdrszMessErreur
|
|
bl affichageMess
|
|
100: @ standard end of the program
|
|
mov r7, #EXIT @ request to exit program
|
|
svc 0 @ perform system call
|
|
iAdrszMessInOrder: .int szMessInOrder
|
|
iAdrszMessPreOrder: .int szMessPreOrder
|
|
iAdrszMessPostOrder: .int szMessPostOrder
|
|
iAdrszMessLevelOrder: .int szMessLevelOrder
|
|
iAdrszMessErreur: .int szMessErreur
|
|
iAdrszCarriageReturn: .int szCarriageReturn
|
|
iAdrstTree: .int stTree
|
|
iAdrstQueue: .int stQueue
|
|
iAdrdisplayElement: .int displayElement
|
|
/******************************************************************/
|
|
/* insert element in the tree */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the tree structure */
|
|
/* r1 contains the value of element */
|
|
/* r0 returns address of element or - 1 if error */
|
|
insertElement:
|
|
push {r1-r7,lr} @ save registers
|
|
mov r4,r0
|
|
mov r0,#node_fin @ reservation place one element
|
|
bl allocHeap
|
|
cmp r0,#-1 @ allocation error
|
|
beq 100f
|
|
mov r5,r0
|
|
str r1,[r5,#node_value] @ store value in address heap
|
|
mov r1,#0
|
|
str r1,[r5,#node_left] @ init left pointer with zero
|
|
str r1,[r5,#node_right] @ init right pointer with zero
|
|
ldr r2,[r4,#tree_size] @ load tree size
|
|
cmp r2,#0 @ 0 element ?
|
|
bne 1f
|
|
str r5,[r4,#tree_root] @ yes -> store in root
|
|
b 4f
|
|
1: @ else search free address in tree
|
|
ldr r3,[r4,#tree_root] @ start with address root
|
|
add r6,r2,#1 @ increment tree size
|
|
clz r7,r6 @ compute zeroes left bits
|
|
add r7,#1 @ for sustract the first left bit
|
|
lsl r6,r7 @ shift number in left
|
|
2:
|
|
lsls r6,#1 @ read left bit
|
|
bcs 3f @ is 1 ?
|
|
ldr r1,[r3,#node_left] @ no store node address in left pointer
|
|
cmp r1,#0 @ if equal zero
|
|
streq r5,[r3,#node_left]
|
|
beq 4f
|
|
mov r3,r1 @ else loop with next node
|
|
b 2b
|
|
3: @ yes
|
|
ldr r1,[r3,#node_right] @ store node address in right pointer
|
|
cmp r1,#0 @ if equal zero
|
|
streq r5,[r3,#node_right]
|
|
beq 4f
|
|
mov r3,r1 @ else loop with next node
|
|
b 2b
|
|
4:
|
|
add r2,#1 @ increment tree size
|
|
str r2,[r4,#tree_size]
|
|
100:
|
|
pop {r1-r7,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* preOrder */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 function address */
|
|
preOrder:
|
|
push {r1-r2,lr} @ save registers
|
|
cmp r0,#0
|
|
beq 100f
|
|
mov r2,r0
|
|
blx r1 @ call function
|
|
|
|
ldr r0,[r2,#node_left]
|
|
bl preOrder
|
|
ldr r0,[r2,#node_right]
|
|
bl preOrder
|
|
100:
|
|
pop {r1-r2,lr} @ restaur registers
|
|
bx lr
|
|
/******************************************************************/
|
|
/* inOrder */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 function address */
|
|
inOrder:
|
|
push {r1-r3,lr} @ save registers
|
|
cmp r0,#0
|
|
beq 100f
|
|
mov r3,r0
|
|
mov r2,r1
|
|
ldr r0,[r3,#node_left]
|
|
bl inOrder
|
|
mov r0,r3
|
|
blx r2 @ call function
|
|
|
|
ldr r0,[r3,#node_right]
|
|
mov r1,r2
|
|
bl inOrder
|
|
100:
|
|
pop {r1-r3,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* postOrder */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 function address */
|
|
postOrder:
|
|
push {r1-r3,lr} @ save registers
|
|
cmp r0,#0
|
|
beq 100f
|
|
mov r3,r0
|
|
mov r2,r1
|
|
ldr r0,[r3,#node_left]
|
|
bl postOrder
|
|
|
|
ldr r0,[r3,#node_right]
|
|
mov r1,r2
|
|
bl postOrder
|
|
mov r0,r3
|
|
blx r2 @ call function
|
|
100:
|
|
pop {r1-r3,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* levelOrder */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the node */
|
|
/* r1 function address */
|
|
levelOrder:
|
|
push {r1-r4,lr} @ save registers
|
|
cmp r0,#0
|
|
beq 100f
|
|
mov r2,r1
|
|
mov r1,r0
|
|
ldr r0,iAdrstQueue @ adresse queue
|
|
bl enqueueNode @ queue the node
|
|
1: @ begin loop
|
|
ldr r0,iAdrstQueue
|
|
bl isEmptyQueue @ is queue empty
|
|
cmp r0,#0
|
|
beq 100f @ yes -> end
|
|
ldr r0,iAdrstQueue
|
|
bl dequeueNode
|
|
mov r3,r0 @ save node
|
|
blx r2 @ call function
|
|
ldr r4,[r3,#node_left] @ left node ok ?
|
|
cmp r4,#0
|
|
beq 2f @ no
|
|
ldr r0,iAdrstQueue @ yes -> enqueue
|
|
mov r1,r4
|
|
bl enqueueNode
|
|
2:
|
|
ldr r4,[r3,#node_right] @ right node ok ?
|
|
cmp r4,#0
|
|
beq 3f @ no
|
|
ldr r0,iAdrstQueue @ yes -> enqueue
|
|
mov r1,r4
|
|
bl enqueueNode
|
|
3:
|
|
b 1b @ and loop
|
|
|
|
100:
|
|
pop {r1-r4,lr} @ restaur registers
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* display node */
|
|
/******************************************************************/
|
|
/* r0 contains node address */
|
|
displayElement:
|
|
push {r1,lr} @ save registers
|
|
ldr r0,[r0,#node_value]
|
|
ldr r1,iAdrsValue
|
|
bl conversion10S
|
|
ldr r0,iAdrszMessResult
|
|
bl affichageMess
|
|
100:
|
|
pop {r1,lr} @ restaur registers
|
|
bx lr @ return
|
|
iAdrszMessResult: .int szMessResult
|
|
iAdrsValue: .int sValue
|
|
/******************************************************************/
|
|
/* enqueue node */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the queue */
|
|
/* r1 contains the value of element */
|
|
/* r0 returns address of element or - 1 if error */
|
|
enqueueNode:
|
|
push {r1-r5,lr} @ save registers
|
|
mov r4,r0
|
|
mov r0,#queue_node_fin @ allocation place heap
|
|
bl allocHeap
|
|
cmp r0,#-1 @ allocation error
|
|
beq 100f
|
|
mov r5,r0 @ save heap address
|
|
str r1,[r5,#queue_node_value] @ store node value
|
|
mov r1,#0
|
|
str r1,[r5,#queue_node_next] @ init pointer next
|
|
ldr r0,[r4,#queue_end]
|
|
cmp r0,#0
|
|
strne r5,[r0,#queue_node_next]
|
|
streq r5,[r4,#queue_begin]
|
|
str r5,[r4,#queue_end]
|
|
mov r0,#0
|
|
pop {r1-r5,lr}
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* dequeue node */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the queue */
|
|
/* r0 returns address of element or - 1 if error */
|
|
dequeueNode:
|
|
push {r1-r5,lr} @ save registers
|
|
ldr r4,[r0,#queue_begin]
|
|
ldr r5,[r4,#queue_node_value]
|
|
ldr r6,[r4,#queue_node_next]
|
|
str r6,[r0,#queue_begin]
|
|
cmp r6,#0
|
|
streq r6,[r0,#queue_end]
|
|
mov r0,r5
|
|
100:
|
|
pop {r1-r5,lr}
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* dequeue node */
|
|
/******************************************************************/
|
|
/* r0 contains the address of the queue */
|
|
/* r0 returns 0 if empty else 1 */
|
|
isEmptyQueue:
|
|
ldr r0,[r0,#queue_begin]
|
|
cmp r0,#0
|
|
movne r0,#1
|
|
bx lr @ return
|
|
/******************************************************************/
|
|
/* memory allocation on the heap */
|
|
/******************************************************************/
|
|
/* r0 contains the size to allocate */
|
|
/* r0 returns address of memory heap or - 1 if error */
|
|
/* CAUTION : The size of the allowance must be a multiple of 4 */
|
|
allocHeap:
|
|
push {r5-r7,lr} @ save registers
|
|
@ allocation
|
|
mov r6,r0 @ save size
|
|
mov r0,#0 @ read address start heap
|
|
mov r7,#0x2D @ call system 'brk'
|
|
svc #0
|
|
mov r5,r0 @ save address heap for return
|
|
add r0,r6 @ reservation place for size
|
|
mov r7,#0x2D @ call system 'brk'
|
|
svc #0
|
|
cmp r0,#-1 @ allocation error
|
|
movne r0,r5 @ return address memory heap
|
|
pop {r5-r7,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 registers
|
|
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 system
|
|
pop {r0,r1,r2,r7,lr} @ restaur registers
|
|
bx lr @ return
|
|
/***************************************************/
|
|
/* Converting a register to a signed decimal */
|
|
/***************************************************/
|
|
/* r0 contains value and r1 area address */
|
|
conversion10S:
|
|
push {r0-r4,lr} @ save registers
|
|
mov r2,r1 @ debut zone stockage
|
|
mov r3,#'+' @ par defaut le signe est +
|
|
cmp r0,#0 @ negative number ?
|
|
movlt r3,#'-' @ yes
|
|
mvnlt r0,r0 @ number inversion
|
|
addlt r0,#1
|
|
mov r4,#10 @ length area
|
|
1: @ start loop
|
|
bl divisionpar10U
|
|
add r1,#48 @ digit
|
|
strb r1,[r2,r4] @ store digit on area
|
|
sub r4,r4,#1 @ previous position
|
|
cmp r0,#0 @ stop if quotient = 0
|
|
bne 1b
|
|
|
|
strb r3,[r2,r4] @ store signe
|
|
subs r4,r4,#1 @ previous position
|
|
blt 100f @ if r4 < 0 -> end
|
|
|
|
mov r1,#' ' @ space
|
|
2:
|
|
strb r1,[r2,r4] @store byte space
|
|
subs r4,r4,#1 @ previous position
|
|
bge 2b @ loop if r4 > 0
|
|
100:
|
|
pop {r0-r4,lr} @ restaur registers
|
|
bx lr
|
|
/***************************************************/
|
|
/* division par 10 unsigned */
|
|
/***************************************************/
|
|
/* r0 dividende */
|
|
/* r0 quotient */
|
|
/* r1 remainder */
|
|
divisionpar10U:
|
|
push {r2,r3,r4, lr}
|
|
mov r4,r0 @ save value
|
|
//mov r3,#0xCCCD @ r3 <- magic_number lower raspberry 3
|
|
//movt r3,#0xCCCC @ r3 <- magic_number higter raspberry 3
|
|
ldr r3,iMagicNumber @ r3 <- magic_number raspberry 1 2
|
|
umull r1, r2, r3, r0 @ r1<- Lower32Bits(r1*r0) r2<- Upper32Bits(r1*r0)
|
|
mov r0, r2, LSR #3 @ r2 <- r2 >> shift 3
|
|
add r2,r0,r0, lsl #2 @ r2 <- r0 * 5
|
|
sub r1,r4,r2, lsl #1 @ r1 <- r4 - (r2 * 2) = r4 - (r0 * 10)
|
|
pop {r2,r3,r4,lr}
|
|
bx lr @ leave function
|
|
iMagicNumber: .int 0xCCCCCCCD
|