#include <bitset>
#include <iostream.h>
#include <string.h>

#define MAX_MESSAGE_SIZE 256
#define PATTERN_SIZE 4

using namespace std;

// Transmitted message = (Message * 2^(PATTERN_SIZE-1)  / P) + Message
// Division is done with modulo 2 arithmetic, which means XOR
// length is the length in bits of the message
bitset<MAX_MESSAGE_SIZE> GetTransmitted(bitset<MAX_MESSAGE_SIZE> message, unsigned length);

// Divide the message with the remainder by the pattern and return true if the remainder is 0, false otherwise
// length is the length in bits of the original message
bool ClientTest(bitset<MAX_MESSAGE_SIZE> messageWithRemainder, unsigned length);

// Here I use CRC-16 which takes message bit 16, 15, 2, and appends a 1 in that order to get the pattern
// length is the length in bits of the message, which must be >=4
bitset<PATTERN_SIZE> GetPattern(bitset<MAX_MESSAGE_SIZE> message);

// Modulo 2 division for the bitset class
// Returns the remainder of numerator / denominator
// Quotient is not needed so is ignored
bitset<PATTERN_SIZE> XORDivide(bitset<MAX_MESSAGE_SIZE> numerator, unsigned numeratorLength, bitset<PATTERN_SIZE> denominator, unsigned denominatorLength);

// Display the bits on the screen for testing
void display (const bitset<MAX_MESSAGE_SIZE>& item, unsigned length);
void display (const bitset<PATTERN_SIZE>& item, unsigned length);

void main(void)
{
	bitset<MAX_MESSAGE_SIZE> message, transmittedMessage;
	char test[42], length;

	do
	{
		cout << "Enter test message, between 2 and 41 bytes" << endl;
		cin >> test;
	}
	while ((length=strlen(test)) < 2);
	cout << endl;

	// store the test message as a series of bits in the bitset class
	for (int counter=0; counter<length; counter++)
	{
		message.set(counter*8+0, test[counter] >> 7);
		message.set(counter*8+1, (test[counter] >> 6) & 1);
		message.set(counter*8+2, (test[counter] >> 5) & 1);
		message.set(counter*8+3, (test[counter] >> 4) & 1);
		message.set(counter*8+4, (test[counter] >> 3) & 1);
		message.set(counter*8+5, (test[counter] >> 2) & 1);
		message.set(counter*8+6, (test[counter] >> 1) & 1);
		message.set(counter*8+7, test[counter] & 1);
	}

	cout << "Binary representation of message:" << endl;
	display(message, length * 8);
	cout << endl;

	transmittedMessage = GetTransmitted(message, length * 8);
	if (ClientTest(transmittedMessage, length * 8))
		cout << "Remainder is 0.  Message Good";
	else
		cout << "Remainder is not 0.  Message Invalid";

	cout << endl;
}

// ------------------------------------------------------------------
// CRC-16 which takes message bit 16, 15, 2, and appends a 1 in that order to get the pattern
// length is the length in bits of the message, which must be >=4
// ------------------------------------------------------------------
bitset<PATTERN_SIZE> GetPattern(bitset<MAX_MESSAGE_SIZE> message)
{
	bitset<PATTERN_SIZE> temp;
	temp.set(3, true);
	temp.set(2, message[16-1]);
	temp.set(1, message[15-1]);
	temp.set(0, message[2-1]);
	
	return temp; // return by copy
}

// ------------------------------------------------------------------
// Divide the message with the remainder by the pattern and return true if the remainder is 0, false otherwise
// length is the length in bits of the original message
// ------------------------------------------------------------------
bool ClientTest(bitset<MAX_MESSAGE_SIZE> messageWithRemainder, unsigned length)
{
	bitset<PATTERN_SIZE> remainder, pattern;

	pattern=GetPattern(messageWithRemainder);
	// Just test cases
	//pattern.set(0,true);
	//pattern.set(1,true);
	//pattern.set(2,false);
	//pattern.set(3,true);
	//pattern.set(4,false);
	//pattern.set(5,true);

	cout << "Transmitted message:" << endl;
	display(messageWithRemainder, length + PATTERN_SIZE -1);
	cout << endl;

	remainder = XORDivide(messageWithRemainder, length + PATTERN_SIZE - 1, pattern, PATTERN_SIZE);

	// If the remainder is 0 then the message was sucessfully transmitted
	return remainder.to_ulong() == 0; 
}

