aboutsummaryrefslogtreecommitdiff
path: root/pixman/test/utils-prng.h
diff options
context:
space:
mode:
Diffstat (limited to 'pixman/test/utils-prng.h')
-rw-r--r--pixman/test/utils-prng.h168
1 files changed, 168 insertions, 0 deletions
diff --git a/pixman/test/utils-prng.h b/pixman/test/utils-prng.h
new file mode 100644
index 000000000..285107f08
--- /dev/null
+++ b/pixman/test/utils-prng.h
@@ -0,0 +1,168 @@
+/*
+ * Copyright © 2012 Siarhei Siamashka <siarhei.siamashka@gmail.com>
+ *
+ * Based on the public domain implementation of small noncryptographic PRNG
+ * authored by Bob Jenkins: http://burtleburtle.net/bob/rand/smallprng.html
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#ifndef __UTILS_PRNG_H__
+#define __UTILS_PRNG_H__
+
+/*
+ * This file provides a fast SIMD-optimized noncryptographic PRNG (pseudorandom
+ * number generator), with the output good enough to pass "Big Crush" tests
+ * from TestU01 (http://en.wikipedia.org/wiki/TestU01).
+ *
+ * SIMD code uses http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
+ * which is a GCC specific extension. There is also a slower alternative
+ * code path, which should work with any C compiler.
+ *
+ * The "prng_t" structure keeps the internal state of the random number
+ * generator. It is possible to have multiple instances of the random number
+ * generator active at the same time, in this case each of them needs to have
+ * its own "prng_t". All the functions take a pointer to "prng_t"
+ * as the first argument.
+ *
+ * Functions:
+ *
+ * ----------------------------------------------------------------------------
+ * void prng_srand_r (prng_t *prng, uint32_t seed);
+ *
+ * Initialize the pseudorandom number generator. The sequence of preudorandom
+ * numbers is deterministic and only depends on "seed". Any two generators
+ * initialized with the same seed will produce exactly the same sequence.
+ *
+ * ----------------------------------------------------------------------------
+ * uint32_t prng_rand_r (prng_t *prng);
+ *
+ * Generate a single uniformly distributed 32-bit pseudorandom value.
+ *
+ * ----------------------------------------------------------------------------
+ * void prng_randmemset_r (prng_t *prng,
+ * void *buffer,
+ * size_t size,
+ * prng_randmemset_flags_t flags);
+ *
+ * Fills the memory buffer "buffer" with "size" bytes of pseudorandom data.
+ * The "flags" argument may be used to tweak some statistics properties:
+ * RANDMEMSET_MORE_00 - set ~25% of bytes to 0x00
+ * RANDMEMSET_MORE_FF - set ~25% of bytes to 0xFF
+ * The flags can be combined. This allows a bit better simulation of typical
+ * pixel data, which normally contains a lot of fully transparent or fully
+ * opaque pixels.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include "pixman-private.h"
+
+/*****************************************************************************/
+
+#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7))
+#define GCC_VECTOR_EXTENSIONS_SUPPORTED
+typedef uint32_t uint32x4 __attribute__ ((vector_size(16)));
+typedef uint8_t uint8x16 __attribute__ ((vector_size(16)));
+#endif
+
+typedef struct
+{
+ uint32_t a, b, c, d;
+} smallprng_t;
+
+typedef struct
+{
+#ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED
+ uint32x4 a, b, c, d;
+#else
+ smallprng_t p1, p2, p3, p4;
+#endif
+ smallprng_t p0;
+} prng_t;
+
+typedef union
+{
+ uint8_t b[16];
+ uint32_t w[4];
+#ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED
+ uint8x16 vb;
+ uint32x4 vw;
+#endif
+} prng_rand_128_data_t;
+
+/*****************************************************************************/
+
+static force_inline uint32_t
+smallprng_rand_r (smallprng_t *x)
+{
+ uint32_t e = x->a - ((x->b << 27) + (x->b >> (32 - 27)));
+ x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17)));
+ x->b = x->c + x->d;
+ x->c = x->d + e;
+ x->d = e + x->a;
+ return x->d;
+}
+
+/* Generate 4 bytes (32-bits) of random data */
+static force_inline uint32_t
+prng_rand_r (prng_t *x)
+{
+ return smallprng_rand_r (&x->p0);
+}
+
+/* Generate 16 bytes (128-bits) of random data */
+static force_inline void
+prng_rand_128_r (prng_t *x, prng_rand_128_data_t *data)
+{
+#ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED
+ uint32x4 e = x->a - ((x->b << 27) + (x->b >> (32 - 27)));
+ x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17)));
+ x->b = x->c + x->d;
+ x->c = x->d + e;
+ x->d = e + x->a;
+ data->vw = x->d;
+#else
+ data->w[0] = smallprng_rand_r (&x->p1);
+ data->w[1] = smallprng_rand_r (&x->p2);
+ data->w[2] = smallprng_rand_r (&x->p3);
+ data->w[3] = smallprng_rand_r (&x->p4);
+#endif
+}
+
+typedef enum
+{
+ RANDMEMSET_MORE_00 = 1, /* ~25% chance for 0x00 bytes */
+ RANDMEMSET_MORE_FF = 2, /* ~25% chance for 0xFF bytes */
+ RANDMEMSET_MORE_00_AND_FF = (RANDMEMSET_MORE_00 | RANDMEMSET_MORE_FF)
+} prng_randmemset_flags_t;
+
+/* Set the 32-bit seed for PRNG */
+void prng_srand_r (prng_t *prng, uint32_t seed);
+
+/* Fill memory buffer with random data */
+void prng_randmemset_r (prng_t *prng,
+ void *buffer,
+ size_t size,
+ prng_randmemset_flags_t flags);
+
+#endif