// Copyright (c) 2016 Satoshi Nakamoto
// Distributed under the MIT/X11 software license, see the accompanying
// file license.txt or http://www.opensource.org/licenses/mit-license.php.


#include <stdio.h>
#include <gmp.h>
#include<math.h>
/* make sure to invoke gcc with -lgmp */


// NEVER i repeat NEVER use a dead big number variable

struct res {
int rh; // height
// each return from recursion increases h by one
// deepest solution returns zero
// no solution returns SOLUTIONNOTFOUND

//logarithm of no. of variables in the level having the most variables)
double e; // maximum entropy per round

long  unsigned long p0;
long  unsigned long p1;
long  unsigned long p2;
};

void nxt(mpz_t r, mpz_t a) {
mpz_t s,t;
mpz_init(s);
mpz_init(t);
mpz_sub_ui(s, a, 1); // bcsub
mpz_mul(t, a, s); // bcmul
mpz_div_2exp(r, t, 1); // bcdiv 2
mpz_clear(s);
mpz_clear(t);
}

int
compare_doubles (const double da, const double db)
{

  return (da > db) - (da < db);
}

static int SUCCESS = 0;
static int SOLUTIONNOTFOUND = 9999999;

//static struct res oracle;


static long  unsigned long longlongbitsminus1;

// h .. number of already pushed hashes to signature
// s .. NOT the number of objects in this layer  !!! see d
// e .. the already signed entropy (bits)
// d .. how many divisions by two need to be performed on s to get actual number of objects in this layer
// d .. This is optimalization to save memory
// b .. this is burst. during a burst (>0) cannot do growth rounds, only merkle reduce rounds
// .... this is an optimalization because merkle reduce rounds tend to appear in bursts

// m .. the total maximum length of message that needs to be signed
static long double messagedigest;
static int burstdefault;

static double maxentropyperlevel = 0.0;

// ooo and sticky are related to burst
// they activate bursts

static int beancounter = 0;

//int debug() {
// return oracle.rh != SOLUTIONNOTFOUND;
//}

//void nextoracle() {
//
/// oracle.p0= 2;
// oracle.p0 |= oracle.p1 << longlongbitsminus1;
// oracle.p1= 2;
// oracle.p1 |= oracle.p2 << longlongbitsminus1;
// oracle.p2= 2;
//
//}

