Number Systems & Two's Complement

Every number system you will encounter is positional: the value of a digit depends on where it sits, not just what it is. In decimal (base 10), the number 347 means 3×10² + 4×10¹ + 7×10⁰. The base, also called the radix, determines how many distinct symbols (digits) exist before you roll over: decimal has 10 (0–9), binary has 2 (0 and 1), hexadecimal has 16 (0–9, then A–F).

Binary (base 2) maps directly onto hardware: a single wire that is either charged or not, a flip-flop that stores either state, a transistor that is either conducting or not. Each binary digit is called a bit. Eight bits make a byte, and most modern architectures work natively with 8, 16, 32, or 64-bit quantities.

Hexadecimal (base 16) is not a separate hardware concept — it is a human shorthand. Every 4 bits correspond to exactly one hex digit, so a 32-bit value is cleanly expressed as 8 hex digits. Kernel developers write addresses and bitmasks in hex almost universally because 0xDEADBEEF is far easier to scan than 32 individual bits.

Converting between bases:

• Binary → Decimal: weight each bit by its positional power of 2 and sum.
• Decimal → Binary: repeatedly divide by 2, collect remainders from bottom to top.
• Binary → Hex: group bits in fours from the right, convert each group.
• Hex → Binary: expand each hex digit to its 4-bit representation.

This positional logic is ancient — the Babylonians used base 60 — but the choice of base 2 for computers is purely an engineering one: two voltage levels are the most reliable thing you can build from transistors.

#include <stdio.h>

int main(void) {
    unsigned int x = 0xDEADBEEF;
    /* Print the same value in multiple bases */
    printf("Decimal  : %u\n", x);       /* 3735928559 */
    printf("Hex      : 0x%X\n", x);     /* 0xDEADBEEF */
    /* Manual binary print, MSB first */
    for (int i = 31; i >= 0; i--) {
        putchar('0' + ((x >> i) & 1));
        if (i % 4 == 0 && i > 0) putchar('_');
    }
    putchar('\n');
    return 0;
}

An unsigned integer stores a non-negative whole number. With n bits you can represent exactly 2ⁿ distinct values: 0 through 2ⁿ−1. A uint8_t holds 0–255; a uint32_t holds 0–4,294,967,295 (~4 billion).

The encoding is exactly the positional value you already know: the bit pattern 00000101 in an 8-bit unsigned integer is 5. There is no sign, no ambiguity. This is sometimes called natural binary or pure binary.

Unsigned arithmetic is arithmetic modulo 2ⁿ. This is not a quirk or a bug — it is the definition. When a uint8_t holding 255 is incremented, it wraps to 0 because 256 mod 256 = 0. The C standard explicitly guarantees this wrapping for unsigned types; it is well-defined behavior.

This modular property is useful: you can detect whether a + b would overflow a uint32_t by checking a + b < a (in C, with uint32_t operands). If overflow happened, the sum wrapped to a small number, so it will be less than a. This idiom appears throughout the Linux kernel.

The kernel's <linux/types.h> defines u8, u16, u32, u64 as guaranteed-width unsigned types. You will see these everywhere in driver code, protocol headers, and memory management. Never confuse them with the platform-dependent unsigned int, which might be 16 bits on a microcontroller.

#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>

/* Safe addition: returns false if overflow would occur */
bool u32_add_safe(uint32_t a, uint32_t b, uint32_t *result) {
    *result = a + b;            /* wraps by definition */
    return (*result >= a);      /* false iff wrapped */
}

int main(void) {
    uint8_t  x = 255;
    printf("%u\n", (uint8_t)(x + 1));  /* 0  — wraps */

    uint32_t r;
    printf("%d\n", u32_add_safe(0xFFFFFFFE, 3, &r)); /* 0 = overflow */
    printf("%d\n", u32_add_safe(10,         3, &r)); /* 1 = ok, r=13  */
    return 0;
}

Hardware adder circuits add bits; they know nothing about signs. If we want negative numbers, we must encode a sign into the bit pattern using a convention. Three conventions have been used in real hardware; understanding all three makes it clear why two's complement won.

