Simple x86 assembler program: Sieve of Eratosthenes

introduction

In my profession, I do not encounter low-level programming: I am engaged in programming in scripting languages. But since the soul requires diversity, broadening the horizons of knowledge or just understanding how the machine works at a low level, I do programming in languages ​​other than those with which I make money - this is my hobby.

And now, I would like to share the experience of creating a simple assembly language program for x86 family processors, with the analysis of which you can begin your journey into conquering the lowlands of abstraction levels.

Before writing it, I formulated such requirements for a future program:

• My program should not be a DOS program. Too many examples are oriented to it in connection with a simple API. My program must have run on modern OSs.
• The program should use a bunch - get at its disposal dynamically allocated memory.
• In order not to be too complicated, the program should work with unsigned integers without the use of hyphens.

For my program, I chose to search for primes using the Sieve of Eratosthenes . I chose nasm as the assembler .

I wrote the code with more emphasis on style and comprehensibility than on the speed of its execution. For example, I didn’t reset the register with help xor eax, eax, but with help mov eax, 0in connection with a more suitable instruction semantics. I decided that since the program pursues exclusively educational goals, you can unbelieve and engage in the pursuit of code style in assembler.

So, let's see what happened.

Where to begin?

Perhaps the most difficult thing that you encounter in the transition from high-level languages ​​to assembler is the organization of memory. Fortunately, there was already a good article on this topic on Habré .

The question also arises of how the data exchange between the internal world of the program and the external environment is realized at such a low level. Here the API of the operating system enters the scene. In DOS, as already mentioned, the interface was quite simple. For example, the program “Hello, world” looked like this:

SECTION .text
    org 0x100
    mov ah, 0x9
    mov dx, hello
    int 0x21
    mov ax, 0x4c00
    int 0x21
SECTION .data
    hello: db "Hello, world!", 0xD, 0xA, '$'

In Windows, the Win32 API is used for these purposes, respectively, the program should use the methods of the corresponding libraries:

%include "win32n.inc"
extern MessageBoxA
import MessageBoxA user32.dll
extern ExitProcess
import ExitProcess kernel32.dll
SECTION code use32 class=code
    ..start:
    push UINT MB_OK
    push LPCTSTR window_title
    push LPCTSTR banner
    push HWND NULL
    call [MessageBoxA]
    push UINT NULL
    call [ExitProcess]
SECTION data use32 class=data
    banner: db "Hello, world!", 0xD, 0xA, 0
    window_title: db "Hello", 0

Here we use the win32n.inc file , where macros are defined that reduce the code for working with the Win32 API.

I decided not to use the OS API directly and chose the way to use functions from the C library. It also opened up the possibility of compiling the program in Linux (and, most likely, in other OSs) - an achievement that is not too big and necessary for this program, but a pleasant achievement.

Subroutine call

The need to call subroutines entails several topics for study: organizing subroutines, passing arguments, creating a stack frame, working with local variables.

Subprograms are the label by which the code is located. The subroutine ends with an instruction ret. For example, here is a subroutine in DOS that displays the string “Hello, world” in the console:

print_hello:
    mov ah, 0x9
    mov dx, hello
    int 0x21
    ret

To call it, you would need to use the instruction call:

call print_hello

For myself, I decided to pass arguments to subprograms through registers and indicate in the comments in which registers which arguments should be, but in high-level languages, arguments are passed through the stack. For example, this is how the function printf from the C library is called :

push hello
call _printf
add esp, 4

Arguments are passed from right to left, the responsibility to clear the stack lies with the caller.

When entering the subroutine, you need to create a new stack frame. This is done as follows:

print_hello:
    push ebp ;сохраняем указатель начала стекового кадра на стеке
    mov ebp, esp ;теперь началом кадра является вершина предыдущего

Accordingly, before exiting, you need to restore the previous state of the stack:

    mov esp, ebp
    pop ebp
    ret

For local variables , a stack is also used on which, after creating a new frame, the required number of bytes is allocated:

print_hello:
    push ebp
    mov ebp, esp
    sub esp, 8 ;опускаем указатель вершины стека на 8 байт, чтобы выделить память

