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 _______________________________________________ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman