Integer Overflow and Wraparound

Part I · Module 13 · Chapter 13.4 · Integer Overflow and Wraparound

1. The Two Rules

Unsigned arithmetic never overflows. A result that cannot be represented is reduced modulo 2ⁿ, where n is the number of bits in the type. This is a definition, not an accident, and the result is exactly specified.

Signed overflow is undefined behaviour. The standard imposes no requirements — Chapter 13.2's category, with everything that follows from it.

The same a + b in source, two completely different standing in the language, decided by one word in the declaration.

UINT_MAX     = 4294967295
UINT_MAX + 1 = 0            <- defined: wraps modulo 2^32
0u - 1       = 4294967295   <- defined: wraps the other way
UINT_MAX * 2 = 4294967294

INT_MAX = 2147483647, INT_MIN = -2147483648

Each unsigned result above is guaranteed by the standard on every conforming implementation. 0u - 1 is UINT_MAX everywhere, not just here.

One note on C23, because it is a common source of confusion: C23 requires signed integers to use two's complement representation. That fixes what the bits mean and does not make signed overflow defined. The operation remains undefined behaviour; only the representation is now pinned down.

2. The Measurement

One loop, written twice. Each increments until the counter stops being positive.

    int count_signed(void)
    {
        int c = 0;
        for (int i = 1; i > 0; i++) { c++; }
        return c;
    }

    unsigned count_unsigned(void)
    {
        unsigned c = 0;
        for (unsigned i = 1; i > 0; i++) { c++; }
        return c;
    }

No warnings at -Wall -Wextra -Wpedantic. At -O2:

_count_signed:
	brk	#0x1

_count_unsigned:
	mov	w0, #-1
	ret

The signed function is a trap instruction. The loop can only end when i stops being positive, which can only happen by overflowing — which is undefined. So the compiler reasoned that a correct program never reaches the end of this loop, that the function therefore never returns, and emitted a trap for the body.

The unsigned function is a constant. Wrapping is defined, so the compiler could work out exactly what the loop does: i runs from 1 up to UINT_MAX and then wraps to 0, so c ends at UINT_MAX. That value is 0xFFFFFFFF, which is what mov w0, #-1 puts in the return register. The compiler did not compile the loop; it computed the answer.

And the confirmation that the trap came from the assumption rather than from anything about loops:

$ cc -std=c17 -O2 -fwrapv -S o2.c
_count_signed:
	mov	w0, #2147483647
	ret

-fwrapv tells the compiler to treat signed overflow as wrapping. The assumption is switched off, the loop becomes analysable, and the trap becomes INT_MAX. One flag, and the function goes from "has no meaning" to "returns 2147483647".

3. Why the Asymmetry Exists

Not an oversight. Two reasons, and knowing them tells you where else to expect this shape.

Unsigned is defined because there is only one sensible answer. Every representation of unsigned integers is positional binary, so "reduce modulo 2ⁿ" is what every machine does anyway. Defining it costs nothing.

Signed is undefined because it bought optimisation. If int overflow were defined to wrap, a compiler could not assume i + 1 > i, and that assumption is what lets it reason about loops — exactly the reasoning visible in §2, where it decided a loop could not terminate. Leaving it undefined lets the compiler treat int arithmetic as ordinary mathematics rather than as modular arithmetic.

The bill for that is §2's trap. The benefit is that ordinary loop code over int indices compiles well without you doing anything. Chapter 13.2 §6's callout is the general version of this trade.

4. The Overflow Check That Only Works Half the Time

Here is the practical consequence, and it is the one that catches working programmers, because the idiom is correct — for one type.

    /* UNSIGNED: a genuine overflow test */
    static int uadd(unsigned a, unsigned b, unsigned *out)
    {
        unsigned r = a + b;
        if (r < a) { return 0; }        /* wrapped */
        *out = r;
        return 1;
    }

   uadd(10, 5)            -> ok=1 value=15
   uadd(UINT_MAX, 1)      -> ok=0  (correctly rejected)

It works because wrapping is defined, and a wrapped sum is necessarily smaller than either operand. The test is valid and the value it inspects is one the standard guarantees.

Now the same shape with int:

    static int sadd_bad(int a, int b, int *out)
    {
        int r = a + b;
        if (r < a) { return 0; }
        *out = r;
        return 1;
    }

   sadd_bad(10, -5)       -> rejected   <- 5 is perfectly representable
   sadd_bad(100, -1)      -> rejected   <- 99 is perfectly representable

It rejects ordinary, in-range additions. Every call above is fully defined — nothing overflows — and the function still reports failure.

For signed values, a + b < a is mathematically just b < 0. It is not a broken overflow test; it is not an overflow test at all. It detects a negative second operand, which is a different question.

So the signed version fails for two independent reasons, and both are worth holding:

