❦ 8 décembre 2014 23:20 +0100, Vincent Bernat <[email protected]> :
> Assuming that RAND_MAX is always a power of two - 1, 32 could be
> replaced by a precomputed value of ffs(RAND_MAX+1)-1.
ebtree defines a fls64() function which seems best suited (RAND_MAX+1
could overflow). Here is a proposed patch for this:
>From 960ad6d49541ffe81c9048398201d307fd2c20cb Mon Sep 17 00:00:00 2001
From: Vincent Bernat <[email protected]>
Date: Mon, 8 Dec 2014 23:37:40 +0100
Subject: [PATCH] BUG/MEDIUM: sample: fix random number upper-bound
random() will generate a number between 0 and RAND_MAX. POSIX mandates
RAND_MAX to be at least 32767. GNU libc uses (1<<31 - 1) as
RAND_MAX.
In smp_fetch_rand(), a reduction is done with a multiply and shift to
avoid skewing the results. However, the shift was always 32 and hence
the numbers were not distributed uniformly in the specified range. We
fix that by computing the highest bit of RAND_MAX and use it to shift.
---
src/sample.c | 6 +++++-
1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/src/sample.c b/src/sample.c
index 0ffc76daf3a9..569f7b387c50 100644
--- a/src/sample.c
+++ b/src/sample.c
@@ -1813,6 +1813,7 @@ smp_fetch_proc(struct proxy *px, struct session *s, void *l7, unsigned int opt,
return 1;
}
+static int random_bits;
/* generate a random 32-bit integer for whatever purpose, with an optional
* range specified in argument.
*/
@@ -1824,7 +1825,7 @@ smp_fetch_rand(struct proxy *px, struct session *s, void *l7, unsigned int opt,
/* reduce if needed. Don't do a modulo, use all bits! */
if (args && args[0].type == ARGT_UINT)
- smp->data.uint = ((uint64_t)smp->data.uint * args[0].data.uint) >> 32;
+ smp->data.uint = ((uint64_t)smp->data.uint * args[0].data.uint) >> random_bits;
smp->type = SMP_T_UINT;
smp->flags |= SMP_F_VOL_TEST | SMP_F_MAY_CHANGE;
@@ -1883,4 +1884,7 @@ static void __sample_init(void)
/* register sample fetch and format conversion keywords */
sample_register_fetches(&smp_kws);
sample_register_convs(&sample_conv_kws);
+
+ /* Setup the number of random bits we can expect with random() */
+ random_bits = fls64(RAND_MAX);
}
--
2.1.3
--
Let the machine do the dirty work.
- The Elements of Programming Style (Kernighan & Plauger)
