bug#32605: 26.1; (random) never returns negative

bug#32605: 26.1; (random) never returns negative

[Francis Wright]

According to my reading of both the documentation for the function
random and its description in the manual, if it is called with no
argument then "the value might be any integer representable in Lisp,
i.e., an integer between ‘most-negative-fixnum’ and
‘most-positive-fixnum’".  Therefore, it should return a negative integer
half the time, but I have never yet seen it return a negative value.  So
either the documentation or the implementation is wrong.  For what it's
worth, I would prefer the documented behaviour over the current actual
behaviour.


In GNU Emacs 26.1 (build 1, x86_64-w64-mingw32)
 of 2018-05-30 built on CIRROCUMULUS
Repository revision: 07f8f9bc5a51f5aa94eb099f3e15fbe0c20ea1ea
Windowing system distributor 'Microsoft Corp.', version 10.0.17134
Recent messages:
Canceling debug-on-entry for all functions
You can run the command ‘cancel-debug-on-entry’ with M-x ca-d-e RET
Canceling debug-on-entry for all functions
1515484088033472457 / 2067076301065092720
t [2 times]
Mark set [2 times]
Saving file c:/Users/fjw/REDUCE@SourceForge/emacs/REDUCE/Big Integer Support/eslbigint.el...
Wrote c:/Users/fjw/REDUCE@SourceForge/emacs/REDUCE/Big Integer Support/eslbigint.el
Type "q" in help window to restore its previous buffer.
mwheel-scroll: End of buffer [6 times]
mwheel-scroll: Beginning of buffer [9 times]
Configured using:
 'configure --without-dbus --host=x86_64-w64-mingw32
 --without-compress-install 'CFLAGS=-O2 -static -g3''

Configured features:
XPM JPEG TIFF GIF PNG RSVG SOUND NOTIFY ACL GNUTLS LIBXML2 ZLIB
TOOLKIT_SCROLL_BARS THREADS LCMS2

Important settings:
  value of $LANG: ENG
  locale-coding-system: cp1252

Major mode: Info

Minor modes in effect:
  diff-auto-refine-mode: t
  shell-dirtrack-mode: t
  show-paren-mode: t
  delete-selection-mode: t
  electric-pair-mode: t
  tooltip-mode: t
  global-eldoc-mode: t
  electric-indent-mode: t
  mouse-wheel-mode: t
  tool-bar-mode: t
  menu-bar-mode: t
  file-name-shadow-mode: t
  global-font-lock-mode: t
  font-lock-mode: t
  blink-cursor-mode: t
  auto-composition-mode: t
  auto-encryption-mode: t
  auto-compression-mode: t
  buffer-read-only: t
  line-number-mode: t
  transient-mark-mode: t

Load-path shadows:
None found.

Features:
(shadow sort mail-extr emacsbug message rmc puny rfc822 mml mml-sec epa
derived epg gnus-util rmail rmail-loaddefs mm-decode mm-bodies mm-encode
mail-parse rfc2231 mailabbrev gmm-utils mailheader sendmail rfc2047
rfc2045 ietf-drums mm-util mail-prsvr mail-utils info eieio-opt speedbar
sb-image ezimage dframe find-func help-fns radix-tree cl-extra thingatpt
misearch multi-isearch edebug reposition time-stamp help-mode cl-print
debug vc-git diff-mode easy-mmode vc-dispatcher vc-svn dired
dired-loaddefs flyspell ispell imenu tramp tramp-compat tramp-loaddefs
trampver ucs-normalize shell pcomplete comint ansi-color ring parse-time
format-spec advice paren delsel cus-start cus-load finder-inf package
easymenu epg-config url-handlers url-parse auth-source cl-seq eieio
eieio-core cl-macs eieio-loaddefs password-cache url-vars seq byte-opt
gv bytecomp byte-compile cconv cl-loaddefs cl-lib elec-pair server
time-date mule-util tooltip eldoc electric uniquify ediff-hook vc-hooks
lisp-float-type mwheel dos-w32 ls-lisp disp-table term/w32-win w32-win
w32-vars term/common-win tool-bar dnd fontset image regexp-opt fringe
tabulated-list replace newcomment text-mode elisp-mode lisp-mode
prog-mode register page menu-bar rfn-eshadow isearch timer select
scroll-bar mouse jit-lock font-lock syntax facemenu font-core
term/tty-colors frame cl-generic cham georgian utf-8-lang misc-lang
vietnamese tibetan thai tai-viet lao korean japanese eucjp-ms cp51932
hebrew greek romanian slovak czech european ethiopic indian cyrillic
chinese composite charscript charprop case-table epa-hook jka-cmpr-hook
help simple abbrev obarray minibuffer cl-preloaded nadvice loaddefs
button faces cus-face macroexp files text-properties overlay sha1 md5
base64 format env code-pages mule custom widget hashtable-print-readable
backquote w32notify w32 lcms2 multi-tty make-network-process emacs)

