Integer overflow - Revision history

Netzhack: "undefined behavior" in C doesn't mean the standard doesn't define it. It means the standard defines that the behavior is undefined!

2025-04-02T11:40:23Z

"undefined behavior" in C doesn't mean the standard doesn't define it. It means the standard defines that the behavior is undefined!

Furey: /* History */ add refsrc. yes, nowrap_add is written incorrectly, see talk page

2024-07-05T00:13:53Z

‎History: add refsrc. yes, nowrap_add is written incorrectly, see talk page

Noisytoot: nowrap_add relies on UB so score wrapping is not fixed in vanilla

2024-07-04T21:32:49Z

nowrap_add relies on UB so score wrapping is not fixed in vanilla

Furey: /* Wrapping the turn counter */ Explicit sub-lede with a refsrc. It's not the version that matters (up to 3.7.0), it's build choice of 32-bit ILP32 vs 64-bit LP64.

2024-07-04T17:27:44Z

‎Wrapping the turn counter: Explicit sub-lede with a refsrc. It's not the version that matters (up to 3.7.0), it's build choice of 32-bit ILP32 vs 64-bit LP64.

Furey: Put the section headers back. Delete "theoretically" when talking about things we are providing examples of. Move the billion dwarf corpses example back to wizard mode section.

2024-07-04T16:53:05Z

Put the section headers back. Delete "theoretically" when talking about things we are providing examples of. Move the billion dwarf corpses example back to wizard mode section.

Umbire the Phantom: The dwarf corpses example was listed as a historical example specifically from SLASH'EM tests - reorganize that and retrieve other changes thrown out with my misaimed copyedit attempt

2024-07-04T16:23:21Z

The dwarf corpses example was listed as a historical example specifically from SLASH'EM tests - reorganize that and retrieve other changes thrown out with my misaimed copyedit attempt

Furey: Putting on my language lawyer hat. Hope it's still readable.

2024-07-04T13:14:17Z

Putting on my language lawyer hat. Hope it's still readable.

Furey: Put back the billion dwarf corpses.

2024-07-04T12:51:09Z

Put back the billion dwarf corpses.

Furey: Recover parts of reverted changes that were okay. {{nethack-367}} is okay, the cases mentioned are specific to version. Move "turn counter" from history to current. Khaos's turn counter game is still not a 1-turn ascension.

2024-07-04T12:41:49Z

Recover parts of reverted changes that were okay. {{nethack-367}} is okay, the cases mentioned are specific to version. Move "turn counter" from history to current. Khaos's turn counter game is still not a 1-turn ascension.

Furey: Revert to a correct revision. Integer overflow is a subtle point in the C language standard, and "copy editing" this article made it wrong.

2024-07-04T11:19:11Z

Revert to a correct revision. Integer overflow is a subtle point in the C language standard, and "copy editing" this article made it wrong.

@@ Line 3: / Line 3: @@
 '''Integer overflow''' occurs when an integer value exceeds the range of its data type.
-For a [[signed variable]], the exact behavior is [[wikipedia:undefined behavior|undefined behavior]] by the C standard. Often what happens, due to [[wikipedia:Two's complement|two's complement arithmetic]], is that the variable wraps to the opposite end of the range: a negative value just beyond the range would become a large positive value, and vice versa. For an unsigned variable, the C standard does define the exact behavior: an unsigned variable that exceeds its capacity becomes a small positive value, or zero, and subtracting too much from a small unsigned variable produces a large value.
+When a [[signed variable|signed integer variable]] overflows, a program's behavior is [[wikipedia:undefined behavior|undefined]], according to the C standard. Often, what happens is that, because negative numbers are represented as a [[wikipedia:Two's complement|two's complement]], the variable wraps to the opposite end of the data type's range: a negative value which just exceeds the range becomes a large positive value, and vice versa. When an unsigned integer variable overflows, the C standard defines the exact behavior: an unsigned value that just exceeds the type's range becomes zero or a small positive value, and subtracting a little more than an unsigned variable's value produces a large value.
-''[[NetHack]]'' protects most variables against integer overflow, both signed and unsigned - however, it is possible to find ways to avoid these limits in [[wizard mode]].  For example, in wizard mode, the character might wish for one billion dwarf corpses, producing an object stack whose total weight may appear to be negative (depending on details of the C implementation used to run NetHack).
+''[[NetHack]]'' protects most variables against integer overflow, both signed and unsigned - however, it is possible to find ways to avoid these limits in [[wizard mode]].  For example, in wizard mode, the character might wish for one billion dwarf corpses, producing an object stack whose total weight may appear to be negative (depending on details of the C implementation used to compile NetHack).
-Any case where an ordinary game (not in wizard mode) can produce an integer overflow is likely to be a [[software bug]].
+Any case where an ordinary game (i.e., not in wizard mode) can produce an integer overflow is a [[software bug]].
-== Current overflows ==
+== Known overflows ==
 === Wrapping the turn counter ===
