[LLVMbugs] [Bug 24267] New: uniform_int_distribution may not be uniform in certain conditions

[bugzilla-daemon at llvm.org]

https://llvm.org/bugs/show_bug.cgi?id=24267

            Bug ID: 24267
           Summary: uniform_int_distribution may not be uniform in certain
                    conditions
           Product: libc++
           Version: unspecified
          Hardware: Other
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: sneves at dei.uc.pt
                CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
    Classification: Unclassified

The libc++ uniform_int_distribution algorithm works, essentially, by figuring
out the number of bits in the specified range [a, b], and then generating
numbers with that amount of bits until it hits one within range. It does this
by (details abridged)

  const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1);
  const size_t _Dt = numeric_limits<_UIntType>::digits;
  size_t __w = _Dt - __clz(_Rp) - 1;
  if ((_Rp & (_UIntType(~0) >> (_Dt - __w))) != 0)
    ++__w;

Suppose _UIntType = uint64_t, a = 0, and b = 2^32. Suppose further that we are
working in a one's complement architecture (unlikely, I know). Then, if
negative zero is accepted as a non-trapped representation, uint64_t(~0) =
uint64_t(-0) = 0, and the number of bits will be one less than intended. In
particular, the value 2^32 will never be selected.

The fix to this is simple and painless: replace _UIntType(~0) by _UIntType(-1),
which is guaranteed to always convert correctly, even outside two's complement.
Or even better, std::numeric_limits<_UIntType>::max().

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20150726/386dcffd/attachment.html>