git: 2ba20004ef76 - main - libc: Reimplement the *rand48 family of functions
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Mon, 06 Oct 2025 19:21:39 UTC
The branch main has been updated by markj:
URL: https://cgit.FreeBSD.org/src/commit/?id=2ba20004ef7649db7654520e8376927c4410d9c3
commit 2ba20004ef7649db7654520e8376927c4410d9c3
Author: Mark Johnston <markj@FreeBSD.org>
AuthorDate: 2025-09-04 19:34:17 +0000
Commit: Mark Johnston <markj@FreeBSD.org>
CommitDate: 2025-10-06 19:20:39 +0000
libc: Reimplement the *rand48 family of functions
Rather than implementing the recurrence using 3 16-bit integers, as was
done in _dorand48() before this patch, provide an equivalent
implementation using 64-bit integers.
For drand48() and erand48(), replace the use of ldexp() with
bit-twiddling assuming IEEE 754 double-precision float layout.
This implementation is significantly faster and requires less code,
while producing identical outputs on supported platforms.
While here, add a STANDARDS section to rand48.3.
Obtained from: https://github.com/apple-oss-distributions/libc
MFC after: 3 weeks
Sponsored by: Klara, Inc.
Differential Revision: https://reviews.freebsd.org/D52429
---
lib/libc/gen/_rand48.c | 34 +++-------------------------
lib/libc/gen/drand48.c | 6 ++---
lib/libc/gen/erand48.c | 9 ++++----
lib/libc/gen/jrand48.c | 7 +++---
lib/libc/gen/lcong48.c | 12 ++--------
lib/libc/gen/lrand48.c | 6 ++---
lib/libc/gen/mrand48.c | 8 ++-----
lib/libc/gen/nrand48.c | 6 +++--
lib/libc/gen/rand48.3 | 5 ++++-
lib/libc/gen/rand48.h | 61 +++++++++++++++++++++++++++++++++++++++++++++++++-
lib/libc/gen/seed48.c | 18 ++++-----------
lib/libc/gen/srand48.c | 13 +++--------
12 files changed, 95 insertions(+), 90 deletions(-)
diff --git a/lib/libc/gen/_rand48.c b/lib/libc/gen/_rand48.c
index 990e2c86949b..114c1595b33d 100644
--- a/lib/libc/gen/_rand48.c
+++ b/lib/libc/gen/_rand48.c
@@ -13,34 +13,6 @@
#include "rand48.h"
-unsigned short _rand48_seed[3] = {
- RAND48_SEED_0,
- RAND48_SEED_1,
- RAND48_SEED_2
-};
-unsigned short _rand48_mult[3] = {
- RAND48_MULT_0,
- RAND48_MULT_1,
- RAND48_MULT_2
-};
-unsigned short _rand48_add = RAND48_ADD;
-
-void
-_dorand48(unsigned short xseed[3])
-{
- unsigned long accu;
- unsigned short temp[2];
-
- accu = (unsigned long) _rand48_mult[0] * (unsigned long) xseed[0] +
- (unsigned long) _rand48_add;
- temp[0] = (unsigned short) accu; /* lower 16 bits */
- accu >>= sizeof(unsigned short) * 8;
- accu += (unsigned long) _rand48_mult[0] * (unsigned long) xseed[1] +
- (unsigned long) _rand48_mult[1] * (unsigned long) xseed[0];
- temp[1] = (unsigned short) accu; /* middle 16 bits */
- accu >>= sizeof(unsigned short) * 8;
- accu += _rand48_mult[0] * xseed[2] + _rand48_mult[1] * xseed[1] + _rand48_mult[2] * xseed[0];
- xseed[0] = temp[0];
- xseed[1] = temp[1];
- xseed[2] = (unsigned short) accu;
-}
+uint48 _rand48_seed = RAND48_SEED;
+uint48 _rand48_mult = RAND48_MULT;
+uint48 _rand48_add = RAND48_ADD;
diff --git a/lib/libc/gen/drand48.c b/lib/libc/gen/drand48.c
index cec04a6a2425..f7f43ff20468 100644
--- a/lib/libc/gen/drand48.c
+++ b/lib/libc/gen/drand48.c
@@ -13,10 +13,10 @@
#include "rand48.h"
-extern unsigned short _rand48_seed[3];
-
double
drand48(void)
{
- return erand48(_rand48_seed);
+ ERAND48_BEGIN;
+ _DORAND48(_rand48_seed);
+ ERAND48_END(_rand48_seed);
}
diff --git a/lib/libc/gen/erand48.c b/lib/libc/gen/erand48.c
index 286904c27839..38d4774a9fe6 100644
--- a/lib/libc/gen/erand48.c
+++ b/lib/libc/gen/erand48.c
@@ -16,8 +16,9 @@
double
erand48(unsigned short xseed[3])
{
- _dorand48(xseed);
- return ldexp((double) xseed[0], -48) +
- ldexp((double) xseed[1], -32) +
- ldexp((double) xseed[2], -16);
+ uint48 tmp;
+
+ ERAND48_BEGIN;
+ DORAND48(tmp, xseed);
+ ERAND48_END(tmp);
}
diff --git a/lib/libc/gen/jrand48.c b/lib/libc/gen/jrand48.c
index 0a9f780a9e5c..93442439d49e 100644
--- a/lib/libc/gen/jrand48.c
+++ b/lib/libc/gen/jrand48.c
@@ -11,14 +11,13 @@
* to anyone/anything when using this software.
*/
-#include <stdint.h>
-
#include "rand48.h"
long
jrand48(unsigned short xseed[3])
{
+ uint48 tmp;
- _dorand48(xseed);
- return ((int32_t)(((uint32_t)xseed[2] << 16) | (uint32_t)xseed[1]));
+ DORAND48(tmp, xseed);
+ return ((int)((tmp >> 16) & 0xffffffff));
}
diff --git a/lib/libc/gen/lcong48.c b/lib/libc/gen/lcong48.c
index f13826b3d3f3..871b2110ed94 100644
--- a/lib/libc/gen/lcong48.c
+++ b/lib/libc/gen/lcong48.c
@@ -13,18 +13,10 @@
#include "rand48.h"
-extern unsigned short _rand48_seed[3];
-extern unsigned short _rand48_mult[3];
-extern unsigned short _rand48_add;
-
void
lcong48(unsigned short p[7])
{
- _rand48_seed[0] = p[0];
- _rand48_seed[1] = p[1];
- _rand48_seed[2] = p[2];
- _rand48_mult[0] = p[3];
- _rand48_mult[1] = p[4];
- _rand48_mult[2] = p[5];
+ LOADRAND48(_rand48_seed, &p[0]);
+ LOADRAND48(_rand48_mult, &p[3]);
_rand48_add = p[6];
}
diff --git a/lib/libc/gen/lrand48.c b/lib/libc/gen/lrand48.c
index a3d0111cf4d5..cc07044b8af9 100644
--- a/lib/libc/gen/lrand48.c
+++ b/lib/libc/gen/lrand48.c
@@ -13,11 +13,9 @@
#include "rand48.h"
-extern unsigned short _rand48_seed[3];
-
long
lrand48(void)
{
- _dorand48(_rand48_seed);
- return ((long) _rand48_seed[2] << 15) + ((long) _rand48_seed[1] >> 1);
+ _DORAND48(_rand48_seed);
+ return (_rand48_seed >> 17) & 0x7fffffff;
}
diff --git a/lib/libc/gen/mrand48.c b/lib/libc/gen/mrand48.c
index 15b0bfb1bd6e..f9128a6d4188 100644
--- a/lib/libc/gen/mrand48.c
+++ b/lib/libc/gen/mrand48.c
@@ -15,13 +15,9 @@
#include "rand48.h"
-extern unsigned short _rand48_seed[3];
-
long
mrand48(void)
{
-
- _dorand48(_rand48_seed);
- return ((int32_t)(((uint32_t)_rand48_seed[2] << 16) |
- (uint32_t)_rand48_seed[1]));
+ _DORAND48(_rand48_seed);
+ return ((int)((_rand48_seed >> 16) & 0xffffffff));
}
diff --git a/lib/libc/gen/nrand48.c b/lib/libc/gen/nrand48.c
index 6c54065e7e0f..f6f4e231105c 100644
--- a/lib/libc/gen/nrand48.c
+++ b/lib/libc/gen/nrand48.c
@@ -16,6 +16,8 @@
long
nrand48(unsigned short xseed[3])
{
- _dorand48(xseed);
- return ((long) xseed[2] << 15) + ((long) xseed[1] >> 1);
+ uint48 tmp;
+
+ DORAND48(tmp, xseed);
+ return ((tmp >> 17) & 0x7fffffff);
}
diff --git a/lib/libc/gen/rand48.3 b/lib/libc/gen/rand48.3
index 1e47c843058e..3ea649354270 100644
--- a/lib/libc/gen/rand48.3
+++ b/lib/libc/gen/rand48.3
@@ -9,7 +9,7 @@
.\" of any kind. I shall in no event be liable for anything that happens
.\" to anyone/anything when using this software.
.\"
-.Dd September 4, 2012
+.Dd September 11, 2025
.Dt RAND48 3
.Os
.Sh NAME
@@ -183,5 +183,8 @@ generator calls.
.Xr arc4random 3 ,
.Xr rand 3 ,
.Xr random 3
+.Sh STANDARDS
+The functions described in this page are expected to conform to
+.St -p1003.1-2008 .
.Sh AUTHORS
.An Martin Birgmeier
diff --git a/lib/libc/gen/rand48.h b/lib/libc/gen/rand48.h
index 9861e99683cb..d3326e851491 100644
--- a/lib/libc/gen/rand48.h
+++ b/lib/libc/gen/rand48.h
@@ -14,10 +14,11 @@
#ifndef _RAND48_H_
#define _RAND48_H_
+#include <sys/types.h>
#include <math.h>
#include <stdlib.h>
-void _dorand48(unsigned short[3]);
+#include "fpmath.h"
#define RAND48_SEED_0 (0x330e)
#define RAND48_SEED_1 (0xabcd)
@@ -27,4 +28,62 @@ void _dorand48(unsigned short[3]);
#define RAND48_MULT_2 (0x0005)
#define RAND48_ADD (0x000b)
+typedef uint64_t uint48;
+
+extern uint48 _rand48_seed;
+extern uint48 _rand48_mult;
+extern uint48 _rand48_add;
+
+#define TOUINT48(x, y, z) \
+ ((uint48)(x) + (((uint48)(y)) << 16) + (((uint48)(z)) << 32))
+
+#define RAND48_SEED TOUINT48(RAND48_SEED_0, RAND48_SEED_1, RAND48_SEED_2)
+#define RAND48_MULT TOUINT48(RAND48_MULT_0, RAND48_MULT_1, RAND48_MULT_2)
+
+#define LOADRAND48(l, x) do { \
+ (l) = TOUINT48((x)[0], (x)[1], (x)[2]); \
+} while (0)
+
+#define STORERAND48(l, x) do { \
+ (x)[0] = (unsigned short)(l); \
+ (x)[1] = (unsigned short)((l) >> 16); \
+ (x)[2] = (unsigned short)((l) >> 32); \
+} while (0)
+
+#define _DORAND48(l) do { \
+ (l) = (l) * _rand48_mult + _rand48_add; \
+} while (0)
+
+#define DORAND48(l, x) do { \
+ LOADRAND48(l, x); \
+ _DORAND48(l); \
+ STORERAND48(l, x); \
+} while (0)
+
+#define ERAND48_BEGIN \
+ union { \
+ union IEEEd2bits ieee; \
+ uint64_t u64; \
+ } u; \
+ int s
+
+/*
+ * Optimization for speed: assume doubles are IEEE 754 and use bit fiddling
+ * rather than converting to double. Specifically, clamp the result to 48 bits
+ * and convert to a double in [0.0, 1.0) via division by 2^48. Normalize by
+ * shifting the most significant bit into the implicit one position and
+ * adjusting the exponent accordingly. The store to the exponent field
+ * overwrites the implicit one.
+ */
+#define ERAND48_END(x) do { \
+ u.u64 = ((x) & 0xffffffffffffULL); \
+ if (u.u64 == 0) \
+ return (0.0); \
+ u.u64 <<= 5; \
+ for (s = 0; !(u.u64 & (1LL << 52)); s++, u.u64 <<= 1) \
+ ; \
+ u.ieee.bits.exp = 1022 - s; \
+ return (u.ieee.d); \
+} while (0)
+
#endif /* _RAND48_H_ */
diff --git a/lib/libc/gen/seed48.c b/lib/libc/gen/seed48.c
index 258c4bac3c9f..f57656ce1121 100644
--- a/lib/libc/gen/seed48.c
+++ b/lib/libc/gen/seed48.c
@@ -13,24 +13,14 @@
#include "rand48.h"
-extern unsigned short _rand48_seed[3];
-extern unsigned short _rand48_mult[3];
-extern unsigned short _rand48_add;
-
unsigned short *
seed48(unsigned short xseed[3])
{
static unsigned short sseed[3];
- sseed[0] = _rand48_seed[0];
- sseed[1] = _rand48_seed[1];
- sseed[2] = _rand48_seed[2];
- _rand48_seed[0] = xseed[0];
- _rand48_seed[1] = xseed[1];
- _rand48_seed[2] = xseed[2];
- _rand48_mult[0] = RAND48_MULT_0;
- _rand48_mult[1] = RAND48_MULT_1;
- _rand48_mult[2] = RAND48_MULT_2;
+ STORERAND48(_rand48_seed, sseed);
+ LOADRAND48(_rand48_seed, xseed);
+ _rand48_mult = RAND48_MULT;
_rand48_add = RAND48_ADD;
- return sseed;
+ return (sseed);
}
diff --git a/lib/libc/gen/srand48.c b/lib/libc/gen/srand48.c
index fd369a094c51..4b82ece72db8 100644
--- a/lib/libc/gen/srand48.c
+++ b/lib/libc/gen/srand48.c
@@ -13,18 +13,11 @@
#include "rand48.h"
-extern unsigned short _rand48_seed[3];
-extern unsigned short _rand48_mult[3];
-extern unsigned short _rand48_add;
-
void
srand48(long seed)
{
- _rand48_seed[0] = RAND48_SEED_0;
- _rand48_seed[1] = (unsigned short) seed;
- _rand48_seed[2] = (unsigned short) (seed >> 16);
- _rand48_mult[0] = RAND48_MULT_0;
- _rand48_mult[1] = RAND48_MULT_1;
- _rand48_mult[2] = RAND48_MULT_2;
+ _rand48_seed = TOUINT48(RAND48_SEED_0, (unsigned short)seed,
+ (unsigned short)(seed >> 16));
+ _rand48_mult = RAND48_MULT;
_rand48_add = RAND48_ADD;
}