Решето Эратосфена (asm x86)

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 19:38, 9 августа 2015.

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

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

Требования к будущей программе:

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

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

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

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

Так же встает вопрос, каким образом на таком низком уровне реализуется обмен данными между внутренним миром программы и внешней средой. Тут на сцену выходит 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.

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

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

Подпрограммы представляют собой метку, по которой располагается код. Заканчивается подпрограмма инструкцией 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 блоков, оформленных в виде подпрограмм:

  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 содержит определение строковых переменных, значения которых, как намекает название файла, менять не предполагается. Только ради этих переменных было сделано исключение к правилу «не использовать глобальные переменные».

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 из библиотеки Си.

Заключение

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