В наше время редко возникает необходимость писать на чистом ассемблере, но я определённо рекомендую это всем, кто интересуется программированием. Вы увидите вещи под иным углом, а навыки пригодятся при отладке кода на других языках.

В этой статье мы напишем с нуля калькулятор обратной польской записи (RPN) на чистом ассемблере x86. Когда закончим, то сможем использовать его так:

$ ./calc "32+6*" # "(3+2)*6" в инфиксной нотации
30

Весь код для статьи здесь. Он обильно закомментирован и может служить учебным материалом для тех, кто уже знает ассемблер.

Начнём с написания базовой программы Hello world! для проверки настроек среды. Затем перейдём к системным вызовам, стеку вызовов, стековым кадрам и соглашению о вызовах x86. Потом для практики напишем некоторые базовые функции на ассемблере x86 — и начнём писать калькулятор RPN.

Предполагается, что у читателя есть некоторый опыт программирования на C и базовые знания компьютерной архитектуры (например, что такое регистр процессора). Поскольку мы будем использовать Linux, вы также должны уметь использовать командную строку Linux.

Настройка среды

Как уже сказано, мы используем Linux (64- или 32-битный). Приведённый код не работает в Windows или Mac OS X.

Для установки нужен только компоновщик GNU ld из binutils, который предварительно установлен в большинстве дистрибутивов, и ассемблер NASM. На Ubuntu и Debian можете установить и то, и другое одной командой:

$ sudo apt-get install binutils nasm

Я бы также рекомендовал держать под рукой таблицу ASCII.

Hello, world!

Для проверки среды сохраните следующий код в файле calc.asm:

; Компоновщик находит символ _start и начинает выполнение программы
; отсюда.
global _start

; В разделе .rodata хранятся константы (только для чтения)
; Порядок секций не имеет значения, но я люблю ставить её вперёд
section .rodata
    ; Объявляем пару байтов как hello_world. Псевдоинструкция базы NASM 
    ; допускает однобайтовое значение, строковую константу или их сочетание,
    ; как здесь. 0xA = новая строка, 0x0 = нуль окончания строки
    hello_world: db "Hello world!", 0xA, 0x0

; Начало секции .text, где находится код программы
section .text
_start:
    mov eax, 0x04           ; записать число 4 в регистр eax (0x04 = write())
    mov ebx, 0x1            ; дескриптор файла (1 = стандартный вывод, 2 = стандартная ошибка)
    mov ecx, hello_world    ; указатель на выводимую строку
    mov edx, 14             ; длина строки
    int 0x80                ; отправляем сигнал прерывания 0x80, который ОС
                            ;   интерпретирует как системный вызов

    mov eax, 0x01           ; 0x01 = exit()
    mov ebx, 0              ; 0 = нет ошибок
    int 0x80

Комментарии объясняют общую структуру. Список регистров и общих инструкций можете изучить в «Руководстве по ассемблеру x86 университета Вирджинии». При дальнейшем обсуждении системных вызовов это тем более понадобится.

Следующие команды собирают файл ассемблера в объектный файл, а затем компонует исполняемый файл:

$ nasm -f elf_i386 calc.asm -o calc
$ ld -m elf_i386 calc.o -o calc

После запуска вы должны увидеть:

$ ./calc
Hello world!

Makefile

Это необязательная часть, но для упрощения сборки и компоновки в будущем можно сделать Makefile. Сохраните его в том же каталоге, что и calc.asm:

CFLAGS= -f elf32
LFLAGS= -m elf_i386

all: calc

calc: calc.o
	ld $(LFLAGS) calc.o -o calc

calc.o: calc.asm
	nasm $(CFLAGS) calc.asm -o calc.o

clean:
	rm -f calc.o calc
        
.INTERMEDIATE: calc.o

Затем вместо вышеприведённых инструкций просто запускаем make.

Системные вызовы

Системные вызовы Linux указывают ОС выполнить для нас какие-то действия. В этой статье мы используем только два системных вызова: write() для записи строки в файл или поток (в нашем случае это стандартное устройство вывода и стандартная ошибка) и exit() для выхода из программы:

syscall 0x01: exit(int error_code)
  error_code - используем 0 для выхода без ошибок и любые другие значения (такие как 1) для ошибок
syscall 0x04: write(int fd, char *string, int length)
  fd — используем 1 для стандартного вывода, 2 для стандартного потока вывода ошибок
  string — указатель на первый символ строки
  length — длина строки в байтах

Системные вызовы настраиваются путём сохранения номера системного вызова в регистре eax, а затем его аргументов в ebx, ecx, edx в таком порядке. Можете заметить, что у exit() только один аргумент — в этом случае ecx и edx не имеют значения.

eax	ebx	ecx	edx
Номер системного вызова	arg1	arg2	arg3

Стек вызовов

Стек вызовов — структура данных, в которой хранится информация о каждом обращении к функции. У каждого вызова собственный раздел в стеке — «фрейм». Он хранит некоторую информацию о текущем вызове: локальные переменные этой функции и адрес возврата (куда программа должна перейти после выполнения функции).

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

Инструкция push заносит что-нибудь на верх стека, а pop уносит данные оттуда. Например, push еах выделяет место наверху стека и помещает туда значение из регистра eax, а pop еах переносит любые данные из верхней части стека в eax и освобождает эту область памяти.

Цель регистра esp — указать на вершину стека. Любые данные выше esp считаются не попавшими в стек, это мусорные данные. Выполнение инструкции push (или pop) перемещает esp. Вы можете манипулировать esp и напрямую, если отдаёте отчёт своим действиям.

Регистр ebp похож на esp, только он всегда указывает примерно на середину текущего кадра стека, непосредственно перед локальными переменными текущей функции (поговорим об этом позже). Однако вызов другой функции не перемещает ebp автоматически, это нужно каждый раз делать вручную.

Соглашение о вызовах для архитектуры x86

В х86 нет встроенного понятия функции как в высокоуровневых языках. Инструкция call — это по сути просто jmp (goto) в другой адрес памяти. Чтобы использовать подпрограммы как функции в других языках (которые могут принимать аргументы и возвращать данные обратно), нужно следовать соглашению о вызовах (существует много конвенций, но мы используем CDECL, самое популярное соглашение для x86 среди компиляторов С и программистов на ассемблере). Это также гарантирует, что регистры подпрограммы не перепутаются при вызове другой функции.

Правила вызывающей стороны

Перед вызовом функции вызывающая сторона должна:

1. Сохранить в стек регистры, которые обязан сохранять вызывающий. Вызываемая функция может изменить некоторые регистры: чтобы не потерять данные, вызывающая сторона должна сохранить их в памяти до помещения в стек. Речь идёт о регистрах eax, ecx и edx. Если вы не используете какие-то из них, то их можно не сохранять.
2. Записать аргументы функции на стек в обратном порядке (сначала последний аргумент, в конце первый аргумент). Такой порядок гарантирует, что вызываемая функция получит из стека свои аргументы в правильном порядке.
3. Вызвать подпрограмму.

По возможности функция сохранит результат в eax. Сразу после call вызывающая сторона должна:

1. Удалить из стека аргументы функции. Обычно это делается путём простого добавления числа байтов в esp. Не забывайте, что стек растёт вниз, поэтому для удаления из стека необходимо добавить байты.
2. Восстановить сохранённые регистры, забрав их из стека в обратном порядке инструкцией pop. Вызываемая функция не изменит никакие другие регистры.

Следующий пример демонстрирует, как применяются эти правила. Предположим, что функция _subtract принимает два целочисленных (4-байтовых) аргумента и возвращает первый аргумент за вычетом второго. В подпрограмме _mysubroutine вызываем _subtract с аргументами 10 и 2:

