#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <sstream>
#include <bitset>
//#include"complex.h"
using namespace std;

int debug;
int decision;
string inp;
string originalBits, encodedBits;
int redundantBits;

void Start();
void OriginalCodeStuff();
void Encode();
void Decode();
string MakeCharToAscii();
void SetRedundantBitsSize();
void SetDecodeRedundantBits();
void DecodeSetOriginalBitsString();

string MakeCharToAscii(char c)
{
	string ret;
	char buffer[33];
	_itoa_s(c, buffer, 2);
	ret += "0";
	ret +=  buffer;
	return ret;
}
void OriginalCodeStuff()
{
	originalBits = "";
	for (int i = 0; i < inp.size(); i++)
	{
		originalBits += MakeCharToAscii(inp[i]);
	}
	cout << "\nOriginal code: " << originalBits << endl;

}
int Power(int a, int b)
{
	int ret = 1;
	for (int i = 0; i < b; i++)
		ret *= a;
	return ret;
}
void SetRedundantBitsSize()
{
	redundantBits = 0;
	while (originalBits.size() + redundantBits + 1 > Power(2, redundantBits))
		redundantBits++;
	cout << "No of redundant bits: " << redundantBits << endl;
}
void SetDecodeRedundantBits()
{
	int i = 0;
	for (;encodedBits.size() + 1 > Power(2, i); i++);
	redundantBits = i;
	cout << "No of redundant bits: " << redundantBits << endl;
}
bool IsBinaryNumber(int i)
{
	while (i > 1)
	{
		if (i % 2 != 0)
			return false;
		i /= 2;
	}
	return true;
}
void SetNormalBitsToEncoded()
{
	for (int i = 0, origIt = 0; i < encodedBits.size(); i++)
	{
		int j = i + 1;
		if (!IsBinaryNumber(j))
		{
			if (origIt >= originalBits.size())
			{
				cout << "Error, Original Iterator larger than Encoded size" << endl;
				return;
			}
			encodedBits[i] = originalBits[origIt];
			origIt++;
		}

	}
}
void DecodeSetOriginalBitsString()
{
	originalBits = string(encodedBits.size() - redundantBits , '0');
	for (int i = 0, j = 0; i < encodedBits.size(); i++)
	{
		if (IsBinaryNumber(i + 1))
			continue;
		if (j < originalBits.size())
		{
			originalBits[j] = encodedBits[i];
			j++;
		}
	}
}
void OutputOriginalText()
{
	stringstream sstream(originalBits);
	string output;
	while (sstream.good())
	{
		bitset<8> bits;
		sstream >> bits;
		char c = char(bits.to_ulong());
		output += c;
	}
	cout << "Original text: " << output << endl;
}
void ds()
{
	if (debug == 1)
		cout << "\n";
}
void dm(string s)
{
	if (debug == 1)
		cout << "s";
}
void dm(int s)
{
	if (debug == 1)
		cout << s;
}
int CountParity(int i, int sz)
{
	int ret = 0;
	int szTemp = sz;
	if (i == sz - 1)
	{
		i++;
		szTemp--;
	}
	for (; szTemp > 0 && i < encodedBits.size(); i++, szTemp--)
	{
		ret += encodedBits[i] == '1' ? 1 : 0;
	}
	return ret;
}
void SetParityBitsToEncoded()
{
	for (int i = 0, origIt = 0; i < encodedBits.size(); i++)
	{
		int j = i + 1;
		if (IsBinaryNumber(j))
		{
			int count = 0;
			int currectIndex = i;
			while (currectIndex < encodedBits.size())
			{
				count += CountParity(currectIndex, j);
				currectIndex += 2*j;
			}
			encodedBits[i] = count % 2 == 0 ? '0' : '1';

		}

	}
}
void EncodedCodeStuff()
{
	encodedBits = "";
	// m + r + 1 <= 2^r
	SetRedundantBitsSize();
	encodedBits = string(redundantBits + originalBits.size(), '0');
	SetNormalBitsToEncoded();
	SetParityBitsToEncoded();
	cout << "Encoded code: " << encodedBits << endl;

}
void Encode()
{
	cout << "\nEnter message: ";
	cin >> inp;
	if (inp.size() == 1 && inp == "3")
		Start();
	OriginalCodeStuff();
	EncodedCodeStuff();
	cout << endl;
	Start();
}
void FindErrors(string o)
{
	int e = 0;
	for (int i = 0; i < o.size(); i++)
	{
		if (o[i] != encodedBits[i])
			e |= (i + 1);
	}
	if (e != 0)
		encodedBits[e-1] = encodedBits[e-1] == '1' ? '0' : '1';
	if (e != 0)
		cout << "Error found, correct code is: " << encodedBits << endl;
}
void Decode()
{
	cout << "\nEnter code: ";
	cin >> inp;
	if (inp.size() == 1 && inp == "3")
		Start();
	encodedBits = inp;
	SetDecodeRedundantBits();
	string temp = encodedBits;
	SetParityBitsToEncoded();
	FindErrors(temp);

	DecodeSetOriginalBitsString();
	cout << "Original: " << originalBits << endl;

	OutputOriginalText();
	cout << endl;
	Start();
}
void Start()
{
	cout << "Enter '1' for Encoding\nEnter '2' for Decoding\nEnter '3' at any point to restart" << endl;
	cin >> decision;
	if (decision == 1)
		Encode();
	else if (decision == 2)
		Decode();
	else if (decision == 3)
		Start();
}

void main()
{

	debug = 0;
	Start();

}