lab2

#include<bits/stdc++.h>
#include "cryptopp/sha.h"
using CryptoPP::SHA256;

using namespace std;
using uc = unsigned char;
using vuc = vector<uc>;

//Constants
constexpr int RANDSZ = (1 << 20);
constexpr int MINNUMBIT = 15;
constexpr int MAXNUMBIT = 20;
constexpr int MAXNUMCOL = 100;
constexpr int MMASK = (1 << 16) - 1;
constexpr int DIGEST_SIZE = 32;

mutex mtx1;
mutex mtx2;

//to compile this:
//-l:libcryptopp.a

//function that allows print vuc in hex
ostream& operator<<(ostream& out, const vuc& v) {
  for (auto& c: v)
    out << setw(2) << setfill('0') << hex << (int)c;
  out << endl;
}

vuc sha256(vuc data) {
  vuc ans(CryptoPP::SHA256::DIGESTSIZE);
  try {
    byte const* pbData = (byte*)data.data();
    unsigned int nDataLen = data.size();
    byte abDigest[CryptoPP::SHA256::DIGESTSIZE];

    CryptoPP::SHA256().CalculateDigest((CryptoPP::byte*)abDigest, (CryptoPP::byte*)pbData, nDataLen);

    memcpy(&ans[0], abDigest, CryptoPP::SHA256::DIGESTSIZE);
  }
  catch(...){};
  return ans;
}

//Generate salt
vuc GenSalt(int size) {
  vuc buff;
  try {
    unsigned seed = std::chrono::high_resolution_clock::now().time_since_epoch().count();
    mt19937 Mrand(seed);
    buff.resize(size);
    for (int i = 0; i < size; i++)
      buff[i] = Mrand() % UCHAR_MAX;
  }
  catch (...) {}
  return buff;
}

//return first sz bits of sha256
unsigned int shaxx(vuc data, int sz) {
  vuc hash;
  unsigned int ans = 0;
  try {
    hash = sha256(data);
    for (int i = 0, j = 0; i < sz; i += 8, j++)
      ans <<= 8, ans ^= ((unsigned int)hash[j]);
  }
  catch(...){};
  return ans;
}

// add (zeros) to the end
vuc pad(unsigned int val) {
  vuc res;
  try {
    res.resize(DIGEST_SIZE);
    fill(res.begin(), res.end(), 0);
    int j = 0;
    stack<uc> st;
    while(val) {
      st.push(val & (unsigned int)UCHAR_MAX);
      val >>= 8;
    }
    while(st.size())
      res[j++] = st.top(), st.pop();
  }
  catch(...){};
  return res;
}

//function that return collision and size of map for task1
tuple<vuc, vuc, long long> subtask1(int sz) {
  unordered_map<unsigned int, vuc> mp;
  try {
    auto start = chrono::high_resolution_clock::now();
    while(true) {
      vuc data = GenSalt(DIGEST_SIZE);
      unsigned int hash = shaxx(data, sz);
      if (mp.count(hash)) {
        return {data, mp[hash], mp.size()};
      }
      mp[hash] = data;
    }
  }
  catch(...){}
}



//check that first q bits of val is '0' q = (num_bits_of_shaxx) / 2 - log2(num_threads) in my case
bool check(int val, int num, int log2numth = 1) {
  return ((val & ((1 << num) - (1 << ((num >> 1) - log2numth)))) == 0);
}

//function that find collision (rho)
void process(vuc init, pair<int, int>* ans1, pair<int, int>* ans2, int num_bit, unordered_map<unsigned int, pair<int, int>>* st, bool flag) {
  unsigned int i = 0, temp;

  while(true) {

    //in case of cycle without 'good' distinguish points
    if (i > (1 << (num_bit >> 1)))
      return;

    mtx1.lock();
    if (*ans1 != pair<int, int>()) {
      mtx1.unlock();
      return;
    }
    mtx1.unlock();

    temp = shaxx(init, num_bit);

    if (check(temp, num_bit)) {
      mtx2.lock();
      if ((*st).count(temp)) {
        *ans1 = {i, flag};
        *ans2 = (*st)[temp];
        mtx2.unlock();
        return;
      }
      (*st)[temp] = {i, flag};
      mtx2.unlock();
    }

    init = pad(temp);
    i++;
  }
}

