Index: head/usr.bin/random/random.6 =================================================================== --- head/usr.bin/random/random.6 (revision 357974) +++ head/usr.bin/random/random.6 (revision 357975) @@ -1,122 +1,120 @@ .\" Copyright (c) 1994 .\" The Regents of the University of California. All rights reserved. .\" .\" Redistribution and use in source and binary forms, with or without .\" modification, are permitted provided that the following conditions .\" are met: .\" 1. Redistributions of source code must retain the above copyright .\" notice, this list of conditions and the following disclaimer. .\" 2. Redistributions in binary form must reproduce the above copyright .\" notice, this list of conditions and the following disclaimer in the .\" documentation and/or other materials provided with the distribution. .\" 3. Neither the name of the University nor the names of its contributors .\" may be used to endorse or promote products derived from this software .\" without specific prior written permission. .\" .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" .\" @(#)random.6 8.2 (Berkeley) 3/31/94 .\" $FreeBSD$ .\" -.Dd December 12, 2019 +.Dd February 15, 2020 .Dt RANDOM 6 .Os .Sh NAME .Nm random .Nd random lines from a file or random numbers .Sh SYNOPSIS .Nm .Op Fl elrUuw .Op Fl f Ar filename .Op Ar denominator .Sh DESCRIPTION .Nm Random has two distinct modes of operations. -The default is to read in lines -from the standard input and randomly write them out -to the standard output with a probability of -1 / +The default is to read lines from standard input and write them to standard +output with a probability of 1.0 / .Ar denominator . +.Ar ( denominator +is a real number greater than or equal to 1.0.) The default .Ar denominator -for this mode of operation is 2, giving each line a 50/50 chance of +for this mode of operation is 2.0, giving each line a 50% chance of being displayed. .Pp -The second mode of operation is to read in a file from -.Ar filename -and randomize the contents of the file and send it back out to +The second mode of operation, selected with the +.Fl f Ar filename +option, reads the specified file and outputs the randomized contents to standard output. -The contents can be randomized based off of newlines or based off of -space characters as determined by -.Xr isspace 3 . +The contents can be randomized in units of lines (split on newline characters) +or in units of words (split on space characters as determined by +.Xr isspace 3 . ) The default .Ar denominator -for this mode of operation is 1, which gives each line a chance to be -displayed, but in a random order. +for this mode of operation is 1.0, which displays every line. .Pp The options are as follows: .Bl -tag -width Ds .It Fl e If the .Fl e option is specified, .Nm does not read or write anything, and simply exits with a random exit value of 0 to .Ar denominator \&- 1, inclusive. +In this mode, +.Ar denominator +must be less than or equal to 256. .It Fl f Ar filename The .Fl f option is used to specify the .Ar filename to read from. Standard input is used if .Ar filename -is set to -.Sq Fl . +is +.Sq - . .It Fl l Randomize the input via newlines (the default). .It Fl r -The -.Fl r -option guarantees that the output is unbuffered. +Do not buffer output. .It Fl U -Tells -.Xr random 6 -that it is okay for it to reuse any given line or word when creating a -randomized output. +Reuse any given line or word when creating a randomized output. .It Fl u -Tells -.Xr random 6 -not to select the same line or word from a file more than once (the -default). +Do not select the same line or word from a file more than once (the default). This does not guarantee uniqueness if there are two of the -same tokens from the input, but it does prevent selecting the same -token more than once. +same tokens in the input. .It Fl w Randomize words separated by .Xr isspace 3 instead of newlines. .El .Sh SEE ALSO .Xr fortune 6 .Sh HISTORY The functionality to randomizing lines and words was added in 2003 by .An Sean Chittenden Aq Mt seanc@FreeBSD.org . .Sh BUGS +This tool is a remnant of the "games" collection formerly part of +.Fx +base. +It probably should have been removed to ports with the rest of that collection. +It does not have a coherent purpose and the motivation for it to be a core base +utility is nonobvious. +.Pp No index is used when printing out tokens from the list which makes it rather slow for large files (10MB+). -For smaller -files, however, it should still be quite fast and efficient. Index: head/usr.bin/random/random.c =================================================================== --- head/usr.bin/random/random.c (revision 357974) +++ head/usr.bin/random/random.c (revision 357975) @@ -1,192 +1,195 @@ /* * Copyright (c) 1994 * The Regents of the University of California. All rights reserved. * * This code is derived from software contributed to Berkeley by * Guy Harris at Network Appliance Corp. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if 0 #ifndef lint static const char copyright[] = "@(#) Copyright (c) 1994\n\ The Regents of the University of California. All rights reserved.\n"; #endif /* not lint */ #ifndef lint static const char sccsid[] = "@(#)random.c 8.5 (Berkeley) 4/5/94"; #endif /* not lint */ #endif #include __FBSDID("$FreeBSD$"); #include #include #include #include #include #include +#include #include #include #include #include #include #include #include "randomize_fd.h" static void usage(void); int main(int argc, char *argv[]) { double denom; int ch, fd, random_exit, randomize_lines, random_type, ret, - selected, unique_output, unbuffer_output; + unique_output, unbuffer_output; + bool selected; char *ep; const char *filename; - denom = 0; + denom = 0.; filename = "/dev/fd/0"; random_type = RANDOM_TYPE_UNSET; random_exit = randomize_lines = unbuffer_output = 0; unique_output = 1; (void)setlocale(LC_CTYPE, ""); while ((ch = getopt(argc, argv, "ef:hlruUw")) != -1) switch (ch) { case 'e': random_exit = 1; break; case 'f': randomize_lines = 1; if (strcmp(optarg, "-") != 0) filename = optarg; break; case 'l': randomize_lines = 1; random_type = RANDOM_TYPE_LINES; break; case 'r': unbuffer_output = 1; break; case 'u': randomize_lines = 1; unique_output = 1; break; case 'U': randomize_lines = 1; unique_output = 0; break; case 'w': randomize_lines = 1; random_type = RANDOM_TYPE_WORDS; break; default: case '?': usage(); /* NOTREACHED */ } argc -= optind; argv += optind; switch (argc) { case 0: - denom = (randomize_lines ? 1 : 2); + denom = (randomize_lines ? 1. : 2.); break; case 1: errno = 0; denom = strtod(*argv, &ep); if (errno == ERANGE) err(1, "%s", *argv); - if (denom <= 0 || *ep != '\0') + if (denom < 1. || *ep != '\0') errx(1, "denominator is not valid."); - if (random_exit && denom > 256) + if (random_exit && denom > 256.) errx(1, "denominator must be <= 256 for random exit."); break; default: usage(); /* NOTREACHED */ } /* * Act as a filter, randomly choosing lines of the standard input * to write to the standard output. */ if (unbuffer_output) setbuf(stdout, NULL); /* * Act as a filter, randomizing lines read in from a given file * descriptor and write the output to standard output. */ if (randomize_lines) { if ((fd = open(filename, O_RDONLY, 0)) < 0) err(1, "%s", filename); ret = randomize_fd(fd, random_type, unique_output, denom); if (!random_exit) return(ret); } /* Compute a random exit status between 0 and denom - 1. */ if (random_exit) return (arc4random_uniform(denom)); /* - * Select whether to print the first line. (Prime the pump.) - * We find a random number between 0 and denom - 1 and, if it's - * 0 (which has a 1 / denom chance of being true), we select the - * line. + * Filter stdin, selecting lines with probability 1/denom, one + * character at a time. */ - selected = (arc4random_uniform(denom) == 0); - while ((ch = getchar()) != EOF) { - if (selected) - (void)putchar(ch); - if (ch == '\n') { - /* End of that line. See if we got an error. */ - if (ferror(stdout)) - err(2, "stdout"); - - /* Now see if the next line is to be printed. */ - selected = (arc4random_uniform(denom) == 0); + do { + selected = random_uniform_denom(denom); + if (selected) { + while ((ch = getchar()) != EOF) { + putchar(ch); + if (ch == '\n') + break; + } + } else { + while ((ch = getchar()) != EOF) + if (ch == '\n') + break; } - } + if (ferror(stdout)) + err(2, "stdout"); + } while (ch != EOF); if (ferror(stdin)) err(2, "stdin"); exit (0); } static void usage(void) { fprintf(stderr, "usage: random [-elrUuw] [-f filename] [denominator]\n"); exit(1); } Index: head/usr.bin/random/randomize_fd.c =================================================================== --- head/usr.bin/random/randomize_fd.c (revision 357974) +++ head/usr.bin/random/randomize_fd.c (revision 357975) @@ -1,248 +1,249 @@ /* * Copyright (C) 2003 Sean Chittenden * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #include __FBSDID("$FreeBSD$"); #include #include #include #include #include +#include #include #include #include #include #include #include "randomize_fd.h" static struct rand_node *rand_root; static struct rand_node *rand_tail; static struct rand_node * rand_node_allocate(void) { struct rand_node *n; n = (struct rand_node *)malloc(sizeof(struct rand_node)); if (n == NULL) err(1, "malloc"); n->len = 0; n->cp = NULL; n->next = NULL; return(n); } static void rand_node_free(struct rand_node *n) { if (n != NULL) { if (n->cp != NULL) free(n->cp); free(n); } } static void rand_node_free_rec(struct rand_node *n) { if (n != NULL) { if (n->next != NULL) rand_node_free_rec(n->next); rand_node_free(n); } } static void rand_node_append(struct rand_node *n) { if (rand_root == NULL) rand_root = rand_tail = n; else { rand_tail->next = n; rand_tail = n; } } int randomize_fd(int fd, int type, int unique, double denom) { u_char *buf; u_int slen; u_long i, j, numnode, selected; struct rand_node *n, *prev; int bufleft, eof, fndstr, ret; size_t bufc, buflen; ssize_t len; rand_root = rand_tail = NULL; bufc = i = 0; bufleft = eof = fndstr = numnode = 0; if (type == RANDOM_TYPE_UNSET) type = RANDOM_TYPE_LINES; buflen = sizeof(u_char) * MAXBSIZE; buf = (u_char *)malloc(buflen); if (buf == NULL) err(1, "malloc"); while (!eof) { /* Check to see if we have bits in the buffer */ if (bufleft == 0) { len = read(fd, buf, buflen); if (len == -1) err(1, "read"); else if (len == 0) { eof++; break; } else if ((size_t)len < buflen) buflen = (size_t)len; bufleft = (int)len; } /* Look for a newline */ for (i = bufc; i <= buflen && bufleft >= 0; i++, bufleft--) { if (i == buflen) { if (fndstr) { if (!eof) { memmove(buf, &buf[bufc], i - bufc); i -= bufc; bufc = 0; len = read(fd, &buf[i], buflen - i); if (len == -1) err(1, "read"); else if (len == 0) { eof++; break; } else if (len < (ssize_t)(buflen - i)) buflen = i + (size_t)len; bufleft = (int)len; fndstr = 0; } } else { buflen *= 2; buf = (u_char *)realloc(buf, buflen); if (buf == NULL) err(1, "realloc"); if (!eof) { len = read(fd, &buf[i], buflen - i); if (len == -1) err(1, "read"); else if (len == 0) { eof++; break; } else if (len < (ssize_t)(buflen - i)) buflen = i + (size_t)len; bufleft = (int)len; } } } if ((type == RANDOM_TYPE_LINES && buf[i] == '\n') || (type == RANDOM_TYPE_WORDS && isspace(buf[i])) || (eof && i == buflen - 1)) { make_token: if (numnode == UINT32_MAX - 1) { errno = EFBIG; err(1, "too many delimiters"); } numnode++; n = rand_node_allocate(); if (-1 != (int)i) { slen = i - (u_long)bufc; n->len = slen + 2; n->cp = (u_char *)malloc(slen + 2); if (n->cp == NULL) err(1, "malloc"); memmove(n->cp, &buf[bufc], slen); n->cp[slen] = buf[i]; n->cp[slen + 1] = '\0'; bufc = i + 1; } rand_node_append(n); fndstr = 1; } } } /* Necessary evil to compensate for files that don't end with a newline */ if (bufc != i) { i--; goto make_token; } (void)close(fd); free(buf); for (i = numnode; i > 0; i--) { selected = arc4random_uniform(numnode); for (j = 0, prev = n = rand_root; n != NULL; j++, prev = n, n = n->next) { if (j == selected) { if (n->cp == NULL) break; - if (arc4random_uniform(denom) == 0) { + if (random_uniform_denom(denom)) { 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; if (n == rand_tail) rand_tail = prev; prev->next = n->next; rand_node_free(n); numnode--; } break; } } } fflush(stdout); if (!unique) rand_node_free_rec(rand_root); return(0); } Index: head/usr.bin/random/randomize_fd.h =================================================================== --- head/usr.bin/random/randomize_fd.h (revision 357974) +++ head/usr.bin/random/randomize_fd.h (revision 357975) @@ -1,45 +1,81 @@ /* * Copyright (C) 2003 Sean Chittenden * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE PROJECT AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE PROJECT OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. * * $FreeBSD$ */ #ifndef __RANDOMIZE_FD__ #define __RANDOMIZE_FD__ #define RANDOM_TYPE_UNSET 0 #define RANDOM_TYPE_LINES 1 #define RANDOM_TYPE_WORDS 2 /* The multiple instance single integer key */ struct rand_node { u_char *cp; u_int len; struct rand_node *next; }; int randomize_fd(int fd, int type, int unique, double denom); +/* + * Generates a random number uniformly in the range [0.0, 1.0). + */ +static inline double +random_unit_float(void) +{ + static const uint64_t denom = (1ull << 53); + static const uint64_t mask = denom - 1; + + uint64_t rand64; + + /* + * arc4random_buf(...) in this use generates integer outputs in [0, + * UINT64_MAX]. + * + * The double mantissa only has 53 bits, so we uniformly mask off the + * high 11 bits and then floating-point divide by 2^53 to achieve a + * result in [0, 1). + * + * We are not allowed to emit 1.0, so denom must be one greater than + * the possible range of the preceeding step. + */ + arc4random_buf(&rand64, sizeof(rand64)); + rand64 &= mask; + return ((double)rand64 / denom); +} + +/* + * Returns true with probability 1 / denom (a floating point number >= 1). + * Otherwise, returns false. + */ +static inline bool +random_uniform_denom(double denom) +{ + return ((uint64_t)(denom * random_unit_float()) == 0); +} #endif