/* 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"