#include <iostream>
#include <Windows.h>
#include <bitset>
#include <iomanip>
#include <iterator>
#include <fstream>
#include <algorithm>
#include <direct.h>
#include <vector>
#include <ctime>

using namespace std;


uint32_t S[] = { 0xc, 0x5, 0x6, 0xb, 0x9, 0x0, 0xa, 0xd, 0x3, 0xe, 0xf, 0x8, 0x4, 0x7, 0x1, 0x2 };
#define n 4
const int n_bit = 4;
#define pw (pow(2, 2 * n))
#define coFu (pow(2, pow(2,2 * n)))
#define per (pow(2, n))
const int bit_si = 256;  //pow(2, 2*n)  //pow(2, 2*n)  2^16 = 65536  2^8 = 256   2^4 = 16   2^3 = 9    2^2 = 4
const int n2bit = 8; //2*n
const int perr = pow(2, n);
string CIPHER = "Modified_Present";

vector<bitset<n2bit>> Nf;
bitset<bit_si>(Fs);
bitset<bit_si>(FsTrue);
bitset<bit_si>(Hs);
vector<bitset<n2bit>> SY;
vector<bitset<2 * n2bit>> trueFunctions;
vector<bitset<2 * n2bit>> reduceTrueFunctions;

//uint32_t x = 0x93AB;
uint32_t x = 0x1234;


////////////////////Шифрование///////////////////////////////////////////////

uint32_t permutation(uint32_t x) {

    uint32_t temp = 0;
    size_t size = sizeof(x) * 4;
    vector <bool> t(size);
    vector <bool> tp(size);
    for (int i = 0; i < size; i++) {
        t[i] = ((x >> (size - i - 1)) & 1);
    }
    tp[0] = t[0];
    tp[1] = t[4];
    tp[2] = t[7];
    tp[3] = t[12];
    tp[4] = t[1];
    tp[5] = t[11];
    tp[6] = t[5];
    tp[7] = t[13];
    tp[8] = t[2];
    tp[9] = t[8];
    tp[10] = t[10];
    tp[11] = t[6];
    tp[12] = t[3];
    tp[13] = t[15];
    tp[14] = t[14];
    tp[15] = t[9];

    for (int i = 0; i < size; ++i) {
        temp = (temp << 1) | tp[i];
    }
    return temp;
}
uint32_t Encode(uint32_t x) {
    uint32_t temp = 0;
    uint32_t tmp = 0;
    size_t size = sizeof(x) * 4;
    for (int i = 4; i <= size; i += 4) {
        tmp = S[((x >> (size - i)) & 0xf)];
        temp = (temp << 4) | tmp;
    }
    temp = permutation(temp);
    return temp;
}
uint32_t sigma = Encode(Encode(x));
//////////////////////////////////////////////////////////////////////////



//////////////////Построение имплицент для подстановки////////////
bool isNf(bitset<n2bit> i) {
    int length = Nf.size();
    for (int y = 0; y < length; y++) {
        if (Nf[y] == i) {
            return true;
        }
    }
    return false;
}
bool isSY(bitset<n2bit> i) {
    int length = SY.size();
    for (int y = 0; y < length; y++) {
        if (SY[y] == i) {
            return true;
        }
    }
    return false;
}

void createFs() {
    for (size_t i = 0; i < pw; i++) {
        if (bitset<n_bit>(i) == bitset<n_bit>(S[(i >> n)])) {
            Fs = Fs << 1;
            Fs |= 1;

        }
        else {
            Fs = Fs << 1;
        }
    }
    FsTrue = Fs;

}

