[libc++] Fix `uniform_int_distribution` for 128-bit result type
authorFabian Wolff <fabian.wolff@alumni.ethz.ch>
Wed, 1 Dec 2021 16:01:06 +0000 (11:01 -0500)
committerLouis Dionne <ldionne.2@gmail.com>
Wed, 1 Dec 2021 16:03:29 +0000 (11:03 -0500)
commitb254c2e2c4aa3298655282b8db37860129bcd7b6
tree63382a75af77bafd759dff65b3c92f896f09b499
parent415e821a5089d7b2a49cc8e1717702f46ffdae86
[libc++] Fix `uniform_int_distribution` for 128-bit result type

Fixes https://llvm.org/PR51520. The problem is that `uniform_int_distribution`
currently uses an unsigned integer with at most 64 bits internally, which
is then casted to the desired result type. If the result type is `int64_t`,
this will produce a negative number if the most significant bit is set,
but if the result type is `__int128_t`, the value remains non-negative
and will be out of bounds for the example in PR#51520. (The reason why
it also seems to work if the upper or lower bound is changed is
because the branch at [1] will then no longer be taken, and proper
rejection sampling takes place.)

The bigger issue here is probably that `uniform_int_distribution` can be
instantiated with `__int128_t` but will silently produce incorrect results
(only the lowest 64 bits can ever be set). libstdc++ also supports `__int128_t`
as a result type, so I have simply extended the maximum width of the
internal intermediate result type.

[1]: https://github.com/llvm/llvm-project/blob/6d28dffb6/libcxx/include/__random/uniform_int_distribution.h#L266-L267

Differential Revision: https://reviews.llvm.org/D114129
libcxx/include/__random/log2.h
libcxx/include/__random/uniform_int_distribution.h
libcxx/test/std/numerics/rand/rand.dis/rand.dist.uni/rand.dist.uni.int/int128.pass.cpp [new file with mode: 0644]