# CS 211 - Lecture 11 - Instruction Sets

Bernhard Firner

2026-02-25

---

## Assembly

* We need to understand some of it
  * To better understand C
  * To better understand your hardware

---

## Operators and Operands

* Assembly is made of simple instructions
  * add, sub, mov, push
* Each operator can have up to two operands
  * E.g. `addq %rax %rdi` will add %rax to %rdi and the result stays in %rdi
  * The **q** suffix means "quad word", or $4\times2=8$ bytes

---

## Suffixes

* Suffixies specify what values an operator works on
  * **addq** adds two quad words, **addl** adds two longs
* These aren't really types, just numbers of bytes

---

## Suffix Lengths

* **b**: byte
* **w**: word (2 bytes)
* **l**: long/double word (4 bytes)
* **q**: quad word (8 bytes)

---

## Registers

* Registers can be used at different sizes
* Each register is 64 bits in x86-64
  * But they can be used with partial sizes
* **rax** is the full size of register **ax**, **eax** is a double word, **ax** is a word
  * **ah** and **al** are the high and low bytes of the last word

---

## General Purpose Registers

* In x86-64, there are 16 registers, each 64 bits
  * But can be treated as 32, 16, or 8
  * qword, dword, word, byte
* Just change the name
  * rax, eax, ax
  * ah, al for the high and low bytes

</div>
<div class="col">
<img style="width: 70%" class="r-stretch" src="./figures/IntelFigure3-5_64-AlternativeRegisterNames.png" />

</div>
</div>

---

## Registers & Memory

---

## Immediate Addressing

* We can use constant values with registers
  * e.g. `$5` refers to the constant value 5
* This sets the destination to 5
  * `movq $5 dst`
* Immediate values can be a source, but not a destination

---

## Register Addressing

* More common to work with register values
* `movq %rax, %rdi`
  * Moves the value in rax to the value in rdi
* A register can be either a source or a destination of an operand

---

## Direct/Absolute

* These are pointer equivalents, and how we access non-register memory
* **Absolute** (or **direct**) addressing uses a hard-coded address
  * `movq 0x40abcd, dst`
  * Would move `memory[0x40abcd]` to destination
  * Notice that there is no dollar sign

---

## Indirect

* **Indirect** addressing gets the address from a register
  * `moveq (%rax), dst`
    * Would move `memory[%rax]` to destination
* The parenthesis indicate that we are using a pointer

---

## Addressing Modes

* There are several ways to do indirect addressing
  * `displacement(base, index, scale)`
* Arrays are very common, so syntax supports displacements (in bytes)
  * `8(%rax)` is `memory[%rax + 8]`
  * like `char_ptr[8]`

---

## Scaling

* This is how we access arrays with offsets in C
* But most displacement has a scaling factor, e.g. ints have a scale of 4 bytes
  * `8(%rax, %rcx, 4)` is `memory[%rax + 8 + 4×%rcx]`
* Can skip the displacement and keep scaling for familiar array access
  * `(%rax, %rcx, 4)` is `memory[%rax + 4×%rcx]`
* Scaling must be 1, 2, 4, or 8

---

## Assembly Vs C

* C code is turned into assembly
* That means, conceptually, it is possible to mix the two
  * And gcc allows us to do this
* This is an advantage of C and C++

---

## Using the Stack

```c
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char** argv) {
    if (argc < 2) {
        printf("This program requires a data file.\n");
        return 1;
    }

// Open datafile for reading.
    FILE* datafile = fopen(argv[1], "r");
    if (datafile == NULL) {
        printf("Error opening file.\n");
        return 2;
    }

// We don't need to get complicated with sscanf
    // Just read in one character at a time
    int input = fgetc(datafile);
    int pushed = 0;
    // EOF is defined in stdio.h, means "End Of File"
    while (input != EOF) {
        // The double %% indicates a register, a single % means a user-provided variable.
        __asm__(
            "push %0"
            : // No outputs
            : "r" ((long long)input) // Input value. "push" requires an 8 byte value
            :
        );
        // This is rewritten into assembly.
        // push %0 tells the compiler that we are going to give it an input argument
        // The : marks a section for outputs, which are aren't using
        // The next : marks inputs, which we are using.
        // The input variable is loaded into any register "r"
        ++pushed;

// For the next loop iteration
        input = fgetc(datafile);
    }

// Finished with the file
    fclose(datafile);

// Reverse
    long long out = 0;
    while (pushed > 0) {
        __asm__(
            "pop %0"
            : "=r" (out) // Output into the out variable.
            :
            :
        );
        putchar(out);
        --pushed;
    }
    putchar('\n');

return 0;
}
```

