#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define CODE_LENGTH 7
#define DATA_LENGTH 4
// see comment below

void do_hamming (char buffer[CODE_LENGTH+1]) {

    int i, j, k;
    int n = CODE_LENGTH;

    // Now for each position 'i', say 7
    // 7 = 1 + 2 + 4. Add (exclusive or) 1 to positions 1, 2, and 4. 
    // (Express 7 as sum of powers of 2
    for (i = 1; i <= n; i++) {
	j = 1; // start from position 1
	k = i;
	while (k > 0) {
	    if (k % 2 == 1)
		buffer[j] = (buffer[j]+buffer[i])%2;
	    k = k / 2;
	    j = j * 2;
	}
    }
}

void set_parity_positions (char buffer[CODE_LENGTH+1], int value) {
    // This function sets the positions in "buffer" that correspond
    // to "powers of 2" to value 'value' (which must be 0 or 1).

    int i = 1, n = CODE_LENGTH;
    while (i <= n) {
	buffer[i] = value;
	i = i*2;
    }
    return;
}

int main () {

    int n = CODE_LENGTH, m = DATA_LENGTH;
    int i, j, k;
    // for recovering from 1 bit errors, (n+1)(2^m) <= 2^n

    char buffer[CODE_LENGTH+1];
    char receiver[CODE_LENGTH+1];
    //We do not use the first element of the array.
    
    printf ("Enter %d binary digits space seperated (that form the data word).\n", m);
    // Get the digits into positions in the buffer that do NOT correspond
    // to the powers of 2. (3, 5, 6, 7, 9, ...)

    // The idea is, clear all bits in the buffer, 
    // set only positions that are powers of 2, 
    // then fill in the other positions in order.

    for (i = 1; i <= n; i++)
	buffer[i] = (char) 0;

    // set only "powers of 2" positions to 1
    set_parity_positions (buffer, 1);
    // Now scan from stdin
    i = 1; j = 1;
    while (j <= m) {
	if (buffer[i] == 1) {
	    i++;
	    continue;
	}
	scanf ("%d", &k);
	buffer[i] = (char)k;
	i++; j++;
    }
    // To make data input easier, positions of "powers of 2" were set. Reset them.
    set_parity_positions (buffer, 0);

    // Calculate the parity bits...
    do_hamming (buffer);

    printf ("Hamming code: ");
    for (i = 1; i <= n; i++) {
	if (buffer[i] == 0)
	    putc ('0', stdout);
	else
	    putc ('1', stdout);
    }
    printf ("\n");

    // Now start the receiver.
    for (i = 1; i <= n; i++)
	receiver[i] = buffer[i];
    receiver[0] = 0; // simply
    // Randomly create an error in a bit
    srandom (time (NULL));
    i = (random()%7)+1;
    if (receiver[i] == 0)
	receiver[i] = 1;
    else 
	receiver[i] = 0;

    // The data that receiver received is now in
    // receiver[]. Let us re-use buffer[] to hold
    // the hamming code that the receiver calculates.
    for (i = 1; i <= n; i++)
	buffer[i] = receiver[i];

    // set the "powers of 2" positions to 0
    set_parity_positions (buffer, 0);

    do_hamming (buffer);

    // let us use 'k' as a counter to hold errored position.
    k = 0;
    // Check each parity bit (powers of 2 positions)
    i = 1;
    while (i <= n) {
	if (buffer[i] != receiver[i])
	    k = k+i;
	i = i*2;
    }

    printf ("Received codeword: ");
    for (i = 1; i <= n; i++) {
	if (receiver[i] == 0)
	    putc ('0', stdout);
	else
	    putc ('1', stdout);
    }
    printf ("\n");
    printf ("Error in bit %d (Positioning begins at 1).\n", k);

    return 0;
}