#include <iostream>
#include <vector>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <memory>
#include <functional>
#include <sstream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <array>

unsigned int total = 0;
unsigned int set_access = 0;

template<typename T> T* ConcurrentAlloc() {
    ++total;
    return new T;
}
template<typename T, typename Arg1> T* ConcurrentAlloc(Arg1&& other) {
    ++total;
    return new T(std::forward<Arg1>(other));
}
template<typename T, typename Arg1, typename Arg2> T* ConcurrentAlloc(Arg1&& arg1, Arg2&& arg2) {
    ++total;
    return new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2));
}

struct Expression {
    virtual ~Expression() {}
    virtual std::string print() = 0;
    virtual unsigned int depth(std::unordered_set<Expression*>&) = 0;
    unsigned int depth() {
        std::unordered_set<Expression*> current;
        return depth(current);
    }
};
struct Constant : public Expression {
    Constant(unsigned int val)
        : value(val) {}
    unsigned int value;
    virtual std::string print() {
        std::stringstream strstr;
        strstr << value;
        return strstr.str();
    }
    virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
        return 1;
    }
};

//std::unordered_map<unsigned int, Constant*> map;
Constant* get_constant(unsigned int constant) {
    return ConcurrentAlloc<Constant>(constant);
    /*
    if (map.find(constant) != map.end())
        return map[constant];
    return map[constant] = ConcurrentAlloc<Constant>(constant);*/
}

struct ChunkReference : public Expression {
    ChunkReference(unsigned int ind)
        : index(ind) {}
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "c[" << index << "]";
        return strstr.str();
    }
    unsigned int index;
    virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
        return 1;
    }
};

struct BinExpr : public Expression {
    BinExpr(Expression* l, Expression* r)
        : lhs(l), rhs(r) {}
    Expression* lhs;
    Expression* rhs;
    virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
        ++set_access;
        assert(exprs.insert(this).second);
        auto result = std::max(lhs->depth(exprs), rhs->depth(exprs)) + 1;
        exprs.erase(this);
        return result;
    }
};
struct PlusExpr : public BinExpr {
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "(" << lhs->print() << " + " << rhs->print() << ")";
        return strstr.str();
    }
    PlusExpr(Expression* l, Expression* r)
        : BinExpr(l, r) {}
};
struct RotrExpr : public BinExpr {
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "(" << lhs->print() << " rotr " << rhs->print() << ")";
        return strstr.str();
    }
    RotrExpr(Expression* l, Expression* r)
        : BinExpr(l, r) {}
};
struct XORExpr : public BinExpr {
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "(" << lhs->print() << " ^ " << rhs->print() << ")";
        return strstr.str();
    }
    XORExpr(Expression* l, Expression* r)
        : BinExpr(l, r) {}
};
struct ANDExpr : public BinExpr {
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "(" << lhs->print() << " & " << rhs->print() << ")";
        return strstr.str();
    }
    ANDExpr(Expression* l, Expression* r)
        : BinExpr(l, r) {}
};
struct RSHIFTExpr : public BinExpr {
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "(" << lhs->print() << " >> " << rhs->print() << ")";
        return strstr.str();
    }
    RSHIFTExpr(Expression* l, Expression* r)
        : BinExpr(l, r) {}
};
struct NOTExpr : public Expression {
    virtual std::string print() {
        std::stringstream strstr;
        strstr << "(~" << negate->print() << ")";
        return strstr.str();
    }
    virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
        ++set_access;
        assert(exprs.insert(this).second);
        auto result = negate->depth(exprs) + 1;
        exprs.erase(this);
	return result;
    }
    NOTExpr(Expression* e)
        : negate(e) {}
    Expression* negate;
};