Memory information:
((conses 16 277958 12135)
 (symbols 56 26263 1)
 (miscs 48 215 603)
 (strings 32 53052 3399)
 (string-bytes 1 1403187)
 (vectors 16 43081)
 (vector-slots 8 801770 16514)
 (floats 8 79 425)
 (intervals 56 1601 17)
 (buffers 992 18))

bug#32605: 26.1; (random) never returns negative

[Stephen Berman]

On Sat, 01 Sep 2018 18:18:01 +0100 Francis Wright <francis.j.wright@gmail.com> wrote:

> According to my reading of both the documentation for the function
> random and its description in the manual, if it is called with no
> argument then "the value might be any integer representable in Lisp,
> i.e., an integer between ‘most-negative-fixnum’ and
> ‘most-positive-fixnum’".  Therefore, it should return a negative integer
> half the time, but I have never yet seen it return a negative value.  So
> either the documentation or the implementation is wrong.  For what it's
> worth, I would prefer the documented behaviour over the current actual
> behaviour.
>
>
> In GNU Emacs 26.1 (build 1, x86_64-w64-mingw32)
>  of 2018-05-30 built on CIRROCUMULUS
> Repository revision: 07f8f9bc5a51f5aa94eb099f3e15fbe0c20ea1ea
> Windowing system distributor 'Microsoft Corp.', version 10.0.17134

