#!/usr/bin/env python3
"""DF-2251 analyzer: given observed ffs i_gen values (from nfsfh output on
the guest), test whether they are linked by the MINSTD chain
x[n+1] = 16807*x[n] mod (2^31-1), with the consumer mapping g = v/2 + 1.

An observer of gen g knows the kernel PRNG state t at that draw is one of
{2*(g-1), 2*(g-1)+1} (the /2 destroys only the LSB).  We forward-iterate
each candidate up to --max-steps LCG steps and check whether it maps to the
next observed gen.  For a healthy random source the hit probability is
~2*max_steps/2^31 (i.e. zero); for MINSTD the link is exact and (absent
interference draws) k is small.
"""
import argparse
import sys

M = 2**31 - 1
A = 16807


def fwd(x):
    return (A * x) % M


def gen(v):
    return v // 2 + 1


def main():
    ap = argparse.ArgumentParser()
    ap.add_argument("--max-steps", type=int, default=4096)
    ap.add_argument("gens", nargs="+", type=int)
    args = ap.parse_args()

    g = args.gens
    print(f"observed i_gen sequence: {g}")
    ok_all = True
    for i in range(len(g) - 1):
        found = None
        for cand in (2 * (g[i] - 1), 2 * (g[i] - 1) + 1):
            c = cand
            for k in range(1, args.max_steps + 1):
                c = fwd(c)
                if gen(c) == g[i + 1]:
                    found = (cand, k, c)
                    break
            if found:
                break
        if found:
            cand, k, state = found
            print(f"gen[{i}]= {g[i]} -> gen[{i+1}]= {g[i+1]}: LINKED "
                  f"(state {cand} + {k} LCG step(s) -> {state})")
        else:
            print(f"gen[{i}]= {g[i]} -> gen[{i+1}]= {g[i+1]}: NOT linked "
                  f"within {args.max_steps} LCG steps")
            ok_all = False
    print("VERDICT:", "MINSTD-LINKED (predictable from a single value)"
          if ok_all else "no MINSTD linkage (not predictable this way)")
    return 0 if ok_all else 1


if __name__ == "__main__":
    sys.exit(main())