/*
 * recover2.c - recover the kernel MINSTD state from a probe.c observation
 * string under the icmptypes-8 model:
 *   'D': 1 draw, d1 <  T
 *   'T': 2 draws, d1 >= T, d2 <  T
 *   'R': 4 draws, d1 >= T, d2 >= T (d3,d4 consumed, never deny)
 * Exhaustive search over states 1..2^31-2, pthreads.
 *
 * usage: recover2 <T> <obs>
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <pthread.h>

#define M 2147483647ULL
#define A 16807ULL

static uint64_t T;
static const char *obs;
static int nobs;

static int simulate(uint64_t s0, uint64_t *endstate)
{
    uint64_t s = s0;
    for (int i = 0; i < nobs; i++) {
        uint64_t d1 = (A * s) % M; s = d1;
        switch (obs[i]) {
        case 'D':
            if (d1 >= T) return 0;
            break;
        case 'T': {
            if (d1 < T) return 0;
            uint64_t d2 = (A * s) % M; s = d2;
            if (d2 >= T) return 0;
            break;
        }
        case 'R': {
            if (d1 < T) return 0;
            uint64_t d2 = (A * s) % M; s = d2;
            if (d2 < T) return 0;
            s = (A * s) % M;         /* reply out-check draw */
            s = (A * s) % M;         /* reply in-check draw */
            break;
        }
        default:
            return 0;
        }
        *endstate = s;
    }
    return 1;
}

struct range { uint64_t lo, hi; };
static struct range ranges[64];
static uint64_t found[16];
static int nfound;
static pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;

static void *worker(void *arg)
{
    struct range *r = arg;
    for (uint64_t s = r->lo; s <= r->hi; s++) {
        uint64_t end;
        if (simulate(s, &end)) {
            pthread_mutex_lock(&mtx);
            if (nfound < 16) { found[nfound] = s; }
            nfound++;
            pthread_mutex_unlock(&mtx);
        }
    }
    return NULL;
}

int main(int argc, char **argv)
{
    if (argc != 3) { fprintf(stderr, "usage: recover2 T obs\n"); return 2; }
    T = strtoull(argv[1], NULL, 0);
    obs = argv[2];
    nobs = strlen(obs);
    int cD=0,cT=0,cR=0;
    for (int i=0;i<nobs;i++){ if(obs[i]=='D')cD++; else if(obs[i]=='T')cT++; else if(obs[i]=='R')cR++; }
    fprintf(stderr, "obs n=%d D=%d T=%d R=%d\n", nobs, cD, cT, cR);

    int nthr = 6;
    uint64_t span = (M - 1) / nthr;
    pthread_t th[64];
    for (int i = 0; i < nthr; i++) {
        ranges[i].lo = 1 + (uint64_t)i * span;
        ranges[i].hi = (i == nthr - 1) ? (M - 1) : ((uint64_t)(i + 1) * span);
        pthread_create(&th[i], NULL, worker, &ranges[i]);
    }
    for (int i = 0; i < nthr; i++) pthread_join(th[i], NULL);

    fprintf(stderr, "search done -> %d match(es)\n", nfound);
    if (nfound == 0) { printf("NO-MATCH\n"); return 1; }
    for (int i = 0; i < nfound && i < 16; i++) {
        uint64_t end;
        simulate(found[i], &end);
        printf("MATCH start=%llu end=%llu\n",
               (unsigned long long)found[i], (unsigned long long)end);
    }
    return 0;
}