strfry: fix random int range boundary, document that srand should have been called, support huge strings, and use uniform random

Signed-off-by: Mattias Andrée <maandree@kth.se>

1 files changed, 32 insertions, 3 deletions

diff --git a/src/string/strfry.c b/src/string/strfry.c
index 39f53e6..5aec420 100644
--- a/src/string/strfry.c
+++ b/src/string/strfry.c
@@ -22,10 +22,41 @@
 /* Durstenfeld's algorithm. */
 
 
+/**
+ * The number of bits to retain from `rand` output.
+ */
+#define BITS  8
+
+
+/**
+ * Generate a `size_t` uniformly random.
+ * 
+ * @param   max  The largest number to generate, inclusive.
+ * @return       A random number between 0 and `max`, inclusively.
+ */
+static size_t
+uniform_random_zu(size_t max)
+{
+  size_t n = max, r = 0, mask = max, s = 1;
+  while (((mask + 1) & ~mask) != mask + 1)
+    mask |= mask >> s++;
+  do
+    for (; n; n >>= BITS)
+      {
+	b = rand();
+	b /= (double)RAND_MAX + 1;
+	r = (r << BITS) | (int)(b * (1 << BITS));
+      }
+  while (r &= mask, r > max);
+  return r;
+}
 
 /**
  * Shuffles all bytes in a string.
  * 
+ * You should have called `srand` before
+ * calling this function.
+ * 
  * This is a GNU joke extension.
  * 
  * @param   anagram  An anagram of the output, will be modified.
@@ -36,14 +67,12 @@
 char* strfry(char* anagram)
 {
   size_t i, j;
-  int r;
   char t;
   if (anagram == NULL)
     return NULL;
   for (i = strlen(anagram); i--;)
     {
-      r = rand();
-      j = (size_t)((double)r / ((double)RAND_MAX + 1) * (double)i); /* TODO This is not uniformally random. */
+      j = uniform_random_zu(i);
       t = anagram[i], anagram[i] = anagram[j], anagram[j] = t;
     }
   return anagram;