Простая программа на ассемблере x86: Решето Эратосфена

Вступительное слово

По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.

И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства x86, с разбора которой можно начать свой путь в покорение низин уровней абстракции.

До ее написания я сформулировал такие требования к будущей программе:

• Моя программа не должна быть программой под DOS. Слишком много примеров ориентировано на нее в связи с простым API. Моя программа обязательно должна была запускаться на современных ОС.
• Программа должна использовать кучу – получать в свое распоряжение динамически распределяемую память.
• Чтобы не быть слишком сложной, программа должна работать с целыми беззнаковыми числами без использования переносов.

Задачей для своей программы я выбрал поиск простых чисел с помощью Решета Эратосфена. В качестве ассемблера я выбрал nasm.

Код я писал с упором больше на стиль и понятность, чем на скорость его выполнения. К примеру, обнуление регистра я проводил не с помощью xor eax, eax, а с помощью mov eax, 0 в связи с более подходящей семантикой инструкции. Я решил, что поскольку программа преследует исключительно учебные цели, можно распоясаться и заниматься погоней за стилем кода в ассемблере.

Итак, посмотрим, что получилось.

С чего начать?

Пожалуй, самая сложная вещь, с которой сталкиваешься при переходе от высокоуровневых языков к ассемблеру, это организация памяти. К счастью, на эту тему на Хабре уже была хорошая статья.

Так же встает вопрос, каким образом на таком низком уровне реализуется обмен данными между внутренним миром программы и внешней средой. Тут на сцену выходит API операционной системы. В DOS, как уже было упомянуто, интерфейс был достаточно простой. К примеру, программа «Hello, world» выглядела так:

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, '$'

В Windows же для этих целей используется Win32 API, соответственно, программа должна использовать методы соответствующих библиотек:

%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

Здесь используется файл win32n.inc, где определены макросы, сокращающие код для работы с Win32 API.

Я решил не использовать напрямую API ОС и выбрал путь использования функций из библиотеки Си. Так же это открыло возможность компиляции программы в Linux (и, скорее всего, в других ОС) – не слишком большое и нужное этой программе достижение, но приятное достижение.

Вызов подпрограмм

Потребность вызывать подпрограммы влечет за собой несколько тем для изучения: организация подпрограмм, передача аргументов, создание стекового кадра, работа с локальными переменными.

Подпрограммы представляют собой метку, по которой располагается код. Заканчивается подпрограмма инструкцией ret. К примеру, вот такая подпрограмма в DOS выводит в консоль строку «Hello, world»:

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

Для ее вызова нужно было бы использовать инструкцию call:

call print_hello

Для себя я решил передавать аргументы подпрограммам через регистры и указывать в комментариях, в каких регистрах какие аргументы должны быть, но в языках высокого уровня аргументы передаются через стек. К примеру, вот так вызывается функция printf из библиотеки Си:

push hello
call _printf
add esp, 4

Аргументы передаются справа налево, обязанность по очистке стека лежит на вызывающей стороне.

При входе в подпрограмму необходимо создать новый стековый кадр. Делается это следующим образом:

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

Соответственно, перед выходом нужно восстановить прежнее состояние стека:

    mov esp, ebp
    pop ebp
    ret

Для локальных переменных так же используется стек, на котором после создания нового кадра выделяется нужное количество байт:

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

Так же архитектура x86 предоставляет специальные инструкции, с помощью которых можно более лаконично реализовать эти действия:

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

    leave ;восстановить стек
    ret

Второй параметр инструкции enter – уровень вложенности подпрограммы. Он нужен для линковки с языками высокого уровня, поддерживающими такую методику организации подпрограмм. В нашем случае это значение можно оставить нулевым.

Непосредственно программа

Проект содержит такие файлы:

• main.asm – главный файл,
• functions.asm – подпрограммы,
• string_constants.asm – определения строковых констант,
• Makefile – сценарий сборки

Рассмотрим код основного файла:


