On Fri, Jan 06, 2023 at 09:00:30PM -0500, Greg Wooledge wrote: > On Sat, Jan 07, 2023 at 01:37:30AM +0000, Sam James wrote: > > random.c:79:21: runtime error: signed integer overflow: 31789 * 127773 > > cannot be represented in type 'int' > > #0 0x559791a301ce in intrand32 > > /usr/src/debug/app-shells/bash-5.2_p15/bash-5.2/lib/sh/random.c:79 > > Well, the code in question looks like this (with comments removed): > > static u_bits32_t > intrand32 (last) > u_bits32_t last; > { > bits32_t h, l, t; > u_bits32_t ret; > > ret = (last == 0) ? 123459876 : last; > h = ret / 127773; > l = ret - (127773 * h); > t = 16807 * l - 2836 * h; > ret = (t < 0) ? t + 0x7fffffff : t; > > return (ret); > }
> /* Minimal Standard generator from > "Random number generators: good ones are hard to find", > Park and Miller, Communications of the ACM, vol. 31, no. 10, > October 1988, p. 1195. Filtered through FreeBSD. I've now read the first half of the paper (it's easily readable up until the section entitled "THEORY"). Bash's C implementation is derived from this code presented in the paper: function Random : real; const a = 16807; m = 2147483647; q = 127773; (* m div a *) r = 2836; (* m mod a *) var lo, hi, test : integer; begin hi := seed div q; lo := seed mod q; test := a * lo - r * hi; if test > 0 then seed := test else seed := test + m; Random := seed / m end; with the additional global variable "seed" of type integer. The paper promises that no value will ever overflow a 32-bit variable, and specifically mentions that the "test" variable can safely be a 32-bit signed value. However, it's pretty clear that "hi" and "lo" are not signed values. Even when rewriting the mod calculation as a multiplication and a subtraction, "lo" (aka "l") should never be negative. I think this patch might be correct: --- lib/sh/random.c.orig 2023-01-07 12:26:09.049950519 -0500 +++ lib/sh/random.c 2023-01-07 12:26:27.469974730 -0500 @@ -70,8 +70,8 @@ There are lots of other combinations of constants to use; look at https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html#Other-random-number-generators */ - bits32_t h, l, t; - u_bits32_t ret; + bits32_t t; + u_bits32_t h, l, ret; /* Can't seed with 0. */ ret = (last == 0) ? 123459876 : last; I tested it briefly, and it builds cleanly and produces the same random results as the unpatched version, at least on my system (compiled with gcc 10.2.1).