Hacker News Reader

Comment by cesarb | Hacker News Reader

> because any arithmetic just silently does the wrong thing

The same thing, but worse, can happen with signed integers. (-3)-INT_MAX is either some huge positive number, or something crazy because it's undefined behavior and the compiler is allowed to do anything it wants.

View on HN

I guess what the parent is saying is that, while the same kind of bugs can happen with signed integers, they are less common than with unsigned integers because they typically involve very big or very small values such as INT_MAX or INT_MIN. This is due to the fact that the "most common values" (close to 0) are at the beginning of the range of unsigned integers, but at the middle of the range of signed integers, so the risk of underflow is lower for signed integers in practice.

I can understand where they come from, especially regarding error handling: for integers whose value must not be negative, it is easier to check for underflow by checking if the result is not negative rather than by checking that the result is not eg smaller than the previous value (eg for addition).

That being said, "number must not be negative" really ought to be encoded in the type system, so that the user of the type knows that they must actually look for underflow.

I guess that part of the problem is that we don't want to check for underflow after each operation, so checking the negativity is a way to "coalesce" several checks after multiple operations. However this is fragile, because the multiple operations could end up producing a positive value, even if some intermediate values where negative.

For full safety, I don't see how we could do better than checking after each operation right now. If we're doing this, I feel like checked_add and friends from rust is a better fit than cramming an unsigned int into a signed one.

I wonder if we could design an integer type with 63 bits of value, plus one bit of "overflow/underflow poison", such that any operation that would under/overflow would saturate that bit to one, but otherwise still perform the operation on the value part. That would allow to coalesce multiple checks while keeping safety even in the presence of multiple faulty operations. I wonder how it could be implemented efficiently though

> I wonder if we could design an integer type with 63 bits of value, plus one bit of "overflow/underflow poison", such that any operation that would under/overflow would saturate that bit to one, but otherwise still perform the operation on the value part. That would allow to coalesce multiple checks while keeping safety even in the presence of multiple faulty operations. I wonder how it could be implemented efficiently though

There is something like that already for floating point. Whenever an overflow or underflow happens, it sets a sticky bit in a separate flags register. You can clear these flags, do a sequence of operations, and at the end, see if any of these flags are set. See https://man7.org/linux/man-pages/man3/fenv.3.html for the standard C API for it.

Your idea for a coalescing overflow type has been explored in the document N2868 [0], a proposal for the C programming language. Instead of reserving a bit from the integer, each integer type is associated with a checked integer type, which holds an integer alongside an overflow bit. Checked integers are opaque and can only be constructed and deconstructed via macros; as I understand it, the idea is that the compiler can use the processor's preexisting overflow flag to represent the checked integer. In particular, the operations on checked integers have the property of coalescing overflow checks that you are looking for.

[0] Supplemental Integer Safety, http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2868.pdf

Reply on news.ycombinator.com