_mysubroutine:
    ; ...
    ; здесь какой-то код
    ; ...
    push ecx       ; сохраняем регистры (я решил не сохранять eax)
    push edx
    push 2         ; второе правило, пушим аргументы в обратном порядке
    push 10
    call _subtract ; eax теперь равен 10-2=8
    add esp, 8     ; удаляем 8 байт со стека (два аргумента по 4 байта)
    pop edx        ; восстанавливаем сохранённые регистры
    pop ecx
    ; ...
    ; ещё какой-то код, где я использую удивительно полезное значение из eax
    ; ...

Правила вызываемой подпрограммы

Перед вызовом подпрограмма должна:

1. Сохранить указатель базового регистра ebp предыдущего фрейма, записав его на стек.
2. Отрегулировать ebp с предыдущего фрейма на текущий (текущее значение esp).
3. Выделить больше места в стеке для локальных переменных, при необходимости переместить указатель esp. Поскольку стек растёт вниз, нужно вычесть недостающую память из esp.
4. Сохранить в стек регистры вызываемой подпрограммы. Это ebx, edi и esi. Необязательно сохранять регистры, которые не планируется изменять.

Стек вызовов после шага 1:



Стек вызовов после шага 2:



Стек вызовов после шага 4:



На этих диаграммах в каждом стековом фрейме указан адрес возврата. Его автоматически вставляет в стек инструкция call. Инструкция ret извлекает адрес с верхней части стека и переходит на него. Эта инструкция нам не нужна, я просто показал, почему локальные переменные функции находятся на 4 байта выше ebp, но аргументы функции — на 8 байт ниже ebp.

На последней диаграмме также можно заметить, что локальные переменные функции всегда начинается на 4 байта выше ebp с адреса ebp-4 (здесь вычитание, потому что мы двигаемся вверх по стеку), а аргументы функции всегда начинается на 8 байт ниже ebp с адреса ebp+8 (сложение, потому что мы двигаемся вниз по стеку). Если следовать правилам из этой конвенции, так будет c переменными и аргументами любой функции.

Когда функция выполнена и вы хотите вернуться, нужно сначала установить eax на возвращаемое значение функции, если это необходимо. Кроме того, нужно:

1. Восстановить сохранённые регистры, вынеся их из стека в обратном порядке.
2. Освободить место в стеке, выделенное локальным переменным на шаге 3, если необходимо: делается простой установкой esp в ebp
3. Восстановить указатель базы ebp предыдущего фрейма, вынеся его из стека.
4. Вернуться с помощью ret

Теперь реализуем функцию _subtract из нашего примера:

_subtract:
    push ebp           ; сохранение указателя базы предыдущего фрейма
    mov ebp, esp        ; настройка ebp
    ; Здесь я бы выделил место на стеке для локальных переменных, но они мне не нужны
    ; Здесь я бы сохранил регистры вызываемой подпрограммы, но я ничего не
    ; собираюсь изменять
    ; Тут начинается функция
    mov eax, [ebp+8]    ; копирование первого аргумента функции в eax. Скобки
                        ; означают доступ к памяти по адресу ebp+8
    sub eax, [ebp+12]   ; вычитание второго аргумента по адресу ebp+12 из первого 
                        ; аргумента
    ; Тут функция заканчивается, eax равен её возвращаемому значению
    ; Здесь я бы восстановил регистры, но они не сохранялись
    ; Здесь я бы освободил стек от переменных, но память для них не выделялась
    pop ebp             ; восстановление указателя базы предыдущего фрейма
    ret

Вход и выход

В приведённом примере вы можете заметить, что функция всегда запускается одинаково: push ebp, mov ebp, esp и выделение памяти для локальных переменных. В наборе x86 есть удобная инструкция, которая всё это выполняет: enter a b, где a — количество байт, которые вы хотите выделить для локальных переменных, b — «уровень вложенности», который мы всегда будем выставлять на 0. Кроме того, функция всегда заканчивается инструкциями pop ebp и mov esp, ebp (хотя они необходимы только при выделении памяти для локальных переменных, но в любом случае не причиняют вреда). Это тоже можно заменить одной инструкцией: leave. Вносим изменения:

