[Pixman] [PATCH 0/5] PRNG upgrade for pixman tests

[Siarhei Siamashka]

A simple linear congruential generator (LCG) has been used for pixman
test suite since the introduction of the tests based on random fuzzing.
There was no particular reason why it was selected. The compilers are
traditionally using LCG. So just implementing LCG for pixman tests, we
got it as good (and as bad) as "rand" from the C library, but
deterministic, predictable and fully under our control.

But LCG has some practical issues, which are already showing up:

For example, random numbers are currently generated 10768371425 times in
blitters-test for the standard run, which is a bit more than 2^33. For
an LCG with 32-bit state, the period can't be more than 2^32 and we are
already exceeding it. It means that the sequences of randomly generated
pixels are going to be inevitably repeating even across runs with different
seeds, thus reducing the quality of testing. A better period length is
needed, which means larger than 32-bit PRNG state.

Additionally LCG is known to have poor statistical properties in the low
bits (the lowest bit is just flipping between 0 and 1 for example), so
only 15 high bits are used for the return value of lcg_rand(). This
results in poor performance when generating large buffers with random
pixel data (one lcg_rand() call per 8 bits of image data).


I looked around and checked different implementations for fast PRNGs
that are commonly in use. If going just after the best statistics
properties, then some cryptographic cypher would be the best choice.
But the performance is also very important for pixman tests, so this
must be also considered. The small noncryptographic PRNG by Bob Jenkins
looked particularly interesting to me:
    http://www.burtleburtle.net/bob/rand/smallprng.html

Another fast PRNG commonly recommended on the Internet in various forums
is xorshift:
    http://en.wikipedia.org/wiki/Xorshift

They both have 128-bit state (if using xor128 for xorshift), which is a
must for good period length. And thir performance is comparable. However
when I tried to run TestU01 PRNG test suite for the xorshift example
directly from wikipedia, it failed even for "Small Crush" test. The PRNG
from Bob Jenkins passes all the tests from TestU01 just fine.

Now taking advantage of SIMD, an obvious choice is to run several instances
of 32-bit PRNGs in parallel and combine their data when preparing random
buffers. Using four 32-bit generators in parallel allows to use 128-bit
SIMD. The only problem here is the choice of seeds for these four
independent generators. We get one seed in the 'srand' call and need to
initialize the state for all the generators. First I tried to use all
the same PRNG to generate seeds. Like taking the user provided seed ->
initializing one PRNG -> generating 4 numbers and using them as seeds.
But it turned out to be a bad choice. The "Big Crush" test did not like
something about it:

========= Summary results of BigCrush =========

 Version:          TestU01 1.2.3
 Generator:        simdprng
 Number of statistics:  160
 Total CPU time:   04:00:41.77
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
 33  CouponCollector, r = 27         6.1e-4
 62  WeightDistrib, r = 0            8.7e-4
 74  RandomWalk1 H (L=50, r=0)       9.5e-4
 91  HammingWeight2, r = 27          5.3e-5
 ----------------------------------------------
 All other tests were passed

Looks like this PRNG is non-cryptographic for a reason. A possible
solution would be to use some cryptographic hash (MD5, SHA1, ...) to
generate truly uncorrelated seeds. But in this case we would need to
pull in the code for this cryptographic hash into pixman source tree
as well. Just for fun I tried to alternatively use LCG to generate
the seeds for the independent generators, and it also worked fine.

As for the SIMD implementation, I decided to take a somewhat unusual
approach. Typically one uses CPU-specific intrinsics. This provides
support for just one hardware platform (let's say x86 SSE2), but
with a choice of multiple compilers (gcc, clang, icc, ...). I decided
to do this the other way around :) And implemented the code using
the GCC specific vector extensions:
    http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
This means that just a single compiler is supported (GCC 4.7 or newer),
but the code is quite conveniently optimized for multiple platforms at
once (x86 SSE2, ARM NEON, PPC Altivec, ...).

In particular, x86-64 users are the happy campers, because SSE2 is
automatically available there without any need to provide extra
flags to the compiler. The users of ARM and PPC hardware may need
to add -mfpu=neon and -maltivec options to CFLAGS in order to make
running the pixman test suite faster.

The same patches are also available at a temporary git branch here:
    http://cgit.freedesktop.org/~siamashka/pixman-g2d/log/?h=prng


Siarhei Siamashka (5):
  test: Change is_little_endian() into inline function
  test: Added a better PRNG (pseudorandom number generator)
  test: Search/replace 'lcg_*' -> 'prng_*'
  test: Switch to the new PRNG instead of old LCG
  test: Get rid of the obsolete 'prng_rand_N' and 'prng_rand_u32'

 demos/Makefile.am           |    3 +-
 test/Makefile.sources       |    3 +
 test/affine-test.c          |  111 ++++++++++----------
 test/alpha-loop.c           |   11 ++-
 test/alphamap.c             |    2 +
 test/blitters-test.c        |   60 +++++------
 test/combiner-test.c        |    4 +-
 test/composite-traps-test.c |   58 +++++-----
 test/composite.c            |   12 +-
 test/glyph-test.c           |   94 ++++++++---------
 test/prng-test.c            |  172 +++++++++++++++++++++++++++++++
 test/region-contains-test.c |   28 +++---
 test/region-test.c          |   10 +-
 test/rotate-test.c          |   14 +--
 test/scaling-helpers-test.c |    9 +-
 test/scaling-test.c         |  129 +++++++++++------------
 test/stress-test.c          |  112 ++++++++++----------
 test/utils-prng.c           |  238 +++++++++++++++++++++++++++++++++++++++++++
 test/utils-prng.h           |  168 ++++++++++++++++++++++++++++++
 test/utils.c                |   25 ++---
 test/utils.h                |   58 +++++-----
 21 files changed, 941 insertions(+), 380 deletions(-)
 create mode 100644 test/prng-test.c
 create mode 100644 test/utils-prng.c
 create mode 100644 test/utils-prng.h

-- 
1.7.8.6