random: use rejection sampling for uniform bounded random integers

[sfrench/cifs-2.6.git] / include / linux / random.h

diff --git a/include/linux/random.h b/include/linux/random.h
index 147a5e0d0b8ed244bf839c5ccfadb0b9352c8be7..3a82c0a8bc465f7a5a0f32e14a98d9b51ee8bd32 100644 (file)
--- a/include/linux/random.h
+++ b/include/linux/random.h
@@ -51,6 +51,46 @@ static inline unsigned long get_random_long(void)
 #endif
 }
 
+u32 __get_random_u32_below(u32 ceil);
+
+/*
+ * Returns a random integer in the interval [0, ceil), with uniform
+ * distribution, suitable for all uses. Fastest when ceil is a constant, but
+ * still fast for variable ceil as well.
+ */
+static inline u32 get_random_u32_below(u32 ceil)
+{
+       if (!__builtin_constant_p(ceil))
+               return __get_random_u32_below(ceil);
+
+       /*
+        * For the fast path, below, all operations on ceil are precomputed by
+        * the compiler, so this incurs no overhead for checking pow2, doing
+        * divisions, or branching based on integer size. The resultant
+        * algorithm does traditional reciprocal multiplication (typically
+        * optimized by the compiler into shifts and adds), rejecting samples
+        * whose lower half would indicate a range indivisible by ceil.
+        */
+       BUILD_BUG_ON_MSG(!ceil, "get_random_u32_below() must take ceil > 0");
+       if (ceil <= 1)
+               return 0;
+       for (;;) {
+               if (ceil <= 1U << 8) {
+                       u32 mult = ceil * get_random_u8();
+                       if (likely(is_power_of_2(ceil) || (u8)mult >= (1U << 8) % ceil))
+                               return mult >> 8;
+               } else if (ceil <= 1U << 16) {
+                       u32 mult = ceil * get_random_u16();
+                       if (likely(is_power_of_2(ceil) || (u16)mult >= (1U << 16) % ceil))
+                               return mult >> 16;
+               } else {
+                       u64 mult = (u64)ceil * get_random_u32();
+                       if (likely(is_power_of_2(ceil) || (u32)mult >= -ceil % ceil))
+                               return mult >> 32;
+               }
+       }
+}
+
 /*
  * On 64-bit architectures, protect against non-terminated C string overflows
  * by zeroing out the first byte of the canary; this leaves 56 bits of entropy.