#31 6.4.2 and 7.0.0 `HashInteger` negated the most negative integer

[Batch Job 1]

HashInteger negated the most negative integer

What happened. Reading the most negative integer performed an undefined negation.

(assert (data -9223372036854775808))

Built with -fsanitize=signed-integer-overflow, that reports symbol.c:855:29: runtime error: negation of -9223372036854775808 cannot be represented in type 'long long'; cast to an unsigned type to negate this value to itself.

The value is the one the manual documents as the lower end of the integer type. Nothing has to go wrong for a program to write it.

Why it is a fix and not a preference. Section 2.3.1 says an integer is "represented internally by CLIPS as a C long long integer", and Appendix F documents SCANNER1 as the warning for "an integer is outside of the range of values that can be represented in the C long long integer type". So the documented range is exactly the range of long long, and this value is the bottom of it. CLIPS agrees:

CLIPS> -9223372036854775808
-9223372036854775808
CLIPS> -9223372036854775809
[SCANNER1] WARNING: Over or underflow of long long integer.
-9223372036854775808

The first is accepted in silence. The second is refused as out of range and clamped — to the first. A value the manual puts in range, and that out-of-range input is clamped to, should not take the implementation through a construct the C standard leaves undefined.

Nor is it avoidable. The literal, a value computed by arithmetic, a value clamped from a larger numeral, and a value read back out of a slot are all the same integer, and HashInteger is how each of them gets interned.

Where it came from. HashInteger in clips_core_source_642/core/symbol.c:

#if WIN_MVC
   if (number < 0)
     { number = - number; }
   tally = (((size_t) number) % range);
#else
   tally = (((size_t) llabs(number)) % range);
#endif

Both branches are undefined for this input. Negating the most negative long long overflows, which is what the WIN_MVC branch does directly. llabs of it is undefined by the same argument, and clang lowers llabs to a negation, which is why the sanitizer sees it on platforms taking the second branch.

The change. One path for every platform, because nothing here was platform dependent in the first place. The negation is carried through unsigned long long, where it is defined, and gives the same magnitude llabs gives for every value llabs can handle.

   if (number < 0)
     { tally = (size_t) (- (unsigned long long) number); }
   else
     { tally = (size_t) number; }

On this host the hash value does not move. llabs of the most negative integer leaves it unchanged, and converting that to size_t gives 2⁶³ — which is also the correct magnitude, so both arrive at bucket 2048. What changes is that the computation is now defined for every input, rather than relying on the wrap a compiler is entitled to assume cannot happen.

A second defect in the same function. 6.4.2 computes % range and then tests range == 0, so the test cannot prevent the division it appears to guard:

   tally = (((size_t) llabs(number)) % range);

   if (range == 0)
     { return tally; }

   return tally;

Both arms return the same value, which is what makes it look like dead code rather than a misordering. CLIPS 7.0.0 fixes it by taking the remainder after the guard, and this adopts that order. Nothing in CLIPS reaches it — INTEGER_HASH_SIZE is 8191 at both call sites in symbol.c, and utility.c passes a hash table's size — so there is no test for it here and none is claimed.

Still present upstream. CLIPS 7.0.0 has the same two branches at core/symbol.c. It fixed the misordered guard and left the negation.