.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 R7, [SP, #16] //SP[4] = R7;
    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; //compare startIndex and endIndex
    BLE booleanOne;
    MOV R0, #-1; //returns -1 if startIndex > endIndex

    LDR LR, [SP, #0];
    ADD SP, SP, #28; //Pop everything out of the stack
    MOV PC, LR; //I dont understand this shit

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: //finally returning