diff options
Diffstat (limited to 'include/linux')
| -rw-r--r-- | include/linux/math64.h | 67 | ||||
| -rw-r--r-- | include/linux/random.h | 17 |
2 files changed, 84 insertions, 0 deletions
diff --git a/include/linux/math64.h b/include/linux/math64.h index 5eb6f064..13efcc08 100644 --- a/include/linux/math64.h +++ b/include/linux/math64.h @@ -82,4 +82,71 @@ static inline s64 div_s64(s64 dividend, s32 divisor) return div_s64_rem(dividend, divisor, &remainder); } +#ifndef mul_u32_u32 +/* + * Many a GCC version messes this up and generates a 64x64 mult :-( + */ +static inline u64 mul_u32_u32(u32 a, u32 b) +{ + return (u64)a * b; +} +#endif + +#if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__) + +#ifndef mul_u64_u64_shr +static __always_inline u64 mul_u64_u64_shr(u64 a, u64 mul, unsigned int shift) +{ + return (u64)(((unsigned __int128)a * mul) >> shift); +} +#endif /* mul_u64_u64_shr */ + +#else + +#ifndef mul_u64_u64_shr +static inline u64 mul_u64_u64_shr(u64 a, u64 b, unsigned int shift) +{ + union { + u64 ll; + struct { +#ifdef __BIG_ENDIAN + u32 high, low; +#else + u32 low, high; +#endif + } l; + } rl, rm, rn, rh, a0, b0; + u64 c; + + a0.ll = a; + b0.ll = b; + + rl.ll = mul_u32_u32(a0.l.low, b0.l.low); + rm.ll = mul_u32_u32(a0.l.low, b0.l.high); + rn.ll = mul_u32_u32(a0.l.high, b0.l.low); + rh.ll = mul_u32_u32(a0.l.high, b0.l.high); + + /* + * Each of these lines computes a 64-bit intermediate result into "c", + * starting at bits 32-95. The low 32-bits go into the result of the + * multiplication, the high 32-bits are carried into the next step. + */ + rl.l.high = c = (u64)rl.l.high + rm.l.low + rn.l.low; + rh.l.low = c = (c >> 32) + rm.l.high + rn.l.high + rh.l.low; + rh.l.high = (c >> 32) + rh.l.high; + + /* + * The 128-bit result of the multiplication is in rl.ll and rh.ll, + * shift it right and throw away the high part of the result. + */ + if (shift == 0) + return rl.ll; + if (shift < 64) + return (rl.ll >> shift) | (rh.ll << (64 - shift)); + return rh.ll >> (shift & 63); +} +#endif /* mul_u64_u64_shr */ + +#endif + #endif /* _LINUX_MATH64_H */ diff --git a/include/linux/random.h b/include/linux/random.h index 3203d13c..9b2bb59a 100644 --- a/include/linux/random.h +++ b/include/linux/random.h @@ -9,7 +9,9 @@ #include <unistd.h> #include <sys/syscall.h> #include <linux/bug.h> +#include <linux/kernel.h> #include <linux/log2.h> +#include <linux/math64.h> #ifdef SYS_getrandom static inline int getrandom(void *buf, size_t buflen, unsigned int flags) @@ -67,4 +69,19 @@ static inline u32 get_random_u32_below(u32 ceil) } } +static inline u64 get_random_u64_below(u64 ceil) +{ + if (ceil <= 1) + return 0; + if (ceil <= U32_MAX) + return get_random_u32_below(ceil); + + for (;;) { + u64 rand = get_random_u64(); + u64 mult = ceil * rand; + if (likely(mult >= -ceil % ceil)) + return mul_u64_u64_shr(ceil, rand, 64); + } +} + #endif /* _LINUX_RANDOM_H */ |