1 /*
2 * Copyright (c) 2017, Alliance for Open Media. All rights reserved.
3 *
4 * This source code is subject to the terms of the BSD 2 Clause License and
5 * the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License
6 * was not distributed with this source code in the LICENSE file, you can
7 * obtain it at www.aomedia.org/license/software. If the Alliance for Open
8 * Media Patent License 1.0 was not distributed with this source code in the
9 * PATENTS file, you can obtain it at www.aomedia.org/license/patent.
10 */
11
12 #ifndef AOM_AV1_ENCODER_RANDOM_H_
13 #define AOM_AV1_ENCODER_RANDOM_H_
14
15 #include <stdint.h>
16
17 #ifdef __cplusplus
18 extern "C" {
19 #endif
20
21 // Advance the generator to its next state, and generate the next 32-bit output.
22 // Note that the low bits of this output are comparatively low-quality, so users
23 // of this function should ensure that the high bits factor through to their
24 // outputs.
lcg_next(uint32_t * state)25 static inline uint32_t lcg_next(uint32_t *state) {
26 *state = (uint32_t)(*state * 1103515245ULL + 12345);
27 return *state;
28 }
29
30 // Generate a random number in the range [0, 32768).
lcg_rand16(uint32_t * state)31 static inline uint32_t lcg_rand16(uint32_t *state) {
32 return (lcg_next(state) / 65536) % 32768;
33 }
34
35 // Generate a random number in the range [0, n)
36 // This is implemented as (rand() * n) / <range of RNG> rather than
37 // rand() % n, for a few reasons: This implementation is faster and less biased,
38 // and if is a power of 2, this uses the higher-quality top bits from the RNG
39 // output rather than the lower-quality bottom bits.
lcg_randint(uint32_t * state,uint32_t n)40 static inline uint32_t lcg_randint(uint32_t *state, uint32_t n) {
41 uint64_t v = ((uint64_t)lcg_next(state) * n) >> 32;
42 return (uint32_t)v;
43 }
44
45 // Generate a random number in the range [lo, hi)
lcg_randrange(uint32_t * state,uint32_t lo,uint32_t hi)46 static inline uint32_t lcg_randrange(uint32_t *state, uint32_t lo,
47 uint32_t hi) {
48 assert(lo < hi);
49 return lo + lcg_randint(state, hi - lo);
50 }
51
52 // Pick k distinct numbers from the set {0, ..., n-1}
53 // All possible sets of k numbers, and all possible orderings of those numbers,
54 // are equally likely.
55 //
56 // Note: The algorithm used here uses resampling to avoid choosing repeated
57 // values. This works well as long as n >> k, but can potentially lead to many
58 // resampling attempts if n is equal to or only slightly larger than k.
lcg_pick(int n,int k,int * out,unsigned int * seed)59 static inline void lcg_pick(int n, int k, int *out, unsigned int *seed) {
60 assert(0 <= k && k <= n);
61 for (int i = 0; i < k; i++) {
62 int v;
63
64 // Inner resampling loop
65 // We have to use a goto here because C does not have a multi-level continue
66 // statement
67 resample:
68 v = (int)lcg_randint(seed, n);
69 for (int j = 0; j < i; j++) {
70 if (v == out[j]) {
71 // Repeated v, resample
72 goto resample;
73 }
74 }
75
76 // New v, accept
77 out[i] = v;
78 }
79 }
80
81 #ifdef __cplusplus
82 } // extern "C"
83 #endif
84
85 #endif // AOM_AV1_ENCODER_RANDOM_H_
86