Write an ARM assembly program that performs a recursive binary search. For each
ID: 3766584 • Letter: W
Question
Write an ARM assembly program that performs a recursive binary search. For each call to recursiveBinarySearch you must use a full descending stack to pass all 4 arguments. The result will be returned in register 0. Model your assembler code after the following C implementation:
int * recursiveBinarySearch(int a[ ], int lb, int ub, int value) {
// lb = lower-bound indice
// ub = upper-bound indice
// value = search value
int half;
if (lb > ub)
return NULL; //value is not in the array
half = (lb+ub) / 2;
if(a[half] == value) //value is in the array
return &a[half]; //return value's address
else if(a[half] > value)
return recursiveBinarySearch (a, lb, half-1, value); //search lower array half
else
return recursiveBinarySearch (a, half+1, ub, value); //search upper array half
};
void main( ) {
const int arraySize = 11;
int myArray[arraySize] = {3,6,8,12,17,22,45,67,99,2089,30001};
int* locationPointer = recursiveBinarySearch(myArray, 0, arraySize-1, 17);
};
Explanation / Answer
#include<stdio.h>
int main(){
int a[10],i,n,m,c,l,u;
printf("Enter the size of an array: ");
scanf("%d",&n);
printf("Enter the elements of the array: " );
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
printf("Enter the number to be search: ");
scanf("%d",&m);
l=0,u=n-1;
c=binary(a,n,m,l,u);
if(c==0)
printf("Number is not found.");
else
printf("Number is found.");
return 0;
}
int binary(int a[],int n,int m,int l,int u){
int mid,c=0;
if(l<=u){
mid=(l+u)/2;
if(m==a[mid]){
c=1;
}
else if(m<a[mid]){
return binary(a,n,m,l,mid-1);
}
else
return binary(a,n,m,mid+1,u);
}
else
return c;
}
ARM assembly program
SRAM_BASE EQU 0x40000000
AREA program6, CODE, READONLY
ENTRY
main
MOV r9, #0
MOV r10, #6
MOV r11, #8
LDR sp, =SRAM_BASE
MOV r1, #0
MOV r2, #5
MOV r3, #6
MOV r4, #8
MOV r5, #11
MOV r6, #12
MOV r7, #16
STMIA sp!, {r1-r7}
BL RBS
LDMDB sp!, {r1-r7}
stop B stop
RBS
;LDR r1, [sp, #-0x1C]
;LDR r2, [sp, #-0x18]
;LDR r3, [sp, #-0x14]
;LDR r4, [sp, #-0x10]
;LDR r5, [sp, #-0xC]
;LDR r6, [sp, #-0x8]
;LDR r7, [sp, #-0x4]
CMP r9, r10 ;compare ub to lb
BGT error ;if ub<lb error
ADD r8, r9, r10 ;add lb and ub
MOV r8, r8, LSR#1 ;half = (lb+ub)/2
mov r13,r8 ;copy the half to new register
CMP r11, r13 ;compare the search to half
MOVEQ r0, r13 ;if a[half] == value
SUBLT r8, r8, #1 ;if a[half] > value, half-1
MOVLT r10, r8 ;ub= half
BLT RBS ;go through again
ADDGT r8, r8, #1 ;if a[half] < value, half+1
MOVGT r9, r8 ;lb = half
BGT RBS
LDMDB sp!, {r1-r7, pc} ;go back to main
stop B stop
END
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.