#28 6.4.2 and 7.0.0 `random` computed a span wider than the integer type

[Batch Job 1]

random computed a span wider than the integer type

What happened. Asking for a random integer over a wide range computed the range's width in a type that cannot hold it.

(random 0 9223372036854775807)
(random -9223372036854775808 9223372036854775807)
(random -9223372036854775808 -1)

Under -fsanitize=signed-integer-overflow each of those reports at miscfun.c. The first overflows on the + 1; the second on the subtraction, whose mathematical result is 2⁶⁴ − 1.

Why it is a fix and not a preference. Section 12.7.4 says the two arguments limit the integer returned, and both of these are integers the manual puts in range — section 2.3.1 makes the type a C long long, and (random 0 9223372036854775807) names its two ends. A call made entirely of values in range should not take the implementation through a construct the C standard leaves undefined.

The answers do not change on this host, which is why this was declined once. reports/README.md recorded the reason, and the reason was about the result: genrand returns a non-negative int, so the value handed back stays inside the two limits however the span wrapped. That is still true. What it did not account for is that the span is computed before the result is, and the overflow is in the span.

Where it came from. RandomFunction in clips_core_source_642/core/miscfun.c:

      rv = begin + (rv % ((end - begin) + 1));

begin, end and rv are all long long. Three of the operations can overflow:

• end - begin whenever the two bounds are more than LLONG_MAX apart,
• (end - begin) + 1 whenever the difference is exactly LLONG_MAX,
• and if the span wrapped to zero, rv % span is a division by zero rather than an overflow.

The change. The span is computed in unsigned long long, where the arithmetic is defined for every pair of bounds. A span of zero means the range covers the whole type, so every value is inside it and the generated value is used as it stands rather than divided by zero.

      span = ((unsigned long long) end - (unsigned long long) begin) + 1ULL;

      if (span == 0ULL)
        { offset = (unsigned long long) rv; }
      else
        { offset = ((unsigned long long) rv) % span; }

      rv = begin + (long long) offset;

The last line stays in long long without a conversion that could be surprising: genrand returns a non-negative int, and offset is no larger than that, so begin + offset is both inside the type and no greater than end. For every range narrow enough that the old expression did not overflow, span holds the same number it did and the result is the same.

What was checked. run-fix-tests.sh builds the core twice under -fsanitize=signed-integer-overflow, once as it stands and once with the single expression put back, and the two disagree about whether miscfun.c reports.

tests/wide-ranges.clp guards the answers. Two thousand draws from each of the four ranges whose width does not fit the type, and from five ordinary ranges including both pairs at the extremes, with every draw tested against both limits and for being an integer. Three one-value ranges — an ordinary one and both ends of the type — where the draw has to be that exact value. And the number of distinct values drawn over zero to nine, which is ten, because a generator that answered a single constant would pass every other check here.

The whole of ../../v1/fact-functions/tests gives identical output, and every other suite under ../ and ../../clips-optimizations/ passes.

Still present upstream. CLIPS 7.0.0 has the same expression in core/miscfun.c.