1. It is wrong on in-range inputs, as measured, because the condition means something else.
2. And when overflow does occur, it is undefined, so the sum it inspects has no defined value to inspect.

The first reason alone is enough to discard it. The second is why no clever rearrangement of the same idea can be made to work.

5. Checking Before, Not After

The correct shape tests whether the operation would overflow, using only arithmetic that cannot itself overflow.

#include <limits.h>

static int sadd_ok(int a, int b, int *out)
{
    if (b > 0 && a > INT_MAX - b) { return 0; }     /* would exceed INT_MAX */
    if (b < 0 && a < INT_MIN - b) { return 0; }     /* would fall below INT_MIN */
    *out = a + b;
    return 1;
}

   sadd_ok(10, -5)        -> ok=1 value=5
   sadd_ok(INT_MAX, 1)    -> ok=0  (correctly rejected)
   sadd_ok(INT_MIN, -1)   -> ok=0  (correctly rejected)

Three properties make it correct:

INT_MAX - b cannot overflow when b > 0, because subtracting a positive from the maximum moves toward zero. The same argument covers INT_MIN - b when b < 0. Every intermediate value is in range, so nothing in the check is undefined.

It is tested before the addition, which Chapter 13.2 §7 established as the rule: a test placed after the operation it guards is not a test.

It reports through a separate channel — a return value, with the result delivered through *out only on success — which is Chapter 9.8 §8's commit-on-success shape and avoids needing a sentinel value that might be a legitimate answer.

The same patterns for the other operations:

Two rows deserve a sentence.

INT_MIN has no positive counterpart. In two's complement the range is asymmetric — -2147483648 to 2147483647 — so -INT_MIN, abs(INT_MIN) and INT_MIN / -1 are all undefined. This is the single most commonly forgotten overflow case, and it is one value.

Multiplication is checked by division because there is no larger type to compute the product in. Where there is one — multiplying two 32-bit values on a target with a 64-bit type — computing in the wider type and range-checking the result is simpler and clearer.

6. Where Overflow Actually Happens

Four places, in roughly descending order of how often they appear in real code.

Sizes and counts. n * sizeof(T) is the classic, and Chapter 9.7 §3 measured the consequence: the multiply wrapped, malloc was asked for zero bytes and succeeded, while calloc with the same factors returned NULL. The arithmetic there is size_t, so it is unsigned and well defined — and still wrong, which is the point of §7 below.

Accumulators. A running total over a long input eventually leaves the range of whatever type holds it. A int sum of values averaging a thousand overflows after about two million of them.

Differences used as comparisons. Chapter 12.9's qsort comparator: return a - b; is undefined whenever the true difference exceeds INT_MAX, and the correct form (a > b) - (a < b) never subtracts.

Index arithmetic near the ends. i - 1 when i is 0 and the type is size_t gives a very large number rather than −1, which is Chapter 13.5's subject and the single most common source of an accidental enormous loop bound.

7. Defined Is Not the Same as Correct

An important corrective, because the chapter so far reads as "unsigned good, signed bad".

    size_t n = huge_count;
    void *p = malloc(n * sizeof(int));       /* defined, and possibly wrong */

size_t is unsigned, so the multiplication is fully defined: it wraps modulo 2ⁿ. The program has no undefined behaviour. It also asks for the wrong number of bytes, and Chapter 9.7 §3 measured malloc returning a non-null pointer for zero bytes in exactly this situation.

Unsigned wrapping gives you a defined answer to the wrong question. It converts "undefined behaviour" into "a specific incorrect value", which is better for reasoning and no better for correctness.

So the rules are different but neither type is safe:

Both need the check. The difference is that for unsigned you may check afterwards, and for signed you must check before.

8. Tools

The compiler says nothing. No warning was issued for either loop in §2, nor for sadd_bad, nor — Chapter 12.9 measured — for an overflowing comparator with both constants visible in the same function.

A sanitizer catches it at run time:

$ cc -std=c17 -fsanitize=undefined o4.c -o o4 && ./o4
runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type 'int'

Exact operation, exact values, exact type, exact line. Chapter 13.10 is the full treatment; the thing to note now is that this is the only tool in this chapter that found anything, and it only finds overflows your test inputs actually reach.

-fwrapv defines the behaviour, as §2 measured. It is a real option with real consequences: it makes signed overflow wrap, which removes the undefined behaviour and removes the optimisations that depended on its absence. It is a reasonable choice for code where overflow is possible and crashing is unacceptable; it is not a substitute for checking, because a wrapped result is still the wrong answer, and it is not portable — it is a compiler option, not a language feature.

C23 adds checked arithmetic — ckd_add, ckd_sub, ckd_mul in <stdckdint.h> — which perform the operation and report overflow through a return value. That is the right long-term answer and it is outside this curriculum's C17 baseline.

9. What You Should Be Able to Say Now

