From 9de9c871bf44b931c7a1bb66d3134e2deb811f88 Mon Sep 17 00:00:00 2001
From: Denys Vlasenko
Date: Sun, 9 Jul 2017 00:39:15 +0200
Subject: shuf: fix random line selection. Closes 9971

"""
For example, given input file:

    foo
    bar
    baz

after shuffling the input file, foo will never end up back on the first line.
This came to light when I ran into a use-case where someone was selecting
a random line from a file using shuf | head -n 1, and the results on busybox
were showing a statistical anomaly (as in, the first line would never ever
be picked) vs the same process running on environments that had gnu coreutils
installed.

On line https://git.busybox.net/busybox/tree/coreutils/shuf.c#n56 it uses
r %= i, which will result in 0 <= r < i, while the algorithm specifies
0 <= r <= i.
"""

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
---
 coreutils/shuf.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'coreutils')

diff --git a/coreutils/shuf.c b/coreutils/shuf.c
index 9f61f2f..217f15c 100644
--- a/coreutils/shuf.c
+++ b/coreutils/shuf.c
@@ -53,7 +53,7 @@ static void shuffle_lines(char **lines, unsigned numlines)
 		/* RAND_MAX can be as small as 32767 */
 		if (i > RAND_MAX)
 			r ^= rand() << 15;
-		r %= i;
+		r %= i + 1;
 		tmp = lines[i];
 		lines[i] = lines[r];
 		lines[r] = tmp;
-- 
cgit v1.1