#include <stdio.h>
#include <vector>
#include <map>
#include <cstdlib>
#include "h_md5.h"

using namespace std;

//class for holding 128bit numbers
class Number
{
    public:
        pair<unsigned long long, unsigned long long> c;
        Number(unsigned long long up, unsigned long long down)
        {c.first=up;c.second=down;}

        int getbit(int bit)
        {
            if(bit<64){
                if((c.second & ((unsigned long long)1 << bit))) return 1;
                return 0;
            }
            bit-=64;
            if((c.first & ((unsigned long long)1 << bit))) return 1;
            return 0;

        }
};

int mat[3000][3000];
int v[3000];

vector<Number> solve(vector<Number> y1, vector<Number> y2, int nBites,
        Number result)
{
    //setup dimensions of matrix
    int R, S;
    R = nBites;
    S = y1.size()+1;
    //fill in matrix
    for(int i = 0; i < R; i++){
        for(int j = 0; j < S; j++)
            mat[i][j]=0;
        mat[i][S-1]=result.getbit(i);
        for(int j = 0; j < S-1; j++){
            mat[i][j]^=y1[j].getbit(i);
            mat[i][j]^=y2[j].getbit(i);
            mat[i][S-1]^=y2[j].getbit(i);
        }
    }

    //solve matrix by gaussian elimination
    int r, temp;
    for(int i = 0; i < S-1;i++)
        v[i]=-1;
    int ro = 0;
    for(int i = 0; i < S-1; i++)
    {
        r=-1;
        for(int j = ro; j < R; j++)
        {
            if(mat[j][i]==1){ r = j; break; }
        }
        if(r==-1) {v[i]=1; continue;}
        for(int j = 0; j < S; j++)
        {
            temp = mat[ro][j]; mat[ro][j]=mat[r][j]; mat[r][j]=temp;
        }
        for(int j = 0; j < R; j++)
        {
            if(j==ro) continue;
            if(mat[j][i]==0) continue;
            for(int k = 0; k < S; k++)
            {
                mat[j][k]^=mat[ro][k];
            }
        }
        ro++;
    }

    //produce result from solved matrix

    ro = 0;
    for(int i = 0; i < S-1; i++)
    {
        if(v[i]==-1)
        {
            for(int j = 0; j < S; j++)
            {
                v[i]+=mat[ro][j];
            }
            v[i]%=2;
            ro++;
        }
    }
    vector<Number> ret;
    for(int i = 0; i < S-1; i++)
    {
        printf("%d: %d\n", i, v[i]);
        if(v[i]==1) ret.push_back(y1[i]);
        else if(v[i]==0) ret.push_back(y2[i]);
        else printf("Something wrong happened\n");
    }
    return ret;
}

//generates random string from a-z of length 256
string genstr()
{
    string ret;
    for(int i = 0; i < 256; i++)
        ret+='a'+rand()%26;
    return ret;
}

int main()
{
    vector<Number> y1, y2;
    pair<unsigned long long, unsigned long long> h;
    map<pair<unsigned long long, unsigned long long>, string> hh;

    //generates two sequences of hashes
    for(int i = 0; i < 256; i++){{
        string str = genstr();
        MD5 md5(str);
        h = md5.lldigest();
        hh[h]=str;
        y1.push_back(Number(h.first, h.second));}

        {string str = genstr();
            MD5 md5(str);
            h = md5.lldigest();
            hh[h]=str;
            y2.push_back(Number(h.first, h.second));}

    }

    vector<Number> ret;

    //finds good sequence
    ret = solve(y1, y2, 128, Number(0x1234,0x5678901234567890ll));

    unsigned long long out = 0, out2 = 0;
    for(int i = 0; i < 256; i++){
        printf("%016LX%016LX\n", ret[i].c.first, ret[i].c.second);
        out^=ret[i].c.first; out2^=ret[i].c.second;
    }
    printf("XOR: %016LX%016LX\n", out, out2);

    //writes file

    FILE *oo = fopen("data.dat", "w");
    for(int i = 0; i < 256; i++)
    {
        fprintf(oo, "%s", hh[ret[i].c].c_str());
    }
    fclose(oo);
}