❦ 10 décembre 2014 06:00 +0100, Willy Tarreau <[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:
>
> Good catch, but I'd rather simply divide by ((u64)RAND_MAX + 1) and
> let gcc notice it's a power of two and implement a hard-coded constant
> shift. There are a lot of things gcc doesn't figure well, but divides
> and multiplies are generally performed optimally :-)
So, here is an updated patch:
>From ec4e0abebcb2258cba550820b316d30137310a52 Mon Sep 17 00:00:00 2001
From: Vincent Bernat <[email protected]>
Date: Wed, 10 Dec 2014 10:31:37 +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 dividing by RAND_MAX+1. gcc is smart enough to turn that
into a shift:
0x000000000046ecc8 <+40>: shr $0x1f,%rax
---
src/sample.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/sample.c b/src/sample.c
index 0ffc76daf3a9..00345a8940eb 100644
--- a/src/sample.c
+++ b/src/sample.c
@@ -1824,7 +1824,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) / ((u64)RAND_MAX+1);
smp->type = SMP_T_UINT;
smp->flags |= SMP_F_VOL_TEST | SMP_F_MAY_CHANGE;
--
2.1.3
--
10.0 times 0.1 is hardly ever 1.0.
- The Elements of Programming Style (Kernighan & Plauger)
