random.h (2853B)
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. 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). 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. 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) 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. 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_