---

## Converted Assembly

```asm
	.file	"blub.c"
	.text
	.section	.rodata
	.align 8
.LC0:
	.string	"This program requires a data file."
.LC1:
	.string	"r"
.LC2:
	.string	"Error opening file."
	.text
	.globl	main
	.type	main, @function
main:
.LFB6:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$48, %rsp
	movl	%edi, -36(%rbp)
	movq	%rsi, -48(%rbp)
	cmpl	$1, -36(%rbp)
	jg	.L2
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	call	puts@PLT
	movl	$1, %eax
	jmp	.L3
.L2:
	movq	-48(%rbp), %rax
	addq	$8, %rax
	movq	(%rax), %rax
	leaq	.LC1(%rip), %rdx
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	fopen@PLT
	movq	%rax, -16(%rbp)
	cmpq	$0, -16(%rbp)
	jne	.L4
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	call	puts@PLT
	movl	$2, %eax
	jmp	.L3
.L4:
	movq	-16(%rbp), %rax
	movq	%rax, %rdi
	call	fgetc@PLT
	movl	%eax, -24(%rbp)
	movl	$0, -20(%rbp)
	jmp	.L5
.L6:
	movl	-24(%rbp), %eax
	cltq
#APP
# 24 "blub.c" 1
	push %rax
# 0 "" 2
#NO_APP
	addl	$1, -20(%rbp)
	movq	-16(%rbp), %rax
	movq	%rax, %rdi
	call	fgetc@PLT
	movl	%eax, -24(%rbp)
.L5:
	cmpl	$-1, -24(%rbp)
	jne	.L6
	movq	-16(%rbp), %rax
	movq	%rax, %rdi
	call	fclose@PLT
	movq	$0, -8(%rbp)
	jmp	.L7
.L8:
#APP
# 47 "blub.c" 1
	pop %rax
# 0 "" 2
#NO_APP
	movq	%rax, -8(%rbp)
	movq	-8(%rbp), %rax
	movl	%eax, %edi
	call	putchar@PLT
	subl	$1, -20(%rbp)
.L7:
	cmpl	$0, -20(%rbp)
	jg	.L8
	movl	$10, %edi
	call	putchar@PLT
	movl	$0, %eax
.L3:
	leave
	ret
.LFE6:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

---

## Loop

<pre>
    int input = fgetc(datafile);
    int pushed = 0;
    while (input != EOF) {
        __asm__(
            "push %0"
            : // No outputs
            : "r" ((long long)input) // Input value. "push" requires an 8 byte value
            :
        );
        ++pushed;

// For the next loop iteration
        input = fgetc(datafile);
    }
</pre>

* `input` at -24(%rbp)
* `pushed` at -20(%rbp)
* `datafile` at -16(%rbp)

</div>
<div class="col">

```asm
	call	fgetc@PLT
	movl	%eax, -24(%rbp)
	movl	$0, -20(%rbp)
	jmp	.L5
.L6:
	movl	-24(%rbp), %eax
	cltq
#APP
# 24 "blub.c" 1
	push %rax
# 0 "" 2
#NO_APP
	addl	$1, -20(%rbp)
	movq	-16(%rbp), %rax
	movq	%rax, %rdi
	call	fgetc@PLT
	movl	%eax, -24(%rbp)
.L5:
	cmpl	$-1, -24(%rbp)
	jne	.L6