Видно, что программа поделена по смыслу на 5 блоков, оформленных в виде подпрограмм:

1. input_max_number — с помощью консоли запрашивает у пользователя максимальное число, до которого производится поиск простых; во избежание ошибок значение ограничено константами MIN_MAX_NUMBER и MAX_MAX_NUMBER
2. allocate_flags_memory — запросить у ОС выделение памяти для массива пометок чисел (простое/составное) в куче; в случае успеха возвращает указатель на выделенную память через регистр eax
3. find_primes_with_eratosthenes_sieve — отсеять составные числа с помощью классического решета Эратосфена;
4. print_primes — вывести в консоль список простых чисел;
5. free_flags_memory — освободить память, выделенную для флагов

Для функций было условлено такое правило: значение возвращается через регистр eax, регистр edx содержит статус. В случае успеха он содержит значение SUCCESS, то есть, 0, в случае неудачи — адрес строки с сообщением об ошибке, которое будет выведено пользователю.

Файл string_constants.asm содержит определение строковых переменных, значения которых, как намекает название файла, менять не предполагается. Только ради этих переменных было сделано исключение к правилу «не использовать глобальные переменные». Я так и не нашел более удобного способа доставлять строковые константы функциям ввода-вывода – подумывал даже записывать на стек непосредственно перед вызовами функций, но решил, что эта идея куда хуже идеи с глобальными переменными.


Для сборки применяется такой сценарий:

Подпрограммы (функции)

input_max_number

Подпрограмма призвана ввести в программу максимальное число, до которого будет производиться поиск простых. Ключевым моментов тут является вызов функции scanf из библиотеки Си:

        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]

Таким образом, сначала в eax записывается адрес памяти на 4 байта ниже указателя базы стека. Это память, выделенная для локальных нужд подпрограммы. Указатель на эту память передается функции scanf как цель для записи данных, введенных с клавиатуры.

После вызова функции, в eax из памяти перемещается введенное значение.

allocate_flags_memory и free_flags_memory

Ключевыми местами этих подпрограмм являются вызовы функций malloc и free из библиотеки Си.

malloc в случае удачи возвращает через регистр eax адрес выделенной памяти, в случае неудачи этот регистр содержит 0. Это самое узкое место программы касательно максимального числа. 32 бит вполне достаточно для поиска простых чисел до 4 294 967 295, но выделить разом столько памяти не получится.

find_primes_with_eratosthenes_sieve

Подпрограмма реализует классический алгоритм для вычеркивания составных чисел, решето Эратосфена, на языке ассемблера x86. Приятна тем, что не использует вызовы внешних функций и не требует обработки ошибок :)

print_primes

Подпрограмма выводит в консоль простые числа. Ключевым моментом тут является вызов функции printf из библиотеки Си.

Заключение

Что ж, программа отвечает всем сформулированным требованиям и, кажется, проста для понимания. Хочется надеяться, кому-нибудь ее разбор поможет вникнуть в программирование на низком уровне и он получит от него такое же удовольствие, какое получил я.

Так же привожу полные исходники программы.

Могу так же привести интересный факт. Поскольку с детства нас учили, что программы на языке ассемблера выполняются быстрее, я решил сравнить скорость выполнения этой программы со скоростью программы на C++, которую я писал когда-то и которая искала простые числа с помощью Решета Аткина. Программа на С++, скомпилированная в Visual Studio с /O2 выполняла поиск до числа 2³⁰ примерно за 25 секунд на моей машине. Программа же на ассемблере показала 15 секунд с Решетом Эратосфена.

Это, конечно, скорее байка, чем научный факт, поскольку не было серьезного тестирования не было выяснения причин, но как интересный факт для завершения статьи подойдет, как мне кажется.

Полезные ссылки

1. Список ресурсов для изучения ассемблера
2. Организация памяти
3. Решето Эратосфена
4. Решето Аткина
5. Стек
6. Стековый кадр