Graphviz 13.0.0~dev.20250424.1043
Loading...
Searching...
No Matches
random.c
Go to the documentation of this file.
1
3
4#include <assert.h>
5#include <limits.h>
6#include <stdint.h>
7#include <stdlib.h>
8#include <string.h>
9#include <util/alloc.h>
10#include <util/gv_math.h>
11#include <util/random.h>
12
13int *gv_permutation(int bound) {
14 if (bound <= 0) {
15 return NULL;
16 }
17
18 // initialize a sequence `{0, 1, …, bound - 1}`
19 int *const p = gv_calloc((size_t)bound, sizeof(int));
20 for (int i = 0; i < bound; i++) {
21 p[i] = i;
22 }
23
24 // perform a Fisher-Yates shuffle
25 for (int i = bound - 1; i > 0; --i) {
26 const int j = gv_random(i + 1);
27 SWAP(&p[i], &p[j]);
28 }
29
30 return p;
31}
32
34static int random_small(int bound) {
35 assert(bound > 0);
36 assert(bound <= RAND_MAX);
37
38 // The interval `[0, RAND_MAX]` is not necessarily neatly divided into
39 // `bound`-sized chunks. E.g. using a bound of 3 with a `RAND_MAX` of 7:
40 // ┌───┬───┬───┬───┬───┬───┬───┬───┐
41 // │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
42 // └───┴───┴───┴───┴───┴───┴───┴───┘
43 // ◄─────────► ◄─────────► ◄─────►
44 // 3 values 3 values 2 values
45 // To guarantee a uniform distribution, derive the upper bound of the last
46 // complete chunk (5 in the example above), above which we discard and
47 // resample to avoid pulling from the partial trailing chunk.
48 const int discard_threshold =
49 RAND_MAX - (int)(((unsigned)RAND_MAX + 1) % (unsigned)bound);
50
51 int r;
52 do {
53 r = rand();
54 } while (r > discard_threshold);
55
56 return r % bound;
57}
58
59uint64_t gv_random_u64(uint64_t bound) {
60 assert(bound > 0);
61
62 // See comment in `random_small`, but note that our maximum generated value
63 // here will be `UINT64_MAX` instead of `RAND_MAX`. Note that we need to do a
64 // slightly different calculation to avoid the integer overflow that would
65 // otherwise result from `UINT64_MAX + 1`.
66 const uint64_t discard_threshold =
67 UINT64_MAX - (UINT64_MAX - bound + 1) % bound;
68
69 uint64_t r;
70 do {
71 // generate a random `uint64_t` value
72 r = 0;
73 for (size_t i = 0; i < sizeof(uint64_t); ++i) {
74 // `RAND_MAX ≥ 32767` is guaranteed, so `random_small(256)` is safe
75 const uint8_t byte = (uint8_t)random_small((int)UINT8_MAX + 1);
76 memcpy((char *)&r + i, &byte, sizeof(byte));
77 }
78 } while (r > discard_threshold);
79
80 return r % bound;
81}
82
83int gv_random(int bound) {
84 assert(bound > 0);
85
86 if (bound > RAND_MAX) {
87 _Static_assert(INT_MAX <= UINT64_MAX,
88 "the `int` type includes non-negative values that do not "
89 "fit in a `uint64_t`, hence some `int` values can never be "
90 "returned by `gv_random_u64`");
91 return (int)gv_random_u64((uint64_t)bound);
92 }
93 return random_small(bound);
94}
Memory allocation wrappers that exit on failure.
static void * gv_calloc(size_t nmemb, size_t size)
Definition alloc.h:26
#define UINT8_MAX
Definition gmlscan.c:337
node NULL
Definition grammar.y:163
Arithmetic helper functions.
#define SWAP(a, b)
Definition gv_math.h:130
static int random_small(int bound)
handle random number generation, bound ≤ RAND_MAX
Definition random.c:34
int gv_random(int bound)
Definition random.c:83
uint64_t gv_random_u64(uint64_t bound)
Definition random.c:59
int * gv_permutation(int bound)
Definition random.c:13
random number generation