git: 5d493a9556ff - stable/13 - LinuxKPI: implement get_random_u32_inclusive()

From: Bjoern A. Zeeb <bz_at_FreeBSD.org>
Date: Wed, 29 Nov 2023 16:37:52 UTC
The branch stable/13 has been updated by bz:

URL: https://cgit.FreeBSD.org/src/commit/?id=5d493a9556ff9c60519838f7a27df60bf695187a

commit 5d493a9556ff9c60519838f7a27df60bf695187a
Author:     Bjoern A. Zeeb <bz@FreeBSD.org>
AuthorDate: 2023-05-16 21:03:30 +0000
Commit:     Bjoern A. Zeeb <bz@FreeBSD.org>
CommitDate: 2023-11-29 16:36:03 +0000

    LinuxKPI: implement get_random_u32_inclusive()
    
    Implementation of get_random_u32_inclusive().
    This is needed by an update for wireless drivers.
    
    Sponsored by:   The FreeBSD Foundation
    
    (cherry picked from commit 1dcd1a539275fe69173bfc4dfc32c963fc7dcdbe)
---
 sys/compat/linuxkpi/common/include/linux/random.h | 30 +++++++++++++++++++++--
 1 file changed, 28 insertions(+), 2 deletions(-)

diff --git a/sys/compat/linuxkpi/common/include/linux/random.h b/sys/compat/linuxkpi/common/include/linux/random.h
index 57310377c0c9..5335cca8251c 100644
--- a/sys/compat/linuxkpi/common/include/linux/random.h
+++ b/sys/compat/linuxkpi/common/include/linux/random.h
@@ -4,6 +4,10 @@
  * Copyright (c) 2010 Panasas, Inc.
  * Copyright (c) 2013-2016 Mellanox Technologies, Ltd.
  * All rights reserved.
+ * Copyright 2023 The FreeBSD Foundation
+ *
+ * Portions of this software was developed by Björn Zeeb
+ * under sponsorship from the FreeBSD Foundation.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -34,8 +38,6 @@
 #include <sys/random.h>
 #include <sys/libkern.h>
 
-#define	get_random_u32() get_random_int()
-
 static inline void
 get_random_bytes(void *buf, int nbytes)
 {
@@ -52,6 +54,30 @@ get_random_int(void)
 	return (val);
 }
 
+#define	get_random_u32() get_random_int()
+
+/*
+ * See "Fast Random Integer Generation in an Interval" by Daniel Lemire
+ * [https://arxiv.org/pdf/1805.10941.pdf] for implementation insights.
+ */
+static inline uint32_t
+get_random_u32_inclusive(uint32_t floor, uint32_t ceil)
+{
+	uint64_t x;
+	uint32_t t, v;
+
+	MPASS(ceil >= floor);
+
+	v = get_random_u32();
+	t = ceil - floor + 1;
+	x = (uint64_t)t * v;
+	while (x < t)
+		x = (uint64_t)t * get_random_u32();
+	v = x >> 32;
+
+	return (floor + v);
+}
+
 static inline u_long
 get_random_long(void)
 {