void createNf_WN() {
    cout << "Creating Nf_WN..." << endl;
    for (size_t i = 0; i < Nf.size(); i++) {
        for (size_t j = i; j < Nf.size(); j++) {
            if (isNf(bitset<n2bit>(Nf[i])& bitset<n2bit>(Nf[j])) == false) {
                Nf.push_back(bitset<n2bit>(Nf[i]) & bitset<n2bit>(Nf[j]));
            }

        }
        //cout << Nf.size() << " " << i  << endl;
    }
}
void createNf_WP() {
    cout << "Creating Nf_WP..." << endl;
    for (size_t i = 0; i < Nf.size(); i++) {
        for (size_t j = i; j < Nf.size(); j++) {
            if (isNf(bitset<n2bit>(Nf[i]) | bitset<n2bit>(Nf[j])) == false) {
                Nf.push_back(bitset<n2bit>(Nf[i]) | bitset<n2bit>(Nf[j]));
            }

        }
        //cout << Nf.size() << " " << i <<  endl;

    }
}
void createNf() {
    cout << "Creating Nf..." << endl;
    for (size_t i = 0; i < pw; i++) {
        if (bitset<n_bit>(i) == bitset<n_bit>(S[(i >> n)])) {
            Nf.push_back(i);
        }
    }
}

bool checkWP() {
    cout << "Check WP..." << endl;
    int length = Nf.size();
    uint64_t mask = pw - 1;
    for (size_t i = 0; i < length; i++) {
        for (size_t j = i; j < length; j++) {
            if (isNf((Nf[i] | Nf[j])) == false) {
                return false;
            }
        }
    }
    return true;
}
bool checkWN() {
    cout << "Check WN..." << endl;
    int length = Nf.size();
    uint64_t mask = pw - 1;
    for (size_t i = 0; i < length; i++) {
        for (size_t j = i; j < length; j++) {
            if (isNf((Nf[i] & Nf[j])) == false) {
                return false;
            }
        }
    }
    return true;
}


/////////////////////////////////Prints////////////////////////////////////////

void printNf(string s) {
    string txt = ".txt";
    string ppNf = "Nf";
    string temp = ppNf + s + txt;
    ofstream pNf(temp);
    pNf << "Function weight: " << Nf.size() << endl;
    for (size_t i = 0; i < Nf.size(); i++) {
        pNf << bitset<n2bit>(Nf[i]) << endl;
    }
    pNf.close();
}
void printSY(string s) {
    string txt = ".txt";
    string ppNf = "Nf";
    string temp = ppNf + s + txt;
    ofstream pNf(temp);
    pNf << "Function weight: " << SY.size() << endl;
    for (size_t i = 0; i < SY.size(); i++) {
        pNf << bitset<n2bit>(SY[i]) << endl;
    }
    pNf.close();
}

void printTrueFunctions(string s) {
    string txt = ".txt";
    string ppNf = "True functions of ";
    string temp = ppNf + s + txt;
    ofstream pNf(temp);
    pNf << "Function weight: " << trueFunctions.size() << endl;
    for (size_t i = 0; i < trueFunctions.size(); i++) {
        pNf << bitset<2 * n2bit>(trueFunctions[i]) << endl;
    }
    pNf.close();
}

void printReduceTrueFunctions(string s) {
    string txt = ".txt";
    string ppNf = "Reduce true functions of ";
    string temp = ppNf + s + txt;
    ofstream pNf(temp);
    pNf << "Function weight: " << reduceTrueFunctions.size() << endl;
    for (size_t i = 0; i < reduceTrueFunctions.size(); i++) {
        pNf << bitset<2 * n2bit>(reduceTrueFunctions[i]) << endl;
    }
    pNf.close();
}
/////////////////////////////////////////////////////////////////




///////////////Решение задачи 1: Построение системы уравнений в функциональнов виде и перебор////////////////////
bitset<n2bit> getBitset(size_t y, int index) {
    bitset<n2bit> temp;
    int counts = 0;
    bool flag = true;
    for (int i = 0; i < n2bit; ++i) {
        if (flag == true) {
            temp[n2bit - i - 1] = ((x >> (perr - ((i%4) + index) - 1)) & 1);
        }
        else{
            temp[n2bit - i - 1] = ((y >> (perr - ((i%4) + index) - 1)) & 1);
        }
        counts++;
        //cout << counts << " " << flag << endl;
        if (counts == n) {
            if (flag == true) {
                flag = false;
            }
            else {
                flag = true;
            }

            counts = 0;
        }
    }
    /*for (int i = 0; i < n2bit; i++) {
        cout << temp[i];
    }*/
    //cout << "temp " << index << ": " << bitset<n2bit>(temp) << endl;
    return temp;
}