@@ Line 17: / Line 17: @@
 [[NAO]] reports one game that ended with less than 0 turns played.<ref>https://s3.amazonaws.com/altorg/dumplog/Khaos/1291644901.nh343.txt</ref>. There are no ascended games with 1 turn or any number of turns less than 2000.
-Since that time, NAO switched from 32-bit binaries to 64-bit binaries, as evidenced by several games recorded with scores higher than 2,147,483,647. Nowadays, wrapping the turn counter on an NAO game would take 4 billion times as long as previously.
+Since that time, NAO switched from 32-bit binaries to 64-bit binaries, as evidenced by several games recorded with scores higher than 2,147,483,647. Nowadays, wrapping the turn counter on an NAO game would take 4 billion times as long as before.
-{{upcoming|NetHack 3.7.0|For games running over 100000 turns, [[prayer]] timeout increases by 1 every 100 turns - this is implemented to prevent denial-of-service attacks against [[public server]]s. If a game runs over one billion turns, it ends immediately in an [[Escaping the dungeon|escape]]:
+{{upcoming|NetHack 3.7.0|For games running over 100,000 turns, [[prayer]] timeout increases by 1 every 100 turns - this is implemented to prevent denial-of-service attacks against [[public server]]s. If a game runs over one billion turns, it ends immediately in an [[Escaping the dungeon|escape]]:
 {{message|The dungeon capitulates.}}}}
@@ Line 29: / Line 29: @@
 * Extreme bonuses to hit or to damage from [[eating jewelry]]
-Wrapping the score<ref>NAO game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref> is supposed to be fixed, but the fix relies on signed integer overflow, which is undefined behaviour.{{refsrc|nethack=3.6.7|src/end.c|19|comment=macro nowrap_add}}
+Wrapping the score<ref>NAO game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref> was supposed to be fixed, but the fix itself relies on signed integer overflow, which is undefined behaviour.{{refsrc|nethack=3.6.7|src/end.c|19|comment=macro nowrap_add}}
 == References ==

@@ Line 29: / Line 29: @@
 * Extreme bonuses to hit or to damage from [[eating jewelry]]
-Wrapping the score<ref>NAO game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref> is supposed to be fixed, but the fix relies on signed integer overflow, which is undefined behaviour.
+Wrapping the score<ref>NAO game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref> is supposed to be fixed, but the fix relies on signed integer overflow, which is undefined behaviour.{{refsrc|nethack=3.6.7|src/end.c|19|comment=macro nowrap_add}}
 == References ==

@@ Line 28: / Line 28: @@
 * Extreme [[intrinsic protection]] from [[prayer]]
 * Extreme bonuses to hit or to damage from [[eating jewelry]]
-* Wrapping the score<ref>NAO game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref>
 == References ==

@@ Line 12: / Line 12: @@
 === Wrapping the turn counter ===
 [[NAO]] reports one game that ended with less than 0 turns played.<ref>https://s3.amazonaws.com/altorg/dumplog/Khaos/1291644901.nh343.txt</ref>. There are no ascended games with 1 turn or any number of turns less than 2000.
-Since that time, NAO switched from 32-bit binaries to 64-bit binaries, as evidenced by several games recorded with scores higher than 2,147,483,647. Wrapping the turn counter on NAO 3.6.7 would take 4 billion times as long as previously.
+Since that time, NAO switched from 32-bit binaries to 64-bit binaries, as evidenced by several games recorded with scores higher than 2,147,483,647. Nowadays, wrapping the turn counter on an NAO game would take 4 billion times as long as previously.
 {{upcoming|NetHack 3.7.0|For games running over 100000 turns, [[prayer]] timeout increases by 1 every 100 turns - this is implemented to prevent denial-of-service attacks against [[public server]]s. If a game runs over one billion turns, it ends immediately in an [[Escaping the dungeon|escape]]:

@@ Line 5: / Line 5: @@
 For a [[signed variable]], the exact behavior is [[wikipedia:undefined behavior|undefined behavior]] by the C standard. Often what happens, due to [[wikipedia:Two's complement|two's complement arithmetic]], is that the variable wraps to the opposite end of the range: a negative value just beyond the range would become a large positive value, and vice versa. For an unsigned variable, the C standard does define the exact behavior: an unsigned variable that exceeds its capacity becomes a small positive value, or zero, and subtracting too much from a small unsigned variable produces a large value.
-''[[NetHack]]'' protects most variables against integer overflow, both signed and unsigned - however, it is possible to find ways to avoid these limits in [[wizard mode]]. Any case where an ordinary game can produce an integer overflow is likely to be a [[software bug]].
+''[[NetHack]]'' protects most variables against integer overflow, both signed and unsigned - however, it is possible to find ways to avoid these limits in [[wizard mode]].  For example, in wizard mode, the character might wish for one billion dwarf corpses, producing an object stack whose total weight may appear to be negative (depending on details of the C implementation used to run NetHack).
-With those statements in mind, it is ''theoretically'' possible to overflow the [[turn]] counter: to date, only one such example has been recorded on [[NAO]] in a game of NetHack 3.4.3 that ended with less than 0 turns played, and there are no ascended games with 1 turn or any number of turns less than 2000.<ref>https://s3.amazonaws.com/altorg/dumplog/Khaos/1291644901.nh343.txt</ref> Since that time, NAO has switched from 32-bit binaries to 64-bit binaries, as evidenced by several games recorded with scores higher than 2,147,483,647 - wrapping the turn counter on NAO 3.6.7 would take 4 billion times as long as previously.
+Any case where an ordinary game (not in wizard mode) can produce an integer overflow is likely to be a [[software bug]].
 {{upcoming|NetHack 3.7.0|For games running over 100000 turns, [[prayer]] timeout increases by 1 every 100 turns - this is implemented to prevent denial-of-service attacks against [[public server]]s. If a game runs over one billion turns, it ends immediately in an [[Escaping the dungeon|escape]]:
 {{message|The dungeon capitulates.}}}}
-==History==
+== History ==
 In [[NetHack 3.4.3]] and previous versions, including some variants based on those versions, cases of integer overflow that are fixed in [[NetHack 3.6.0]] include:
@@ Line 19: / Line 27: @@
 * Extreme bonuses to hit or to damage from [[eating jewelry]]
 * Wrapping the score<ref>NAO game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref>
-==References==
+== References ==
 <references/>
 {{nethack-367}}
 [[Category:Development]]

@@ Line 1: / Line 1: @@
 {{Wikipedia|Integer overflow}}
-'''Integer overflow''' occurs when a numeric variable exceeds its maximum capacity. Generally what happens, due to [http://en.wikipedia.org/wiki/Two%27s_complement two's complement arithmetic], is that the variable wraps to the opposite end of the range. So for a [[signed variable]], a negative value just beyond the range would become a large positive value, and vice versa. An unsigned variable that exceeds its capacity would become a small positive value, or zero. Subtracting too much from a small unsigned variable would produce a large value.
+'''Integer overflow''' occurs when an integer value exceeds the range of its data type. For a [[signed variable]], the exact behavior is undefined.<ref>[[wikipedia:undefined behavior]] -- "undefined behavior" is a term of art in the C standard</ref>. Often what happens, due to [http://en.wikipedia.org/wiki/Two%27s_complement two's complement arithmetic], is that the variable wraps to the opposite end of the range: a negative value just beyond the range would become a large positive value, and vice versa.  For an unsigned variable, the C standard does define the exact behavior: an unsigned variable that exceeds its capacity becomes a small positive value, or zero, and subtracting too much from a small unsigned variable produces a large value.
-NetHack protects most variables against integer overflow. However, in [[wizard mode]], it is easy to find ways to avoid these limits. For example, in wizard mode, the character might wish for one billion dwarf corpses, producing an object stack whose total weight may appear to be negative (depending on details of the C implementation used to run NetHack).
+NetHack protects most variables against integer overflow, both signed and unsigned. However, in [[wizard mode]], it is easy to find ways to avoid these limits. For example, in wizard mode, the character might wish for one billion dwarf corpses, producing an object stack whose total weight may appear to be negative (depending on details of the C implementation used to run NetHack).
 Any case where an ordinary game (not in wizard mode) can produce an integer overflow is likely to be a [[software bug]].
@@ Line 19: / Line 19: @@
 == History ==
-In the past, cases of integer overflow have included:
+In [[NetHack 3.4.3]], cases of integer overflow have included:
 * [[Negative gold]] -- fixed in NetHack 3.6.0
 * Extreme [[intrinsic protection]] from [[prayer]] -- fixed in NetHack 3.6.0

@@ Line 4: / Line 4: @@
 NetHack protects most variables against integer overflow. Any case where an ordinary game (not in [[wizard mode]]) can produce an integer overflow is likely to be a [[software bug]].
 == History ==
@@ Line 12: / Line 22: @@
 * Extreme bonuses to hit or to damage from [[eating jewelry]] -- fixed in NetHack 3.6.0
 * Wrapping the score<ref>[[NAO]] game by ctaboir on 2006-10-03 with score -2,147,474,899; dumplog not available</ref><ref>[[NAO]] game by pug on 2007-11-12 with score -2,145,868,906; dumplog not available</ref> -- fixed in NetHack 3.6.0
 == References ==
@@ Line 18: / Line 27: @@
 [[Category:Development]]