Особенности реализации рекурсивных программ в ассемблере
Рекурсивные алгоритмы предполагают реализацию в виде процедуры, которая сама себя вызывает. При этом необходимо обеспечить, чтобы каждый последовательный вызов процедуры не разрушал данных, полученных в результате предыдущего вызова. Для этого, каждый вызов должен иметь свой набор параметров, регистры и все промежуточные результаты. Средства модульного программирования ассемблера позволяют выполнить это требование и реализовать рекурсивный алгоритм. Для сохранения данных очередного вызова и передачи параметров следующей активации процедуры лучше использовать стек. А удобную организацию стека позволяют организовать структуры.
Структура в ассемблере аналогична структурам (записям) в языках высокого уровня. Структура представляет собой шаблон с описаниями форматов данных, который можно накладывать на различные участки памяти, чтобы затем обращаться к полям этих участков памяти с помощью имен, определенных в описании структуры. Особенно удобны структуры при обращении к областям памяти, не входящим в сегменты данных и кода программы, т.е. полям, которые нельзя описать с помощью символических имен.
Формат описания структуры:
<Имя структуры> STRUCT
<Описание полей>
<Имя структуры> ENDS
где <Имя структуры> – символьное имя структуры,
<Описание полей> – любой набор псевдокоманд определения переменных или вложенных структур.
Эта последовательность директив описывает, но не размещает в памяти структуру данных. Для чтения или записи элемента структуры применяется точечная нотация:
<Имя структуры>. <Имя поля>.
Кроме того, структуры используются, когда в программе многократно повторяются сложные коллекции данных с единым строением, но с различными значениями полей. В этом случае, для создания такой структуры в памяти достаточно использовать имя структуры как псевдокоманды по шаблону:
<Имя переменной> <Имя структуры>
<<Значение поля 1>, <Значение поля 2>,…<Значение поля n>>
Например, пусть в программе, обрабатывающей данные о студентах, необходимо объявить несколько блоков данных с однородными сведениями о нескольких студентах. Такие данные удобно оформить в виде структуры с именем Student:
Student struct
Family db 20 dup (' ' ) ; Фамилия студента
Name db 15 dup(' ') ; Имя
Birthdata db ' / / ' ; Дата рождения
Student ends
Определить с помощью этой структуры в программе две переменные с именами stud1 и stud2 можно следующим обращением:
stud1 Student <’Иванов’,’Петр’,’23/12/72’>
stud2 Student <’Сидоров’,’Павел’,’12/05/84’> .
При создании рекурсивных процедур STRUCT используется для описания шаблона данных очередного вызова (фрейма активации). При обращении к данным фрейма или сохранении фрейма очередной активации обращение происходит с помощью полей структуры, что значительно упрощает процессы чтения и записи в стек данных активации.
Пример 1.6. Написать рекурсивную процедуру вычисления факториала числа.
В процедуре определения факториала числа воспользуемся следующими утверждениями:
N*(N-1)! , при N0 – рекурсивное утверждение;
N! =
1 , при N=0 – базисное утверждение.
Таким образом, каждая активация должна иметь доступ и сохранять результат вычисления и текущее значение числа для расчета N*(N-1). Кроме того, при очередном вызове процедура должна сохранять регистр базы параметров (EBP) и адрес возврата. Поэтому фрейм активации включает:
значение регистра EBP – 4 байта,
адрес возврата для случая ближнего вызова – 4 байта,
число N на данном уровне рекурсии – 2 байта,
адрес результата – 4 байта.
Для работы с фреймом опишем структуру, перечисляя поля в том порядке, в котором они будут размещаться в стеке (рисунок 1.6).
F
RAME
STRUCT
SAVE_EBP DD ?
SAVE_EIP DD ?
Рисунок 1.6 – Структура
Frame
RESULT_ADDR DD ?
FRAME ENDS
Текст программы:
.586
.MODEL flat, stdcall
OPTION CASEMAP:NONE
Include kernel32.inc
Include masm32.inc
IncludeLib kernel32.lib
IncludeLib masm32.lib
FRAME STRUCT
SAVE_EBP DD ?
SAVE_EIP DD ?
n DW ?
result_addr DD ?
FRAME ENDS
.CONST
MsgExit DB "Press Enter to Exit",0AH,0DH,0
.DATA
n DW 5 ; N – исходное число
.DATA?
inbuf DB 100 DUP (?)
result DD ? ; резервирование памяти под результат
.CODE
Start:
push offset result ; запись в стек адреса результата
push n ; запись в стек исходного числа
call fact
XOR EAX,EAX
Invoke StdOut,ADDR MsgExit
Invoke StdIn,ADDR inbuf,LengthOf inbuf
Invoke ExitProcess,0
fact PROC
push EBP
mov EBP,ESP
push EBX
push AX
; извлечение из стека адреса результата
mov EBX,FRAME.result_addr[EBP]
mov AX,FRAME.n[EBP] ; извлечение из стека N
cmp AX,0
je done ; выход из рекурсии
push EBX ; сохранение в стеке адреса результата
dec AX ; N=N-1
push AX ; сохранение в стеке очередного N
call fact ; рекурсивный вызов
; извлечение из стека адреса результата
mov EBX,FRAME.result_addr[EBP]
; вычисление результата очередной активации
mov AX,[EBX]
mul FRAME.n[EBP]
jmp short return
done: mov EAX,1 ; если ax=0 , то факториал равен 1
; запоминаем результат активации
return: mov [EBX],AX
pop AX
pop EBX
pop EBP
ret 6
fact ENDP
End Start
На рисунке 1.7 показано содержимое стека во время выполнения рекурсивной процедуры (3 активации).
Рисунок 1.7 – Содержимое стека в процессе рекурсивного спуска