ARM Recursive Binary Search

Assignment

Solution 

.data

numbers:    .word   28,37,44,60,85,99,121,127,129,138

.word   143,155,162,164,175,179,205,212,217,231

.word   235,238,242,248,250,258,283,286,305,311

.word   316,322,326,351,355,364,366,376,391,398

.word   408,410,415,418,425,437,441,452,474,488

.word   506,507,526,532,534,547,548,583,585,595

.word   603,621,640,661,666,690,692,713,719,750

.word   755,768,775,776,784,785,791,797,798,804

.word   828,842,846,858,884,887,890,893,908,936

.word   939,953,960,970,978,979,981,990,1002,1007

.text

.globl main

main:                           @ main function

stmfdsp!,{lr}              @ save lr

ldr r0,=numbers             @ pointer to array

ldr r1,=#418                @ key

mov r2,#0                   @ start index

mov r3,#99                  @ end index

mov r4,#0

stmfdsp!,{r4}              @ pass num calls on the stack

blbinary_search           @ call binary search

ldr   r1, =0xFF200000         @ load ledr_base in r1

str r0,[r1,#0]              @ save final value in ledr_base to display on leds

mov r0,#0                   @ exit without error

ldmfdsp!,{lr}              @ restore lr

movpc,lr                 @ return

@——————————————–

@ binary search routine

@ On entry:

@   r0 = address of numbers array

@   r1 = key

@   r2 = start index

@   r3 = end Index

@   [sp,#0] = num calls

binary_search:

stmfdsp!,{r4-r7,lr}        @ save registers on the stack

sub sp,sp,#4                @ allocate space for a temporary variable

sub r5,r3,r2                @ calculate endindex-startindex

lsr r5,r5,#1                @ divide by 2

add r5,r5,r2                @ calculate middle: startindex + (endindex-startindex)/2

ldr r4,[sp,#24]             @ load numcalls from stack

add r4,r4,#1                @ increment numcalls

if1:

cmp r2,r3                   @ if startindex>endindex

ble if2

mov r0,#-1                  @ return -1

b   ret1

if2:

ldr r6,[r0,r5,lsl #2]       @ load numbers[middleIndex] in r6

cmp r6,r1                   @ if (numbers[middleindex]==key)

bne if3

mov r7,r5                   @ keyindex= middleindex

b   save1

if3:

cmp r6,r1                   @ if (numbers[middleindex]>key)

ble else1

str r0,[sp,#0]              @ save r0 in the stack

sub r3,r5,#1                @ set end index to middleIndex-1

stmfdsp!,{r4}              @ pass num calls on the stack

blbinary_search           @ recurse

mov r7,r0                   @ keyindex = binary_search(numbers,key,start,middle-1,numcalls)

ldr r0,[sp,#0]              @ load r0 from the stack

b   save1

else1:

str r0,[sp,#0]              @ save r0 in the stack

add r2,r5,#1                @ set start index to middleIndex+1

stmfdsp!,{r4}              @ pass num calls on the stack

blbinary_search           @ recurse

mov r7,r0                   @ keyindex = binary_search(numbers,key,middle+1,end,numcalls)

ldr r0,[sp,#0]              @ load r0 from the stack

save1:

mvn r4,r4                   @ calculate -numCalls

add r4,r4,#1

str r4,[r0,r5,lsl #2]       @ save numcalls: numbers[middleIndex]=-numCalls

mov r0,r7                   @ return keyIndex

ret1:

add sp,sp,#4                @ remove temp variable from stack

ldmfdsp!,{r4-r7,lr}        @ pop registers from the stack

add sp,sp,#4                @ remove passed argument from stack

movpc,lr                   @ return