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

#define LGX 17
#define LMX 32+16  //32bit data and 16 bits of 0s augmented
#define LTX LGX

// The CRC-CCITT polynomial is x^16 + x^12 + x^5 + 1
char gX[LGX] = {1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,1}; // polynomial

void left_shit (char buf[], int size) {

    int i;
    for (i = 1; i < size; i++)
	buf[i-1] = buf[i];
    buf[size-1] = 0;
    return;
}

//performs mX/gX and gives remainder in tX
void do_division (char mX[], char tX[]) {

   int i = 0, j = LGX-1, k = 0, l = 0;

    // copy the first LTX digits of mX into tX
    for (i = 0; i < LTX; i++)
	tX[i] = mX[i];

    j = LGX; // next digit to be brought down
    //we perform division until the second last step
    //the last step is done outside the loop
    while (j < LMX) {
	if (tX[0] == 0) {
	    //we must xor with all 0s, i.e, tX[] 
	    //remains the same.
	    
	    //now left shift.
	    left_shit (tX, LTX);
	    //bring down the next digit.
	    tX[LTX-1] = mX[j];
	    j++;
	}
	else {
	    //do actual xor of tX and gX
	    for (i = 0; i < LTX; i++) {
		if (tX[i] == 0 && gX[i] == 0 ||
		    tX[i] == 1 && gX[i] == 1)
		    tX[i] = 0;
		else
		    tX[i] = 1;
	    }
	    // now left shift
	    left_shit (tX, LTX);
	    //bring down the next digit.
	    tX[LTX-1] = mX[j];
	    j++;
	}
    }
    //perform the last step
    if (tX[0] == 0) {
	//we must xor with all 0s, i.e, tX[] 
	//remains the same.
    }	
    else {
	//do actual xor of tX and gX
	for (i = 0; i < LTX; i++) {
	    if (tX[i] == 0 && gX[i] == 0 ||
		tX[i] == 1 && gX[i] == 1)
		tX[i] = 0;
	    else
		tX[i] = 1;
	
	}
    //tX[] now contains the end remainder.
    }
    return;
}

int main () {
    
    // gX ) mX (ignore_quotient
    //      ..
    //      tX

    int i, j;
    char mX[LMX] = {};
    char tX[LTX] = {}; //remainder
    char rmX[LMX] = {}; //receiver mX[]

    // fill Mx randomly
    srandom (time(NULL));
    for (i = 0; i < LMX; i++)
	mX[i] = random()%2;
    // the last LGX-1 bits must be 0, i.e
    // these bits are augmented to the actual
    // data to be sent, which is only 32 bits
    // in our case. the rest 16 bits of 0s 
    // correspond to we using a 16 bit gX.
    for (i = (LMX-(LGX-1)); i < LMX; i++)
	mX[i] = 0;

    printf ("G(x): ");
    for (i = 0; i < LGX; i++)
	printf ("%d", (int)gX[i]);

    printf ("\nM(x): ");
    for (i = 0; i < LMX; i++)
	printf ("%d", (int)mX[i]);
    printf ("\n");

    do_division (mX, tX);
    
    // add tX (from index 1) to the last LGX-1 of  mX
    for (i = (LMX-(LGX-1)), j = 1; i < LMX; i++, j++)
	mX[i] = tX[j];

    printf ("Sending to receiver: ");
    for (i = 0; i < LMX; i++)
	printf ("%d", (int)mX[i]);
    printf ("\n");

    // The receiver start.....

    //copy to rmX[]
    for (i = 0; i < LMX; i++)
	rmX[i] = mX[i];

    // Decide whether to create an error or not
    if (random()%2 == 0) {
	//select a random bit
	i = random()%LMX;
	if (rmX[i] == 0)
	    rmX[i] = 1;
	else
	    rmX[i] = 0;
	printf ("Created a transmission error in bit %d\n", i);
    }

    //clear tX
    for (i = 0; i < LTX; i++)
	tX[i] = 0;
    do_division (rmX, tX);
    //only if tX is all 0s, it means there is no transmission error.
    for (i = 0; i < LTX; i++)
	if (tX[i] == 1) {
	    printf ("Receiver says error in transmission.\n");
	    return 0;
	}
    printf ("Receiver: received data without errors.\n");
    return 0;
}