The x86 architecture also provides special instructions with the help of which these actions can be more succinctly implemented:

print_hello:
    enter 8, 0 ;создать новый кадр, выделить 8 байт для локальных переменных
    leave ;восстановить стек
    ret

The second parameter of the instruction enteris the nesting level of the subroutine. It is needed for linking with high-level languages ​​that support such a technique for organizing routines. In our case, this value can be left zero.

The program itself

The project contains the following files:

• main.asm - main file,
• functions.asm - routines
• string_constants.asm - definitions of string constants,
• Makefile - build script

Consider the code for the main file:


It can be seen that the program is divided in meaning into 5 blocks, designed as subprograms:

1. input_max_number- using the console it asks the user for the maximum number to which simple ones are searched; to avoid errors, the value is limited by constants MIN_MAX_NUMBERandMAX_MAX_NUMBER
2. allocate_flags_memory- request from the OS the allocation of memory for the array of tagging numbers (simple / compound) on the heap; if successful, returns a pointer to the allocated memory through the registereax
3. find_primes_with_eratosthenes_sieve - weed out composite numbers using the classic sieve of Eratosthenes;
4. print_primes - display in the console a list of primes;
5. free_flags_memory - free up memory allocated for flags

For functions, this rule was agreed: the value is returned through the register eax, the register edxcontains the status. In case of success, it contains a value SUCCESS, that is, 0in case of failure, the address of the line with the error message that will be displayed to the user.

The file string_constants.asmcontains a definition of string variables whose values, as the name of the file hints, are not intended to be changed. It was only for the sake of these variables that an exception was made to the “do not use global variables” rule. I never found a more convenient way to deliver string constants to I / O functions - I even thought about writing to the stack immediately before function calls, but decided that this idea is much worse than the idea with global variables.


The following scenario is used for assembly:

Subprograms (functions)

input_max_number

The subprogram is intended to introduce into the program the maximum number up to which simple ones will be searched. The key point here is the function call scanffrom the C library:

        mov eax, ebp
        sub eax, 4
        push eax
        push str_max_number_input_format ;см. string_constants.asm
        call _scanf
        add esp, 8
        mov eax, [ebp-4]

Thus, eaxthe memory address is written 4 bytes below the stack base pointer first. This is the memory allocated for the local needs of the subprogram. A pointer to this memory is passed to the function scanfas the target for writing data entered from the keyboard.

After calling the function, the eaxentered value is moved to the memory.

allocate_flags_memory and free_flags_memory

Key locations of these routines are the functions of the challenges mallocand freeof the C library.

mallocin case of success, returns the eaxaddress of the allocated memory through the register , in case of failure, this register contains 0. This is the bottleneck of the program regarding the maximum number. 32 bits is enough to search for primes up to 4,294,967,295, but you won’t be able to allocate as much memory at once.

find_primes_with_eratosthenes_sieve

The subroutine implements the classical algorithm for striking out composite numbers, the sieve of Eratosthenes, in x86 assembly language. It is pleasant because it does not use external function calls and does not require error handling :)

print_primes

The routine prints prime numbers to the console. The key point here is the function call printffrom the C library.

Conclusion

Well, the program meets all the stated requirements and seems easy to understand. I would like to hope that someone’s analysis of it will help to understand programming at a low level and he will enjoy it as much as I did.

I also bring the complete source code of the program .

I can also give an interesting fact. Since we were taught from childhood that assembler programs run faster, I decided to compare the speed of this program with the speed of a C ++ program that I wrote once and was looking for primes using the Atkin Reshet . A C ++ program compiled in Visual Studio c /O2searched up to 2 ³⁰in about 25 seconds on my car. The program in assembler showed 15 seconds with the Sieve of Eratosthenes.

This, of course, is more a trick than a scientific fact, since there was no serious testing, there was no clarification of the reasons, but as an interesting fact, it seems to me to complete the article.

useful links

1. List of Resources for Learning Assembler
2. Memory organization
3. Sieve of Eratosthenes
4. Atkin sieve
5. Stack
6. Stack frame