bool Kangaroo::CheckCollisionSOTA(Point& pnt, Int& t, uint32_t TameType, Int& w, uint32_t WildType, bool IsNeg) {
    if (IsNeg) {
        t.ModNegK1order();
    }
    if (TameType == TAME) {
        Int pk = t;
        pk.ModSubK1order(&w);
        Int sv = pk;
        pk.ModAddK1order(&rangeWidthDiv2);
        Point P = secp->ComputePublicKey(&pk);
        if (P.equals(pnt))
            return true;
        pk = sv;
        pk.ModNegK1order();
        pk.ModAddK1order(&rangeWidthDiv2);
        P = secp->ComputePublicKey(&pk);
        return P.equals(pnt);
    } else {
        Int pk = t;
        pk.ModSubK1order(&w);
        if (pk.bits64[3] >> 63)
            pk.ModNegK1order();
        pk.ShiftR(1);
        Int sv = pk;
        pk.ModAddK1order(&rangeWidthDiv2);
        Point P = secp->ComputePublicKey(&pk);
        if (P.equals(pnt))
            return true;
        pk = sv;
        pk.ModNegK1order();
        pk.ModAddK1order(&rangeWidthDiv2);
        P = secp->ComputePublicKey(&pk);
        return P.equals(pnt);
    }
    return false;
}

void Kangaroo::SolveKeyCPU(TH_PARAM *ph) {
    vector<ITEM> dps;
    double lastSent = 0;
    int thId = ph->threadId;
    ph->nbKangaroo = CPU_GRP_SIZE;

#ifdef USE_SYMMETRY
    ph->symClass = new uint64_t[CPU_GRP_SIZE];
    for (int i = 0; i < CPU_GRP_SIZE; i++) ph->symClass[i] = 0;
#endif

    IntGroup *grp = new IntGroup(CPU_GRP_SIZE);
    Int *dx = new Int[CPU_GRP_SIZE];
    if (ph->px == NULL) {
        ph->px = new Int[CPU_GRP_SIZE];
        ph->py = new Int[CPU_GRP_SIZE];
        ph->distance = new Int[CPU_GRP_SIZE];
        CreateHerd(CPU_GRP_SIZE, ph->px, ph->py, ph->distance, TAME);
    }

    if (keyIdx == 0) {
        ::printf("[+] SolveKeyCPU Thread %02d: %d kangaroos\n", ph->threadId, CPU_GRP_SIZE);
    }

    ph->hasStarted = true;
    Int dy, rx, ry, _s, _p;
    int max_iterations = (1 << dpSize) * 20;
    std::vector<uint64_t> old(CPU_GRP_SIZE * OLD_LEN, 0);
    std::vector<int> kangIterations(CPU_GRP_SIZE, 0);

    while (!endOfSearch) {
        for (int i = 0; i < CPU_GRP_SIZE; i++) {
            if (i < CPU_GRP_SIZE 3) {
                ph->distance[i].Rand(rangePower - 4);
            } else {
                ph->distance[i].Rand(rangePower - 1); 
                ph->distance[i].bits64[0] &= 0xFFFFFFFFFFFFFFFE;
            }
            ph->px[i] = ph->distance[i];
            ph->py[i] = ph->distance[i];
        }

        for (int i = CPU_GRP_SIZE 3; i < 2 * CPU_GRP_SIZE 3; i++) {
            ph->px[i].ModSub(&ph->distance[i], &rangeWidthDiv2); / Wild 1
        }
        for (int i = 2 * CPU_GRP_SIZE 3; i < CPU_GRP_SIZE; i++) {
            ph->px[i].ModAdd(&ph->distance[i], &rangeWidthDiv2); / Wild 2
        }

        bool found = false;

        while (!found) {
            for (int i = 0; i < CPU_GRP_SIZE; i++) {
                bool invert = (ph->py[i].bits64[0] & 1);
                bool cycled = false;

                for (int j = 0; j < OLD_LEN; j++) {
                    if (old[OLD_LEN * i + j] == ph->distance[i].bits64[0]) {
                        cycled = true;
                        break;
                    }
                }

                old[OLD_LEN * i + (kangIterations[i] % OLD_LEN)] = ph->distance[i].bits64[0];
                kangIterations[i]++;
                if (kangIterations[i] > max_iterations) {
                    cycled = true;
                }

                if (cycled) {
                    if (i < CPU_GRP_SIZE 3) {
                        ph->distance[i].Rand(rangePower - 4);
                    } else {
                        ph->distance[i].Rand(rangePower - 1);
                        ph->distance[i].bits64[0] &= 0xFFFFFFFFFFFFFFFE;
                    }
                    kangIterations[i] = 0;
                    ph->px[i] = ph->distance[i];
                    ph->py[i] = ph->distance[i];
                    if (i >= CPU_GRP_SIZE 3) {
                        if (i < 2 * CPU_GRP_SIZE 3) {
                            ph->px[i].ModSub(&ph->distance[i], &rangeWidthDiv2); / Wild 1
                        } else {
                            ph->px[i].ModAdd(&ph->distance[i], &rangeWidthDiv2); / Wild 2
                        }
                    }
                    memset(&old[OLD_LEN * i], 0, 8 * OLD_LEN);
                    continue;
                }

                int jmp_ind = ph->px[i].bits64[0] % NB_JUMP;
                Int *jumpDist = &jumpDistance[jmp_ind];
                if (invert) jumpDist->ModNeg();
                ph->px[i].ModAdd(&ph->px[i], jumpDist);
                if (invert) ph->distance[i].ModSub(jumpDist);
                else ph->distance[i].ModAdd(jumpDist);

                if (IsDP(&ph->px[i])) {
                    LOCK(ghMutex);
                    if (!endOfSearch) {
                        if (CheckCollisionSOTA(keyToSearch, ph->distance[i], (i < CPU_GRP_SIZE 3) ? TAME : ((i < 2 * CPU_GRP_SIZE 3) ? WILD : WILD2), ph->distance[i], NB_JUMP, invert)) {
                            CreateHerd(1, &ph->px[i], &ph->py[i], &ph->distance[i], (i < CPU_GRP_SIZE 3) ? TAME : ((i < 2 * CPU_GRP_SIZE 3) ? WILD : WILD2), false);
                            collisionInSameHerd++;
                        }
                    }
                    UNLOCK(ghMutex);
                }
                if (!endOfSearch) counters[thId]++;
            }
        }
    }

    delete grp;
    delete[] dx;
    safe_delete_array(ph->px);
    safe_delete_array(ph->py);
    safe_delete_array(ph->distance);
#ifdef USE_SYMMETRY
    safe_delete_array(ph->symClass);
#endif
    ph->isRunning = false;
}