_subtract:
    enter 0, 0            ; сохранение указателя базы предыдущего фрейма и настройка ebp
    ; Здесь я бы сохранил регистры вызываемой подпрограммы, но я ничего не 
    ; собираюсь изменять
    ; Тут начинается функция
    mov eax, [ebp+8]    ; копирование первого аргумента функции в eax. Скобки
                        ; означают доступ к памяти по адресу ebp+8
    sub eax, [ebp+12]   ; вычитание второго аргумента по адресу ebp+12 из 
                        ; первого аргумента
    ; Тут функция заканчивается, eax равен её возвращаемому значению
    ; Здесь я бы восстановил регистры, но они не сохранялись
    leave              ; восстановление указателя базы предыдущего фрейма
    ret

Написание некоторых основных функций

Усвоив соглашение о вызовах, можно приступить к написанию некоторых подпрограмм. Почему бы не обобщить код, который выводит "Hello world!", для вывода любых строк: функция _print_msg.

Здесь понадобится ещё одна функция _strlen для подсчёта длины строки. На C она может выглядеть так:

size_t strlen(char *s) {
    size_t length = 0;
    while (*s != 0)
    {           // начало цикла
        length++;
        s++;
    }           // конец цикла
    return length;
}

Другими словами, с самого начала строки мы добавляем 1 к возвращаемым значением для каждого символа, кроме нуля. Как только замечен нулевой символ, возвращаем накопленное в цикле значение. В ассемблере это тоже довольно просто: можно использовать как базу ранее написанную функцию _subtract:

_strlen:
    enter 0, 0          ; сохраняем указатель базы предыдущего фрейма и настраиваем ebp
    ; Здесь я бы сохранил регистры вызываемой подпрограммы, но я ничего не 
    ; собираюсь изменять
    ; Здесь начинается функция
    mov eax, 0          ; length = 0
    mov ecx, [ebp+8]    ; первый аргумент функции (указатель на первый
                        ; символ строки) копируется в ecx (его сохраняет вызывающая 
                        ; сторона, так что нам нет нужды сохранять)
_strlen_loop_start:     ; это метка, куда можно перейти
    cmp byte [ecx], 0   ; разыменование указателя и сравнение его с нулём. По
                        ; умолчанию память считывается по 32 бита (4 байта).
                        ; Иное нужно указать явно. Здесь мы указываем
                        ; чтение только одного байта (один символ)
    je _strlen_loop_end ; выход из цикла при появлении нуля
    inc eax             ; теперь мы внутри цикла, добавляем 1 к возвращаемому значению
    add ecx, 1          ; переход к следующему символу в строке
    jmp _strlen_loop_start  ; переход обратно к началу цикла
_strlen_loop_end:
    ; Здесь функция заканчивается, eax равно возвращаемому значению
    ; Здесь я бы восстановил регистры, но они не сохранялись
    leave               ; восстановление указателя базы предыдущего фрейма
    ret

Уже неплохо, верно? Сначала написать код на C может помочь, потому что большая его часть непосредственно преобразуется в ассемблер. Теперь можно использовать эту функцию в _print_msg, где мы применим все полученные знания:

_print_msg:
    enter 0, 0
    ; Здесь начинается функция
    mov eax, 0x04       ; 0x04 = системный вызов write()
    mov ebx, 0x1        ; 0x1 = стандартный вывод
    mov ecx, [ebp+8]    ; мы хотим вывести первый аргумент этой функции,
    ; сначала установим edx на длину строки. Пришло время вызвать _strlen
    push eax            ; сохраняем регистры вызываемой функции (я решил не сохранять edx)
    push ecx       
    push dword [ebp+8]  ; пушим аргумент _strlen в _print_msg. Здесь NASM
                        ; ругается, если не указать размер, не знаю, почему.
                        ; В любом случае указателем будет dword (4 байта, 32 бита)
    call _strlen        ; eax теперь равен длине строки
    mov edx, eax        ; перемещаем размер строки в edx, где он нам нужен
    add esp, 4          ; удаляем 4 байта со стека (один 4-байтовый аргумент char*)
    pop ecx             ; восстанавливаем регистры вызывающей стороны
    pop eax
    ; мы закончили работу с функцией _strlen, можно инициировать системный вызов
    int 0x80
    leave
    ret

