Hello,

I have been given an assignment in which I am to write an assembly language version of the following binary search function & use a suitable main program written in C to test my function. The function in C in which I had to translate to assembly is:

``````int search(int a[], int low, int high, int value)
{
int mid;

if (low > high)
return -1;
mid = ( low + high) / 2;
if (a[mid] == value)
return mid;
else if (value < a[mid])
return search(a, low, mid - 1, value);
else
return search(a, mid + 1, high, value);
}``````

The assembly code which I wrote (Yes, I was hungry):

``````[SECTION .text]

global  search

search: push    EBP
mov     EBP, ESP

add     ESP, -4         ; Allocate mid at EBP - 4
lea     EBX, [EBP + 4]  ; Load "value" into EBX
lea     ECX, [EBP + 8]  ; Load "high" into ECX
lea     EDI, [EBP + 12] ; Load "Low" into EDI
lea     ESI, [EBP + 16] ; Load array *P into ESI

cmp     EDI, ECX        ; if (low>high)
jg      poptarts        ; jmp to return -1
jmp     fishsticks      ; Keep going

poptarts:
mov     EAX, -1         ; return -1
jmp     last

fishsticks:
;       mov     [EBP - 4], 0    ; Mid = 0
mov     [EBP - 4], EDI  ; Mid = low
add     [EBP - 4], ECX  ; Mid = low + high
mov     EAX, [EBP - 4]  ; EAX = Mid == (low + high)
mov     EDX, 2
div     EDX             ; Mid / 2
mov     [EBP - 4], EAX  ; Move quotient into Mid
mov     EDX, 0

strawberry:
imul    EAX, 4          ; Multiply quotient by 4 to get dwords
add     ESI, EAX        ; Move the pointer to mid
cmp     [ESI], EBX      ; Compare mid to value
je      dorritos
jmp     ducksauce

dorritos:
mov     EAX, [ESI]
jmp     last

ducksauce:
cmp     EBX, [ESI]
jl      search1
jmp     search2

search1
mov     EBX, 0
mov     EBX, [EBP + 4]
push    EBX

mov     ECX, 0
mov     ECX, [EBP - 4]
sub     ECX, -1
push    ECX

mov     EDX, 0
mov     EDX, [EBP + 12]
push    EDX

mov     EDI, 0
mov     EDI, [EBP + 16]
push    EDI
call    search

search2:
mov     EBX, 0
mov     EBX, [EBP + 4]
push    EBX

mov     ECX, 0
mov     ECX, [EBP + 8]
push    ECX

mov     EDX, 0
mov     EDX, [EBP - 4]
push    EDX

mov     EDI, 0
mov     EDI, [EBP + 16]
push    EDI
call    search

last:   add     ESP, 4
mov     ESP, EBP
pop     EBP
ret``````

The easiest part of the program is the hardest for me, because I took courses in java instead of C. So I need to write a main program which uses scanf to initialize the elements of the array, then use a sort algorithm to sort the array and store the lowest (array[0]) and the highest (array[n-1]). Then the program needs to prompt the user for the desired value which they want to search and call the assembly search function.

Thank You

3
Contributors
9
Replies
10
Views
9 Years
Discussion Span
Last Post by csurfer

Hi if i understood you rite its a binary search program u are trying to code in C?

if its jus that then below would be your main program

``````#include<stdio.h>

