Реклама:

В листинге 5.7 приведен возможный вариант программы на языке С для компьютера Pentium 4 после трансляции. Регистр ЕВР используется в качестве указателя фрейма. Первые два слова требуются для сборки, поэтому первый параметр п (или N, поскольку регистр символов в макроассемблере не важен) находится в ячейке ЕВР + 8, а за ним следуют параметры i и j в ячейках ЕВР + 12 и ЕВР + 16 соответственно. Локальная переменная к находится в ЕВР + 20.

Листинг 5.7. Решение задачи "Ханойская башня" для Pentium 4

.586 ; компилируется для Pentium .MODEL FLAT

PUBLIC _towers ; экспорт 'towers'

EXTERN _printf:NEAR ; импорт printf .CODE

_towers: PUSH EBP ; сохраняет EBP (указатель фрейма)

MOV EBP, ESP ; устанавливает новый

; указатель фрейма над ESP

CMP[EBP+8].l ; if(n-1)

JNE LI ; переход, если n не равно 1

MOV ЕАХ, [EBP+16] ; printf ("...", i. j);

PUSH ЕАХ ; сохранение параметров i, j и формата

MOV ЕАХ, [EBP+12] ; строка помещается в стек

PUSH ЕАХ ; в обратном порядке (требование языка С) PUSH OFFSET FLAT:format ; OFFSET FLAT - это адрес формата

CALL _printf ; вызов процедуры printf

ADD ESP, 12 ; удаление параметров из стека

JMP Done ; завершение

LI: MOV ЕАХ,6 ; начало вычисления k=6-i-j

SUB ЕАХ, [EBP+12] ; EAX=6-i

SUB EAX, [EBP+16] : EAX=6-i-j

MOV [EBP+20], EAX ; k=EAX

PUSH EAX ; начало процедуры towers(n-1. i. k)

MOV EAX, [EBP+12] ; EAX=i

PUSH EAX : помещает в стек i

MOV EAX, [EBP+8] ; EAX=n

DEC EAX ; EAX=n-l

PUSH EAX : помещает в стек n-1

CALL _towers ; вызов процедуры towers(n-l, i, 6-i-j)

ADD ESP, 12 : удаляет параметры из стека

MOV ЕАХ, [EBP+16] : начало процедуры towers (1, i. j)

PUSH EAX ; помещает в стек j

MOV EAX, [EBP+12] ; EAX=i

PUSH EAX ; помещает в стек i

PUSH 1 : помещает в стек 1

CALL _towers ; вызывает процедуру towersd, i, j)

ADD ESP, 12 ; удаляет параметры из стека

MOV ЕАХ, [EBP+12] ; начало процедуры towers(n-1, 6-i-j, i)

PUSH EAX : помещает в стек i

MOV EAX, [EBP+20] : EAX=k

PUSH EAX : помещает в стек k

MOV EAX, [EBP+8] ; EAX = n

DEC EAX ; EAX=n-l

PUSH EAX : помещает в стек n-1

CALL _towers ; вызов процедуры towers(n-1, 6-i-j, i)

ADD ESP, 12 ; корректировка указателя стека

Done: LEAVE ; подготовка к выходу

RET 0 ; возврат к вызывающей программе

.DATA

format DB "Переместить диск с %6 на ; форматирующая строка

END

Процедура начинается с создания нового фрейма в конце старого. Для этого значение регистра ESP копируется в указатель фрейма ЕВР. Затем п сравнивается с 1, и если n > 1, совершается переход к оператору else. Тогда код then помещает в стек три значения: адрес форматирующей строки, i и j, а затем вызывает сам себя.

Параметры помещаются в стек в обратном порядке, поскольку это требование языка С. Необходимо поместить указатель на форматирующую строку в вершину стека. Процедура printf имеет переменное число параметров, и если параметры будут помещаться в стек в прямом порядке, то процедура не сможет узнать, в каком месте стека находится форматирующая строка.

После вызова процедуры к регистру ESP прибавляется 12, чтобы удалить параметры из стека. На самом деле они не удаляются из памяти, но изменение регистра ESP делает их недоступными через обычные операции со стеком.

Выполнение части el se начинается с метки L1. Здесь сначала вычисляется выражение 6 - i - j, а полученное значение сохраняется в переменной к. Сохранение значения в переменной к избавляет от необходимости вычислять это выражение во второй раз.

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

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

Ханойская башня || Оглавление || Решение задачи "Ханойская башня" на ассемблере UltraSPARC III