Skip to content

Assembly generation

Introduction

This time we have reached a milestone: we will finally be generating assembly instead of python. We covered working with the stack and registers, which cause the most problems for beginners in assembly, in the previous article, so this time there is very little left to do. At this point, our compiler generates python code whose structure completely matches the desired assembly. The only remaining task is to handle screen output, everything else is ready.

Hello World, or printing strings to the screen

Most educational compilers choose MIPS assembly, but I don't like running code in an emulator, so I chose x86 GNU assembly, which comes with gcc, without much thought. I can't say exactly why, but I wanted the 32-bit version. For our purposes, it is not necessary to be an assembly guru, but we need to be able to write programs at the "Hello World" level.

Let's create a template that we will build upon. Imagine we have a file helloworld.s with the following content:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
.global _start
        .data
hello: .ascii "hello world\n"
        hello_len = . - hello
        .align 2
        .text
_start:
        movl $4, %eax         # sys_write system call (check asm/unistd_32.h for the table)
        movl $1, %ebx         # file descriptor (stdout)
        movl $hello, %ecx     # message to write
        movl $hello_len, %edx # message length
        int  $0x80            # make system call

_end:
        movl $1, %eax   # sys_exit system call
        movl $0, %ebx   # error code 0
        int $0x80       # make system call

Then we can compile it using the as and ld commands as follows:

as --march=i386 --32 -o helloworld.o helloworld.s &&
ld -m elf_i386 helloworld.o -o helloworld &&
./helloworld

If everything went well, you should see a proud greeting on the screen. Now let's understand what is happening there. There are only two system calls — sys_write and sys_exit. In C, the same thing could be written as follows:

#include <sys/syscall.h>
#include <unistd.h>

int main(void) {
        syscall(SYS_write, 1, "hello world\n", 12);
        return 0;
}

If the stars align correctly, gcc will generate approximately the same assembly code. For our needs, no other system calls are required; write and exit are more than enough, as the only interaction with the outside world in wend is screen output.

Wend does not perform any string operations, only printing constant strings to the screen, so my compiler creates a unique identifier for each string in the header just like for our hello world. For printing boolean values, two constant strings "true" and "false" are used. What about numbers? Well, here we need to do a bit of work. I'm lazy and didn't want to deal with linking glibc and the like, so the luxury of printf is unavailable to me. No problem, sys_write is more than enough!

Printing decimal numbers

sys_write can print strings to the screen, so we need to learn how to convert numbers (I only have signed 32-bit numbers) to string representation. For this, I rolled up my sleeves and wrote the function print_int32:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
.global _start
        .data
        .align 2
        .text
_start:
        pushl $-729
        call print_int32
        addl $4, %esp
_end:
        movl $1, %eax   # sys_exit system call
        movl $0, %ebx   # error code 0
        int $0x80       # make system call

print_int32:
        movl 4(%esp), %eax  # the number to print
        cdq
        xorl %edx, %eax
        subl %edx, %eax     # abs(%eax)
        pushl $10           # base 10
        movl %esp, %ecx     # buffer for the string to print
        subl $16, %esp      # max 10 digits for a 32-bit number (keep %esp dword-aligned)
0:      xorl %edx, %edx     #     %edx = 0
        divl 16(%esp)       #     %eax = %edx:%eax/10 ; %edx = %edx:%eax % 10
        decl %ecx           #     allocate one more digit
        addb $48, %dl       #     %edx += '0'       # 0,0,0,0,0,0,0,0,0,0,'1','2','3','4','5','6'
        movb %dl, (%ecx)    #     store the digit   # ^                   ^                    ^
        test %eax, %eax     #                       # %esp                %ecx (after)         %ecx (before)
        jnz 0b              # until %eax==0         #                     <----- %edx = 6 ----->
        cmp %eax, 24(%esp)  # if the number is negative                            |
        jge 0f              #                                                      |
        decl %ecx           # allocate one more character                          |
        movb $45, 0(%ecx)   # '-'                                                  |
0:      movl $4, %eax       # write system call                                    |
        movl $1, %ebx       # stdout                                               |
        leal 16(%esp), %edx # the buffer to print                                  |
        subl %ecx, %edx     # number of digits    <--------------------------------┘
        int $0x80           # make system call
        addl $20, %esp      # deallocate the buffer
        ret

Reading someone else's assembly code is not easy, so let me provide the python equivalent of our function:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
def print_int32(n):
    buffer = [ None ]*16 # output string buffer
    ecx = 0              # number of characters stored in the buffer

    eax = abs(n)
    while True:
        edx = eax %  10
        eax = eax // 10
        buffer[ecx] = chr(edx + ord('0'))
        ecx += 1
        if eax == 0: break

    if n<0:
        buffer[ecx] = '-'
        ecx += 1

    print(''.join(buffer[ecx-1::-1]))


print_int32(-729)

I am calling write only once, so we need to prepare a string buffer. A 32-bit number will not require more than 11 characters, so I allocate 16 for the buffer (to align the stack to the edge of the machine word). Then I convert the absolute value of the given number to a string, and finally attach a minus if the number was negative.

This way, we can print strings and numbers to the screen, and notably, without the headache of linking with some 32-bit version of libc on a 64-bit system.

This code allows to compile the print statement of our language, but in addition to that, it is handy for debugging. GDB is for the faint-hearted; inserting print statements everywhere is our thing ;)

Putting it all together

Well, that's about it. Now, we take the python code generation template, and instead of outputting python's print(), we simply write call print_int32, and instead of eax = eax * ebx, we write imull %ebx, %eax. Thus, we gradually translate python instructions into assembly, and we're done! No subtleties left, the long-awaited compiler is almost ready. You can take release v0.0.5 and play with it.

The intermediate goal has been achieved: we have learned to compile our own language into real x86 GNU assembly. At the moment, I am using the external library sly for parsing, but along the way, I found out that writing your own parser is not difficult at all. And at the same time, we can tweak the grammar of the language to make it more pleasant!

The next two articles will be about how to create a lexer and parser yourself, the ready code is already in the repository.

Comments