237 lines
8.9 KiB
Plaintext
237 lines
8.9 KiB
Plaintext
/* ARM assembly AARCH64 Raspberry PI 3B */
|
|
/* program binSearch64.s */
|
|
|
|
/*******************************************/
|
|
/* Constantes file */
|
|
/*******************************************/
|
|
/* for this file see task include a file in language AArch64 assembly*/
|
|
.include "../includeConstantesARM64.inc"
|
|
|
|
/*********************************/
|
|
/* Initialized data */
|
|
/*********************************/
|
|
.data
|
|
sMessResult: .asciz "Value find at index : @ \n"
|
|
szCarriageReturn: .asciz "\n"
|
|
sMessRecursif: .asciz "Recursive search : \n"
|
|
sMessNotFound: .asciz "Value not found. \n"
|
|
|
|
TableNumber: .quad 4,6,7,10,11,15,22,30,35
|
|
.equ NBELEMENTS, (. - TableNumber) / 8
|
|
/*********************************/
|
|
/* UnInitialized data */
|
|
/*********************************/
|
|
.bss
|
|
sZoneConv: .skip 24
|
|
/*********************************/
|
|
/* code section */
|
|
/*********************************/
|
|
.text
|
|
.global main
|
|
main: // entry of program
|
|
mov x0,4 // search first value
|
|
ldr x1,qAdrTableNumber // address number table
|
|
mov x2,NBELEMENTS // number of élements
|
|
bl bSearch
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
mov x0,#11 // search median value
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#NBELEMENTS
|
|
bl bSearch
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // decimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
mov x0,#12 //value not found
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#NBELEMENTS
|
|
bl bSearch
|
|
cmp x0,#-1
|
|
bne 2f
|
|
ldr x0,qAdrsMessNotFound
|
|
bl affichageMess
|
|
b 3f
|
|
2:
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
3:
|
|
mov x0,#35 // search last value
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#NBELEMENTS
|
|
bl bSearch
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
/****************************************/
|
|
/* recursive */
|
|
/****************************************/
|
|
ldr x0,qAdrsMessRecursif
|
|
bl affichageMess // display message
|
|
|
|
mov x0,#4 // search first value
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#0 // low index of elements
|
|
mov x3,#NBELEMENTS - 1 // high index of elements
|
|
bl bSearchR
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
mov x0,#11
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#0
|
|
mov x3,#NBELEMENTS - 1
|
|
bl bSearchR
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
mov x0,#12
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#0
|
|
mov x3,#NBELEMENTS - 1
|
|
bl bSearchR
|
|
cmp x0,#-1
|
|
bne 4f
|
|
ldr x0,qAdrsMessNotFound
|
|
bl affichageMess
|
|
b 5f
|
|
4:
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
5:
|
|
mov x0,#35
|
|
ldr x1,qAdrTableNumber
|
|
mov x2,#0
|
|
mov x3,#NBELEMENTS - 1
|
|
bl bSearchR
|
|
ldr x1,qAdrsZoneConv
|
|
bl conversion10 // décimal conversion
|
|
ldr x0,qAdrsMessResult
|
|
ldr x1,qAdrsZoneConv
|
|
bl strInsertAtCharInc // insert result at @ character
|
|
bl affichageMess // display message
|
|
|
|
|
|
100: // standard end of the program
|
|
mov x0, #0 // return code
|
|
mov x8, #EXIT // request to exit program
|
|
svc #0 // perform the system call
|
|
|
|
//qAdrsMessValeur: .quad sMessValeur
|
|
qAdrsZoneConv: .quad sZoneConv
|
|
qAdrszCarriageReturn: .quad szCarriageReturn
|
|
qAdrsMessResult: .quad sMessResult
|
|
qAdrsMessRecursif: .quad sMessRecursif
|
|
qAdrsMessNotFound: .quad sMessNotFound
|
|
qAdrTableNumber: .quad TableNumber
|
|
|
|
/******************************************************************/
|
|
/* binary search iterative */
|
|
/******************************************************************/
|
|
/* x0 contains the value to search */
|
|
/* x1 contains the adress of table */
|
|
/* x2 contains the number of elements */
|
|
/* x0 return index or -1 if not find */
|
|
bSearch:
|
|
stp x1,lr,[sp,-16]! // save registers
|
|
stp x2,x3,[sp,-16]! // save registers
|
|
stp x4,x5,[sp,-16]! // save registers
|
|
mov x3,#0 // low index
|
|
sub x4,x2,#1 // high index = number of elements - 1
|
|
1:
|
|
cmp x3,x4
|
|
bgt 99f
|
|
add x2,x3,x4 // compute (low + high) /2
|
|
lsr x2,x2,#1
|
|
ldr x5,[x1,x2,lsl #3] // load value of table at index x2
|
|
cmp x5,x0
|
|
beq 98f
|
|
bgt 2f
|
|
add x3,x2,#1 // lower -> index low = index + 1
|
|
b 1b // and loop
|
|
2:
|
|
sub x4,x2,#1 // bigger -> index high = index - 1
|
|
b 1b // and loop
|
|
98:
|
|
mov x0,x2 // find !!!
|
|
b 100f
|
|
99:
|
|
mov x0,#-1 //not found
|
|
100:
|
|
ldp x4,x5,[sp],16 // restaur 2 registers
|
|
ldp x2,x3,[sp],16 // restaur 2 registers
|
|
ldp x1,lr,[sp],16 // restaur 2 registers
|
|
ret // return to address lr x30
|
|
/******************************************************************/
|
|
/* binary search recursif */
|
|
/******************************************************************/
|
|
/* x0 contains the value to search */
|
|
/* x1 contains the adress of table */
|
|
/* x2 contains the low index of elements */
|
|
/* x3 contains the high index of elements */
|
|
/* x0 return index or -1 if not find */
|
|
bSearchR:
|
|
stp x2,lr,[sp,-16]! // save registers
|
|
stp x3,x4,[sp,-16]! // save registers
|
|
stp x5,x6,[sp,-16]! // save registers
|
|
cmp x3,x2 // index high < low ?
|
|
bge 1f
|
|
mov x0,#-1 // yes -> not found
|
|
b 100f
|
|
1:
|
|
add x4,x2,x3 // compute (low + high) /2
|
|
lsr x4,x4,#1
|
|
ldr x5,[x1,x4,lsl #3] // load value of table at index x4
|
|
cmp x5,x0
|
|
beq 99f
|
|
bgt 2f // bigger ?
|
|
add x2,x4,#1 // no new search with low = index + 1
|
|
bl bSearchR
|
|
b 100f
|
|
2: // bigger
|
|
sub x3,x4,#1 // new search with high = index - 1
|
|
bl bSearchR
|
|
b 100f
|
|
99:
|
|
mov x0,x4 // find !!!
|
|
b 100f
|
|
100:
|
|
ldp x5,x6,[sp],16 // restaur 2 registers
|
|
ldp x3,x4,[sp],16 // restaur 2 registers
|
|
ldp x2,lr,[sp],16 // restaur 2 registers
|
|
ret // return to address lr x30
|
|
/********************************************************/
|
|
/* File Include fonctions */
|
|
/********************************************************/
|
|
/* for this file see task include a file in language AArch64 assembly */
|
|
.include "../includeARM64.inc"
|