void checkCollision() {
    size_t size = pow(2, sizeof(x) * 4);
    size_t size_of_x = sizeof(x) * 4;
    for (size_t y = 0; y < size; ++y) {
        int count_of_true = 0;
        for (int index = 0; index < size_of_x; index+= 4) {
            if (isSY(getBitset(y, index)) == false) {
                break;
            }
            else {
                count_of_true++;
            }
        }
        if (count_of_true == 4) {
            trueFunctions.push_back(y);
            /*cout << "x: = " << bitset<16>(x) << endl;
            cout << "y: = " << bitset<16>(y) << endl;
            system("pause");*/
        }
    }

    cout << "Количество подходящих вариантов: " << trueFunctions.size() << endl;
}


uint32_t getUintFromBitset(bitset<2 * n2bit> tp) {
    uint32_t temp = 0;
    for (int i = 0; i < 2 * n2bit; i++) {
        temp = (((temp << 1) | tp[2 * n2bit - i - 1]) & 0xffff);
    }
    return temp;
}

void thin_out_of_the_true_functions() {
    size_t size_of_true_Functions = trueFunctions.size();
    uint32_t temp = 0;
    for (int i = 0; i < size_of_true_Functions; ++i) {
        temp = getUintFromBitset(trueFunctions.at(i));
        if (sigma == Encode(permutation(temp))) {
            reduceTrueFunctions.push_back(trueFunctions.at(i));
        }
    }
}



/////////////////////////////////////////////////////////////////////////////////////////////////////////////////

///////////////////////Составляем систему//////////////////////////////////
bitset<n> get_fore_bits_from_x(uint32_t vec, int index) {
    size_t size = sizeof(vec) * 4;
    return ((vec >> (size - index - 4)) & 0xf);
}


void createSystem() {
    bitset<n2bit> temp =0;
    bitset<4> tmp = 0;
    size_t Nf_vec_size = Nf.size();
    for (size_t i = 0; i < Nf_vec_size; ++i) {
        temp = Nf.at(i);
        for (int j = 0; j < n; j++) {
            tmp[n - j - 1] = temp[n2bit - j - 1];
        }
        for (int index = 0; index < (2 * n2bit); index += 4) {
            if (tmp == get_fore_bits_from_x(x, index)) {
                SY.push_back(Nf.at(i));
            }
        }
    }
}




///////////////////////////////////////////////////////////////////////



//////////////////////////////////////////////////////////////////////

int main() {
    srand(time(NULL));
    setlocale(LC_ALL, "Russian");

    /*uint32_t y = 0x93AB;
    cout << "y: = " << get_fore_bits_from_x(y, 12) << endl;

    cout << "x: = " << bitset<16>(x) << endl;
    cout << "y: = " << bitset<16>(y) << endl;*/




    createFs();
    createNf();
    printNf(" Fs of " + CIPHER);

    int choise = 0;
    cout << "Выберите: \n\t1. WP \n\t2. WN" << endl;
    cin >> choise;

    switch (choise)
    {
    case 1:
        createNf_WP();
        printNf(" Hs_WP of " + CIPHER);
        createSystem();
        printSY(" System");
        checkCollision();
        printTrueFunctions("WP");
        thin_out_of_the_true_functions();
        printReduceTrueFunctions("WP");
        break;
    case 2:
        createNf_WN();
        printNf(" Hs_WN of " + CIPHER);
        createSystem();
        printSY(" System");
        checkCollision();
        printTrueFunctions("WN");
        thin_out_of_the_true_functions();
        printReduceTrueFunctions("WN");
        break;
    default:
        break;
    }
    cout << bitset<2 * n2bit>(sigma) << endl;

    Nf.clear();
    trueFunctions.clear();

    return 0;
}