Lecture 2: Assembly

Introduction

Today, we’ll start talking about the 64-bit x86 assembly language – the language of 64-bit x86 processors
We will also see a bit of C code – you’ll get to learn C by example
The plan for today is to learn:
1. Number bases recap
2. The CPU from a programmer’s perspective
3. How to load data into the CPU
4. Arithmetic
5. How to make decisions

Aside: A little bit about numbers and number bases

We will be working with numbers quite a bit and in different roles: counting, addresses, offsets, switches, etc.
For simplicity, we will (mostly) avoid floating point and talk about integers
In majority of cultures (feel free to let me know if I’m wrong), we humans use the decimal system
- We have 10 digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
- Positional system - right-to-left - least to most significant digit: 1s, 10s, 100s, 1000s, …, or: 10⁰, 10¹, 10², 10³, …
- When counting up by 1, we increment the least significant digit until it reaches 9, then switch to 0 and increment the next digit
- Example: 9213
- Any decimal number with n + 1 digits can be broken down as: a_n × 10ⁿ + a_n − 1 × 10^n − 1 + a_n − 2 × 10^n − 2 + ... + a₀ × 10⁰
Computers understand binary: everything is either 0 or 1 (off or on)
Also a positional system, but only 2 digits: 0 and 1
Example: 111101₂
Any binary number is broken down into digits similarly to decimal, but the base is 2: a_n × 2ⁿ + a_n − 1 × 2^n − 1 + a_n − 2 × 2^n − 2 + ... + a₀ × 2⁰
Binary: easy for computer, but impractical
Solution? converting between decimal and binary? Too cumbersome
Solution! Use bases that are easier to convert: octal or hexadecimal
Octal: 8 digits - 0-7
For example 371₈
Most useful for us: hexadecimal
Digits: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F (can be also lower case)
Because 16 = 2⁴, each digit corresponds to 4 binary digits so they map nicely

E.g., 88E5 = 1000100011100101

1 0 0 0    1 0 0 0    1 1 1 0    0 1 0 1

8+0+0+0    8+0+0+0    8+4+2+0    0+4+0+1

   8          8          E          5

What’s the job of a CPU?

What does a CPU do?
Simplistically: It basically just sits there doing the following over and over again:
1. Read the next instruction
2. Analyze it
3. Execute it
4. Go to 1
This is a simplified fetch-decode-execute cycle (we might look at it in more detail later)
Note, executing an instruction might change which instruction we read the next
Just like anything in the computer, instructions are just sequences of 0s and 1s
Really, everything could be simply expressed on a punch card (hole for 1, no hole for 0)
Writing instructions as 0s and 1s is a terrible use of human time
Programmers created mnemonics for instructions - these mnemonics form the assembly language
For some time, people wrote programs exclusively using these mnemonics
Nowadays, we generally prefer higher level languages
The instructions that a particular CPU understand is called an instruction set, which forms part of the instruction set architecture (ISA)
An ISA is a model of the CPU from the programmer’s perspective - it describes how to control the CPU from software

x86_64

The ISA that we are using in this course usually denoted as x86_64, which means it’s the 64-bit variant of the x86 architecture
It traces its roots to early Intel processors from the 70s, starting with 8086 (itself based on 8008, which was based on 4004)
8008 was an 8-bit processor, 8086 was a 16 bit processor
For those CPUs it meant that the processor was literally connected to the memory with 8 or 16 wires (8086 actually used 20 wires to communicate with the memory, so addressing was 20 bits)
Development continued with 80286 and 80386, which was the first 32-bit processor
AMD was the first manufacturer to offer a 64bit processor based on the x86 design - the Athlon64
Note, that all x86 processors are backward compatible with 8086 - what ran on 8086 can still run on modern CPUs

Where does assembly fit in today?

Recall the compilation pipeline:

-- hello.c --> | Preprocessor | -- hello.i --> | Compiler | -- hello.s --> | Assembler | -- hello.o --> | Linker | -- hello -->

The C compiler processes a C program and outputs a sequence of instructions
The next stage is the assembler – a program which translates instructions expressed as mnemonics into machine code (= sequences of 0s and 1s)
An assembler is a simple program and is bad at giving good feedback (as you will find out)

Aside

Other programming languages you might use have a similar pipeline - even Python and Java
Both translate their source code into something called bytecode – it is something like a “higher-level” machine code for a virtual machine - an idealized computer implemented in software
Google “JVM instructions” or “Python bytecode instructions” (or “Python dis module”)

Programming in Assembly

As mentioned above, we program in assembly by writing down instructions
There are some auxiliary things we can do in an assembly source, but that’s about it
First, how do we represent data?

Data

Our CPU is 64 bit, which means everything we do needs to be somehow expressible in (chunks of) 8, 16, 32 or 64 bit numbers
Recall binary: 64 bits mean that we have 64 0s and 1s
It is most useful to be comfortable with making basic conversions between decimal, binary and hexadecimal (base 16)
Ask questions if examples aren’t clear
The CPU works with the following “data types”:
- byte (suffix b) = 1 byte = 8 bits
- word (suffix w) = 2 bytes = 16 bits
- double word (suffix l) = 4 bytes = 32 bits
- quad word (suffix q) = 8 bytes = 64 bits
These correspond to the C types: char, short, int and long

Where does it go?

Where do we put the values (data) we want to work with on the CPU?
Memory of course! - but that would be slow!
The CPU offers several registers - these are small slots for storing values up to 64 bits
There are some special-purpose registers, which we won’t be touching directly
There are also 16 general purpose registers - we will use these a lot
They are also 64 bit, but allow us to use “sub registers” of size 32, 16 and 8

