What’s the goal?
In early January, a friend messaged saying that he was doing Day 1 of Advent of Code in Assembly Code, and it was a really interesting challenge. As someone who has never touched Assembly Code, I naively thought how hard can it be?, and decided to join him.
I’m running this on an ARM Macbook, so this post relates to my experiences with that architecture. Working with an Intel instruction set will vary, but the most of the ideas should be relatively transferrable as I’m not using any complex instructions here.
The challenge boiled down to reading a list of numbers, and counting how many of them are larger than the previous number in the list. For example, in the following example there are 7 numbers that are larger than the previous number:
199 (N/A - no previous measurement)
200 (increased)
208 (increased)
210 (increased)
200 (decreased)
207 (increased)
240 (increased)
269 (increased)
260 (decreased)
263 (increased)
Easy, right? This is a pretty basic problem to solve in most modern programming languages, but without some of the abstractions provided to you by a modern programming language, things are not quite so easy..
The code I ended up writing to solve this and print the answer to stdout can be found on my github
How do you even run an assembly program?
To run an assembly program, like with any other programming language, you need to turn the code that you have written into something that the machine can understand. Whilst assembly is close to direct machine code, its not quite there. In order to run it, we need to pass it through two programs, an assembler, and a linker. Both of these conveniently come with Mac developer tools, and the program names are as and ld respectively.
An assembler’s job is to convert assembly language mnemonics (instructions) into binary machine language, and translate names for memory addresses into numeric addresses.
The end result of the assembler is a binary ‘object’ file, given a .o extension by convention. The memory addresses generated by an assembler are actually offsets, as opposed to absolute locations. Generally, an object file will be linked with several other object files and libraries to produce a program.
The job of a linker is to link together these object files and libraries, by assigning absolute memory locations to everything. The output of this is a binary executable which can be directly run from the command line. In this post, we are only dealing with one assembly file, so there are no other object files or libraries to worry about, however, it does need to link our memory addresses to something that the operating system can understand.
Usage of these two is reasonably simple. I made a small makefile to save on typing, but you would run something like the following in order to generate a binary executable called bin/filename from a source assembly file called filename.s
as -o filename.o filename.s
ld filename -o ./bin/filename -e _start -arch arm64 -L /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/lib -lSystem
Our first assembly program
Lets look at an extremely simple assembly program. The following codeblock is a Hello World program that will print out the string Hello World! when run.
Hello world in assembly
.global _start @ Provide program starting address to linker
helloworld: .ascii "Hello World!\n"
@ Setup the parameters to print hello world
@ and then call Linux to do it.
_start: mov X0, #1 @ 1 = StdOut
adr X1, helloworld @ string to print
mov X2, #13 @ length of our string
mov X16, #4 @ MacOS write system call
svc 0 @ Call linux to output the string
@ Setup the parameters to exit the program
@ and then call Linux to do it.
mov X0, #0 @ Use 0 return code
mov X16, #1 @ Service command code 1 terminates this program
svc 0 @ Call MacOS to terminate the program
There are a few interesting things to note. Starting from the top..
.global _start @ Provide program starting address to linker
helloworld: .ascii "Hello World!\n"
In the above code, the .global directive allows you to mark specific parts of your code to ensure that they are added to the object code (.o file), in order for the linker to find them. In the commands above, this is what allows the linker to use the -e _start flag to understand where to begin the code. In conjunction with the flag in the linker, we are telling the program where it should start.
The second line is pretty self-explanatory, and allows us to easily define the string "Hello World" in ascii. Importantly, we can refer to this from other places in our code so it acts like an immutable variable.
_start: mov X0, #1 @ 1 = StdOut
This is our first real line of code. The very first part, _start, tells the linker that this is the beginning of our program, as mentiond above. We then have our first instruction, mov. Instructions are the building blocks of any assembly language program, and they generally take the form of an instruction followed by two or three parameters. The mov instruction simply moves the thing from the second parameter into the first parameter. In this case, we are moving the number 1 into register X0.
Registers are areas which contain very fast storage inside the processor. They can either hold values, or point to specific memory locations. In my M1 Pro chip, there are 29 general-purpose registers (x0-x28), plus a number of special registers. The only special register that we will be dealing with is sp, or the stack pointer. This is used to point to an area of memory that you are using in your program.
_start: mov X0, #1 @ 1 = StdOut
adr X1, helloworld @ string to print
mov X2, #13 @ length of our string
mov X16, #4 @ MacOS write system call
svc 0 @ Call linux to output the string
The above block of code constitutes a syscall. This is the process of our program interacting with the outside world, ie, the operating system itself. The secret incantation required to perform different types of syscall varies depending on your processor, but essentially requires putting data into the correct registers, then calling the instruction scv 0.
The syscall above is to write to stdout. What we had to do here was to put the correct Mac syscall code into the x16 register, and then you pass the arguments to the syscall into x0 through x2. We can look up the required arguments and the order we need to pass them in by looking at the man page for the write function, using man 2 write, or similar for whichever syscall we are attempting to do.
Reading a file
There are several ways we could have read in our data, for example simply defining it inside our program, or passing it in through stdout. For this challenge, I decided to read the input from a file. To do this, we need to interact with the operating system, ie, use a syscall. There are three steps required as part of reading a file, all of which require different syscalls:
- Open the file in read mode
- Read the contents of the file
- Close the file
As mentioned above, we can use Apple’s documentation, coupled with the man pages to get documentation of how to use these syscalls, and ultimately we end up with the following code in order to open the file and read our data into memory.
Reading from file in assembly
.text
filename: .ascii "/path/to/file"
_start:
@ Open the file to read input
adr x0, filename @ Filename
mov x1, #0 @ Read only
mov x16, #5 @ Open
svc 0 @ Call
mov x19, x0 @ Save file descriptor
@ (non-negative integer == success) to x19
@ Read from file
sub sp, sp, 0x10000 @ Allocate 2^16 bits on the stack
mov x1, sp @ Buffer address (on the stack)
mov x2, 0x10000 @ Buffer size
mov x16, #3 @ Read
svc 0 @ Call
mov x20, x0 @ Returns the amount of bytes read. Store in x20
@ Close file
mov x0, x19 @ Move file descriptor back to x0
mov x16, #6 @ Close
svc 0 @ Call
At this point, we have our file contents in memory at the location referred to by sp. All of the data has been read in as ASCII characters, which means we could successfully print those characters out to stdout, but that is not ideal for doing numeric calculations.
Converting ASCII characters to numbers
In memory right now, we will have something like the ASCII row shown below. Below it is the integer representation of each of the ASCII characters - You can convert very simply with an ASCII table, for numbers, you do this simply by taking 48 off the ASCII representation. Ultimately, we want to get to a point where we have numbers, for example 199 and 200, stored in a way where we can access each number in turn.
ASCII | 49 57 57 10 50 48 48 10
int | 1 9 9 \n 2 0 0 \n
To perform the conversion, we need to run through memory starting at sp, and then:
- Check for a newline - If there is one, we are at the end of the number
- Convert to an integer
- Multiply previous total by 10
- Add new number to previous total Repeat until you hit a newline
So, if we are reading 199\n (from the example above), we will do:
Previous total | New digit
0 | 49 -> 1
1 (x10 = 10) | 57 -> 9
19 (x10 = 190) | 59 -> 9
199 | \n -> Done
Once we have our number, we can overwrite the digit in the stack. As our numbers will fit into a 32 bit int (=4 bytes, or ASCII chars), we can freely overwrite past data without accidentally altering data we haven’t read yet.
The code to do this is as follows:
Convert ASCII characters into numbers
mov x9, sp @ 1. Read position in the buffer
mov x10, sp @ 2. Write position in the buffer
mov x11, 0 @ 3. Accumulated total
mov x12, 0 @ 4. Current byte we're reading
mov x13, sp @ 5. The end of our useful information. sp =
add x13, x13, x20 @ start of our information. x20 contains
add x13, x13, x20 @ the amount of bytes that we read from
add x13, x13, 1 @ the file.
_convert_loop_start:
ldrb w12, [x9] @ Read value at x9 into x12 (1 byte)
cmp x12, 10 @ If x12 == 10 (= \n)
beq _convert_loop_newline @ Then branch to newline code
sub x12, x12, 48 @ Else sub 48 to get back to real number
mov x14, 10 @ So we can multiply by 10
mul x11, x11, x14 @ Multiply accumulated total by 10
add x11, x11, x12 @ Add new digit to accumulated total
b _convert_loop_end @ Glorious success
_convert_loop_newline:
str w11, [x10] @ Store x11 (accumulated total) at memory
@ position of x10 (write position)
add x10, x10, 4 @ Increment x10 (write position) by 4 bytes
mov x11, 0 @ Reset x11 (accumulated total)
@ Onwards to _convert_loop_end
_convert_loop_end:
add x9, x9, 1 @ Increment x9 (read position) by 1 byte
cmp x13, x9 @ Compare read position against end of buffer
bne _convert_loop_start @ If not at end of buffer
str w11, [x10] @ Store our last number
Note: At this point, we have stored the memory location of the start of our data inside the stack pointer,
spand the end of our data is inx13. These will both be useful in future
There are a few new things in this code, namely the comparison , cmp, and branching, beq, bne operators. These are the fundamental building blocks of if statements and loops in modern programming languages. As you can see, we are also starting to write something resembling functions, eg _convert_loop_start, which are used to add some sense and readability to our control flow.
Comparison and branching operators allow us to write code such as the following very basic if statement - This can quite easily be turned into loops by jumping to an instruction further above the point in the program you are in at any point:
cmp x12, 10 @ Compare the value in register x12 to 10
bne _code_to_run_if_not_equal @ If x12 != 10, jump to the section of code called _code_to_run_if_not_equal
add x12, 10 @ Otherwise, add 10 to the value in register x12
After reading the advent of code input file into memory, we can read the contents using lldb to check that it contains what we expected. Lldb gives the following output when we read the first 16 blocks of memory at our stack pointer:
(lldb) x/16x `$sp`
0x16fdef5c0: 0x000000bf 0x000000b9 0x000000bc 0x000000bd
0x16fdef5d0: 0x000000cc 0x000000d5 0x000000d7 0x000000e3
0x16fdef5e0: 0x000000de 0x000000dd 0x000000ec 0x000000eb
0x16fdef5f0: 0x000000ec 0x000000e8 0x000000e0 0x000000e4
Note: These numbers are “little-endian”, ie, numbers towards the right are less significant than those on the left
Using a Hex converter, we can translate this to the numbers that this represents, which luckily represents the correct numbers:
0x16fdef5c0: 191 185 188 189
0x16fdef5d0: 204 213 215 227
0x16fdef5e0: 222 221 236 235
0x16fdef5f0: 236 232 224 228
Performing the calculation
Now, we have our numbers stored in memory correctly, we need to perform our calculation. This invovles looping through the numbers, comparing each number to the previous one. If the next number is larger than the previous, we need to increment a counter by 1.
Perform increment calculation
_processing_start:
add x9, sp, 4 @ 1. Read position in the buffer (start off
@ at sp + 2. This lets us avoid any issues
@ relating to the first number having
@ nothing to compare against)
ldr w11, [sp] @ 2. Previous 32-bit number
mov x12, 0 @ 3. Current 32-bit number
mov x14, 0 @ 4. A counter tracking increases
add x13, x10, 4 @ 5. The end of our useful information
_count_loop_start:
ldr w12, [x9] @ Load current number into x12 (use w12 to
@ get 32 bits)
cmp x12, x11 @ Compare w12 and w11
blt _count_loop_no_increment @ If less than, don't increment counter
_count_loop_increment:
add x14, x14, 1 @ Increment x14 (counter) by 1
_count_loop_no_increment:
mov x11, x12 @ Move current number into previous number
add x9, x9, 4 @ Add 2 to read position
cmp x9, x13 @ Compare current read position to end of
@ useful info
bne _count_loop_start @ If not yet at end of file, back to start of
@ loop
In the above code, we are using the register x14 as our counter, and therefore out answer should be inside that register. Unfortunately, it is a 32-bit integer, so we need to convert it back to ASCII so that we can display it.
Printing our our answer
We can use a similar trick to before to do this conversion - Namely, we need to repeatedly divide the number by 10 and store the remainder, converting all of our remainders into ASCII until we get to the end of the number.
For example:
1709 / 10 = 170 | 9
170 / 10 = 17 | 0
17 / 10 = 1 | 7
1 / 10 = 0 | 1
Reading backwards, we get our number in single integers. We can then add 48 to each of these to get our ASCII characters, and finally print to stdout.
Convert integer to ASCII and print to stdout
_print_start:
mov x9, 0 @ The remainder
mov x10, x14 @ Our remaining number
mov x11, 0 @ A counter of number of digits
mov x12, 10 @ To help divide by 10
mov x13, sp @ Write location for the characters to print
add x13, x13, 3 @ Cheating a bit - I know the output is 4
@ digits, so this lets us start at a position
@ on the stack and work backwards without
@ running out of room.
mov x15, 0 @ Helper
mov x17, 0 @ Another helper
_print_loop_start:
udiv x15, x10, x12 @ Stores quotient in x15
mov x17, x10 @ Store original number in x17
mov x10, x15 @ Store quotient in x10
mul x15, x15, x12 @ Store quotient * 10 in x15
sub x9, x17, x15 @ Calculate remainder
add x9, x9, 48 @ Convert to ascii
strb w9, [x13] @ Store character in memory
add x11, x11, 1 @ Add 1 to counter
sub x13, x13, 1 @ Decrease write location by 1
cmp x10, 0 @ If quotient = 0, we are done
bne _print_loop_start @ Else, back to our print loop
add x11, x11, 1 @ Add 1 to counter to print the final digit
_print_to_stdout:
mov x0, #1 @ 1 = stdout
mov x1, x13 @ String to print out
mov x2, x11 @ length of string
mov x16, #4 @ write
svc 0 @ Call
_exit:
mov x0, #0 @ Use 0 return code
mov x16, #1 @ Exit program
svc 0 @ Call
And finally, our answer has been printed to the console!
What did I learn?
It’s really interesting trying to write code with literally zero abstractions - You have to really think about how computers work in their most basic form. I’d recommend it as a challenge to anyone who likes computers.
I’d never properly thought about how a program interacts with the operating system through syscalls, though it makes a lot of sense having been through this process.
Though my implementation is almost certainly not the most efficient from either a performance or lines-of-code perspective, the fact that this took over 200 lines of assembly code (admittedly a fair few of them are comments!) has really given me an appreciation of what early programmers accomplished, as well as a huge appreciation for how easy higher-level languages have made programming. You could write this program quite comfortably in 3 lines of Python!!
References
A few interesting links that I found during this that really helped me during this process.