void main()
{
int a[10], low=0,high=0,mid=0,value,n,i;
printf("enter the no of elements needed");
scanf("%d",&n);
printf("enter the array elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter value to be searched ");
scanf("%d"&value);
low = 0;
high = n;
mid = (low + high ) /2;
for(i=0;i<n;i++)
{
k=search(a[i],low, high,value);
}

if(k== -1)
else printf("search succesfful, the value %d is found at %d,value,mid+1);
}``````

i hpe it works..

u may have to skip the part of calculating the mid in the main pgm. as ur already calculatin in the functn

if its jus that then below would be your main program

#include<stdio.h>

void main()
{
int a[10], low=0,high=0,mid=0,value,n,i;
printf("enter the no of elements needed");
scanf("%d",&n);
printf("enter the array elements");
for(i=0;i<n;i++)
scanf("%d",&a);
printf("enter value to be searched ");
scanf("%d"&value);
low = 0;
high = n;
mid = (low + high ) /2;
for(i=0;i<n;i++)
{
k=search(a,low, high,value);
}

if(k== -1)
else printf("search succesfful, the value %d is found at %d,value,mid+1);
}
i hpe it works..

Compiled using GCC linked with your code:

``````HW7C.c: In function `main':
HW7C.c:12: error: invalid operands to binary &
HW7C.c:18: error: `k' undeclared (first use in this function)
HW7C.c:18: error: (Each undeclared identifier is reported only once
HW7C.c:18: error: for each function it appears in.)
HW7C.c:23: error: missing terminating " character
HW7C.c:24: error: syntax error before '}' token
HW7C.c:4: warning: return type of 'main' is not `int'``````

bump

Bumping is rude, kthxbye.

I think the conversation is loosing track. You want to write a C program to write main function,take input in array and then sort it through some sorting algorithm and then run search through your assembly program right? Concentrate on that.Do this first:

1)Writing a main program and taking inputs into array should be simple as it is very much similar to JAVA programming the same thing.Do it first.

2)You will get all the help needed for sorting algorithms form this community threads and also the link
http://en.wikipedia.org/wiki/Sorting_algorithm

3)If you want it still simplified here you get algorithm and modules to write bubble sort and also simulated explaination.
http://www.cs.princeton.edu/~ah/alg_anim/gawain-4.0/BubbleSort.html

4)After this concentrate on making it search for the user input in the array through your assembly code.

Don't loose your way.Concentrate on what path to take to make compiler do your work.Then you can code anything.

I think the conversation is loosing track. You want to write a C program to write main function,take input in array and then sort it through some sorting algorithm and then run search through your assembly program right? Concentrate on that.Do this first:

1)Writing a main program and taking inputs into array should be simple as it is very much similar to JAVA programming the same thing.Do it first.

2)You will get all the help needed for sorting algorithms form this community threads and also the link
http://en.wikipedia.org/wiki/Sorting_algorithm

3)If you want it still simplified here you get algorithm and modules to write bubble sort and also simulated explaination.
http://www.cs.princeton.edu/~ah/alg_anim/gawain-4.0/BubbleSort.html

4)After this concentrate on making it search for the user input in the array through your assembly code.

Don't loose your way.Concentrate on what path to take to make compiler do your work.Then you can code anything.

K I took what someone else gave me and played around with it for a while and its still not working. How about I write what im supposed to do in java to prove that im not an idiot and just not used to C syntax and then someone translates that into C for me? Just kidding, but seriously this is aggrivating. My deadline is arriving and I am still recieving the following error messages:

``````HW7C.c: In function `main':
HW7C.c:24: error: syntax error before "value"
HW7C.c:24: error: syntax error before ')' token``````

The source:

``````#include<stdio.h>

main()
{
int a[10], low=0, high=0, mid=0, value, n, i, k;
printf("Please enter the number of elements needed (Highest value): \n");
scanf("%i", &n);
printf("Please enter the array elements: \n");
for(i=0;i<n;i++)
scanf("%i", &a[i]);
printf("Please enter value to be searched: \n");
scanf("%i", &value);
low = 0;
high = n;
mid = (low + high) /2;
printf("mid: \n %i", mid);
for(i=0;i<n;i++)
{
k = search(a[i],low, high, value);
}

if(k == -1)
else printf("Search successful, the value %i is found at %i \n" value, mid+1);
}``````

all the errors have been resolved. The correct printf syntax has also been implemented. Now however, I am having a problem getting the mid value. When my code gets to the printing mid section it just prints a blank line for mid...displaying nothing in otherwords. Why is this? I have defined mid as (low + high) / 2 where low = 0 and high = n. So if 10 is entered the mid should be 5. Then when compiled with gcc as the linker between the .c file and .asm it gets to that blank mid line and then terminates due to a floating point exception. However, I use integers and no floating point numbers or IEEE in my assembly code. Therefore, it is impossible to have a floating point exception when using doublewords which are made up of integers and ints. I could see if I was using 64 floating point bit instructions in the .asm file and %lf and declaring my variables as floats running into a floating point exception. But nowhere in either of the linked sources is there any use of floating point numbers. The only thing I can figure is when the assembly program attempts to use its search function something is going terribly wrong.

In conclusion, I would like to know if there is something wrong with my C code or my assembly code....As I see nothing wrong with either.

The new updated C source:

``````#include<stdio.h>

main()
{
int a[10], low=0, high=0, mid=0, value, n, i, k;
printf("Please enter the number of elements needed (Highest value): \n");
scanf("%i", &n);
printf("Please enter the array elements: \n");
for(i=0;i<n;i++)
scanf("%i", &a[i]);
printf("Please enter value to be searched: \n");
scanf("%i", &value);
low = 0;
high = n;
mid = (low + high) /2;
printf("mid: \n %i", mid);
for(i=0;i<n;i++)
{
k = search(a[i],low, high, value);
}

if(k == -1)
else printf("Search successful, the value %i value is found at %i\n", value, mid+1);
}``````

You have used %i every where for scanning integer variables as:

``scanf("%i", &n);``

this is wrong the correct usage is,

``scanf("%d", &n);``

You need to correct this all throughout the program, and ya before calling the search function you need to call a function to sort the inputs and I didn't see any such function in your program.And I hope your search calling function is correct ;).

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.