From e43340649f45c865c6ed4d8aad8eb3944aea8057 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sat, 26 Mar 2016 16:00:37 +0100 Subject: strfry: fix random int range boundary, document that srand should have been called, support huge strings, and use uniform random MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- src/string/strfry.c | 35 ++++++++++++++++++++++++++++++++--- 1 file changed, 32 insertions(+), 3 deletions(-) (limited to 'src') 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; -- cgit v1.2.3-70-g09d2