#include<stdio.h>
#include<math.h>
#include<string.h>

#define MAXINT 65536
#define SIZE 100

int arr[SIZE][SIZE];    // a global array , to contain table information
int ele=0,ind=0;   // indices to be used in above array

void summ(int i);

int isPow2(int i)
{
    /*if input no is power of two retrun 1 , else 0*/
    if(MAXINT % i==0)
        return 1;   //true
    return 0;   //false
}

int calcPow(int i)
{
    /*Thism ethod returns , what is power of 2 , in a no.
        which is of form 2 to the power p */
    /* return p , from input of format 2^p */
    int count=-1;
    /* validate */
    if(!isPow2(i))
        printf("flow error...");
    else
        while(i>0)
        {
            i/=2;
            count++;
        }

    return count;
}

int findLowerOf2(int i)
{
    /*a function to calculate the no , JUST below i , which is power of 2 */
    int count=-1;

    if(isPow2(i))
        return pow(2,i);
    else
        while(i>0)
        {
            i/=2;
            count++;
        }


    return pow(2,count);
}
void callSumm(int i)
{
    /* A method to call summ() method , with assertion that
        all global parameters are incremented at each call to summ()
    */
    ind=0;
    summ(i);
    arr[ele][ind++]=-1;
    ele++;

}
void dieError()
{
    /* If failure , exit the program*/
    //exit(1);
}

int howManyTimes(int val,int a[])
{
    /* a method to check that how many times
        no val is occuring  in array a[]
    */
    int i,count=0;
    for(i=0;a[i]!=-1;i++)
        if(a[i]==val)
            count++;
    return count;
}

void checkInput(int argc,char str[])
{
    int i=0;
    if (argc<2)
    {
        printf("usage: filename.o 'The code string' ");
        printf(" ex. \n a.out 110110 \n");
        dieError();
    }
    for(i=0;i<strlen(str);i++)
        if(!(str[i]=='0' || str[i]=='1'))
        {
            printf("Please enter a binary string only.....\n");
            dieError();
        }
}


int calr(int m)
{
    /*Method to calculate checksum bits for
        given m , databits
    */
    int r=0;
    for(r=0;r<=m;r++)
        if(m <= pow(2,r)-1-r)
            return r;
}

int isEven(int i)
{
    return i%2==0;
}

void summ(int i)
{
    /* The method to initialize contents of global array by power of 2's sum for each entry */
    int j=0; //index no
    if(isPow2(i))
    {
        /*input no i is of power of 2's form like 1,2,4,8,16...*/
        arr[ele][ind]=calcPow(i);
        /*calculate what's the power of 2 , in the no, & store to global array*/
        ind++;
    }
    else
    {
        /*input no i is NOT of power of 2's form  */
        j=findLowerOf2(i);
        /* try to find just last no , which is of form of power of 2 */

        arr[ele][ind]=calcPow(j);
        /* again calculate the power*/
        ind++;
        i=i-j; /* differnce in the no & the last no which is of form of power of 2 */
        /*now call method recursively for the new no (i=i-j) */
        summ(i);
    }
}

int main(int argc,char *argv[])
{
        /* Declaretions ...*/
    /* flag & index variables*/
    int i,j,k=0,flag,temp;
    /* The output codeword container */
    char coded[SIZE];
    int len; //total length of coded word
    int m;  //code bits
    int r;      //check bits
    /* to associate & contain equations of checkbits */
    int count[SIZE][SIZE];

    /* validate input  */
    checkInput(argc,argv[1]);

    /*calculate no of check bits required n thus total length */
    m=strlen(argv[1]);
    r=calr(m);
    len=m+r;


    /* Fill the global container ,  according to the size info
        of m,r & len */
    for(i=1;i<=len;i++)
        callSumm(i);

    for(j=0,k=0;j<r;j++)
    {
        for(i=0,k=0;i<len;i++)
            if(howManyTimes(j,arr[i]))
                count[j][k++]=i+1;

        count[j][k]=-1;
    }


    /*Fill the code word....,except check bits*/
    for(i=0,j=0;j<len;j++)
    {
        if(!isPow2(j+1))
            coded[j]=argv[1][i++];
        else
            coded[j]='x';  //initialize checkbits by character x

    }

    /* Now **********
        Frame all equations & solve them
        & fill entries in coded table accordingly
    */
    for(i=0;i<r;i++)
    {
        for(flag=0,j=1;count[i][j]!=-1;j++)
        {
            temp=count[i][j]-1;
                if (coded[temp]=='1')
                    flag+=1;
                else if (coded[temp]=='0')
                    flag+=0;
        }
            temp=count[i][0]-1;
            if (isEven(flag))
                coded[temp]='0';
            else
                coded[temp]='1';
    }

    printf("The Hamming coded word for your data is ");
    for(i=0;i<len;i++)
        printf("%c",coded[i]);
    printf("");

}