11176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/* 21176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Copyright © 2012 Siarhei Siamashka <siarhei.siamashka@gmail.com> 31176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 41176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Based on the public domain implementation of small noncryptographic PRNG 51176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * authored by Bob Jenkins: http://burtleburtle.net/bob/rand/smallprng.html 61176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 71176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Permission is hereby granted, free of charge, to any person obtaining a 81176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * copy of this software and associated documentation files (the "Software"), 91176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * to deal in the Software without restriction, including without limitation 101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * the rights to use, copy, modify, merge, publish, distribute, sublicense, 111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * and/or sell copies of the Software, and to permit persons to whom the 121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Software is furnished to do so, subject to the following conditions: 131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * The above copyright notice and this permission notice (including the next 151176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * paragraph) shall be included in all copies or substantial portions of the 161176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Software. 171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * DEALINGS IN THE SOFTWARE. 251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck */ 261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 271176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#ifndef __UTILS_PRNG_H__ 281176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#define __UTILS_PRNG_H__ 291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/* 311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * This file provides a fast SIMD-optimized noncryptographic PRNG (pseudorandom 321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * number generator), with the output good enough to pass "Big Crush" tests 331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * from TestU01 (http://en.wikipedia.org/wiki/TestU01). 341176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 351176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * SIMD code uses http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html 361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * which is a GCC specific extension. There is also a slower alternative 371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * code path, which should work with any C compiler. 381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * The "prng_t" structure keeps the internal state of the random number 401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * generator. It is possible to have multiple instances of the random number 411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * generator active at the same time, in this case each of them needs to have 421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * its own "prng_t". All the functions take a pointer to "prng_t" 431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * as the first argument. 441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Functions: 461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * ---------------------------------------------------------------------------- 481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * void prng_srand_r (prng_t *prng, uint32_t seed); 491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Initialize the pseudorandom number generator. The sequence of preudorandom 511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * numbers is deterministic and only depends on "seed". Any two generators 521176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * initialized with the same seed will produce exactly the same sequence. 531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * ---------------------------------------------------------------------------- 551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * uint32_t prng_rand_r (prng_t *prng); 561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Generate a single uniformly distributed 32-bit pseudorandom value. 581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * ---------------------------------------------------------------------------- 601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * void prng_randmemset_r (prng_t *prng, 611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * void *buffer, 621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * size_t size, 631176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * prng_randmemset_flags_t flags); 641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * 651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * Fills the memory buffer "buffer" with "size" bytes of pseudorandom data. 661176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * The "flags" argument may be used to tweak some statistics properties: 671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * RANDMEMSET_MORE_00 - set ~25% of bytes to 0x00 681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * RANDMEMSET_MORE_FF - set ~25% of bytes to 0xFF 691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * The flags can be combined. This allows a bit better simulation of typical 701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * pixel data, which normally contains a lot of fully transparent or fully 711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck * opaque pixels. 721176bdada62cabc6ec4b0308a930e83b679d5d36John Reck */ 731176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 741176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#ifdef HAVE_CONFIG_H 751176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include <config.h> 761176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#endif 771176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 781176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#include "pixman-private.h" 791176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 801176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/*****************************************************************************/ 811176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 821176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 7)) 831176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#define GCC_VECTOR_EXTENSIONS_SUPPORTED 841176bdada62cabc6ec4b0308a930e83b679d5d36John Recktypedef uint32_t uint32x4 __attribute__ ((vector_size(16))); 851176bdada62cabc6ec4b0308a930e83b679d5d36John Recktypedef uint8_t uint8x16 __attribute__ ((vector_size(16))); 861176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#endif 871176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 881176bdada62cabc6ec4b0308a930e83b679d5d36John Recktypedef struct 891176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 901176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint32_t a, b, c, d; 911176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} smallprng_t; 921176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 931176bdada62cabc6ec4b0308a930e83b679d5d36John Recktypedef struct 941176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 951176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED 961176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint32x4 a, b, c, d; 971176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#else 981176bdada62cabc6ec4b0308a930e83b679d5d36John Reck smallprng_t p1, p2, p3, p4; 991176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#endif 1001176bdada62cabc6ec4b0308a930e83b679d5d36John Reck smallprng_t p0; 1011176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} prng_t; 1021176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1031176bdada62cabc6ec4b0308a930e83b679d5d36John Recktypedef union 1041176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 1051176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint8_t b[16]; 1061176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint32_t w[4]; 1071176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED 1081176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint8x16 vb; 1091176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint32x4 vw; 1101176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#endif 1111176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} prng_rand_128_data_t; 1121176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1131176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/*****************************************************************************/ 1141176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1151176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic force_inline uint32_t 1161176bdada62cabc6ec4b0308a930e83b679d5d36John Recksmallprng_rand_r (smallprng_t *x) 1171176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 1181176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint32_t e = x->a - ((x->b << 27) + (x->b >> (32 - 27))); 1191176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17))); 1201176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->b = x->c + x->d; 1211176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->c = x->d + e; 1221176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->d = e + x->a; 1231176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return x->d; 1241176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1251176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1261176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/* Generate 4 bytes (32-bits) of random data */ 1271176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic force_inline uint32_t 1281176bdada62cabc6ec4b0308a930e83b679d5d36John Reckprng_rand_r (prng_t *x) 1291176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 1301176bdada62cabc6ec4b0308a930e83b679d5d36John Reck return smallprng_rand_r (&x->p0); 1311176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1321176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1331176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/* Generate 16 bytes (128-bits) of random data */ 1341176bdada62cabc6ec4b0308a930e83b679d5d36John Reckstatic force_inline void 1351176bdada62cabc6ec4b0308a930e83b679d5d36John Reckprng_rand_128_r (prng_t *x, prng_rand_128_data_t *data) 1361176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 1371176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#ifdef GCC_VECTOR_EXTENSIONS_SUPPORTED 1381176bdada62cabc6ec4b0308a930e83b679d5d36John Reck uint32x4 e = x->a - ((x->b << 27) + (x->b >> (32 - 27))); 1391176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17))); 1401176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->b = x->c + x->d; 1411176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->c = x->d + e; 1421176bdada62cabc6ec4b0308a930e83b679d5d36John Reck x->d = e + x->a; 1431176bdada62cabc6ec4b0308a930e83b679d5d36John Reck data->vw = x->d; 1441176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#else 1451176bdada62cabc6ec4b0308a930e83b679d5d36John Reck data->w[0] = smallprng_rand_r (&x->p1); 1461176bdada62cabc6ec4b0308a930e83b679d5d36John Reck data->w[1] = smallprng_rand_r (&x->p2); 1471176bdada62cabc6ec4b0308a930e83b679d5d36John Reck data->w[2] = smallprng_rand_r (&x->p3); 1481176bdada62cabc6ec4b0308a930e83b679d5d36John Reck data->w[3] = smallprng_rand_r (&x->p4); 1491176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#endif 1501176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} 1511176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1521176bdada62cabc6ec4b0308a930e83b679d5d36John Recktypedef enum 1531176bdada62cabc6ec4b0308a930e83b679d5d36John Reck{ 1541176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RANDMEMSET_MORE_00 = 1, /* ~25% chance for 0x00 bytes */ 1551176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RANDMEMSET_MORE_FF = 2, /* ~25% chance for 0xFF bytes */ 1561176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RANDMEMSET_MORE_00000000 = 4, /* ~25% chance for 0x00000000 clusters */ 1571176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RANDMEMSET_MORE_FFFFFFFF = 8, /* ~25% chance for 0xFFFFFFFF clusters */ 1581176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RANDMEMSET_MORE_00_AND_FF = (RANDMEMSET_MORE_00 | RANDMEMSET_MORE_00000000 | 1591176bdada62cabc6ec4b0308a930e83b679d5d36John Reck RANDMEMSET_MORE_FF | RANDMEMSET_MORE_FFFFFFFF) 1601176bdada62cabc6ec4b0308a930e83b679d5d36John Reck} prng_randmemset_flags_t; 1611176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1621176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/* Set the 32-bit seed for PRNG */ 1631176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid prng_srand_r (prng_t *prng, uint32_t seed); 1641176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1651176bdada62cabc6ec4b0308a930e83b679d5d36John Reck/* Fill memory buffer with random data */ 1661176bdada62cabc6ec4b0308a930e83b679d5d36John Reckvoid prng_randmemset_r (prng_t *prng, 1671176bdada62cabc6ec4b0308a930e83b679d5d36John Reck void *buffer, 1681176bdada62cabc6ec4b0308a930e83b679d5d36John Reck size_t size, 1691176bdada62cabc6ec4b0308a930e83b679d5d36John Reck prng_randmemset_flags_t flags); 1701176bdada62cabc6ec4b0308a930e83b679d5d36John Reck 1711176bdada62cabc6ec4b0308a930e83b679d5d36John Reck#endif 172