shithub: libvpx

Info  •  Files  •  Log  •  Branches

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

--- a/vp10/encoder/palette.c

+++ b/vp10/encoder/palette.c

@@ -39,12 +39,20 @@

   }

 }

+// 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];

-  srand((unsigned int) data[0]);

+  assert(n <= 32768);

+

   memset(count, 0, sizeof(count[0]) * k);

   memset(centroids, 0, sizeof(centroids[0]) * k * dim);

@@ -59,8 +67,7 @@

   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];