Вступительное слово
По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.
И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства 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– сценарий сборки
Рассмотрим код основного файла:
main.asm
%define SUCCESS 0
%define MIN_MAX_NUMBER 3
%define MAX_MAX_NUMBER 4294967294
global _main
extern _printf
extern _scanf
extern _malloc
extern _free
SECTION .text
_main:
enter 0, 0
;ввод максимального числа
call input_max_number
cmp edx, SUCCESS
jne .custom_exit
mov [max_number], eax
;выделяем память для массива флагов
mov eax, [max_number]
call allocate_flags_memory
cmp edx, SUCCESS
jne .custom_exit
mov [primes_pointer], eax
;отсеять составные числа
mov eax, [primes_pointer]
mov ebx, [max_number]
call find_primes_with_eratosthenes_sieve
;вывести числа
mov eax, [primes_pointer]
mov ebx, [max_number]
call print_primes
;освободить память от массива флагов
mov eax, [primes_pointer]
call free_flags_memory
;выход
.success:
push str_exit_success
call _printf
jmp .return
.custom_exit:
push edx
call _printf
.return:
mov eax, SUCCESS
leave
ret
%include "functions.asm"
SECTION .data
max_number: dd 0
primes_pointer: dd 0
%include "string_constants.asm"
Видно, что программа поделена по смыслу на 5 блоков, оформленных в виде подпрограмм:
input_max_number— с помощью консоли запрашивает у пользователя максимальное число, до которого производится поиск простых; во избежание ошибок значение ограничено константамиMIN_MAX_NUMBERиMAX_MAX_NUMBERallocate_flags_memory— запросить у ОС выделение памяти для массива пометок чисел (простое/составное) в куче; в случае успеха возвращает указатель на выделенную память через регистрeaxfind_primes_with_eratosthenes_sieve— отсеять составные числа с помощью классического решета Эратосфена;print_primes— вывести в консоль список простых чисел;free_flags_memory— освободить память, выделенную для флагов
Для функций было условлено такое правило: значение возвращается через регистр
eax, регистр edx содержит статус. В случае успеха он содержит значение SUCCESS, то есть, 0, в случае неудачи — адрес строки с сообщением об ошибке, которое будет выведено пользователю.Файл
string_constants.asm содержит определение строковых переменных, значения которых, как намекает название файла, менять не предполагается. Только ради этих переменных было сделано исключение к правилу «не использовать глобальные переменные». Я так и не нашел более удобного способа доставлять строковые константы функциям ввода-вывода – подумывал даже записывать на стек непосредственно перед вызовами функций, но решил, что эта идея куда хуже идеи с глобальными переменными.string_constants.asm
;подписи ввода-вывода, форматы
str_max_number_label: db "Max number (>=3): ", 0
str_max_number_input_format: db "%u", 0
str_max_number_output_format: db "Using max number %u", 0xD, 0xA, 0
str_print_primes_label: db "Primes:", 0xD, 0xA, 0
str_prime: db "%u", 0x9, 0
str_cr_lf: db 0xD, 0xA, 0
;сообщения выхода
str_exit_success: db "Success!", 0xD, 0xA, 0
str_error_max_num_too_little: db "Max number is too little!", 0xD, 0xA, 0
str_error_max_num_too_big: db "Max number is too big!", 0xD, 0xA, 0
str_error_malloc_failed: db "Can't allocate memory!", 0xD, 0xA, 0
Для сборки применяется такой сценарий:
Makefile
ifdef SystemRoot
format = win32
rm = del
ext = .exe
else
format = elf
rm = rm -f
ext =
endif
all: primes.o
gcc primes.o -o primes$(ext)
$(rm) primes.o
primes.o:
nasm -f $(format) main.asm -o primes.o
Подпрограммы (функции)
input_max_number
Код подпрограммы
; Ввести максимальное число
; Результат: EAX - максимальное число
input_max_number:
;создать стек-фрейм,
;4 байта для локальных переменных
enter 4, 1
;показываем подпись
push str_max_number_label ;см. string_constants.asm
call _printf
add esp, 4
;вызываем 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]
;проверка
cmp eax, MIN_MAX_NUMBER
jb .number_too_little
cmp eax, MAX_MAX_NUMBER
ja .number_too_big
jmp .success
;выход
.number_too_little:
mov edx, str_error_max_num_too_little ;см. string_constants.asm
jmp .return
.number_too_big:
mov edx, str_error_max_num_too_big ;см. string_constants.asm
jmp .return
.success:
push eax
push str_max_number_output_format ;см. string_constants.asm
call _printf
add esp, 4
pop eax
mov edx, SUCCESS
.return:
leave
ret
Подпрограмма призвана ввести в программу максимальное число, до которого будет производиться поиск простых. Ключевым моментов тут является вызов функции
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
Код подпрограмм
; Выделить память для массива флагов
; Аргумент: EAX - максимальное число
; Результат: EAX - указатель на память
allocate_flags_memory:
enter 8, 1
;выделить EAX+1 байт
inc eax
mov [ebp-4], eax
push eax
call _malloc
add esp, 4
;проверка
cmp eax, 0
je .fail
mov [ebp-8], eax
;инициализация
mov byte [eax], 0
cld
mov edi, eax
inc edi
mov edx, [ebp-4]
add edx, eax
mov al, 1
.write_true:
stosb
cmp edi, edx
jb .write_true
;выход
mov eax, [ebp-8]
jmp .success
.fail:
mov edx, str_error_malloc_failed ;см. string_constants.asm
jmp .return
.success:
mov edx, SUCCESS
.return:
leave
ret
; Освободить память от массива флагов
; Аргумент: EAX - указатель на память
free_flags_memory:
enter 0, 1
push eax
call _free
add esp, 4
leave
ret
Ключевыми местами этих подпрограмм являются вызовы функций
malloc и free из библиотеки Си.malloc в случае удачи возвращает через регистр eax адрес выделенной памяти, в случае неудачи этот регистр содержит 0. Это самое узкое место программы касательно максимального числа. 32 бит вполне достаточно для поиска простых чисел до 4 294 967 295, но выделить разом столько памяти не получится.find_primes_with_eratosthenes_sieve
Код подпрограммы
;Найти простые числа с помощью решета Эратосфена
;Аргументы: EAX - указатель на массив флагов, EBX - максимальное число
find_primes_with_eratosthenes_sieve:
enter 8, 1
mov [ebp-4], eax
add eax, ebx
inc eax
mov [ebp-8], eax
;вычеркиваем составные числа
cld
mov edx, 2 ;p = 2
mov ecx, 2 ;множитель с = 2
.strike_out_cycle:
;x = c*p
mov eax, edx
push edx
mul ecx
pop edx
cmp eax, ebx
jbe .strike_out_number
jmp .increase_p
.strike_out_number:
mov edi, [ebp-4]
add edi, eax
mov byte [edi], 0
inc ecx ;c = c + 1
jmp .strike_out_cycle
.increase_p:
mov esi, [ebp-4]
add esi, edx
inc esi
mov ecx, edx
inc ecx
.check_current_number:
mov eax, ecx
mul eax
cmp eax, ebx
ja .return
lodsb
inc ecx
cmp al, 0
jne .new_p_found
jmp .check_current_number
.new_p_found:
mov edx, ecx
dec edx
mov ecx, 2
jmp .strike_out_cycle
.return:
leave
ret
Подпрограмма реализует классический алгоритм для вычеркивания составных чисел, решето Эратосфена, на языке ассемблера x86. Приятна тем, что не использует вызовы внешних функций и не требует обработки ошибок :)
print_primes
Код подпрограммы
; Вывести простые числа
; Параметры: EAX - указатель на массив флагов, EBX - максимальное число
print_primes:
enter 12, 1
mov [ebp-4], eax
mov [ebp-8], ebx
push str_print_primes_label
call _printf
add esp, 4
cld
mov esi, [ebp-4]
mov edx, esi
add edx, [ebp-8]
inc edx
mov [ebp-12], edx
mov ecx, 0
.print_cycle:
lodsb
cmp al, 0
jne .print
jmp .check_finish
.print:
push esi
push ecx
push str_prime ;см. string_constants.asm
call _printf
add esp, 4
pop ecx
pop esi
mov edx, [ebp-12]
.check_finish:
inc ecx
cmp esi, edx
jb .print_cycle
push str_cr_lf
call _printf
add esp, 4
leave
ret
Подпрограмма выводит в консоль простые числа. Ключевым моментом тут является вызов функции
printf из библиотеки Си.Заключение
Что ж, программа отвечает всем сформулированным требованиям и, кажется, проста для понимания. Хочется надеяться, кому-нибудь ее разбор поможет вникнуть в программирование на низком уровне и он получит от него такое же удовольствие, какое получил я.
Так же привожу полные исходники программы.
Могу так же привести интересный факт. Поскольку с детства нас учили, что программы на языке ассемблера выполняются быстрее, я решил сравнить скорость выполнения этой программы со скоростью программы на C++, которую я писал когда-то и которая искала простые числа с помощью Решета Аткина. Программа на С++, скомпилированная в Visual Studio с
/O2 выполняла поиск до числа 230 примерно за 25 секунд на моей машине. Программа же на ассемблере показала 15 секунд с Решетом Эратосфена. Это, конечно, скорее байка, чем научный факт, поскольку не было серьезного тестирования не было выяснения причин, но как интересный факт для завершения статьи подойдет, как мне кажется.