```

</div>
</div>

---

## Printing Loop

<pre>
    // Finished with the file
    fclose(datafile);

// Reverse
    long long out = 0;
    while (pushed > 0) {
        __asm__(
            "pop %0"
            : "=r" (out) // Output into the out variable.
            :
            :
        );
        putchar(out);
        --pushed;
    }
    putchar('\n');
</pre>

* `pushed` at -20(%rbp)
* `datafile` at -16(%rbp)
* `out` at -8(%rbp)
* The value of '\n' is 10

</div>

```asm
	movq	-16(%rbp), %rax
	movq	%rax, %rdi
	call	fclose@PLT
	movq	$0, -8(%rbp)
	jmp	.L7
.L8:
#APP
# 47 "blub.c" 1
	pop %rax
# 0 "" 2
#NO_APP
	movq	%rax, -8(%rbp)
	movq	-8(%rbp), %rax
	movl	%eax, %edi
	call	putchar@PLT
	subl	$1, -20(%rbp)
.L7:
	cmpl	$0, -20(%rbp)
	jg	.L8
	movl	$10, %edi
	call	putchar@PLT
```

</div>
</div>

---

## Checking Status

```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(int argc, char** argv) {
    if (argc < 3) {
        printf("Please provide 2 numbers as inputs.\n");
        return 1;
    }

int a = atoi(argv[1]);
    int b = atoi(argv[2]);

int c = a + b;
    // jo is jump if overflow bit is set
    asm("jo OVERFLOW");
    asm("jmp NOOVERFLOW");
    asm("OVERFLOW:");
    // We jump over this line if no overflow is detected.
    printf("overflow!\n");
    asm("NOOVERFLOW:");
    return 0;
}
```

---

## Detecting Overflow

* Status registers allow us to check for special conditions

<pre>
$ ./a.out 2147483648 2147483647
$ ./a.out 2147483648 2147483648
overflow!
</pre>

---

## Status Registers

---

## Complicated! Ugly! Confusing!

* Focus on the goal
  * Every assembly instruction is translated into a number
  * That number is given to your hardware, making it do something
* You can compile your C code with comments, making it easier to inspect
<pre>
gcc overflow.c -g -c -o overflow.o
objdump -d -M att -S overflow.o
</pre>

---

## Objdump

```
overflow.o:     file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <main>:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int main(int argc, char** argv) {
   0:	f3 0f 1e fa          	endbr64
   4:	55                   	push   %rbp
   5:	48 89 e5             	mov    %rsp,%rbp
   8:	48 83 ec 20          	sub    $0x20,%rsp
   c:	89 7d ec             	mov    %edi,-0x14(%rbp)
   f:	48 89 75 e0          	mov    %rsi,-0x20(%rbp)
    if (argc < 3) {
  13:	83 7d ec 02          	cmpl   $0x2,-0x14(%rbp)
  17:	7f 16                	jg     2f <main+0x2f>
        printf("Please provide 2 numbers as inputs.\n");
  19:	48 8d 05 00 00 00 00 	lea    0x0(%rip),%rax        # 20 <main+0x20>
  20:	48 89 c7             	mov    %rax,%rdi
  23:	e8 00 00 00 00       	call   28 <main+0x28>
        return 1;
  28:	b8 01 00 00 00       	mov    $0x1,%eax
  2d:	eb 4f                	jmp    7e <NOOVERFLOW+0x5>
    }

int a = atoi(argv[1]);
  2f:	48 8b 45 e0          	mov    -0x20(%rbp),%rax
  33:	48 83 c0 08          	add    $0x8,%rax
  37:	48 8b 00             	mov    (%rax),%rax
  3a:	48 89 c7             	mov    %rax,%rdi
  3d:	e8 00 00 00 00       	call   42 <main+0x42>
  42:	89 45 f4             	mov    %eax,-0xc(%rbp)
    int b = atoi(argv[2]);
  45:	48 8b 45 e0          	mov    -0x20(%rbp),%rax
  49:	48 83 c0 10          	add    $0x10,%rax
  4d:	48 8b 00             	mov    (%rax),%rax
  50:	48 89 c7             	mov    %rax,%rdi
  53:	e8 00 00 00 00       	call   58 <main+0x58>
  58:	89 45 f8             	mov    %eax,-0x8(%rbp)

int c = a + b;
  5b:	8b 55 f4             	mov    -0xc(%rbp),%edx
  5e:	8b 45 f8             	mov    -0x8(%rbp),%eax
  61:	01 d0                	add    %edx,%eax
  63:	89 45 fc             	mov    %eax,-0x4(%rbp)
    // jo is jump if overflow bit is set
    asm("jo OVERFLOW");
  66:	70 02                	jo     6a <OVERFLOW>
    asm("jmp NOOVERFLOW");
  68:	eb 0f                	jmp    79 <NOOVERFLOW>

000000000000006a <OVERFLOW>:
    asm("OVERFLOW:");
    // We jump over this line if no overflow is detected.
    printf("overflow!\n");
  6a:	48 8d 05 00 00 00 00 	lea    0x0(%rip),%rax        # 71 <OVERFLOW+0x7>
  71:	48 89 c7             	mov    %rax,%rdi
  74:	e8 00 00 00 00       	call   79 <NOOVERFLOW>

0000000000000079 <NOOVERFLOW>:
    asm("NOOVERFLOW:");
    return 0;
  79:	b8 00 00 00 00       	mov    $0x0,%eax
}
  7e:	c9                   	leave
  7f:	c3                   	ret
