Assembly, from Zero: x86-64 and ARM64

A guidebook for software engineers. Third in the series, after the Rust performance guidebook and the SIMD guidebook.

By the end of this guidebook you will be able to do eight things:

1. Read the assembly that compilers, debuggers, profilers and crash dumps show you, and know what each line is doing.
2. Write functions by hand on x86-64 and ARM64 that obey the calling convention, run, and can be called from C or Rust.
3. Decode instruction bytes by hand, because you will know how both machines pack an instruction into bytes.
4. Predict what a loop costs, because you will know how a CPU really runs instructions (not just how the manual says it does).
5. Reason about atomics and memory ordering on both a strong machine (x86-64) and a weak one (ARM64).
6. Embed assembly in Rust with asm!, global_asm! and naked functions, and know when not to.
7. Generate assembly from your own compiler, and build a dispatch loop and a tiny JIT for your own interpreter.
8. Teach all of it, from a five-minute explanation to a talk for 500 people.

If you finish the capstones, you will not feel "I read about assembly." You will feel "I can sit in front of a machine I have never seen, and it will not scare me."

A note on "I". This guidebook was written by an AI (Claude), working in a sandbox with real tools. When the text says "I ran this," "I measured that" or "I could not check this," it means exactly that: the command was run, or the check was not possible, during the writing. Nothing in it is a story about a human author's past. If you publish this under your own name, change the "I" where it feels wrong to you, but keep the honesty: say what you ran yourself and what you did not.

How to use this guidebook

Every chapter has the same shape, and every shape answers three questions:

Each chapter walks through these in order: The problem first, The model, Build it, Why it is this way, Common mistakes, Say it simply, and Check yourself.

Do the exercises. Reading alone is half the learning. Each chapter ends with exercises, and each is marked with a level:

• Warm-up: do it right after reading. It checks that the words and the picture landed.
• Core: needs the chapter's main ideas used together. Do all of these.
• Stretch: needs extra thinking or a longer build. For when you want more.

Many exercises start with Predict, then check. Write your prediction down on paper first. The gap between what you predicted and what you saw is where the learning happens.

How code is marked. Every code block says which machine it is for. If I ran it while writing this guidebook, the output below it is the real output. If I could not run it, it says Not run: check this on your machine. I never show made-up output as real. Where a number is only an illustration, it is labeled as one.

A note on voice. This guidebook says "we" when we do a step together, "you" when I talk to you, and "I" only for honest opinions and honest limits, like "I could not check this on real hardware."

What you need before you start

Skills. You can program in some language (Rust or C is best). You are fine with a terminal. You know what hex is (0xFF is 255). That's all. We build everything else.

Default platform. Linux on x86-64, and ARM64 side by side. Where macOS or Windows differ, a box says so.

Tools. On Ubuntu or Debian (or WSL2 on Windows):

sudo apt install binutils gcc clang llvm gdb strace xxd qemu-user \
                 binutils-aarch64-linux-gnu gcc-aarch64-linux-gnu
# Rust: install with rustup (https://rustup.rs). Use 1.88 or newer for
# naked functions (Chapter 35). Everything else needs only 1.59+.

If you are on Apple silicon, you already have an ARM64 machine. Use Docker or a Linux VM for the x86-64 examples. If you have no ARM64 machine, qemu-aarch64 runs ARM64 Linux programs on your x86-64 laptop.

Versions used to write and check this guidebook (the sandbox was Ubuntu 24.04, checked in October 2026):

Newer tools behave the same for everything we use.

The machine behind the measurements. An Intel Xeon @ 2.80 GHz, one core, x86-64, in a rented virtual machine. Your numbers will differ. The shapes will not: a branch miss will still hurt, a cache miss will still hurt more.

One more thing, and I want to be straight about it. While I was writing, the hardware under my virtual machine changed. The CPU flags it reported were different in different sessions, and some measurements moved by up to 2 times (others, such as the cost of a dependent add or the 9-times penalty for a random branch, did not move at all). So I took the numbers that are meant to be compared with each other back to back in one session, I repeated the important ones, and wherever two sessions disagreed I tell you both. Read the note at the start of Part 8, and treat every absolute number in this guidebook as "an example from one machine," and every ratio as the thing to trust.

What I could not check. I want to be honest about this up front:

• ARM64 code ran under qemu-user. That is an emulator. It gives correct results, but not real ARM64 timing and not real weak-memory behavior.
• The sandbox had one core. So I could not catch a real memory-ordering reorder, or show false sharing. Chapters 27 and 31 explain this and give you the tests to run on your own multi-core machine.
• The virtual machine did not expose hardware performance counters (perf stat printed <not supported>), so every perf command in this guidebook is marked as not run.
• Naked functions (Rust 1.88+) were not run, because the sandbox compiler was 1.75.

Study paths

"I have a weekend." Part 1 (Chapters 1 to 4), then Chapter 5, Chapter 10 to 12, and Chapter 14 to 15. You will be able to read disassembly and write a tiny function.

"I want to read compiler output well." Part 1, Part 2 (Chapters 6 and 7 especially), Part 3, Chapter 14 to 16, Chapter 19, then Part 8 and Chapter 33.

"I want to write a compiler backend or a JIT." Parts 1 to 4, Chapters 18 to 20, Chapter 24, then all of Part 12.

"I want to give a talk." Part 1, Chapter 12, Chapter 15, Chapter 26, Chapter 31, then the Teaching Kit.

"I want to master it." Everything in order. Plan about 13 weeks, with exercises. The Teaching Kit has a schedule.

Table of contents

Part 1: The Machine

• Chapter 1. What assembly is, and why you would learn it
• Chapter 2. The machine: one loop, a few registers, one big array
• Chapter 3. Two machines: x86-64 and ARM64
• Chapter 4. Your toolchain and your first two programs
• Chapter 5. Reading assembly: the vocabulary and the method

Part 2: Memory and Data Movement

• Chapter 6. Moving data: memory, mov, widths and constants
• Chapter 7. Addressing modes: how an address is built
• Chapter 8. The stack is just memory with a register in charge
• Chapter 9. Data in memory: sections, structs and padding

Part 3: Control Flow, Flags and Branches

• Chapter 10. Flags: one-bit answers to comparison questions
• Chapter 11. Branches and loops
• Chapter 12. Branch prediction and branchless code
• Chapter 13. Jump tables and indirect branches

Part 4: Functions and the Calling Convention

• Chapter 14. The calling convention: a contract between strangers
• Chapter 15. The frame: prologue, epilogue, alignment and unwinding
• Chapter 16. Writing real functions by hand
• Chapter 17. The ABI zoo: other systems, other rules

Part 5: Arithmetic

• Chapter 18. Integers: add, subtract, carry and overflow
• Chapter 19. Multiply and divide: the expensive operations
• Chapter 20. Shifts, rotates and bit tricks
• Chapter 21. Floating point: the other register file

Part 6: Real Programs

• Chapter 22. Strings and memory: strlen, memcpy and the speed ladder
• Chapter 23. Talking to the kernel: system calls, the start-up stack and a cat clone

Part 7: How Instructions Become Bytes

• Chapter 24. x86-64 encoding: prefix, opcode, ModRM, SIB
• Chapter 25. ARM64 encoding: 32 bits, fields and fit

Part 8: How the CPU Really Runs Your Code

• Chapter 26. Out-of-order execution: latency, throughput and the dependency chain
• Chapter 27. The memory hierarchy: caches, parallel misses and what the prefetcher does
• Chapter 28. Measuring honestly: benchmarks, models and the tools

Part 9: SIMD from the Assembly Side

• Chapter 29. Vector instructions in assembly: lanes, masks and vector-length-agnostic code

Part 10: Concurrency at the Instruction Level

• Chapter 30. Atomic read-modify-write: lock, load-exclusive and LSE
• Chapter 31. Memory ordering: the strong machine and the weak machine

Part 11: The Toolchain, Compilers and Rust

• Chapter 32. Objects, relocations and linking
• Chapter 33. What compilers do: reading optimized output
• Chapter 34. Finding the instruction behind a crash
• Chapter 35. Assembly inside Rust: asm!, global_asm! and naked functions

Part 12: Assembly for Language Builders

• Chapter 36. A compiler backend in 130 lines: from expressions to assembly on two machines
• Chapter 37. Interpreter dispatch: switch, computed goto and tail calls
• Chapter 38. A tiny JIT: writing machine code into memory and calling it

Part 13: Putting It All Together

• Chapter 39. The philosophy of the machine

The Teaching Kit

The Capstone Projects

Appendix A: Cheat sheets

Glossary

Reading map

Part 1: The Machine

After this Part you can read a small compiled function, run and break a program on both machines, and say what a CPU does in one loop. This is the foundation. Every later Part stands on it.

Chapter 1. What assembly is, and why you would learn it

In this chapter: You will see the problem assembly was invented to solve. You will learn what an assembler really does, and why this skill is still useful when compilers are so good. You will also learn what "assembly" does not mean: it is not one language.

You need first: Nothing.

The problem first

A CPU only understands numbers. A program, at the lowest level, is a long list of numbers in memory. Each number (or small group of numbers) tells the CPU to do one small thing.

Picture a programmer who writes those numbers by hand. Here is a tiny real program. It jumps over two do-nothing instructions and returns:

address   bytes    what it means
0         eb 02    jump forward 2 bytes
2         90       nop (do nothing)
3         90       nop (do nothing)
4         c3       ret   <-- the jump lands here

Now you decide you need one more nop. Add it, and look what happens:

address   bytes    what it means
0         eb 03    jump forward 3 bytes     <-- you had to change this
2         90       nop
3         90       nop
4         90       nop
5         c3       ret

The 02 had to become 03. Those are real bytes from the GNU assembler. By hand, you would have to find every jump and every data reference that crosses your edit, and fix each one. Miss one, and the program jumps into the middle of an instruction.

The hard part was never the numbers. The hard part was that one small edit moved everything after it.

The fix is old and simple. Give each place a name, and let a tool count the bytes. The names are called labels. The tool is called an assembler. You write jmp done, and the assembler works out eb 02 or eb 03 for you.

The model (the "what")

Machine code is the numbers the CPU reads. Assembly language is the same thing, written with names instead of numbers. An assembler is the program that turns the names back into numbers.

 you write            the assembler produces       the CPU sees
 ---------            ----------------------       ------------
 add rax, rbx   -->   48 01 d8                -->  "add the register rbx into rax"

Those bytes are real: I assembled this line and looked at the result with objdump. Notice what the assembler did not do. It did not optimize. It did not check your logic. One line becomes (mostly) one instruction. The line between "assembly" and "machine code" is a text editor.

Three things change from one machine to the next, and you must keep them apart:

So "assembly" is not one language. It is a family. This guidebook teaches the two ISAs that run almost everything today: x86-64 (most servers, desktops and laptops) and ARM64 (phones, Apple silicon, many cloud chips). Holding both in your head at once is the trick. You will see what is true of every CPU, and what is just one company's taste.

Why learn it at all? Compilers are very good. So why? There are four reasons that last.

1. To read. Profilers, debuggers, crash dumps and Compiler Explorer all end in assembly. If you cannot read it, those tools go silent exactly when the problem gets hard. This is the most common use, and the first thing we build.
2. To know what the machine can do. A compiler can only use instructions that exist. If you do not know that the CPU has an instruction that adds eight numbers at once, you cannot ask for it.
3. To write where it matters. Some code cannot be written in a high-level language. The first instructions that run when the kernel is entered, the code that switches between threads, and parts of crypto libraries are written by hand.
4. To debug what only exists down there. A stack that is not aligned. A function that breaks a calling convention. A value that lost its upper bits. You cannot see these in source code. In assembly they are obvious.

Build it (the "how")

Let's do the single most useful habit in this whole guidebook: predict, then look.

Take this C function. Before reading further, write down what you think the x86-64 assembly will be.

int add(int a, int b) { return a + b; }

Now here is what gcc -O2 produced on this guidebook's machine, for both ISAs:

# x86-64, gcc 13.3 -O2 (Intel syntax)
add:
    lea     eax, [rdi+rsi]
    ret

// ARM64, gcc 13.3 -O2
add:
    add     w0, w0, w1
    ret

Did you expect add eax, ... on x86-64? Most people do. The compiler used lea, an instruction whose name means "load effective address." It is an address calculator that the compiler borrows to do addition, because it can write to a different register than it reads. We meet it in Chapter 7. For now, the lesson is: the compiler knows tricks you do not yet know. Let's try two more.

long mul3(long x)  { return x * 3;  }
long mul10(long x) { return x * 10; }

# x86-64
mul3:   lea  rax, [rdi+rdi*2]        # x + x*2
        ret
mul10:  lea  rax, [rdi+rdi*4]        # x + x*4  = x*5
        add  rax, rax                # x*5 * 2  = x*10
        ret

// ARM64
mul3:   add  x0, x0, x0, lsl 1       // x + (x << 1)
        ret
mul10:  add  x0, x0, x0, lsl 2       // x + (x << 2) = x*5
        lsl  x0, x0, 1               // *2           = x*10
        ret

Neither machine used a multiply instruction. A multiply is slower than a shift and an add, so the compiler spelled x * 10 as (x + x*4) * 2. Both machines got the same idea in different words. This is the kind of thing you will start to see once you can read.

Why it is this way (the "why")

Why did anyone invent assemblers? Because of the problem at the top: moving addresses. Everything beyond labels (directives, macros, relocations, linkers) exists to keep one promise: the human writes names, and the tool computes numbers. You will meet this promise again in Chapter 32 when we open the linker.

Here is a claim you will hear: "in assembly, the machine does exactly what you wrote." It is half true, so let's be careful. The compiler no longer moves your work around. That part is true. But the CPU still does. A modern CPU runs many instructions at once, out of order, and guesses which way branches will go. It is only required to make the result look as if it ran your instructions one by one. So assembly removes the compiler's tricks. It does not remove the CPU's tricks. Part 8 is about those.

What would have to be true for "assembly is obsolete" to be correct? It would have to be true that no bug and no slowdown ever crosses the line between your source code and the machine. But they do, all the time. A function that reads a long as an int. A struct with padding you did not expect. A loop that never got vectorized. Each of these is easy to see in assembly and invisible in source.

Common mistakes

• Thinking assembly is one language. It is not. An x86-64 program is noise to an ARM64 chip. What transfers is the mental model: registers, memory, flags, the stack, the calling convention.
• Thinking hand-written assembly beats the compiler. For general code it usually loses. A compiler tries thousands of tricks per second and never gets tired. Hand-written assembly wins only when you know something the compiler cannot (a special instruction, a calling convention it does not know, a timing rule).
• Thinking you must write big programs. You will write small ones. The real prize is reading big ones.

Say it simply

Assembly is machine code with names. An assembler is a tool that turns the names back into numbers and counts the addresses for you. Each kind of CPU has its own assembly, so it is a family and not one language. You learn it mostly to read what compilers and debuggers show you, and to understand what the machine can really do.

Check yourself

