#include <iostream>
#include <set>
#include <vector>
#include <map>

using namespace std;

typedef unsigned char byte;

int popcount(byte b)
{
  int count = 0;
  for(int i = 0; i < 8; i++)
  {
    if(b & (1 << i))
      count++;
  }
  return count;
}

byte mult(vector<byte>& A, byte w)
{
  byte syndrome = 0;
  for(size_t i = 0; i < A.size(); i++)
  {
    //check parity of row i
    bool parity = popcount(A[i] & w) % 2 == 1;
    if(parity)
    {
      syndrome |= (1 << i);
    }
  }
  return syndrome;
}

void printBin(byte b)
{
  for(int i = 7; i >= 0; i--)
    cout << ((b & (1 << i)) ? '1' : '0');
}

int main()
{
  vector<byte> A;
  A.push_back(0x1E);
  A.push_back(0x66);
  A.push_back(0xAA);
  A.push_back(0xFF);
  cout << "Code matrix:\n";
  for(int i = 0; i < 4; i++)
  {
    printBin(A[i]);
    cout << '\n';
  }
  cout << '\n';
  cout << "All codewords:\n";
  int numCodewords = 0;
  for(int i = 0; i < 256; i++)
  {
    byte b = i;
    if(mult(A, b) == 0)
    {
      printBin(b);
      cout << '\n';
      numCodewords++;
    }
  }
  vector<set<byte>> cosets(16);
  cout << "Code has " << numCodewords << " codewords.\n";
  for(int i = 0; i < 256; i++)
  {
    byte syndrome = mult(A, i);
    cosets[syndrome].insert(i);
  }
  /*
  cout << "Cosets:\n";
  for(int i = 0; i < 16; i++)
  {
    for(auto w : cosets[i])
    {
      printBin(w);
      cout << ' ';
    }
    cout << '\n';
  }
  cout << '\n';
  */
  vector<byte> leaders(16);
  for(int i = 0; i < 16; i++)
  {
    byte leader = 0xFF;
    byte minPop = 8;
    for(auto w : cosets[i])
    {
      if(popcount(w) < minPop)
      {
        minPop = popcount(w);
        leader = w;
      }
    }
    cout << "Syndrome ";
    printBin(i);
    cout << " leader: ";
    printBin(leader);
    cout << '\n';
    leaders[i] = leader;
  }
  vector<byte> toDecode;
  toDecode.push_back(0xAD);
  toDecode.push_back(0x5B);
  toDecode.push_back(0xC0);
  for(auto w : toDecode)
  {
    cout << "Decoding ";
    printBin(w);
    cout << " ...\n";
    byte syndrome = mult(A, w);
    cout << "Syndrome is ";
    printBin(syndrome);
    cout << "\n";
    cout << "Corrected word: ";
    printBin(w ^ leaders[syndrome]);
    cout << "\n\n";
  }
  return 0;
}