Refactor prng* from cpp macros into inline functions.

Remove 32-bit variant, convert prng64() to prng_lg_range(), and add
prng_range().

5 files changed, 80 insertions, 36 deletions

diff --git a/include/jemalloc/internal/ckh.h b/include/jemalloc/internal/ckh.h
index 75c1c97..45fb345 100644
--- a/include/jemalloc/internal/ckh.h
+++ b/include/jemalloc/internal/ckh.h
@@ -40,9 +40,7 @@ struct ckh_s {
 #endif
 
 	/* Used for pseudo-random number generation. */
-#define	CKH_A		1103515241
-#define	CKH_C		12347
-	uint32_t	prng_state;
+	uint64_t	prng_state;
 
 	/* Total number of items. */
 	size_t		count;
diff --git a/include/jemalloc/internal/jemalloc_internal.h.in b/include/jemalloc/internal/jemalloc_internal.h.in
index 12d51be..616eb9f 100644
--- a/include/jemalloc/internal/jemalloc_internal.h.in
+++ b/include/jemalloc/internal/jemalloc_internal.h.in
@@ -547,7 +547,7 @@ size2index_compute(size_t size)
 #if (NTBINS != 0)
 	if (size <= (ZU(1) << LG_TINY_MAXCLASS)) {
 		size_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1;
-		size_t lg_ceil = lg_floor(pow2_ceil(size));
+		size_t lg_ceil = lg_floor(pow2_ceil_zu(size));
 		return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin);
 	}
 #endif
@@ -644,7 +644,7 @@ s2u_compute(size_t size)
 #if (NTBINS > 0)
 	if (size <= (ZU(1) << LG_TINY_MAXCLASS)) {
 		size_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1;
-		size_t lg_ceil = lg_floor(pow2_ceil(size));
+		size_t lg_ceil = lg_floor(pow2_ceil_zu(size));
 		return (lg_ceil < lg_tmin ? (ZU(1) << lg_tmin) :
 		    (ZU(1) << lg_ceil));
 	}
diff --git a/include/jemalloc/internal/private_symbols.txt b/include/jemalloc/internal/private_symbols.txt
index 216367e..d910202 100644
--- a/include/jemalloc/internal/private_symbols.txt
+++ b/include/jemalloc/internal/private_symbols.txt
@@ -348,7 +348,9 @@ pages_map
 pages_purge
 pages_trim
 pages_unmap
-pow2_ceil
+pow2_ceil_u32
+pow2_ceil_u64
+pow2_ceil_zu
 prof_active_get
 prof_active_get_unlocked
 prof_active_set
diff --git a/include/jemalloc/internal/prng.h b/include/jemalloc/internal/prng.h
index 216d0ef..83c9090 100644
--- a/include/jemalloc/internal/prng.h
+++ b/include/jemalloc/internal/prng.h
@@ -18,31 +18,9 @@
  * proportional to bit position.  For example, the lowest bit has a cycle of 2,
  * the next has a cycle of 4, etc.  For this reason, we prefer to use the upper
  * bits.
- *
- * Macro parameters:
- *   uint32_t r          : Result.
- *   unsigned lg_range   : (0..32], number of least significant bits to return.
- *   uint32_t state      : Seed value.
- *   const uint32_t a, c : See above discussion.
  */
-#define	prng32(r, lg_range, state, a, c) do {				\
-	assert((lg_range) > 0);						\
-	assert((lg_range) <= 32);					\
-									\
-	r = (state * (a)) + (c);					\
-	state = r;							\
-	r >>= (32 - (lg_range));					\
-} while (false)
-
-/* Same as prng32(), but 64 bits of pseudo-randomness, using uint64_t. */
-#define	prng64(r, lg_range, state, a, c) do {				\
-	assert((lg_range) > 0);						\
-	assert((lg_range) <= 64);					\
-									\
-	r = (state * (a)) + (c);					\
-	state = r;							\
-	r >>= (64 - (lg_range));					\
-} while (false)
+#define	PRNG_A	UINT64_C(6364136223846793005)
+#define	PRNG_C	UINT64_C(1442695040888963407)
 
 #endif /* JEMALLOC_H_TYPES */
 /******************************************************************************/
