#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <thread>
#include <atomic>
#include <chrono>
#include <queue>
#include <mutex>
#include <unordered_map>
#include <cmath>
#include <fstream>
#include <openssl/ec.h>
#include <openssl/sha.h>
#include <openssl/ripemd.h>
#include <openssl/bn.h>
#include <openssl/obj_mac.h>
#include <openssl/evp.h>

using namespace std;

// Configuration
const string TARGET_HASH160 = "b907c3a2a3b27789dfb509b730dd47703c272868";
const string BASE_KEY = "000000000000000000000000000000000000000000000000000000000005749f";
const int PUZZLE_NUM = 20;
const int WORKERS = thread::hardware_concurrency();

// Historical flip counts
const unordered_map<int, int> FLIP_TABLE = {
    {20, 8}, {21, 9}, {22, 11}, {23, 12}, {24, 9}, {25, 12}, {26, 14}, {27, 13},
    {28, 16}, {29, 18}, {30, 16}, {31, 13}, {32, 14}, {33, 15}, {34, 16}, {35, 19},
    {36, 14}, {37, 23}, {38, 21}, {39, 23}, {40, 20}, {41, 25}, {42, 24}, {43, 19},
    {44, 24}, {45, 21}, {46, 24}, {47, 27}, {48, 21}, {49, 30}, {50, 29}, {51, 25},
    {52, 27}, {53, 26}, {54, 30}, {55, 31}, {56, 31}, {57, 33}, {58, 28}, {59, 30},
    {60, 31}, {61, 25}, {62, 35}, {63, 34}, {64, 34}, {65, 37}, {66, 35}, {67, 31},
    {68, 34}
};

// Global variables
atomic<bool> stop_event(false);
mutex result_mutex;
queue<tuple<string, size_t, int>> results;

// Predict flip count
int predict_flips(int puzzle_num) {
    if (FLIP_TABLE.count(puzzle_num)) {
        return FLIP_TABLE.at(puzzle_num);
    }
    return 8; // Default
}

// Binomial coefficient
size_t combinations_count(int n, int k) {
    if (k > n) return 0;
    if (k * 2 > n) k = n - k;
    if (k == 0) return 1;

    size_t result = n;
    for(int i = 2; i <= k; ++i) {
        result *= (n - i + 1);
        result /= i;
    }
    return result;
}

// Generate combinations
vector<vector<int>> generate_combinations(int n, int k) {
    vector<vector<int>> combinations;
    vector<int> current(k, 0);
    for (int i = 0; i < k; ++i) current[i] = i;

    while (true) {
        combinations.push_back(current);

        int i = k - 1;
        while (i >= 0 && current[i] == n - k + i) --i;
        if (i < 0) break;

        ++current[i];
        for (int j = i + 1; j < k; ++j) current[j] = current[j - 1] + 1;
    }
    return combinations;
}

// Convert BIGNUM to hex string
string bn_to_hex(const BIGNUM* bn) {
    char* hex = BN_bn2hex(bn);
    string result(hex);
    OPENSSL_free(hex);
    return result;
}

// XOR operation for BIGNUM
void bn_xor(BIGNUM* result, const BIGNUM* a, const BIGNUM* b) {
    BIGNUM* tmp = BN_new();
    BN_copy(result, a);
    
    for (int i = 0; i < max(BN_num_bits(a), BN_num_bits(b)); ++i) {
        if (BN_is_bit_set(a, i) != BN_is_bit_set(b, i)) {
            BN_set_bit(result, i);
        } else {
            BN_clear_bit(result, i);
        }
    }
    
    BN_free(tmp);
}

