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 #include "utils.h"
28 #include "utils-prng.h"
29
30 #if defined(HAVE_GCC_VECTOR_EXTENSIONS) && defined(__SSE2__)
31 #include <xmmintrin.h>
32 #endif
33
smallprng_srand_r(smallprng_t * x,uint32_t seed)34 void smallprng_srand_r (smallprng_t *x, uint32_t seed)
35 {
36 uint32_t i;
37 x->a = 0xf1ea5eed, x->b = x->c = x->d = seed;
38 for (i = 0; i < 20; ++i)
39 smallprng_rand_r (x);
40 }
41
42 /*
43 * Set a 32-bit seed for PRNG
44 *
45 * LCG is used here for generating independent seeds for different
46 * smallprng instances (in the case if smallprng is also used for
47 * generating these seeds, "Big Crush" test from TestU01 detects
48 * some problems in the glued 'prng_rand_128_r' output data).
49 * Actually we might be even better using some cryptographic
50 * hash for this purpose, but LCG seems to be also enough for
51 * passing "Big Crush".
52 */
prng_srand_r(prng_t * x,uint32_t seed)53 void prng_srand_r (prng_t *x, uint32_t seed)
54 {
55 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
56 int i;
57 prng_rand_128_data_t dummy;
58 smallprng_srand_r (&x->p0, seed);
59 x->a[0] = x->a[1] = x->a[2] = x->a[3] = 0xf1ea5eed;
60 x->b[0] = x->c[0] = x->d[0] = (seed = seed * 1103515245 + 12345);
61 x->b[1] = x->c[1] = x->d[1] = (seed = seed * 1103515245 + 12345);
62 x->b[2] = x->c[2] = x->d[2] = (seed = seed * 1103515245 + 12345);
63 x->b[3] = x->c[3] = x->d[3] = (seed = seed * 1103515245 + 12345);
64 for (i = 0; i < 20; ++i)
65 prng_rand_128_r (x, &dummy);
66 #else
67 smallprng_srand_r (&x->p0, seed);
68 smallprng_srand_r (&x->p1, (seed = seed * 1103515245 + 12345));
69 smallprng_srand_r (&x->p2, (seed = seed * 1103515245 + 12345));
70 smallprng_srand_r (&x->p3, (seed = seed * 1103515245 + 12345));
71 smallprng_srand_r (&x->p4, (seed = seed * 1103515245 + 12345));
72 #endif
73 }
74
75 static force_inline void
store_rand_128_data(void * addr,prng_rand_128_data_t * d,int aligned)76 store_rand_128_data (void *addr, prng_rand_128_data_t *d, int aligned)
77 {
78 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
79 if (aligned)
80 {
81 *(uint8x16 *)addr = d->vb;
82 return;
83 }
84 else
85 {
86 #ifdef __SSE2__
87 /* workaround for http://gcc.gnu.org/PR55614 */
88 _mm_storeu_si128 (addr, _mm_loadu_si128 ((__m128i *)d));
89 return;
90 #endif
91 }
92 #endif
93 /* we could try something better for unaligned writes (packed attribute),
94 * but GCC is not very reliable: http://gcc.gnu.org/PR55454 */
95 memcpy (addr, d, 16);
96 }
97
98 /*
99 * Helper function and the actual code for "prng_randmemset_r" function
100 */
101 static force_inline void
randmemset_internal(prng_t * prng,uint8_t * buf,size_t size,prng_randmemset_flags_t flags,int aligned)102 randmemset_internal (prng_t *prng,
103 uint8_t *buf,
104 size_t size,
105 prng_randmemset_flags_t flags,
106 int aligned)
107 {
108 prng_t local_prng = *prng;
109 prng_rand_128_data_t randdata;
110 size_t i;
111
112 while (size >= 16)
113 {
114 prng_rand_128_data_t t;
115 if (flags == 0)
116 {
117 prng_rand_128_r (&local_prng, &randdata);
118 }
119 else
120 {
121 prng_rand_128_r (&local_prng, &t);
122 prng_rand_128_r (&local_prng, &randdata);
123 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
124 if (flags & RANDMEMSET_MORE_FF)
125 {
126 const uint8x16 const_C0 =
127 {
128 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0,
129 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0, 0xC0
130 };
131 randdata.vb |= (t.vb >= const_C0);
132 }
133 if (flags & RANDMEMSET_MORE_00)
134 {
135 const uint8x16 const_40 =
136 {
137 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40,
138 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40, 0x40
139 };
140 randdata.vb &= (t.vb >= const_40);
141 }
142 if (flags & RANDMEMSET_MORE_FFFFFFFF)
143 {
144 const uint32x4 const_C0000000 =
145 {
146 0xC0000000, 0xC0000000, 0xC0000000, 0xC0000000
147 };
148 randdata.vw |= ((t.vw << 30) >= const_C0000000);
149 }
150 if (flags & RANDMEMSET_MORE_00000000)
151 {
152 const uint32x4 const_40000000 =
153 {
154 0x40000000, 0x40000000, 0x40000000, 0x40000000
155 };
156 randdata.vw &= ((t.vw << 30) >= const_40000000);
157 }
158 #else
159 #define PROCESS_ONE_LANE(i) \
160 if (flags & RANDMEMSET_MORE_FF) \
161 { \
162 uint32_t mask_ff = (t.w[i] & (t.w[i] << 1)) & 0x80808080; \
163 mask_ff |= mask_ff >> 1; \
164 mask_ff |= mask_ff >> 2; \
165 mask_ff |= mask_ff >> 4; \
166 randdata.w[i] |= mask_ff; \
167 } \
168 if (flags & RANDMEMSET_MORE_00) \
169 { \
170 uint32_t mask_00 = (t.w[i] | (t.w[i] << 1)) & 0x80808080; \
171 mask_00 |= mask_00 >> 1; \
172 mask_00 |= mask_00 >> 2; \
173 mask_00 |= mask_00 >> 4; \
174 randdata.w[i] &= mask_00; \
175 } \
176 if (flags & RANDMEMSET_MORE_FFFFFFFF) \
177 { \
178 int32_t mask_ff = ((t.w[i] << 30) & (t.w[i] << 31)) & \
179 0x80000000; \
180 randdata.w[i] |= mask_ff >> 31; \
181 } \
182 if (flags & RANDMEMSET_MORE_00000000) \
183 { \
184 int32_t mask_00 = ((t.w[i] << 30) | (t.w[i] << 31)) & \
185 0x80000000; \
186 randdata.w[i] &= mask_00 >> 31; \
187 }
188
189 PROCESS_ONE_LANE (0)
190 PROCESS_ONE_LANE (1)
191 PROCESS_ONE_LANE (2)
192 PROCESS_ONE_LANE (3)
193 #endif
194 }
195 if (is_little_endian ())
196 {
197 store_rand_128_data (buf, &randdata, aligned);
198 buf += 16;
199 }
200 else
201 {
202
203 #ifndef __has_builtin
204 #define __has_builtin(x) 0
205 #endif
206
207 #ifdef HAVE_GCC_VECTOR_EXTENSIONS
208 # if __has_builtin(__builtin_shufflevector)
209 randdata.vb =
210 __builtin_shufflevector (randdata.vb, randdata.vb,
211 3, 2, 1, 0, 7, 6 , 5, 4,
212 11, 10, 9, 8, 15, 14, 13, 12);
213 # else
214 static const uint8x16 bswap_shufflemask =
215 {
216 3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12
217 };
218 randdata.vb = __builtin_shuffle (randdata.vb, bswap_shufflemask);
219 # endif
220
221 store_rand_128_data (buf, &randdata, aligned);
222 buf += 16;
223 #else
224 uint8_t t1, t2, t3, t4;
225 #define STORE_ONE_LANE(i) \
226 t1 = randdata.b[i * 4 + 3]; \
227 t2 = randdata.b[i * 4 + 2]; \
228 t3 = randdata.b[i * 4 + 1]; \
229 t4 = randdata.b[i * 4 + 0]; \
230 *buf++ = t1; \
231 *buf++ = t2; \
232 *buf++ = t3; \
233 *buf++ = t4;
234
235 STORE_ONE_LANE (0)
236 STORE_ONE_LANE (1)
237 STORE_ONE_LANE (2)
238 STORE_ONE_LANE (3)
239 #endif
240 }
241 size -= 16;
242 }
243 i = 0;
244 while (i < size)
245 {
246 uint8_t randbyte = prng_rand_r (&local_prng) & 0xFF;
247 if (flags != 0)
248 {
249 uint8_t t = prng_rand_r (&local_prng) & 0xFF;
250 if ((flags & RANDMEMSET_MORE_FF) && (t >= 0xC0))
251 randbyte = 0xFF;
252 if ((flags & RANDMEMSET_MORE_00) && (t < 0x40))
253 randbyte = 0x00;
254 if (i % 4 == 0 && i + 4 <= size)
255 {
256 t = prng_rand_r (&local_prng) & 0xFF;
257 if ((flags & RANDMEMSET_MORE_FFFFFFFF) && (t >= 0xC0))
258 {
259 memset(&buf[i], 0xFF, 4);
260 i += 4;
261 continue;
262 }
263 if ((flags & RANDMEMSET_MORE_00000000) && (t < 0x40))
264 {
265 memset(&buf[i], 0x00, 4);
266 i += 4;
267 continue;
268 }
269 }
270 }
271 buf[i] = randbyte;
272 i++;
273 }
274 *prng = local_prng;
275 }
276
277 /*
278 * Fill memory buffer with random data. Flags argument may be used
279 * to tweak some statistics properties:
280 * RANDMEMSET_MORE_00 - set ~25% of bytes to 0x00
281 * RANDMEMSET_MORE_FF - set ~25% of bytes to 0xFF
282 * RANDMEMSET_MORE_00000000 - ~25% chance for 00000000 4-byte clusters
283 * RANDMEMSET_MORE_FFFFFFFF - ~25% chance for FFFFFFFF 4-byte clusters
284 */
prng_randmemset_r(prng_t * prng,void * voidbuf,size_t size,prng_randmemset_flags_t flags)285 void prng_randmemset_r (prng_t *prng,
286 void *voidbuf,
287 size_t size,
288 prng_randmemset_flags_t flags)
289 {
290 uint8_t *buf = (uint8_t *)voidbuf;
291 if ((uintptr_t)buf & 15)
292 {
293 /* unaligned buffer */
294 if (flags == 0)
295 randmemset_internal (prng, buf, size, 0, 0);
296 else if (flags == RANDMEMSET_MORE_00_AND_FF)
297 randmemset_internal (prng, buf, size, RANDMEMSET_MORE_00_AND_FF, 0);
298 else
299 randmemset_internal (prng, buf, size, flags, 0);
300 }
301 else
302 {
303 /* aligned buffer */
304 if (flags == 0)
305 randmemset_internal (prng, buf, size, 0, 1);
306 else if (flags == RANDMEMSET_MORE_00_AND_FF)
307 randmemset_internal (prng, buf, size, RANDMEMSET_MORE_00_AND_FF, 1);
308 else
309 randmemset_internal (prng, buf, size, flags, 1);
310 }
311 }
312