/src/aom/av1/encoder/random.h

Source (jump to first uncovered line)
/*
 * 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_

Coverage Report

Created: 2025-06-22 08:04

Line	Count	Source (jump to first uncovered line)
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	0	static inline uint32_t lcg_next(uint32_t *state) {
26	0	state = (uint32_t)(state * 1103515245ULL + 12345);
27	0	return *state;
28	0	} Unexecuted instantiation: encoder.c:lcg_next Unexecuted instantiation: palette.c:lcg_next Unexecuted instantiation: ratectrl.c:lcg_next Unexecuted instantiation: rdopt.c:lcg_next Unexecuted instantiation: superres_scale.c:lcg_next Unexecuted instantiation: tx_search.c:lcg_next Unexecuted instantiation: ransac.c:lcg_next
29
30		// Generate a random number in the range [0, 32768).
31	0	static inline uint32_t lcg_rand16(uint32_t *state) {
32	0	return (lcg_next(state) / 65536) % 32768;
33	0	} Unexecuted instantiation: encoder.c:lcg_rand16 Unexecuted instantiation: palette.c:lcg_rand16 Unexecuted instantiation: ratectrl.c:lcg_rand16 Unexecuted instantiation: rdopt.c:lcg_rand16 Unexecuted instantiation: superres_scale.c:lcg_rand16 Unexecuted instantiation: tx_search.c:lcg_rand16 Unexecuted instantiation: ransac.c:lcg_rand16
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	0	static inline uint32_t lcg_randint(uint32_t *state, uint32_t n) {
41	0	uint64_t v = ((uint64_t)lcg_next(state) * n) >> 32;
42	0	return (uint32_t)v;
43	0	} Unexecuted instantiation: encoder.c:lcg_randint Unexecuted instantiation: palette.c:lcg_randint Unexecuted instantiation: ratectrl.c:lcg_randint Unexecuted instantiation: rdopt.c:lcg_randint Unexecuted instantiation: superres_scale.c:lcg_randint Unexecuted instantiation: tx_search.c:lcg_randint Unexecuted instantiation: ransac.c:lcg_randint
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	0	uint32_t hi) {
48	0	assert(lo < hi);
49	0	return lo + lcg_randint(state, hi - lo);
50	0	} Unexecuted instantiation: encoder.c:lcg_randrange Unexecuted instantiation: palette.c:lcg_randrange Unexecuted instantiation: ratectrl.c:lcg_randrange Unexecuted instantiation: rdopt.c:lcg_randrange Unexecuted instantiation: superres_scale.c:lcg_randrange Unexecuted instantiation: tx_search.c:lcg_randrange Unexecuted instantiation: ransac.c:lcg_randrange
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	0	static inline void lcg_pick(int n, int k, int out, unsigned int seed) {
60	0	assert(0 <= k && k <= n);
61	0	for (int i = 0; i < k; i++) {
62	0	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	0	resample:
68	0	v = (int)lcg_randint(seed, n);
69	0	for (int j = 0; j < i; j++) {
70	0	if (v == out[j]) {
71		// Repeated v, resample
72	0	goto resample;
73	0	}
74	0	}
75
76		// New v, accept
77	0	out[i] = v;
78	0	}
79	0	} Unexecuted instantiation: encoder.c:lcg_pick Unexecuted instantiation: palette.c:lcg_pick Unexecuted instantiation: ratectrl.c:lcg_pick Unexecuted instantiation: rdopt.c:lcg_pick Unexecuted instantiation: superres_scale.c:lcg_pick Unexecuted instantiation: tx_search.c:lcg_pick Unexecuted instantiation: ransac.c:lcg_pick
80
81		#ifdef __cplusplus
82		} // extern "C"
83		#endif
84
85		#endif // AOM_AV1_ENCODER_RANDOM_H_