struct res findt(int h, mpz_t s, long  double e, unsigned d, int ooo, int stick) {
beancounter++;

// int oracbit = oracle.p0 & 1;
// nextoracle();

struct res x;
double n = 0.;


if (h < 0) {
// maximum hashes heuristic cap exceeded

// Terminate without a solution

x.rh = SOLUTIONNOTFOUND;
x.e = 0;
x.p0 = 0;
x.p1 = 0;
x.p2 = 0;
return x;
}

int mustreducetopk = 0;
int canreducebemoreorfour = 0;

if ((e >= messagedigest) ) { // must
mustreducetopk = 1;
}

// here I must compare number of variables with the cached division
// to see if we have less than 8 variables in this level
//(after level with 8 variables comes a level with 4 variables-the public key level)
// in this case the algorithm will terminate and return a valid solution(iff all entropy is signed)
unsigned long int cacheddiv = 8;
cacheddiv <<= d;

int cmp = mpz_cmp_ui(s, cacheddiv);

if (cacheddiv == 0) {

// OVERFLOW OF DIVIDER
// Terminate without a solution here?

int terminateaftertoomanymerklereductions = 0;

if (terminateaftertoomanymerklereductions){

x.rh = SOLUTIONNOTFOUND;
x.e = 0;
x.p0 = 0;
x.p1 = 0;
x.p2 = 0;
return x;
}


// approximate double based compute

double huge = mpz_get_d (s);

double ex = 8.0 * exp2 ((double)d);



cmp = compare_doubles(huge, ex);


}




if ((cmp == 0) || (cmp > 0)) {
canreducebemoreorfour = 1;
}



if (mustreducetopk && !canreducebemoreorfour) {

// solution found. 0
x.rh = SUCCESS;
x.e = 0;
x.p0 = 0;
x.p1 = 0;
x.p2 = 0;
return x;
}

if (mustreducetopk || canreducebemoreorfour) {

// no entropy signed when reducing
n = 0;

// // print
/// mpz_out_str(stdout, 10, b);  putchar('\n');
/// printf("%lf \n", n);


// counter of the burst
int ppp = ooo-1;
if (ppp <= 0) {
ppp = 0;
}


// if ((oracle.rh == SOLUTIONNOTFOUND) || (oracbit == 1)) {

// recurse
x = findt(h-1, s, e+n, d+1, ppp, 1);

// } else {
// x.rh = SOLUTIONNOTFOUND;
// x.e = 0;
// x.p0 = 0;
// x.p1 = 0;
// x.p2 = 0;
// }

// add this level to total length
x.rh++;

// mark 1 bit
x.p2 *= 2;
x.p2 |= x.p1 >> longlongbitsminus1;
x.p1 *= 2;
x.p1 |= x.p0 >> longlongbitsminus1;
x.p0 *= 2;
x.p0++;


if (mustreducetopk) {
return x;
}


} else {
x.rh = SOLUTIONNOTFOUND;
x.e = 0;
x.p0 = 0;
x.p1 = 0;
x.p2 = 0;
}

// if not burst
if (ooo == 0) {
mpz_t b, t;


mpz_init(b);

struct res y;

//
// printf("~~~~%i ~~~~ \n",beancounter);

// explode
if (d > 0) {
// here i apply the cached merkle reduce rounds



// if (debug()) {
// // print
// mpz_out_str(stdout, 10, s);  putchar('\n');
// }



mpz_init(t);


if (1) {
mpz_t xx;
mpz_init(xx);
mpz_t gg;
mpz_init(gg);
mpz_t oo;
mpz_init(oo);
mpz_t pp;
mpz_init(pp);

mpz_set_ui(xx, 1);
mpz_mul_2exp(gg, xx, d);
mpz_sub_ui(oo,gg,1);

// if (debug()) {
// // print
// mpz_out_str(stdout, 10, oo);  putchar('\n');
// }


mpz_add(pp,oo,s);



mpz_div_2exp(t, pp, d);


// mpz_div_2exp(t, s, d);

// don't forget to free the big number
mpz_clear(pp);
// don't forget to free the big number
mpz_clear(oo);
// don't forget to free the big number
mpz_clear(gg);
// don't forget to free the big number
mpz_clear(xx);

} else {
mpz_div_2exp(t, s, d);
}


// if (debug()) {
// // print
// mpz_out_str(stdout, 10, t);  putchar('\n');
// }

// here I calculate the entropy from t
n = (mpz_get_d (t));

} else {

// print
// mpz_out_str(stdout, 10, s);  putchar('\n');

// here I calculate the entropy from t
n = (mpz_get_d (s));

}

// if (debug()) {
// // Print entropy
// printf("|%i|%lf \n", beancounter,n);
// }


n = log2(n);


// explode
if (d > 0) {
nxt(b, t);
mpz_clear(t);
} else {
nxt(b, s);
}

// print
// mpz_out_str(stdout, 10, b);  putchar('\n');

// here I calculate the entropy from b
n = (mpz_get_d (b));
// if (debug()) {
// // Print entropy
// printf("|%i|%lf \n", beancounter,n);
// }
n = log2(n);


// while (1) {
// sleep(1);
// }

// check if it exceeds the per-round entropy treshold cap
if ((n > maxentropyperlevel) && (maxentropyperlevel != 0.0)) {




// don't forget to free the big number
mpz_clear(b);

// don't do this
return x;
}


// // print

// printf("%lf \n", n);


// burst counter
int ppp = ooo;
if (stick == 1) {
ppp = burstdefault;
}

// If x branch was successful, this branch should not be longer.
if (x.rh != SOLUTIONNOTFOUND) {
h = x.rh+1;
}

// // print
// printf("|%i|%lf \n", beancounter,n);

// if ((oracle.rh == SOLUTIONNOTFOUND) || (oracbit == 0)) {
// // recurse
y = findt(h-1, b, e+n, 0, ppp, stick);
// } else {
// y.rh = SOLUTIONNOTFOUND;
// y.e = 0;
// y.p0 = 0;
// y.p1 = 0;
// y.p2 = 0;
// }

// free big number
mpz_clear(b);

// just check if solution
if (y.rh == SOLUTIONNOTFOUND) {
return x;
}

// add this level to total length
y.rh++;

if (y.e < n) {

y.e = n;

// // print
// printf("|%i|%lf \n", beancounter,n);


// while (1) {
// sleep(1);
// }

}


// mark 0 bit
y.p2 *= 2;
y.p2 |= y.p1 >> longlongbitsminus1;
y.p1 *= 2;
y.p1 |= y.p0 >> longlongbitsminus1;
y.p0 *= 2;



// get choice leading to shorter. Long is bad
if (x.rh > y.rh) {
x = y;

// get choice leading to less max entropy per level. Big is bad
} else if ((x.rh == y.rh) && (x.e > y.e)) {
x = y;
}

return x;

}

return x;
}