// Compute HASH160 from BIGNUM private key
string compute_hash160(const BIGNUM* priv_key) {
    EC_KEY* ec_key = EC_KEY_new_by_curve_name(NID_secp256k1);
    if (!ec_key) return "";

    if (!EC_KEY_set_private_key(ec_key, priv_key)) {
        EC_KEY_free(ec_key);
        return "";
    }

    const EC_GROUP* group = EC_KEY_get0_group(ec_key);
    EC_POINT* pub_key = EC_POINT_new(group);
    if (!pub_key) {
        EC_KEY_free(ec_key);
        return "";
    }

    if (!EC_POINT_mul(group, pub_key, priv_key, nullptr, nullptr, nullptr)) {
        EC_POINT_free(pub_key);
        EC_KEY_free(ec_key);
        return "";
    }

    unsigned char pubkey[65];
    int pubkey_len = EC_POINT_point2oct(group, pub_key, POINT_CONVERSION_COMPRESSED, pubkey, sizeof(pubkey), nullptr);
    EC_POINT_free(pub_key);
    EC_KEY_free(ec_key);

    if (pubkey_len != 33) return "";

    unsigned char sha256[SHA256_DIGEST_LENGTH];
    SHA256(pubkey, pubkey_len, sha256);

    unsigned char ripemd160[RIPEMD160_DIGEST_LENGTH];
    RIPEMD160(sha256, SHA256_DIGEST_LENGTH, ripemd160);

    stringstream ss;
    for (int i = 0; i < RIPEMD160_DIGEST_LENGTH; ++i) {
        ss << hex << setw(2) << setfill('0') << (int)ripemd160[i];
    }
    return ss.str();
}

// Worker function
void worker(const BIGNUM* base_bn, int bit_length, int flip_count, size_t start_index, size_t end_index) {
    vector<vector<int>> combinations = generate_combinations(bit_length, flip_count);
    BIGNUM* current_bn = BN_new();
    BIGNUM* flip_mask = BN_new();

    for (size_t i = start_index; i < end_index && !stop_event.load(); ++i) {
        BN_zero(flip_mask);
        for (int pos : combinations[i]) {
            BN_set_bit(flip_mask, pos);
        }
        
        bn_xor(current_bn, base_bn, flip_mask);

        string hash160 = compute_hash160(current_bn);
        if (hash160 == TARGET_HASH160) {
            string hex_key = bn_to_hex(current_bn);
            lock_guard<mutex> lock(result_mutex);
            results.push(make_tuple(hex_key, i+1, flip_count));
            stop_event.store(true);
            break;
        }

        if ((i+1) % 10000 == 0) {
            cout << "Checked " << (i+1) << " combinations\r";
            cout.flush();
        }
    }

    BN_free(current_bn);
    BN_free(flip_mask);
}

// Parallel search
void parallel_search() {
    BIGNUM* base_bn = BN_new();
    BN_hex2bn(&base_bn, BASE_KEY.c_str());

    int flip_count = predict_flips(PUZZLE_NUM);
    size_t total_combs = combinations_count(PUZZLE_NUM, flip_count);

    cout << "Searching Puzzle " << PUZZLE_NUM << " (256-bit)" << endl;
    cout << "Base Key: " << BASE_KEY << endl;
    cout << "Target HASH160: " << TARGET_HASH160 << endl;
    cout << "Predicted Flip Count: " << flip_count << " bits" << endl;
    cout << "Total Possible Combinations: " << total_combs << endl;
    cout << "Using " << WORKERS << " workers..." << endl;

    vector<thread> threads;
    size_t chunk_size = total_combs / WORKERS;
    auto start_time = chrono::high_resolution_clock::now();

    for (int i = 0; i < WORKERS; ++i) {
        size_t start = i * chunk_size;
        size_t end = (i == WORKERS-1) ? total_combs : start + chunk_size;
        threads.emplace_back(worker, base_bn, PUZZLE_NUM, flip_count, start, end);
    }

    for (auto& t : threads) t.join();
    BN_free(base_bn);

    if (!results.empty()) {
        auto [hex_key, checked, flips] = results.front();
        auto elapsed = chrono::duration_cast<chrono::seconds>(
            chrono::high_resolution_clock::now() - start_time).count();

        cout << "\nFound solution!" << endl;
        cout << "Private Key: " << hex_key << endl;
        cout << "Bit Flips: " << flips << endl;
        cout << "Checked " << checked << " combinations in "
             << elapsed << " seconds (" << (checked/elapsed) << " keys/sec)" << endl;

        ofstream out("solution.txt");
        out << hex_key;
        out.close();
    } else {
        cout << "\nSolution not found. Try adjusting flip count." << endl;
    }
}

int main() {
    #if OPENSSL_VERSION_NUMBER < 0x10100000L
    OpenSSL_add_all_algorithms();
    #endif

    parallel_search();

    #if OPENSSL_VERSION_NUMBER < 0x10100000L
    EVP_cleanup();
    #endif

    return 0;
}