// ------------------------------------------------------------------
// Transmitted message = (Message * 2^(PATTERN_SIZE-1)  / P) + Message
// Division is done with modulo 2 arithmetic, which means XOR
// ------------------------------------------------------------------
bitset<MAX_MESSAGE_SIZE> GetTransmitted(bitset<MAX_MESSAGE_SIZE> message, unsigned length)
{
	bitset<PATTERN_SIZE> remainder;

	// Shift the message over PATTERN_SIZE-1 times, filling with zeros
	bitset<PATTERN_SIZE> pattern;

	pattern=GetPattern(message);
//	pattern.set(0,true);
//	pattern.set(1,true);
//	pattern.set(2,false);
//	pattern.set(3,true);
//	pattern.set(4,false);
//	pattern.set(5,true);


	cout << "Pattern:" << endl;
	display(pattern, PATTERN_SIZE);
	cout << endl;

	cout << "Message * 2^n:" << endl;
	display(message, length + PATTERN_SIZE - 1);
	cout << endl;

	// Divide the message by the pattern to get the remainder
	remainder = XORDivide(message, length + PATTERN_SIZE - 1, pattern, PATTERN_SIZE);
	
	// Add the remainder to the message, which amounts an append of the original message
	for (int counter=0; counter < PATTERN_SIZE; counter++)
		message.set(length+counter, remainder[counter]);

	return message;
}

// ------------------------------------------------------------------
// Modulo 2 division for the bitset class
// Returns the remainder of numerator / denominator
// Quotient is not needed so is ignored
// ------------------------------------------------------------------
bitset<PATTERN_SIZE> XORDivide(bitset<MAX_MESSAGE_SIZE> numerator, unsigned numeratorLength, bitset<PATTERN_SIZE> denominator, unsigned denominatorLength)
{
	bitset<PATTERN_SIZE> remainder;
	unsigned position=denominatorLength;
	unsigned counter, outputCount=2;

	// Ignore leading 0s in the numerator
	while (numerator[0]==false && numeratorLength > 0)
	{

		// The bitset class is either bugged or badly written such that the shift operator goes the wrong way - right is left and left is right
		numerator>>=1;
		numeratorLength--;
	}

	cout << "Dividend:" << endl;
	display(numerator, numeratorLength);
	cout << endl;

	cout << "Divisor:" << endl;
	display(denominator, denominatorLength);
	cout << endl;

	// for the first step, get the remainder as the XOR of the initial bits of the numerator and denominator
	for (counter=0; counter < denominatorLength; counter++)
		remainder.set(counter, numerator[counter] ^ denominator[counter]);
	
	cout << "Quotient:" << endl << '1';

	// while bits remain, drop them down and repeat the XOR as in long division
	while (position < numeratorLength)
	{
		do
		{
			// The bitset class is either bugged or badly written such that the shift operator goes the wrong way - right is left and left is right
			remainder>>=1;
			remainder.set(denominatorLength - 1, numerator[position++]);

			if (remainder[0]==true)
				cout << '1';
			else
				cout << '0';

			if (outputCount++ % 8 ==0)
				cout << ' ';
		} while (remainder[0]==false && position < numeratorLength);

		// If you are not done dividing XOR the remainder with the divisor to get the new remainder
		if (position < numeratorLength)
		{
			for (counter=0; counter < denominatorLength; counter++)
				remainder.set(counter, remainder[counter] ^ denominator[counter]);
		}
	}

	cout << endl << endl;

	remainder>>=1;
	remainder.set(denominatorLength - 1, numerator[position++]);

	return remainder;
}

// Display the bits on the screen for testing
void display (const bitset<MAX_MESSAGE_SIZE>& item, unsigned length)
{
	for (int counter=0; counter < length && counter < MAX_MESSAGE_SIZE; counter++)
	{
		cout << item[counter];
		if ((((counter+1) % 8) == 0) && (counter!=0))
			cout << ' ';
	}

	cout << endl;
}

// Display the bits on the screen for testing
void display (const bitset<PATTERN_SIZE>& item, unsigned length)
{
	for (int counter=0; counter < length && counter < PATTERN_SIZE; counter++)
	{
		cout << item[counter];
		if ((((counter+1) % 8) == 0) && (counter!=0))
			cout << ' ';
	}

	cout << endl;
}