Moving data

To move into registers, between registers and between registers and memory, we use the mov instruction:
```
mov Source, Destination
movq Source, Destination
movb Source, Destination
```
The Source and Destination above are what we call operands
There are three kinds:
1. Immediate - e.g., $42 or $0x4F
2. Register - e.g., %rax
3. Memory reference - needs the memory address stored in a register: (%rax)
We’ll talk about the last kind more next time
Example:
```
movq $52, %rax
movq %rax, %rbx
```

Arithmetic

We also have multiple two-operand arithmetic instructions: add, sub, imul, idiv, and, or, xor, etc.
They use the same general form as mov and perform the operation on the two operands and store the result in the Destination
General rule: for an operation OP: Destination = Destination OP Source
E.g., asm addq $3, %rax imul %rax, %rbx
Exercise: 28 - (10 + 3) * 2 - translate to assembly
- Can only do one operation at a time
- Use BODMAS (Brackets, Orders, Division & Multiplication, Addition & Subtraction)
- Compute (10+3) first:
```
movq $10, %rax
movq $3, %rbx     # optional, could just do addq $3, %rax
addq %rbx, %rax   # result will be in rax
```
- Multiply by 2
```
imulq $2, %rax
```
- Subtract from 28
```
movq $28, %rbx
subq %rax, %rbx
```
- Result is now in rbx
There are also unary (single operand) instructions inc, dec, neg, not
The single operand is also the destination

Jumping and Labels

Sometimes we need to jump to another part of code
We use the jmp instruction (unconditional jump)
We jump to an address - in the source expressed as a label

Conditional Branching

To make decisions, we need to be able to jump conditionally
We can compare using the cmp instruction
```
cmp Sub, Min
```
Performs Min - Sub, but discards the result
Sub = subtrahend
Min = minuend
The next instruction is usually one of the following
1. je - jump if equal
2. jne - jump if not equal
3. jg - jump if Min > Sub
4. jge - jump if Min >= Sub
5. jl - jump if Min < Sub
6. jle - jump if Min <= Sub
There are a few more, but these should be enough for us
When programming conditional jumps, always pay attention to how the cmp instruction works - in GNU assembly the sense is reversed
Note: In practice, we will also reverse the condition we jump in - we’ll talk about this in the next lecture

Calling Functions

Functions can be called using the call instruction
Note, we will learn how to write functions next week (today we will write only one function: main)
call takes one operand – the address of the function’s body – most often we will use a symbolic name that represents that address
For example, calling the function printf is as simple as call printf… or is it?
You should ask:
1. Where do arguments go?
2. How does the return value get passed back to the caller?
These questions are answered by the calling conventions - these are defined by the operating system and platform combination
Usually it is a combination of registers and the call stack
For example, the calling conventions for Linux on x86_64 are defined by the System V Application Binary Interface (ABI) for AMD64
Make note of these conventions as they will be important over the next two weeks

SysV ABI x86_64 Calling Conventions

Arguments

The first 6 arguments to any function are passed in the following 6 registers:

Argument	Register
1	`%rdi`
2	`%rsi`
3	`%rdx`
4	`%rcx`
5	`%r8`
6	`%r9`

We shouldn’t need more than 6 arguments
“But… what if my function has more than 6 arguments?” I hear you ask - They go onto the stack (next week’s topic)
Note, that for passing 32-bit, 16-bit, or 8-bit values, use the corresponding lower subregister

Special Case: `printf`, `fprintf`, `scanf`, etc.

Functions like printf, fprintf, etc., are special: they take variable numbers of arguments
Let’s take printf: it takes at least a format string, which can be followed by additional arguments – depending on how many format specifiers are in the format string
Do now: skim through man 3 printf
For this class, calling these functions in assembly involves an additional step: the register %al needs to be set to 0, e.g., using mov $0, %al

Return Value

The return value is passed in the register %rax

Register Saving

The last question we need to answer is: what happens to registers between function calls?
Can we rely on registers staying the same after we call a function?
Remember that a (library) function is a completely independent piece of code
It will most likely need to use some registers to perform whatever it needs to
Shall the function (the callee) save all registers it uses and then restore them before returning?
Shall we (as the caller) save all registers we want preserved somewhere and then restore them after the function returns?
The answer: a mix of both
The ABI distinguishes so-called callee-save and caller-save registers
For callee-save, the function that is being called is responsible for preserving the value in the register (i.e., the caller shouldn’t be able to observe any difference in those registers after the call returns)
For caller-save, also called temporaries, it is the caller that needs to save whatever they want to keep

Callee-save registers

%rbx, %rbp, and %r12–%r15

Caller-save registers

all argument registers (see above), the return value register (%rax), %r10, %r11

These are best used as temporaries - they might “go bad” as soon as you call a function.

Structure of an Assembly File

The assembly programs we will write will have the following general structure:


.global main    # any symbols (e.g., functions) that should be visible 
                # outside this module, need to be declared global

.text           # begin the executable code segment

main:           # start of the main function
  enter $0, $0  # set up the call stack (more next time)

  # code
  # ...
  # code
  # ...
  # code

  leave         # clean up the stack space
  ret           # return from the function

# more functions ...

.data           # beginning of the data segment
                # - this is where global variables are defined

format_string:
  .asciz "Hello, my age is: %d\n"

some_long_integer:
  .quad 42