И посмотрим плоды нашей тяжёлой работы, используя эту функцию в полной программе “Hello, world!”.

_start:
    enter 0, 0
    ; сохраняем регистры вызывающей стороны (я решил никакие не сохранять)
    push hello_world    ; добавляем аргумент для _print_msg
    call _print_msg
    mov eax, 0x01           ; 0x01 = exit()
    mov ebx, 0              ; 0 = без ошибок
    int 0x80

Хотите верьте, хотите нет, но мы рассмотрели все основные темы, которые нужны для написания базовых программ на ассемблере x86! Теперь у нас есть весь вводный материал и теория, так что полностью сосредоточимся на коде и применим полученные знания для написания нашего калькулятора RPN. Функции будут намного длиннее и даже станут использовать некоторые локальные переменные. Если хотите сразу увидеть готовую программу, вот она.

Для тех из вас, кто не знаком с обратной польской записью (иногда называемой обратной польской нотацией или постфиксной нотацией), то здесь выражения вычисляются с помощью стека. Поэтому нужно создать стек, а также функции _pop и _push для манипуляций с этим стеком. Понадобится ещё функция _print_answer, которая выведет в конце вычислений строковое представление числового результата.

Создание стека

Сначала определим для нашего стека пространство в памяти, а также глобальную переменную stack_size. Желательно изменить эти переменные так, чтобы они попали не в раздел .rodata, а в .data.

section .data
    stack_size: dd 0        ; создаём переменную dword (4 байта) со значением 0
    stack: times 256 dd 0   ; заполняем стек нулями

Теперь можно реализовать функции _push и _pop:

_push:
    enter 0, 0
    ; Сохраняем регистры вызываемой функции, которые будем использовать
    push eax
    push edx
    mov eax, [stack_size]
    mov edx, [ebp+8]
    mov [stack + 4*eax], edx    ; Заносим аргумент на стек. Масштабируем по
                                ; четыре байта в соответствии с размером dword
    inc dword [stack_size]      ; Добавляем 1 к stack_size
    ; Восстанавливаем регистры вызываемой функции
    pop edx
    pop eax
    leave
    ret

_pop:
    enter 0, 0
    ;  Сохраняем регистры вызываемой функции
    dec dword [stack_size]      ; Сначала вычитаем 1 из stack_size
    mov eax, [stack_size]
    mov eax, [stack + 4*eax]    ; Заносим число на верх стека в eax
    ; Здесь я бы восстановил регистры, но они не сохранялись
    leave
    ret

Вывод чисел

_print_answer намного сложнее: придётся конвертировать числа в строки и использовать несколько других функций. Понадобится функция _putc, которая выводит один символ, функция mod для вычисления остатка от деления (модуля) двух аргументов и _pow_10 для возведения в степень 10. Позже вы поймёте, зачем они нужны. Это довольно просто, вот код:

_pow_10:
    enter 0, 0
    mov ecx, [ebp+8]    ; задаёт ecx (сохранённый вызывающей стороной) аргументом 
                        ; функции
    mov eax, 1          ; первая степень 10 (10**0 = 1)
_pow_10_loop_start:     ; умножает eax на 10, если ecx не равно 0
    cmp ecx, 0
    je _pow_10_loop_end
    imul eax, 10
    sub ecx, 1
    jmp _pow_10_loop_start
_pow_10_loop_end:
    leave
    ret

_mod:
    enter 0, 0
    push ebx
    mov edx, 0          ; объясняется ниже
    mov eax, [ebp+8]
    mov ebx, [ebp+12]
    idiv ebx            ; делит 64-битное целое [edx:eax] на ebx. Мы хотим поделить
                        ; только 32-битное целое eax, так что устанавливаем edx равным 
                        ; нулю.
                        ; частное сохраняем в eax, остаток в edx. Как обычно, получить 
                        ; информацию по конкретной инструкции можно из справочников, 
                        ; перечисленных в конце статьи.
    mov eax, edx        ; возвращает остаток от деления (модуль)
    pop ebx
    leave
    ret

