.include "address_map_arm.s"
.text
.global binary_search

_mystart:

binary_search: //R0 *numbers; R1 key; R2 startIndex; R3 endIndex
    SUB SP, SP, #28 //making space for 7 other registers
    STR R8, [SP, #20] //SP[5] = R8; middleIndex
    STR R0, [SP, #16] //SP[4] = R0; back up of *numbers
    STR R6, [SP, #12] //SP[3] = R6; numbers[middleIndex]
    STR R5, [SP, #8]  //SP[2] = R5; keyIndex
    STR R4, [SP, #4]  //SP[1] = R4; NumCalls
    STR LR, [SP, #0]  //SP[0] = LR

    SUB R8, R3, R2 //
    ADD R8, R2, R8, LSR#1

    LDR R4, [SP, #24] //loading NumCalls onto R4
    ADD R4, R4, #1    //NumCalls++
    STR R4, [SP, #24] //storing R4 onto NumCalls

    LDR R6, [R0, R8, LSL#2] //R6 = numbers[middleIndex]

    CMP R2, R3
    BLE booleanOne


    MOV R0, #-1 //returns -1 if startIndex > endIndex

    //restore
    LDR R8, [SP, #20]
    LDR R6, [SP, #12]
    LDR R5, [SP, #8]
    LDR R4, [SP, #4]
    LDR LR, [SP, #0]

    ADD SP, SP, #28 //Pop everything out of the stack
    MOV PC, LR

booleanOne: //numbers[middleIndex] == key
    CMP R6, R1
    BNE booleanTwo
    MOV R5, R8
    B returnStep

booleanTwo: //numbers[middleIndex] > key
    CMP R6, R1
    BLE booleanThree
    SUB R3, R8, #1;
    BL binary_search;
    MOV R5, R0;
    B returnStep

booleanThree: //else
    ADD R2, R8, #1;
    BL binary_search;
    MOV R5, R0;
    B returnStep;

returnStep:
    RSB R6, R4, #0 //-NumCalls
    LDR R7, [SP, #16]
    STR R6, [R7, R8, LSL#2] //assigning -NumCalls to number[middleIndex]
    MOV R0, R5

    //restore
    LDR R8, [SP, #20]
    LDR R6, [SP, #12]
    LDR R5, [SP, #8]
    LDR R4, [SP, #4]
    LDR LR, [SP, #0]

    ADD SP, SP, #28
    MOV PC, LR