```

---

## Common Instructions

* Math
* Binary logic
* Comparisons
* Setting the instruction pointer

---

## Mov

* The mov instruction is very common
* Load a value into a destination

---

## Example Minimal Program

* The value in `%eax` is returned from main
  * Edit the constant used in the `movl` instruction
  * Compile the program, run it, and run `echo $?` to see the number

```asm
	.file	"asm.c"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$0, %eax
	popq	%rbp
	ret
.LFE0:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

---

## Hex Support

* Immediate addressing supports hex

```asm
main:
.LFB0:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$0x44, %eax
	popq	%rbp
	ret
```

---

## Binary Support

* Immediate addressing also support binary

```asm
main:
.LFB0:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
	movl	$0b11, %eax
	popq	%rbp
	ret
```

---

## Math instructions

* **add** & **sub**: These add and subtract
* **mul**: Multiplication
* **div**: Division
* Multiplication and division use a single operation, and store the result in `%rax`
  * The remainder of multiplication is left in `%rdx`
  * They looked like different operations in C, but they aren't in assembly

---

## Example

```asm
	.file	"asm.c"
	.text
	.globl	main
	.type	main, @function
main:
.LFB0:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
# Move 10 in eax
	movl	$10, %eax
# Move 20 in ebx
	movl	$20, %ebx
# Move add ebx into eax (eax = 30)
	addl	%ebx, %eax
# Subtract 3 from eax (eax = 27)
	subl	$3, %eax
# Move 3 into ebx
	movl	$3, %ebx
# We want to divide, but this is going to use all 64 bits
# So we need to sign extend the value in eax
# cqto is the mnemonic for "convert quad to oct"
	cqto
# Finally we divide.
# This stores the quotient in %rbx and remainder in %rdx.
	idivl	%ebx
# ebx is 27/3 = 9
# Multiplication likewise automatically uses whatever is in rbx
	movl	$4, %ebx
# 4*9 = 36, which is the return value of main.
	imull	%ebx
	popq	%rbp
	ret
.LFE0:
	.size	main, .-main
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

---

## lea

* **lea** is "load effective address"
* It calculates an address, as in indirect memory addressing, and stores it in a register
  * This is a trick to doing addition and multiplication in a single instruction!
  * But the scaling value must be 1, 2, 4, or 8

```asm
main:
.LFB0:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
# Move 10 in eax
	movl	$10, %eax
# Move 3 in ebx
	movl	$3, %ebx
# 5 + eax + 4*ebx = 15 + 12 = 27
    leal	5(%eax, %ebx, 4), %eax
	popq	%rbp
	ret
