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

Instructions

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.