Integer Arithmetic

Integer representation based on fixed-size machine words are finite.

• I.e., only finite number of possible values can be represented.
• E.g., for a word with $w$ bits, we can represent $2^w$ possible values.

This can result in strange results with doing arithmetic leading to security vulnerabilities.

Addition

Addition of unsigned values:

• Start with the least significant digit and carry excess into the next most-significant digit.

An overflow occurs if the sum of the w-bit (unsigned) integer value is too large to represent using a w-bit word.

• The excess one bit (that overflows) will be of value $2^w$ and you are left with an effective sum of w bit integers a and b is $(a+b)mod(2^w)$. The true sum is the sum of the two.

Addition of signed values. The sum of signed w-bit can't be represented:

• If sum exceeds $2^{w-1}-1$, it becomes negative (overflow).
• If sum is less than $-2^{w-1}$, it becomes positive (negative overflow).

Two's Complement Arithmetic

Negation: if x is a two-complement integer value, -x can be computing by inverting the bits, then adding 1.

• This works becasue inverting all bits is equvalent to subtracting from a bit string consisting of all 1 bits. A bitstring of all 1 has the value -1, so inverting the bits of x and adding 1 means $−1 − x + 1 = 0 − x = −x$

Integer Arithmetic In C

C data types are "close to" machine data types.

Here are some traps:

• Certain operations in C are implementation defined

  • This isn't as bad as undefined behavior
  • The compiler will document what the code will do but it can vary within a range of allowed behaviors.

• Certain operations in C are undefined behavior

  • Program could do anything.
  • Compiler can (and often does) assume that undefined behavior will never occcur, leading to surprising "optimizations."
    • Compiler optimizations are things that the compiler does to translate your code to machine language in order to optimize hardware use . It includes some interesting things like finding sequences of machine langauge that are consistent with the source code. When the compiler generates target instructions, it can generate code that makes the program break when there is undefined behavior in the source code.
  • All operations after an undefined behavior don't matter any more.

Shifts

Shifts move the bits in a value some number of positions left or right.

• Bits shifted out are discounted (to the left)
• Bits shifted in could be 0 or 1 depending on operand type.
• Left shift by 1 bit = multiply by 2, right shift by 1 bit = di
• vide by 2
• Typically faster than multiplication/division

For signed bits:

• Shifting x (0b00001111) to the left by five bits (x << 5) is an undefined behavior. This is because left shifts into or past the sign bit are undefined. Anything could happen when the program attempts to perform this computation.
• Right shifts could either replicate the sign bit ("arithmetic" shift) or shift in 0 bits ("logical" shift). E.g., 0x80000000 >> 1 could yield either oxC0000000 or 0x40000000. This is an implementation-defined behavioral

Conversions

Size Conversions When integer values are converted to a different sized representation:

• unsigned small --> large: 0 bits added (value preserved)
• signed small --> large: sign bit duplicated (value preserved)
• unsigned large --> small: truncation (value could change)
• signed large --> small: truncation (value could change)

Signed-ness conversions When signed and unsigned values are used in an expression

• the signed value is converted to unsigned (by reinterpreting its bits as an unsigned value)
• The result is unsigned.
• Surprising results can occur

Overflows

Overflow for unsigned types is defined in terms of wrapping.

unsigned x = UINT_MAX;
x++;

• x is guaranteed to be 0 no matter what.

unsigned x = 0;
x--;

• guaranteed to print the value of UINT_MAX

The overflow for signed interger types is undefined.