@@ -56,5 +34,46 @@
 /******************************************************************************/
 #ifdef JEMALLOC_H_INLINES
 
+#ifndef JEMALLOC_ENABLE_INLINE
+uint64_t	prng_lg_range(uint64_t *state, unsigned lg_range);
+uint64_t	prng_range(uint64_t *state, uint64_t range);
+#endif
+
+#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_PRNG_C_))
+JEMALLOC_ALWAYS_INLINE uint64_t
+prng_lg_range(uint64_t *state, unsigned lg_range)
+{
+	uint64_t ret;
+
+	assert(lg_range > 0);
+	assert(lg_range <= 64);
+
+	ret = (*state * PRNG_A) + PRNG_C;
+	*state = ret;
+	ret >>= (64 - lg_range);
+
+	return (ret);
+}
+
+JEMALLOC_ALWAYS_INLINE uint64_t
+prng_range(uint64_t *state, uint64_t range)
+{
+	uint64_t ret;
+	unsigned lg_range;
+
+	assert(range > 1);
+
+	/* Compute the ceiling of lg(range). */
+	lg_range = jemalloc_ffsl(pow2_ceil_u64(range)) - 1;
+
+	/* Generate a result in [0..range) via repeated trial. */
+	do {
+		ret = prng_lg_range(state, lg_range);
+	} while (ret >= range);
+
+	return (ret);
+}
+#endif
+
 #endif /* JEMALLOC_H_INLINES */
 /******************************************************************************/
diff --git a/include/jemalloc/internal/util.h b/include/jemalloc/internal/util.h
index 0bccea2..dfe5c93 100644
--- a/include/jemalloc/internal/util.h
+++ b/include/jemalloc/internal/util.h
@@ -123,7 +123,9 @@ void	malloc_printf(const char *format, ...) JEMALLOC_FORMAT_PRINTF(1, 2);
 #ifndef JEMALLOC_ENABLE_INLINE
 int	jemalloc_ffsl(long bitmap);
 int	jemalloc_ffs(int bitmap);
-size_t	pow2_ceil(size_t x);
+uint64_t	pow2_ceil_u64(uint64_t x);
+uint32_t	pow2_ceil_u32(uint32_t x);
+size_t	pow2_ceil_zu(size_t x);
 size_t	lg_floor(size_t x);
 void	set_errno(int errnum);
 int	get_errno(void);
@@ -150,9 +152,8 @@ jemalloc_ffs(int bitmap)
 	return (JEMALLOC_INTERNAL_FFS(bitmap));
 }
 
-/* Compute the smallest power of 2 that is >= x. */
-JEMALLOC_INLINE size_t
-pow2_ceil(size_t x)
+JEMALLOC_INLINE uint64_t
+pow2_ceil_u64(uint64_t x)
 {
 
 	x--;
@@ -161,13 +162,37 @@ pow2_ceil(size_t x)
 	x |= x >> 4;
 	x |= x >> 8;
 	x |= x >> 16;
-#if (LG_SIZEOF_PTR == 3)
 	x |= x >> 32;
-#endif
 	x++;
 	return (x);
 }
 
+JEMALLOC_INLINE uint32_t
+pow2_ceil_u32(uint32_t x)
+{
+
+	x--;
+	x |= x >> 1;
+	x |= x >> 2;
+	x |= x >> 4;
+	x |= x >> 8;
+	x |= x >> 16;
+	x++;
+	return (x);
+}
+
+/* Compute the smallest power of 2 that is >= x. */
+JEMALLOC_INLINE size_t
+pow2_ceil_zu(size_t x)
+{
+
+#if (LG_SIZEOF_PTR == 3)
+	return (pow2_ceil_u64(x));
+#else
+	return (pow2_ceil_u32(x));
+#endif
+}
+
 #if (defined(__i386__) || defined(__amd64__) || defined(__x86_64__))
 JEMALLOC_INLINE size_t
 lg_floor(size_t x)