```

---

## Comparisons

* There are multiple comparisons operators, all beginning with "cmp"
* The way comparisons actually work is by subtracting the operators
* Flags in the status register are then set, and used for branching
  * As we saw with the `jo` example (jump if overflow)
  * There are lots of jump: `jg` (jump if greater), `jne` jump if not equal, etc

---

## Function Calls

* Function calls is another type of execution jumping
  * But now we need to worry about stack and register state
  * What if the function we call messes up our registers?
  * How do we get back?

---

## Function Calls

* The `call` instruction saves the instruction pointer (`%rip` or `%eip`) onto the stack
  * So our return address is on the stack, that's how we get back
* The `ret` function returns to the address on the top of the stack
* But what if the function used stack memory?

---

## Using Stack Memory

* Look at any function call in assembly
  * You'll see it begin with two operations with the stack pointers
* First, save the current base pointer onto the stack
  * This puts it on top of the return address
* Then copy the current top of the stack over the base pointer

```
	pushq	%rbp
	movq	%rsp, %rbp
```

---

## Memory Example

```C
void use_stack() {
    int bob[10];
    return;
}

int main(void) {
    return 0;
}
```

---

## Memory Example

* Memory is then claimed by subtracting a number from `%ebp` or `%rbp`
  * ebp or rbp depends on if memory is 32 or 64 bits
* Here we allocate 48 bytes on the stack for our 10 ints
  * 40 for the ints, 8 for the pointer (since we have an array variable)

```asm
use_stack:
.LFB0:
	endbr64
	pushq	%rbp
	movq	%rsp, %rbp
	subq	$48, %rsp
```

---

## Cleaning Up

* We need to give up the memory
  * So we simply reset %rbp and %rsp to their prior states

```asm
	movq	%rbp, %rsp
	popq	%rbp
```

* Those are done automatically by the `leave` function

---

## What We've Learned

* Now you see that instructions are also just numbers in memory
* And the stack is just a pile of memory that every function uses
  * Stores everything from local variables to return addresses
  * Anything but dynamically allocated memory
* But what are instructions *really*? How does a number do addition?

---

## What is ADD?

* What is an instruction? What does Intel say?

</div>
</div>

---

## What is ADD?

* (Note: operand order is swapped for Intel syntax vs ATT)

</div>
</div>

---

## What is ADD?

* Look at the three additions from the objdump from early in the lecture

* Notice that the immediate values (0x8 and 0x10) are in the instructions themselves
  * In lines 33 and 49, `%rax` had a pointer value, so these are 64-bit (addq)
  * 48 is 0b01001000, indicating that 64 bit values should be used
    * See [https://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix](https://wiki.osdev.org/X86-64_Instruction_Encoding#REX_prefix)
* Documentation says that instruction is REX.W + 83 for immediate 64 bit addition
* 01 indicates register to register 8, 16, or 32 bit addition

-v-

## Objdump

```
overflow.o:     file format elf64-x86-64

Disassembly of section .text:

0000000000000000 <main>:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

0000000000000079 <NOOVERFLOW>:
    asm("NOOVERFLOW:");
    return 0;
  79:	b8 00 00 00 00       	mov    $0x0,%eax
}
  7e:	c9                   	leave
  7f:	c3                   	ret
```

---

## What is PUSH?

---

## What is PUSH?

* `rax` is register 0
* So opcode 50 is PUSH into register 0
* Notice that the very common operation is a single byte

---

## Who Wants This?

* Who would want to read this?
  * Not a human!
* These opcodes are just numbers
* They becomes 0s and 1s on wires, which go into your CPU
  * And that's where the magic of computer architecture takes over!

---

## The Life of an Instruction

* You run a program. Now what?
* It is converted into binary and loaded into memory
* Where does it start?
  * At main
* What does that mean?
  * The `instruction pointer` is set to the address of main

---

## Instruction Loading (idyllic)

* Instructions are loaded one at a time and executed
* Each clock cycle, we increment the `instruction pointer` by one
  * (aside: some architectures call the `instruction pointer` the `program counter`)
* The instruct at the location is loaded and causes something to happen

</div>
<div class="col">

</div>
</div>

---

## Next Time

* We'll learn about the part where "Stuff Happens"
* That's computer architecture!
  * Where do these signals go?
  * And how do they turn into results?