1. Unsigned arithmetic wraps modulo 2ⁿ by definition; signed overflow is undefined behaviour.
2. Measured and guaranteed: UINT_MAX + 1 is 0, 0u - 1 is UINT_MAX.
3. C23 requires two's complement representation and still leaves signed overflow undefined.
4. Measured: the same loop gave brk #0x1 for int and a compile-time constant for unsigned, with no warning on either.
5. -fwrapv turned the trap into mov w0, #2147483647 — the assumption switched off, visible in one instruction.
6. The asymmetry exists because unsigned has one sensible answer and signed undefinedness buys optimisation.
7. if (r < a) is a genuine overflow test for unsigned — measured accepting 10+5 and rejecting UINT_MAX+1.
8. For signed it is mathematically just b < 0 — measured rejecting 10 + (−5), which is in range. It fails on ordinary inputs and inspects an undefined value.
9. Check before, using arithmetic that cannot itself overflow: a > INT_MAX - b when b > 0.
10. INT_MIN is the asymmetric case — -INT_MIN, abs(INT_MIN) and INT_MIN / -1 are all undefined.
11. Defined is not correct: unsigned wrapping gives a specific wrong answer, which is how malloc got asked for zero bytes (9.7 §3).
12. The compiler found nothing; a sanitizer reported the operation, values, type and line.

10. Exercises

Exercise 1 — defined or undefined. For each, say which, and give the result where it is defined.

unsigned u = 0; u = u - 1;
int i = INT_MAX; i = i + 1;
unsigned char c = 255; c = c + 1;
int j = INT_MIN; j = -j;
size_t n = 0; n = n - 1;
int k = INT_MIN; k = k / -1;
unsigned v = UINT_MAX; v = v * 3;

Exercise 2 — explain the promotion. (unsigned char)255 + 1 evaluated to 256, not 0. Explain why, name the rule, and say what changes if the result is stored back into an unsigned char.

Exercise 3 — fix the check. Each is wrong. Say why, and give a correct version.

int add(int a, int b)      { int r = a + b; if (r < a) return -1; return r; }
int mul(int a, int b)      { long r = (long)a * b; if (r > INT_MAX) return -1; return (int)r; }
int neg(int a)             { return -a; }
unsigned sub(unsigned a, unsigned b) { unsigned r = a - b; if (r > a) return 0; return r; }

For the second, say on which targets it is correct and why that is a Chapter 13.3 question.

Exercise 4 — predict the compilation. For each loop, say whether the compiler may assume it terminates, and what it might emit at -O2.

for (int i = 0;  i <= n;       i++) { }        /* n is int           */
for (unsigned i = 0; i < n;    i++) { }        /* n is unsigned      */
for (int i = 1;  i != 0;       i++) { }
for (int i = 0;  i < n + 1;    i++) { }        /* n is INT_MAX       */

Exercise 5 — the accumulator. A function sums an array of int into an int. Give the condition under which it overflows, two different fixes, and say what each fix costs.

Exercise 6 — the one value. Explain why INT_MIN needs special handling in negation, absolute value and division, using the range measured in §1.

Exercise 7 — defined but wrong. Explain, using §7 and Chapter 9.7 §3, how a fully defined size_t multiplication leads to a buffer overflow, and give the two ways to prevent it.

Exercise 8 — choose the tool. You have a program that occasionally produces absurd totals. Say what you would run, in what order, and what each step can and cannot tell you.

11. Summary

• Unsigned wraps modulo 2ⁿ, by definition. Signed overflow is undefined.
• Guaranteed: UINT_MAX + 1 == 0, 0u - 1 == UINT_MAX. C23 pins the representation, not the overflow.
• Measured: one loop became brk #0x1 for int and a constant for unsigned. No warning either way.
• -fwrapv turned the trap into 2147483647 — the assumption, switched off.
• if (r < a) is a real test for unsigned and is just b < 0 for signed — measured rejecting 10 + (−5).
• Check before, with arithmetic that cannot overflow: a > INT_MAX - b.
• INT_MIN is the asymmetric value — negation, abs and / -1 are all undefined there.
• Defined is not correct: unsigned wrapping produced the malloc-for-zero-bytes bug.
• The compiler found nothing; a sanitizer named the operation, the values and the line.

One row of §6's table was deferred with a promise, and it is the one that produces the most spectacular failures. i - 1 when i is zero and the type is unsigned does not give −1; it gives a number near four billion, and a loop bounded by it will run essentially forever. That is not an overflow bug in the sense this chapter has described — the arithmetic is defined and correct — it is a bug about which type the arithmetic happened in, decided by conversion rules that run silently before the operator does. Those rules will take a comparison whose truth is obvious to any reader, convert one side behind your back, and make it evaluate false. The next chapter is about those conversions and the comparisons they break — including the measured fact that the direct form is caught by a flag this curriculum has used all along, while the loop forms that actually hang a program draw no diagnostic at all.