Реклама

Наш канал:

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

Ханойская башня

Теперь, когда мы изучили уровень архитектуры набора команд трех машин, нам нужно все обобщить. Давайте подробно рассмотрим все тот же пример решения задачи «Ханойская башня»). В листинге 5.6 приведена версия этой программы на языке Java. В следующих подразделах мы предложим программы на ассемблере Pentium 4 и UltraSPARC III.

Однако чтобы избежать проблем с вводом-выводом Java, для машин Pentium 4 и UltraSPARC III мы будем транслировать версию программы не на Java, а на С. Единственное различие — это замена Java-оператора println стандартным оператором языка С:

printf("Переместить диск с %й на %й\п". i, j)

Синтаксис строки в операторе printf не важен (строка печатается буквально за исключением символов *d, означающих, что следующее целое число будет представлено в десятичной системе счисления). Здесь важно только то, что процедура вызывается с тремя параметрами: форматирующей строкой и двумя целыми числами.

Мы использовали язык С для Pentium 4 и UltraSPARC III, поскольку библиотека ввода-вывода Java для этих машин недоступна, в отличие от библиотеки С ввода-вывода. Разница минимальна — всего один оператор вывода строки на экран.

Решение задачи «Ханойская башня» на ассемблере Pentium 4

В листинге 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