Adding upstream version 5:7.0.15.upstream/5%7.0.15upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

10 files changed, 1145 insertions, 0 deletions

diff --git a/deps/jemalloc/test/src/SFMT.c b/deps/jemalloc/test/src/SFMT.c
new file mode 100644
index 0000000..c05e218
--- /dev/null
+++ b/deps/jemalloc/test/src/SFMT.c
@@ -0,0 +1,719 @@
+/*
+ * This file derives from SFMT 1.3.3
+ * (http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html), which was
+ * released under the terms of the following license:
+ *
+ *   Copyright (c) 2006,2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima
+ *   University. All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions are
+ *   met:
+ *
+ *       * Redistributions of source code must retain the above copyright
+ *         notice, this list of conditions and the following disclaimer.
+ *       * Redistributions in binary form must reproduce the above
+ *         copyright notice, this list of conditions and the following
+ *         disclaimer in the documentation and/or other materials provided
+ *         with the distribution.
+ *       * Neither the name of the Hiroshima University nor the names of
+ *         its contributors may be used to endorse or promote products
+ *         derived from this software without specific prior written
+ *         permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+/**
+ * @file  SFMT.c
+ * @brief SIMD oriented Fast Mersenne Twister(SFMT)
+ *
+ * @author Mutsuo Saito (Hiroshima University)
+ * @author Makoto Matsumoto (Hiroshima University)
+ *
+ * Copyright (C) 2006,2007 Mutsuo Saito, Makoto Matsumoto and Hiroshima
+ * University. All rights reserved.
+ *
+ * The new BSD License is applied to this software, see LICENSE.txt
+ */
+#define SFMT_C_
+#include "test/jemalloc_test.h"
+#include "test/SFMT-params.h"
+
+#if defined(JEMALLOC_BIG_ENDIAN) && !defined(BIG_ENDIAN64)
+#define BIG_ENDIAN64 1
+#endif
+#if defined(__BIG_ENDIAN__) && !defined(__amd64) && !defined(BIG_ENDIAN64)
+#define BIG_ENDIAN64 1
+#endif
+#if defined(HAVE_ALTIVEC) && !defined(BIG_ENDIAN64)
+#define BIG_ENDIAN64 1
+#endif
+#if defined(ONLY64) && !defined(BIG_ENDIAN64)
+  #if defined(__GNUC__)
+    #error "-DONLY64 must be specified with -DBIG_ENDIAN64"
+  #endif
+#undef ONLY64
+#endif
+/*------------------------------------------------------
+  128-bit SIMD data type for Altivec, SSE2 or standard C
+  ------------------------------------------------------*/
+#if defined(HAVE_ALTIVEC)
+/** 128-bit data structure */
+union W128_T {
+    vector unsigned int s;
+    uint32_t u[4];
+};
+/** 128-bit data type */
+typedef union W128_T w128_t;
+
+#elif defined(HAVE_SSE2)
+/** 128-bit data structure */
+union W128_T {
+    __m128i si;
+    uint32_t u[4];
+};
+/** 128-bit data type */
+typedef union W128_T w128_t;
+
+#else
+
+/** 128-bit data structure */
+struct W128_T {
+    uint32_t u[4];
+};
+/** 128-bit data type */
+typedef struct W128_T w128_t;
+
+#endif
+
+struct sfmt_s {
+    /** the 128-bit internal state array */
+    w128_t sfmt[N];
+    /** index counter to the 32-bit internal state array */
+    int idx;
+    /** a flag: it is 0 if and only if the internal state is not yet
+     * initialized. */
+    int initialized;
+};
+
+/*--------------------------------------
+  FILE GLOBAL VARIABLES
+  internal state, index counter and flag
+  --------------------------------------*/
+
+/** a parity check vector which certificate the period of 2^{MEXP} */
+static uint32_t parity[4] = {PARITY1, PARITY2, PARITY3, PARITY4};
+
+/*----------------
+  STATIC FUNCTIONS
+  ----------------*/
+static inline int idxof(int i);
+#if (!defined(HAVE_ALTIVEC)) && (!defined(HAVE_SSE2))
+static inline void rshift128(w128_t *out,  w128_t const *in, int shift);
+static inline void lshift128(w128_t *out,  w128_t const *in, int shift);
+#endif
+static inline void gen_rand_all(sfmt_t *ctx);
+static inline void gen_rand_array(sfmt_t *ctx, w128_t *array, int size);
+static inline uint32_t func1(uint32_t x);
+static inline uint32_t func2(uint32_t x);
+static void period_certification(sfmt_t *ctx);
+#if defined(BIG_ENDIAN64) && !defined(ONLY64)
+static inline void swap(w128_t *array, int size);
+#endif
+
+#if defined(HAVE_ALTIVEC)
+  #include "test/SFMT-alti.h"
+#elif defined(HAVE_SSE2)
+  #include "test/SFMT-sse2.h"
+#endif
+
+/**
+ * This function simulate a 64-bit index of LITTLE ENDIAN
+ * in BIG ENDIAN machine.
+ */
+#ifdef ONLY64
+static inline int idxof(int i) {
+    return i ^ 1;
+}
+#else
+static inline int idxof(int i) {
+    return i;
+}
+#endif
+/**
+ * This function simulates SIMD 128-bit right shift by the standard C.
+ * The 128-bit integer given in in is shifted by (shift * 8) bits.
+ * This function simulates the LITTLE ENDIAN SIMD.
+ * @param out the output of this function
+ * @param in the 128-bit data to be shifted
+ * @param shift the shift value
+ */
+#if (!defined(HAVE_ALTIVEC)) && (!defined(HAVE_SSE2))
+#ifdef ONLY64
+static inline void rshift128(w128_t *out, w128_t const *in, int shift) {
+    uint64_t th, tl, oh, ol;
+
+    th = ((uint64_t)in->u[2] << 32) | ((uint64_t)in->u[3]);
+    tl = ((uint64_t)in->u[0] << 32) | ((uint64_t)in->u[1]);
+
+    oh = th >> (shift * 8);
+    ol = tl >> (shift * 8);
+    ol |= th << (64 - shift * 8);
+    out->u[0] = (uint32_t)(ol >> 32);
+    out->u[1] = (uint32_t)ol;
+    out->u[2] = (uint32_t)(oh >> 32);
+    out->u[3] = (uint32_t)oh;
+}
+#else
+static inline void rshift128(w128_t *out, w128_t const *in, int shift) {
+    uint64_t th, tl, oh, ol;
+
+    th = ((uint64_t)in->u[3] << 32) | ((uint64_t)in->u[2]);
+    tl = ((uint64_t)in->u[1] << 32) | ((uint64_t)in->u[0]);
+
+    oh = th >> (shift * 8);
+    ol = tl >> (shift * 8);
+    ol |= th << (64 - shift * 8);
+    out->u[1] = (uint32_t)(ol >> 32);
+    out->u[0] = (uint32_t)ol;
+    out->u[3] = (uint32_t)(oh >> 32);
+    out->u[2] = (uint32_t)oh;
+}
+#endif
+/**
+ * This function simulates SIMD 128-bit left shift by the standard C.
+ * The 128-bit integer given in in is shifted by (shift * 8) bits.
+ * This function simulates the LITTLE ENDIAN SIMD.
+ * @param out the output of this function
+ * @param in the 128-bit data to be shifted
+ * @param shift the shift value
+ */
+#ifdef ONLY64
+static inline void lshift128(w128_t *out, w128_t const *in, int shift) {
+    uint64_t th, tl, oh, ol;
+
+    th = ((uint64_t)in->u[2] << 32) | ((uint64_t)in->u[3]);
+    tl = ((uint64_t)in->u[0] << 32) | ((uint64_t)in->u[1]);
+
+    oh = th << (shift * 8);
+    ol = tl << (shift * 8);
+    oh |= tl >> (64 - shift * 8);
+    out->u[0] = (uint32_t)(ol >> 32);
+    out->u[1] = (uint32_t)ol;
+    out->u[2] = (uint32_t)(oh >> 32);
+    out->u[3] = (uint32_t)oh;
+}
+#else
+static inline void lshift128(w128_t *out, w128_t const *in, int shift) {
+    uint64_t th, tl, oh, ol;
+
+    th = ((uint64_t)in->u[3] << 32) | ((uint64_t)in->u[2]);
+    tl = ((uint64_t)in->u[1] << 32) | ((uint64_t)in->u[0]);
+
+    oh = th << (shift * 8);
+    ol = tl << (shift * 8);
+    oh |= tl >> (64 - shift * 8);
+    out->u[1] = (uint32_t)(ol >> 32);
+    out->u[0] = (uint32_t)ol;
+    out->u[3] = (uint32_t)(oh >> 32);
+    out->u[2] = (uint32_t)oh;
+}
+#endif
+#endif
+
+/**
+ * This function represents the recursion formula.
+ * @param r output
+ * @param a a 128-bit part of the internal state array
+ * @param b a 128-bit part of the internal state array
+ * @param c a 128-bit part of the internal state array
+ * @param d a 128-bit part of the internal state array
+ */
+#if (!defined(HAVE_ALTIVEC)) && (!defined(HAVE_SSE2))
+#ifdef ONLY64
+static inline void do_recursion(w128_t *r, w128_t *a, w128_t *b, w128_t *c,
+				w128_t *d) {
+    w128_t x;
+    w128_t y;
+
+    lshift128(&x, a, SL2);
+    rshift128(&y, c, SR2);
+    r->u[0] = a->u[0] ^ x.u[0] ^ ((b->u[0] >> SR1) & MSK2) ^ y.u[0]
+	^ (d->u[0] << SL1);
+    r->u[1] = a->u[1] ^ x.u[1] ^ ((b->u[1] >> SR1) & MSK1) ^ y.u[1]
+	^ (d->u[1] << SL1);
+    r->u[2] = a->u[2] ^ x.u[2] ^ ((b->u[2] >> SR1) & MSK4) ^ y.u[2]
+	^ (d->u[2] << SL1);
+    r->u[3] = a->u[3] ^ x.u[3] ^ ((b->u[3] >> SR1) & MSK3) ^ y.u[3]
+	^ (d->u[3] << SL1);
+}
+#else
+static inline void do_recursion(w128_t *r, w128_t *a, w128_t *b, w128_t *c,
+				w128_t *d) {
+    w128_t x;
+    w128_t y;
+
+    lshift128(&x, a, SL2);
+    rshift128(&y, c, SR2);
+    r->u[0] = a->u[0] ^ x.u[0] ^ ((b->u[0] >> SR1) & MSK1) ^ y.u[0]
+	^ (d->u[0] << SL1);
+    r->u[1] = a->u[1] ^ x.u[1] ^ ((b->u[1] >> SR1) & MSK2) ^ y.u[1]
+	^ (d->u[1] << SL1);
+    r->u[2] = a->u[2] ^ x.u[2] ^ ((b->u[2] >> SR1) & MSK3) ^ y.u[2]
+	^ (d->u[2] << SL1);
+    r->u[3] = a->u[3] ^ x.u[3] ^ ((b->u[3] >> SR1) & MSK4) ^ y.u[3]
+	^ (d->u[3] << SL1);
+}
+#endif
+#endif
+
+#if (!defined(HAVE_ALTIVEC)) && (!defined(HAVE_SSE2))
+/**
+ * This function fills the internal state array with pseudorandom
+ * integers.
+ */
+static inline void gen_rand_all(sfmt_t *ctx) {
+    int i;
+    w128_t *r1, *r2;
+
+    r1 = &ctx->sfmt[N - 2];
+    r2 = &ctx->sfmt[N - 1];
+    for (i = 0; i < N - POS1; i++) {
+	do_recursion(&ctx->sfmt[i], &ctx->sfmt[i], &ctx->sfmt[i + POS1], r1,
+	  r2);
+	r1 = r2;
+	r2 = &ctx->sfmt[i];
+    }
+    for (; i < N; i++) {
+	do_recursion(&ctx->sfmt[i], &ctx->sfmt[i], &ctx->sfmt[i + POS1 - N], r1,
+	  r2);
+	r1 = r2;
+	r2 = &ctx->sfmt[i];
+    }
+}
+
+/**
+ * This function fills the user-specified array with pseudorandom
+ * integers.
+ *
+ * @param array an 128-bit array to be filled by pseudorandom numbers.
+ * @param size number of 128-bit pseudorandom numbers to be generated.
+ */
+static inline void gen_rand_array(sfmt_t *ctx, w128_t *array, int size) {
+    int i, j;
+    w128_t *r1, *r2;
+
+    r1 = &ctx->sfmt[N - 2];
+    r2 = &ctx->sfmt[N - 1];
+    for (i = 0; i < N - POS1; i++) {
+	do_recursion(&array[i], &ctx->sfmt[i], &ctx->sfmt[i + POS1], r1, r2);
+	r1 = r2;
+	r2 = &array[i];
+    }
+    for (; i < N; i++) {
+	do_recursion(&array[i], &ctx->sfmt[i], &array[i + POS1 - N], r1, r2);
+	r1 = r2;
+	r2 = &array[i];
+    }
+    for (; i < size - N; i++) {
+	do_recursion(&array[i], &array[i - N], &array[i + POS1 - N], r1, r2);
+	r1 = r2;
+	r2 = &array[i];
+    }
+    for (j = 0; j < 2 * N - size; j++) {
+	ctx->sfmt[j] = array[j + size - N];
+    }
+    for (; i < size; i++, j++) {
+	do_recursion(&array[i], &array[i - N], &array[i + POS1 - N], r1, r2);
+	r1 = r2;
+	r2 = &array[i];
+	ctx->sfmt[j] = array[i];
+    }
+}
+#endif
+
+#if defined(BIG_ENDIAN64) && !defined(ONLY64) && !defined(HAVE_ALTIVEC)
+static inline void swap(w128_t *array, int size) {
+    int i;
+    uint32_t x, y;
+
+    for (i = 0; i < size; i++) {
+	x = array[i].u[0];
+	y = array[i].u[2];
+	array[i].u[0] = array[i].u[1];
+	array[i].u[2] = array[i].u[3];
+	array[i].u[1] = x;
+	array[i].u[3] = y;
+    }
+}
+#endif
+/**
+ * This function represents a function used in the initialization
+ * by init_by_array
+ * @param x 32-bit integer
+ * @return 32-bit integer
+ */
+static uint32_t func1(uint32_t x) {
+    return (x ^ (x >> 27)) * (uint32_t)1664525UL;
+}
+
+/**
+ * This function represents a function used in the initialization
+ * by init_by_array
+ * @param x 32-bit integer
+ * @return 32-bit integer
+ */
+static uint32_t func2(uint32_t x) {
+    return (x ^ (x >> 27)) * (uint32_t)1566083941UL;
+}
+
+/**
+ * This function certificate the period of 2^{MEXP}
+ */
+static void period_certification(sfmt_t *ctx) {
+    int inner = 0;
+    int i, j;
+    uint32_t work;
+    uint32_t *psfmt32 = &ctx->sfmt[0].u[0];
+
+    for (i = 0; i < 4; i++)
+	inner ^= psfmt32[idxof(i)] & parity[i];
+    for (i = 16; i > 0; i >>= 1)
+	inner ^= inner >> i;
+    inner &= 1;
+    /* check OK */
+    if (inner == 1) {
+	return;
+    }
+    /* check NG, and modification */
+    for (i = 0; i < 4; i++) {
+	work = 1;
+	for (j = 0; j < 32; j++) {
+	    if ((work & parity[i]) != 0) {
+		psfmt32[idxof(i)] ^= work;
+		return;
+	    }
+	    work = work << 1;
+	}
+    }
+}
+
+/*----------------
+  PUBLIC FUNCTIONS
+  ----------------*/
+/**
+ * This function returns the identification string.
+ * The string shows the word size, the Mersenne exponent,
+ * and all parameters of this generator.
+ */
+const char *get_idstring(void) {
+    return IDSTR;
+}
+
+/**
+ * This function returns the minimum size of array used for \b
+ * fill_array32() function.
+ * @return minimum size of array used for fill_array32() function.
+ */
+int get_min_array_size32(void) {
+    return N32;
+}
+
+/**
+ * This function returns the minimum size of array used for \b
+ * fill_array64() function.
+ * @return minimum size of array used for fill_array64() function.
+ */
+int get_min_array_size64(void) {
+    return N64;
+}
+
+#ifndef ONLY64
+/**
+ * This function generates and returns 32-bit pseudorandom number.
+ * init_gen_rand or init_by_array must be called before this function.
+ * @return 32-bit pseudorandom number
+ */
+uint32_t gen_rand32(sfmt_t *ctx) {
+    uint32_t r;
+    uint32_t *psfmt32 = &ctx->sfmt[0].u[0];
+
+    assert(ctx->initialized);
+    if (ctx->idx >= N32) {
+	gen_rand_all(ctx);
+	ctx->idx = 0;
+    }
+    r = psfmt32[ctx->idx++];
+    return r;
+}
+
+/* Generate a random integer in [0..limit). */
+uint32_t gen_rand32_range(sfmt_t *ctx, uint32_t limit) {
+    uint32_t ret, above;
+
+    above = 0xffffffffU - (0xffffffffU % limit);
+    while (1) {
+	ret = gen_rand32(ctx);
+	if (ret < above) {
+	    ret %= limit;
+	    break;
+	}
+    }
+    return ret;
+}
+#endif
+/**
+ * This function generates and returns 64-bit pseudorandom number.
+ * init_gen_rand or init_by_array must be called before this function.
+ * The function gen_rand64 should not be called after gen_rand32,
+ * unless an initialization is again executed.
+ * @return 64-bit pseudorandom number
+ */
+uint64_t gen_rand64(sfmt_t *ctx) {
+#if defined(BIG_ENDIAN64) && !defined(ONLY64)
+    uint32_t r1, r2;
+    uint32_t *psfmt32 = &ctx->sfmt[0].u[0];
+#else
+    uint64_t r;
+    uint64_t *psfmt64 = (uint64_t *)&ctx->sfmt[0].u[0];
+#endif
+
+    assert(ctx->initialized);
+    assert(ctx->idx % 2 == 0);
+
+    if (ctx->idx >= N32) {
+	gen_rand_all(ctx);
+	ctx->idx = 0;
+    }
+#if defined(BIG_ENDIAN64) && !defined(ONLY64)
+    r1 = psfmt32[ctx->idx];
+    r2 = psfmt32[ctx->idx + 1];
+    ctx->idx += 2;
+    return ((uint64_t)r2 << 32) | r1;
+#else
+    r = psfmt64[ctx->idx / 2];
+    ctx->idx += 2;
+    return r;
+#endif
+}
+
+/* Generate a random integer in [0..limit). */
+uint64_t gen_rand64_range(sfmt_t *ctx, uint64_t limit) {
+    uint64_t ret, above;
+
+    above = KQU(0xffffffffffffffff) - (KQU(0xffffffffffffffff) % limit);
+    while (1) {
+	ret = gen_rand64(ctx);
+	if (ret < above) {
+	    ret %= limit;
+	    break;
+	}
+    }
+    return ret;
+}
+
+#ifndef ONLY64
+/**
+ * This function generates pseudorandom 32-bit integers in the
+ * specified array[] by one call. The number of pseudorandom integers
+ * is specified by the argument size, which must be at least 624 and a
+ * multiple of four.  The generation by this function is much faster
+ * than the following gen_rand function.
+ *
+ * For initialization, init_gen_rand or init_by_array must be called
+ * before the first call of this function. This function can not be
+ * used after calling gen_rand function, without initialization.
+ *
+ * @param array an array where pseudorandom 32-bit integers are filled
+ * by this function.  The pointer to the array must be \b "aligned"
+ * (namely, must be a multiple of 16) in the SIMD version, since it
+ * refers to the address of a 128-bit integer.  In the standard C
+ * version, the pointer is arbitrary.
+ *
+ * @param size the number of 32-bit pseudorandom integers to be
+ * generated.  size must be a multiple of 4, and greater than or equal
+ * to (MEXP / 128 + 1) * 4.
+ *
+ * @note \b memalign or \b posix_memalign is available to get aligned
+ * memory. Mac OSX doesn't have these functions, but \b malloc of OSX
+ * returns the pointer to the aligned memory block.
+ */
+void fill_array32(sfmt_t *ctx, uint32_t *array, int size) {
+    assert(ctx->initialized);
+    assert(ctx->idx == N32);
+    assert(size % 4 == 0);
+    assert(size >= N32);
+
+    gen_rand_array(ctx, (w128_t *)array, size / 4);
+    ctx->idx = N32;
+}
+#endif
+
+/**
+ * This function generates pseudorandom 64-bit integers in the
+ * specified array[] by one call. The number of pseudorandom integers
+ * is specified by the argument size, which must be at least 312 and a
+ * multiple of two.  The generation by this function is much faster
+ * than the following gen_rand function.
+ *
+ * For initialization, init_gen_rand or init_by_array must be called
+ * before the first call of this function. This function can not be
+ * used after calling gen_rand function, without initialization.
+ *
+ * @param array an array where pseudorandom 64-bit integers are filled
+ * by this function.  The pointer to the array must be "aligned"
+ * (namely, must be a multiple of 16) in the SIMD version, since it
+ * refers to the address of a 128-bit integer.  In the standard C
+ * version, the pointer is arbitrary.
+ *
+ * @param size the number of 64-bit pseudorandom integers to be
+ * generated.  size must be a multiple of 2, and greater than or equal
+ * to (MEXP / 128 + 1) * 2
+ *
+ * @note \b memalign or \b posix_memalign is available to get aligned
+ * memory. Mac OSX doesn't have these functions, but \b malloc of OSX
+ * returns the pointer to the aligned memory block.
+ */
+void fill_array64(sfmt_t *ctx, uint64_t *array, int size) {
+    assert(ctx->initialized);
+    assert(ctx->idx == N32);
+    assert(size % 2 == 0);
+    assert(size >= N64);
+
+    gen_rand_array(ctx, (w128_t *)array, size / 2);
+    ctx->idx = N32;
+
+#if defined(BIG_ENDIAN64) && !defined(ONLY64)
+    swap((w128_t *)array, size /2);
+#endif
+}
+
+/**
+ * This function initializes the internal state array with a 32-bit
+ * integer seed.
+ *
+ * @param seed a 32-bit integer used as the seed.
+ */
+sfmt_t *init_gen_rand(uint32_t seed) {
+    void *p;
+    sfmt_t *ctx;
+    int i;
+    uint32_t *psfmt32;
+
+    if (posix_memalign(&p, sizeof(w128_t), sizeof(sfmt_t)) != 0) {
+	return NULL;
+    }
+    ctx = (sfmt_t *)p;
+    psfmt32 = &ctx->sfmt[0].u[0];
+
+    psfmt32[idxof(0)] = seed;
+    for (i = 1; i < N32; i++) {
+	psfmt32[idxof(i)] = 1812433253UL * (psfmt32[idxof(i - 1)]
+					    ^ (psfmt32[idxof(i - 1)] >> 30))
+	    + i;
+    }
+    ctx->idx = N32;
+    period_certification(ctx);
+    ctx->initialized = 1;
+
+    return ctx;
+}
+
+/**
+ * This function initializes the internal state array,
+ * with an array of 32-bit integers used as the seeds
+ * @param init_key the array of 32-bit integers, used as a seed.
+ * @param key_length the length of init_key.
+ */
+sfmt_t *init_by_array(uint32_t *init_key, int key_length) {
+    void *p;
+    sfmt_t *ctx;
+    int i, j, count;
+    uint32_t r;
+    int lag;
+    int mid;
+    int size = N * 4;
+    uint32_t *psfmt32;
+
+    if (posix_memalign(&p, sizeof(w128_t), sizeof(sfmt_t)) != 0) {
+	return NULL;
+    }
+    ctx = (sfmt_t *)p;
+    psfmt32 = &ctx->sfmt[0].u[0];
+
+    if (size >= 623) {
+	lag = 11;
+    } else if (size >= 68) {
+	lag = 7;
+    } else if (size >= 39) {
+	lag = 5;
+    } else {
+	lag = 3;
+    }
+    mid = (size - lag) / 2;
+
+    memset(ctx->sfmt, 0x8b, sizeof(ctx->sfmt));
+    if (key_length + 1 > N32) {
+	count = key_length + 1;
+    } else {
+	count = N32;
+    }
+    r = func1(psfmt32[idxof(0)] ^ psfmt32[idxof(mid)]
+	      ^ psfmt32[idxof(N32 - 1)]);
+    psfmt32[idxof(mid)] += r;
+    r += key_length;
+    psfmt32[idxof(mid + lag)] += r;
+    psfmt32[idxof(0)] = r;
+
+    count--;
+    for (i = 1, j = 0; (j < count) && (j < key_length); j++) {
+	r = func1(psfmt32[idxof(i)] ^ psfmt32[idxof((i + mid) % N32)]
+		  ^ psfmt32[idxof((i + N32 - 1) % N32)]);
+	psfmt32[idxof((i + mid) % N32)] += r;
+	r += init_key[j] + i;
+	psfmt32[idxof((i + mid + lag) % N32)] += r;
+	psfmt32[idxof(i)] = r;
+	i = (i + 1) % N32;
+    }
+    for (; j < count; j++) {
+	r = func1(psfmt32[idxof(i)] ^ psfmt32[idxof((i + mid) % N32)]
+		  ^ psfmt32[idxof((i + N32 - 1) % N32)]);
+	psfmt32[idxof((i + mid) % N32)] += r;
+	r += i;
+	psfmt32[idxof((i + mid + lag) % N32)] += r;
+	psfmt32[idxof(i)] = r;
+	i = (i + 1) % N32;
+    }
+    for (j = 0; j < N32; j++) {
+	r = func2(psfmt32[idxof(i)] + psfmt32[idxof((i + mid) % N32)]
+		  + psfmt32[idxof((i + N32 - 1) % N32)]);
+	psfmt32[idxof((i + mid) % N32)] ^= r;
+	r -= i;
+	psfmt32[idxof((i + mid + lag) % N32)] ^= r;
+	psfmt32[idxof(i)] = r;
+	i = (i + 1) % N32;
+    }
+
+    ctx->idx = N32;
+    period_certification(ctx);
+    ctx->initialized = 1;
+
+    return ctx;
+}
+
+void fini_gen_rand(sfmt_t *ctx) {
+    assert(ctx != NULL);
+
+    ctx->initialized = 0;
+    free(ctx);
+}
diff --git a/deps/jemalloc/test/src/btalloc.c b/deps/jemalloc/test/src/btalloc.c
new file mode 100644
index 0000000..d570952
--- /dev/null
+++ b/deps/jemalloc/test/src/btalloc.c
@@ -0,0 +1,6 @@
+#include "test/jemalloc_test.h"
+
+void *
+btalloc(size_t size, unsigned bits) {
+	return btalloc_0(size, bits);
+}
diff --git a/deps/jemalloc/test/src/btalloc_0.c b/deps/jemalloc/test/src/btalloc_0.c
new file mode 100644
index 0000000..77d8904
--- /dev/null
+++ b/deps/jemalloc/test/src/btalloc_0.c
@@ -0,0 +1,3 @@
+#include "test/jemalloc_test.h"
+
+btalloc_n_gen(0)
diff --git a/deps/jemalloc/test/src/btalloc_1.c b/deps/jemalloc/test/src/btalloc_1.c
new file mode 100644
index 0000000..4c126c3
--- /dev/null
+++ b/deps/jemalloc/test/src/btalloc_1.c
@@ -0,0 +1,3 @@
+#include "test/jemalloc_test.h"
+
+btalloc_n_gen(1)
diff --git a/deps/jemalloc/test/src/math.c b/deps/jemalloc/test/src/math.c
new file mode 100644
index 0000000..1758c67
--- /dev/null
+++ b/deps/jemalloc/test/src/math.c
@@ -0,0 +1,2 @@
+#define MATH_C_
+#include "test/jemalloc_test.h"
diff --git a/deps/jemalloc/test/src/mq.c b/deps/jemalloc/test/src/mq.c
new file mode 100644
index 0000000..9b5f672
--- /dev/null
+++ b/deps/jemalloc/test/src/mq.c
@@ -0,0 +1,27 @@
+#include "test/jemalloc_test.h"
+
+/*
+ * Sleep for approximately ns nanoseconds.  No lower *nor* upper bound on sleep
+ * time is guaranteed.
+ */
+void
+mq_nanosleep(unsigned ns) {
+	assert(ns <= 1000*1000*1000);
+
+#ifdef _WIN32
+	Sleep(ns / 1000);
+#else
+	{
+		struct timespec timeout;
+
+		if (ns < 1000*1000*1000) {
+			timeout.tv_sec = 0;
+			timeout.tv_nsec = ns;
+		} else {
+			timeout.tv_sec = 1;
+			timeout.tv_nsec = 0;
+		}
+		nanosleep(&timeout, NULL);
+	}
+#endif
+}
diff --git a/deps/jemalloc/test/src/mtx.c b/deps/jemalloc/test/src/mtx.c
new file mode 100644
index 0000000..d9ce375
--- /dev/null
+++ b/deps/jemalloc/test/src/mtx.c
@@ -0,0 +1,61 @@
+#include "test/jemalloc_test.h"
+
+#ifndef _CRT_SPINCOUNT
+#define _CRT_SPINCOUNT 4000
+#endif
+
+bool
+mtx_init(mtx_t *mtx) {
+#ifdef _WIN32
+	if (!InitializeCriticalSectionAndSpinCount(&mtx->lock,
+	    _CRT_SPINCOUNT)) {
+		return true;
+	}
+#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
+	mtx->lock = OS_UNFAIR_LOCK_INIT;
+#else
+	pthread_mutexattr_t attr;
+
+	if (pthread_mutexattr_init(&attr) != 0) {
+		return true;
+	}
+	pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_DEFAULT);
+	if (pthread_mutex_init(&mtx->lock, &attr) != 0) {
+		pthread_mutexattr_destroy(&attr);
+		return true;
+	}
+	pthread_mutexattr_destroy(&attr);
+#endif
+	return false;
+}
+
+void
+mtx_fini(mtx_t *mtx) {
+#ifdef _WIN32
+#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
+#else
+	pthread_mutex_destroy(&mtx->lock);
+#endif
+}
+
+void
+mtx_lock(mtx_t *mtx) {
+#ifdef _WIN32
+	EnterCriticalSection(&mtx->lock);
+#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
+	os_unfair_lock_lock(&mtx->lock);
+#else
+	pthread_mutex_lock(&mtx->lock);
+#endif
+}
+
+void
+mtx_unlock(mtx_t *mtx) {
+#ifdef _WIN32
+	LeaveCriticalSection(&mtx->lock);
+#elif (defined(JEMALLOC_OS_UNFAIR_LOCK))
+	os_unfair_lock_unlock(&mtx->lock);
+#else
+	pthread_mutex_unlock(&mtx->lock);
+#endif
+}
diff --git a/deps/jemalloc/test/src/test.c b/deps/jemalloc/test/src/test.c
new file mode 100644
index 0000000..f97ce4d
--- /dev/null
+++ b/deps/jemalloc/test/src/test.c
@@ -0,0 +1,234 @@
+#include "test/jemalloc_test.h"
+
+/* Test status state. */
+
+static unsigned		test_count = 0;
+static test_status_t	test_counts[test_status_count] = {0, 0, 0};
+static test_status_t	test_status = test_status_pass;
+static const char *	test_name = "";
+
+/* Reentrancy testing helpers. */
+
+#define NUM_REENTRANT_ALLOCS 20
+typedef enum {
+	non_reentrant = 0,
+	libc_reentrant = 1,
+	arena_new_reentrant = 2
+} reentrancy_t;
+static reentrancy_t reentrancy;
+
+static bool libc_hook_ran = false;
+static bool arena_new_hook_ran = false;
+
+static const char *
+reentrancy_t_str(reentrancy_t r) {
+	switch (r) {
+	case non_reentrant:
+		return "non-reentrant";
+	case libc_reentrant:
+		return "libc-reentrant";
+	case arena_new_reentrant:
+		return "arena_new-reentrant";
+	default:
+		unreachable();
+	}
+}
+
+static void
+do_hook(bool *hook_ran, void (**hook)()) {
+	*hook_ran = true;
+	*hook = NULL;
+
+	size_t alloc_size = 1;
+	for (int i = 0; i < NUM_REENTRANT_ALLOCS; i++) {
+		free(malloc(alloc_size));
+		alloc_size *= 2;
+	}
+}
+
+static void
+libc_reentrancy_hook() {
+	do_hook(&libc_hook_ran, &test_hooks_libc_hook);
+}
+
+static void
+arena_new_reentrancy_hook() {
+	do_hook(&arena_new_hook_ran, &test_hooks_arena_new_hook);
+}
+
+/* Actual test infrastructure. */
+bool
+test_is_reentrant() {
+	return reentrancy != non_reentrant;
+}
+
+JEMALLOC_FORMAT_PRINTF(1, 2)
+void
+test_skip(const char *format, ...) {
+	va_list ap;
+
+	va_start(ap, format);
+	malloc_vcprintf(NULL, NULL, format, ap);
+	va_end(ap);
+	malloc_printf("\n");
+	test_status = test_status_skip;
+}
+
+JEMALLOC_FORMAT_PRINTF(1, 2)
+void
+test_fail(const char *format, ...) {
+	va_list ap;
+
+	va_start(ap, format);
+	malloc_vcprintf(NULL, NULL, format, ap);
+	va_end(ap);
+	malloc_printf("\n");
+	test_status = test_status_fail;
+}
+
+static const char *
+test_status_string(test_status_t test_status) {
+	switch (test_status) {
+	case test_status_pass: return "pass";
+	case test_status_skip: return "skip";
+	case test_status_fail: return "fail";
+	default: not_reached();
+	}
+}
+
+void
+p_test_init(const char *name) {
+	test_count++;
+	test_status = test_status_pass;
+	test_name = name;
+}
+
+void
+p_test_fini(void) {
+	test_counts[test_status]++;
+	malloc_printf("%s (%s): %s\n", test_name, reentrancy_t_str(reentrancy),
+	    test_status_string(test_status));
+}
+
+static void
+check_global_slow(test_status_t *status) {
+#ifdef JEMALLOC_UNIT_TEST
+	/*
+	 * This check needs to peek into tsd internals, which is why it's only
+	 * exposed in unit tests.
+	 */
+	if (tsd_global_slow()) {
+		malloc_printf("Testing increased global slow count\n");
+		*status = test_status_fail;
+	}
+#endif
+}
+
+static test_status_t
+p_test_impl(bool do_malloc_init, bool do_reentrant, test_t *t, va_list ap) {
+	test_status_t ret;
+
+	if (do_malloc_init) {
+		/*
+		 * Make sure initialization occurs prior to running tests.
+		 * Tests are special because they may use internal facilities
+		 * prior to triggering initialization as a side effect of
+		 * calling into the public API.
+		 */
+		if (nallocx(1, 0) == 0) {
+			malloc_printf("Initialization error");
+			return test_status_fail;
+		}
+	}
+
+	ret = test_status_pass;
+	for (; t != NULL; t = va_arg(ap, test_t *)) {
+		/* Non-reentrant run. */
+		reentrancy = non_reentrant;
+		test_hooks_arena_new_hook = test_hooks_libc_hook = NULL;
+		t();
+		if (test_status > ret) {
+			ret = test_status;
+		}
+		check_global_slow(&ret);
+		/* Reentrant run. */
+		if (do_reentrant) {
+			reentrancy = libc_reentrant;
+			test_hooks_arena_new_hook = NULL;
+			test_hooks_libc_hook = &libc_reentrancy_hook;
+			t();
+			if (test_status > ret) {
+				ret = test_status;
+			}
+			check_global_slow(&ret);
+
+			reentrancy = arena_new_reentrant;
+			test_hooks_libc_hook = NULL;
+			test_hooks_arena_new_hook = &arena_new_reentrancy_hook;
+			t();
+			if (test_status > ret) {
+				ret = test_status;
+			}
+			check_global_slow(&ret);
+		}
+	}
+
+	malloc_printf("--- %s: %u/%u, %s: %u/%u, %s: %u/%u ---\n",
+	    test_status_string(test_status_pass),
+	    test_counts[test_status_pass], test_count,
+	    test_status_string(test_status_skip),
+	    test_counts[test_status_skip], test_count,
+	    test_status_string(test_status_fail),
+	    test_counts[test_status_fail], test_count);
+
+	return ret;
+}
+
+test_status_t
+p_test(test_t *t, ...) {
+	test_status_t ret;
+	va_list ap;
+
+	ret = test_status_pass;
+	va_start(ap, t);
+	ret = p_test_impl(true, true, t, ap);
+	va_end(ap);
+
+	return ret;
+}
+
+test_status_t
+p_test_no_reentrancy(test_t *t, ...) {
+	test_status_t ret;
+	va_list ap;
+
+	ret = test_status_pass;
+	va_start(ap, t);
+	ret = p_test_impl(true, false, t, ap);
+	va_end(ap);
+
+	return ret;
+}
+
+test_status_t
+p_test_no_malloc_init(test_t *t, ...) {
+	test_status_t ret;
+	va_list ap;
+
+	ret = test_status_pass;
+	va_start(ap, t);
+	/*
+	 * We also omit reentrancy from bootstrapping tests, since we don't
+	 * (yet) care about general reentrancy during bootstrapping.
+	 */
+	ret = p_test_impl(false, false, t, ap);
+	va_end(ap);
+
+	return ret;
+}
+
+void
+p_test_fail(const char *prefix, const char *message) {
+	malloc_cprintf(NULL, NULL, "%s%s\n", prefix, message);
+	test_status = test_status_fail;
+}
diff --git a/deps/jemalloc/test/src/thd.c b/deps/jemalloc/test/src/thd.c
new file mode 100644
index 0000000..9a15eab
--- /dev/null
+++ b/deps/jemalloc/test/src/thd.c
@@ -0,0 +1,34 @@
+#include "test/jemalloc_test.h"
+
+#ifdef _WIN32
+void
+thd_create(thd_t *thd, void *(*proc)(void *), void *arg) {
+	LPTHREAD_START_ROUTINE routine = (LPTHREAD_START_ROUTINE)proc;
+	*thd = CreateThread(NULL, 0, routine, arg, 0, NULL);
+	if (*thd == NULL) {
+		test_fail("Error in CreateThread()\n");
+	}
+}
+
+void
+thd_join(thd_t thd, void **ret) {
+	if (WaitForSingleObject(thd, INFINITE) == WAIT_OBJECT_0 && ret) {
+		DWORD exit_code;
+		GetExitCodeThread(thd, (LPDWORD) &exit_code);
+		*ret = (void *)(uintptr_t)exit_code;
+	}
+}
+
+#else
+void
+thd_create(thd_t *thd, void *(*proc)(void *), void *arg) {
+	if (pthread_create(thd, NULL, proc, arg) != 0) {
+		test_fail("Error in pthread_create()\n");
+	}
+}
+
+void
+thd_join(thd_t thd, void **ret) {
+	pthread_join(thd, ret);
+}
+#endif
diff --git a/deps/jemalloc/test/src/timer.c b/deps/jemalloc/test/src/timer.c
new file mode 100644
index 0000000..c451c63
--- /dev/null
+++ b/deps/jemalloc/test/src/timer.c
@@ -0,0 +1,56 @@
+#include "test/jemalloc_test.h"
+
+void
+timer_start(timedelta_t *timer) {
+	nstime_init(&timer->t0, 0);
+	nstime_update(&timer->t0);
+}
+
+void
+timer_stop(timedelta_t *timer) {
+	nstime_copy(&timer->t1, &timer->t0);
+	nstime_update(&timer->t1);
+}
+
+uint64_t
+timer_usec(const timedelta_t *timer) {
+	nstime_t delta;
+
+	nstime_copy(&delta, &timer->t1);
+	nstime_subtract(&delta, &timer->t0);
+	return nstime_ns(&delta) / 1000;
+}
+
+void
+timer_ratio(timedelta_t *a, timedelta_t *b, char *buf, size_t buflen) {
+	uint64_t t0 = timer_usec(a);
+	uint64_t t1 = timer_usec(b);
+	uint64_t mult;
+	size_t i = 0;
+	size_t j, n;
+
+	/* Whole. */
+	n = malloc_snprintf(&buf[i], buflen-i, "%"FMTu64, t0 / t1);
+	i += n;
+	if (i >= buflen) {
+		return;
+	}
+	mult = 1;
+	for (j = 0; j < n; j++) {
+		mult *= 10;
+	}
+
+	/* Decimal. */
+	n = malloc_snprintf(&buf[i], buflen-i, ".");
+	i += n;
+
+	/* Fraction. */
+	while (i < buflen-1) {
+		uint64_t round = (i+1 == buflen-1 && ((t0 * mult * 10 / t1) % 10
+		    >= 5)) ? 1 : 0;
+		n = malloc_snprintf(&buf[i], buflen-i,
+		    "%"FMTu64, (t0 * mult / t1) % 10 + round);
+		i += n;
+		mult *= 10;
+	}
+}