_putc:
    enter 0, 0
    mov eax, 0x04       ; write()
    mov ebx, 1          ; стандартный вывод
    lea ecx, [ebp+8]    ; входной символ
    mov edx, 1          ; вывести только 1 символ
    int 0x80
    leave
    ret

Итак, как мы выводим отдельные цифры в числе? Во-первых, обратите внимание, что последняя цифра числа равна остатку от деления на 10 (например, 123 % 10 = 3), а следующая цифра — это остаток от деления на 100, поделенный на 10 (например, (123 % 100)/10 = 2). В общем, можно найти конкретную цифру числа (справа налево), найдя (число % 10**n) / 10**(n-1), где число единиц будет равно n = 1, число десятков n = 2 и так далее.

Используя это знание, можно найти все цифры числа с n = 1 до n = 10 (это максимальное количество разрядов в знаковом 4-байтовом целом). Но намного проще идти слева направо — так мы сможем печатать каждый символ, как только находим его, и избавиться от нулей в левой части. Поэтому перебираем числа от n = 10 до n = 1.

На C программа будет выглядеть примерно так:

#define MAX_DIGITS 10
void print_answer(int a) {
    if (a < 0) { // если число отрицательное
        putc('-'); // вывести знак «минус»
        a = -a; // преобразовать в положительное число
    }
    int started = 0;
    for (int i = MAX_DIGITS; i > 0; i--) {
        int digit = (a % pow_10(i)) / pow_10(i-1);
        if (digit == 0 && started == 0) continue; // не выводить лишние нули
        started = 1;
        putc(digit + '0');
    }
}

Теперь вы понимаете, зачем нам эти три функции. Давайте реализуем это на ассемблере:

%define MAX_DIGITS 10

_print_answer:
    enter 1, 0              ; используем 1 байт для переменной "started" в коде C
    push ebx
    push edi
    push esi
    mov eax, [ebp+8]        ; наш аргумент "a"
    cmp eax, 0              ; если число не отрицательное, пропускаем этот условный 
                            ; оператор
    jge _print_answer_negate_end
    ; call putc for '-'
    push eax
    push 0x2d               ; символ '-'
    call _putc
    add esp, 4
    pop eax
    neg eax                 ; преобразуем в положительное число
_print_answer_negate_end:
    mov byte [ebp-4], 0     ; started = 0
    mov ecx, MAX_DIGITS     ; переменная i
_print_answer_loop_start:
    cmp ecx, 0
    je _print_answer_loop_end
    ; вызов pow_10 для ecx. Попытаемся сделать ebx как переменную "digit" в коде C.
    ; Пока что назначим edx = pow_10(i-1), а ebx = pow_10(i)
    push eax
    push ecx
    dec ecx             ; i-1
    push ecx            ; первый аргумент для _pow_10
    call _pow_10
    mov edx, eax        ; edx = pow_10(i-1)
    add esp, 4
    pop ecx             ; восстанавливаем значение i для ecx
    pop eax
    ; end pow_10 call
    mov ebx, edx        ; digit = ebx = pow_10(i-1)
    imul ebx, 10        ; digit = ebx = pow_10(i)
    ; вызываем _mod для (a % pow_10(i)), то есть (eax mod ebx)
    push eax
    push ecx
    push edx
    push ebx            ; arg2, ebx = digit = pow_10(i)
    push eax            ; arg1, eax = a
    call _mod
    mov ebx, eax        ; digit = ebx = a % pow_10(i+1), almost there
    add esp, 8
    pop edx
    pop ecx
    pop eax
    ; завершение вызова mod
    ; делим ebx (переменная "digit" ) на pow_10(i) (edx). Придётся сохранить пару 
    ; регистров, потому что idiv использует для деления и edx, eax. Поскольку 
    ; edx является нашим делителем, переместим его в какой-нибудь 
    ; другой регистр
    push esi
    mov esi, edx
    push eax
    mov eax, ebx
    mov edx, 0
    idiv esi            ; eax хранит результат (цифру)
    mov ebx, eax        ; ebx = (a % pow_10(i)) / pow_10(i-1), переменная "digit" в коде C
    pop eax
    pop esi
    ; end division
    cmp ebx, 0                        ; если digit == 0
    jne _print_answer_trailing_zeroes_check_end
    cmp byte [ebp-4], 0               ; если started == 0
    jne _print_answer_trailing_zeroes_check_end
    jmp _print_answer_loop_continue   ; continue
