# Binary Search Array in ARM Assembly Language On Cyclone V FPGA On DE1-Soc. Assignment Solution.

## Instructions

Objective
Write an ARM program Convert miles to kilometres in ARM assembly language.

## Requirements and Specifications

1. You will implement the “C function” in Figure 4 in ARM assembly which is described below. This function is used as a reference code and it will help you in writing your ARM assembly code.
2. If you find any part of the explanation below unclear then try compiling the C code in Figure 4 using the Microsoft Visual Studio (the programming environment you used in APSC 160) then “single-step” through each line of code in Figure 4 using the integrated debugger in Visual Studio. If you have forgotten how to do the latter you may want to refer to the following article: https: //msdn.microsoft.com/en-us/library/y740d9d3.aspx.
3. As the name implies, the function binary_search() uses a binary search algorithm to look through a sorted array of positive integers (numbers) for a specific number (key) and returns the position of that number in the sorted array (keyIndex).
4. The start of the array is passed into binary_search() using the 32-bit integer pointer argument numbers. The syntax “int *numbers” means that “numbers” is a pointer to an integer. A pointer is just a memory address. We treat this pointer as the base of an array using the syntax “numbers[middleIndex]”. The syntax “numbers[i]” where numbers has type “pointer to int” means access (read or write) the i-th element of the integer array with base address given by the value of “numbers”.
5. The positions in array numbers are numbered 0 to endIndex. If the number key is not in the array then -1 is returned. In addition, the number of times the loop iterates is recorded in the variable “NumCalls”.
6. To see how the code operates, consider Figure 5 where we pass binary_search() the global array “numbers” which contains 100 elements numbered 0 through 99 and search an element with value equal to 418. The C keyword volatile in this code just means that the compiler should not assume it can allocate the location pointed to by ledr in a register. The result returned to main() by binary_search() is 43. Also, the contents of the array “numbers” are modified as shown in Figure 6. For example, the number 488 shown in Figure 4 has been replaced by -1 in Figure 6. This occurred when executing Line 18 in Figure 4 with the value NumCalls equal to 1. Similarly, the value 418 in Figure 5 has been replaced by -6 in Figure 6 when executing Line 18 in Figure 4 with NumCalls equal to 6. Notice how the value of NumCalls is increased on Line 20 in Figure 4.
7. When you write ARM code for this program you can verify you implemented this part correctly by examining the contents of the array “numbers” in memory in the “memory” tab of the Altera Monitor Program. This tab in the Altera Monitor Program allows you to examine the contents of the DRAM memory at any given address. Thus, you can use it to check if the elements of the array have been examined by your calls to binary_search(). You can also see the order in which your program examined them.
Screenshots of output
Source Code
```.text .globl binary_search binary_search: // int binary_search ( int * numbers , int key , int length )     push {r4-r8, lr} // // save the registers we use and return address     mov r3, #0 // startIndex = 0;     sub r4, r2, #1 // int endIndex = length - 1;     lsr r5, r4, #1 // int middleIndex = endIndex /2;     mvn r6, #0 // int keyIndex = -1;     mov r7, #1 // int NumIters = 1; while1: // while ( keyIndex == -1) {     cmn r6, #1 // // compare keyIndex with -1     bne endWhile1 // // if not equal, end while if1: // if ( startIndex > endIndex )     cmp r3, r4 // // compare startIndex with endIndex     ble elseif1 // // if startIndex <= endIndex, go to else     b endWhile1 // break ; elseif1: // else if ( numbers [ middleIndex ] == key )     ldr r8, [r0, r5, LSL #2] // // load numbers[middleIndex]     cmp r8, r1 // // compare numbers[middleIndex] with key     bne elseif2 // // if numbers[middleIndex] != key, go to else     mov r6, r5 // keyIndex = middleIndex ;     b endif1 // // go to end of if elseif2: // else if ( numbers [ middleIndex ] > key ) {                                 // // we already have numbers[middleIndex] in r8     cmp r8, r1 // // compare numbers[middleIndex] with key     ble else1 // // if numbers[middleIndex] <= key, go to else     sub r4, r5, #1 // endIndex = middleIndex -1;     b endif1 // // go to end of if else1: //} else {     add r3, r5, #1 // startIndex = middleIndex +1; endif1: //}         // // load numbers[middleIndex]     rsb r8, r7, #0 // // load -NumIters     str r8, [r0, r5, LSL #2] // numbers [ middleIndex ] = - NumIters ;     sub r8, r4, r3 // // calculate (endIndex - startIndex)     lsr r8, r8, #1 // // calculate ( endIndex - startIndex )/2;     add r5, r3, r8 // middleIndex = startIndex + ( endIndex - startIndex )/2;     add r7, r7, #1 // NumIters ++;     b while1 // // repeat while loop endWhile1: //}     mov r0, r6 //return keyIndex ;     pop {r4-r8, lr} // //restore registers and return address     mov pc,lr // // return to main ```