int roundsform_heuristics(double m) {
double room = 10.;/ 10 rounds more than expected allowed

// m160bit ..  84rounds ~~ +10
// m256bit .. 133rounds ~~ +10

return (int)((m * 0.510416667) + 2.333333333 + room);
}

int main(int argc, char *argv[])
{
// get machine word
longlongbitsminus1 = ((8*sizeof(unsigned long long))-1);
printf("LLsizem1:%Lu\n",longlongbitsminus1);


  int h;  h = 0;



//  mpz_out_str(stdout, 10, b);  putchar('\n');




struct res r;





long double m = 128.0;
long double md = 8.0;


int burstd = 0;
int burst = 15;

double elimit = 0.;
double elimitd = 0.;

// load the command line parameters
if (argc == 7) {
sscanf(argv[1], "%Lf", &m);
sscanf(argv[2], "%Lf", &md);

sscanf(argv[3], "%i", &burst);
sscanf(argv[4], "%i", &burstd);

sscanf(argv[5], "%lf", &elimit);
sscanf(argv[6], "%lf", &elimitd);
}


// predict rounds using heuristic
h = roundsform_heuristics(m);
h = 0xffff;



printf("\nINPUT: Digest M=%Lf; Mdelta=%Lf ; HeuriMaxHashes X=%i ;"
"  BURST=%i Bdelta=%i ; logLimit %lf logLdelta %lf \n\n",m,md,h,burst, burstd, elimit, elimitd);



// solve slightly different many times over the night
int i;
for (i = 0; i < 1000;i++) {


  mpz_t b;  mpz_init(b);
  mpz_set_str(b, "4", 10);/ the 10 represents the radix

// real run
// oracle.rh = SOLUTIONNOTFOUND;
maxentropyperlevel = elimit;
burstdefault = burst;
messagedigest = m;
r = findt(h,b,0,0,0,0);
// oracle = r;

// // also verify
// findt(h,b,0,0,0,0);


mpz_clear(b);


if (r.rh == SOLUTIONNOTFOUND) {
printf("SOLUTION WAS NOT FOUND PROBABLY BECAUSE HEURISTIC LIMIT IS TOO LOW: %i\n ", h);
printf("try giving more room to the heuristics\n");

return 0;
}

// print the solution
printf("BITS of Message Digest: %Lf SHORTEST HASHES: %i, burst=%i , e=%lf , PATH",m, r.rh, burstdefault, r.e);

// print the algorithm bitmap (solution)
if (r.p2 == 0) {
if (r.p1 == 0) {
printf("  %Lx | %Lx %Lx %Lx\n\n\n", r.p0, r.p2, r.p1, r.p0);
} else {
printf("  %Lx%Lx | %Lx %Lx %Lx\n\n\n", r.p1, r.p0, r.p2, r.p1, r.p0);
}} else {
printf("  %Lx%Lx%Lx | %Lx %Lx %Lx\n\n\n", r.p2, r.p1, r.p0, r.p2, r.p1, r.p0);
}

if ((md == 0.) && (burstd == 0) && (elimitd == 0.)) {

return 0;
}


// solve slightly different again

m += md;
if (h != 0xffff) {
h = roundsform_heuristics(m);
}
burst += burstd;
elimit += elimitd;
}

  return 0;

}