Простая программа на ассемблере 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_constatns.asm – определения строковых констант,
• Makefile – сценарий сборки

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

%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_constatns.asm" 

Видно, что программа поделена по смыслу на 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_constatns.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 

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

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 выполняла поиск до числа 2³⁰ примерно за 25 секунд на моей машине. Программа же на ассемблере показала 15 секунд с Решетом Эратосфена.

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

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

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