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

int gen_ckbits (void);
int getbit_tx  (int n);

int calc_syndrome (void);
int getbit_rx  (int n);

// Syndrome Table.
// This maps the "syndromes" to actual bit error masks
//
// (...I included this in this file, just to simplify downloading.. you might
// want to toss this into an include file...)
struct {
	unsigned int  nSyndrome;
	unsigned char nBitError1;  // Always valid
	unsigned char nBitError2;  // zero indicates NULL.
} SyndromeTable[127] = {
{0x0003, 14, 15},
{0x0006, 13, 14},
{0x000C, 12, 13},
{0x0018, 11, 12},
{0x0030, 10, 11},
{0x0060,  9, 10},
{0x00C0,  8, 9},
{0x0180,  7, 8},
{0x0300,  6, 7},
{0x0600,  5, 6},
{0x0C00,  4, 5},
{0x15D3, 43, 44},
{0x1763, 20, 21},
{0x1800,  3, 4},
{0x18CD, 28, 29},
{0x193B, 59, 60},
{0x1E1B, 31, 32},
{0x21CD, 56, 57},
{0x220B, 38, 39},
{0x2867, 35, 36},
{0x2BA6, 42, 43},
{0x2D31, 49, 50},
{0x2E7D, 25, 26},
{0x2EC6, 19, 20},
{0x3000,  2, 3},
{0x3149, 51, 52},
{0x319A, 27, 28},
{0x3276, 58, 59},
{0x3657, 53, 54},
{0x3C36, 30, 31},
{0x439A, 55, 56},
{0x4416, 37, 38},
{0x468D, 40, 41},
{0x4841, 61, 62},
{0x4989, 33, 34},
{0x4B7B, 45, 46},
{0x4BD7, 22, 23},
{0x4E0F, 16, 17},
{0x502A, 62, 63},
{0x50CE, 34, 35},
{0x51B7, 46, 47},
{0x51E1, 23, 24},
{0x530D, 17, 18},
{0x574C, 41, 42},
{0x5A62, 48, 49},
{0x5CD1, 47, 48},
{0x5CFA, 24, 25},
{0x5D8C, 18, 19},
{0x6000,  1, 2},
{0x6039, 36, 37},
{0x6292, 50, 51},
{0x6334, 26, 27},
{0x64EC, 57, 58},
{0x650F, 39, 40},
{0x6815, 63, 64},
{0x6CAE, 52, 53},
{0x6F21, 54, 55},
{0x740B, 15, 16},
{0x786C, 29, 30},
{0x7897, 60, 61},
{0x7B07, 32, 33},
{0x7EE3, 44, 45},
{0x7FBB, 21, 22},
{0x8000, 64, 0},
{0x8001, 15, 0},
{0x8002, 14, 0},
{0x8004, 13, 0},
{0x8008, 12, 0},
{0x8010, 11, 0},
{0x8020, 10, 0},
{0x8040,  9, 0},
{0x8080,  8, 0},
{0x8100,  7, 0},
{0x8200,  6, 0},
{0x8400,  5, 0},
{0x8800,  4, 0},
{0x88E9, 60, 0},
{0x8A09, 32, 0},
{0x8CB1, 44, 0},
{0x8D21, 21, 0},
{0x9000,  3, 0},
{0x90C7, 52, 0},
{0x91D2, 59, 0},
{0x9412, 31, 0},
{0x9962, 43, 0},
{0x9A2B, 26, 0},
{0x9A42, 20, 0},
{0xA000,  2, 0},
{0xA017, 37, 0},
{0xA18E, 51, 0},
{0xA305, 40, 0},
{0xA3A4, 58, 0},
{0xA51F, 55, 0},
{0xA824, 30, 0},
{0xB2C4, 42, 0},
{0xB44F, 48, 0},
{0xB456, 25, 0},
{0xB484, 19, 0},
{0xB83F, 62, 0},
{0xB887, 34, 0},
{0xB929, 46, 0},
{0xB94D, 23, 0},
{0xBA05, 17, 0},
{0xC000,  1, 0},
{0xC02E, 36, 0},
{0xC31C, 50, 0},
{0xC60A, 39, 0},
{0xC748, 57, 0},
{0xC885, 28, 0},
{0xCA3E, 54, 0},
{0xD048, 29, 0},
{0xE401, 38, 0},
{0xE588, 41, 0},
{0xE685, 56, 0},
{0xE815, 63, 0},
{0xE849, 35, 0},
{0xE89E, 47, 0},
{0xE8AC, 24, 0},
{0xE908, 18, 0},
{0xEE2D, 49, 0},
{0xF07E, 61, 0},
{0xF10E, 33, 0},
{0xF252, 45, 0},
{0xF29A, 22, 0},
{0xF40A, 16, 0},
{0xF91F, 27, 0},
{0xFC69, 53, 0}
};

