| 516 | |
| 517 | template<unsigned int N, unsigned int K> |
| 518 | bool Equihash<N,K>::OptimisedSolve(const eh_HashState& base_state, |
| 519 | const std::function<bool(std::vector<unsigned char>)> validBlock, |
| 520 | const std::function<bool(EhSolverCancelCheck)> cancelled) |
| 521 | { |
| 522 | eh_index init_size { 1 << (CollisionBitLength + 1) }; |
| 523 | eh_index recreate_size { UntruncateIndex(1, 0, CollisionBitLength + 1) }; |
| 524 | |
| 525 | // First run the algorithm with truncated indices |
| 526 | |
| 527 | const eh_index soln_size { 1 << K }; |
| 528 | std::vector<std::shared_ptr<eh_trunc>> partialSolns; |
| 529 | size_t invalidCount = 0; |
| 530 | { |
| 531 | |
| 532 | // 1) Generate first list |
| 533 | LogPrint(BCLog::POW, "Generating first list\n"); |
| 534 | size_t hashLen = HashLength; |
| 535 | size_t lenIndices = sizeof(eh_trunc); |
| 536 | std::vector<TruncatedStepRow<TruncatedWidth>> Xt; |
| 537 | Xt.reserve(init_size); |
| 538 | unsigned char tmpHash[HashOutput]; |
| 539 | for (eh_index g = 0; Xt.size() < init_size; g++) { |
| 540 | GenerateHash(base_state, g, tmpHash, HashOutput); |
| 541 | for (eh_index i = 0; i < IndicesPerHashOutput && Xt.size() < init_size; i++) { |
| 542 | Xt.emplace_back(tmpHash+(i*N/8), N/8, HashLength, CollisionBitLength, |
| 543 | (g*IndicesPerHashOutput)+i, CollisionBitLength + 1); |
| 544 | } |
| 545 | if (cancelled(ListGeneration)) throw solver_cancelled; |
| 546 | } |
| 547 | |
| 548 | // 3) Repeat step 2 until 2n/(k+1) bits remain |
| 549 | for (size_t r = 1; r < K && Xt.size() > 0; r++) { |
| 550 | LogPrint(BCLog::POW, "Round %zu:\n", r); |
| 551 | // 2a) Sort the list |
| 552 | LogPrint(BCLog::POW, "- Sorting list\n"); |
| 553 | std::sort(Xt.begin(), Xt.end(), CompareSR(CollisionByteLength)); |
| 554 | if (cancelled(ListSorting)) throw solver_cancelled; |
| 555 | |
| 556 | LogPrint(BCLog::POW, "- Finding collisions\n"); |
| 557 | size_t i = 0; |
| 558 | size_t posFree = 0; |
| 559 | std::vector<TruncatedStepRow<TruncatedWidth>> Xc; |
| 560 | while (i < Xt.size() - 1) { |
| 561 | // 2b) Find next set of unordered pairs with collisions on the next n/(k+1) bits |
| 562 | size_t j = 1; |
| 563 | while (i+j < Xt.size() && |
| 564 | HasCollision(Xt[i], Xt[i+j], CollisionByteLength)) { |
| 565 | j++; |
| 566 | } |
| 567 | |
| 568 | // 2c) Calculate tuples (X_i ^ X_j, (i, j)) |
| 569 | //bool checking_for_zero = (i == 0 && Xt[0].IsZero(hashLen)); |
| 570 | for (size_t l = 0; l < j - 1; l++) { |
| 571 | for (size_t m = l + 1; m < j; m++) { |
| 572 | // We truncated, so don't check for distinct indices here |
| 573 | TruncatedStepRow<TruncatedWidth> Xi {Xt[i+l], Xt[i+m], |
| 574 | hashLen, lenIndices, |
| 575 | CollisionByteLength}; |
no test coverage detected