Talk:Integer overflow

From NetHackWiki
Jump to navigation Jump to search

Weight wrapping

Just (re)tested this one in SLASH'EM, with a billion dwarf corpses. The weight does indeed wrap, enabling you to carry a virtually unlimited amount. I think it's easy to miss this one, because if you wish for too much weight, you'll wrap it back to positive, so it takes some fiddling in wizard mode. Obviously, this is not something that would ever be feasible in a real game. -Ion frigate (talk) 06:20, 4 July 2024 (UTC)

Have you attempted this in later stable versions? --Umbire the Phantom (talk) 16:23, 4 July 2024 (UTC)
The billion dwarf corpses are back in. I'd like to keep the wizard mode (debug mode) stuff low, because debug mode is meant to bypass the normal game. But an example or two is good. Furey (talk) 12:57, 4 July 2024 (UTC)

Let me make this more explicit. Weight wrapping by wishing for a billion of anything works in wizard mode and does not work in non-wizard mode. This is true in:

So moving the billion dwarf corpse case into "cases of integer overflow fixed in 3.6.0" was wrong.

Of course, I could be wrong. If so, please provide source code citations (with line numbers) or describe an actual game (wizard mode or non wizard mode) where the above analysis is wrong.

Furey (talk) 17:12, 4 July 2024 (UTC)

Obviously, you can't wish for a billion of anything in a normal game. But the situation described in the original article - collecting loadstones - is technically feasible (since they don't rot away) with someone scripting a bunch of pudding farming and polypiling or wishing. In fact, an easier way to do it would likely be to get hungerless casting on dig, and zap it at the ceiling 200 million times. With 3.4.3's predictable mechanics for prayer and the inviolability of jelly forts, it would (eventually) work.
To be clear, I did not intend for the "billion dwarf corpses" to be in the article proper. Merely to say that (at least in older versions of the game), there was no bounds checking on encumbrance, and it could overflow to negative, with the negative encumbrance behaving as one would expect. The billion dwarf corpses is just a quick way to confirm that in wizard mode. But zapping dig at the ceiling 200 million times is well within the bounds of possibility for a real game.
Incidentally, in 32-bit Windows binaries (but not self-compiled Linux versions on 64-bit systems), I used to be able to overflow the counter for "number of items on a square". Meaning that I could actually generate "-1 dwarf corpses" on a square, with the negative item affecting encumbrance (again) exactly as you'd expect. It was doing this that I discovered directly overflowing the weight counter, since wishing for a billion dwarf corpses does *not* cause them to automatically drop to the floor, as they don't encumber you. -Ion frigate (talk) 19:38, 4 July 2024 (UTC)
It looks like zap-ceiling-200-million-times is doable in a normal game. Or zap ceiling less often, polypile to loadstones. function weight() in 3.4.3 and 3.6.1 and even in 3.7 has a plain old "wt * (int) obj->quan" and both terms are ints so even on a 64-bit platform that's only 32 bits of multiplication result. Sigh. I guess weight wrapping is possible in a normal game, and it's not even fixed in 3.6.7 or 3.7. https://github.com/NetHack/NetHack/blob/NetHack-3.6.7_Released/src/mkobj.c#L1471 Furey (talk) 20:14, 4 July 2024 (UTC)
Random ass YANI: put a capitulation style test in merged() so that creation of an object stack with a weight higher than 1 billion causes a black hole and ends the game. Would need similar test for putting objects into containers. Just a YANI. Furey (talk) 20:30, 4 July 2024 (UTC)

Integer overflow is defined by the C language standard, and is not "a result of twos complement arithmetic"

I wrote: 

Integer overflow occurs when a numeric variable exceeds its maximum capacity. Generally what happens, due to two's complement arithmetic, is that the variable wraps to the opposite end of the range.

Umbire copy-edited it to: 

Integer overflow occurs when a numeric variable exceeds its maximum capacity as a result of two's complement arithmetic, wrapping to the opposite end of the variable's range:

This is incorrect.

https://www.open-std.org/JTC1/sc22/wg14/www/docs/n1256.pdf is a draft of ISO/IEC 9899:TC3, the ISO international standard for C, based on ANSI Standard X3.159-1989. There have been several ANSI and ISO standards published for C over the years, and they all say the same thing about undefined behavior, so this one is as good as any. (ISO, the author and copyright owner, finances their activities by selling copies of the standard to people and organizations who need the actual Standard. So it's common for discussions about the Standard to cite drafts).

Section 6.5(5) of the Standard says: 

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined

Thus, undefined behavior from integer overflow is not "due to two's complement arithmetic", it's due to the evaluation of an expression that produces a result that is outside the range of the relevant type. Every integral type has an implementation-specified range; for the signed integer type, the range is INT_MIN to INT_MAX.

Undefined behavior is a powerful and dangerous concept. A program with undefined behavior may produce any behavior whatsoever. For example, using the value of an uninitialized auto variable is undefined behavior. A naive programmer might assume that the variable has some value, it's just unknown which one. That is false: that would be unspecified behavior, not undefined behavior. A standards-conforming C implementation may translate this program to do anything, or nothing. (Amusingly, "play a game of nethack" is sometimes used as an example of what a standards-conforming C implementation may cause a program to do when undefined behavior happens.)

This brings me to the second sentence of the correct version of the lede: Generally what happens, due to two's complement arithmetic, is that the variable wraps to the opposite end of the range. Generally here means not guaranteed, not all the time, but usually or often. It is generally the case that computers running NetHack use two's complement arithmetic. But not always, and not required. And it is generally the case that implementations of C just use the native machine arithmetic instructions, and that signed arithmetic types in C have overflow behavior that is the same as the native machine's arithmetic instructions. But not always, and not required. (Although the C standard does specify the behavior of overflow on unsigned arithmetic types, and thus every conforming C implementation must do it the way the standard says, even if the native machine instructions don't do it that way -- in that case, the implementation must arrange to produce the result required by the standard).

In the incorrect version of the lede, the word generally is missing, and the words "as a result" are added. This is not true. Evaluating a signed expression that is outside the range of representable values is an integer overflow, no matter whether the implementation uses two's complement arithmetic, one's complement arithmetic, or sign-and-magnitude arithmetic.

References:

Rescuing reverted changes

I will rescue parts of the reverted changes that are correct and informative, with a broad view of "informative". But I won't stand for incorrect information in technical articles about software development.

Furey (talk) 12:24, 4 July 2024 (UTC)

Score wrapping protection in 3.6.7 is written incorrectly

https://github.com/NetHack/NetHack/blob/NetHack-3.6/src/end.c#L19 

/* add b to long a, convert wraparound to max value */
#define nowrap_add(a, b) (a = ((a + b) < 0 ? LONG_MAX : (a + b)))

This does not work. If a C implementation (i.e. a C compiler) can prove that a and b are both nonnegative, then the compiler can replace the expression (a + b) < 0 with the expression false. Because either (a + b) really is nonnegative, and it is okay to simplify to false, or (a + b) overflows the range of the appropriate integral type, and that is undefined behavior, and it is okay for the C implementation to choose any behavior that it wants: including simplifying (a + b) < 0 to false.

This is really the heart of understanding how modern C compilers can and do treat code which may have undefined behavior for certain input data. The implementation must produce the Standard-defined behavior for input data with defined behavior, but is allowed to produce any result for input data with undefined behavior.

Assuming b is always restricted to be nonnegative (which it is), this is a correct implementation: 

#define nowrap_add(a, b) (a = (a <= LONG_MAX - b) ? (a + b) : LONG_MAX))

Furey (talk) 00:32, 5 July 2024 (UTC)

Retrieved from "https://nethackwiki.com/index.php?title=Talk:Integer_overflow&oldid=174241"