Integer overflow: Difference between revisions

Revision as of 20:34, 16 April 2010

Revision as of 01:47, 26 April 2010

Line 6:

The [[register width]] of a processor determines the range of values that can be represented. Typical [[Binary numeral system|binary]] register widths include:

: 8 bits (maximum representable value 2⁸ -− 1 = 255),

: 16 bits (maximum representable value 2¹⁶ -− 1 = 65,535),

: 32 bits (the most common width for personal computers {{As of|2005|lc=on}}, maximum representable value 2³² -− 1 = 4,294,967,295),

: 64 bits (maximum representable value 2⁶⁴ -− 1 = 18,446,744,073,709,551,615),

: 128 bits (maximum representable value 2¹²⁸ -− 1 = 340,282,366,920,938,463,463,374,607,431,768,211,455)

Since an arithmetic operation may produce a result larger than the maximum representable value, a potential error condition may result. In the [[C (programming language)|C programming language]], signed integer overflow causes [[undefined behavior]], while unsigned integer overflow causes the number to be reduced [[modular arithmetic|modulo a power of two]], meaning that unsigned integers "wrap around" on overflow.

A "wrap around" corresponds to the fact, that e.g. if the addition of two positive integers produces an overflow, it may result in a negative number. In counting, one just starts over again from the bottom.

Example: 16 bit signed integer: 30000 + 30000 = -5536−5536.

<!-- Diagram that illustrates wrapping behavior of integer representation. -->

In [[computer graphics]] or [[signal processing]], it is typical to work on data that ranges from 0 to 1 or from -1−1 to 1. An example of this is a [[grayscale]] image where 0 represents black, 1 represents white, and values in-between represent varying shades of gray. One operation that one may want to support is brightening the image by multiplying every pixel by a constant. [[Saturated arithmetic]] allows one to just blindly multiply every [[pixel]] by that constant without worrying about overflow by just sticking to a reasonable outcome that all these pixels larger than 1 (i.e. [[high dynamic range imaging|"brighter than white"]]) just become white and all values "darker than black" just become black.

==Security ramifications==