diff options
| author | Denys Vlasenko | 2017-07-09 00:39:15 +0200 |
|---|---|---|
| committer | Denys Vlasenko | 2017-08-04 02:17:42 +0200 |
| commit | 310bcec4dcfaeaf4afa40a5b03e588fd224aeda3 (patch) | |
| tree | 762447d2598dac871f7b9d39f705923499cf25a7 | |
| parent | 8fd69c7bdb217d1c5030dbc9cfdb0acb4205c6b7 (diff) | |
| download | busybox-310bcec4dcfaeaf4afa40a5b03e588fd224aeda3.zip busybox-310bcec4dcfaeaf4afa40a5b03e588fd224aeda3.tar.gz | |
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>
| -rw-r--r-- | coreutils/shuf.c | 2 |
1 files changed, 1 insertions, 1 deletions
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; |