Sign-magnitude: Dedicate the most significant bit (MSB) as a sign flag (0 = positive, 1 = negative). The remaining bits hold the magnitude. So in 8 bits, 00000101 = +5 and 10000101 = −5. This is exactly how we write signed decimals (the minus sign is separate from the digits).

Problems with sign-magnitude:

1. Two zeros: 00000000 = +0 and 10000000 = −0. Every comparison and equality check must special-case this.
2. Adder circuits fail: Adding 00000101 (+5) and 10000011 (−3) bit-by-bit gives a wrong answer. You'd need a separate subtraction circuit that inspects the sign bits first — more hardware, more complexity.
3. Range: 8-bit sign-magnitude covers −127 to +127 (not −128).

One's complement: Negate a number by flipping all bits. So +5 = 00000101 and −5 = 11111010. Adding +5 and −3 (11111100) gives 11111111 with a carry out; you must add that carry back in ("end-around carry"). Still two zeros (00000000 = +0, 11111111 = −0). Used in older machines like the UNIVAC 1100 and early network checksum algorithms (the IP/TCP checksum is one's complement, which is why it's slightly weird).

Two's complement: Negate by flipping all bits then adding 1. So +5 = 00000101 and −5 = 11111011. Adding +5 and −3 (11111101) on a plain binary adder gives 00000010 = 2. Correct, no special hardware. Only one zero. This is why every modern CPU uses two's complement.

/* Demonstrate the three encodings of -5 in 8 bits */
#include <stdint.h>
#include <stdio.h>

int main(void) {
    /* Sign-magnitude -5: set MSB, magnitude 5 */
    uint8_t sm  = 0b10000101;  /* 0x85 */

    /* One's complement -5: flip all bits of +5 */
    uint8_t oc  = (uint8_t)~(uint8_t)5; /* 0xFA = 11111010 */

    /* Two's complement -5: ~5 + 1 */
    uint8_t tc  = (uint8_t)(~(uint8_t)5 + 1); /* 0xFB = 11111011 */

    printf("sign-mag  0x%02X\n", sm); /* 0x85 */
    printf("ones-comp 0x%02X\n", oc); /* 0xFA */
    printf("twos-comp 0x%02X\n", tc); /* 0xFB */

    /* C's signed int8_t IS two's complement (C23 mandates it) */
    int8_t official = -5;
    printf("int8_t    0x%02X\n", (uint8_t)official); /* 0xFB */
    return 0;
}

The why behind two's complement is elegant and worth internalizing fully.

The circular number line: Imagine an n-bit unsigned counter. Count up from 0: 0, 1, 2, … 2ⁿ−1, and then it wraps back to 0. Now relabel the upper half: instead of calling those values 2ⁿ⁻¹ through 2ⁿ−1, call them −2ⁿ⁻¹ through −1. That's it. That's two's complement.

Concretely in 4 bits:

Bit pattern  Unsigned  Two's-complement signed
0000             0            0
0001             1            1
0010             2            2
0011             3            3
0100             4            4
0101             5            5
0110             6            6
0111             7            7
1000             8           -8   ← MSB=1: negative
1001             9           -7
1010            10           -6
1011            11           -5
1100            12           -4
1101            13           -3
1110            14           -2
1111            15           -1

Key observations:

1. MSB is the sign bit: bit pattern with MSB=1 are negative, MSB=0 are non-negative. BUT the MSB is not merely a flag — it carries weight −2ⁿ⁻¹ in the positional sum. For a 4-bit number b3 b2 b1 b0, the value is −8·b3 + 4·b2 + 2·b1 + 1·b0. This is why the range is asymmetric.

2. Asymmetric range: 8-bit two's complement covers −128 to +127. There is one extra negative number (−128) with no positive counterpart. The magnitude of the most-negative number cannot be represented. This is why abs(INT_MIN) is undefined behavior in C — it would need to produce 128, which overflows.

3. Negation formula: To negate x, compute ~x + 1. This falls out of the encoding: x + (~x + 1) = x + ~x + 1 = (2ⁿ − 1) + 1 = 2ⁿ ≡ 0 (mod 2ⁿ). Negation is its own inverse (mostly — except for INT_MIN where negation overflows).

