[RFC PATCH v1 19/50] net/sched/sch_netem: Simplify get_crandom

[George Spelvin]

This can be done with a single 32x32-bit multiply, rather
than a 64x64 as previously written.

One conditional subtract is required to handle the 33rd bit
of value - state->last, but that's cheaper than the wider multiply
even on 64-bit platforms, and much cheaper on 32-bit.

The need for a 33rd bit to hold rho+1 is avoided by using ~rho
instead.

(Found while auditing prandom_u32() callers.)

Signed-off-by: George Spelvin <lkml@xxxxxxx>
Cc: Jamal Hadi Salim <jhs@xxxxxxxxxxxx>
Cc: Cong Wang <xiyou.wangcong@xxxxxxxxx>
Cc: Jiri Pirko <jiri@xxxxxxxxxxx>
Cc: netdev@xxxxxxxxxxxxxxx
---
 net/sched/sch_netem.c | 16 +++++++---------
 1 file changed, 7 insertions(+), 9 deletions(-)

diff --git a/net/sched/sch_netem.c b/net/sched/sch_netem.c
index 7b7503326faf5..fa41601538b21 100644
--- a/net/sched/sch_netem.c
+++ b/net/sched/sch_netem.c
@@ -180,17 +180,15 @@ static void init_crandom(struct crndstate *state, unsigned long rho)
  */
 static u32 get_crandom(struct crndstate *state)
 {
-	u64 value, rho;
-	unsigned long answer;
+	u32 value = prandom_u32(), last, rho, answer;
 
-	if (!state || state->rho == 0)	/* no correlation */
-		return prandom_u32();
+	if (!state || (rho = state->rho) == 0)	/* no correlation */
+		return value;
+	last = state->last;
+	answer = last + reciprocal_scale(value - last, ~rho);
 
-	value = prandom_u32();
-	rho = (u64)state->rho + 1;
-	answer = (value * ((1ull<<32) - rho) + state->last * rho) >> 32;
-	state->last = answer;
-	return answer;
+	/* Handle 33rd bit of difference */
+	return state->last = value >= last ? answer : answer - ~rho;
 }
 
 /* loss_4state - 4-state model loss generator
-- 
2.26.0