_print_answer_trailing_zeroes_check_end:
    mov byte [ebp-4], 1     ; started = 1
    add ebx, 0x30           ; digit + '0'
    ; вызов putc
    push eax
    push ecx
    push edx
    push ebx
    call _putc
    add esp, 4
    pop edx
    pop ecx
    pop eax
    ; окончание вызова putc
_print_answer_loop_continue:
    sub ecx, 1
    jmp _print_answer_loop_start
_print_answer_loop_end:
    pop esi
    pop edi
    pop ebx
    leave
    ret

Это было тяжкое испытание! Надеюсь, комментарии помогают разобраться. Если вы сейчас думаете: «Почему нельзя просто написать printf("%d")?», то вам понравится окончание статьи, где мы заменим функцию именно этим!

Теперь у нас есть все необходимые функции, осталось реализовать основную логику в _start — и на этом всё!

Вычисление обратной польской записи

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

Например, если мы хотим вычислить 84/3+6* (это выражение также можно записать в виде 6384/+*), процесс выглядит следующим образом:

Шаг	Символ	Стек перед	Стек после
1	8	[]	[8]
2	4	[8]	[8, 4]
3	/	[8, 4]	[2]
4	3	[2]	[2, 3]
5	+	[2, 3]	[5]
6	6	[5]	[5, 6]
7	*	[5, 6]	[30]

Если на входе допустимое постфиксное выражение, то в конце вычислений на стеке остаётся лишь один элемент — это и есть ответ, результат вычислений. В нашем случае число равно 30.

В ассемблере нужно реализовать нечто вроде такого кода на C:

int stack[256];         // наверное, 256 слишком много для нашего стека
int stack_size = 0;

int main(int argc, char *argv[]) {
    char *input = argv[0];
    size_t input_length = strlen(input);
    
    for (int i = 0; i < input_length; i++) {
        char c = input[i];
        if (c >= '0' && c <= '9') { // если символ — это цифра
            push(c - '0'); // преобразовать символ в целое число и поместить в стек
        } else {
            int b = pop();
            int a = pop();
            if (c == '+') {
                push(a+b);
            } else if (c == '-') {
                push(a-b);
            } else if (c == '*') {
                push(a*b);
            } else if (c == '/') {
                push(a/b);
            } else {
                error("Invalid input\n");
                exit(1);
            }
        }
    }
    
    if (stack_size != 1) {
        error("Invalid input\n");
        exit(1);
    }
    
    print_answer(stack[0]);
    exit(0);
}

Теперь у нас имеются все функции, необходимые для реализации этого, давайте начнём.

_start:
    ; аргументы _start получаются не так, как в других функциях.
    ; вместо этого esp указывает непосредственно на argc (число аргументов), а 
    ; esp+4 указывает на argv. Следовательно, esp+4 указывает на название
    ; программы, esp+8 - на первый аргумент и так далее
    mov esi, [esp+8]         ; esi = "input" = argv[0]
    ; вызываем _strlen для определения размера входных данных
    push esi
    call _strlen
    mov ebx, eax             ; ebx = input_length
    add esp, 4
    ; end _strlen call
    mov ecx, 0               ; ecx = "i"
