Вступительное слово
По своей профессии я не сталкиваюсь с низкоуровневым программированием: занимаюсь программированием на скриптовых языках. Но поскольку душа требует разнообразия, расширения горизонтов знаний или просто понимания, как работает машина на низком уровне, я занимаюсь программированием на языках, отличающихся от тех, с помощью которых зарабатываю деньги – такое у меня хобби.
И вот, я хотел бы поделиться опытом создания простой программы на языке ассемблера для процессоров семейства 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 секунд с Решетом Эратосфена. Это, конечно, скорее байка, чем научный факт, поскольку не было серьезного тестирования не было выяснения причин, но как интересный факт для завершения статьи подойдет, как мне кажется.