//func make initial values's numbers of iterations equal (крч, приводит к такому виду, в котором им нужно одинаковое число итераций(применение shaxx и padding) до коллизии)
void correctInitVals(pair<int, int>& i, pair<int, int>& j, vuc& init1, vuc& init2, vuc& cp1, vuc& cp2, int size) {
  //check that data from different threads
  if (i.second != j.second) {
      if (i.second == 1)
        swap(i, j);
    }
    else {
      if (i.second == 1)
        memcpy(&init1[0], &init2[0], init1.size());
      else
        memcpy(&init2[0], &init1[0], init2.size());
    }

    //to equalize num_of_iter
    while(i.first > j.first) {
      memcpy(&cp1[0], &init1[0], init1.size());
      init1 = pad(shaxx(cp1, size));
      i.first--;
    }
    while(j.first > i.first) {
      memcpy(&cp2[0], &init2[0], init2.size());
      init2 = pad(shaxx(cp2, size));
      j.first--;
    }
}

tuple<vuc, vuc, long long> subtask2(int sz) {
  pair<int, int> i; // idx/thread_id
  pair<int, int> j; // idx/thread_id
  unordered_map<unsigned int, pair<int, int>> st;
  vuc initValFirstThread, initValSecondThread, cp1, cp2; //cp1 - copy of initValFirstThread, cp2 - copy of initValSecondThread
  try {
    initValFirstThread = GenSalt(DIGEST_SIZE);
    initValSecondThread = GenSalt(DIGEST_SIZE);
    cp1.resize(DIGEST_SIZE);
    cp2.resize(DIGEST_SIZE);
    memcpy(&cp1[0], &initValFirstThread[0], DIGEST_SIZE);
    memcpy(&cp2[0], &initValSecondThread[0], DIGEST_SIZE);

    thread th1(process, initValFirstThread, &i, &j, sz, &st, 0);
    thread th2(process, initValSecondThread, &i, &j, sz, &st, 1);

    if (th1.joinable())
      th1.join();
    if (th2.joinable())
      th2.join();

    //in case of cycle without 'good' distinguish points
    if (i.first == 0 && j.first == 0)
      return {vuc(), vuc(), -1};

    correctInitVals(i, j, initValFirstThread, initValSecondThread, cp1, cp2, sz);

    while(true) {
      if (initValFirstThread == initValSecondThread)
        break;
      memcpy(&cp1[0], &initValFirstThread[0], DIGEST_SIZE);
      memcpy(&cp2[0], &initValSecondThread[0], DIGEST_SIZE);
      initValFirstThread = pad(shaxx(cp1, sz));
      initValSecondThread = pad(shaxx(cp2, sz));
    }
  }
  catch(...) {}
  return {cp1, cp2, st.size()};
}

//count requred info about func, flag is used for print collisions
void task_handler(function<tuple<vuc, vuc, long long>(int i)> func, bool flag = 0) {
  for (int i = MINNUMBIT; i <= MAXNUMBIT; i++) {

    double tim = 0;
    long long sz = 0;
    int num_of_itr = 0;
    set<pair<vuc, vuc>> st;

    while(st.size() < MAXNUMCOL) {
      auto start = chrono::high_resolution_clock::now();
      auto [a, b, c] = func(i);
      auto fn = chrono::high_resolution_clock::now();
      if (c != -1) { // to don't count case when can't find distinguished point
        tim += (chrono::duration_cast<chrono::duration<double>>(fn - start)).count();
        st.emplace(a, b);
        sz += c;
        num_of_itr++;
      }
    }
    if (flag) {
      for (auto [a, b]: st) {
        cout << a << b << endl;
        //cout << sha256(a) << sha256(b) << endl << endl; //to check correctness
      }
      return;
    }
    cout << i << " initValFirstThread bits of sha256 - time = " << tim / num_of_itr << " ms, size = " << sz * sizeof(int) / num_of_itr << " bytes" << endl;
  }
}

int main() {
  //task_handler(subtask1);
  //task_handler(subtask2);
  return 0;
}