aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--include/string.h3
-rw-r--r--src/string/strfry.c35
2 files changed, 35 insertions, 3 deletions
diff --git a/include/string.h b/include/string.h
index f04e4a9..99608d9 100644
--- a/include/string.h
+++ b/include/string.h
@@ -1387,6 +1387,9 @@ char* __gnu_basename(const char*)
/**
* 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.
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;