/*

 * Copyright © 2012 Siarhei Siamashka <siarhei.siamashka@gmail.com>

 *

 * Based on the public domain implementation of small noncryptographic PRNG

 * authored by Bob Jenkins: http://burtleburtle.net/bob/rand/smallprng.html

 *

 * Permission is hereby granted, free of charge, to any person obtaining a

 * copy of this software and associated documentation files (the "Software"),

 * to deal in the Software without restriction, including without limitation

 * the rights to use, copy, modify, merge, publish, distribute, sublicense,

 * and/or sell copies of the Software, and to permit persons to whom the

 * Software is furnished to do so, subject to the following conditions:

 *

 * The above copyright notice and this permission notice (including the next

 * paragraph) shall be included in all copies or substantial portions of the

 * Software.

 *

 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL

 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING

 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER

 * DEALINGS IN THE SOFTWARE.

 */

#ifndef __UTILS_PRNG_H__

#define __UTILS_PRNG_H__

/*

 * This file provides a fast SIMD-optimized noncryptographic PRNG (pseudorandom

 * number generator), with the output good enough to pass "Big Crush" tests

 * from TestU01 (http://en.wikipedia.org/wiki/TestU01).

 *

 * SIMD code uses http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html

 * which is a GCC specific extension. There is also a slower alternative

 * code path, which should work with any C compiler.

 *

 * The "prng_t" structure keeps the internal state of the random number

 * generator. It is possible to have multiple instances of the random number

 * generator active at the same time, in this case each of them needs to have

 * its own "prng_t". All the functions take a pointer to "prng_t"

 * as the first argument.

 *

 * Functions:

 *

 * ----------------------------------------------------------------------------

 * void prng_srand_r (prng_t *prng, uint32_t seed);

 *

 * Initialize the pseudorandom number generator. The sequence of preudorandom

 * numbers is deterministic and only depends on "seed". Any two generators

 * initialized with the same seed will produce exactly the same sequence.

 *

 * ----------------------------------------------------------------------------

 * uint32_t prng_rand_r (prng_t *prng);

 *

 * Generate a single uniformly distributed 32-bit pseudorandom value.

 *

 * ----------------------------------------------------------------------------

 * void prng_randmemset_r (prng_t                  *prng,

 *                         void                    *buffer,

 *                         size_t                   size,

 *                         prng_randmemset_flags_t  flags);

 *

 * Fills the memory buffer "buffer" with "size" bytes of pseudorandom data.

 * The "flags" argument may be used to tweak some statistics properties:

 *    RANDMEMSET_MORE_00 - set ~25% of bytes to 0x00

 *    RANDMEMSET_MORE_FF - set ~25% of bytes to 0xFF

 * The flags can be combined. This allows a bit better simulation of typical

 * pixel data, which normally contains a lot of fully transparent or fully

 * opaque pixels.

 */

#ifdef HAVE_CONFIG_H

#include <config.h>

#endif

#include "pixman-private.h"

/*****************************************************************************/

#ifdef HAVE_GCC_VECTOR_EXTENSIONS

typedef uint32_t uint32x4 __attribute__ ((vector_size(16)));

typedef uint8_t  uint8x16 __attribute__ ((vector_size(16)));

#endif

typedef struct

{

    uint32_t a, b, c, d;

} smallprng_t;

typedef struct

{

#ifdef HAVE_GCC_VECTOR_EXTENSIONS

    uint32x4 a, b, c, d;

#else

    smallprng_t p1, p2, p3, p4;

#endif

    smallprng_t p0;

} prng_t;

typedef union

{

    uint8_t  b[16];

    uint32_t w[4];

#ifdef HAVE_GCC_VECTOR_EXTENSIONS

    uint8x16 vb;

    uint32x4 vw;

#endif

} prng_rand_128_data_t;

/*****************************************************************************/

static force_inline uint32_t

smallprng_rand_r (smallprng_t *x)

{

    uint32_t e = x->a - ((x->b << 27) + (x->b >> (32 - 27)));

    x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17)));

    x->b = x->c + x->d;

    x->c = x->d + e;

    x->d = e + x->a;

    return x->d;

}

/* Generate 4 bytes (32-bits) of random data */

static force_inline uint32_t

prng_rand_r (prng_t *x)

{

    return smallprng_rand_r (&x->p0);

}

/* Generate 16 bytes (128-bits) of random data */

static force_inline void

prng_rand_128_r (prng_t *x, prng_rand_128_data_t *data)

{

#ifdef HAVE_GCC_VECTOR_EXTENSIONS

    uint32x4 e = x->a - ((x->b << 27) + (x->b >> (32 - 27)));

    x->a = x->b ^ ((x->c << 17) ^ (x->c >> (32 - 17)));

    x->b = x->c + x->d;

    x->c = x->d + e;

    x->d = e + x->a;

    data->vw = x->d;

#else

    data->w[0] = smallprng_rand_r (&x->p1);

    data->w[1] = smallprng_rand_r (&x->p2);

    data->w[2] = smallprng_rand_r (&x->p3);

    data->w[3] = smallprng_rand_r (&x->p4);

#endif

}

typedef enum

{

    RANDMEMSET_MORE_00        = 1, /* ~25% chance for 0x00 bytes */

    RANDMEMSET_MORE_FF        = 2, /* ~25% chance for 0xFF bytes */

    RANDMEMSET_MORE_00000000  = 4, /* ~25% chance for 0x00000000 clusters */

    RANDMEMSET_MORE_FFFFFFFF  = 8, /* ~25% chance for 0xFFFFFFFF clusters */

    RANDMEMSET_MORE_00_AND_FF = (RANDMEMSET_MORE_00 | RANDMEMSET_MORE_00000000 |

                                 RANDMEMSET_MORE_FF | RANDMEMSET_MORE_FFFFFFFF)

} prng_randmemset_flags_t;

/* Set the 32-bit seed for PRNG */

void prng_srand_r (prng_t *prng, uint32_t seed);

/* Fill memory buffer with random data */

void prng_randmemset_r (prng_t                  *prng,

                        void                    *buffer,

                        size_t                   size,

                        prng_randmemset_flags_t  flags);

#endif