diff options
| author | Alex Converse <aconverse@google.com> | 2015-10-14 11:03:14 -0700 |
|---|---|---|
| committer | Alex Converse <aconverse@google.com> | 2015-10-24 13:38:23 -0700 |
| commit | 171fd8999fe8fdf04b5e836ff4eb0106ac6d7501 (patch) | |
| tree | 700ba6f690e476975f4e63d77c1079703965fba1 | |
| parent | d162934bdca89b156194732226746993356344ef (diff) | |
| download | libvpx-171fd8999fe8fdf04b5e836ff4eb0106ac6d7501.tar.gz | |
palette: Replace rand() call with custom LCG.
The custom LCG is based on the POSIX recommend constants for a 16-bit
rand(). This implementation uses less computation than typical standard
library procedures which have been extended for 32-bit support, is
guaranteed to be reentrant, and identical everywhere.
Change-Id: I3140bbd566f44ab820d131c584a5d4ec6134c5a0
Ref: http://pubs.opengroup.org/onlinepubs/9699919799/functions/rand.html
| -rw-r--r-- | vp10/encoder/palette.c | 13 |
1 files changed, 10 insertions, 3 deletions
diff --git a/vp10/encoder/palette.c b/vp10/encoder/palette.c index b6fd6533e..fd5f402d8 100644 --- a/vp10/encoder/palette.c +++ b/vp10/encoder/palette.c @@ -39,12 +39,20 @@ void vp10_calc_indices(const double *data, const double *centroids, } } +// Generate a random number in the range [0, 32768). +static unsigned int lcg_rand16(unsigned int *state) { + *state = *state * 1103515245 + 12345; + return *state / 65536 % 32768; +} + static void calc_centroids(const double *data, double *centroids, const uint8_t *indices, int n, int k, int dim) { int i, j, index; int count[PALETTE_MAX_SIZE]; + unsigned int rand_state = data[0]; + + assert(n <= 32768); - srand((unsigned int) data[0]); memset(count, 0, sizeof(count[0]) * k); memset(centroids, 0, sizeof(centroids[0]) * k * dim); @@ -59,8 +67,7 @@ static void calc_centroids(const double *data, double *centroids, for (i = 0; i < k; ++i) { if (count[i] == 0) { - // TODO(huisu): replace rand() with something else. - memcpy(centroids + i * dim, data + (rand() % n) * dim, + memcpy(centroids + i * dim, data + (lcg_rand16(&rand_state) % n) * dim, sizeof(centroids[0]) * dim); } else { const double norm = 1.0 / count[i]; |