qemu/pixman/test/utils-prng.h

   1 /*
   2  * Copyright © 2012 Siarhei Siamashka <siarhei.siamashka@gmail.com>
   3  *
   4  * Based on the public domain implementation of small noncryptographic PRNG
   5  * authored by Bob Jenkins: http://burtleburtle.net/bob/rand/smallprng.html
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a
   8  * copy of this software and associated documentation files (the "Software"),
   9  * to deal in the Software without restriction, including without limitation
  10  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  11  * and/or sell copies of the Software, and to permit persons to whom the
  12  * Software is furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice (including the next
  15  * paragraph) shall be included in all copies or substantial portions of the
  16  * Software.
  17  *
  18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  21  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  22  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  24  * DEALINGS IN THE SOFTWARE.
  25  */
  26
  27 #ifndef __UTILS_PRNG_H__
  28 #define __UTILS_PRNG_H__
  29
  30 /*
  31  * This file provides a fast SIMD-optimized noncryptographic PRNG (pseudorandom
  32  * number generator), with the output good enough to pass "Big Crush" tests
  33  * from TestU01 (http://en.wikipedia.org/wiki/TestU01).
  34  *
  35  * SIMD code uses http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
  36  * which is a GCC specific extension. There is also a slower alternative
  37  * code path, which should work with any C compiler.
  38  *
  39  * The "prng_t" structure keeps the internal state of the random number
  40  * generator. It is possible to have multiple instances of the random number
  41  * generator active at the same time, in this case each of them needs to have
  42  * its own "prng_t". All the functions take a pointer to "prng_t"
  43  * as the first argument.
  44  *
  45  * Functions:
  46  *
  47  * ----------------------------------------------------------------------------
  48  * void prng_srand_r (prng_t *prng, uint32_t seed);
  49  *
  50  * Initialize the pseudorandom number generator. The sequence of preudorandom
  51  * numbers is deterministic and only depends on "seed". Any two generators
  52  * initialized with the same seed will produce exactly the same sequence.
  53  *
  54  * ----------------------------------------------------------------------------
  55  * uint32_t prng_rand_r (prng_t *prng);
  56  *
  57  * Generate a single uniformly distributed 32-bit pseudorandom value.
  58  *
  59  * ----------------------------------------------------------------------------
  60  * void prng_randmemset_r (prng_t                  *prng,
  61  *                         void                    *buffer,
  62  *                         size_t                   size,
  63  *                         prng_randmemset_flags_t  flags);
  64  *
  65  * Fills the memory buffer "buffer" with "size" bytes of pseudorandom data.
  66  * The "flags" argument may be used to tweak some statistics properties:
  67  *    RANDMEMSET_MORE_00 - set ~25% of bytes to 0x00
  68  *    RANDMEMSET_MORE_FF - set ~25% of bytes to 0xFF
  69  * The flags can be combined. This allows a bit better simulation of typical
  70  * pixel data, which normally contains a lot of fully transparent or fully
  71  * opaque pixels.
  72  */
  73
  74 #ifdef HAVE_CONFIG_H
  75 #include <config.h>
  76 #endif
  77
  78 #include "pixman-private.h"
  79
  80 /*****************************************************************************/
  81
  82 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
  83 typedef uint32_t uint32x4 __attribute__ ((vector_size(16)));
  84 typedef uint8_t  uint8x16 __attribute__ ((vector_size(16)));
  85 #endif
  86
  87 typedef struct
  88 {
  89     uint32_t a, b, c, d;
  90 } smallprng_t;
  91
  92 typedef struct
  93 {
  94 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
  95     uint32x4 a, b, c, d;
  96 #else
  97     smallprng_t p1, p2, p3, p4;
  98 #endif
  99     smallprng_t p0;
 100 } prng_t;
 101
 102 typedef union
 103 {
 104     uint8_t  b[16];
 105     uint32_t w[4];
 106 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
 107     uint8x16 vb;
 108     uint32x4 vw;
 109 #endif
 110 } prng_rand_128_data_t;
 111
 112 /*****************************************************************************/
 113
 114 static force_inline uint32_t
 115 smallprng_rand_r (smallprng_t *x)
 116 {
 117     uint32_t e = x->a - ((x->b << 27) + (x->b >> (32 - 27)));
 118     x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17)));
 119     x->b = x->c + x->d;
 120     x->c = x->d + e;
 121     x->d = e + x->a;
 122     return x->d;
 123 }
 124
 125 /* Generate 4 bytes (32-bits) of random data */
 126 static force_inline uint32_t
 127 prng_rand_r (prng_t *x)
 128 {
 129     return smallprng_rand_r (&x->p0);
 130 }
 131
 132 /* Generate 16 bytes (128-bits) of random data */
 133 static force_inline void
 134 prng_rand_128_r (prng_t *x, prng_rand_128_data_t *data)
 135 {
 136 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
 137     uint32x4 e = x->a - ((x->b << 27) + (x->b >> (32 - 27)));
 138     x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17)));
 139     x->b = x->c + x->d;
 140     x->c = x->d + e;
 141     x->d = e + x->a;
 142     data->vw = x->d;
 143 #else
 144     data->w[0] = smallprng_rand_r (&x->p1);
 145     data->w[1] = smallprng_rand_r (&x->p2);
 146     data->w[2] = smallprng_rand_r (&x->p3);
 147     data->w[3] = smallprng_rand_r (&x->p4);
 148 #endif
 149 }
 150
 151 typedef enum
 152 {
 153     RANDMEMSET_MORE_00        = 1, /* ~25% chance for 0x00 bytes */
 154     RANDMEMSET_MORE_FF        = 2, /* ~25% chance for 0xFF bytes */
 155     RANDMEMSET_MORE_00000000  = 4, /* ~25% chance for 0x00000000 clusters */
 156     RANDMEMSET_MORE_FFFFFFFF  = 8, /* ~25% chance for 0xFFFFFFFF clusters */
 157     RANDMEMSET_MORE_00_AND_FF = (RANDMEMSET_MORE_00 | RANDMEMSET_MORE_00000000 |
 158                                  RANDMEMSET_MORE_FF | RANDMEMSET_MORE_FFFFFFFF)
 159 } prng_randmemset_flags_t;
 160
 161 /* Set the 32-bit seed for PRNG */
 162 void prng_srand_r (prng_t *prng, uint32_t seed);
 163
 164 /* Fill memory buffer with random data */
 165 void prng_randmemset_r (prng_t                  *prng,
 166                         void                    *buffer,
 167                         size_t                   size,
 168                         prng_randmemset_flags_t  flags);
 169
 170 #endif