4. Single adder for both signs: A CPU's adder doesn't need to know whether operands are signed or unsigned. 3 + (−5) and 3 + 251 use identical bit operations on an 8-bit adder; it's the programmer's/compiler's interpretation that differs. This unification of addition hardware is the entire point.

/* Verify the weight formula: value = -2^(n-1)*MSB + sum of lower bits */
#include <stdint.h>
#include <stdio.h>

int twos_value_4bit(uint8_t nibble) {
    nibble &= 0xF;
    int b3 = (nibble >> 3) & 1;
    int b2 = (nibble >> 2) & 1;
    int b1 = (nibble >> 1) & 1;
    int b0 = (nibble >> 0) & 1;
    return -8*b3 + 4*b2 + 2*b1 + b0;  /* -2^3 weight on MSB */
}

int main(void) {
    for (uint8_t i = 0; i < 16; i++)
        printf("%04b (0x%X) = %d\n", i, i, twos_value_4bit(i));
    /* Note: %b is a C23 extension; use gcc -std=c23 or print manually */
    return 0;
}

C gives you both signed and unsigned integer types, and the rules for mixing them cause an enormous amount of confusion and bugs.

Ranges (assuming two's complement, which C23 mandates and all current hardware implements):

• uint8_t: 0 to 255
• int8_t: −128 to 127
• uint32_t: 0 to 4,294,967,295
• int32_t: −2,147,483,648 to 2,147,483,647

The comparison trap: In C, when you compare a signed integer with an unsigned integer, the signed operand is implicitly converted to unsigned. If the signed value was negative, it wraps to a huge positive number, and the comparison gives a nonsensical result. Classic kernel bug pattern:

int len = get_user_input();  /* could be negative! */
if (len < MAX_BUF_SIZE)      /* len converted to unsigned → huge */
    memcpy(buf, src, len);   /* huge copy → buffer overflow */

Integer promotion: Arithmetic in C always happens at int width or wider. A uint8_t + uint8_t is computed as int + int, then truncated back. This means uint8_t x = 200; uint8_t y = 100; int z = x + y; gives 300, not 44, because the addition happens in int before any truncation.

Signed overflow is undefined behavior: This is the most dangerous asymmetry. Unsigned overflow is guaranteed to wrap. Signed overflow is UB in C (not C++20 which inherits C's rule here) — the compiler is allowed to assume it never happens. In practice, with -O2, gcc will optimize away checks like if (x + 1 < x) when x is signed, because signed overflow can't happen (by the standard's assumption), so x + 1 is always greater than x. This is a real source of security bugs when developers assume the check will work.

The Linux kernel uses -fwrapv to force signed overflow to wrap, which is a deliberate deviation from the standard to prevent this class of optimizer surprises.

/* The signed-vs-unsigned comparison trap */
#include <stdio.h>
#include <string.h>

#define BUFSIZE 64
char buf[BUFSIZE];

void dangerous(int user_len) {
    /* BAD: user_len promoted to unsigned for comparison */
    if ((unsigned)user_len < BUFSIZE) {   /* -1 becomes 4294967295 */
        /* This branch IS taken for user_len == -1 */
        memcpy(buf, "x", user_len); /* passes (size_t)-1 = huge */
    }
}

void safe(int user_len) {
    /* GOOD: check sign first, then compare magnitudes */
    if (user_len > 0 && user_len < BUFSIZE) {
        memcpy(buf, "x", (size_t)user_len);
    }
}

int main(void) {
    /* Demonstrate: -1 as unsigned is UINT_MAX */
    int neg = -1;
    unsigned u = (unsigned)neg;
    printf("(unsigned)-1 = %u\n", u);  /* 4294967295 */
    printf("-1 < 64u is %s\n",
           (unsigned)neg < 64u ? "TRUE" : "FALSE"); /* TRUE — bug! */
    return 0;
}

Overflow occurs when an arithmetic result cannot be represented in the destination type. The behavior differs critically by signedness:

Unsigned overflow (wrapping): Always wraps modulo 2ⁿ. C standard guarantees this. UINT_MAX + 1 == 0. Useful for timestamps, sequence numbers, and hash functions that intentionally wrap. The TCP sequence number space is a 32-bit modular counter.

Signed overflow (undefined behavior in C/C++): The standard says the behavior is undefined — the program has no meaning. In practice:

• Without optimization: usually wraps on two's complement hardware.
• With -O2 or -O3: the compiler exploits UB for optimization. for (int i = 0; i >= 0; i++) can be compiled as an infinite loop because the compiler assumes i never overflows, so the condition is always true.
• With -fwrapv (Linux kernel uses this): wraps reliably.
• With -fsanitize=signed-integer-overflow (UBSan): traps at runtime.

Common overflow scenarios in systems code:

1. size_t n = count * sizeof(T) — if count is attacker-controlled and overflows size_t, n is too small.
2. int offset = base + user_delta — signed overflow in pointer arithmetic.
3. Loop counters that were meant to stop but don't because the termination condition uses a signed variable that wraps.

Detection without UBSan (for C, using GCC builtins):

if (__builtin_add_overflow(a, b, &result)) { /* handle */ }

This compiles to a single add + jo (jump-on-overflow) on x86-64 — essentially zero overhead.

/* Demonstrate overflow behavior and safe alternatives */
#include <stdint.h>
#include <stdio.h>
#include <stdbool.h>

int main(void) {
    /* Unsigned wrapping — well defined */
    uint32_t u = UINT32_MAX;
    printf("UINT32_MAX + 1 = %u\n", u + 1);  /* 0 */

    /* Signed overflow — avoid in production; compile with -fwrapv to test */
    /* int32_t s = INT32_MAX; s + 1 is UB without -fwrapv */

    /* Safe: use GCC/Clang built-in overflow check */
    int32_t a = 2000000000, b = 2000000000, result;
    if (__builtin_add_overflow(a, b, &result)) {
        printf("Signed overflow detected!\n");
    } else {
        printf("Result: %d\n", result);
    }

    /* Kernel-style size multiplication check */
    size_t count = (size_t)-1 / 4 + 1; /* one more than fits */
    size_t bytes;
    if (__builtin_mul_overflow(count, (size_t)4, &bytes)) {
        printf("Allocation size overflow!\n");
    }
    return 0;
}

When you move a value from a narrower type to a wider type, the extra bits must be filled somehow. The rule depends on whether the source is signed or unsigned.

Zero extension (unsigned source): Fill the new high bits with 0. (uint32_t)(uint8_t)200 = 200. Simple and obvious.

Sign extension (signed source): Copy the MSB (sign bit) into all new high bits. (int32_t)(int8_t)-5 = −5. Let's see why this works:

• int8_t −5 is 11111011.
• Sign-extending to 32 bits: 11111111 11111111 11111111 11111011.
• This 32-bit two's complement value is −2³¹ + 2³⁰ + … + 2³ + 2¹ + 2⁰ = −5. Correct!

Sign extension preserves the numeric value. Zero extension also preserves the numeric value — for unsigned values. The rules are:

• (int32_t)(uint8_t)x → zero-extend (source is unsigned, fill with 0s)
• (int32_t)(int8_t)x → sign-extend (source is signed, fill with sign bit)
• (uint32_t)(int8_t)x → sign-extend to 32 bits, then reinterpret as unsigned

That last rule is the source of many surprises. (uint32_t)(int8_t)-1 is 0xFFFFFFFF = 4,294,967,295, not 255.

In assembly, dedicated instructions handle this:

• x86: MOVSX (move with sign extension), MOVZX (move with zero extension)
• ARM: SXTB/SXTH/SXTW, UXTB/UXTH
• RISC-V: sign extension is built into load instructions (lb = load byte sign-extended, lbu = load byte zero-extended)

In the Linux kernel, functions that read user-supplied values from hardware registers or network packets must be meticulous about which extension they use. A driver reading an 8-bit signed temperature sensor must use (int8_t) casts to preserve the sign, not (uint8_t) which would turn −10°C into 246.

/* Sign extension vs zero extension */
#include <stdint.h>
#include <stdio.h>

int main(void) {
    int8_t  s8 = -5;       /* 0xFB */
    uint8_t u8 = 251;      /* 0xFB — same bits, different meaning */

    /* Zero-extending unsigned: fills with 0s */
    uint32_t ze = (uint32_t)u8;
    printf("zero-extend 251  -> %u (0x%08X)\n", ze, ze); /* 251 */

    /* Sign-extending signed: fills with sign bit (1s for negative) */
    int32_t  se = (int32_t)s8;
    printf("sign-extend -5   -> %d (0x%08X)\n", se, (uint32_t)se); /* -5 */

    /* The trap: sign-extend then reinterpret as unsigned */
    uint32_t trap = (uint32_t)(int32_t)s8;  /* sign-extend FIRST */
    printf("(uint32_t)(int32_t)-5 = %u (0x%08X)\n", trap, trap); /* huge! */

    /* Correct for unsigned context: zero-extend */
    uint32_t correct = (uint32_t)u8;  /* u8 is already unsigned */
    printf("(uint32_t)(uint8_t)251 = %u\n", correct);  /* 251 */
    return 0;
}

The C standard defines char, short, int, long, long long with minimum sizes but allows them to vary by platform. This ambiguity is a recurring source of portability bugs in kernel and systems code.

Platform-dependent sizes (implementation-defined):

• int: at least 16 bits; 32 bits on virtually all current platforms
• long: 32 bits on Windows (LP32/LLP64), 64 bits on Linux/macOS x86-64 (LP64)
• long long: at least 64 bits

This means sizeof(long) is 4 on Windows 64-bit but 8 on Linux 64-bit. Code that assumes otherwise is broken on one of them.

Fixed-width types (<stdint.h>, C99+):

• int8_t / uint8_t: exactly 8 bits
• int16_t / uint16_t: exactly 16 bits
• int32_t / uint32_t: exactly 32 bits
• int64_t / uint64_t: exactly 64 bits

The Linux kernel defines its own equivalents in <linux/types.h>: __u8, __u16, __u32, __u64 (and signed variants __s8 etc.), used in uAPI headers that must be stable across all compilers. Inside the kernel, u8/u16/u32/u64 are the preferred aliases.

Why ranges are exactly 2ⁿ−1 (unsigned) and −2ⁿ⁻¹ to 2ⁿ⁻¹−1 (signed): Unsigned: n bits encode 2ⁿ states: 0, 1, …, 2ⁿ−1. Signed (two's complement): MSB has weight −2ⁿ⁻¹. The most negative value is 100…0 = −2ⁿ⁻¹. The most positive is 011…1 = 2ⁿ⁻¹−1. The asymmetry is structural.

The INT_MIN pitfall: −INT_MIN on a 32-bit system should be 2,147,483,648 which does not fit in int32_t. abs(INT_MIN) is undefined behavior. The Linux kernel has explicit guards against this in places where user space can control the value.

#include <stdint.h>
#include <limits.h>
#include <stdio.h>

int main(void) {
    /* Show ranges using the formulas */
    printf("uint8  : 0 to %u\n",   (uint8_t)-1);           /* 255 */
    printf("int8   : %d to %d\n",  INT8_MIN,  INT8_MAX);   /* -128 to 127 */
    printf("uint32 : 0 to %u\n",   UINT32_MAX);            /* 4294967295 */
    printf("int32  : %d to %d\n",  INT32_MIN, INT32_MAX);  /* -2^31 to 2^31-1 */
    printf("uint64 : 0 to %llu\n", UINT64_MAX);
    printf("int64  : %lld to %lld\n", INT64_MIN, INT64_MAX);

    /* Platform-dependent sizes */
    printf("sizeof(int)       = %zu\n", sizeof(int));    /* 4 on x86-64 */
    printf("sizeof(long)      = %zu\n", sizeof(long));   /* 8 on Linux x86-64 */
    printf("sizeof(long long) = %zu\n", sizeof(long long)); /* 8 */

    /* The INT_MIN trap */
    int32_t m = INT32_MIN;  /* -2147483648 */
    printf("INT32_MIN negated wraps: %d\n", -m); /* -2147483648 again (UB!) */
    return 0;
}

Two's complement enables a family of efficient bit-manipulation idioms that appear throughout the Linux kernel and compiler-generated code. Understanding these lets you read low-level code fluently.

Arithmetic right shift vs. logical right shift: Shifting right by 1 divides by 2 for unsigned numbers (logical shift: fill with 0). For signed two's complement, an arithmetic right shift fills the vacated bits with the sign bit, preserving the sign. So −8 >> 1 should give −4, not 2,147,483,644. In C, right-shifting a signed negative value is implementation-defined (but on every real platform it does arithmetic shift). GCC documents this for all its targets.

Fast sign test: x >> (WORD_BITS - 1) gives all-zeros (positive/zero) or all-ones (negative) for signed x. Used to create a mask without branches.

Conditional negate without branching:

int mask = x >> 31;      /* 0x00000000 or 0xFFFFFFFF */
int abs_x = (x + mask) ^ mask;  /* |x| without if/else */

This is how abs() is often compiled.

Power-of-two check: x != 0 && (x & (x - 1)) == 0. When x is a power of two, it has exactly one 1-bit; subtracting 1 flips that bit and sets all lower bits; AND with original gives 0.

Clearing the lowest set bit: x & (x - 1). Kerneluse: __builtin_ctz (count trailing zeros) and related bit ops in memory allocators and scheduling bitmaps.

Rounding up to alignment: (x + (align - 1)) & ~(align - 1) — the ALIGN() macro in <linux/align.h>. For align=4: add 3, then zero the low 2 bits.

These tricks are not just clever — they avoid branches, which means no branch misprediction penalties on modern out-of-order CPUs. In a hot kernel path called millions of times per second, that matters.

/* Bit-manipulation idioms from real systems code */
#include <stdint.h>
#include <stdio.h>

#define ALIGN_UP(x, a)  (((x) + (a) - 1) & ~((a) - 1))

static inline int is_power_of_two(uint32_t x) {
    return x != 0 && (x & (x - 1)) == 0;
}

static inline int32_t abs_branchless(int32_t x) {
    int32_t mask = x >> 31;       /* arithmetic shift: all 0s or all 1s */
    return (x + mask) ^ mask;     /* conditional negate */
}

int main(void) {
    printf("ALIGN_UP(13, 4)  = %u\n", ALIGN_UP(13u, 4u));  /* 16 */
    printf("ALIGN_UP(16, 4)  = %u\n", ALIGN_UP(16u, 4u));  /* 16 */
    printf("ALIGN_UP(17, 8)  = %u\n", ALIGN_UP(17u, 8u));  /* 24 */

    printf("pow2(8)=%d pow2(7)=%d\n",
           is_power_of_two(8), is_power_of_two(7)); /* 1 0 */

    printf("abs(-5)=%d abs(5)=%d\n",
           abs_branchless(-5), abs_branchless(5));  /* 5 5 */

    /* Arithmetic shift on signed negative */
    int32_t neg = -8;
    printf("-8 >> 1 = %d (arithmetic)\n", neg >> 1);  /* -4 */
    printf("-8 as bits: ");
    for (int i = 31; i >= 0; i--) putchar('0' + ((neg >> i) & 1));
    putchar('\n');
    return 0;
}

At the ISA level, the CPU mostly has one set of addition/subtraction instructions that work identically for signed and unsigned — because two's complement makes that possible. The difference is in which condition flags you check afterward.

On x86-64, ADD sets:

• CF (Carry Flag): set when unsigned overflow occurs (carry out of MSB).
• OF (Overflow Flag): set when signed overflow occurs (sign changed unexpectedly).
• SF (Sign Flag): the MSB of the result.
• ZF (Zero Flag): result is zero.

Signed vs. unsigned branches check different flags:

• JA/JB (jump-above/jump-below): unsigned comparison — checks CF.
• JG/JL (jump-greater/jump-less): signed comparison — checks OF and SF.

The compiler emits different jump instructions based on whether the C variables are int or unsigned int. Same arithmetic instruction, different check.

On RISC-V, the ISA is even more explicit: SLTU (set-less-than unsigned) and SLT (set-less-than signed) are distinct instructions. Load instructions lb (load byte signed) and lbu (load byte unsigned) explicitly encode the extension type.

You can see all this in Compiler Explorer (godbolt.org): write a simple signed-vs-unsigned comparison in C and flip the types — the jump instruction changes from jl to jb. This is the live embodiment of the theory.

// x86-64 assembly for signed vs unsigned comparison
// (illustrative; view exact output at godbolt.org)

// C source:
//   int is_less_signed(int a, int b)   { return a < b; }
//   int is_less_unsigned(uint32_t a, uint32_t b) { return a < b; }

// Compiled output (conceptual, gcc -O2):
//
// is_less_signed:
//     cmp  edi, esi
//     setl al        ; set if less (signed): OF != SF
//     movzx eax, al
//     ret
//
// is_less_unsigned:
//     cmp  edi, esi
//     setb al        ; set if below (unsigned): CF == 1
//     movzx eax, al
//     ret
//
// Same CMP, different SET instruction — the entire
// signed vs unsigned distinction lives in the branch opcode.

The Linux kernel is 25+ million lines of C. Integer overflow bugs appear regularly in security audits. Understanding the patterns lets you both read kernel code critically and write safe code.

Pattern 1 — Size multiplication: vmalloc(count * size) where both are user-controlled. Fix: array_size(count, size) from <linux/overflow.h>, which returns SIZE_MAX on overflow, causing the allocation to fail gracefully rather than succeed with too-small a buffer.

Pattern 2 — Index arithmetic in ioctl handlers: offset + length > buf_size where offset and length are u32. If offset + length overflows u32 it wraps to a small number, the check passes, and the copy proceeds out of bounds. Fix: check length > buf_size - offset (avoids the addition entirely, safe if offset <= buf_size).

Pattern 3 — Signed/unsigned mismatch in comparisons: A function returns int as an error code (negative) or a valid size (non-negative). The caller stores it in size_t (unsigned). size_t sz = read(...); if (sz > MAX) — the check is skipped when sz is (size_t)-1 (error cast to unsigned).

The kernel's tools:

• <linux/overflow.h>: check_add_overflow(), check_mul_overflow(), array_size(), struct_size().
• CONFIG_UBSAN_INTEGER_OVERFLOW: runtime sanitizer.
• CONFIG_KASAN: catches some downstream effects of overflows.
• Sparse (make C=1): static analysis tool that tracks sign mismatches; understands __user, __be32, etc.

The struct_size(ptr, array_member, count) macro from <linux/overflow.h> is the canonical way to calculate sizes of flexible-array-member structs and appears hundreds of times in driver code.

/* Kernel-style safe size computation */
/* This mimics <linux/overflow.h> patterns */
#include <stdint.h>
#include <stddef.h>
#include <stdio.h>
#include <limits.h>

/* Safe array size: returns SIZE_MAX on overflow */
static inline size_t array_size(size_t a, size_t b) {
    size_t result;
    if (__builtin_mul_overflow(a, b, &result))
        return SIZE_MAX;  /* signals overflow to caller */
    return result;
}

int main(void) {
    /* Attacker controls count; element size is fixed */
    size_t count = SIZE_MAX / 8 + 2;  /* just enough to overflow * 8 */
    size_t sz = array_size(count, 8);

    if (sz == SIZE_MAX) {
        printf("Overflow detected; refusing allocation.\n");
    } else {
        printf("Safe to allocate %zu bytes\n", sz);
    }

    /* Safe index check: avoid addition overflow */
    uint32_t offset = 0xFFFFFFF0, length = 0x20, buf_size = 0x100;
    if (length > buf_size || offset > buf_size - length) {
        printf("Access out of bounds (caught safely)\n");
    }
    return 0;
}