Sunday, February 19, 2012

Booths Algorithm Solver in C ( 8 bit )

#include<stdio.h>
void dectobin(int n,int a[])
{
    int x=0,b[8],i;
    for(i=0;i<8;i++)
        b[i]=-1;
    do
    {
        b[x++]=n%2;
        n=n/2;
    }
    while(n!=0);
    for(i=7;i>=0;i--)
    {    
        if(b[i]==-1)
            a[7-i]=0;
        else
            a[7-i]=b[i];
    }
}
int bintodec(int a[])
{
    int base=1,i,dec=0;
    for(i=15;i>=0;i--)
    {
        dec=dec+(a[i]*base);
        base=base*2;
    }
    return dec;
}
void shift_right(int a[],int q[],int *q1)
{    
    int i;
    int t1[8];
    int t2[8];
    t1[0]=a[0];
    t2[0]=a[7];
    *q1=q[7];
    for(i=1;i<8;i++)
        t1[i]=a[i-1];
    for(i=0;i<8;i++)
        a[i]=t1[i];    
    for(i=1;i<8;i++)
        t2[i]=q[i-1];
    for(i=0;i<8;i++)
        q[i]=t2[i];
}
void add(int array_value1[],int array_value2[],int a[])
{
    int array_value3[8];
    int overflow[9];
    int i;
    for (i=0;i<8;i++) 
        overflow[i]=0;
    for (i=7;i>=0;i--)
    {
        a[i]=array_value1[i]+array_value2[i]+overflow[i];
        if(a[i]>1)
        {
            overflow[i-1]=1;
            a[i]%=2;
        }
    }
}
void complement(int input[],int c[])
{
    int i;
    for(i=0;i<8;i++)
    {
        if(input[i]==0)
            c[i]=1;
        else
            c[i]=0;
    }
}
void sub(int array_value1[],int array_value2[],int a[])
{
    int t[8],t1[8],t2[8];
    complement(array_value2,t1);
    int t3[8]={0,0,0,0,0,0,0,1};
    add(array_value1,t1,t);
    complement(t,a);
}
void display(int a[],int q[],int q1,int m[],int event_id)
{
    int i;
    printf("\n");
    for(i=0;i<8;i++)
        printf("%d",a[i]);
    printf("\t");
    for(i=0;i<8;i++)
        printf("%d",q[i]);
    printf("\t");
    printf("%d",q1);
    printf("\t");
    for(i=0;i<8;i++)
        printf("%d",m[i]);
    printf("\t");
    if(event_id==0)
        printf("Shift Right");
    if(event_id==1)
        printf("A<--A-M");
    if(event_id==2)
        printf("A<--A+M");
    printf("\n-------------------------------------------------");
}
void event_00(int a[],int q[],int *q1,int m[])
{
    shift_right(a,q,q1);
    display(a,q,*q1,m,0);
}
void event_11(int a[],int q[],int *q1,int m[])
{
    shift_right(a,q,q1);
    display(a,q,*q1,m,0);
}
void event_10(int a[],int q[],int *q1,int m[])
{
    sub(m,a,a);
    display(a,q,*q1,m,1);    
    shift_right(a,q,q1);
    display(a,q,*q1,m,0);
}
void event_01(int a[],int q[],int *q1,int m[])
{
    add(m,a,a);
    display(a,q,*q1,m,2);    
    shift_right(a,q,q1);
    display(a,q,*q1,m,0);
}
main()
{
    printf("================================================\n");
    printf("*****Program To Implement Booth's Algorithm*****\n");
    printf("================================================\n\n");
    int a[8],q[8],q1=0,m[8],res[16];
    int mp,ml,i,x=0;
    for(i=0;i<8;i++)
        a[i]=0;
    printf("Enter multiplicand value:");
    scanf("%d",&mp);
    dectobin(mp,m);
    printf("Enter multiplier value:");
    scanf("%d",&ml);
    dectobin(ml,q);
    printf("\n A \t\t Q\t\tQ_-1\t  M");
    printf("\n-------------------------------------------------");
    display(a,q,q1,m,-1);
    for(i=0;i<8;i++)
    {
        printf("\t[Step %d]",i+1);
        if(q[7]==0&&q1==0)
            event_00(a,q,&q1,m);
        else if(q[7]==0&&q1==1)
            event_01(a,q,&q1,m);
        else if(q[7]==1&&q1==0)
            event_10(a,q,&q1,m);    
        else 
            event_11(a,q,&q1,m);
    }
    printf("\nMultiplied Value:-\n\n");
    for(i=0;i<8;i++)
    {
        printf("%d",a[i]);
        res[x++]=a[i];
    }
    for(i=0;i<8;i++)
    {
        printf("%d",q[i]);
        res[x++]=q[i];
    }
    printf(" (%d)\n\n",bintodec(res));
    printf("[Programmer-Rahul Kar]\n");
    
}

2 comments:

  1. Good implementation! But stack at line 60.
    And, it would be work fine if change it to:

    If (i > 0) overflow[i-1] = 1;

    Thanks

    ReplyDelete