Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.320

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

А теперь рассмотрим ту же программу на ассемблере UltraSPARC III (листинг 5.8). Поскольку программа для UltraSPARC III совершенно нечитабельна даже после длительной практики, мы решили определить несколько символов, чтобы прояснить дело. Чтобы такая программа работала, ее перед ассемблированием нужно пропустить через программу под названием срр (препроцессор С). Здесь мы используем строчные буквы, поскольку ассемблер UltraSPARC III этого требует (это на тот случай, если читатели захотят набрать эту программу и запустить).

Листинг 5.8. Решение задачи «Ханойская башня» для UltraSPARC III

Idefine N %i 0 /* N - это входной параметр 0 */

Idefine I %М /* I - это входной параметр 1 */

Idefine J %i2 /* J - это входной параметр 2 */

Idefine К Я10 /* К - это локальная переменная 0 */