_main_loop_start:
    cmp ecx, ebx             ; если (i >= input_length)
    jge _main_loop_end
    mov edx, 0
    mov dl, [esi + ecx]      ; то загрузить один байт из памяти в нижний байт
                             ; edx. Остальную часть edx обнуляем.
                             ; edx = переменная c = input[i]
    cmp edx, '0'
    jl _check_operator
    cmp edx, '9'
    jg _print_error
    sub edx, '0'
    mov eax, edx             ; eax = переменная c - '0' (цифра, не символ)
    jmp _push_eax_and_continue
_check_operator:
    ; дважды вызываем _pop для выноса переменной b в edi, a переменной b - в eax
    push ecx
    push ebx
    call _pop
    mov edi, eax             ; edi = b
    call _pop                ; eax = a
    pop ebx
    pop ecx
    ; end call _pop
    cmp edx, '+'
    jne _subtract
    add eax, edi                 ; eax = a+b
    jmp _push_eax_and_continue
_subtract:
    cmp edx, '-'
    jne _multiply
    sub eax, edi                 ; eax = a-b
    jmp _push_eax_and_continue
_multiply:
    cmp edx, '*'
    jne _divide
    imul eax, edi                ; eax = a*b
    jmp _push_eax_and_continue
_divide:
    cmp edx, '/'
    jne _print_error
    push edx                     ; сохраняем edx, потому что регистр обнулится для idiv
    mov edx, 0
    idiv edi                     ; eax = a/b
    pop edx
    ; теперь заносим eax на стек и продолжаем
_push_eax_and_continue:
    ; вызываем _push
    push eax
    push ecx
    push edx
    push eax          ; первый аргумент
    call _push
    add esp, 4
    pop edx
    pop ecx
    pop eax
    ; завершение call _push
    inc ecx
    jmp _main_loop_start
_main_loop_end:
    cmp byte [stack_size], 1      ; если (stack_size != 1), печать ошибки
    jne _print_error
    mov eax, [stack]
    push eax
    call _print_answer
    ; print a final newline
    push 0xA
    call _putc
    ; exit successfully
    mov eax, 0x01           ; 0x01 = exit()
    mov ebx, 0              ; 0 = без ошибок
    int 0x80                ; здесь выполнение завершается
_print_error:
    push error_msg
    call _print_msg
    mov eax, 0x01
    mov ebx, 1
    int 0x80

Понадобится ещё добавить строку error_msg в раздел .rodata:

section .rodata
    ; Назначаем на некоторые байты error_msg. Псевдоинструкция db в NASM
    ; позволяет использовать однобайтовое значение, строковую константу или их 
    ; сочетание. 0xA = новая строка, 0x0 = нуль окончания строки
    error_msg: db "Invalid input", 0xA, 0x0

И мы закончили! Удивите всех своих друзей, если они у вас есть. Надеюсь, теперь вы с большей теплотой отнесётесь к языкам высокого уровня, особенно если вспомнить, что многие старые программы писали полностью или почти полностью на ассемблере, например, оригинальный RollerCoaster Tycoon!

Весь код здесь. Спасибо за чтение! Могу продолжить, если вам интересно.

Дальнейшие действия

Можете попрактиковаться, реализовав несколько дополнительных функций:

1. Выдать вместо segfault сообщение об ошибке, если программа не получает аргумент.
2. Добавить поддержку дополнительных пробелов между операндами и операторами во входных данных.
3. Добавить поддержку многоразрядных операндов.
4. Разрешить ввод отрицательных чисел.
5. Заменить _strlen на функцию из стандартной библиотеки C, а _print_answer заменить вызовом printf.

Дополнительные материалы

• «Руководство по ассемблеру x86 университета Вирджинии» — более подробное изложение многих тем, рассмотренных нами, в том числе дополнительная информация по всем популярным инструкциям x86.
• «Искусство выбора регистров Intel». Хотя большинство регистров x86 — регистры общего назначения, но у многих есть историческое значение. Следование этим соглашениям может улучшить читаемость кода и, как интересный побочный эффект, даже немного оптимизировать размер двоичных файлов.
• NASM: Intel x86 Instruction Reference — полное руководство по всем малоизвестным инструкциям x86.