/* | |

* Copyright (c) 2017, Alliance for Open Media. All rights reserved. | |

* | |

* This source code is subject to the terms of the BSD 2 Clause License and | |

* the Alliance for Open Media Patent License 1.0. If the BSD 2 Clause License | |

* was not distributed with this source code in the LICENSE file, you can | |

* obtain it at www.aomedia.org/license/software. If the Alliance for Open | |

* Media Patent License 1.0 was not distributed with this source code in the | |

* PATENTS file, you can obtain it at www.aomedia.org/license/patent. | |

*/ | |

#ifndef AOM_AV1_ENCODER_RANDOM_H_ | |

#define AOM_AV1_ENCODER_RANDOM_H_ | |

#include <stdint.h> | |

#ifdef __cplusplus | |

extern "C" { | |

#endif | |

// Advance the generator to its next state, and generate the next 32-bit output. | |

// Note that the low bits of this output are comparatively low-quality, so users | |

// of this function should ensure that the high bits factor through to their | |

// outputs. | |

static inline uint32_t lcg_next(uint32_t *state) { | |

*state = (uint32_t)(*state * 1103515245ULL + 12345); | |

return *state; | |

} | |

// Generate a random number in the range [0, 32768). | |

static inline uint32_t lcg_rand16(uint32_t *state) { | |

return (lcg_next(state) / 65536) % 32768; | |

} | |

// Generate a random number in the range [0, n) | |

// This is implemented as (rand() * n) / <range of RNG> rather than | |

// rand() % n, for a few reasons: This implementation is faster and less biased, | |

// and if is a power of 2, this uses the higher-quality top bits from the RNG | |

// output rather than the lower-quality bottom bits. | |

static inline uint32_t lcg_randint(uint32_t *state, uint32_t n) { | |

uint64_t v = ((uint64_t)lcg_next(state) * n) >> 32; | |

return (uint32_t)v; | |

} | |

// Generate a random number in the range [lo, hi) | |

static inline uint32_t lcg_randrange(uint32_t *state, uint32_t lo, | |

uint32_t hi) { | |

assert(lo < hi); | |

return lo + lcg_randint(state, hi - lo); | |

} | |

// Pick k distinct numbers from the set {0, ..., n-1} | |

// All possible sets of k numbers, and all possible orderings of those numbers, | |

// are equally likely. | |

// | |

// Note: The algorithm used here uses resampling to avoid choosing repeated | |

// values. This works well as long as n >> k, but can potentially lead to many | |

// resampling attempts if n is equal to or only slightly larger than k. | |

static inline void lcg_pick(int n, int k, int *out, unsigned int *seed) { | |

assert(0 <= k && k <= n); | |

for (int i = 0; i < k; i++) { | |

int v; | |

// Inner resampling loop | |

// We have to use a goto here because C does not have a multi-level continue | |

// statement | |

resample: | |

v = (int)lcg_randint(seed, n); | |

for (int j = 0; j < i; j++) { | |

if (v == out[j]) { | |

// Repeated v, resample | |

goto resample; | |

} | |

} | |

// New v, accept | |

out[i] = v; | |

} | |

} | |

#ifdef __cplusplus | |

} // extern "C" | |

#endif | |

#endif // AOM_AV1_ENCODER_RANDOM_H_ |