Talk:Integer overflow - Revision history

Netzhack: /* Defining "undefined behavior" */ new section

2025-04-02T11:47:17Z

‎Defining "undefined behavior": new section

Furey: Score wrapping protection in 3.6.7 is written incorrectly.

2024-07-05T00:33:02Z

Score wrapping protection in 3.6.7 is written incorrectly.

Furey: /* Weight wrapping */ YANI: weight of 1 billion creates black hole.

2024-07-04T20:31:12Z

‎Weight wrapping: YANI: weight of 1 billion creates black hole.

Furey: Okay, looks like a zap-ceiling-200-million-times is doable in a normal game. And not fixed in 3.6.7 or 3.7.

2024-07-04T20:14:43Z

Okay, looks like a zap-ceiling-200-million-times is doable in a normal game. And not fixed in 3.6.7 or 3.7.

Ion frigate: reply

2024-07-04T19:38:47Z

Furey: /* Weight wrapping */ Analysis with source code citations.

2024-07-04T17:12:47Z

‎Weight wrapping: Analysis with source code citations.

Umbire the Phantom: query

2024-07-04T16:23:46Z

query

Furey: /* Weight wrapping */ okay

2024-07-04T12:57:40Z

‎Weight wrapping: okay

Furey: line breaks, oops

2024-07-04T12:25:56Z

line breaks, oops

Furey: Copy editing made the lede wrong. Here is how.

2024-07-04T12:24:47Z

Copy editing made the lede wrong. Here is how.

← Older revision		Revision as of 11:47, 2 April 2025
Line 71:		Line 71:

	[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 00:32, 5 July 2024 (UTC)		[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 00:32, 5 July 2024 (UTC)
		+
		+	== Defining "undefined behavior" ==
		+
		+	I edited the page today. The previous version said something implying that "undefined behavior" meant that the C standard doesn't say what happens if an overflow occurred. This is a misunderstanding of "undefined behavior". The C standard DOES say what happens in case of a signed integer overflow: namely, "undefined behavior" happens. (In other words, as a previous editor wrote above, the program may, ''in conformance with the standard'', do '''absolutely anything'''.) I rewrote the section to reflect this specialized usage. [[User:Netzhack\|Netzhack]] ([[User talk:Netzhack\|talk]]) 11:47, 2 April 2025 (UTC)

← Older revision		Revision as of 00:33, 5 July 2024
Line 56:		Line 56:

	[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 12:24, 4 July 2024 (UTC)		[[User:Furey\|Furey]] ([[User talk: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 <tt>a</tt> and <tt>b</tt> are both nonnegative, then the compiler can replace the expression <tt>(a + b) < 0</tt> with the expression <tt>false</tt>. Because either <tt>(a + b)</tt> really is nonnegative, and it is okay to simplify to false, or <tt>(a + b)</tt> 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 <tt>(a + b) < 0</tt> 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 <tt>b</tt> 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))
		+
		+	[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 00:32, 5 July 2024 (UTC)

@@ Line 23: / Line 23: @@
 :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. -[[User:Ion frigate|Ion frigate]] ([[User talk: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 [[User:Furey|Furey]] ([[User talk:Furey|talk]]) 20:14, 4 July 2024 (UTC)
 ==Integer overflow is defined by the C language standard, and is not "a result of twos complement arithmetic"==

@@ Line 22: / Line 22: @@
 :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. -[[User:Ion frigate|Ion frigate]] ([[User talk:Ion frigate|talk]]) 19:38, 4 July 2024 (UTC)
 ==Integer overflow is defined by the C language standard, and is not "a result of twos complement arithmetic"==

← Older revision		Revision as of 19:38, 4 July 2024
Line 18:		Line 18:

	[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 17:12, 4 July 2024 (UTC)		[[User:Furey\|Furey]] ([[User talk: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 [[spellbook of dig\|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. -[[User:Ion frigate\|Ion frigate]] ([[User talk:Ion frigate\|talk]]) 19:38, 4 July 2024 (UTC)

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

← Older revision		Revision as of 17:12, 4 July 2024
Line 5:		Line 5:

	: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. [[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 12:57, 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. [[User:Furey\|Furey]] ([[User talk: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:
		+	* https://nethackwiki.com/wiki/Source:SLASH%27EM_0.0.7E7F2/objnam.c#line2758
		+	* https://nethackwiki.com/index.php?title=Source:NetHack_3.4.3/src/objnam.c#line2472
		+	* https://nethackwiki.com/index.php?title=Source:NetHack_3.6.0/src/objnam.c#line3267
		+	* https://github.com/NetHack/NetHack/blob/NetHack-3.6.7_Released/src/objnam.c#L3864
		+	* https://github.com/NetHack/NetHack/blob/NetHack-3.7/src/objnam.c#L4992
		+
		+	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.
		+
		+	[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 17:12, 4 July 2024 (UTC)

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

@@ Line 1: / Line 1: @@
 ==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. -[[User:Ion frigate|Ion frigate]] ([[User talk:Ion frigate|talk]]) 06:20, 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. [[User:Furey|Furey]] ([[User talk:Furey|talk]]) 12:57, 4 July 2024 (UTC)

@@ Line 24: / Line 24: @@
 References:
-https://en.wikipedia.org/wiki/ANSI_C is a good overview of ANSI and ISO standards over the years.
+* https://en.wikipedia.org/wiki/ANSI_C is a good overview of ANSI and ISO standards over the years.
-https://en.wikipedia.org/wiki/Integer_overflow is a good introduction and is cited in our article.
+* https://en.wikipedia.org/wiki/Integer_overflow is a good introduction and is cited in our article.
-https://en.wikipedia.org/wiki/Undefined_behavior
+* https://en.wikipedia.org/wiki/Undefined_behavior
 == Rescuing reverted changes ==

← Older revision		Revision as of 12:24, 4 July 2024
Line 1:		Line 1:
	==Weight wrapping==		==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. -[[User:Ion frigate\|Ion frigate]] ([[User talk:Ion frigate\|talk]]) 06:20, 4 July 2024 (UTC)		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. -[[User:Ion frigate\|Ion frigate]] ([[User talk:Ion frigate\|talk]]) 06:20, 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:
		+	https://en.wikipedia.org/wiki/ANSI_C is a good overview of ANSI and ISO standards over the years.
		+	https://en.wikipedia.org/wiki/Integer_overflow is a good introduction and is cited in our article.
		+	https://en.wikipedia.org/wiki/Undefined_behavior
		+
		+	== 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.
		+
		+	[[User:Furey\|Furey]] ([[User talk:Furey\|talk]]) 12:24, 4 July 2024 (UTC)