Prompted by this report, I just ran `M-: (random)' twice, with these
results:

1407814790132564328 (#o116114401367331100550, #x13899017bb648168)
-5902216973509885 (#o-247600437205762375, #x-14f808fa17e4fd)

This was on a build from current master under GNU/Linux

Steve Berman

bug#32605: 26.1; (random) never returns negative

[Noam Postavsky]

retitle 32605 [w64] (random) never returns negative
tags 32605 + confirmed
quit

Stephen Berman <stephen.berman@gmx.net> writes:

> On Sat, 01 Sep 2018 18:18:01 +0100 Francis Wright <francis.j.wright@gmail.com> wrote:
>> Therefore, it should return a negative integer
>> half the time, but I have never yet seen it return a negative value.

>> In GNU Emacs 26.1 (build 1, x86_64-w64-mingw32)

> Prompted by this report, I just ran `M-: (random)' twice, with these
> results:
>
> 1407814790132564328 (#o116114401367331100550, #x13899017bb648168)
> -5902216973509885 (#o-247600437205762375, #x-14f808fa17e4fd)
>
> This was on a build from current master under GNU/Linux

This bug seems specific to 64 bit Windows builds.

bug#32605: 26.1; (random) never returns negative

[Andy Moreton]

On Tue 04 Sep 2018, Noam Postavsky wrote:

> retitle 32605 [w64] (random) never returns negative
> tags 32605 + confirmed
> quit
>
> Stephen Berman <stephen.berman@gmx.net> writes:
>
>> On Sat, 01 Sep 2018 18:18:01 +0100 Francis Wright <francis.j.wright@gmail.com> wrote:
>>> Therefore, it should return a negative integer
>>> half the time, but I have never yet seen it return a negative value.
>
>>> In GNU Emacs 26.1 (build 1, x86_64-w64-mingw32)
>
>> Prompted by this report, I just ran `M-: (random)' twice, with these
>> results:
>>
>> 1407814790132564328 (#o116114401367331100550, #x13899017bb648168)
>> -5902216973509885 (#o-247600437205762375, #x-14f808fa17e4fd)
>>
>> This was on a build from current master under GNU/Linux
>
> This bug seems specific to 64 bit Windows builds.

ON 64bit Windows, sysdep.c sets RAND_BITS to 31, but random (in w32.c)
only provides 30 bits. It looks like the mixing in get_random does not
result in the top fixnum bit being set.

    AndyM

bug#32605: [w64] (random) never returns negative

[Lars Ingebrigtsen]

Andy Moreton <andrewjmoreton@gmail.com> writes:

>> This bug seems specific to 64 bit Windows builds.
>
> ON 64bit Windows, sysdep.c sets RAND_BITS to 31, but random (in w32.c)
> only provides 30 bits. It looks like the mixing in get_random does not
> result in the top fixnum bit being set.

So it's this:

int
random (void)
{
  /* rand_as183 () gives us 15 random bits...hack together 30 bits.  */
  return ((rand_as183 () << 15) | rand_as183 ());
}

So running rand_as183 and taking another bit from that might do the
trick?  Eli, do you have any comments here?

-- 
(domestic pets only, the antidote for overdose, milk.)
   bloggy blog: http://lars.ingebrigtsen.no

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Lars Ingebrigtsen <larsi@gnus.org>
> Cc: 32605@debbugs.gnu.org, Eli Zaretskii <eliz@gnu.org>
> Date: Thu, 12 Aug 2021 15:17:46 +0200
> 
> Andy Moreton <andrewjmoreton@gmail.com> writes:
> 
> >> This bug seems specific to 64 bit Windows builds.
> >
> > ON 64bit Windows, sysdep.c sets RAND_BITS to 31, but random (in w32.c)
> > only provides 30 bits. It looks like the mixing in get_random does not
> > result in the top fixnum bit being set.
> 
> So it's this:
> 
> int
> random (void)
> {
>   /* rand_as183 () gives us 15 random bits...hack together 30 bits.  */
>   return ((rand_as183 () << 15) | rand_as183 ());
> }
> 
> So running rand_as183 and taking another bit from that might do the
> trick?  Eli, do you have any comments here?

The 'random' emulation in w32.c was never adapted to w64.

Instead of calling rand_as183 one more time, perhaps it's better to
trivially transform the value we have?  Something like

    int val = ((rand_as183 () << 15) | rand_as183 ());
  #ifdef __x86_64__
    return 2 * val - 0x3FFFFFFF;
  #else
    return val;
  #endif

Andy, can you test this, please?

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Thu 12 Aug 2021, Eli Zaretskii wrote:

>> From: Lars Ingebrigtsen <larsi@gnus.org>
>> Cc: 32605@debbugs.gnu.org, Eli Zaretskii <eliz@gnu.org>
>> Date: Thu, 12 Aug 2021 15:17:46 +0200
>> 
>> Andy Moreton <andrewjmoreton@gmail.com> writes:
>> 
>> >> This bug seems specific to 64 bit Windows builds.
>> >
>> > ON 64bit Windows, sysdep.c sets RAND_BITS to 31, but random (in w32.c)
>> > only provides 30 bits. It looks like the mixing in get_random does not
>> > result in the top fixnum bit being set.
>
> The 'random' emulation in w32.c was never adapted to w64.

Surely real the problem is that RAND_BITS is 31, but the random() in
w32.c does not provide 31 random bits (and thus fails to meet the API
contract).

In 32bit builds this problem is hidden because 30 bits are sufficient
for a fixnum, so the value of bit30 in the result is ignored.

On 64bit builds, 62 bits are needed for a fixnum, and trying to assemble
a random number from multiple components does not work if RAND_BITS says
31 bits are usable, but the highest bit in that value is always zero.

Also see 

> Instead of calling rand_as183 one more time, perhaps it's better to
> trivially transform the value we have?  Something like
>
>     int val = ((rand_as183 () << 15) | rand_as183 ());
>   #ifdef __x86_64__
>     return 2 * val - 0x3FFFFFFF;
>   #else
>     return val;
>   #endif
>
> Andy, can you test this, please?

That does not produce any negative random numbers within a reasonable
number of attempts (a few dozen calls).

Instead, calling rand_as183 again (as below) does produce positive and
negative random numbers on 32bit and 64bit builds with a similar number
of attempts:

return ((rand_as183 () << 30) | (rand_as183 () << 15) | rand_as183 ());

While this may be less efficient, it at least meets the contract of
providing 31 random bits.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Thu, 12 Aug 2021 21:34:09 +0100
> 
> >     int val = ((rand_as183 () << 15) | rand_as183 ());
> >   #ifdef __x86_64__
> >     return 2 * val - 0x3FFFFFFF;
> >   #else
> >     return val;
> >   #endif
> >
> > Andy, can you test this, please?
> 
> That does not produce any negative random numbers within a reasonable
> number of attempts (a few dozen calls).

Thanks for testing.

> Instead, calling rand_as183 again (as below) does produce positive and
> negative random numbers on 32bit and 64bit builds with a similar number
> of attempts:
> 
> return ((rand_as183 () << 30) | (rand_as183 () << 15) | rand_as183 ());
> 
> While this may be less efficient, it at least meets the contract of
> providing 31 random bits.

What about the variant below, does it produce better results?

    int val = ((rand_as183 () << 15) | rand_as183 ());
  #ifdef __x86_64__
    return 2 * val - 0x7FFFFFFF;
  #else
    return val;
  #endif

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Fri 13 Aug 2021, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Thu, 12 Aug 2021 21:34:09 +0100
>> 
>> >     int val = ((rand_as183 () << 15) | rand_as183 ());
>> >   #ifdef __x86_64__
>> >     return 2 * val - 0x3FFFFFFF;
>> >   #else
>> >     return val;
>> >   #endif
>> >
>> > Andy, can you test this, please?
>> 
>> That does not produce any negative random numbers within a reasonable
>> number of attempts (a few dozen calls).
>
> Thanks for testing.

You elided the detail of my previous message:

  Surely real the problem is that RAND_BITS is 31, but the random() in
  w32.c does not provide 31 random bits (and thus fails to meet the API
  contract).

  In 32bit builds this problem is hidden because 30 bits are sufficient
  for a fixnum, so the value of bit30 in the result is ignored.

  On 64bit builds, 62 bits are needed for a fixnum, and trying to assemble
  a random number from multiple components does not work if RAND_BITS says
  31 bits are usable, but the highest bit in that value is always zero.

Please answer that. This function appears to not work properly at all.

>> Instead, calling rand_as183 again (as below) does produce positive and
>> negative random numbers on 32bit and 64bit builds with a similar number
>> of attempts:
>> 
>> return ((rand_as183 () << 30) | (rand_as183 () << 15) | rand_as183 ());
>> 
>> While this may be less efficient, it at least meets the contract of
>> providing 31 random bits.
>
> What about the variant below, does it produce better results?
>
>     int val = ((rand_as183 () << 15) | rand_as183 ());
>   #ifdef __x86_64__
>     return 2 * val - 0x7FFFFFFF;
>   #else
>     return val;
>   #endif

Why is this any better ? On 32bit builds it does not return 31 random
bits (only a 30bit value) and on 64bit builds the lowest bit is not
random.

I'm not sure I see the point of this bit manipulation as it does not
spread randomness throughout the bits in the returned value.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Fri, 13 Aug 2021 22:12:29 +0100
> 
> You elided the detail of my previous message:

Because I had nothing useful to say in response.  If someone wants to
work on a better emulation of 'random' for w64, that's fine; I don't
consider myself an expert in this area, and therefore not sure I even
understand the significance of providing 31 bits of randomness from a
functions such as 'random', which AFAIR is not the standard of RNGs.
My goal was to make the current implementation better with relatively
simple and straightforward changes.  Calling rand_as183 one more time
is IMHO not a good solution; but again, I'm not an expert.

> > What about the variant below, does it produce better results?
> >
> >     int val = ((rand_as183 () << 15) | rand_as183 ());
> >   #ifdef __x86_64__
> >     return 2 * val - 0x7FFFFFFF;
> >   #else
> >     return val;
> >   #endif
> 
> Why is this any better ? On 32bit builds it does not return 31 random
> bits (only a 30bit value) and on 64bit builds the lowest bit is not
> random.

I hoped it will be better because it produced negative values as well,
not only positive values, without any performance penalty.  For a
problem that was left unsolved for 3 years it sounds good enough to
me.

So my proposal is to install the above until someone comes up with a
better solution.  But if that's unacceptable, let alone if my
participation in this discussion is an annoyance, like it seems to be,
I'll readily bow out of it.

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Sat 14 Aug 2021, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Fri, 13 Aug 2021 22:12:29 +0100
>> 
>> You elided the detail of my previous message:
>
> Because I had nothing useful to say in response.  If someone wants to
> work on a better emulation of 'random' for w64, that's fine; I don't
> consider myself an expert in this area, and therefore not sure I even
> understand the significance of providing 31 bits of randomness from a
> functions such as 'random', which AFAIR is not the standard of RNGs.
> My goal was to make the current implementation better with relatively
> simple and straightforward changes.  Calling rand_as183 one more time
> is IMHO not a good solution; but again, I'm not an expert.

Please look at get_random() in sysdep.c: it constructs wider random
numbers by concatenating random bits from calling random() in a loop,
and expects that the result of each call in that loop returns RAND_BITS
(defined in sysdep.c as 31 on this platform).

The random() replacement in w32.c does not meet this contract, as it
only provides 30 bits, causing get_random() to produce a concatenated
result containing bits with fixed, non-random values.

>> > What about the variant below, does it produce better results?
>> >
>> >     int val = ((rand_as183 () << 15) | rand_as183 ());
>> >   #ifdef __x86_64__
>> >     return 2 * val - 0x7FFFFFFF;
>> >   #else
>> >     return val;
>> >   #endif
>> 
>> Why is this any better ? On 32bit builds it does not return 31 random
>> bits (only a 30bit value) and on 64bit builds the lowest bit is not
>> random.
>
> I hoped it will be better because it produced negative values as well,
> not only positive values, without any performance penalty.  For a
> problem that was left unsolved for 3 years it sounds good enough to
> me.

There doesn't seem to be any point in making changes if they disguise a
bug rather than fixing it. Your proposal just changes which bits in the
the result are non-random.

> So my proposal is to install the above until someone comes up with a
> better solution.  But if that's unacceptable, let alone if my
> participation in this discussion is an annoyance, like it seems to be,
> I'll readily bow out of it.

As far as I can see the way to fix this is one of:
a) Fix random() in w32.c to return a 31 bit random number.

b) Modify the logic in sysdep.c that defines RAND_BITS to set it to 30
   on this platform, so get_random() produces working results.
   The get_random() loop would then need one call to random on 32bit
   builds (FIXNUM_BITS is 30), and three on 64bit builds (FIXNUM_BITS is 62).

I'm not an expert on random numbers either, and your efforts are not an
annoyance, but I am puzzled why you so strongly prize performance over
correctness in this instance.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Sat, 14 Aug 2021 09:31:06 +0100
> 
> I'm not an expert on random numbers either, and your efforts are not an
> annoyance, but I am puzzled why you so strongly prize performance over
> correctness in this instance.

Because I have no idea how important the "correctness" part is, or
why.  OTOH, this stuff, when used, tends to be in the inner loops, so
performance matters.

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Sat 14 Aug 2021, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Sat, 14 Aug 2021 09:31:06 +0100
>> 
>> I'm not an expert on random numbers either, and your efforts are not an
>> annoyance, but I am puzzled why you so strongly prize performance over
>> correctness in this instance.
>
> Because I have no idea how important the "correctness" part is, or
> why.  OTOH, this stuff, when used, tends to be in the inner loops, so
> performance matters.

I doubt anyone expects cryptographic quality randomness or any given
statistical distribution from such a general purpose routine, but they
have a reasonable expectation that the results from 'get_random' do not
have stuck bits that are always non-random.

In which case perhaps the solution is to change the RAND_BITS logic
in sysdep.c on Windows to override the RAND_BITS definition:

+   #ifdef WINDOWSNT
+   /* Use w32.c replacement for random().  */
+   # define RAND_BITS 15
+   #endif

    #ifndef RAND_BITS
    # ifdef HAVE_RANDOM
    #  define RAND_BITS 31
    # else /* !HAVE_RANDOM */
    ...
    #endif

..and then in w32.c make 'random' return the 15bit value from
'rand_as183':

    int
    random (void)
    {
      /* rand_as183 () gives us 15 random bits.  */
      return rand_as183 ();
    }

That should result in 'get_random' receiving 15 bits of randomness in
each loop iteration and thus computing a valid result.

[This could obviously be optimised to open code 'rand_as183' in 'random',
 or allow the compiler to inline it by moving the w32.c implementations
 of 'random' and 'srandom' into sysdep.c]

As 'get_random_bignum' (in fns.c) calls 'get_random' in a loop, that
should also remove bugs from that function on this platform.


Perhaps this would be helped by having a test for 'get_random', to check
that every bit of a fixnum is toggled after a reasonable number of
calls. While that does not test the statistical distribution of the
random number sequence, it would ensure that the values returned by
'get_random' are not always positive, or always even, etc.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Sat, 14 Aug 2021 12:06:00 +0100
> 
> >> I'm not an expert on random numbers either, and your efforts are not an
> >> annoyance, but I am puzzled why you so strongly prize performance over
> >> correctness in this instance.
> >
> > Because I have no idea how important the "correctness" part is, or
> > why.  OTOH, this stuff, when used, tends to be in the inner loops, so
> > performance matters.
> 
> I doubt anyone expects cryptographic quality randomness or any given
> statistical distribution from such a general purpose routine, but they
> have a reasonable expectation that the results from 'get_random' do not
> have stuck bits that are always non-random.
> 
> In which case perhaps the solution is to change the RAND_BITS logic
> in sysdep.c on Windows to override the RAND_BITS definition:
> 
> +   #ifdef WINDOWSNT
> +   /* Use w32.c replacement for random().  */
> +   # define RAND_BITS 15
> +   #endif
> 
>     #ifndef RAND_BITS
>     # ifdef HAVE_RANDOM
>     #  define RAND_BITS 31
>     # else /* !HAVE_RANDOM */
>     ...
>     #endif
> 
> ..and then in w32.c make 'random' return the 15bit value from
> 'rand_as183':

Why not keep the 30 bits we produce today on 32-bit builds?

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Sat 14 Aug 2021, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Sat, 14 Aug 2021 12:06:00 +0100
>> 
>> >> I'm not an expert on random numbers either, and your efforts are not an
>> >> annoyance, but I am puzzled why you so strongly prize performance over
>> >> correctness in this instance.
>> >
>> > Because I have no idea how important the "correctness" part is, or
>> > why.  OTOH, this stuff, when used, tends to be in the inner loops, so
>> > performance matters.
>> 
>> I doubt anyone expects cryptographic quality randomness or any given
>> statistical distribution from such a general purpose routine, but they
>> have a reasonable expectation that the results from 'get_random' do not
>> have stuck bits that are always non-random.
>> 
>> In which case perhaps the solution is to change the RAND_BITS logic
>> in sysdep.c on Windows to override the RAND_BITS definition:
>> 
>> +   #ifdef WINDOWSNT
>> +   /* Use w32.c replacement for random().  */
>> +   # define RAND_BITS 15
>> +   #endif
>> 
>>     #ifndef RAND_BITS
>>     # ifdef HAVE_RANDOM
>>     #  define RAND_BITS 31
>>     # else /* !HAVE_RANDOM */
>>     ...
>>     #endif
>> 
>> ..and then in w32.c make 'random' return the 15bit value from
>> 'rand_as183':
>
> Why not keep the 30 bits we produce today on 32-bit builds?

For 32bit builds (FIXNUM_BITS is 30), either:

 a) define RAND_BITS to 30, 'random' calls 'rand_as183' twice.
    'get_random' needs 1 call to 'random' (total 2 calls of 'rand_as183').

 b) define RAND_BITS to 15, 'random' calls 'rand_as183' once.
    'get_random' needs 2 calls to 'random' (total 2 calls of 'rand_as183').

For 64bit builds (FIXNUM_BITS is 62), either:

 a) define RAND_BITS to 30, 'random' calls 'rand_as183' twice.
    'get_random' needs 3 calls to 'random' (total 6 calls of 'rand_as183').

 b) define RAND_BITS to 15, 'random' calls 'rand_as183' once.
    'get_random' needs 4 calls to 'random' (total 4 calls of 'rand_as183').

On 32bit builds both options are roughly equivalent.
On 64bit builds option (b) is better as option (a) does unnecessary work.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Sat, 14 Aug 2021 13:10:08 +0100
> 
> > Why not keep the 30 bits we produce today on 32-bit builds?
> 
> For 32bit builds (FIXNUM_BITS is 30), either:
> 
>  a) define RAND_BITS to 30, 'random' calls 'rand_as183' twice.
>     'get_random' needs 1 call to 'random' (total 2 calls of 'rand_as183').
> 
>  b) define RAND_BITS to 15, 'random' calls 'rand_as183' once.
>     'get_random' needs 2 calls to 'random' (total 2 calls of 'rand_as183').
> 
> For 64bit builds (FIXNUM_BITS is 62), either:
> 
>  a) define RAND_BITS to 30, 'random' calls 'rand_as183' twice.
>     'get_random' needs 3 calls to 'random' (total 6 calls of 'rand_as183').
> 
>  b) define RAND_BITS to 15, 'random' calls 'rand_as183' once.
>     'get_random' needs 4 calls to 'random' (total 4 calls of 'rand_as183').
> 
> On 32bit builds both options are roughly equivalent.
> On 64bit builds option (b) is better as option (a) does unnecessary work.

The above assumes we will never call 'random' except via 'get_random'.
Is that something we want to bet on?

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Sat 14 Aug 2021, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Sat, 14 Aug 2021 13:10:08 +0100
>> 
>> > Why not keep the 30 bits we produce today on 32-bit builds?
>> 
>> For 32bit builds (FIXNUM_BITS is 30), either:
>> 
>>  a) define RAND_BITS to 30, 'random' calls 'rand_as183' twice.
>>     'get_random' needs 1 call to 'random' (total 2 calls of 'rand_as183').
>> 
>>  b) define RAND_BITS to 15, 'random' calls 'rand_as183' once.
>>     'get_random' needs 2 calls to 'random' (total 2 calls of 'rand_as183').
>> 
>> For 64bit builds (FIXNUM_BITS is 62), either:
>> 
>>  a) define RAND_BITS to 30, 'random' calls 'rand_as183' twice.
>>     'get_random' needs 3 calls to 'random' (total 6 calls of 'rand_as183').
>> 
>>  b) define RAND_BITS to 15, 'random' calls 'rand_as183' once.
>>     'get_random' needs 4 calls to 'random' (total 4 calls of 'rand_as183').
>> 
>> On 32bit builds both options are roughly equivalent.
>> On 64bit builds option (b) is better as option (a) does unnecessary work.
>
> The above assumes we will never call 'random' except via 'get_random'.
> Is that something we want to bet on?

Option (b) fixes bugs in the current code. Currently 'get_random' is the
only caller of 'random'.  If inefficiency is a problem after later code
changes, then then this issue can be revisited.

Another option is to replace the imlementation of 'random' in w32.c with
a different PRNG that can generate 31 bits more efficiently than using 3
calls to 'rand_as183'.

Yet another possibility is to use 'getrandom' from gnulib instead of all
of this Windows specific code, but that may bring a fresh set of
concerns to be considered.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Sat, 14 Aug 2021 14:40:35 +0100
> 
> >> On 32bit builds both options are roughly equivalent.
> >> On 64bit builds option (b) is better as option (a) does unnecessary work.
> >
> > The above assumes we will never call 'random' except via 'get_random'.
> > Is that something we want to bet on?
> 
> Option (b) fixes bugs in the current code. Currently 'get_random' is the
> only caller of 'random'.  If inefficiency is a problem after later code
> changes, then then this issue can be revisited.
> 
> Another option is to replace the imlementation of 'random' in w32.c with
> a different PRNG that can generate 31 bits more efficiently than using 3
> calls to 'rand_as183'.
> 
> Yet another possibility is to use 'getrandom' from gnulib instead of all
> of this Windows specific code, but that may bring a fresh set of
> concerns to be considered.

Thanks, I've decided to go with a hybrid approach that doesn't change
how 32-bit builds behaved up to now.

bug#32605: [w64] (random) never returns negative

[Andy Moreton]

On Sat 14 Aug 2021, Eli Zaretskii wrote:

>> From: Andy Moreton <andrewjmoreton@gmail.com>
>> Date: Sat, 14 Aug 2021 14:40:35 +0100
>> 
>> >> On 32bit builds both options are roughly equivalent.
>> >> On 64bit builds option (b) is better as option (a) does unnecessary work.
>> >
>> > The above assumes we will never call 'random' except via 'get_random'.
>> > Is that something we want to bet on?
>> 
>> Option (b) fixes bugs in the current code. Currently 'get_random' is the
>> only caller of 'random'.  If inefficiency is a problem after later code
>> changes, then then this issue can be revisited.
>> 
>> Another option is to replace the imlementation of 'random' in w32.c with
>> a different PRNG that can generate 31 bits more efficiently than using 3
>> calls to 'rand_as183'.
>> 
>> Yet another possibility is to use 'getrandom' from gnulib instead of all
>> of this Windows specific code, but that may bring a fresh set of
>> concerns to be considered.
>
> Thanks, I've decided to go with a hybrid approach that doesn't change
> how 32-bit builds behaved up to now.

That looks fine, and the bug reported by the OP now appears fixed in
testing on 32bit and 64bit builds.

    AndyM

bug#32605: [w64] (random) never returns negative

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Sat, 14 Aug 2021 19:47:22 +0100
> 
> On Sat 14 Aug 2021, Eli Zaretskii wrote:
> 
> > Thanks, I've decided to go with a hybrid approach that doesn't change
> > how 32-bit builds behaved up to now.
> 
> That looks fine, and the bug reported by the OP now appears fixed in
> testing on 32bit and 64bit builds.

Thanks for testing.