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 #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
smallprng_rand_r(smallprng_t * x)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
prng_rand_r(prng_t * x)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
prng_rand_128_r(prng_t * x,prng_rand_128_data_t * data)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