aboutsummaryrefslogtreecommitdiffstats
path: root/src/string/str
diff options
context:
space:
mode:
authorMattias Andrée <maandree@kth.se>2016-03-26 16:00:37 +0100
committerMattias Andrée <maandree@kth.se>2016-03-26 16:00:44 +0100
commite43340649f45c865c6ed4d8aad8eb3944aea8057 (patch)
tree5ea99f9c339e3a55e8911629926145e2c618b7a0 /src/string/str
parentm (diff)
downloadslibc-e43340649f45c865c6ed4d8aad8eb3944aea8057.tar.gz
slibc-e43340649f45c865c6ed4d8aad8eb3944aea8057.tar.bz2
slibc-e43340649f45c865c6ed4d8aad8eb3944aea8057.tar.xz
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>
Diffstat (limited to '')
-rw-r--r--src/string/strfry.c35
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;