This is a PHP mt_rand() seed cracker.  In the most trivial invocation
mode, it finds possible seeds given the very first mt_rand() output
after possible seeding with mt_srand().  With advanced invocation modes,
it is also able to match multiple, non-first, and/or inexact mt_rand()
outputs to possible seed values.

Currently, it attacks the mt_rand() algorithm of PHP versions 5.2.1
through 7.0.x.  PHP below 5.2.1 is totally unsupported.  PHP 7.1.0+ is
mostly unsupported, although in the simplest modes PHP 7.1.0+ seeds will
occasionally be found (in those special cases where the algorithm does
not deviate from 5.2.1's).

Here's a sample run.  First generate a sample "random" number using PHP
5.2.1 through 7.0.x:

$ php5 -r 'mt_srand(1234567890); echo mt_rand(), "\n";'
1328851649

Now build and run the cracker (on an i7-4770K CPU, using 256-bit AVX2):

$ make
gcc -Wall -march=native -mtune=generic -O2 -fomit-frame-pointer -funroll-loops -fopenmp php_mt_seed.c -o php_mt_seed
php_mt_seed.c:47:2: warning: #warning AVX-512 not enabled. Try gcc -mavx512f (on Intel Knights Landing, Skylake-X, or some newer). [-Wcpp]
 #warning AVX-512 not enabled. Try gcc -mavx512f (on Intel Knights Landing, Skylake-X, or some newer).
  ^
$ time ./php_mt_seed 1328851649
Found 0, trying 637534208 - 671088639, speed 90430384 seeds per second 
seed = 658126103
Found 1, trying 1207959552 - 1241513983, speed 90483861 seeds per second 
seed = 1234567890
Found 2, trying 4261412864 - 4294967295, speed 90495070 seeds per second 
Found 2

real	0m47.464s
user	6m17.200s
sys	0m0.004s

In under one minute of real time, it found the original seed, another
seed that also produces the same mt_rand() output, and it searched the
rest of the 32-bit seed space (not finding other matches).

Testing on a bigger machine (two E5-2670 v1 CPUs, using 128-bit AVX):

$ time ./php_mt_seed 1328851649
Found 0, trying 637534208 - 671088639, speed 233529013 seeds per second 
seed = 658126103
Found 1, trying 1207959552 - 1241513983, speed 235929600 seeds per second 
seed = 1234567890
Found 2, trying 4261412864 - 4294967295, speed 237802057 seeds per second 
Found 2

real	0m18.061s
user	9m33.431s
sys	0m0.007s

Matching of multiple outputs:

$ php5 -r 'mt_srand(1234567890); for ($i = 0; $i < 10; $i++) { echo mt_rand(0, 9), " "; } echo "\n";'
6 6 4 1 1 2 8 4 5 8

On the same machine as above:

$ time ./php_mt_seed 6 6 0 9  6 6 0 9  4 4 0 9  1 1 0 9  1 1 0 9  2 2 0 9  8 8 0 9  4 4 0 9  5 5 0 9  8 8 0 9
Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10
Found 0, trying 1207959552 - 1241513983, speed 218833252 seeds per second 
seed = 1234567890
Found 1, trying 4261412864 - 4294967295, speed 221372096 seeds per second 
Found 1

real	0m19.405s
user	10m15.530s
sys	0m0.021s

Matching inexact outputs, if we had some uncertainty about the numbers:

$ time ./php_mt_seed 6 6 0 9  6 6 0 9  4 4 0 9  1 1 0 9  1 1 0 9  2 2 0 9  7 8 0 9  4 4 0 9  0 0 0 0  8 8 0 9
Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 RANGE-FROM-10 EXACT-FROM-10 SKIP EXACT-FROM-10
Found 0, trying 1207959552 - 1241513983, speed 214939422 seeds per second 
seed = 1234567890
Found 1, trying 1409286144 - 1442840575, speed 216148181 seeds per second 
seed = 1414163717
Found 2, trying 1879048192 - 1912602623, speed 217482429 seeds per second 
seed = 1893625793
Found 3, trying 2785017856 - 2818572287, speed 219120208 seeds per second 
seed = 2804485451
Found 4, trying 3791650816 - 3825205247, speed 219933341 seeds per second 
seed = 3810276440
Found 5, trying 4261412864 - 4294967295, speed 220228054 seeds per second 
Found 5

real	0m19.503s
user	10m14.207s
sys	0m0.019s

Notice how "7 8 0 9" specifies a range of possible values (7 to 8), and
"0 0 0 0" means to skip (ignore) this one mt_rand() output value.  In
our case, this uncertainty results in several additional possible seeds
being found.

To build php_mt_seed for first generation Xeon Phi (Knights Corner),
install Intel's C compiler and run "make mic".  To run php_mt_seed on
Xeon Phi, copy Intel C compiler's OpenMP runtime library (such as
libiomp5.so) to the Xeon Phi card, e.g. using scp.  Then SSH in to the
card and run a command like:

$ LD_LIBRARY_PATH=. time ./php_mt_seed 1328851649
Found 0, trying 536870912 - 805306367, speed 440058124 seeds per second 
seed = 658126103
Found 1, trying 1073741824 - 1342177279, speed 511305630 seeds per second 
seed = 1234567890
Found 2, trying 4026531840 - 4294967295, speed 579357099 seeds per second 
Found 2
real    0m 7.60s
user    28m 45.01s
sys     0m 3.78s

This is on a Xeon Phi 5110P.

Advanced invocation modes work too, but the performance impact of the
non-vectorized portions of code is higher than on regular CPUs:

$ LD_LIBRARY_PATH=. time ./php_mt_seed 6 6 0 9  6 6 0 9  4 4 0 9  1 1 0 9  1 1 0 9  2 2 0 9  7 8 0 9  4 4 0 9  0 0 0 0  8 8 0 9
Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 RANGE-FROM-10 EXACT-FROM-10 SKIP EXACT-FROM-10
Found 0, trying 1073741824 - 1342177279, speed 348617475 seeds per second 
seed = 1234567890
Found 1, trying 1342177280 - 1610612735, speed 356015193 seeds per second 
seed = 1414163717
Found 2, trying 1879048192 - 2147483647, speed 365573578 seeds per second 
seed = 1893625793
Found 3, trying 2684354560 - 2952790015, speed 372309925 seeds per second 
seed = 2804485451
Found 4, trying 3758096384 - 4026531839, speed 377318914 seeds per second 
seed = 3810276440
Found 5, trying 4026531840 - 4294967295, speed 378078107 seeds per second 
Found 5
real    0m 11.40s
user    44m 38.16s
sys     0m 1.67s

Building and running on second generation Xeon Phi (Knights Landing) and
later doesn't necessarily require a special make target since those
support AVX-512 (which recent gcc supports too) and doesn't necessarily
require any runtime library tricks (perhaps not when Xeon Phi is the
host CPU rather than a coprocessor).  Here are the same benchmarks on a
Xeon Phi 7290 used as the host processor:

$ time ./php_mt_seed 1328851649
Found 0, trying 536870912 - 805306367, speed 1248537004 seeds per second
seed = 658126103
Found 1, trying 1073741824 - 1342177279, speed 1359166865 seeds per second
seed = 1234567890
Found 2, trying 4026531840 - 4294967295, speed 1453621602 seeds per second
Found 2

real    0m2.952s
user    13m51.549s
sys     0m1.213s

$ time ./php_mt_seed 6 6 0 9  6 6 0 9  4 4 0 9  1 1 0 9  1 1 0 9  2 2 0 9  7 8 0 9  4 4 0 9  0 0 0 0  8 8 0 9
Pattern: EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 EXACT-FROM-10 RANGE-FROM-10 EXACT-FROM-10 SKIP EXACT-FROM-10
Found 0, trying 1073741824 - 1342177279, speed 1130254551 seeds per second
seed = 1234567890
Found 1, trying 1342177280 - 1610612735, speed 1147160068 seeds per second
seed = 1414163717
Found 2, trying 1879048192 - 2147483647, speed 1181791315 seeds per second
seed = 1893625793
Found 3, trying 2684354560 - 2952790015, speed 1203746439 seeds per second
seed = 2804485451
Found 4, trying 3758096384 - 4026531839, speed 1224135629 seeds per second
seed = 3810276440
Found 5, trying 4026531840 - 4294967295, speed 1227601170 seeds per second
Found 5

real    0m3.501s
user    16m17.088s
sys     0m0.096s

This is when building with gcc 7.1.1.  The speeds with icc 17.0.4 happen
to be around 10% worse.

All of the above benchmarks are on CPUs running at stock clocks, with
turbo boost and HT enabled (where applicable).  Compiler versions vary
(gcc 4.4.7 to 7.1.1; icc 14.0.0 and 17.0.4), and so do Linux
distributions and kernel versions (which affects how threads are
scheduled across the logical CPUs).  And yes, all of these are on Linux.