struct ExpressionHolder {
    ExpressionHolder()
        : e(0) {}
    Expression* e;
    ExpressionHolder(unsigned int constant) {
        e = get_constant(constant);
    }
    ExpressionHolder(Expression* expr) {
        e = expr;
    }
    ExpressionHolder operator+(const ExpressionHolder& other) const {
        return ExpressionHolder(ConcurrentAlloc<PlusExpr>(e, other.e));
    }
    ExpressionHolder operator&(const ExpressionHolder& other) const {
        return ExpressionHolder(ConcurrentAlloc<ANDExpr>(e, other.e));
    }
    ExpressionHolder operator>>(const ExpressionHolder& other)const {
        return ExpressionHolder(ConcurrentAlloc<RSHIFTExpr>(e, other.e));
    }
    ExpressionHolder operator>>(unsigned int other)const {
        return ExpressionHolder(ConcurrentAlloc<RSHIFTExpr>(e, get_constant(other)));
    }
    ExpressionHolder operator^(const ExpressionHolder& other) const {
        return ExpressionHolder(ConcurrentAlloc<XORExpr>(e, other.e));
    }
    ExpressionHolder rotate(const ExpressionHolder& other) const {
        return ExpressionHolder(ConcurrentAlloc<RotrExpr>(e, other.e));
    }
    ExpressionHolder rotate(unsigned int other) const {
        return ExpressionHolder(ConcurrentAlloc<RotrExpr>(e, get_constant(other)));
    }
    ExpressionHolder operator~() const {
        return ExpressionHolder(ConcurrentAlloc<NOTExpr>(e));
    }
};

ExpressionHolder h[] = {
    0x6a09e667,
    0xbb67ae85,
    0x3c6ef372,
    0xa54ff53a,
    0x510e527f,
    0x9b05688c,
    0x1f83d9ab,
    0x5be0cd19
};
ExpressionHolder k[] = {    
   0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
   0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
   0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
   0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
   0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
   0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
   0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
   0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};
ExpressionHolder w[64] = {
    ConcurrentAlloc<ChunkReference>(0),
    ConcurrentAlloc<ChunkReference>(1),
    ConcurrentAlloc<ChunkReference>(2),
    ConcurrentAlloc<ChunkReference>(3),
    ConcurrentAlloc<ChunkReference>(4),
    ConcurrentAlloc<ChunkReference>(5),
    ConcurrentAlloc<ChunkReference>(6),
    ConcurrentAlloc<ChunkReference>(7),
    ConcurrentAlloc<ChunkReference>(8),
    ConcurrentAlloc<ChunkReference>(9),
    ConcurrentAlloc<ChunkReference>(10),
    ConcurrentAlloc<ChunkReference>(11),
    ConcurrentAlloc<ChunkReference>(12),
    ConcurrentAlloc<ChunkReference>(13),
    ConcurrentAlloc<ChunkReference>(14),
    ConcurrentAlloc<ChunkReference>(15)
};

int main() {
    for(int i = 16; i < 64; i++) {
        auto s0 = w[i - 15].rotate(17) ^ w[i - 15].rotate(18) ^ (w[i - 15] >> 2);

        auto s1 = w[i - 2].rotate(17) ^ w[i - 2].rotate(19) ^ (w[i - 2] >> 10);
        w[i] = w[i - 16] + s0 + w[i - 7] + s1;
    }
    std::array<ExpressionHolder, 8> loopvars;
    for(int i = 0; i < 8; i++)
        loopvars[i] = h[i];

    for(int i = 0; i < 4; i++) {
        auto&& la = loopvars[0];
        auto&& lb = loopvars[1];
        auto&& lc = loopvars[2];
        auto&& ld = loopvars[3];
        auto&& le = loopvars[4];
        auto&& lf = loopvars[5];
        auto&& lg = loopvars[6];
        auto&& lh = loopvars[7];

        auto s0 = la.rotate(2) ^ la.rotate(13) ^ la.rotate(22);
        auto maj = (la & lb) ^ (la & lc) ^ (lb & lc);
        auto t2 = s0 + maj;

        auto s1 = le.rotate(6) ^ le.rotate(11) ^ le.rotate(25);
        auto ch = (le & lf) ^ ((~le) & lg);
        auto t1 = lh + s1 + ch + k[i] + w[i];
        
        lh = lg;
        lg = lf;
        lf = le;
        le = ld + t1;
        ld = lc;
        lc = lb;
        lb = la;
        la = t1 + t2;
    }
    for(int i = 0; i < 8; i++) {
        h[i] = h[i] + loopvars[i];
    }
    std::array<unsigned int, 8> depths;
    std::cout << "total " << total << '\n';
    for(int index = 0; index < 8; index++) {
        std::cout << "Depth h[" << (depths[index] = h[index].e->depth()) << "]: " << std::endl;
        std::cout << "set_access " << set_access << '\n';
        set_access = 0;
    }
}