Exercise 1.1 (Warm-up): Explain. In five sentences, explain to a friend what an assembler does. Use one analogy and say where it breaks. What a strong answer includes: it turns names into numbers; it counts addresses so edits do not break jumps; it does not optimize; one line is roughly one instruction; an analogy (a phone's contact list turns names into numbers) with a limit (a contact list does not compute distances).

Exercise 1.2 (Warm-up): Predict, then check. Write a file with jmp done, then five nop lines, then done: ret. Predict the bytes of the jmp. Then assemble and check. Now put 200 nops in the middle (use .rept 200 and .endr). Predict again. Setup: as -o j.o j.s && objdump -d -M intel j.o, with .intel_syntax noprefix at the top. A correct result: the first jump is 2 bytes (eb 05). The second one is longer, because a 1-byte distance cannot reach 200. Hint: look at the first byte.

Exercise 1.3 (Core): Predict, then check. Predict the x86-64 -O2 output for each of these, then check on Compiler Explorer or with gcc -O2 -S -masm=intel: long mul5(long x), unsigned long div4(unsigned long x), unsigned long mod8(unsigned long x). A correct result: no imul, div or idiv appears in any of them. (On this guidebook's machine: lea, then shr, then and.) Write one sentence for each saying why the compiler's trick is valid.

Exercise 1.4 (Core): Compare the machines. Compile long f(long a, long b) { return a*2 + b; } for x86-64 and for ARM64 (aarch64-linux-gnu-gcc -O2 -S). Both fit in two instructions. Without looking anything up, say what the one line of each does. A correct result: x86-64 uses lea to do a scaled add; ARM64 uses add with a shifted operand (lsl 1). Both fold the "times two" into the add.

Exercise 1.5 (Stretch): Design and defend. A manager says: "Assembly is obsolete. We will remove it from interviews." Write a short, fair answer that agrees with what is true in this and says what is lost. What a strong answer includes: writing it by hand is rare and shrinking; reading it is needed more each year (profilers, crash dumps, closed-source binaries, compiler output); a person who can read it debugs faster; the cost of not knowing it shows up only on hard bugs.

Chapter 2. The machine: one loop, a few registers, one big array

In this chapter: You will learn the one mental model that every later chapter uses. A CPU is a small box with a few storage cells, connected to a very large memory, running one loop. You will build a toy CPU in Rust (about 40 lines) so the loop is not abstract.

You need first: Chapter 1.

The problem first

A modern CPU has billions of transistors. You cannot reason about that. Yet programmers reason about programs on it every day, and are right. How?

Because there is a contract: a small, simple picture of the machine. If the hardware keeps the contract, you never need to think about the transistors. This chapter is about that picture.

The model (the "what")

Here is the whole picture. A CPU has:

• a few storage cells inside it, called registers;
• a connection to a very large memory, which is a long row of bytes;
• one special register, the program counter, that says which instruction is next (it is called rip on x86-64 and pc on ARM64);
• a few flags: single bits that remember facts about the last operation, such as "the result was zero."

The program itself lives in memory as ordinary bytes. This is called the stored-program idea: the instructions and the data live in the same memory.

The CPU runs one loop, forever:

        +----------------------------------------------+
        |                                              |
        v                                              |
   +---------+     +---------+     +----------+     +--+------+
   |  FETCH  |---->| DECODE  |---->| EXECUTE  |---->| ADVANCE |
   +---------+     +---------+     +----------+     +---------+
   read the        work out        do it: compute,   move the pc
   bytes at pc     what they mean  or read/write     to the next
                                   memory            instruction

Look at the diagram and find the one place where control flow lives. It is the last box. Normally "advance" moves the program counter to the next instruction. A branch (or jump) is just an instruction that sets the program counter to somewhere else instead. That is the only way a program ever changes what it does next. Loops, if, function calls, exceptions, even the operating system switching between programs: all of them come down to "something set the program counter."

Now the cells themselves. Registers are the fastest storage there is. The next instruction can use a register value almost immediately. But they are few:

Why so few? Because every instruction has to name its registers, and names cost bits. Sixteen registers need 4 bits per name. Thirty-one need 5. That is why a 32-bit instruction can still name three registers on ARM64 (Chapter 25). A machine with four hundred registers would make every instruction bigger, for a benefit that most code cannot use. When a program needs more values than there are registers, the compiler spills some into memory and loads them back later. You will see spill code in every large function you read.

Memory is the opposite: huge and slow. Here are numbers measured on this guidebook's machine, by chasing a chain of pointers so each load must wait for the one before it:

A register is available in less than one nanosecond. Memory that missed every cache took about 100 times longer. (About the 8 MiB row: my first run read 121 ns. A second run read 37 ns, and I wrongly called the first one noise. A third session read about 137 ns again. The real cause was that my rented virtual machine had been moved between different physical hosts, which have different shared caches. Part 8 tells that story, because it is a lesson in itself. For now, take the lesson to be the two ends of the table: a first-level hit is under 2 ns, and main memory is 100 times slower.) The gap between those two is where most of performance engineering lives. Chapter 27 returns to it.

One rule follows: to compute on a value, it must be in a register. (x86-64 bends this a little. Some instructions can take one operand directly from memory, but the CPU still loads it first.)

Three small facts will save you pain later.

1. Instructions are data. A program can read its own bytes. A program can also write bytes and then run them. That is exactly what a JIT compiler does (Chapter 38). Modern systems restrict this with page permissions, but the idea underneath is that code is just bytes.
2. The loop is a contract, not the silicon. Real CPUs run many instructions at once and out of order. The loop above is what they promise looks true from outside. Part 8 shows what is really inside.
3. The state is small. At any moment, everything the machine "knows" is: all the registers, all the flags, all of memory, and the program counter. A debugger shows you exactly this. A bug is a gap between the state you believe the machine is in and the state it is really in. Assembly gives you no place to hide a wrong belief.

An analogy that helps: think of a cook at a kitchen counter. The counter is the registers: small, but everything on it is within reach. The pantry is memory: big, but each trip takes time. The cook's finger on the recipe line is the program counter. Now the limits of the analogy. In the kitchen the recipe is on paper, separate from the food. Here the recipe is stored in the pantry too, and the cook can edit it. Also a real cook can read ahead and prepare the next steps. A CPU does exactly that, and has to hide it so the result looks as if no one read ahead.

Build it (the "how")

The best way to understand a loop is to build it. Here is a toy CPU in Rust. It has 4 registers, 256 bytes of memory, a program counter, one flag, and 5 instructions. The program sums the numbers 1 to 10. Notice that the program is stored in the same memory array as everything else.

// A toy CPU: 4 registers, 256 bytes of memory, 5 instructions.
const HALT: u8 = 0; // HALT                (1 byte)
const LOADI: u8 = 1; // LOADI reg, number  (3 bytes)
const ADD: u8 = 2; // ADD reg, reg         (3 bytes)
const DEC: u8 = 3; // DEC reg              (2 bytes)  sets the zero flag
const JNZ: u8 = 4; // JNZ address          (2 bytes)  jump if zero flag is 0

fn main() {
    let mut mem = [0u8; 256];
    let program: [u8; 14] = [
        1, 0, 0,  //  0: LOADI r0, 0     sum = 0
        1, 1, 10, //  3: LOADI r1, 10    i = 10
        2, 0, 1,  //  6: ADD   r0, r1    sum += i     <- loop starts here
        3, 1,     //  9: DEC   r1        i -= 1
        4, 6,     // 11: JNZ   6         if i != 0, go back to address 6
        0,        // 13: HALT
    ];
    mem[..program.len()].copy_from_slice(&program); // the program lives in memory

    let mut reg = [0u8; 4];
    let mut pc: usize = 0; // program counter
    let mut zero = false;  // the one flag
    let mut steps = 0;

    loop {
        let opcode = mem[pc]; // FETCH
        steps += 1;
        match opcode { // DECODE + EXECUTE
            LOADI => { reg[mem[pc + 1] as usize] = mem[pc + 2]; pc += 3; }
            ADD => { let (d, s) = (mem[pc + 1] as usize, mem[pc + 2] as usize);
                     reg[d] = reg[d].wrapping_add(reg[s]); pc += 3; }
            DEC => { let r = mem[pc + 1] as usize;
                     reg[r] = reg[r].wrapping_sub(1); zero = reg[r] == 0; pc += 2; }
            JNZ => { if !zero { pc = mem[pc + 1] as usize; } else { pc += 2; } }
            HALT => break,
            _ => panic!("bad opcode {} at {}", opcode, pc),
        }
        if steps <= 7 {
            println!("step {steps}: after it, pc={pc:2} r0={:3} r1={:2} zero={zero}", reg[0], reg[1]);
        }
    }
    println!("halted after {steps} steps: r0 = {} (sum of 1..=10 is 55)", reg[0]);
}

Compile with rustc -O -o toy toy.rs and run it. This is the real output from this guidebook's machine:

step 1: after it, pc= 3 r0=  0 r1= 0 zero=false
step 2: after it, pc= 6 r0=  0 r1=10 zero=false
step 3: after it, pc= 9 r0= 10 r1=10 zero=false
step 4: after it, pc=11 r0= 10 r1= 9 zero=false
step 5: after it, pc= 6 r0= 10 r1= 9 zero=false
step 6: after it, pc= 9 r0= 19 r1= 9 zero=false
step 7: after it, pc=11 r0= 19 r1= 8 zero=false
halted after 33 steps: r0 = 55 (sum of 1..=10 is 55)

Look at step 5. After the JNZ at address 11, the program counter went back to 6. That is the loop. Nothing else makes a loop. And the count adds up: 2 setup steps, then 10 trips through 3 instructions, then 1 HALT: 2 + 30 + 1 = 33.

This toy is missing almost everything a real CPU has. But it has the shape. Every machine in this guidebook is this loop with more instructions, wider registers, and a lot of cleverness hidden underneath.

Why it is this way (the "why")

Why store the program in memory with the data? Before the late 1940s, many machines were re-wired or re-plugged by hand for each new program. The stored-program idea, discussed in the mid-1940s and working in machines like the Manchester "Baby" in 1948, made a program just another thing you could load, copy and change. That one decision is why software exists as a separate thing from hardware.

The price is that code and data are the same stuff. So a bug that writes to the wrong address can rewrite a program, and an attacker who can write data can try to run it. Almost every modern security rule about memory (non-executable pages, write-protected code) exists to bring back a separation that the stored-program idea gave away.

Why is "set the program counter" the only control mechanism? Because it is the smallest possible one. With it you can build every kind of control flow. A function call is "save where to come back to, then set the pc." An interrupt is "save the state, then set the pc to a fixed handler." A context switch between two programs is "save all state of one, load all state of the other, set the pc." One small idea, used many times.

Common mistakes

• Thinking registers have types. A register is just 64 bits. Whether those bits mean a signed number, an unsigned number, an address or a float is decided by the instruction that uses them, not by the register.
• Thinking memory is fast. A cache hit is, and a miss is not. Chapter 27 has the numbers.
• Thinking the loop is literally what happens. It is the promise. What happens is cleverer.

Say it simply

A CPU is a few fast storage cells (registers) next to a huge slow memory. The program is stored in that memory as bytes. The CPU repeats one loop: fetch the instruction at the program counter, decode it, execute it, and move the counter on. A jump is just an instruction that sets the counter somewhere else. That is the only way control ever changes.

Check yourself

Exercise 2.1 (Warm-up): Trace by hand. In the toy CPU, change LOADI r1, 10 to LOADI r1, 5. Predict how many steps the machine takes and what r0 ends as. Then run it. A correct result: 2 + 5×3 + 1 = 18 steps, and r0 = 15.

Exercise 2.2 (Warm-up): Explain. In five sentences, explain the stored-program idea to a friend. Say why "instructions are data" is both useful and dangerous. Give one analogy and where it breaks. What a strong answer includes: code and data share memory; that lets programs load and generate programs (compilers, JITs); it also lets a bad write change code, so systems add permissions; the cook-and-recipe analogy fails because a real recipe is not stored in the pantry.

Exercise 2.3 (Core): Break it on purpose. In the toy CPU, move the program so that after HALT at address 13 you put the byte values 1, 0, 99 (a LOADI r0, 99 instruction), and change the HALT into a NOP-like instruction of your own that just advances pc by 1. What does the machine do when it reaches the new bytes? What did you just show about code and data? A correct result: it runs the extra bytes as an instruction, because nothing marks those bytes as "data."

Exercise 2.4 (Core): Implement. Add two instructions to the toy CPU: LOAD reg, address and STORE reg, address. Write a program that adds four numbers stored at addresses 100 to 103 and stores the total at address 104. Run it. Done when: the total is in memory at address 104, and you have printed the bytes of memory from 100 to 104.

Exercise 2.5 (Core): Predict, then check. Using the latency table above, a loop does one dependent load per step from a 256 MiB working set, and 100 million steps. Predict its run time. Then think: how long would it take if the same data fit in the first cache? A correct result: roughly 15 to 19 seconds versus roughly 0.17 seconds, a gap of about 100 times. (Your machine will differ. The shape will not.)

Exercise 2.6 (Stretch): Design and defend. The toy CPU has 4 registers. Add a fifth and a sixth. What must change in the instruction format? When would more registers stop paying off? What a strong answer includes: register numbers are stored in the instruction, so more registers need more bits; our toy uses a whole byte, so it costs nothing here, but in a real encoding every bit counts; the benefit shrinks because few programs need many live values at once.

Chapter 3. Two machines: x86-64 and ARM64

In this chapter: You will learn the honest comparison of the two instruction sets we use. You will see real numbers that contradict a common story. And you will learn the syntax dialects, so you never again lose an hour to "why are the operands backwards?"

You need first: Chapter 2.

The problem first

Why learn two machines? Because learning one makes you think "this is how a CPU works." Learning two shows you which parts are the idea of a CPU and which are one company's taste. A reader who has seen both can pick up a third in a weekend.

The model (the "what")

x86-64 descends from the 8086 chip of 1978, through an unbroken chain of backward compatibility. It grew in steps: 16 bits, then 32, then 64 (AMD designed the 64-bit step, and Intel adopted it). It is called a CISC (complex instruction set computer) design. Instructions vary in length. One instruction can do several things.

ARM64 (also called AArch64; its instruction set is called A64) was announced in 2011 as a deliberate restart. ARM dropped most of its own 32-bit past. It is a RISC (reduced instruction set computer) design. Every instruction is exactly 4 bytes. Most do one thing. Memory is touched only by dedicated load and store instructions.

Here is a side-by-side view. The numbers in the last row come from real measurement, which I'll explain below.

That last row surprised me, and it will probably surprise you. The common story says x86-64 code is denser because its instructions are variable length. So I measured it. I disassembled the C library (libc.so.6) on this guidebook's machine and measured the length of all 385,673 x86-64 instructions in it. The average was 4.16 bytes. ARM64's average is 4 by definition. The variable-length design did not buy density here. It bought a long tail: about 4% of instructions are 1 byte, and a few are 11 bytes or more, but most sit between 2 and 7.

(One honest note. The x86-64 and ARM64 libraries come from different builds, so their instruction counts are not a fair comparison. The average length of x86-64 instructions is a fair measurement of that one library.)

Syntax dialects. Each machine has more than one way to spell instructions. For x86-64, you will constantly meet two:

• Intel syntax: mov rax, rbx. The destination is on the left. Used by Intel's manuals, and by this guidebook.
• AT&T syntax: mov %rbx, %rax. The source is on the left, registers start with %, constants start with $. This is the default of objdump and gdb on Linux.

They are the same machine. Here is the real output of the same bytes in both:

$ objdump -d -M intel x.o          $ objdump -d x.o
   0:  48 01 d8   add rax,rbx         0:  48 01 d8   add %rbx,%rax

A big share of beginner confusion in disassembly is nothing more than this flip.

We will write Intel syntax, and tell the GNU assembler so with .intel_syntax noprefix at the top of every file. There is one catch: the GNU assembler wants the word ptr when you give a size. NASM writes byte [rsi]. The GNU assembler in Intel mode wants byte ptr [rsi]. Without it you get this real error:

Error: ambiguous operand size for `cmp'

For ARM64 there is effectively one syntax. Mnemonics are lowercase in output (add) and uppercase in manuals (ADD). They are identical.

A third machine, in one box. RISC-V is an open instruction set that you will meet more and more. It has 32 registers where x0 is always zero, instructions that are 32 bits (with an optional 16-bit short form), and no flags register at all: a branch compares two registers directly. Knowing x86-64 and ARM64 makes RISC-V a weekend of reading. We do not teach it here.

Build it (the "how")

Let's watch the two machines solve the same two tiny problems. First, a*2 + b:

# x86-64 (real gcc 13.3 -O2 output)
f:      lea     rax, [rsi+rdi*2]       # rax = rsi + rdi*2   (one instruction)
        ret

// ARM64 (real gcc 13.3 -O2 output)
f:      add     x0, x1, x0, lsl 1      // x0 = x1 + (x0 << 1) (one instruction)
        ret

Now the one that shows the real difference: add 1 to a number in memory. In C that is (*p)++.

# x86-64
inc:    add     QWORD PTR [rdi], 1     # one instruction: load, add, store
        ret

// ARM64
inc:    ldr     x1, [x0]               // load
        add     x1, x1, 1              // add
        str     x1, [x0]               // store
        ret

x86-64 does it in one instruction and ARM64 in three. That is the "arithmetic can read memory" row in the table, made visible. Here is the catch, and it is a good thing to hold onto: how an ISA is spelled is not how it runs. Inside a modern x86-64 core, that one instruction is split into smaller steps (a load, an add and a store) that look a lot like the three ARM64 ones. Chapter 26 shows how. So "one instruction" does not mean "one unit of work."

Why it is this way (the "why")

Both designs are answers to the same question: what do we make cheap, and what do we push somewhere else?

x86-64 made compatibility cheap. Code from 1985 still runs. The price was a complicated encoding. Instruction boundaries are ambiguous (a disassembler that starts in the wrong place produces plausible nonsense; Chapter 24 shows it). The decoder is a hard piece of hardware.

ARM64 made decoding cheap. Because every instruction is 4 bytes, finding where the next one starts is trivial, and a core can look at many instructions at once. The price was flexibility. An instruction cannot hold a big constant, or a long jump distance. So loading a 64-bit constant takes up to four instructions, and building an address takes two (Chapters 6 and 7).

Neither design is "better." Each pays in a different currency. A fair way to say it: the engineers made a bet about which costs would matter in twenty years, and both bets have worked out well enough to run the world.

One more idea to carry forward. ARM64 has a zero register: reading xzr gives 0, and writing to it throws the value away. That sounds small. But code needs zero constantly: to clear a value, to compare against zero, to discard a result. On x86-64 you spend a real instruction on it (xor eax, eax). On ARM64 it is free. A small choice, repeated in every program, is what an ISA is.

Common mistakes

• Reading AT&T and Intel as different machines. If the operands look backwards, check the syntax first.
• Believing "CISC means dense code." Measure before you believe: 4.16 bytes on average here.
• Believing "one instruction means one cheap step." It does not. See Chapter 26.

Say it simply

x86-64 is the old, compatible, variable-length machine. ARM64 is the newer, regular, fixed-length machine. They solve the same problem with different trade-offs, and neither is simply better. They also have different spellings (Intel and AT&T for x86-64), so the same bytes can look backwards. Learn both and you can see which ideas belong to every CPU.

Check yourself

Exercise 3.1 (Warm-up): Translate. Convert these Intel-syntax lines to AT&T by hand, then check with as and objdump: mov rax, rbx, add rax, 16, mov rax, [rbx], lea rsi, [rdi+rcx*4]. A correct result: operands swap; registers get %; numbers get $; memory like [rbx] becomes (%rbx); and [rdi+rcx*4] becomes (%rdi,%rcx,4).

Exercise 3.2 (Warm-up): Explain. In five sentences, explain why (*p)++ is one instruction on x86-64 and three on ARM64, and then explain why "one instruction" is misleading. What a strong answer includes: x86-64 allows a memory operand in arithmetic; ARM64 allows memory only in loads and stores; the x86-64 core internally breaks it into smaller steps; so the work is the same, and the difference is in how the instruction set packs it.

Exercise 3.3 (Core): Break it and fix it. Write the line cmp [rsi], 0 in a GNU assembler Intel-syntax file. Read the error. Fix it two ways (byte ptr and dword ptr) and look at the bytes of each. A correct result: the error says the operand size is ambiguous. The two fixes give different instructions (a different opcode and a different immediate size), because the assembler cannot guess how many bytes you meant to compare.

Exercise 3.4 (Core): Measure code density. Take a C file of at least a few hundred lines (any one you have). Compile it for x86-64 and for ARM64 with -O2 -c, and compare the .text sizes with size. Then write down what you expected before you ran it. A correct result: the two sizes are within a modest percentage of each other. A big gap means something else differs (different inlining, a different unroll). If you see one, find out why.

Exercise 3.5 (Stretch): Design and defend. Suppose you are designing a new ISA. Pick one: (a) 64 registers and 5-byte instructions, or (b) 16 registers and 3-byte instructions. For a CPU that runs mostly big loops over arrays, defend your pick against the other. What a strong answer includes: the cost of register names in bits; spills versus encoding size; decode width; instruction cache pressure; and a statement of which workload you assumed.

Chapter 4. Your toolchain and your first two programs

In this chapter: You will assemble, link, run, break, trace and debug a real program on both machines. You will learn how a program talks to the operating system. And you will see what the OS did before your first instruction ran.

You need first: Chapters 2 and 3.

The problem first

Your program only knows how to compute. It cannot touch the screen, a file, or the network. Those belong to hardware, and your code is not allowed near hardware. So how does hello, world ever reach a terminal?

The answer is that you ask the operating system, politely, with one special instruction. Everything else in this chapter is the detail of how.

The model (the "what")

A system call (syscall) is a function call into the kernel. You put a small number in a register that says which service you want. You put the arguments in other registers. Then you run one special instruction, and the kernel does the work for you.

Two syscalls are enough to build the whole first part of assembly programming: write (put bytes on a file descriptor; 1 means standard output) and exit (tell the OS you are done, with a status number).

Here is the contract on Linux. This is the real convention, from the kernel:

(An error comes back as a small negative number, which is -errno.)

Read that table twice, especially the last row. On x86-64 the syscall instruction itself uses rcx and r11 to save where to return. So both are destroyed. This will bite you in a minute. Also notice that the fourth argument is r10, not rcx.

The numbers differ because ARM64 uses a newer, tidier table, while x86-64 keeps the order it grew into. Neither is "right." They are just different histories.

A box for other systems: on macOS, you normally do not make syscalls directly. You call functions in the system library. (The raw ARM64 macOS door is svc #0x80 with the number in x16, and the numbers differ from Linux.) On Windows, there is no stable public syscall number at all. You call functions in kernel32.dll and ntdll.dll. The Linux way is the cleanest one to learn on.

Build it (the "how")

Three tools make up the whole workflow, and all three exist on any Linux system:

1. The assembler (as): a text file in, an object file out. The object file has your instructions plus notes saying "patch this address once we know where things live."
2. The linker (ld): joins object files, picks final addresses, applies those notes. It makes an executable.
3. The disassembler (objdump -d): machine code back to text. Use it constantly. The fastest way to learn what compilers do is to read what they produce.

Here is the complete x86-64 program. Print a message, then exit.

# hello_x86.s -- Linux x86-64, Intel syntax, no libc
    .intel_syntax noprefix
    .global _start              # the name the linker uses as the entry point

    .section .rodata            # read-only data
msg:
    .ascii "hello, machine\n"
msg_len = . - msg               # "." means "here", so this is the byte count

    .section .text              # code
_start:
    # write(1, msg, msg_len)
    mov     rax, 1              # syscall number: write
    mov     rdi, 1              # file descriptor 1 = standard output
    lea     rsi, [rip+msg]      # address of the message
    mov     rdx, msg_len        # how many bytes
    syscall
    # exit(0)
    mov     rax, 60             # syscall number: exit
    xor     edi, edi            # status 0
    syscall

And the same program on ARM64:

// hello_arm.s -- Linux ARM64, no libc
    .global _start

    .section .rodata
msg:
    .ascii "hello, machine\n"
msg_len = . - msg

    .section .text
_start:
    // write(1, msg, msg_len)
    mov     x0, 1               // file descriptor 1 = standard output
    adrp    x1, msg             // the page that holds msg
    add     x1, x1, :lo12:msg   // plus the offset inside that page
    mov     x2, msg_len         // how many bytes
    mov     x8, 64              // syscall number: write
    svc     #0
    // exit(0)
    mov     x0, 0               // status 0
    mov     x8, 93              // syscall number: exit
    svc     #0

Assemble, link, run:

as -o hello_x86.o hello_x86.s && ld -o hello_x86 hello_x86.o
./hello_x86 ; echo "exit status: $?"

aarch64-linux-gnu-as -o hello_arm.o hello_arm.s
aarch64-linux-gnu-ld -o hello_arm hello_arm.o
qemu-aarch64 ./hello_arm        # or just ./hello_arm on a native ARM64 machine

Real output of both on this guidebook's machine:

hello, machine
exit status: 0
hello, machine

Now let's read the x86-64 program one line at a time, because each line teaches something you will use for the rest of your life.

• mov rax, 1 copies the number 1 into the register rax. The name mov is a lie. Nothing moves. The value is copied, and the source stays.
• lea rsi, [rip+msg] computes an address instead of loading from one. lea means "load effective address." The form [rip+msg] means "the address of msg, measured from where this instruction itself lives." Read it as rsi = &msg.
• mov rdx, msg_len copies the length. The assembler computed it for us: . means "the current position," so . - msg is the distance from the start of the string to here, which is the string's length. That is 15, and it matters. (Count hello, machine plus the newline: 14 characters and one newline make 15.)
• syscall hands control to the kernel. The kernel uses your registers as its arguments. You decide what you want, not how the bytes get written.
• xor edi, edi makes edi zero. This is the standard way to write zero on x86-64. It is 2 bytes. We will see why edi and not rdi in Chapter 6.

Now the real bytes. Here is what objdump -d -M intel shows for the program we just built:

401000:  48 c7 c0 01 00 00 00   mov    rax,0x1
401007:  48 c7 c7 01 00 00 00   mov    rdi,0x1
40100e:  48 8d 35 eb 0f 00 00   lea    rsi,[rip+0xfeb]    # 402000 <msg>
401015:  48 c7 c2 0f 00 00 00   mov    rdx,0xf
40101c:  0f 05                  syscall
40101e:  48 c7 c0 3c 00 00 00   mov    rax,0x3c
401025:  31 ff                  xor    edi,edi
401027:  0f 05                  syscall

Three things to see here. The mov rdx, 0xf shows the assembler computed the length as 15 (0xf). The lea is a 7-byte instruction. And check the address math: the instruction after the lea is at 0x401015. Add 0xfeb, and you get 0x402000, which is msg. A rip-relative distance is always measured from the end of the instruction. Also notice that mov rax, 1 took 7 bytes. Chapter 6 shows why that is wasteful.

On ARM64 the same exercise gives (real output):

400078:  d2800020   mov   x0, #0x1
40007c:  90000001   adrp  x1, 400000
400080:  91027021   add   x1, x1, #0x9c
400084:  d28001e2   mov   x2, #0xf
400088:  d2800808   mov   x8, #0x40
40008c:  d4000001   svc   #0x0
400090:  d2800000   mov   x0, #0x0
400094:  d2800ba8   mov   x8, #0x5d
400098:  d4000001   svc   #0x0

Every instruction is exactly 4 bytes. The adrp and add pair builds the address of msg in two steps, because one 4-byte instruction cannot hold a full address. Chapter 7 explains.

Break it on purpose

Now the most valuable part. Change one thing at a time, and watch what happens. These are real results from this machine.

(Shells report a death by signal as 128 plus the signal number: 128+11 is 139, and 128+4 is 132.)

The lesson from the first row is the big one. The kernel trusts your register contract completely. There is no type check. If the number in rax is wrong, you get a different service, not an error message. That is the world you now program in. (I deliberately did not suggest changing 60 to 93 on x86-64. Syscall 93 there is fchown, which changes the owner of a file descriptor, and that is not something to run casually.)

Let's use two more tools to see what the machine did. First strace, which prints every syscall a program makes:

$ strace ./helloC
execve("./helloC", ["./helloC"], ...) = 0
write(1, "hello, machine\n", 15hello, machine
)        = 15
getpid()                                = 1311
+++ killed by SIGSEGV +++

Then gdb, which shows the machine state at any moment:

$ gdb -q -batch -ex 'break _start' -ex run -ex 'info registers rip rsp' \
      -ex 'x/4i $pc' -ex stepi -ex stepi -ex 'info registers rax rdi' \
      -ex 'x/s &msg' ./hello_x86
Breakpoint 1, 0x0000000000401000 in _start ()
rip            0x401000            0x401000 <_start>
rsp            0x7fffffffea40      0x7fffffffea40
=> 0x401000 <_start>:   mov    $0x1,%rax
   0x401007 <_start+7>: mov    $0x1,%rdi
   0x40100e <_start+14>: lea    0xfeb(%rip),%rsi        # 0x402000
   0x401015 <_start+21>: mov    $0xf,%rdx
rax            0x1                 1
rdi            0x1                 1
0x402000:       "hello, machine\n"

Notice gdb prints AT&T syntax by default (mov $0x1,%rax). To flip it, run set disassembly-flavor intel once, or put it in ~/.gdbinit. That is Chapter 3's warning, alive.

The trap

Here is a bug nearly everyone writes once. We want to print hi three times, so we keep the count in rcx:

    mov     rcx, 3              # counter
again:
    mov     eax, 1              # write
    mov     edi, 1
    lea     rsi, [rip+msg]
    mov     edx, 3
    syscall                     # <-- this destroys rcx
    dec     rcx
    jnz     again

How many lines should it print? Three. What did it print? In one second, 2,467,086 lines. Why? Because the syscall instruction wrote the return address into rcx. After the call, rcx held a huge address. We subtracted 1 and it was still not zero, so we looped again, billions of times. The fix is to keep the counter in a register the kernel does not touch, like r12. With that one change it printed hi exactly three times. And the ARM64 version, with the counter in x19, also printed exactly three times. On ARM64, only x0 is destroyed, so this trap is rarer there.

(That is the "first instinct, then it breaks" path. The first instinct is "any register will do." It will not, and the table above tells you which are safe.)

What the loader did before _start

The program we built is an ELF file (Linux's executable format). Before your first instruction ran, the kernel did this:

1. It read the ELF headers and created a private address space for the process.
2. It mapped .text as readable and executable, and .rodata as read-only.
3. It built a stack, and put argc, the argv strings and the environment on it.
4. It pointed the stack register (rsp or sp) at the top of that stack. On x86-64 it is 16-byte aligned: gdb above shows 0x7fffffffea40, which ends in 0.
5. It set the program counter to _start.

That is the entire ceremony. Everything after that is your program. Chapter 23 reads the argc and argv that the kernel left on the stack.

Why it is this way (the "why")

Why can't your code just call the kernel like any function? Because the kernel runs with more privilege than you. The CPU has modes. Your code runs in a restricted one, and the kernel runs in a trusted one. An ordinary call would let you jump into the middle of kernel code at any address. The syscall instruction is a controlled door: the CPU switches modes and jumps to exactly one address the kernel chose. You can ask. You cannot wander.

Why does the kernel trust the register contract? Because there is nothing else to trust. At this level there are no types and no function signatures, just registers. The "standard library" of the machine is the list of syscall numbers and their register rules. That list is an ABI (application binary interface): a contract about bytes and registers, not about source code. Chapter 14 builds on this idea for ordinary function calls.

Common mistakes

• Forgetting .global _start. The linker then complains it cannot find the entry point (or warns and guesses).
• Forgetting to exit. The CPU keeps going past your last instruction into whatever bytes come next. That is the SIGSEGV above.
• A wrong length. Too short cuts your message. Too long prints garbage after it. Let the assembler count with . - msg.
• Trusting rcx and r11 across a syscall on x86-64. They are destroyed.
• Writing to .rodata. It is read-only, so you get SIGSEGV.

Say it simply

To talk to the outside world, a program asks the kernel by running one special instruction after putting a service number and arguments in agreed registers. Two services, write and exit, are enough for a first program. The kernel believes your registers completely, so a wrong number runs a different service and no one stops you. The tools to see all of this are as, ld, objdump, strace and gdb.

Check yourself

Exercise 4.1 (Warm-up): Predict, then check. Write exit(300) and predict the status the shell reports. Check with echo $?. A correct result: 44. Say why in one sentence.

Exercise 4.2 (Warm-up): Explain. In five sentences, explain to a friend why your program cannot write to the screen directly, and what a system call is. Use one analogy and say where it breaks. What a strong answer includes: privilege levels; the kernel owns hardware; a syscall is a controlled door with one fixed entry point; an analogy such as a bank teller window (you cannot walk into the vault, you ask at the window); the limit of the analogy (a teller can refuse and check your ID, while the CPU door trusts the registers you give).

Exercise 4.3 (Core): Break it and fix it. Build the rcx loop above. Run it with timeout 1 ./prog | wc -l. Explain the number you see. Fix it two different ways (one with a different register, one by saving and restoring rcx around the syscall). Check that you now get exactly 3 lines. Hint: look at the table of destroyed registers.

Exercise 4.4 (Core): Implement. Write a program for both ISAs that reads one byte from standard input (read: number 0 on x86-64, 63 on ARM64) into a buffer in .bss, then writes that byte back out. Test with echo Xyz | ./prog. Done when: it prints X, and you can say what the read syscall returned in rax or x0.

Exercise 4.5 (Core): Use the tools. Run strace ./hello_x86 and strace -c ./hello_x86. Then run strace on /bin/true. Count the syscalls in each. What does the difference tell you about what a normal program does before main? A correct result: your handwritten program makes two syscalls (plus execve); a normal dynamically linked program makes dozens before it reaches main (loading libraries and setting up memory).

Exercise 4.6 (Stretch): Design and defend. The kernel does validate some things (a bad pointer gives an error, not a crash of the kernel). Describe what kinds of checking an OS interface could add (types, argument counts, ownership), and what each one would cost per call. What a strong answer includes: the interface runs on every call, so cost matters; checks that are free (is this pointer in the process's memory?) versus costly (verifying types, which registers cannot carry); and a view on where the checking should live (in the library on top, not in the door).

Chapter 5. Reading assembly: the vocabulary and the method

In this chapter: You will learn the small vocabulary that covers almost everything you will read, using real data. You will learn a method for reading any function. And you will read your first piece of compiler output on both machines.

You need first: Chapter 4.

The problem first

You open a disassembly of a function. It is two hundred lines. You read for twenty minutes and understand nothing. Why?

Because you are trying to read it like prose, from the top, one word at a time. Experienced readers do not. They look for landmarks first (calls, loops, decisions), then fill in the detail. And they know the small vocabulary that almost everything is made from.

The model (the "what")

How big is that vocabulary really? An instruction set has thousands of instructions. But they are not used equally. I counted every instruction in the C library (libc.so.6) on this machine, for both ISAs. These are static counts: the instructions that exist in the file, not the ones executed.

The top 10 mnemonics are 69% of all x86-64 instructions and 77% of ARM64. The top 20 are 86% and 92%. The top 40 are 93.5% and 98%. So an older claim in this guidebook, that "about twenty instructions are the overwhelming majority," holds up. And another old claim, that mov is "30 to 50%" of all code, was too high: it is 29.6% on x86-64 and 18.2% on ARM64 here.

Some of this table needs a word. nop is 4% because compilers insert do-nothing instructions as padding, to line up the start of functions and loops on nice addresses. endbr64, which is another 1% of x86-64, is a marker that real Linux builds put at the start of functions (Chapter 17). On ARM64, ldp and stp (load and store a pair) are the standard way to save and restore two registers at once. You will meet them in Chapter 8.

The method. Here is how experienced readers approach a function. Ask these seven questions, in this order. Do not read line by line yet.

1. Where does it start and end? A function ends at ret. There may be more than one ret.
2. What are its inputs? Look at which argument registers it reads before writing them (rdi, rsi, rdx, rcx on x86-64; x0 to x7 on ARM64). We prove this in Chapter 14.
3. Where are the loops? A backward jump (a jump to an address before the jump) is a loop.
4. Where are the decisions? A cmp or test followed by a conditional jump is an if.
5. Where does it call other code? Look for call and bl.
6. What memory does it touch, and how wide? Brackets mean memory. The width tells you the type: 8 bytes is a long or a pointer, 4 bytes an int, 1 byte a char.
7. What does it return? Look at what is in rax (or x0) right before ret.

Only after those seven, read the lines.

Build it (the "how")

Let's apply the method to a real function. Here is the C:

long sum(const long *a, long n) {
    long s = 0;
    for (long i = 0; i < n; i++) s += a[i];
    return s;
}

Here is the real gcc 13.3 -O2 output (with vectorization turned off, so it stays small):

# x86-64
sum:
    test    rsi, rsi            # is n == 0 or negative?
    jle     .L4                 #   yes: skip to the "return 0" path
    lea     rdx, [rdi+rsi*8]    # rdx = a + n*8 : the END of the array
    xor     eax, eax            # s = 0
.L3:
    add     rax, QWORD PTR [rdi]   # s += *p      (memory operand, 8 bytes)
    add     rdi, 8                 # p++          (advance 8 bytes)
    cmp     rdi, rdx               # p == end ?
    jne     .L3                    #   no: loop (backward jump)
    ret
.L4:
    xor     eax, eax            # return 0
    ret

// ARM64
sum:
    cmp     x1, 0               // n <= 0 ?
    ble     .L4                 //   yes: return 0
    mov     x2, x0              // p = a
    mov     x0, 0               // s = 0 (x0 is also the return register)
    add     x3, x2, x1, lsl 3   // end = a + n*8
.L3:
    ldr     x1, [x2], 8         // x1 = *p, then p += 8   (post-index: load AND advance)
    add     x0, x0, x1          // s += x1
    cmp     x2, x3              // p == end ?
    bne     .L3                 //   no: loop
    ret
.L4:
    mov     x0, 0
    ret

Let's apply the seven questions to the x86-64 one.

1. Start and end: sum: to the two rets.
2. Inputs: rdi and rsi are read before being written. So the function takes two arguments (a pointer and a count).
3. Loops: jne .L3 jumps back to .L3. One loop.
4. Decisions: test rsi, rsi; jle is a guard for n <= 0. cmp rdi, rdx; jne is the loop test.
5. Calls: none. This is a leaf function (it calls nothing).
6. Memory: one QWORD PTR [rdi] read, 8 bytes at a time. So it reads longs.
7. Return: rax holds s.

Now look at what the compiler did. The C says "a[i] with a counter i." The assembly has no i. It has a pointer that walks forward by 8 each time, and a precomputed end pointer. The loop stops when the pointer reaches the end. The compiler rewrote your loop. You will often see this. The disassembly is a translation of your idea, not a copy of it.

Also compare the two machines. The x86-64 loop adds directly from memory (add rax, [rdi]). ARM64 must load first (ldr), and its post-indexed ldr x1, [x2], 8 loads and advances the pointer in one instruction, doing the job of x86-64's separate add rdi, 8. The loop body is four instructions on each machine. Same shape, different spelling.

Let's see why -O2 matters. Here is the same function at -O0 (no optimization). The inner loop is 10 instructions instead of 4, and almost every one touches memory, because every variable lives on the stack:

# x86-64, gcc -O0 (the loop part)
.L3:
    mov     rax, QWORD PTR -8[rbp]      # load i
    lea     rdx, 0[0+rax*8]
    mov     rax, QWORD PTR -24[rbp]     # load a
    add     rax, rdx
    mov     rax, QWORD PTR [rax]
    add     QWORD PTR -16[rbp], rax     # s += ... (read, add, write memory)
    add     QWORD PTR -8[rbp], 1        # i++      (read, add, write memory)
.L2:
    mov     rax, QWORD PTR -8[rbp]
    cmp     rax, QWORD PTR -32[rbp]
    jl      .L3

Read -O0 once, to see the naive translation of each C construct. Then never study it again. Real programs, and real profiles, are -O2 or -O3.

Your habit for life: open Compiler Explorer (godbolt.org) in a tab and leave it open. Paste a function, pick the compiler and flags (-O2, and --target=aarch64-linux-gnu for ARM64), and read. Then predict what changes if you edit the C. This one loop, predict then look, is how the vocabulary becomes intuition.

Why it is this way (the "why")

Why is the vocabulary so small? Because of how programs are shaped. Most code moves data (mov, ldr, str), makes decisions (cmp, test, jumps), and calls other code (call, bl, ret). Arithmetic is a small part. This is a fact about software, not about CPUs. It also tells you where the machine's design effort should go: making moves and branches fast. And it is true on both machines, even though they look different.

Why did the compiler turn the index loop into a pointer loop? Two reasons. A pointer that advances by 8 needs one instruction (add rdi, 8); an index needs a multiply-by-8 (folded into the address) and a separate counter. And the compare can be against the end pointer, so the loop needs only one live variable, not two. Fewer instructions per trip, and fewer registers busy. The compiler calls this strength reduction: replacing something costly with something cheaper that gives the same result.

What would have to be true for this to be a bad idea? If you needed the index i itself (to print it, or to index a second array), the compiler would keep it. And if the loop is vectorized (Chapter 29), the shape changes again. So "the compiler rewrote my loop" is normal, and what it rewrote it into depends on what you wrote.

Common mistakes

• Reading -O0 output and thinking it is what ships. It is not.
• Reading line by line from the top. Landmarks first.
• Ignoring widths. DWORD PTR versus QWORD PTR is the difference between int and long.
• Forgetting the output is a translation. The loop you see may not be the loop you wrote.
• Mixing up AT&T and Intel. If operands look backwards, check the flavor.

Say it simply

Most instructions in real code are moves, compares, jumps and calls. About twenty different instructions cover nine tenths of what you will read. To read a function, look for landmarks first: where it starts and ends, its loops (backward jumps), its decisions (compare then jump), its calls, and its memory accesses. The compiler rewrites your loops, so you are reading a translation of your idea.

Check yourself

Exercise 5.1 (Warm-up): Read it. Here is real gcc -O1 output for a function. Before looking at the C, say what it does and what its argument is.

# x86-64
count_a:
    movzx   eax, BYTE PTR [rdi]
    test    al, al
    je      .L4
    mov     edx, 0
.L3:
    cmp     al, 97
    sete    al
    movzx   eax, al
    add     rdx, rax
    add     rdi, 1
    movzx   eax, BYTE PTR [rdi]
    test    al, al
    jne     .L3
.L1:
    mov     rax, rdx
    ret
.L4:
    mov     edx, 0
    jmp     .L1

// ARM64
count_a:
    mov     x2, x0
    ldrb    w1, [x0]
    cbz     w1, .L4
    mov     x0, 0
.L3:
    cmp     w1, 97
    cinc    x0, x0, eq
    ldrb    w1, [x2, 1]!
    cbnz    w1, .L3
.L1:
    ret
.L4:
    mov     x0, 0
    b       .L1

Hint: 97 is the code for a letter. A byte read that stops at zero is a C string. A correct result: it counts how many times the letter a appears in a C string. Your answer should mention the stop-at-zero test, the width (1 byte), and what sete (x86-64) and cinc (ARM64) each do.

Exercise 5.2 (Warm-up): Explain. In five sentences, explain to a friend the seven-question method, using the sum function. What a strong answer includes: landmarks before lines; a backward jump means a loop; compare then jump means a decision; brackets mean memory and the width gives the type; the compiler rewrote the index loop into a pointer loop.

Exercise 5.3 (Core): Measure your own binary. Count the instructions in any program on your machine:

objdump -d --no-show-raw-insn -M intel /usr/bin/ls \
  | awk -F'\t' 'NF>=2 {split($2,a," "); print a[1]}' \
  | sort | uniq -c | sort -rn | head -15

Write down the top five and compare them to the table above. Explain every difference you see. A correct result: mov first, then a mix of cmp, jmp, call, je, lea. Differences come from the binary being small, from stub code, or from different compilers.

Exercise 5.4 (Core): Compare optimization levels. Compile sum with -O0, -O1, -O2 and -O3 (add -fno-tree-vectorize for one run and leave it off for another). For each, count the instructions and count how many of them touch memory in the loop body. Predict the numbers first. A correct result: -O0 has about 20 instructions in total and 10 in the loop, with many memory touches; -O2 has 13 in total and 4 in the loop, with one. Without -fno-tree-vectorize at -O3, you will see vector registers (Chapter 29).

Exercise 5.5 (Core): Predict, then check. Predict how gcc -O2 compiles int sum32(const int *a, long n) (4-byte elements). What changes from sum: the scale, the register names, the width of the load? Check. A correct result: the end pointer uses scale 4 (or a shift by 2), the add uses a 32-bit register (eax or w0), and on x86-64 the memory operand is DWORD PTR.

Exercise 5.6 (Stretch): Design and defend. The compiler rewrote an index loop into a pointer loop. Name two reasons that is better. Then give one situation where the index form would be better to keep, and say what the compiler does about it. What a strong answer includes: fewer instructions per iteration; fewer live registers; when you need the index (second array, printing), or for vectorization the compiler may keep an index and compute addresses from it.

Part 1 wrap-up

What you can now do:

• Say what a CPU does in one loop, and name its four kinds of state.
• Assemble, link, run, trace and debug a program on x86-64 and ARM64.
• Make a Linux system call on both machines, and name which registers it destroys.
• Read Intel and AT&T syntax without confusion.
• Read a small compiled function with the seven-question method.
• Say why a measured number beats a belief (the instruction length and frequency data).

Mini project: the machine in your hands. Time: 2 to 4 hours.

Write one program, on both ISAs, that does all of this:

1. Puts the number 5 in a register, turns it into the character '5' (add 48), stores that byte in memory, and prints it with write. (Hint: you need an address for write. A byte on the stack, or in .bss, will do.)
2. Crashes on purpose, twice: once with ud2 (x86-64) or udf #0 (ARM64), and once by jumping to an address in .data.
3. For each crash, captures the state in gdb and writes down the exact value of the program counter and the register that held the bad address.

Done when: someone else can build and run it from your README alone. The README shows the objdump -d output with each line explained in your own words, and the two crash captures.

Write-up (half a page): What did you expect to see? What did you see? What surprised you?

Reading list for Part 1:

• Linux syscall(2) man page (man 2 syscall). Lists the exact register conventions for every architecture. Start here to check Chapter 4's table.
• Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1 (free PDF). The basic execution environment chapter is the official picture of Chapter 2's registers and flags.
• Arm Architecture Reference Manual for A-profile (free with registration). The programmer's model: the official ARM64 register list.
• Computer Systems: A Programmer's Perspective (Bryant and O'Hallaron). The machine-level chapters are the classic companion for x86-64.
• Matt Godbolt, "What Has My Compiler Done for Me Lately? Unbolting the Compiler's Lid" (CppCon 2017). The best 60-minute introduction to reading compiler output. Watch it after Chapter 5.

Teach it back. In five sentences, as if to a friend who has never seen assembly, explain what a CPU does, how a program asks the OS for help, and how to start reading a function. Use the toy CPU as your example.

Part 2: Memory and Data Movement

After this Part you can move data around on both machines, build any address you need, use the stack, and lay out structs by hand. These are the things most instructions in real code do (remember: mov, ldr and str were the top of our frequency table).

Chapter 6. Moving data: memory, mov, widths and constants

In this chapter: You will learn what memory looks like to the CPU, how bytes are ordered, and how mov works on both machines. You will learn the width rules that cause silent bugs. And you will learn how each machine builds a big constant.

You need first: Chapters 2 and 4.

The problem first

You have a value in a register. You want it in memory. Or the other way round. Easy, until the questions start. How many bytes? Which end goes first? What happens to the other bits of the register? And what if the number you want to load is too big to fit inside the instruction?

Each of these has an answer, and each answer is a trap if you guess.

The model (the "what")

Memory is one long array of bytes. Address 0 is the first byte, address 1 the second, and so on. A pointer is just a number that is an index into that array. A data structure is only an agreement about what the numbers at which offsets mean.

(Your process does not own all of that array. The operating system gives each process a private view, and if you touch an address you were not given, the CPU raises an exception and your process dies with a segfault. Memory safety, at the instruction level, is one sentence long.)

Byte order. Say you store the 8-byte number 0x0102030405060708 at some address. In what order do the bytes land? Both of our machines are little-endian: the low byte goes at the lowest address. Here is a real run. This program writes those 8 bytes to the terminal, and xxd shows them:

$ ./endian | xxd
00000000: 0807 0605 0403 0201

The bytes look backwards. That is little-endian. You will see this every time you read a hex dump. (ARM64 hardware can do big-endian too, but Linux always runs it little-endian, so treat the two machines as the same here.)

Alignment. An address is aligned for a size if it is a multiple of that size. Address 16 is aligned for 8 bytes; address 17 is not. A common claim is that ARM64 faults on misaligned access, so let me be careful.

• On x86-64, misaligned ordinary loads and stores work.
• On ARM64, misaligned ordinary loads and stores also work on normal memory. I tested this: an 8-byte ldr at an odd address ran fine under qemu-user and returned the right bytes.
• What is not allowed on ARM64: atomic and acquire/release instructions (ldxr, ldar, and friends) need natural alignment. The manual says they fault otherwise. (Under qemu-user I could not make this fault happen, so check it on real hardware before you rely on it.)

So alignment is not a correctness rule for plain loads on either machine. It is a speed rule, and I measured it. A loop of 8-byte loads on this machine took about 0.64 ns each when the load sat inside one 64-byte cache line, and about 0.93 ns each when it crossed a line boundary, which is about 1.5 times slower. (In an earlier session, on what was evidently different hardware, I measured 0.43 ns against 0.82 ns, nearly double. Part 8 explains why my numbers moved.) Crossing a cache line costs more because the CPU must touch two lines.

The mov family. Both machines have three kinds of operand: an immediate (a constant inside the instruction), a register, and memory. On x86-64, mov handles all combinations except memory-to-memory. On ARM64, mov is registers and immediates only. Memory has its own instructions: ldr (load register) and str (store register).

# x86-64: the mov matrix (Intel syntax; the size word needs "ptr")
    mov     rax, 42                 # immediate -> register
    mov     rax, rbx                # register  -> register
    mov     rax, [rbx]              # memory    -> register   (a load, 8 bytes)
    mov     [rbx], rax              # register  -> memory     (a store)
    mov     byte ptr [rbx], 65      # immediate -> memory, 1 byte (we MUST say the size)
    mov     qword ptr [rbx], 7      # immediate -> memory, 8 bytes

// ARM64: the same matrix, with ldr and str for memory
    mov     x0, #42                 // immediate -> register
    mov     x1, x0                  // register  -> register
    ldr     x0, [x1]                // memory    -> register   (a load, 8 bytes)
    str     x0, [x1]                // register  -> memory     (a store)
    mov     w2, #65
    strb    w2, [x1]                // store 1 byte. The suffix picks the width:
                                    //   strb = 1, strh = 2, str w = 4, str x = 8

Width. x86-64 puts the width in the register name: al is 1 byte, ax is 2, eax is 4, rax is 8. ARM64 uses w0 for the low 32 bits of x0, and puts the width of memory accesses in the instruction (ldrb, ldrh, ldr).

Now the two rules that bite everyone once.

Rule 1: writing a 32-bit register zeroes the upper half. Writing 8 or 16 bits does not. Here is a real run. We set every bit of a register, then write a smaller piece:

    mov     rax, -1             # rax = 0xffffffffffffffff
    mov     eax, 5              # write the 32-bit half
    mov     rbx, -1
    mov     bl, 5               # write the 8-bit part
    mov     rcx, -1
    mov     cx, 5               # write the 16-bit part

rax   0x5
rbx   0xffffffffffffff05
rcx   0xffffffffffff0005

Writing eax wiped the top 32 bits of rax. Writing bl and cx left the upper bits alone. ARM64 does the same for its 32-bit w registers: writing w0 zeroes the top of x0.

Rule 2: narrow loads must say how to fill the rest. If you load a byte into a 64-bit register, what goes in the other 56 bits? Zeros (right for unsigned) or copies of the sign bit (right for signed). The machines spell this differently. Real encodings:

x86-64                                       ARM64
movzx  eax, byte ptr [rdi]  (0f b6 07)       ldrb   w0, [x1]   (zero-extend byte)
movsx  rax, byte ptr [rdi]  (48 0f be 07)    ldrsb  x0, [x1]   (sign-extend byte)
movsxd rax, dword ptr [rdi] (48 63 07)       ldrsw  x0, [x1]   (sign-extend 32 -> 64)

The sign-extending forms matter whenever a signed int is used as a 64-bit index. You will see movsxd and ldrsw in output whenever C code indexes an array with an int.

Big constants. An instruction has only so many bits, so it can hold only so big a constant.

On x86-64, mov eax, 5 is the 5-byte instruction b8 05 00 00 00. The constant is a 32-bit field. But watch what the assembler did for mov rax, 5:

b8 05 00 00 00           mov    eax,0x5          5 bytes
48 c7 c0 05 00 00 00     mov    rax,0x5          7 bytes
48 b8 f0 de bc 9a 78 56 34 12   movabs rax,0x123456789abcdef0   10 bytes
31 c0                    xor    eax,eax          2 bytes
48 31 c0                 xor    rax,rax          3 bytes

Look at how many bytes the same idea costs. mov eax, 5 is shorter than mov rax, 5, and because of Rule 1 it does the same job (the top half becomes zero). So compilers write mov eax, 5 whenever the value fits. And that is why xor edi, edi appears in our hello program: it is 2 bytes, while xor rdi, rdi is 3. Both forms clear the upper bits, so it is not about correctness: xor reg, reg wins because it is shorter, and because the CPU recognizes it as a zeroing idiom that does not wait on the old value of the register. Only movabs can carry a full 64-bit constant, and it is 10 bytes.

ARM64 cannot hold a 64-bit constant in 4 bytes, so it builds one in pieces of 16 bits:

    movz    x0, #0x1234, lsl #48    // set one 16-bit slice, zero the rest
    movk    x0, #0x5678, lsl #32    // "move, keep": overwrite one slice, keep the rest
    movk    x0, #0x9abc, lsl #16
    movk    x0, #0xdef0
    // x0 = 0x123456789abcdef0, in four instructions

When you read four movk-style instructions in a row in a disassembly, you are watching a constant being built, slice by slice. A compiler may also put the constant in a small table next to the code (a literal pool) and load it with one ldr. And ARM64 has one more trick for logic instructions: certain repeating bit patterns, like 0xff or 0x00ff00ff00ff00ff, fit directly inside and, orr and eor. A random constant like 0xf0f0f0f1 does not, and the assembler tells you so:

Error: immediate out of range at operand 3 -- `and x2,x3,#0xf0f0f0f1'

That is the message every ARM64 beginner meets. Chapter 25 shows exactly why.

Build it (the "how")

Let's put together the data-movement pieces in a small program. It stores a quad word, reads it back one byte at a time, and shows how the pieces differ.

# x86-64: store, then read back with different widths
    .intel_syntax noprefix
    .global _start
    .bss
buf:    .space 8
    .text
_start:
    lea     rbx, [rip+buf]
    mov     rax, 0x1122334455667788
    mov     [rbx], rax                  # store all 8 bytes
    movzx   ecx, byte ptr [rbx]         # the lowest-address byte: 0x88
    movzx   edx, byte ptr [rbx+7]       # the highest-address byte: 0x11
    mov     edi, ecx                    # exit status = low byte read
    mov     eax, 60
    syscall

Predict the exit status before you run it. Little-endian says the byte at the lowest address is the low byte of the number, 0x88, which is 136. When I ran it, the status was 136.

Here is the first instinct that breaks. Most people, seeing 0x1122334455667788, expect the first byte in memory to be 0x11. That is how we write numbers on paper, and big-endian machines do store it that way. On our machines it is the other way around. The only reliable habit is: whenever you look at memory bytes, ask "which direction is low?"

Why it is this way (the "why")

Why does a 32-bit write zero the top half? The old 32-bit x86 code used eax, and when AMD extended it to 64 bits, they made 32-bit writes zero the top. The reason is speed. If a write to eax kept the old top half of rax, the CPU would have to wait for the old value of rax before finishing, even though you never use it. Zeroing breaks that false wait. For 8-bit and 16-bit writes, the old behavior was already fixed in history, so they merge. This is a design choice, and it is also why 8-bit and 16-bit operations are sometimes slower than 32-bit ones.

Why is the constant so small? Because the immediate is stored inside the instruction, and an instruction is short. A 64-bit constant would make every instruction longer, and almost every constant a program uses is small (0, 1, -1, 8, a mask). So both machines make the common case cheap and the rare case a multi-step process.

The trade-off. x86-64 spends bytes on flexibility (a memory operand, a long constant when you need one). ARM64 spends instructions on regularity (load, then compute; build constants in slices). Neither is faster by itself. Which one wins depends on what the code does, and a later chapter shows that the CPU can hide much of the difference.

What would make this design wrong? If most programs used big constants and wide values, the cost of movabs and movk ladders would dominate. The reason that is not the case is a fact about software, and it is the same fact we met in Chapter 5: code mostly moves data and compares small things.

Common mistakes

• Using mov rax, 5 instead of mov eax, 5. It works, but costs 2 more bytes.
• Forgetting the size word. mov [rbx], 7 is ambiguous. Say qword ptr or dword ptr.
• Assuming a byte write clears the register. It does not. Use movzx.
• Reading a hex dump left to right as a number. It is little-endian. The first byte is the lowest.
• Using a signed load for unsigned data. 0xff loaded with ldrsb is -1, not 255.

Say it simply

Memory is one long array of bytes, and on both our machines the low byte of a number goes at the lowest address. A 32-bit register write clears the top half of the 64-bit register, but an 8-bit or 16-bit write does not. Narrow loads must say whether to fill with zeros or sign bits. Constants live inside instructions, so big ones take extra steps: one long instruction on x86-64, and a ladder of 16-bit pieces on ARM64.

Check yourself

Exercise 6.1 (Warm-up): Predict, then check. Store 0x0102030405060708 in memory and read it back with movzx from offsets 0, 1 and 7. Predict the three bytes. Then run it and print each as an exit status. A correct result: 0x08, 0x07, 0x01.

Exercise 6.2 (Warm-up): Explain. In five sentences, explain to a friend why a uint32_t write in C is "free" on x86-64 while a uint8_t write can cost extra. Give an analogy and say where it breaks. What a strong answer includes: a 32-bit write replaces the whole register so there is no dependence on the old value; an 8-bit write keeps the other bits so it must wait for the old value; analogy: replacing a whole page of a notebook versus editing one word on it (you must read the page first); where it breaks: the CPU renames registers to hide some of this.

Exercise 6.3 (Core): Break it and fix it. Assemble mov [rbx], 7 and read the error. Then fix it three ways (byte, dword, qword) and compare the encoded lengths with objdump. A correct result: the error says ambiguous operand size; the three fixes differ in opcode and in how many immediate bytes follow.

Exercise 6.4 (Core): Implement. On both ISAs, write a function-free program that loads the value 0xdeadbeefcafef00d into a register, then stores it to .bss and reads back its second byte using both a zero-extending and a sign-extending load. Exit with each result in turn and compare. Done when: the zero-extended result is 0xf0 (240) and the sign-extended low byte of the exit code shows the same bits, and you can explain why the printed number changes only if you look at the full register. Hint: look at what movsx puts in the upper 56 bits, and check with gdb.

Exercise 6.5 (Core): Change one thing. Run the cache-line benchmark idea yourself: write a C loop that does 8-byte loads at offset 0, then at offset 61 inside each 64-byte line (use memcpy into a local to avoid a C alignment problem). Measure both. A correct result: the crossing case is noticeably slower, around 1.5 to 2 times on common x86-64 chips. Your ratio may differ. Explain it in terms of cache lines.

Exercise 6.6 (Stretch): Design and defend. Suppose you could add one new addressing or constant feature to ARM64 to avoid movk ladders without making instructions longer. Propose one, and state what it would cost in decode complexity or in space. What a strong answer includes: a clear mechanism (for example a literal pool with a PC-relative load, which ARM64 already has); an honest cost (a memory access, cache pressure, or a wider encoding); and a statement of which constants are common enough to matter.

Chapter 7. Addressing modes: how an address is built

In this chapter: You will learn the ways each machine builds a memory address, and the instruction lea, which builds an address without touching memory. You will learn how both machines reach a variable in your program's data.

You need first: Chapter 6.

The problem first

Say you have an array of 8-byte numbers and you want element i. The address is start + i*8. You could compute that in three instructions (multiply, add, load). But array indexing happens so often that both machines build the arithmetic into the load itself. That is what an addressing mode is: a recipe for building an address inside one instruction.

The model (the "what")

x86-64 has one general recipe. The address is:

base + index * scale + displacement

All parts are optional. The base and index are registers, the scale is 1, 2, 4 or 8, and the displacement is a constant number of bytes. Here are real encodings of some forms (checked with the GNU assembler):

mov rax, [rbx]               48 8b 03
mov rax, [rsp]               48 8b 04 24            <- notice the extra 24 byte
mov rax, [rbx+16]            48 8b 43 10
mov rax, [rbx+rcx*4]         48 8b 04 8b
mov rax, [rbx+rcx*4+16]      48 8b 44 8b 10
mov rax, [rbx+rcx*3]         ERROR: not a valid base/index expression

The last line is the point. The scale can only be 1, 2, 4 or 8. Those are the sizes of the common types (char, short, int, long or pointer). Anything else, like times 3, needs a separate instruction. (The extra 24 byte in the [rsp] form is a special case we meet in Chapter 24.)

ARM64 has a narrower set. The address is a base register, plus one of:

    ldr     x0, [x1]                    // base only
    ldr     x0, [x1, #16]               // base + constant (a multiple of 8, 0..32760)
    ldr     x0, [x1, x2]                // base + register
    ldr     x0, [x1, x2, lsl #3]        // base + register << 3   (scaled index)
    ldr     x0, [x1, w2, sxtw #3]       // base + (sign-extended 32-bit index) << 3
    ldr     x0, [x1, #16]!              // pre-index:  x1 += 16 first, then load
    ldr     x0, [x1], #16               // post-index: load first, then x1 += 16

The ranges are easy to get backwards, so here are the real rules, checked with the assembler:

• A scaled unsigned constant: 0 to 32,760 for an 8-byte ldr (that is 4095 × 8). It must be a multiple of the access size.
• An unscaled signed constant: -256 to +255, with any alignment. The assembler picks this form (ldur) on its own when you write ldr x0, [x1, #3] or #-256.
• Anything outside those ranges is rejected: ldr x0, [x1, #32768] and ldr x0, [x1, #-257] both give "immediate offset out of range."

The pre-index and post-index modes are the unusual part. They change the base register as part of the load. Post-index [x1], #16 means "use x1, then add 16 to it." This is the machine's array-walking mode: one instruction loads and moves the pointer. You saw it in Chapter 5: ldr x1, [x2], 8.

And sxtw ("sign-extend word") appears constantly in compiled ARM64 code, for the same reason movsxd does on x86-64. A C int index is 32 bits and signed, but an address is 64 bits. [x0, w1, sxtw] in output is a sign that the source indexed with an int.

lea: an address calculator. x86-64's lea ("load effective address") computes the address recipe but does not touch memory. It just hands you the number.

    lea     rax, [rbx+rcx*4+16]     # rax = rbx + rcx*4 + 16   (no memory access)
    lea     rax, [rdi+rdi*2]        # rax = rdi * 3            (just arithmetic)

The second line is the compiler's famous trick, and we saw it in Chapter 1: x * 3 becomes lea rax, [rdi+rdi*2]. Why use an address calculator for arithmetic? Three reasons: it takes three inputs and writes a separate output register (so it does not destroy a source), it combines shift and add in one step, and, critically, lea does not change the flags. I checked the encoding of cmp rax, rbx; lea rcx, [rax+rax*2+5]; je done. A flag set by cmp survives the lea. A compiler uses this to compute something in between a compare and the jump that depends on it. ARM64 does the same job with a shifted operand: add x0, x0, x0, lsl 1.

Reaching a variable in your data. A very common job is getting the address of a global variable or a string. Both machines use the program counter as the base, so the address is a distance from the current instruction. That keeps code position-independent: the whole program can load at a different place, and the distance stays the same.

On x86-64 it is one instruction (we used it already):

    lea     rdi, [rip+msg]          # rdi = address of msg
    mov     rax, [rip+counter]      # load the value stored AT counter

(Note for the GNU assembler: write [rip+msg]. The form [rel msg] is NASM syntax, and the GNU assembler rejects it with "bad expression.")

On ARM64 a 4-byte instruction cannot hold a full distance, so the job takes two steps:

    adrp    x0, msg                 // x0 = the 4 KiB page that holds msg
    add     x0, x0, :lo12:msg       // + the offset of msg inside that page
    ldr     x1, [x0]                // use it

adrp reaches any page within plus or minus 4 GiB of the instruction. The :lo12: names the low 12 bits of the address. Why 12? Because 2 to the power 12 is 4096, a page, and the low 12 bits of an address say where inside the page you are. So adrp finds the page, and add finds the spot. When you see adrp over and over in ARM64 output (it was 3.2% of all instructions in our libc count), you are watching the machine rebuild addresses each time rather than keep them in registers.

Build it (the "how")

Let's write array indexing on both machines. We sum the 4 numbers 10, 20, 30, 40 using the index form of each addressing mode.

# x86-64: sum arr[0..4) with base + index*8
    .intel_syntax noprefix
    .global _start
    .data
arr:    .quad 10, 20, 30, 40
    .text
_start:
    lea     rbx, [rip+arr]          # base
    xor     eax, eax                # sum = 0
    xor     ecx, ecx                # i = 0
again:
    add     rax, [rbx + rcx*8]      # sum += arr[i]   (scale 8 = size of a quad)
    inc     rcx
    cmp     rcx, 4
    jl      again
    mov     rdi, rax                # exit status = sum = 100
    mov     eax, 60
    syscall

// ARM64: the same, with a scaled register index
    .global _start
    .data
arr:    .quad 10, 20, 30, 40
    .text
_start:
    adrp    x1, arr
    add     x1, x1, :lo12:arr       // base
    mov     x0, 0                   // sum
    mov     x2, 0                   // i
again:
    ldr     x3, [x1, x2, lsl #3]    // x3 = arr[i]
    add     x0, x0, x3
    add     x2, x2, 1
    cmp     x2, 4
    b.lt    again
    mov     x8, 93                  // x0 already holds the sum = 100
    svc     #0

Both exit with status 100. The two loops have the same shape, and the interesting line is the load: [rbx + rcx*8] versus [x1, x2, lsl #3]. Each folds the "times 8" into the address.

Why it is this way (the "why")

Why can x86-64 only scale by 1, 2, 4 or 8? The scale is stored in 2 bits of the instruction (Chapter 24). Two bits give four choices, and the four sizes of the basic types are the four useful ones. The address adder in the CPU has a tiny fixed shifter in front of it for exactly this. Multiplying by 3 would need a real multiplier, which is much bigger and slower, so the design leaves it out.

Why does ARM64 split an address into adrp plus add? Because a 4-byte instruction has no room. After you spend 5 bits on the destination register and a few more on the opcode, you have about 21 bits left for a distance. That reaches 4 GiB when counted in 4 KiB pages, which is plenty for one program. Instead of making instructions longer, ARM64 chose two instructions. It is the same bet as before: spend instructions to keep decoding simple.

What would make lea-as-arithmetic a bad idea? It would be a bad idea if lea were slow. On some older chips, a lea with three parts took extra cycles, and compilers must know which. This is a place where the instruction's meaning and its speed are separate questions, and Part 8 teaches you where to look the speed up.

Common mistakes

• Writing [rel msg] or [msg] in GNU Intel syntax. Use [rip+msg].
• Using scale 3, 5, 6 or 10. Not allowed. Use lea or shifts.
• Expecting ldr x0, [x1, #3] to be an error on ARM64. The assembler quietly picks the unscaled form.
• Forgetting that lea does not read memory. lea rax, [rbx] is just mov rax, rbx.
• Using a 32-bit index without sxtw. A negative int index would become a huge positive number.

Say it simply

An addressing mode is a recipe for an address, built inside one instruction. x86-64 offers base plus index times 1, 2, 4 or 8 plus a constant. ARM64 offers base plus a constant, or plus one shifted register, with optional update of the base afterwards. lea computes an address without loading anything, and compilers borrow it for arithmetic because it leaves the flags alone. To reach a global variable, both machines measure from the program counter, ARM64 in two steps (adrp and add).

Check yourself

Exercise 7.1 (Warm-up): Decode by hand. What address does [rbx + rcx*4 + 16] compute when rbx = 0x1000 and rcx = 5? What does ldr x0, [x1, x2, lsl #3] load from when x1 = 0x2000 and x2 = 3? A correct result: 0x1000 + 20 + 16 = 0x1024, and 0x2000 + 24 = 0x2018.

Exercise 7.2 (Warm-up): Explain. In five sentences, explain why a compiler writes x*3 as lea rax, [rdi+rdi*2]. Give an analogy and say where it breaks. What a strong answer includes: lea is an address calculation borrowed for arithmetic; scale 2 plus the base gives times 3; it writes a separate output and does not change flags; analogy: using a tape measure (made for distances) to also add two numbers; it breaks because lea is limited to the shapes the address recipe allows.

Exercise 7.3 (Core): Predict, then check. Predict the bytes of mov rax, [rbx+rcx*8+0x100]. Then assemble and check. Which part tells the CPU the scale? A correct result: it uses a ModRM byte and a SIB byte followed by a 4-byte displacement (since 0x100 does not fit one signed byte). Hint: compare with the 1-byte displacement in [rbx+16].

Exercise 7.4 (Core): Implement. Write both programs above and then change them to sum an array of 4-byte ints (.long) instead of quad words. On ARM64 you will need a 32-bit load; on x86-64 a 32-bit register. Make the status come out right when one element is negative. Done when: an array 10, -20, 30, 40 gives the sum 60, and you can explain whether you needed movsxd/ldrsw.

Exercise 7.5 (Core): Break it. On ARM64, write ldr x0, [x1, #4] and ldr x0, [x1, #32768]. Read what the assembler does with each, then check the first one's encoding with objdump. A correct result: the first assembles as ldur (unscaled form); the second is rejected as out of range. Explain why #4 is not a multiple of 8.

Exercise 7.6 (Stretch): Design and defend. The x86-64 scale is 2 bits. Propose a 3-bit scale field. Which new values would you offer, and what would it cost the hardware and the instruction length? What a strong answer includes: which sizes matter (for example 16 for 16-byte structs), a clear cost in encoding space or a bigger shifter, and the evidence that the sizes are needed (compilers must otherwise emit a shift or lea, as we saw with a 16-byte struct in Chapter 9).

Chapter 8. The stack is just memory with a register in charge

In this chapter: You will learn what the stack really is, how push and pop work on x86-64, and how ARM64 does the same job without them. You will learn why the stack grows downward and why alignment matters.

You need first: Chapters 6 and 7.

The problem first

Your function needs somewhere to keep a value while it calls another function. A register will not do, because the other function might use that register. Memory would do, but where in memory? And how do you find it again, and how do you free it? You want a place that grows when you need it and shrinks when you are done, in strict last-in, first-out order.

That place is the stack.

The model (the "what")

The stack is a region of ordinary memory. A single register, the stack pointer (rsp on x86-64, sp on ARM64), holds the address of the "top." Both machines grow the stack downward: the top moves to a lower address as you add things.

 high addresses
   +-----------------+
   | older data      |
   +-----------------+
   | value A         |   <- pushed first
   +-----------------+
   | value B         |   <- pushed second   <- rsp points here (the top)
   +-----------------+
   | (free space)    |
 low addresses

Look at where rsp points: at the last thing pushed. Pushing moves it down; popping moves it back up.

x86-64 has real instructions for this:

    push    rax            # rsp = rsp - 8;  [rsp] = rax
    pop     rbx            # rbx = [rsp];    rsp = rsp + 8

The real bytes for push qword ptr [rbx+rcx*8] are ff 34 cb. And push rax alone is one byte (50).

ARM64 has no push or pop. It uses the store and load instructions with the pre-index and post-index modes from Chapter 7, and it prefers to move two registers at a time with stp ("store pair") and ldp ("load pair"):

    stp     x0, x1, [sp, #-16]!     // sp -= 16, then store x0 at [sp] and x1 at [sp+8]
    ldp     x0, x1, [sp], #16       // load x0 and x1 from [sp], then sp += 16

Here is a real run. Four numbers 1, 2, 3, 4 loaded into x2 to x5. We push them as two pairs and pop them as two pairs. The real encodings:

a9bf0fe2   stp  x2, x3, [sp, #-16]!
a9bf17e4   stp  x4, x5, [sp, #-16]!
a8c11fe6   ldp  x6, x7, [sp], #16
a8c127e8   ldp  x8, x9, [sp], #16

After this, x6 and x7 hold 3 and 4 (the last pair pushed comes out first), and x8 and x9 hold 1 and 2. That reversal is the whole idea of a stack.

Alignment. Both machines expect the stack pointer to be a multiple of 16 at the right moments. On ARM64 the hardware can check this on every stack access, so a misaligned sp can crash. On x86-64 nothing checks rsp, but the calling convention promises 16-byte alignment, and instructions like movaps do fault on a misaligned address. We saw the kernel hand us an aligned rsp at _start: gdb printed 0x7fffffffea50, which ends in 0. Chapter 15 says exactly where the promise applies.

A stack is memory, not magic. There is no special hardware stack in either machine. push is defined as "subtract from rsp, then store." ARM64 has no push at all and just does the same thing with sp. When a debugger prints a "stack trace," it is walking a chain of saved values that the calling convention placed in known positions. If a bug overwrites that chain, the debugger shows fiction.

Build it (the "how")

Let's reverse an array in place, using the stack as the helper. First x86-64: push all five elements, then pop them back into the array. Pops come out in the opposite order, so the array is reversed.

# x86-64: reverse arr = [1,2,3,4,5] using push and pop
    .intel_syntax noprefix
    .global _start
    .data
arr:    .quad 1, 2, 3, 4, 5
    .text
_start:
    lea     rbx, [rip+arr]
    xor     ecx, ecx
pushing:
    push    qword ptr [rbx + rcx*8]     # push arr[i]  (memory to stack in one instruction)
    inc     rcx
    cmp     rcx, 5
    jl      pushing
    xor     ecx, ecx
popping:
    pop     qword ptr [rbx + rcx*8]     # pop into arr[i]
    inc     rcx
    cmp     rcx, 5
    jl      popping
    mov     rdi, [rbx]                  # arr[0] is now 5
    shl     rdi, 4
    add     rdi, [rbx+32]               # arr[4] is now 1  ->  status = 5*16 + 1
    mov     eax, 60
    syscall

I predicted 5*16 + 1 = 81, ran it, and the status was 81.

Now ARM64, with pairs. This is the program from the encodings above, finished: it pushes (1,2) then (3,4), pops them back, and computes a status from the result.

// ARM64: push and pop pairs
    .global _start
    .data
    .balign 16
arr:    .quad 1, 2, 3, 4
    .text
_start:
    adrp    x10, arr
    add     x10, x10, :lo12:arr
    ldp     x2, x3, [x10]               // x2=1 x3=2
    ldp     x4, x5, [x10, #16]          // x4=3 x5=4
    stp     x2, x3, [sp, #-16]!         // push pair
    stp     x4, x5, [sp, #-16]!         // push second pair
    ldp     x6, x7, [sp], #16           // pop: x6=3 x7=4
    ldp     x8, x9, [sp], #16           // pop: x8=1 x9=2
    lsl     x0, x6, #4                  // status = x6*16 + x9 = 3*16 + 2
    add     x0, x0, x9
    mov     x8, #93
    svc     #0

The status was 50, as predicted.

Why it is this way (the "why")

Why does the stack grow downward? It is an historical choice. Programs used to have code at the bottom of memory, the heap growing up from just above it, and the stack starting at the top and growing down. The two grow toward each other, and the free space between them is shared. On a modern system the layout is more complicated, but the direction stuck. It is not better or worse, only agreed upon, and everything (debuggers, unwinders, the convention) now assumes it.

Why does ARM64 prefer pairs? Because a function almost always saves registers in pairs: the frame pointer and the link register, then two callee-saved registers, and so on. A single pair instruction does the work of two stores and one stack adjustment. It also keeps sp a multiple of 16 for free. This is a design that matches how real code behaves, the same lesson as the frequency table: ldp and stp were 4.6% and 3.8% of all ARM64 instructions in libc.

What is the limit of a stack? Its size. The OS gives each thread a fixed amount (commonly 8 MiB for the main thread on Linux), with an unmapped guard page below it. Recursion that goes too deep walks down into the guard page and the program dies with a segfault. That is a stack overflow, and it is the guard working as designed.

Common mistakes

• Unbalanced push and pop. If you push three times and pop twice, rsp is wrong when you return, and the return address is read from the wrong place.
• Forgetting that the stack grows down. A local at [rsp+8] is above [rsp], so it is something pushed earlier.
• Breaking 16-byte alignment on ARM64. sub sp, sp, #8 followed by a stack access can fault. Move sp in multiples of 16.
• Using stack memory after it is freed. After pop or after adding back to sp, the bytes are still there but are fair game for the next push.

Say it simply

The stack is ordinary memory, managed by one register that points at the top and moves downward as you add things. x86-64 has push and pop. ARM64 has no such instructions and uses store and load with the base-updating addressing modes, usually a pair at a time. Everything stack-related (frames, saved registers, return addresses) is a convention built on that one register.

Check yourself

Exercise 8.1 (Warm-up): Trace by hand. Start with rsp = 0x7000. What are rsp and the memory contents after push 1; push 2; push 3? And after one pop? A correct result: rsp is 0x6fe8 after the three pushes; the value 3 is at 0x6fe8, 2 at 0x6ff0, 1 at 0x6ff8. After the pop, rsp is 0x6ff0 and the popped value is 3.

Exercise 8.2 (Warm-up): Explain. In five sentences, explain to a friend why ARM64 does not need push and pop. Use an analogy and say where it breaks. What a strong answer includes: pre- and post-indexed addressing already do "move the pointer and store"; pairs make it efficient; analogy: a stack of plates where the same tool both adds the plate and shifts the pile; where it breaks: real plates cannot be reached at an offset, while the CPU can read at [sp+8] without popping.

Exercise 8.3 (Core): Break it. In the x86-64 reverse program, remove the last pop from the loop so you pop one fewer value, or change the loop count to 4. Predict the result, run it, and use gdb to look at rsp at exit. A correct result: the array is wrong in its last element, and rsp is not where it began.

Exercise 8.4 (Core): Implement. On both ISAs, write a loop that pushes the numbers 1 to 8, then pops them and adds them up. On ARM64, use stp/ldp pairs and keep sp aligned. Done when: the sum is 36, the stack pointer is back at its starting value at the end, and you printed sp before and after in gdb to prove it.

Exercise 8.5 (Core): Predict, then check. What would happen if you pushed in an endless loop with no pops? Predict how many pushes it takes, using an 8 MiB stack. Then run it and read the signal and the address with gdb. A correct result: it keeps going for a long while (each push is 8 bytes, so you need about a million pushes to use 8 MiB) and then dies with SIGSEGV near the guard page. Say what the faulting address is relative to rsp.

Exercise 8.6 (Stretch): Design and defend. Some designs keep return addresses on a separate stack from data. Give one reason that is a good idea and one cost. What a strong answer includes: a bug that overwrites data cannot reach return addresses, which blocks a class of attacks; the cost is a second register and memory area to manage, and an extra place to switch on every thread and every context switch.

Chapter 9. Data in memory: sections, structs and padding

In this chapter: You will learn how to declare data in an assembly file, how structs become offsets, and how padding changes the size of a struct. You will fix a stride bug that is easy to write.

You need first: Chapters 6 to 8.

The problem first

Assembly has no types and no structs. It has bytes and offsets. If you want a struct point { long x; long y; }, you have to say in your own words that "x is at offset 0 and y is at offset 8," and then write those numbers every time you touch a field. Write them by hand, and the day you add a field, every number is wrong. We want the assembler to count for us, the same lesson as Chapter 1 about labels, one level up.

The model (the "what")

An assembly file is divided into sections. The three you need:

The last row is a clever trick. .bss bytes are not stored in your file at all. The loader allocates them and fills them with zeros when the program starts. I built two programs that each reserve one megabyte, one in .data and one in .bss. The real file sizes:

.data version: 1,057,392 bytes
.bss  version:     4,736 bytes

Both programs use one megabyte of memory when they run. One of them costs a megabyte of disk.

Data directives say how many bytes each item takes:

    .section .data
counter:    .quad  0                    # 8 bytes
table:      .quad  1, 1, 2, 3, 5, 8     # six 8-byte values
tiny:       .byte  0x41                 # 1 byte  ('A')
mix:        .short 1, 2, 3              # three 2-byte values
ratio:      .long  0x3F800000           # 4 bytes (that bit pattern is the float 1.0)
    .section .rodata
digits:     .ascii "0123456789"         # no terminator
greeting:   .asciz "hi\n"               # asciz adds a 0 byte at the end

Two traps live here. First, .word means different sizes on the two machines. I assembled the same file for both. On x86-64, .word is 2 bytes. On ARM64 it is 4. Do not assume .word is 2 bytes. Use .short (2) and .long (4), which mean the same everywhere. Second, .align means different things. On x86-64, .align 4 means "align to a multiple of 4 bytes." On ARM64, .align 4 means "align to 2 to the power 4, which is 16 bytes." I tested both: after a single byte, .align 4 put the next label at offset 4 on x86-64 and at offset 16 on ARM64. To avoid the whole confusion, use .balign 16, which always means 16 bytes.

Structs are offsets. Let the assembler name them:

    .set point.x, 0                     # named offsets, computed by the assembler
    .set point.y, 8
    .set point.size, 16

An array of structs is base + i * size + field_offset. Here is where a real mistake hides, and it is worth looking at slowly.

Build it (the "how")

We have three points, (1,2), (3,4), (5,6), laid out one after another in memory: 1, 2, 3, 4, 5, 6. Each point is 16 bytes. We want the sum of the y fields: 2 + 4 + 6 = 12.

The first instinct: you know the scale is 8 (the size of a long), so write [rcx + rdx*8 + point.y]. Here is why that breaks. Index i must step 16 bytes per point, not 8. With scale 8, index 1 reads the second quad in the array, which is y of point 0 or x of point 1 depending on the field offset. I ran this arithmetic: reading with a stride of 8 returns [3, 4] for indices 1 and 2, but the correct y values for those points are [4, 6]. The code looks right and gives the wrong answer. It is an easy bug to write.

The scale is limited to 1, 2, 4 and 8, and 16 is not allowed. So we have to multiply the index ourselves (a shift by 4 gives times 16), or walk a pointer that advances by 16.

# x86-64: sum of the y fields of 3 points
    .intel_syntax noprefix
    .global _start
    .set point.x, 0
    .set point.y, 8
    .set point.size, 16
    .data
points: .quad 1, 2, 3, 4, 5, 6          # (1,2) (3,4) (5,6)
N = 3
    .text
_start:
    lea     rcx, [rip+points]
    xor     eax, eax                    # sum = 0
    xor     edx, edx                    # i = 0
next:
    mov     rsi, rdx
    shl     rsi, 4                      # i * 16 : the scale alone cannot do this
    add     rax, [rcx + rsi + point.y]  # base + (i*16) + field offset
    inc     rdx
    cmp     rdx, N
    jl      next
    mov     rdi, rax                    # status = 12
    mov     eax, 60
    syscall

// ARM64: the same, walking a pointer by the struct size
    .global _start
    .equ point_y, 8
    .data
points: .quad 1, 2, 3, 4, 5, 6
    .text
_start:
    adrp    x1, points
    add     x1, x1, :lo12:points
    mov     x0, 0                       // sum
    mov     x2, 3                       // count
next:
    ldr     x3, [x1, #point_y]          // p->y
    add     x0, x0, x3
    add     x1, x1, #16                 // next struct: p += sizeof(struct point)
    subs    x2, x2, 1
    b.ne    next
    mov     x8, 93
    svc     #0

Both exit with status 12, as predicted. (Compilers on both machines usually pick the pointer-walking shape, as you saw in Chapter 5, so this is also how you will see it in real output.)

Padding. A compiler inserts invisible gaps so every field sits at an address that suits its size. Look at this real run, from C compiled and run on this machine:

struct a { char a; long b; char c; };   // fields in this order
struct b { long b; char a; char c; };   // same fields, reordered

struct{char,long,char}: size=24  offsets a=0 b=8 c=16
struct{long,char,char}: size=16  offsets b=0 a=8 c=9

The same three fields take 24 bytes in one order and 16 in the other, which is a third smaller. The rule: each field's offset is a multiple of its own size, and the whole struct's size is rounded up to its largest field's alignment. The first struct has 7 bytes of padding after a, and 7 more after c.

C never reorders your fields. Rust does. I ran this too, with rustc 1.75:

Rust default repr: size=16 align=8
Rust repr(C)     : size=24 align=8

A Rust struct with the fields u8, u64, u8 is 16 bytes by default, because the compiler is free to put the big field first. With #[repr(C)] (the C layout), it is 24. This matters the moment you write assembly that touches a Rust struct: you must use #[repr(C)] or you cannot know the offsets. Chapter 35 returns to this.

Why it is this way (the "why")

Why do alignment and padding exist? Because the hardware likes it. A field that sits inside one cache line and one word is read in one step (we measured the cost of crossing a line in Chapter 6). Padding spends bytes to save time. It also means that struct order is a real performance lever: for hot data, put the largest fields first.

Why does .bss exist? Because most big buffers start as zeros, and storing a megabyte of zeros in a file is waste. The trick turns "initialized to nothing" into "nothing stored."

What is the principle underneath? The same one as labels in Chapter 1: the human names things and the tool computes the numbers. Field offsets are labels for distances inside a struct.

Common mistakes

• The wrong stride for an array of structs. Use the struct's size, not the size of one field.
• Using .word and .align across machines. Use .short, .long and .balign.
• Forgetting the NUL. .ascii has no terminator. .asciz does.
• Assuming a Rust struct has C layout. It does not, unless you say #[repr(C)].
• Writing to .rodata. It faults.

Say it simply

An assembly file has sections: code, read-only data, initialized data, and zero-filled data that costs no disk space. Structs do not exist at this level. Fields are just offsets, and you should let the assembler name them. An array of structs steps by the whole struct's size, and compilers add padding so fields land on friendly addresses. Rust reorders fields unless you use #[repr(C)].

Check yourself

Exercise 9.1 (Warm-up): Predict, then check. What is sizeof for struct { int a; char b; int c; char d; }? What size do you get if you reorder it to put the ints first? Predict, then check with a C program and offsetof. A correct result: 16 bytes in the first order; 12 after reordering (4 + 4 + 1 + 1 + 2 padding).

Exercise 9.2 (Warm-up): Explain. In five sentences, explain .bss to a friend. Give an analogy and say where it breaks. What a strong answer includes: zero-initialized memory costs no file space because the loader creates and zeroes it; analogy: buying an empty lot instead of a lot with a pile of nothing already delivered; where it breaks: the memory is real once the program runs.

Exercise 9.3 (Core): Break it and fix it. In the x86-64 struct program, change shl rsi, 4 to a use of scale 8 (the buggy way). What does the program return? Explain the number. Then fix it. A correct result: the status is not 12 (it adds the wrong elements). Explain which quad words it summed.

Exercise 9.4 (Core): Implement. Define struct employee { long id; char name[16]; long salary; } in an assembly file with named offsets. Write find_max_salary(records, n) on x86-64 and ARM64. Use the assembler to compute the struct size from the offsets, and prove it by printing . - label between two consecutive records. Done when: it finds the right maximum for a 5-record array, and it also works for n = 1 and n = 0 (decide what n = 0 should return and say why).

Exercise 9.5 (Core): Rust layout. In Rust, write a struct with fields u8, u32, u16, u8 and print its size with and without #[repr(C)]. Use std::mem::offset_of! or manual pointer arithmetic to print each field's offset. Predict first. A correct result: the default layout is smaller or equal. Explain each gap in the repr(C) version.

Exercise 9.6 (Stretch): Design and defend. A hot loop reads only the y field of a million points. Compare the array-of-structs layout {x, y} with a struct-of-arrays layout (all x in one array, all y in another). Which is better for this loop and why? Name one loop where the other is better. What a strong answer includes: cache lines are full of useful data in the struct-of-arrays layout when only y is read; vector loads are straightforward for it; the array-of-structs layout is better when each iteration needs both fields of the same point.

Answer notes for Part 2

Read these only after you have tried the problems.

• 6.4: The sign-extended load of a byte whose top bit is 1 fills the register with 1s. The exit status only shows the low 8 bits, so both loads print the same status. To see the difference, print the whole register in gdb (p/x $rax), or compare the two results with a cmp.
• 7.3: 48 8b 84 cb 00 01 00 00. 48 is the 64-bit prefix, 8b is the load, 84 selects "SIB byte plus 4-byte displacement," and cb is the SIB byte holding scale 8 (top two bits 11), index rcx and base rbx.
• 8.5: With an 8 MiB stack and 8 bytes per push, you need about a million pushes before the stack is gone. The fault address is just below the lowest mapped stack page.
• 9.1: int a at 0, char b at 4, 3 bytes padding, int c at 8, char d at 12, 3 bytes tail padding gives 16. Reordering gives a 0, c 4, b 8, d 9, with 2 bytes of tail padding: 12.

Part 2 wrap-up

What you can now do:

• Say which byte of a number is first in memory, and prove it with a hex dump.
• Use mov, ldr and str with the right widths, and say what each leaves in the upper bits.
• Write any address you need: base, index, scale, offset, and PC-relative.
• Use lea as arithmetic, and say why it leaves flags alone.
• Use the stack with push/pop on x86-64 and stp/ldp on ARM64.
• Lay out a struct by hand, and say why padding exists.

Mini project: the memory laboratory. Time: 3 to 5 hours.

On both ISAs, build a program that:

1. Defines an array of 8 quad words in .data and a string in .rodata.
2. Sums the array three ways: base-plus-displacement, base-plus-scaled-index, and a walking pointer (post-index on ARM64).
3. Reverses the array in place using the stack.
4. Prints each result.
5. Dumps its own array as hex bytes before and after, using a small loop, so little-endian layout is visible.

Done when: all three sums are equal; your dump matches xxd of the same memory in gdb (x/64xb &arr); and you wrote one paragraph explaining why the reverse worked without a second array.

Write-up (half a page): What did you expect, what did you see, what did you learn?

Break it: remove one .balign, store to .rodata on purpose, and push without popping. Write down the exact fault each time.

Reading list for Part 2:

• Intel SDM Vol. 1, chapter on data types and addressing modes. The official definition of base, index, scale and displacement.
• Arm Architecture Reference Manual, load/store addressing modes. The exact offset ranges and the pre/post-index rules.
• Ulrich Drepper, "What Every Programmer Should Know About Memory" (2007). The long-standing long-form explanation of caches and memory behavior. Read the early sections on alignment and cache lines.
• Eli Bendersky's blog post "Stack frame layout on x86-64". A clear picture of how the stack is used by compiled code. (We do this properly in Part 4.)
• The GNU assembler manual (info as), "Machine Dependencies" for each target. This is where the .align and .word differences are documented.

Teach it back. In five sentences, as if to a friend, explain how a CPU finds element i of an array, and why the same instruction does not work for an array of 16-byte structs on x86-64.

Part 3: Control Flow, Flags and Branches

After this Part you can write any if, loop or switch by hand on both machines. You will know why a branch can cost ten times what its neighbors cost, and when removing it is worth it.

Chapter 10. Flags: one-bit answers to comparison questions

In this chapter: You will learn what flags are, how cmp uses them, and how every conditional jump is a question about those flags. You will learn one difference between the machines (the carry flag) that older guides get wrong.

You need first: Chapters 2 and 6.

The problem first

A CPU has no if. It has a program counter and instructions that change it. So how does it decide? It needs a place to remember the result of a comparison, so that a later instruction can ask about it. That place is the flags.

The model (the "what")

Flags are single bits that arithmetic instructions set to describe what just happened. On x86-64 they live in the FLAGS register. On ARM64 they are the four bits of NZCV. Four of them do nearly all the work:

The deepest idea of this chapter is this: flags hold raw facts, not opinions. After a - b, the flags say whether the result was zero, whether its top bit is set, whether the subtraction ran out of bits unsigned, and whether it ran out of bits signed. They do not say "a is less than b." Whether that is true depends on whether you meant a and b as signed or unsigned numbers. The flags do not know. You say which, afterwards, by the jump you choose.

cmp a, b is not a special comparator. It is a subtraction a - b whose result is thrown away. Only the flags are kept. Every conditional jump is a question about those flags.

Here is the table of questions. Be careful with the unsigned rows for ARM64. Look at the carry column:

Look at the unsigned rows. x86-64 says "less than" means CF=1. ARM64 says "less than" means C=0. The carry flag is inverted for subtraction between the two machines. I did not want to take this on trust, so I measured it. Here are real flag values after four operations, read from the actual hardware flags on x86-64 and from NZCV under qemu-user on ARM64:

For addition, the two machines agree: carry out means 1. For subtraction, x86-64 sets CF when there is a borrow, and ARM64 sets C when there is no borrow. That is exactly what the table says. If you ever translate code from one machine to the other, this is the line that bites.

Other flag facts worth knowing:

• Signed overflow happens when two numbers with the same sign give a result with the other sign. INT64_MAX + 1 shows it: OF=1.
• Unsigned carry happens when a bit falls out of the top. 0xFFFFFFFFFFFFFFFF + 1 shows it: CF=1, and the result is zero (ZF=1).
• On x86-64, inc and dec change every flag except CF. I tested it: after stc (set carry) and inc rax, CF was still 1.
• On x86-64, most arithmetic sets flags every time. On ARM64, only instructions with an s suffix (adds, subs) and the compare instructions (cmp, cmn, tst) set them. When you read ARM64 code, the s tells you flags matter here.

Build it (the "how")

Let's see the "raw facts" idea fail on purpose. We compare -1 with 1, as bits 0xFFFFFFFFFFFFFFFF against 1. The flags are the same either way. Only the jump differs:

# x86-64
    mov     rax, -1             # all bits set
    mov     rbx, 1
    cmp     rax, rbx
    jl      yes                 # signed less-than   (swap this for jb to test unsigned)

I ran both. With jl the program took the branch (the answer was "yes, -1 is less than 1"). With jb it did not (as an unsigned number, 0xFFFFFFFFFFFFFFFF is the biggest value there is). Same cmp, same flags, two different truths, chosen by your jump.

That is a very common bug. A C int compared with an unsigned quietly becomes an unsigned comparison, and the compiler emits jb or ja. In assembly you can see the choice. In C you cannot.

Now the other flag tool, test. test a, b does a AND b, throws away the result, and keeps the flags. The famous form is test rax, rax: it ANDs a register with itself, so ZF tells you whether it is zero and SF tells you whether it is negative. You saw it in Chapter 5 guarding n <= 0.

Why it is this way (the "why")

Why raw facts, not opinions? Because it is cheap and general. The subtraction already computes everything in one pass. Reading four bits out of it costs nothing. And the same flags serve signed and unsigned code, so the hardware needs only one compare path.

Why does ARM64 invert the carry? Because ARM defines subtraction as an addition: a - b is computed as a + (NOT b) + 1. The carry out of that addition means "no borrow." The designers kept the adder's carry as it is, one meaning for add and sub. x86-64 went the other way: it flips the carry out of a subtraction so that CF means "borrow." Neither choice is wrong. They are two ways to spend the same single bit.

What would make flags a bad idea? They are a hidden shared state. Every instruction that sets flags is a write to a place that every later conditional reads. That creates a chain the CPU must track. RISC-V avoids the problem by having no flags at all: beq and blt compare two registers inside the branch itself. It is a real trade-off, and the next two chapters show what the flag chain costs.

Common mistakes

• Choosing the wrong jump for the type. jl versus jb. Use the table.
• Assuming CF means the same thing on ARM64. For subtraction it is inverted.
• Putting an instruction that changes flags between the cmp and its jump. The flags belong to the most recent flag-setting instruction.
• Forgetting that lea and mov do not change flags (good to know), but add does (bad to forget).
• Expecting inc to change CF. It does not on x86-64.

Say it simply

Flags are single bits that remember facts about the last operation: zero, negative, carry or borrow, and overflow. A compare is a subtraction that keeps only the flags. A conditional jump then asks a question about those flags, and you choose whether to treat the numbers as signed or unsigned by choosing the jump. On subtraction the carry flag means "borrow" on x86-64 and "no borrow" on ARM64.

Check yourself

Exercise 10.1 (Warm-up): Predict, then check. Predict CF, ZF, SF and OF after mov al, 127; add al, 1 and after mov al, 255; add al, 1 (8-bit registers). Then check using pushfq and gdb, or with the helper program idea from this chapter. A correct result: the first gives OF=1, SF=1, CF=0, ZF=0 (a signed overflow). The second gives CF=1, ZF=1, SF=0, OF=0 (an unsigned wrap).

Exercise 10.2 (Warm-up): Explain. In five sentences, explain to a friend why the same cmp can mean "less" or "not less." Use an analogy and say where it breaks. What a strong answer includes: flags are raw facts about a subtraction; signed and unsigned are two readings of the same bits; analogy: a thermometer reading of 30 can mean hot in Celsius and cold in Fahrenheit (the number is the same; the scale is chosen later); it breaks because in the CPU the "scale" is chosen by an instruction, not by a label on the number.

Exercise 10.3 (Core): Break it. Write the -1 versus 1 program above on x86-64 with jl, then with jb. Predict both results first. Then rewrite it for ARM64 with b.lt and b.lo. Do the results match? A correct result: jl and b.lt say "yes"; jb and b.lo say "no". The answers match even though the carry values are opposite.

Exercise 10.4 (Core): Measure it yourself. Write an ARM64 program that does cmp x0, x1 for (5, 3) and (5, 7), reads nzcv with mrs x0, nzcv, shifts it right by 28, and exits with the result. Do the same on x86-64 with pushfq and pop rax. Make a table like the one above. A correct result: your C and CF columns are opposite for the subtraction cases.

Exercise 10.5 (Core): Trace by hand. For mov rax, 5; mov rbx, 7; cmp rax, rbx, work out by hand the result of 5 - 7 as a 64-bit value, and the four flags. Then say which of jl, jb, jg, ja, je are taken. A correct result: the result is 0xFFFFFFFFFFFFFFFE; SF=1, CF=1 (borrow), ZF=0, OF=0; jl, jb and jne are taken; jg, ja and je are not.

Exercise 10.6 (Stretch): Design and defend. RISC-V has no flags: a branch compares two registers directly. Give two advantages and two disadvantages of that design. Then say which one you would choose for a CPU that runs 8 instructions at a time. What a strong answer includes: advantages: no hidden shared state, branches are independent so the hardware tracks fewer dependencies; disadvantages: compare-and-branch is a bigger instruction, and multi-word arithmetic (carry chains) needs extra instructions to recover the carry; plus a reasoned choice for a wide CPU.

Chapter 11. Branches and loops

In this chapter: You will learn how each machine jumps, how loops are built from jumps, and the three branch instructions that save a compare (test, cbz, tbz). You will see why compilers write loops the way they do.

You need first: Chapter 10.

The problem first

You have a flag question, and you want the program to act on it. A branch is an instruction that says: if the question is true, set the program counter to this label. Otherwise, fall through to the next instruction. A jump with no question (always taken) is an unconditional branch.

The model (the "what")

# x86-64: the branch family
    cmp     rax, rbx
    je      equal               # taken if ZF=1
    jne     not_equal
    jl      less                # signed
    jae     above_or_equal      # unsigned
    jmp     always              # no question asked

// ARM64: the same family
    cmp     x0, x1
    b.eq    equal
    b.ne    not_equal
    b.lt    less                // signed
    b.hs    above_or_equal      // unsigned
    b       always

How far can a branch reach? A branch stores its distance inside the instruction, so the distance has a limit. This is a real constraint when a function gets large. On x86-64 you can see two sizes for the same je, with real encodings:

74 01                 je  short_target     (1-byte distance: reaches about +/-127 bytes)
0f 84 c8 00 00 00     je  near_target      (4-byte distance: reaches about +/-2 GiB)

The assembler picks the short form when the target is close and the long form when it is not. On ARM64 the reach is fixed by the instruction:

(tbz has less room than cbz, because the instruction also holds a bit number.)

Three instructions that save a compare.

• test (x86-64). test rax, rax sets flags from rax AND rax. It is the idiom for "is this zero, or negative?" Compilers use test/je for almost every null-pointer check. You can also test a mask: test al, 8 checks whether bit 3 is set.
• cbz and cbnz (ARM64). "Compare and branch if zero / if not zero." One instruction does the compare and the branch: cbz x0, done. It does not touch the flags.
• tbz and tbnz (ARM64). "Test bit and branch." tbnz x0, #3, set branches if bit 3 of x0 is 1. It is the hardware way to write if (flags & 8).

x86-64 has no instruction that fuses a compare and a branch into one encoded instruction. But modern x86-64 cores do macro-fusion: they spot a cmp or test followed immediately by a conditional jump and run the pair as one internal operation. So two instructions on the page can cost the same as one.

Loops. Every loop is these two shapes. A while loop tests at the top. A do-while loop tests at the bottom. Compilers prefer the do-while shape for counted loops, because it needs one branch per trip instead of two. They guard it once with an if before the loop begins. You saw exactly this in Chapter 5: test rsi, rsi; jle .L4 (the guard), then the loop body, then cmp; jne at the bottom.

Counting down removes the compare entirely, because an instruction that decrements already sets the zero flag.

Build it (the "how")

Let's sum the numbers 1 to 20. The answer is 210. First counting up on x86-64:

# x86-64: do-while shape, counting up
    .intel_syntax noprefix
    .global _start
    .text
_start:
    xor     eax, eax            # sum = 0
    mov     ecx, 1              # i = 1
top:
    add     eax, ecx            # body
    inc     ecx                 # update
    cmp     ecx, 20             # test
    jle     top                 # signed i <= 20 -> go again
    mov     edi, eax            # exit status = sum = 210
    mov     eax, 60
    syscall

Now counting down. The cmp disappears:

# x86-64: counting down. dec sets ZF, so no compare is needed.
    xor     eax, eax
    mov     ecx, 20
top:
    add     eax, ecx
    dec     ecx                 # ecx -= 1, and ZF = (ecx == 0)
    jnz     top                 # repeat while it is not zero
    ...

// ARM64: counting down. subs sets the flags.
    mov     w0, #0              // sum
    mov     w1, #20
top:
    add     w0, w0, w1
    subs    w1, w1, #1          // the "s" suffix: set flags
    b.ne    top

All three exit with status 210. The count-down versions are one instruction shorter in the loop. That is why compiled loops so often count down, even when your source counts up (when the order does not matter to the result).

One more tip: x86-64 has a loop instruction ("decrement rcx and jump if not zero"). Do not use it. It exists for history, and on modern chips it is slower than dec plus jnz. This is a good example of a rule from Chapter 5's vocabulary: not every instruction in the manual is one you want.

Why it is this way (the "why")

Why does the loop test go at the bottom? Count the branches per trip. A top-tested loop needs a conditional branch at the top (to leave) and an unconditional jmp at the bottom (to return). A bottom-tested loop needs only one conditional branch per trip. Over a million trips, that is a million fewer instructions.

Why do branches have limited reach? Because the distance is stored inside the instruction, and an instruction is small. tbz has a small reach because it also stores a register and a bit number. When a target is too far, the compiler (or the linker) reverses the test and jumps over an unconditional b, which has a much bigger reach. When you see an inverted jump over a lone b in real output, now you know the cause.

What would make this bad? The conditional branch is also the place where the CPU has to guess. Which way it goes decides what the CPU fetches next, before the answer is known. That is the subject of the next chapter, and it is where branches get expensive.

Common mistakes

• Using jle when the counter is unsigned. Use jbe.
• A loop that never ends because the counter is changed inside the body. (Or because a syscall destroyed it. See Chapter 4.)
• Off-by-one: jl versus jle. Write the first and last value on paper.
• Using loop. Slower than dec and jnz.
• Forgetting the guard. A do-while loop runs at least once. If n can be zero, you need the if before it.

Say it simply

A branch is an instruction that sets the program counter if a flag condition holds. A loop is a branch that goes backward. Compilers put the test at the bottom so each trip costs one branch, and they count down when they can, because decrementing sets the zero flag for free. test, cbz and tbz save a compare when you only need to ask about zero or a single bit.

Check yourself

Exercise 11.1 (Warm-up): Predict, then check. Without running anything, say how many times the body runs for mov ecx, 5; top: ...; dec ecx; jnz top and for the same loop with mov ecx, 0 at the start. Then run both with a counter. A correct result: 5 times, and then... a huge number of times (4 billion), because dec of 0 wraps around to 0xFFFFFFFF, which is not zero. That is the "forgot the guard" bug.

Exercise 11.2 (Warm-up): Explain. In five sentences, explain why compilers put the loop test at the bottom. Include an analogy and where it breaks. What a strong answer includes: one conditional branch per trip instead of a conditional plus an unconditional jump; the guard before the loop covers the zero-trip case; analogy: checking the oven at the end of each stir rather than walking back to the door; where it breaks: the CPU predicts the branch, so the real cost is mispredictions and not instruction count alone.

Exercise 11.3 (Core): Implement. Write count_set_bits(x) on both ISAs with a loop that tests the low bit and shifts right (do not use popcnt or cnt). Use test al, 1 or tbnz x0, #0 for the test. Done when: it returns 0 for 0, 1 for 1, 8 for 0xFF, and 64 for 0xFFFFFFFFFFFFFFFF, and you can say how many loop trips each case needs.

Exercise 11.4 (Core): Break it. Write a long jump on x86-64: je far with .rept 200 of nop between the jump and its target. Look at the encoded bytes. Then do the same on ARM64 with a cbz and .rept 300000 of nop, and read what the assembler says. A correct result: x86-64 switches to the 6-byte near form. ARM64's cbz cannot reach about 1.2 MB of padding: I got Error: conditional branch out of range. With 200,000 nops (800 KB) it assembled and linked fine.

Exercise 11.5 (Core): Predict, then check. Compile long count(const long *a, long n) { long c = 0; for (long i = 0; i < n; i++) c += (a[i] == 0); return c; } at -O2 for both machines. Predict whether each compiler counts up or down and whether it uses a pointer or an index. Read the output. A correct result: it depends on the compiler version. The point is to see whether your prediction was right, and to name every transformation you spot.

Exercise 11.6 (Stretch): Design and defend. cbz and tbz exist on ARM64 and cost encoding space. Make the case for removing them in favor of cmp plus b.cond, or for adding more fused-compare branches. Use the frequency data from Chapter 5 (cbz was 2.4% of ARM64 instructions, cbnz 1.4%, tbnz 0.7%). What a strong answer includes: the data shows they are common enough to justify; the saving is one instruction and no flag write; the cost is encoding space and a smaller reach; and a reasoned position.

Chapter 12. Branch prediction and branchless code

In this chapter: You will learn why a branch can be slow even when it is only one instruction. You will measure the cost on a real machine. You will learn the instructions that choose a value without branching, and the cases where removing a branch makes code slower.

You need first: Chapters 10 and 11.

The problem first

The CPU in Chapter 2 runs one instruction at a time. A real CPU does not. It starts the next instructions before the current ones finish, like a factory line, so that many instructions are in progress at once. This line is called the pipeline.

A branch is a problem for a pipeline. To keep it full, the CPU must fetch the instructions after the branch. But which ones? Until the flags are known, the CPU does not know whether the branch will jump. Waiting would leave the line empty. So the CPU guesses.

The model (the "what")

This guess is called branch prediction. The CPU keeps a record of how each branch behaved before, and bets on the same again. It starts running the guessed path right away. This is speculative execution. If the guess was right, no time was lost. If it was wrong, the CPU has to throw away everything it started on the wrong path and begin again from the correct place. That is a misprediction.

   time -->
   guessed right:   [fetch A][fetch B][fetch C]...            keeps going
   guessed wrong:   [fetch A][fetch B (wrong!)] ...flush... [fetch X][fetch Y]
                                              ^^^^^^^^^^^^^
                                              this gap is the cost

How much does a miss cost? Typical numbers are around 15 to 20 cycles on a modern desktop or server core. The exact number depends on the chip. Agner Fog's microarchitecture manuals list it for each one. Rather than quote a figure, let me measure it. This is the experiment, in C. The loop adds up the elements of an array that are at least 128. The array holds random numbers from 0 to 255, so the branch is true half the time, with no pattern.

// branchy: a real conditional branch (compiled with if-conversion off)
long branchy(const int* d) {
    long s = 0;
    for (int i = 0; i < N; i++) { if (d[i] >= 128) s += d[i]; }
    return s;
}
// branchless: arithmetic only. m is all-ones if bit 7 is set, else zero.
long branchless(const int* d) {
    long s = 0;
    for (int i = 0; i < N; i++) { int v = d[i]; int m = -((v >> 7) & 1); s += v & m; }
    return s;
}

Each is run on the random array, and then on the same array sorted. When it is sorted, the branch is false for the first half and true for the second half, so it becomes easy to predict. I confirmed in the disassembly that the first function really has a conditional jump (jle) and the second does not. Real results on this machine (Intel Xeon @ 2.80 GHz, one core, in a VM), best of five runs:

Read this table slowly, because it holds three lessons.

1. The branch costs 9 times more on random data (4.02 vs 0.44). The work is identical. Only the predictability changed. (The size of the ratio depends on how much other work is in the loop; a tiny loop like this one shows a large ratio. 9 times is what I measured, and I repeated the experiment in two more sessions and got 9.8 and 9.0 times, so this ratio is stable even though other numbers on this machine were not. See the note at the start of Part 8.)
2. The branchless version is flat: 0.80 ns either way. It does not care about the data. On random data it is 5 times faster than the branchy loop.
3. On sorted data the branchless version is slower: 0.80 versus 0.44. When the branch is easy to predict, the branch is nearly free, and the branchless code does extra arithmetic for nothing. So "branchless is faster" is not a rule. It is a rule for unpredictable data.

Let's work out the cost of one miss. Half the elements miss. The extra time per element is about 4.02 minus 0.44, which is 3.58 ns. Divide by one half, and one miss costs about 7 ns. If this core ran near 2.8 GHz, that is about 20 cycles. (I did not measure the clock, so treat "about 20 cycles" as the right ballpark and not an exact figure.)

The tools for choosing without branching.

x86-64 has cmovcc, the conditional move: copy the source to the destination if the flag condition holds, otherwise do nothing. And setcc turns a flag into a 0 or 1 in a register.

# x86-64: max(a, b) without a branch
    mov     rax, -5             # a
    mov     rcx, 3              # b
    cmp     rax, rcx
    cmovl   rax, rcx            # if a < b (signed), rax = b. Otherwise leave rax alone.
    # rax = 3. No branch exists, so nothing can be mispredicted.

ARM64 has a richer family: csel (select), cset (set to 1 or 0), cinc, csinc, csneg:

// ARM64: max(a, b)
    mov     x0, #-5
    mov     x1, #3
    cmp     x0, x1
    csel    x0, x0, x1, ge      // x0 = (x0 >= x1) ? x0 : x1   -> 3

I ran both, and both returned 3. Now the family, which a lot of compiler output uses:

• csel xd, xn, xm, cond picks xn if the condition holds, else xm.
• cset xd, cond sets xd to 1 if the condition holds, else 0.
• csinc xd, xn, xm, cond picks xn if the condition holds, otherwise xm + 1.

csinc is easy to read backwards. I tested csinc x0, xzr, x0, eq, which is not "x0 + 1 if equal, else 0." With the condition true, the result was xzr (0), and with the condition false, it was x0 + 1 (11 when x0 was 10). The pattern is "first source if true, second source plus one if false." And cset is defined as csinc xd, xzr, xzr, <opposite condition>.

ARM64 has one more tool that has no x86-64 twin: ccmp, a conditional compare. It compares only if the previous condition held, and otherwise forces the flags to a fixed value you choose. That builds || and && chains without branches:

// ARM64: z = (x == 0 || y == 0), with no branch
    cmp     x0, #0
    ccmp    x1, #0, #4, ne      // if x != 0: compare y with 0.  else: set flags to 0b0100 (Z=1)
    cset    x2, eq              // Z is set if either was zero

I tested it with (x=5, y=0) and got 1, and with (x=5, y=6) and got 0. The third operand, #4, is the flag pattern to install when the condition fails, and 4 means Z=1.

Build it (the "how")

Let's see how the compiler wrote the branchless loop from the experiment. It did not use cmov at all. It did this, real output from gcc -O1:

    mov     edx, DWORD PTR [rdi]    # v
    mov     eax, edx
    shl     eax, 24
    sar     eax, 31                 # arithmetic shift: smear one bit across the whole register
    and     eax, edx                # v & mask
    cdqe
    add     rcx, rax                # s += ...
    add     rdi, 4
    cmp     rdi, rsi
    jne     (top)

There is still one branch, the loop test at the bottom, but it is almost always taken, so it predicts perfectly. The unpredictable data-dependent branch is gone, replaced by a shift that turns one bit into a mask. This is the mask trick: if the condition is a bit, smear it into all-ones or all-zeros and and it with the value.

Why it is this way (the "why")

The idea underneath is data flow over control flow. A branch asks the CPU to choose what to do. A cmov asks it to choose which value, after computing both. The first needs a guess. The second needs none, because there is nothing to guess; both paths' values are computed (cheaply, predictably) and one is picked. You trade a possible 20-cycle stall for a few extra, certain instructions. That trade wins when the branch is unpredictable and loses when it is not, exactly as the table showed.

Where branchless cannot go. A cmov picks between values. It cannot skip an operation. If one path dereferences a pointer that might be null, a branchless version would still dereference it, and fault. This is why a compiler keeps a branch for p ? *p : 0. I compiled that, and gcc -O2 produced test rdi, rdi; je .L1; mov eax, [rdi]: a real branch that guards the load. The same goes for division (a divide by zero) and anything with a side effect. When you see a branch where you expected a cmov, this is usually why.

The cost of speculation. A CPU that runs ahead on a guess does work that might be thrown away. In 2018 researchers showed that the leftover effects of such discarded work (in the cache) could leak secrets. The attacks are called Spectre and Meltdown. This is why some software uses extra instructions to stop speculation. It is a good reminder that "the CPU guesses" is not only a performance fact.

Common mistakes

• Assuming branchless is always faster. It lost on sorted data above. Measure on your data.
• Assuming a compiler cmov is always a win. Compilers sometimes make a branch into a cmov and make code slower, when the branch was predictable.
• Using cmov where one path must not run. It still computes both.
• Benchmarking only sorted or only random data. Test both, and the real data.
• Ignoring the loop branch. It is usually predictable, so it is rarely the problem.

Say it simply

A CPU runs ahead of the branch by guessing which way it will go. A right guess is free. A wrong guess costs around 15 to 20 cycles. On random data a branch inside a loop can make that loop several times slower, and on this machine it was 9 times. Instructions like cmov and csel pick a value without branching, and win when the branch is unpredictable, but lose when it is easy, and cannot skip work that must not run.

Check yourself

Exercise 12.1 (Warm-up): Predict, then check. Before running the benchmark, predict the four numbers in the table in your own words (which are fast, which slow, and by roughly how much). Then compile br.c as shown and run it. Compare. A correct result: branchy-random is the slowest by a wide factor; branchless is flat; branchy-sorted is the fastest. Your absolute numbers will differ.

Exercise 12.2 (Warm-up): Explain. In five sentences, explain to a friend why one branch can cost 20 times a simple instruction. Use an analogy and say where it breaks. What a strong answer includes: the CPU runs ahead on a guess; a wrong guess throws away the work; analogy: a driver who takes a turn before the GPS says, and has to turn back; where it breaks: the CPU has a record of past behavior and is right most of the time.

Exercise 12.3 (Core): Implement. On both ISAs, write abs(x) and clamp(x, lo, hi) with no branches. Use cmov/csel or cneg on ARM64 (hint: cneg negates if a condition holds). Done when: both are correct for 0, -1, INT64_MIN and INT64_MAX. For abs(INT64_MIN), say what your code returns and what a correct abs should return (there is no positive value that fits).

Exercise 12.4 (Core): Break it. Change the benchmark so the branch is predictable in a different way: use data that repeats a pattern like 0,255,0,255,.... Predict the branchy time. Run it. A correct result: modern predictors learn short patterns, so the branchy loop is fast again, close to the sorted time. That shows what the CPU actually predicts: not "sorted," but "a pattern it can learn."

Exercise 12.5 (Core): Predict, then check. Compile int f(int *p) { return p ? *p : 0; } and int g(int a, int b) { return a < b ? a : b; } at -O2 for both ISAs. Predict which one uses cmov or csel and which one keeps a branch. Check. A correct result: g is branchless (cmov/csel); f keeps a branch to guard the load. Say why for each.

Exercise 12.6 (Stretch): Design and defend. A colleague says: "always compile with a flag that turns every branch into a cmov." Write a reply that is fair. Say when it would help, when it would hurt, and how you would settle it with data. What a strong answer includes: unpredictable branches benefit; predictable ones lose (the sorted case); some paths cannot be speculated (loads, divides, side effects); the test is a benchmark on real data, and a profile (such as branch-miss counters) to find which branches miss.

Chapter 13. Jump tables and indirect branches

In this chapter: You will learn how a switch becomes a table, how a jump through a table works on both machines, and what an indirect branch costs. This is the base for the interpreter loop you will build in Chapter 37.

You need first: Chapters 7, 11 and 12.

The problem first

You have a switch with many cases. A chain of cmp and je would test them one after another: slow for the last case. If the cases are the numbers 0, 1, 2, 3, ..., there is a better way. Use the number to index a table of addresses, and jump straight there. One lookup, no matter how many cases.

The model (the "what")

A normal branch has its target written inside the instruction. An indirect branch takes its target from a register or from memory. That is what lets the target be chosen at run time. The table of addresses is a jump table.

# x86-64: a jump table by hand
    .section .rodata
    .balign 8
table:
    .quad case0, case1, case2, case3       # the addresses of four labels
    .text
    mov     eax, 2                          # the selector
    cmp     eax, 3
    ja      default                         # outside 0..3? (unsigned: also catches negatives)
    lea     rdx, [rip+table]
    jmp     qword ptr [rdx + rax*8]         # jump to the address stored at table[selector]

// ARM64: the same idea
    .section .rodata
    .balign 8
table:
    .quad case0, case1, case2, case3
    .text
    mov     x0, #2
    cmp     x0, #3
    b.hi    default                         // unsigned
    adrp    x1, table
    add     x1, x1, :lo12:table
    ldr     x2, [x1, x0, lsl #3]            // x2 = table[selector]
    br      x2                              // indirect branch

I ran both with the selector set to 2, and each landed on case2 and exited with status 30, as expected. One detail worth a second look: the single cmp and ja handles both "too big" and "negative." A negative number, read as unsigned, is enormous, so it is above 3. This is a favorite compiler trick: one unsigned compare checks both ends of a range.

What the compiler really does. Here is something that surprised me, so run this yourself. Take a switch where every case just returns a constant:

int f(int x){ switch(x){ case 0: return 10; case 1: return 20; case 2: return 37;
                          case 3: return 41; case 4: return 5;  case 5: return 77; default: return -1; } }

gcc -O2 did not make a jump table. It made a table of the answers: a range check (cmp edi, 5; ja), and then one load, mov eax, [table + rdi*4]. There was no indirect jump at all. A jump table appears only when the cases do different work. So here is a switch whose cases call different functions, and the real gcc -O2 output.

On x86-64, built as a non-PIE program, the table holds absolute addresses:

g:
    cmp     edi, 4
    ja      .L2
    mov     edi, edi                       # zero the upper half of rdi (a 32-bit write)
    jmp     [QWORD PTR .L4[0+rdi*8]]       # jump through the table
.L4:
    .quad   .L8, .L7, .L6, .L5, .L3        # one address per case

Built the default way (a position-independent program), the table holds distances instead of addresses, so it works wherever the program loads:

g:
    cmp     edi, 4
    ja      .L2
    lea     rdx, .L4[rip]                  # the table's address
    mov     edi, edi
    movsx   rax, DWORD PTR [rdx+rdi*4]     # load a 4-byte offset, sign-extended
    add     rax, rdx                       # table address + offset = the real target
    jmp     rax
.L4:
    .long   .L8-.L4, .L7-.L4, .L6-.L4, .L5-.L4, .L3-.L4

On ARM64 the compiler did something different for the same five cases: it used a short chain of compares (cmp w0, 2; beq ...; cmp w0, 3 ...) with no table at all. With 12 cases, it built a table of one-byte offsets:

h:  cmp     w0, 11
    bls     .L17
    mov     w0, -1
    ret
.L17:
    adrp    x1, .L4
    add     x1, x1, :lo12:.L4
    ldrb    w1, [x1, w0, uxtw]             // one BYTE per case
    adr     x0, .Lrtx4
    add     x1, x0, w1, sxtb #2            // base + (byte * 4)
    br      x1
.L4:
    .byte   (.L15 - .Lrtx4) / 4, (.L14 - .Lrtx4) / 4, ...

Why one byte, and why divide by 4? Every ARM64 instruction is 4 bytes, so a target is always a multiple of 4. The table stores the distance in instructions, so one byte can reach 128 instructions either way. That is a neat use of the fixed instruction width, and it makes the table 8 times smaller than a table of 8-byte addresses.

Computed goto. GNU C has a feature, goto *ptr, that compiles to an indirect jump. It is how many fast interpreters are written. We use it in Chapter 37.

Build it (the "how")

The two programs above are complete once you add the case labels. Here is the x86-64 one in full:

    .intel_syntax noprefix
    .global _start
    .section .rodata
    .balign 8
table:
    .quad case0, case1, case2, case3
    .text
_start:
    mov     eax, 2                      # try 0..3 and 9
    cmp     eax, 3
    ja      default
    lea     rdx, [rip+table]
    jmp     qword ptr [rdx + rax*8]
case0:  mov edi, 10
        jmp done
case1:  mov edi, 20
        jmp done
case2:  mov edi, 30
        jmp done
case3:  mov edi, 40
        jmp done
default: mov edi, 99
done:   mov eax, 60
        syscall

Change mov eax, 2 to each of 0, 1, 2, 3 and 9. You should get 10, 20, 30, 40 and 99.

Why it is this way (the "why")

Why is an indirect branch harder to predict? A conditional branch has two possible outcomes. An indirect branch can have as many targets as there are table entries. The CPU must guess where to go, not just whether. So the predictor holds a record of past targets, and an unpredictable selector (say, the opcode in an interpreter) can miss often. This is why interpreter dispatch is a performance topic, and why Chapter 37 measures it.

Why do position-independent programs use offsets? The address of a table entry's target changes when the program loads at a new address. An absolute address in the table would need patching by the loader on every run. An offset from the table itself never changes. This is the same "everything is a distance" idea as rip-relative addressing and adrp.

The security angle. Indirect branches are a target for attacks (an attacker who can change a table entry controls where the program goes). Modern systems add checks. On x86-64 Linux, compilers often emit notrack jmp and every indirect-jump target starts with endbr64 (Chapter 17). On ARM64 there is a similar feature called BTI.

What would make a jump table the wrong choice? If there are only two or three cases, a compare chain is smaller and well predicted. If the cases are sparse (say, 1, 1000, 1000000), a table would be mostly empty, so compilers use a binary search of compares instead. The compiler chooses by counting.

Common mistakes

• Not range-checking the selector. A bad index jumps to garbage.
• Using a signed compare for the range check. Use unsigned (ja, b.hi), so negatives are rejected too.
• A table in .data when it can be .rodata. Read-only is safer.
• Absolute addresses in position-independent code. Use offsets.
• Expecting a switch to always become a table. It may become a value table, a compare chain, or a tree.

Say it simply

A jump table is an array of addresses. You use the selector as an index, load the address, and jump to it, so any case takes the same time. One unsigned compare checks the range. Compilers build tables only when the cases do different work, and use offsets instead of addresses in position-independent code. An indirect branch has many possible targets, so it can be harder to predict than a normal branch.

Check yourself

Exercise 13.1 (Warm-up): Predict, then check. Using the x86-64 jump table, predict the exit status for selectors 0, 3 and 4. Run all three. A correct result: 10, 40, 99.

Exercise 13.2 (Warm-up): Explain. In five sentences, explain to a friend why one cmp and one ja rejects both too-large and negative selectors. What a strong answer includes: a negative number read as unsigned is a huge positive number; so "above 3, unsigned" covers both ends; this saves a second compare.

Exercise 13.3 (Core): Implement. Extend the jump-table program so that a table of 8 handlers each add a different amount to a running total, and loop over a short array of selectors. Do it on both ISAs. Make the ARM64 table use offsets in instructions (as the compiler did) rather than addresses. Done when: an array of selectors like [3, 0, 7, 2] gives the right total, and a selector of 8 or more is handled safely.

Exercise 13.4 (Core): Predict, then check. Compile your own switch with 4, 8, 20 and 100 cases, once with a different function call per case and once returning constants. For each of the 8 versions, predict: jump table, value table, or compare chain? Check on both ISAs. A correct result: the constant-returning ones become value tables (or arithmetic), and the others become jump tables beyond a handful of cases. Record where each compiler's threshold lies.

Exercise 13.5 (Core): Break it. Remove the range check from your jump table and call it with selector 9. What does the program do? Use gdb to find the address it jumped to. A correct result: it jumps to whatever bytes sit after the table, and crashes (SIGSEGV or SIGILL). Explain why the range check is not optional.

Exercise 13.6 (Stretch): Design and defend. An interpreter's main loop has 60 opcodes. Compare (a) one switch with one indirect jump at the top, and (b) a separate indirect jump at the end of every opcode handler (the "threaded" style). Which predicts better, and why? What a strong answer includes: in (a) all dispatches share one branch, so the predictor sees a mixed history; in (b) each handler's jump has its own history, which often follows patterns (an if is often followed by a jump); cost is code size and compiler support (computed goto). We measure this in Chapter 37.

Answer notes for Part 3

• 11.1: dec ecx on 0 gives 0xFFFFFFFF, which is not zero, so the loop runs about 4.29 billion times. The fix is a guard (test ecx, ecx; jz skip) before the loop.
• 12.3: abs(INT64_MIN) has no correct positive answer in 64 bits. Two's complement negation of the most negative number gives the same number back (INT64_MIN). Real code must decide: wrap, saturate, or trap. In C it is undefined behavior; in Rust, abs panics in debug builds and wrapping_abs returns INT64_MIN.
• 12.4: A repeating pattern like 0,255,0,255 is learned by the predictor within a few iterations; expect the time to drop to near the sorted case.
• 13.3 (hint): On ARM64, a table entry (handler - table_base) / 4 fits in a byte if all handlers are within 128 instructions. Compute with .byte (label - base)/4 and decode with add x1, base, w1, sxtb #2.

Part 3 wrap-up

What you can now do:

• Name the four flags and say which instructions set them on each machine.
• Choose the right conditional jump for signed and unsigned comparisons.
• Say why the carry flag is inverted between x86-64 and ARM64 for subtraction.
• Write loops in do-while shape and count-down shape.
• Say what a branch misprediction costs, and show it with a measurement.
• Write max, abs and a boolean chain without branches, and say when not to.
• Build and read a jump table on both machines.

Mini project: the branch laboratory. Time: 4 to 6 hours.

On both ISAs, in assembly or C with inspected output:

1. Classify an array of signed 64-bit numbers into counts of negative, zero and positive, first with branches, then without them (setcc or cset).
2. Write a binary search over a sorted 16-element array, once with branches and once with cmov/csel picking the next index.
3. Benchmark both pairs on random and sorted data and make a four-cell table like the one in Chapter 12.

Done when: the branchy and branchless versions give identical answers on INT64_MIN, INT64_MAX, and an array of all-equal values; and you can say, for each loop, whether its branch is predictable and why.

Write-up (half a page): For each of your four numbers, what did you predict and what did you see?

Reading list for Part 3:

• Agner Fog, "The microarchitecture of Intel, AMD and VIA CPUs" (agner.org/optimize). Misprediction penalties and predictor behavior for each chip. Read the branch prediction section for the chip you own.
• Daniel Lemire's blog on branch mispredictions and branchless code. Short, measured experiments in the same spirit as Chapter 12.
• The famous Stack Overflow question "Why is processing a sorted array faster than processing an unsorted array?" The experiment you reproduced, with its long answer. Read it after you have run your own.
• Arm Architecture Reference Manual: conditional select and conditional compare instructions. The exact definitions of csel, csinc and ccmp.
• Kocher et al., "Spectre Attacks: Exploiting Speculative Execution" (2018/2019). The paper that showed speculation has security consequences.

Teach it back. In five sentences, as if to a friend, explain what a CPU does when it meets a branch, and when removing the branch is a good idea.

Part 4: Functions and the Calling Convention

After this Part you can write functions that C and Rust can call, call functions that C and Rust wrote, and read any function prologue without guessing. This is the Part where assembly stops being a toy.

Chapter 14. The calling convention: a contract between strangers

In this chapter: You will learn the contract that lets code written by different people, in different languages, call each other. You will learn which registers carry arguments, which survive a call, and how both machines pass floats, big structs and extra arguments.

You need first: Chapters 6 to 8.

The problem first

You write a function. Someone else, with a different compiler and in a different language, writes the code that calls it. They have never seen your source. How does the caller know where to put the arguments? Where will the answer be? And which of their values will still be there when your function returns?

The hardware helps only a little. The call instruction saves a return address, and ret goes back to it. That is all. Everything else, every register role, is a promise people made. The promise is called the calling convention, and the larger agreement that includes it (sizes, layouts, names) is the ABI: the application binary interface.

The model (the "what")

On Linux, x86-64 follows the System V AMD64 ABI, and ARM64 follows the Arm 64-bit Procedure Call Standard (AAPCS64). Here is the contract for both, in one table. Notice the details that are easy to forget: r11 is caller-saved, x18 is a platform register, and the low halves of v8-v15 are callee-saved. Read each row.

Look at three rows more closely.

Caller-saved versus callee-saved. This is the heart of the contract. A caller-saved register may be destroyed by any call. If the caller wants its value after the call, the caller must save it somewhere first. A callee-saved register must come back unchanged. If a function wants to use rbx, it must save the old value on entry and restore it before returning. The split exists because someone has to do the saving, and the contract divides the job so that neither side saves more than it needs. A function that only needs a few scratch values can use caller-saved registers for free.

The link register. On x86-64, call pushes the return address onto the stack, and ret pops it. On ARM64, bl ("branch with link") puts the return address in register x30, and ret jumps to it. Because x30 is overwritten by the next bl, a function that calls others must save x30 on the stack first. That is why you see stp x29, x30, [sp, #-16]! at the start of every non-leaf ARM64 function.

The hidden pointer. A function that returns a big struct has no register big enough. The caller reserves space and passes its address as a hidden first argument. On x86-64 that address goes in rdi, and the function returns it in rax. On ARM64 it goes in x8.

Let's check these claims against a real compiler, because this is an area where memory is not good enough. Here is a function call mixing integers and floats:

extern long f(long a, double b, long c, double d);
long call_mixed(void) { return f(1, 2.0, 3, 4.0); }

Where do the four arguments go? Integers and floats use separate register sequences. So the first integer goes in rdi, the first float in xmm0, the second integer in rsi (not rdx), and the second float in xmm1. Here is the real gcc -O1 output:

# x86-64
    mov     edi, 1              # 1st integer argument -> rdi
    movsd   xmm0, QWORD PTR .LC0[rip]   # 2.0 -> xmm0
    mov     esi, 3              # 2nd integer argument -> rsi   (NOT rdx)
    movsd   xmm1, QWORD PTR .LC1[rip]   # 4.0 -> xmm1
    call    f

Note that the integer and float sequences count separately: the second integer is rsi, not rdx.

Now a struct that is too big for registers:

struct big { long a, b, c, d; };           // 32 bytes
struct big make_big(long x);
struct big pass_big(struct big s);

On both machines the caller makes a temporary copy. But the two machines hand it to the function differently, and it is easy to mix them up. Here is what I saw in the real output:

• Returning struct big: x86-64 put the address of the result space in rdi (mov rdi, rsp), and ARM64 put it in x8.
• Passing struct big as an argument: x86-64 copied the 32 bytes onto the stack, as part of the stack arguments. ARM64 copied the struct to memory and passed a pointer to the copy in x0, an ordinary argument register. (Only a returned big struct uses x8. An argument does not.)

Stack arguments. When there are more arguments than registers, the rest go on the stack. x86-64 has 6 integer argument registers. ARM64 has 8. Here is a call with 10 integer arguments, real output from gcc -O1 with the callee defined elsewhere:

# x86-64: call10(x) calls f10(x, 2, 3, ..., 10)
call10:
    sub     rsp, 8              # padding, so rsp is 16-aligned at the call
    push    10                  # arguments 10, 9, 8, 7 go on the stack, last one first
    push    9
    push    8
    push    7
    mov     r9d, 6              # arguments 6 down to 2 go in registers
    mov     r8d, 5              # (argument 1, x, is already in rdi)
    mov     ecx, 4
    mov     edx, 3
    mov     esi, 2
    call    f10@PLT
    add     rsp, 40             # the CALLER removes the stack arguments (and padding)
    ret

// ARM64: the same call. Only arguments 9 and 10 do not fit in x0..x7.
call10:
    sub     sp, sp, #32
    stp     x29, x30, [sp, 16]      // save frame pointer and return address
    add     x29, sp, 16
    mov     x1, 10
    str     x1, [sp, 8]             // argument 10 at [sp+8]
    mov     x1, 9
    str     x1, [sp]                // argument 9 at [sp]
    mov     x7, 8                   // arguments 8 down to 2 in registers
    mov     x6, 7
    mov     x5, 6
    mov     x4, 5
    mov     x3, 4
    mov     x2, 3
    mov     x1, 2
    bl      f10
    ...

Notice how the callee on x86-64 reads its stack arguments: at [rsp+8], [rsp+16] and so on. Why +8, not +0? Because [rsp] holds the return address that call just pushed. The first stack argument sits right above it. On ARM64 the callee reads [sp] and [sp, 8] directly, because nothing was pushed on the stack by the bl.

Finally, variadic functions like printf. When you call a function that takes ..., x86-64 requires you to set al (the low byte of rax) to an upper bound on the number of vector registers you used for arguments. I compiled printf("%f\n", 1.5) and saw mov eax, 1 before the call. Forgetting this is a classic bug in hand-written assembly: a call to printf with a float prints garbage.

Build it (the "how")

The best way to learn this table is to read it from a debugger. Use this ritual on any function you do not understand: set a breakpoint at its first instruction, and print the argument registers.

(gdb) break sum3
(gdb) run
(gdb) info registers rdi rsi rdx      # on x86-64: the first three arguments
(gdb) info registers x0 x1 x2         # on ARM64

If the values are the arguments you passed, the convention is working. If they are not, one of the two sides is not following it.

Why it is this way (the "why")

Why are there callee-saved registers at all? Imagine every register was caller-saved. Then every call would force the caller to save everything it cared about, even if the callee used just one register. Now imagine every register was callee-saved. Then every function would have to save every register it touched, even for tiny leaf functions that could have used scratch space. The split is a compromise. Roughly half and half is what both ABIs chose, and it works well because most functions need a few scratch registers and a few that last.

Why does the ABI pass arguments in registers? Because memory is slow (Chapter 2 measured the gap). An argument in a register is available at once. Early x86 ABIs passed everything on the stack. The 64-bit ABIs moved to registers when machines had enough of them.

What would make a different ABI better? Only measurements of the code that actually runs. The six-versus-eight argument-register difference is an example: ARM64 has more registers to spend, so more calls avoid the stack entirely.

The principle underneath: an ABI is a contract about bytes and registers, not about source languages. That is why C, Rust, Go and Swift can call each other when they agree to use the C ABI (extern "C" in Rust). Rust's own ABI is deliberately not stable. We return to this in Chapter 17.

Common mistakes

• Counting integer and float arguments together on x86-64. They use separate sequences.
• Using rcx for the 4th argument in a syscall. Syscalls use r10. Function calls use rcx.
• Forgetting that rdx is destroyed by a call. It is caller-saved.
• Using rbx without saving it. It is callee-saved; the caller trusts it.
• Reading the first stack argument at [rsp] on x86-64. That is the return address. It is at [rsp+8].
• Not setting al before calling a variadic function.

Say it simply

The calling convention says where arguments go, where the answer comes back, and which registers a function must leave alone. On x86-64 the first six integer arguments go in rdi, rsi, rdx, rcx, r8, r9 and floats in xmm0 to xmm7, counted separately. On ARM64, integers go in x0 to x7. Registers split into those a call may destroy (caller-saved) and those a function must restore (callee-saved). Extra arguments go on the stack.

Check yourself

Exercise 14.1 (Warm-up): Predict, then check. For long f(long a, double b, long c, double d, long e), say which register holds each argument on x86-64 and on ARM64. Check with a call compiled at -O1. A correct result: x86-64: rdi, xmm0, rsi, xmm1, rdx. ARM64: x0, d0, x1, d1, x2.

Exercise 14.2 (Warm-up): Explain. In five sentences, explain caller-saved versus callee-saved to a friend. Use an analogy and say where it breaks. What a strong answer includes: someone must preserve values across a call; scratch registers are free for anyone to use but die at a call; preserved registers must be restored; analogy: a shared kitchen where some counters you must clean before leaving and others you can leave messy; it breaks because registers do not have a "kitchen manager"; only the convention enforces it.

Exercise 14.3 (Core): Read it. Write a C function with 8 integer parameters that returns their sum, compile at -O2 for both machines, and mark in the output every place it reads a stack argument. Predict the offsets first. A correct result: x86-64 reads [rsp+8] and [rsp+16] (arguments 7 and 8); ARM64 reads none (8 arguments fit in x0-x7).

Exercise 14.4 (Core): Break it. Write a call_printf in assembly that prints a float with printf("%f\n", 1.5), once without setting al and once with mov eax, 1. What happens? A correct result: it may print garbage or crash without the right al, depending on the libc. Explain what printf does with al.

Exercise 14.5 (Core): Predict, then check. Compile struct s { long a; long b; }; struct s mk(long x); and struct s16 { long a, b; } pass and return by value. Where does a 16-byte struct go on each machine? Check. Does it need the hidden pointer? A correct result: on both machines a 16-byte struct of two longs fits in two registers (rax:rdx returned on x86-64, x0:x1 on ARM64). No hidden pointer. The hidden pointer appears only above 16 bytes.

Exercise 14.6 (Stretch): Design and defend. Propose a calling convention where all registers are callee-saved. What would be good, and what would be bad? For what kind of program might it win? What a strong answer includes: leaf functions would pay to save what they use, even when never needed; deep call chains would be cheap for the caller; a program of many small leaf functions would lose; one with long-running functions and few calls could win.

Chapter 15. The frame: prologue, epilogue, alignment and unwinding

In this chapter: You will learn what every function does at its start and end, why the stack must be aligned at a call, and how debuggers walk back through callers. You will see two failures on purpose: a crash from bad alignment, and a backtrace full of nonsense.

You need first: Chapter 14.

The problem first

A function needs a private place for its local variables and its saved registers. It must put that place on the stack, in a way that cannot collide with its caller's or its callee's. It must also leave behind enough information that a debugger can find the caller later. The shape that does all this is called a stack frame.

The model (the "what")

A function that makes calls (a non-leaf function) typically does this:

• Prologue (at the start): save what must be saved (the old frame pointer, the return address on ARM64, any callee-saved registers it will use), and reserve space for locals.
• Body: do the work.
• Epilogue (at the end): undo the prologue in reverse order, then return.

Here is the same small function on both machines, real gcc -O1 output with the frame pointer kept (-fno-omit-frame-pointer):

extern long g(long);
long h(long x) { long y = g(x) + 1; return y * 2; }

# x86-64
h:
    push    rbp                 # save the caller's frame pointer
    mov     rbp, rsp            # rbp now marks the base of this frame
    call    g@PLT               # g(x): rdi is already x
    lea     rax, 2[rax+rax]     # (g + 1) * 2, in one lea
    pop     rbp                 # restore the caller's frame pointer
    ret

// ARM64
h:
    stp     x29, x30, [sp, -16]!    // save frame pointer AND return address, in one pair
    mov     x29, sp                 // x29 marks the base of this frame
    bl      g
    add     x0, x0, 1
    lsl     x0, x0, 1
    ldp     x29, x30, [sp], 16      // restore both
    ret

Read them side by side. The shapes match. On x86-64 call already stored the return address, so only rbp is pushed. On ARM64 bl put the return address in x30, which the next bl will overwrite, so the function saves both x29 and x30. The pair instruction does it in one step.

The frame pointer (rbp or x29) is a register that points at a known place in the frame. Following it, then following the saved one it points to, walks the chain of callers. Compilers often drop it at -O2 to free a register (-fomit-frame-pointer), and use rsp-relative offsets instead. When a profiler wants stack traces cheaply, people build with the frame pointer on.

Leaf functions. A function that calls nothing needs no saved return address. The ARM64 x30 stays put. And on x86-64 something clever is allowed: the red zone. The 128 bytes below rsp are reserved for the running function, and signal handlers will not touch them. So a leaf function can use locals there without even adjusting rsp. Here is a real leaf function, compiled with the default stack protector turned off:

# x86-64: leaf function with a local array, gcc -O1
leaf:
    mov     QWORD PTR -24[rsp], rdi     # a[0] = x      <-- below rsp: the red zone
    add     rdi, 1
    mov     QWORD PTR -16[rsp], rdi     # a[1] = x + 1
    mov     rax, QWORD PTR -24[rsp]
    mov     rdx, QWORD PTR -16[rsp]
    add     rax, rdx
    ret

No sub rsp. The locals live at negative offsets. (Operating system kernels turn the red zone off, because an interrupt can arrive at any time and would use that memory. Windows x64 has no red zone either. Apple's ARM64 ABI has one of 128 bytes.)

With the default Ubuntu compiler flags, the same function looks different. The compiler adds a stack protector: it plants a secret value (a "canary") just above the locals, and checks it before returning:

leaf:
    sub     rsp, 40
    mov     rax, QWORD PTR fs:40            # load the canary from thread-local storage
    mov     QWORD PTR 24[rsp], rax          # place it above the locals
    ...
    mov     rdx, QWORD PTR 24[rsp]
    sub     rdx, QWORD PTR fs:40            # is it unchanged?
    jne     .L4                             # no: something overwrote it
    add     rsp, 40
    ret
.L4:
    call    __stack_chk_fail@PLT            # abort the program

If a buffer overflow wrote past the array, it would crush the canary before reaching the return address, and the check catches it. When you read real distro binaries, you will see fs:0x28 (that is 40 in hex) all the time. Now you know what it is.

Alignment. The ABI says the stack pointer must be a multiple of 16 at the moment of a call. That means that on entry to a function, after call has pushed 8 bytes, rsp is 8 more than a multiple of 16. I measured it: in a small test program, rsp mod 16 was 0 in _start just before the call, and 8 at the first instruction of the called function. That is why the example in Chapter 14 had sub rsp, 8 and why many prologues push one extra register. It is padding to bring the stack back to a multiple of 16 before the next call.

Why does alignment matter? Some instructions require it. movaps stores 16 bytes and only works at a 16-byte aligned address. A compiler uses it freely for locals, expecting the ABI to have aligned the stack. I tested what happens if you break the rule:

    movups  xmmword ptr [rsp+8], xmm0     # unaligned store: works
    movaps  xmmword ptr [rsp+8], xmm0     # aligned-only store at a bad address

The first ran. The second crashed with SIGSEGV (status 139), from a general-protection fault. This is a famous failure: a function works for years, then someone calls it from assembly with a misaligned stack, and it dies on a movaps deep inside printf. On ARM64 the rule is stricter: sp must be 16-aligned whenever it is used for a memory access, and the hardware can check it.

Unwinding. When you type bt in a debugger, or when an exception propagates, the runtime has to walk backward through the callers. With a frame-pointer chain, that is easy. Without one, the runtime needs a table that says, for every instruction address, "here is how big the frame is at this point." That table is CFI (call frame information), written by the compiler as .cfi_ directives and stored in the .eh_frame section. Hand-written assembly has none unless you write it. Let's see what that costs. Here is the factorial function (Chapter 16 explains it), hand-written with no unwinding information. I stopped it at the base case and asked gdb for a backtrace:

#0  0x0000000000401015 in base ()
#1  0x000000000040100f in fact ()
#2  0x0000000000000002 in ?? ()
#3  0x000000000040100f in fact ()
#4  0x0000000000000003 in ?? ()
#5  0x000000000040100f in fact ()

Look at frames 2 and 4. 0x2 and 0x3 are not addresses. They are the saved values of n that the function pushed. The debugger took them for return addresses, because without CFI it can only guess. Now the same function with CFI directives added:

fact:
    .cfi_startproc
    cmp     rdi, 1
    jle     base
    push    rdi
    .cfi_adjust_cfa_offset 8    # tell the unwinder: the stack just grew by 8
    dec     rdi
    call    fact
    pop     rdi
    .cfi_adjust_cfa_offset -8   # and shrank by 8
    imul    rax, rdi
    ret
base:
    mov     eax, 1
    ret
    .cfi_endproc

Real backtrace after that change:

#0  fact () at fact_cfi.s:18
#1  0x000000000040100f in fact () at fact_cfi.s:12
#2  0x000000000040100f in fact () at fact_cfi.s:12
#3  0x000000000040100f in fact () at fact_cfi.s:12
#4  0x000000000040100f in fact () at fact_cfi.s:12
#5  0x0000000000401027 in _start () at fact_cfi.s:24

Four recursive frames and _start, exactly right. (Assemble with as -g to get the source line numbers.) The lesson: a function with no unwind information is invisible to debuggers, profilers and exception handlers. If you write assembly that others will call, add the .cfi_ directives.

A related gotcha from the same experiments: when I linked a hand-written .s file with gcc, the linker warned missing .note.GNU-stack section implies executable stack. Add this line at the end of every assembly file you link into a normal program, to say that it does not need an executable stack:

    .section .note.GNU-stack,"",@progbits      # x86-64 (on ARM64 write %progbits)

Build it (the "how")

Let's write the standard prologue and epilogue for a non-leaf function that needs a local variable and a callee-saved register. We will follow the contract exactly.

# x86-64: a non-leaf function that keeps one value across a call
# long twice_plus_one(long x) { return g(x) * 2 + x; }   // needs x after the call
twice_plus_one:
    push    rbx                 # we want to use rbx, which is callee-saved: save it
    mov     rbx, rdi            # keep x in rbx. A call will not touch it
    call    g                   # entry rsp was 8 mod 16; push made it 0: aligned for the call
    lea     rax, [rbx+rax*2]    # g(x) * 2 + x
    pop     rbx                 # restore the caller's rbx
    ret

I ran both versions with a g that adds 10, called with 5, and each printed 35 (that is 5 + (5+10)×2).

Check the alignment by counting. On entry rsp is 8 mod 16. After push rbx it is 0 mod 16, so the call is aligned. That one push did two jobs: it saved a register and fixed the alignment. A compiler arranges exactly this, and when you see an "extra" push in a prologue, this is often why.

On ARM64 the same function saves x30 (for the bl) and x19 (our callee-saved register), as a pair, which also keeps sp aligned:

// ARM64
twice_plus_one:
    stp     x29, x30, [sp, #-32]!   // 32 bytes keeps sp a multiple of 16
    mov     x29, sp
    str     x19, [sp, #16]          // save callee-saved x19
    mov     x19, x0                 // keep x in x19
    bl      g
    add     x0, x19, x0, lsl 1      // x + g(x)*2
    ldr     x19, [sp, #16]
    ldp     x29, x30, [sp], #32
    ret

Why it is this way (the "why")

Why 16-byte alignment? The CPU's widest common vector register is 16 bytes (and wider ones want more). A stack that is always aligned means locals can be accessed with fast aligned instructions and without a check. The ABI pays a small padding cost to make that safe for everyone.

Why have a frame pointer at all, if rsp can be used? Because rsp moves as you push and pop, so offsets change within a function. A frame pointer stays still, so locals have fixed offsets, and debuggers can walk the chain without tables. The cost is one register. Both are reasonable. Some builds keep it for easier profiling.

Why does the unwind table exist? Because the chain is not always there. Exceptions (C++, Rust panics) must unwind through frames that were compiled without a frame pointer, and the table says how to do it without running any code.

What would be better? A design where hardware keeps a separate stack of return addresses only (a shadow stack) would remove a whole class of attacks. Newer chips have this (Intel's CET shadow stack, ARM's pointer authentication). Chapter 17 shows the extra instructions you will see for it.

Common mistakes

• Misaligned stack at a call. Count the bytes: on entry it is 8 off.
• Writing a prologue and forgetting the epilogue (or the reverse), so rsp is wrong at ret.
• Using the red zone in a non-leaf function. A call overwrites it.
• Using the red zone in kernel code. It is not safe there.
• Hand-written functions with no CFI. Debuggers and profilers will show nonsense.
• Forgetting .note.GNU-stack in assembly linked with gcc.

Say it simply

A function sets up a frame at its start and tears it down at its end, saving whatever the contract requires. The stack must be 16-byte aligned at every call, which means 8 off on function entry, and a missing push or pad is a common bug. Leaf functions on x86-64 may use a 128-byte red zone below rsp. Debuggers walk back through callers using frame pointers or unwind tables, and hand-written assembly needs .cfi_ directives to be visible to them.

Check yourself

Exercise 15.1 (Warm-up): Count by hand. A function is entered with rsp = 0x7ffe0008. It does push rbp, push rbx, and sub rsp, 24. What is rsp at the next call? Is it aligned? A correct result: 0x7ffe0008 - 0x28 = 0x7ffdffe0. It is a multiple of 16 (it ends in 0), so the call is aligned.

Exercise 15.2 (Warm-up): Explain. In five sentences, explain what the stack protector canary does. Use an analogy and say where it breaks. What a strong answer includes: a secret value placed between locals and the return address; checked before return; an overflow that reaches the return address must cross it; analogy: a tripwire in front of a door; where it breaks: an attacker who can read the canary first, or who writes only specific bytes, can step over it.

Exercise 15.3 (Core): Break it. In a program with a call from _start, make the called function use movaps on a local at [rsp] without fixing alignment. Observe the crash. Then fix it by adding one push or sub rsp, 8. A correct result: it crashes with SIGSEGV until rsp is a multiple of 16 at the movaps. Say how you computed the fix.

Exercise 15.4 (Core): Implement. Write twice_plus_one on both machines and a test g that returns its argument plus 10. Call it from _start with 5 and exit with the result. Done when: the exit status is 5 + (5+10)*2 = 35, you printed rsp at the call in gdb and showed it is a multiple of 16, and the ARM64 version restores x19 before returning.

Exercise 15.5 (Core): Predict, then check. Compile the same non-leaf function with -O0, -O1 and -O2, with and without -fno-omit-frame-pointer. Predict which versions use rbp/x29 as a frame pointer. Check, and count the prologue instructions. A correct result: -O0 always keeps it; -O2 drops it unless you ask. Write down the instruction counts.

Exercise 15.6 (Stretch): Design and defend. A separate shadow stack stores only return addresses. Give two things it protects against, and one thing it does not. What a strong answer includes: protects return-address overwrite (stack smashing) and return-oriented programming; does not protect against corruption of data, function pointers, or logic bugs; has a cost (a second stack, a check on each return).

Chapter 16. Writing real functions by hand

In this chapter: You will write four real functions on both machines: one the compiler can call, a number printer, a recursive function, and an iterative one. You will also break the contract on purpose and watch what happens. By the end you will have a print_u64 that we reuse in later parts.

You need first: Chapters 14 and 15.

The problem first

Reading about conventions is not the same as obeying them. The only way to be sure you understand a rule is to write code that depends on it and see it work, then break it and see it fail.

The model (the "what")

A function you write by hand has to do four things: read its arguments from the right places, keep the callee-saved registers safe, keep the stack aligned, and leave its result in the return register. Here are the four functions. All of the output below was produced on this guidebook's machine (the ARM64 programs under qemu-user).

Function 1: sum3, called from C

Here is the smallest useful one: add three numbers. It is a leaf function, so it needs no frame.

# sum3.s -- x86-64
    .intel_syntax noprefix
    .global sum3
    .type sum3, @function
sum3:                           # long sum3(long a, long b, long c)
    lea     rax, [rdi+rsi]      # a + b
    add     rax, rdx            # + c
    ret
    .section .note.GNU-stack,"",@progbits

// sum3.s -- ARM64
    .global sum3
    .type sum3, %function
sum3:
    add     x0, x0, x1
    add     x0, x0, x2
    ret
    .section .note.GNU-stack,"",%progbits

/* main.c */
#include <stdio.h>
extern long sum3(long, long, long);
int main(void) { printf("sum3(2,3,4) = %ld\n", sum3(2, 3, 4)); return 0; }

Build and run: gcc -o m3 main.c sum3.s && ./m3 on x86-64, and aarch64-linux-gnu-gcc -static -o m3a main.c sum3.s && qemu-aarch64 ./m3a for ARM64. Both printed sum3(2,3,4) = 9. C found your function by its name, passed the arguments where the ABI says, and read the answer from rax or x0. That is the whole contract working.

Function 2: print_u64, a number printer

We need to print numbers to test things from here on. The idea: divide by 10 again and again. Each remainder is a digit, and they come out last digit first, so we fill a buffer from the end backward.

# x86-64: print_u64(rdi = value). Prints decimal and a newline. A leaf function.
print_u64:
    sub     rsp, 40              # entry rsp is 8 mod 16, so this leaves it 16-aligned
    lea     rsi, [rsp+32]        # rsi = one past the end of a 32-byte buffer
    mov     byte ptr [rsi-1], 10 # the newline goes last
    dec     rsi
    mov     rax, rdi             # the number
    mov     ecx, 10
.digit:
    xor     edx, edx             # div uses rdx:rax, so rdx must be zero first
    div     rcx                  # rax = rax / 10, rdx = rax % 10
    add     dl, 48               # remainder -> ASCII digit
    dec     rsi
    mov     [rsi], dl
    test    rax, rax
    jnz     .digit               # do-while: the value 0 prints "0"
    lea     rdx, [rsp+32]
    sub     rdx, rsi             # length = end - start
    mov     edi, 1
    mov     eax, 1
    syscall                      # write(1, rsi, length)
    add     rsp, 40
    ret

// ARM64: print_u64(x0 = value). A leaf function.
print_u64:
    sub     sp, sp, #48          // keep sp 16-aligned
    add     x1, sp, #32          // one past the end of the buffer
    mov     w2, #10
    strb    w2, [x1, #-1]!       // newline; the pre-index moves x1 back by one
    mov     x3, #10
digit:
    udiv    x4, x0, x3           // x4 = x0 / 10
    msub    x5, x4, x3, x0       // x5 = x0 - x4*10  (the remainder)
    add     w5, w5, #48
    strb    w5, [x1, #-1]!
    mov     x0, x4
    cbnz    x0, digit
    add     x2, sp, #32
    sub     x2, x2, x1           // length
    mov     x0, #1               // x1 already points at the first digit
    mov     x8, #64
    svc     #0
    add     sp, sp, #48
    ret