diff options
author | ache <ache@FreeBSD.org> | 2008-08-08 02:46:47 +0000 |
---|---|---|
committer | ache <ache@FreeBSD.org> | 2008-08-08 02:46:47 +0000 |
commit | 42825e9561229aeb9c6ca0cc9a84fc439960f241 (patch) | |
tree | cb1e18eaabc237340aafc9f33b13f71f70f4ff3a /games | |
parent | 823689b09c9db6b0a03a78837e4c02b453e37d8d (diff) | |
download | FreeBSD-src-42825e9561229aeb9c6ca0cc9a84fc439960f241.zip FreeBSD-src-42825e9561229aeb9c6ca0cc9a84fc439960f241.tar.gz |
1) Fix longstanding math bug with denominator > 1 (wrong probability).
Test case:
random -f some_small_file 10000
(in most cases must be no output)
2) Prevent number of lines > RANDOM_MAX (overflow or nothing may be
choosed) with EFBIG err()
3) After line is found, terminate list loop for -U case too,
since nothing to do in the rest of the loop left.
Diffstat (limited to 'games')
-rw-r--r-- | games/random/randomize_fd.c | 24 |
1 files changed, 16 insertions, 8 deletions
diff --git a/games/random/randomize_fd.c b/games/random/randomize_fd.c index e1011fb..c625d14 100644 --- a/games/random/randomize_fd.c +++ b/games/random/randomize_fd.c @@ -32,6 +32,7 @@ __FBSDID("$FreeBSD$"); #include <ctype.h> #include <err.h> +#include <errno.h> #include <stdlib.h> #include <stdio.h> #include <string.h> @@ -94,10 +95,11 @@ int randomize_fd(int fd, int type, int unique, double denom) { u_char *buf; - u_int numnode, j, selected, slen; + u_int slen; + u_long i, j, numnode, selected; struct rand_node *n, *prev; int bufleft, eof, fndstr, ret; - size_t bufc, buflen, i; + size_t bufc, buflen; ssize_t len; rand_root = rand_tail = NULL; @@ -173,6 +175,11 @@ randomize_fd(int fd, int type, int unique, double denom) (type == RANDOM_TYPE_WORDS && isspace(buf[i])) || (eof && i == buflen - 1)) { make_token: + if (numnode == RANDOM_MAX) { + errno = EFBIG; + err(1, "too many lines"); + } + numnode++; n = rand_node_allocate(); if (-1 != (int)i) { slen = i - (u_long)bufc; @@ -188,7 +195,6 @@ randomize_fd(int fd, int type, int unique, double denom) } rand_node_append(n); fndstr = 1; - numnode++; } } } @@ -202,16 +208,18 @@ randomize_fd(int fd, int type, int unique, double denom) } for (i = numnode; i > 0; i--) { - selected = ((int)denom * random())/(RANDOM_MAX / numnode); + selected = random() % numnode; for (j = 0, prev = n = rand_root; n != NULL; j++, prev = n, n = n->next) { if (j == selected) { if (n->cp == NULL) break; - ret = printf("%.*s", (int)n->len - 1, n->cp); - if (ret < 0) - err(1, "printf"); + if ((int)(denom * random() / RANDOM_MAX) == 0) { + ret = printf("%.*s", (int)n->len - 1, n->cp); + if (ret < 0) + err(1, "printf"); + } if (unique) { if (n == rand_root) rand_root = n->next; @@ -221,8 +229,8 @@ randomize_fd(int fd, int type, int unique, double denom) prev->next = n->next; rand_node_free(n); numnode--; - break; } + break; } } } |