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.

The above benchmarks are of php_mt_seed 3.3.  Results should be the same
and speeds similar for php_mt_seed 3.4, except that it should be
slightly faster at skipping (ignoring) mt_rand() outputs (as requested
with "0 0 0 0" in some of the examples).