int MakeBlockOf8      (char *buffer);
int CorrectBlockOf8   (char *buffer);


// Basic code is (64, 48)
// Will correct 1 bit errors, and all 2 bit burst errors.

//  Buffer must be as follows:  8 bytes long, where first 6 bytes
//  are valid data.  The last two bytes will be filled in with
//  FEC bytes.
//
int MakeBlockOf8 (char *buffer)
{
	int n,bit;
	unsigned int ckbits = 0;
	unsigned int check_word;

	for (n = 1; n <= 48; n++) {
		bit = buffer[(n-1)/ 8] >> ((n-1)%8);
		bit &= 1;
		if (1 & (bit ^ (ckbits >> 15))) {
			ckbits ^= 0x6815;
		}
		ckbits <<= 1;
	}
	ckbits ^= 0x0002;
	// the MSB of ckbits is "bit0".. So, we need to transpose them..
	check_word = 0;
	for (n = 1; n < 16; n++) {
		check_word |= (ckbits & 0x8000);
		check_word >>= 1;
		ckbits <<= 1;
	}
	buffer[6] = (unsigned char)(check_word & 0xFF);
	buffer[7] = (unsigned char)(check_word >> 8);

	return check_word;
}

// return:  -1 if uncorrectable
//           0 if no errors detected
//           1 if one error was corrected
//           2 if two errors were corrected..
int CorrectBlockOf8 (char *buffer)
{
	int i, n,bit;
	int nByte, nBit;
	int parity=0;
	int syndrome=0;

	// Generate Syndrome
	for (n = 1; n <= 64; n++) {
		bit = buffer[(n-1)/ 8] >> ((n-1)%8);
		bit &= 1;
		parity ^= bit;
		if (n == 63) bit ^= 1;
		if (n < 64) {
			syndrome <<= 1;
			if (1 & (bit ^ (syndrome >> 15))) {
				syndrome ^= 0x6815;
			}
		}
	}
	syndrome &= 0x7FFF;
	if (parity) {
		syndrome |= 0x8000;
	}

	if (syndrome == 0) {
		return 0;
	}
	else {
		printf ("\n\rSyndrome = %04X", syndrome);
		for (i = 0; i <  127; i++) {
			if (SyndromeTable[i].nSyndrome == syndrome) {
				// Correct first bit error.
				nByte = (SyndromeTable[i].nBitError1 - 1) / 8;
				nBit  = (SyndromeTable[i].nBitError1 - 1) % 8;
				buffer[nByte] ^= (1 << nBit);
				if (SyndromeTable[i].nBitError2 != 0) {
					// Correct 2nd bit error
					nByte = (SyndromeTable[i].nBitError2 - 1) / 8;
					nBit  = (SyndromeTable[i].nBitError2 - 1) % 8;
					buffer[nByte] ^= (1 << nBit);
					// return 2 signifying double bit correction
					return 2;
				}
				else {
					// That was all, return 1 signifying singe bit correction
					return 1;
				}
			}
		}
		// Syndrome not found!  Uncorrectable!! return -1
		return -1;
	}
}

char szTest[8];

