On Fri, Aug 05, 2022 at 02:12:35PM -0500, luci...@bronze.ctrl-c.club wrote:
> So this is the final verison of the patch solving the following
> problems:
>
> >The program is broken in multiple ways: return value clamping, casting
> >from double to uint32_t, wrong error checking for putchar, lack of
> >warnings when compiling.
>
> Now the program is more pedantic and complicated, but at least it does
> what is says in the man page.
>
> Ok, deraadt, tb?
Pretty much. Below is my suggestion, based on yours.
> +CFLAGS=-Wall -Wconversion
I dropped these again. I don't think -Wconversion is helpful here. It
doesn't understand the semantics of arc4random_buf(), so it whines for
no good reason. I can be convinced to add -Wall.
I pulled Campbell's license and code up to the top, in particular, we
can avoid prototypes. I switched a few variables from unsigned to int
since that makes more sense to me. I dropped the error check to
fprintf().
I dealt with -e differently than in your diff: reject denominators < 1
since those makes no sense. Document that. If -e is given, make sure
denom is at most 256, this way arc4random_uniform() will return a value
between 0 and 255, which exit() will not truncate. The nature of -e is
that we can't signal an error via return value, so we had better
succeed.
Other than that, I think this is good to go in. Surely the manual could
be improved...
Index: random.6
===================================================================
RCS file: /cvs/src/games/random/random.6,v
retrieving revision 1.7
diff -u -p -r1.7 random.6
--- random.6 31 May 2007 19:19:18 -0000 1.7
+++ random.6 5 Aug 2022 20:24:45 -0000
@@ -43,9 +43,10 @@
.Nm
reads lines from the standard input and copies them to the standard
output with a probability of 1/denominator.
-The default value for
+The
.Ar denominator
-is 2.
+must be at least 1,
+its default value is 2.
.Pp
The options are as follows:
.Bl -tag -width Ds
@@ -55,7 +56,7 @@ If the
option is specified,
.Nm
does not read or write anything, and simply exits with a random
-exit value of 0 to
+exit value of 0 to the minimum of 255 and
.Ar denominator
\&- 1, inclusive.
.It Fl r
Index: random.c
===================================================================
RCS file: /cvs/src/games/random/random.c,v
retrieving revision 1.20
diff -u -p -r1.20 random.c
--- random.c 7 Mar 2016 12:07:56 -0000 1.20
+++ random.c 5 Aug 2022 20:30:53 -0000
@@ -33,8 +33,35 @@
* SUCH DAMAGE.
*/
+/*-
+ * Copyright (c) 2014 Taylor R. Campbell
+ * 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 AUTHOR 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 AUTHOR 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 <err.h>
#include <errno.h>
+#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
@@ -42,6 +69,101 @@
__dead void usage(void);
int
+clz64(uint64_t x)
+{
+ static const uint64_t mask[] = {
+ 0xffffffff00000000, 0xffff0000, 0xff00, 0xf0, 0xc, 0x2,
+ };
+ static const int zeroes[] = {
+ 32, 16, 8, 4, 2, 1,
+ };
+ int clz = 0;
+ int i;
+
+ if (x == 0)
+ return 64;
+
+ for (i = 0; i < 6; i++) {
+ if ((x & mask[i]) == 0)
+ clz += zeroes[i];
+ else
+ x >>= zeroes[i];
+ }
+
+ return clz;
+}
+
+uint64_t
+random64(void)
+{
+ uint64_t r;
+
+ arc4random_buf(&r, sizeof(uint64_t));
+
+ return r;
+}
+
+/*
+ * random_real: Generate a stream of bits uniformly at random and
+ * interpret it as the fractional part of the binary expansion of a
+ * number in [0, 1], 0.00001010011111010100...; then round it.
+ */
+double
+random_real(void)
+{
+ int exponent = -64;
+ uint64_t significand;
+ int shift;
+
+ /*
+ * Read zeros into the exponent until we hit a one; the rest
+ * will go into the significand.
+ */
+ while (__predict_false((significand = random64()) == 0)) {
+ exponent -= 64;
+ /*
+ * If the exponent falls below -1074 = emin + 1 - p,
+ * the exponent of the smallest subnormal, we are
+ * guaranteed the result will be rounded to zero. This
+ * case is so unlikely it will happen in realistic
+ * terms only if random64 is broken.
+ */
+ if (__predict_false(exponent < -1074))
+ return 0;
+ }
+
+ /*
+ * There is a 1 somewhere in significand, not necessarily in
+ * the most significant position. If there are leading zeros,
+ * shift them into the exponent and refill the less-significant
+ * bits of the significand. Can't predict one way or another
+ * whether there are leading zeros: there's a fifty-fifty
+ * chance, if random64 is uniformly distributed.
+ */
+ shift = clz64(significand);
+ if (shift != 0) {
+ exponent -= shift;
+ significand <<= shift;
+ significand |= (random64() >> (64 - shift));
+ }
+
+ /*
+ * Set the sticky bit, since there is almost surely another 1
+ * in the bit stream. Otherwise, we might round what looks
+ * like a tie to even when, almost surely, were we to look
+ * further in the bit stream, there would be a 1 breaking the
+ * tie.
+ */
+ significand |= 1;
+
+ /*
+ * Finally, convert to double (rounding) and scale by
+ * 2^exponent.
+ */
+ return ldexp((double)significand, exponent);
+}
+
+int
main(int argc, char *argv[])
{
double denom;
@@ -77,16 +199,20 @@ main(int argc, char *argv[])
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.");
break;
default:
- usage();
+ usage();
}
- /* Compute a random exit status between 0 and denom - 1. */
- if (random_exit)
- return (arc4random_uniform(denom));
+ /* Return a random exit status between 0 and min(denom - 1, 255). */
+ if (random_exit) {
+ if (denom > 256)
+ denom = 256;
+
+ return arc4random_uniform(denom);
+ }
/*
* Act as a filter, randomly choosing lines of the standard input
@@ -94,25 +220,26 @@ main(int argc, char *argv[])
*/
if (unbuffer_output)
setvbuf(stdout, NULL, _IONBF, 0);
-
+
/*
* 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.
*/
- selected = arc4random_uniform(denom) == 0;
+ selected = random_real() < 1 / denom;
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");
+ int retch;
- /* Now see if the next line is to be printed. */
- selected = arc4random_uniform(denom) == 0;
+ if (selected) {
+ errno = 0;
+ retch = putchar(ch);
+ if (retch == EOF && errno)
+ err(2, "putchar");
}
+ if (ch == '\n')
+ /* Now see if the next line is to be printed. */
+ selected = random_real() < 1 / denom;
}
if (ferror(stdin))
err(2, "stdin");
