1 /* 2 * Copyright 2012 Siarhei Siamashka <siarhei.siamashka (at) 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 #if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)) 83 #define GCC_VECTOR_EXTENSIONS_SUPPORTED 84 typedef uint32_t uint32x4 __attribute__ ((vector_size(16))); 85 typedef uint8_t uint8x16 __attribute__ ((vector_size(16))); 86 #endif 87 88 typedef struct 89 { 90 uint32_t a, b, c, d; 91 } smallprng_t; 92 93 typedef struct 94 { 95 #ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED 96 uint32x4 a, b, c, d; 97 #else 98 smallprng_t p1, p2, p3, p4; 99 #endif 100 smallprng_t p0; 101 } prng_t; 102 103 typedef union 104 { 105 uint8_t b[16]; 106 uint32_t w[4]; 107 #ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED 108 uint8x16 vb; 109 uint32x4 vw; 110 #endif 111 } prng_rand_128_data_t; 112 113 /*****************************************************************************/ 114 115 static force_inline uint32_t 116 smallprng_rand_r (smallprng_t *x) 117 { 118 uint32_t e = x->a - ((x->b << 27) + (x->b >> (32 - 27))); 119 x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17))); 120 x->b = x->c + x->d; 121 x->c = x->d + e; 122 x->d = e + x->a; 123 return x->d; 124 } 125 126 /* Generate 4 bytes (32-bits) of random data */ 127 static force_inline uint32_t 128 prng_rand_r (prng_t *x) 129 { 130 return smallprng_rand_r (&x->p0); 131 } 132 133 /* Generate 16 bytes (128-bits) of random data */ 134 static force_inline void 135 prng_rand_128_r (prng_t *x, prng_rand_128_data_t *data) 136 { 137 #ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED 138 uint32x4 e = x->a - ((x->b << 27) + (x->b >> (32 - 27))); 139 x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17))); 140 x->b = x->c + x->d; 141 x->c = x->d + e; 142 x->d = e + x->a; 143 data->vw = x->d; 144 #else 145 data->w[0] = smallprng_rand_r (&x->p1); 146 data->w[1] = smallprng_rand_r (&x->p2); 147 data->w[2] = smallprng_rand_r (&x->p3); 148 data->w[3] = smallprng_rand_r (&x->p4); 149 #endif 150 } 151 152 typedef enum 153 { 154 RANDMEMSET_MORE_00 = 1, /* ~25% chance for 0x00 bytes */ 155 RANDMEMSET_MORE_FF = 2, /* ~25% chance for 0xFF bytes */ 156 RANDMEMSET_MORE_00000000 = 4, /* ~25% chance for 0x00000000 clusters */ 157 RANDMEMSET_MORE_FFFFFFFF = 8, /* ~25% chance for 0xFFFFFFFF clusters */ 158 RANDMEMSET_MORE_00_AND_FF = (RANDMEMSET_MORE_00 | RANDMEMSET_MORE_00000000 | 159 RANDMEMSET_MORE_FF | RANDMEMSET_MORE_FFFFFFFF) 160 } prng_randmemset_flags_t; 161 162 /* Set the 32-bit seed for PRNG */ 163 void prng_srand_r (prng_t *prng, uint32_t seed); 164 165 /* Fill memory buffer with random data */ 166 void prng_randmemset_r (prng_t *prng, 167 void *buffer, 168 size_t size, 169 prng_randmemset_flags_t flags); 170 171 #endif 172