int main ()
{
	int check_bits, syndrome, nrc, i;

	randomize ();

//	check_bits = gen_ckbits ();
//	printf ("\nCheck bits = %04X", check_bits);
//	syndrome   = calc_syndrome ();
//	printf ("\nSyndrome   = %04X", syndrome);

// TEST #1  No Bit Errors (example data from book)
	printf ("\n\rTEST #1:  No Bit Errors.");
	szTest[0] = 0x91;
	szTest[1] = 0xD5;
	szTest[2] = 0xB3;
	szTest[3] = 0xF7;
	szTest[4] = 0x48;
	szTest[5] = 0x2C;
	szTest[6] = 0x00;
	szTest[7] = 0x00;
	printf ("\n\rInput Block       = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = MakeBlockOf8 (szTest);
	printf ("\n\rCheckbits = %04X", nrc);
	printf ("\n\rEncoded Block     = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = CorrectBlockOf8 (szTest);
	printf ("\n\r#Corrections = %d", nrc);
	printf ("\n\rCorrected Block   = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

// TEST #2  One Bit Error introduced randomly
	printf ("\n\r\n\rTEST #2:  Randomly introduced 1 Bit Error.");
	szTest[0] = 0x91;
	szTest[1] = 0xD5;
	szTest[2] = 0xB3;
	szTest[3] = 0xF7;
	szTest[4] = 0x48;
	szTest[5] = 0x2C;
	szTest[6] = 0x00;
	szTest[7] = 0x00;
	printf ("\n\rInput Block       = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = MakeBlockOf8 (szTest);
	printf ("\n\rCheckbits = %04X", nrc);
	printf ("\n\rEncoded Block     = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	// Introduce 1 bit error
	szTest[random(8)] ^= (1 << random(8));
	printf ("\n\rCorrupted Block   = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = CorrectBlockOf8 (szTest);
	printf ("\n\r#Corrections = %d", nrc);
	printf ("\n\rCorrected Block   = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

// TEST #3  Two Bit Errors (taken from the book)
	printf ("\n\r\n\rTEST #3:  2 Bit Errors.");
	szTest[0] = 0x91;
	szTest[1] = 0xD5;
	szTest[2] = 0xB3;
	szTest[3] = 0xF7;
	szTest[4] = 0x48;
	szTest[5] = 0x2C;
	szTest[6] = 0x00;
	szTest[7] = 0x00;
	printf ("\n\rInput Block       = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = MakeBlockOf8 (szTest);
	printf ("\n\rCheckbits = %04X", nrc);
	printf ("\n\rEncoded Block     = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	// Introduce a 2 bit error
	szTest[1] = 0xD6;
	printf ("\n\rCorrupted Block   = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = CorrectBlockOf8 (szTest);
	printf ("\n\r#Corrections = %d", nrc);
	printf ("\n\rCorrected Block   = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

// TEST #4  Random!!! (random 1 bit errors, random 2 bit bursts)
	printf ("\n\r\n\rTEST #4:  Random Data and bit pair errors!");
	for (i = 0; i < 6; i++) {
		szTest[i] = random(256);
	}
	szTest[6] = 0x00;
	szTest[7] = 0x00;

	printf ("\n\rInput Block       = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = MakeBlockOf8 (szTest);
	printf ("\n\rCheckbits = %04X", nrc);
	printf ("\n\rEncoded Block     = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	// Introduce bit errors
	switch (random(3)) {
		case 0:
			// Do 1 bit error
			szTest[random(8)] ^= (1 << random(8));
			printf ("\n\rCorrupted (1 err) = ");
			break;
		case 1:
			// do a 2 bit burst error
			szTest[random(8)] ^= (3 << random(7));
			printf ("\n\rCorrupted (2 err) = ");
			break;
		case 2:
			// algorithm shouldn't be able to do this.  watch it fail.
			szTest[random(8)] ^= (7 << random(6));
			printf ("\n\rCorrupted (3 err) = ");
			break;
	}
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);

	nrc = CorrectBlockOf8 (szTest);
	printf ("\n\r#Corrections = %d", nrc);
	printf ("\n\rCorrected Block   = ");
	for (i = 0; i < 8; i++) printf ("%02x ", (unsigned char)szTest[i]);
}


// First pass at this problem.  Very bit-oriented stuff below.  Stops
// at generating syndromes.
//
int gen_ckbits ()
{
	int n,bit;
	unsigned int ckbits = 0;
	for (n = 1; n <= 48; n++) {
		bit = getbit_tx(n);
		if (1 & (bit ^ (ckbits >> 15))) {
			ckbits ^= 0x6815;
		}
		ckbits <<= 1;
	}
	return ckbits ^ 0x0002;
}

int getbit_tx(int n)
{
	char c;
	const char *invector
	  = "1000100110101011110011011110111100010010001101001111110101000010";

	c = invector[n-1];
	if (c == '0')
		return 0;
	if (c == '1')
		return 1;
	return -1;
}

int calc_syndrome ()
{
	int n,bit;
	int parity=0;
	int syndrome=0;
	for (n = 1; n <= 64; n++) {
		bit = getbit_rx(n);
		parity ^= bit;
		if (n == 63) bit ^= 1;
		if (n < 64) {
			syndrome <<= 1;
			if (1 & (bit ^ (syndrome >> 15))) {
				syndrome ^= 0x6815;
			}
		}
	}
	syndrome &= 0x7FFF;
	if (parity) {
		syndrome |= 0x8000;
	}
	return syndrome;
}

int getbit_rx (int n)
{
	char c;
	// Good vector
	//const char *invector
	//  = "1000100110101011110011011110111100010010001101001111110101000010";

	// Bad vector (bits 9 and 10 are bad)
	const char *invector
	  = "1000100101101011110011011110111100010010001101001111110101000010";

	c = invector[n-1];
	if (c == '0')
		return 0;
	if (c == '1')
		return 1;
	return -1;
}