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
        add     ESP, 16

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]
        add     EDX, 1
        push    EDX

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

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.

Please help,

Thank You

Recommended Answers

All 9 Replies

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)
printf("element not found");
else printf("search succesfful, the value %d is found at %d,value,mid+1);
}

i hpe it works..

commented: Bad code -2

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)
printf("element not found");
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'

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)
                printf("element not found \n");
        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)
                printf("element not found \n");
        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 ;).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.