fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cassert>
  4. #include <ctime>
  5. #include <cstdlib>
  6. #include <memory>
  7. #include <functional>
  8. #include <sstream>
  9. #include <algorithm>
  10. #include <unordered_map>
  11. #include <unordered_set>
  12. #include <fstream>
  13. #include <array>
  14.  
  15. unsigned int total = 0;
  16. unsigned int set_access = 0;
  17.  
  18. template<typename T> T* ConcurrentAlloc() {
  19.     ++total;
  20.     return new T;
  21. }
  22. template<typename T, typename Arg1> T* ConcurrentAlloc(Arg1&& other) {
  23.     ++total;
  24.     return new T(std::forward<Arg1>(other));
  25. }
  26. template<typename T, typename Arg1, typename Arg2> T* ConcurrentAlloc(Arg1&& arg1, Arg2&& arg2) {
  27.     ++total;
  28.     return new T(std::forward<Arg1>(arg1), std::forward<Arg2>(arg2));
  29. }
  30.  
  31. struct Expression {
  32.     virtual ~Expression() {}
  33.     virtual std::string print() = 0;
  34.     virtual unsigned int depth(std::unordered_set<Expression*>&) = 0;
  35.     unsigned int depth() {
  36.         std::unordered_set<Expression*> current;
  37.         return depth(current);
  38.     }
  39. };
  40. struct Constant : public Expression {
  41.     Constant(unsigned int val)
  42.         : value(val) {}
  43.     unsigned int value;
  44.     virtual std::string print() {
  45.         std::stringstream strstr;
  46.         strstr << value;
  47.         return strstr.str();
  48.     }
  49.     virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
  50.         return 1;
  51.     }
  52. };
  53.  
  54. //std::unordered_map<unsigned int, Constant*> map;
  55. Constant* get_constant(unsigned int constant) {
  56.     return ConcurrentAlloc<Constant>(constant);
  57.     /*
  58.     if (map.find(constant) != map.end())
  59.         return map[constant];
  60.     return map[constant] = ConcurrentAlloc<Constant>(constant);*/
  61. }
  62.  
  63. struct ChunkReference : public Expression {
  64.     ChunkReference(unsigned int ind)
  65.         : index(ind) {}
  66.     virtual std::string print() {
  67.         std::stringstream strstr;
  68.         strstr << "c[" << index << "]";
  69.         return strstr.str();
  70.     }
  71.     unsigned int index;
  72.     virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
  73.         return 1;
  74.     }
  75. };
  76.  
  77. struct BinExpr : public Expression {
  78.     BinExpr(Expression* l, Expression* r)
  79.         : lhs(l), rhs(r) {}
  80.     Expression* lhs;
  81.     Expression* rhs;
  82.     virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
  83.         ++set_access;
  84.         assert(exprs.insert(this).second);
  85.         auto result = std::max(lhs->depth(exprs), rhs->depth(exprs)) + 1;
  86.         exprs.erase(this);
  87.         return result;
  88.     }
  89. };
  90. struct PlusExpr : public BinExpr {
  91.     virtual std::string print() {
  92.         std::stringstream strstr;
  93.         strstr << "(" << lhs->print() << " + " << rhs->print() << ")";
  94.         return strstr.str();
  95.     }
  96.     PlusExpr(Expression* l, Expression* r)
  97.         : BinExpr(l, r) {}
  98. };
  99. struct RotrExpr : public BinExpr {
  100.     virtual std::string print() {
  101.         std::stringstream strstr;
  102.         strstr << "(" << lhs->print() << " rotr " << rhs->print() << ")";
  103.         return strstr.str();
  104.     }
  105.     RotrExpr(Expression* l, Expression* r)
  106.         : BinExpr(l, r) {}
  107. };
  108. struct XORExpr : public BinExpr {
  109.     virtual std::string print() {
  110.         std::stringstream strstr;
  111.         strstr << "(" << lhs->print() << " ^ " << rhs->print() << ")";
  112.         return strstr.str();
  113.     }
  114.     XORExpr(Expression* l, Expression* r)
  115.         : BinExpr(l, r) {}
  116. };
  117. struct ANDExpr : public BinExpr {
  118.     virtual std::string print() {
  119.         std::stringstream strstr;
  120.         strstr << "(" << lhs->print() << " & " << rhs->print() << ")";
  121.         return strstr.str();
  122.     }
  123.     ANDExpr(Expression* l, Expression* r)
  124.         : BinExpr(l, r) {}
  125. };
  126. struct RSHIFTExpr : public BinExpr {
  127.     virtual std::string print() {
  128.         std::stringstream strstr;
  129.         strstr << "(" << lhs->print() << " >> " << rhs->print() << ")";
  130.         return strstr.str();
  131.     }
  132.     RSHIFTExpr(Expression* l, Expression* r)
  133.         : BinExpr(l, r) {}
  134. };
  135. struct NOTExpr : public Expression {
  136.     virtual std::string print() {
  137.         std::stringstream strstr;
  138.         strstr << "(~" << negate->print() << ")";
  139.         return strstr.str();
  140.     }
  141.     virtual unsigned int depth(std::unordered_set<Expression*>& exprs) {
  142.         ++set_access;
  143.         assert(exprs.insert(this).second);
  144.         auto result = negate->depth(exprs) + 1;
  145.         exprs.erase(this);
  146. 	return result;
  147.     }
  148.     NOTExpr(Expression* e)
  149.         : negate(e) {}
  150.     Expression* negate;
  151. };
  152.  
  153. struct ExpressionHolder {
  154.     ExpressionHolder()
  155.         : e(0) {}
  156.     Expression* e;
  157.     ExpressionHolder(unsigned int constant) {
  158.         e = get_constant(constant);
  159.     }
  160.     ExpressionHolder(Expression* expr) {
  161.         e = expr;
  162.     }
  163.     ExpressionHolder operator+(const ExpressionHolder& other) const {
  164.         return ExpressionHolder(ConcurrentAlloc<PlusExpr>(e, other.e));
  165.     }
  166.     ExpressionHolder operator&(const ExpressionHolder& other) const {
  167.         return ExpressionHolder(ConcurrentAlloc<ANDExpr>(e, other.e));
  168.     }
  169.     ExpressionHolder operator>>(const ExpressionHolder& other)const {
  170.         return ExpressionHolder(ConcurrentAlloc<RSHIFTExpr>(e, other.e));
  171.     }
  172.     ExpressionHolder operator>>(unsigned int other)const {
  173.         return ExpressionHolder(ConcurrentAlloc<RSHIFTExpr>(e, get_constant(other)));
  174.     }
  175.     ExpressionHolder operator^(const ExpressionHolder& other) const {
  176.         return ExpressionHolder(ConcurrentAlloc<XORExpr>(e, other.e));
  177.     }
  178.     ExpressionHolder rotate(const ExpressionHolder& other) const {
  179.         return ExpressionHolder(ConcurrentAlloc<RotrExpr>(e, other.e));
  180.     }
  181.     ExpressionHolder rotate(unsigned int other) const {
  182.         return ExpressionHolder(ConcurrentAlloc<RotrExpr>(e, get_constant(other)));
  183.     }
  184.     ExpressionHolder operator~() const {
  185.         return ExpressionHolder(ConcurrentAlloc<NOTExpr>(e));
  186.     }
  187. };
  188.  
  189. ExpressionHolder h[] = {
  190.     0x6a09e667,
  191.     0xbb67ae85,
  192.     0x3c6ef372,
  193.     0xa54ff53a,
  194.     0x510e527f,
  195.     0x9b05688c,
  196.     0x1f83d9ab,
  197.     0x5be0cd19
  198. };
  199. ExpressionHolder k[] = {    
  200.    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
  201.    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
  202.    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
  203.    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
  204.    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
  205.    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
  206.    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
  207.    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
  208. };
  209. ExpressionHolder w[64] = {
  210.     ConcurrentAlloc<ChunkReference>(0),
  211.     ConcurrentAlloc<ChunkReference>(1),
  212.     ConcurrentAlloc<ChunkReference>(2),
  213.     ConcurrentAlloc<ChunkReference>(3),
  214.     ConcurrentAlloc<ChunkReference>(4),
  215.     ConcurrentAlloc<ChunkReference>(5),
  216.     ConcurrentAlloc<ChunkReference>(6),
  217.     ConcurrentAlloc<ChunkReference>(7),
  218.     ConcurrentAlloc<ChunkReference>(8),
  219.     ConcurrentAlloc<ChunkReference>(9),
  220.     ConcurrentAlloc<ChunkReference>(10),
  221.     ConcurrentAlloc<ChunkReference>(11),
  222.     ConcurrentAlloc<ChunkReference>(12),
  223.     ConcurrentAlloc<ChunkReference>(13),
  224.     ConcurrentAlloc<ChunkReference>(14),
  225.     ConcurrentAlloc<ChunkReference>(15)
  226. };
  227.  
  228. int main() {
  229.     for(int i = 16; i < 64; i++) {
  230.         auto s0 = w[i - 15].rotate(17) ^ w[i - 15].rotate(18) ^ (w[i - 15] >> 2);
  231.  
  232.         auto s1 = w[i - 2].rotate(17) ^ w[i - 2].rotate(19) ^ (w[i - 2] >> 10);
  233.         w[i] = w[i - 16] + s0 + w[i - 7] + s1;
  234.     }
  235.     std::array<ExpressionHolder, 8> loopvars;
  236.     for(int i = 0; i < 8; i++)
  237.         loopvars[i] = h[i];
  238.  
  239.     for(int i = 0; i < 4; i++) {
  240.         auto&& la = loopvars[0];
  241.         auto&& lb = loopvars[1];
  242.         auto&& lc = loopvars[2];
  243.         auto&& ld = loopvars[3];
  244.         auto&& le = loopvars[4];
  245.         auto&& lf = loopvars[5];
  246.         auto&& lg = loopvars[6];
  247.         auto&& lh = loopvars[7];
  248.  
  249.         auto s0 = la.rotate(2) ^ la.rotate(13) ^ la.rotate(22);
  250.         auto maj = (la & lb) ^ (la & lc) ^ (lb & lc);
  251.         auto t2 = s0 + maj;
  252.  
  253.         auto s1 = le.rotate(6) ^ le.rotate(11) ^ le.rotate(25);
  254.         auto ch = (le & lf) ^ ((~le) & lg);
  255.         auto t1 = lh + s1 + ch + k[i] + w[i];
  256.  
  257.         lh = lg;
  258.         lg = lf;
  259.         lf = le;
  260.         le = ld + t1;
  261.         ld = lc;
  262.         lc = lb;
  263.         lb = la;
  264.         la = t1 + t2;
  265.     }
  266.     for(int i = 0; i < 8; i++) {
  267.         h[i] = h[i] + loopvars[i];
  268.     }
  269.     std::array<unsigned int, 8> depths;
  270.     std::cout << "total " << total << '\n';
  271.     for(int index = 0; index < 8; index++) {
  272.         std::cout << "Depth h[" << (depths[index] = h[index].e->depth()) << "]: " << std::endl;
  273.         std::cout << "set_access " << set_access << '\n';
  274.         set_access = 0;
  275.     }
  276. }
Success #stdin #stdout 0s 2984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
total 1136
Depth h[34]: 
set_access 10899
Depth h[26]: 
set_access 1610
Depth h[18]: 
set_access 221
Depth h[10]: 
set_access 26
Depth h[34]: 
set_access 2353
Depth h[26]: 
set_access 449
Depth h[18]: 
set_access 85
Depth h[10]: 
set_access 15
https://ideone.com/T9Z32
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!