A simple x86 assembly program: Sieve of Eratosthenes

opening speech

In my profession, I do not encounter low-level programming: I do programming in scripting languages. But since the soul requires diversity, expanding the horizons of knowledge or simply 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 so, I would like to share the experience of creating a simple program in assembly language for processors of the x86 family, with the analysis of which you can begin your journey into conquering lowlands of abstraction levels.

Before writing it, I formulated the following requirements for the future program:

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

The task for my program, I chose to search for primes using the Sieve of Eratosthenes . As an assembler, I chose nasm .
')
I wrote the code with more emphasis on style and clarity than on its speed. For example, I did not reset the register using xor eax, eax , but using mov eax, 0 due to more appropriate instruction semantics. I decided that since the program is purely for educational purposes, it is possible to unleash and pursue the style of the code in assembler.

So, let's see what happened.

Where to begin?

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

It also raises the question of how data is exchanged between the internal world of the program and the external environment at such a low level. Here comes the operating system API. In DOS, as already mentioned, the interface was fairly simple. For example, the “Hello, world” program 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, the win32n.inc file is used , 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 a program in Linux (and, most likely, in other operating systems) - not a great achievement, but necessary for this program, but a pleasant achievement.

Subroutine call

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

Subroutines are the label on which the code is located. The routine ends with the ret instruction. For example, this subroutine in DOS displays the string “Hello, world” to the console:

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

To call her, you would use the call instruction:

 call print_hello 

For myself, I decided to pass arguments to subroutines through registers and specify in the comments which registers should have any arguments, but in high-level languages, arguments are passed through the stack. For example, the printf function from the C library is called like this:

 push hello call _printf add esp, 4 

Arguments are passed from right to left; the responsibility for clearing 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 , the 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 which you can more concisely implement these actions:

 print_hello: enter 8, 0 ;  ,  8     leave ;  ret 

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

Directly the program

The project contains the following files:

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

Consider the code of the main file:


It can be seen that the program is divided into 5 blocks, designed in the form of subroutines:

1. input_max_number - using the console prompts the user for the maximum number to which the search for primes is performed; to avoid errors, the value is limited by the constants MIN_MAX_NUMBER and MAX_MAX_NUMBER
2. allocate_flags_memory — request the OS to allocate memory for an array of number marks (simple / compound) on the heap; if successful, returns a pointer to the allocated memory through the eax register
3. find_primes_with_eratosthenes_sieve - filter out composite numbers using the classic sieve of Eratosthenes;
4. print_primes - output a list of prime numbers to the console;
5. free_flags_memory - free memory allocated for flags

For functions, the following rule was agreed: the value is returned via the eax register, the edx contains the status. If successful, it contains the value of SUCCESS , that is, 0 , in case of failure, the address of the string with an error message that will be displayed to the user.

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


The following script is used for the build:

Subprograms (functions)

input_max_number

The subroutine is designed to enter into the program the maximum number, which will be searched for simple ones. The key points here are calling the scanf function from 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, first, eax records the memory address 4 bytes below the stack base pointer. This is the memory allocated for the local needs of the subroutine. A pointer to this memory is passed to the scanf function as a target for writing data entered from the keyboard.

After calling the function, the entered value is moved to the eax memory.

allocate_flags_memory and free_flags_memory

The key points of these routines are calls to the malloc and free functions from the C library.

In case of success, malloc returns the address of the allocated memory through the eax register, in case of failure, this register contains 0 . This is the bottleneck of the program for the maximum number. 32 bits is quite enough to search for primes up to 4,294,967,295, but it will not be possible to allocate so much memory at once.

find_primes_with_eratosthenes_sieve

The subroutine implements the classical algorithm for crossing out compound numbers, the sieve of Eratosthenes, in assembler language x86. Pleasant because it does not use calls to external functions and does not require error handling :)

print_primes

The subroutine outputs prime numbers to the console. The key point here is to call the printf function from the C library.

Conclusion

Well, the program meets all the stated requirements and seems to be easy to understand. I would like to hope that someone will help her to understand programming at a low level and he will receive from him the same pleasure that I received.

Also cite the full source code of the program .

I can also bring an interesting fact. Since we were taught from childhood that assembly language programs run faster, I decided to compare the speed of this program with the speed of the C ++ program I wrote once and which looked for simple numbers using Reshet Atkin . A C ++ program compiled in Visual Studio with /O2 performed a search up to the number 2 ^{30 in} about 25 seconds on my machine. The assembler program showed 15 seconds with the Sieve of Eratosthenes.

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

useful links

1. List of resources for learning assembler
2. Memory organization
3. Sieve of Eratosthenes
4. Sieve Atkina
5. Stack
6. Stack frame