Пильщиков

160 Программирование на языке ассемблера IBM PC Глава 1

гистрами, что и процедура. Дело в том, что исходный текст программы в дальнейшем может измениться (а это происходит очень часто), и может оказаться так, что после этих изменений основной программе потребуются эти регистры. И хорошо, если мы при этом вспомним, что надо подправить процедуру. Чаще же всего про это забывают, и потому основная программа и процедура начинают мешать друг другу. Поэтому лучше сразу предусмотреть в процедуре сохранение регистров, тогда при любых изменениях основная программа может не волноваться за свои регистры. (Для поддержки этого стиля программирования в систему команд ПК, начиная с процессора 80186, даже введены специальные команды PUSHA и РОРА, которые позволяют сохранять в стеке и восстанавливать из стека значения регистров общего назначения - см. разд. 8.2.)

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

9ЗА. Передача параметров сложных типов

Теперь рассмотрим еще один случай передачи параметра по ссылке - когда параметром является данное сложного типа (массив, структура и т. п.). Даже если процедура не меняет это данное, ей все равно обычно передается не само данное (для него может просто не хватить регистров), а его начальный адрес. Зная этот адрес, процедура может легко добраться до любой части этого данного.

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

X DB 100 DUP(?)

Y DB 25 DUP(?)

и требуется записать в регистр DL сумму максимальных элементов этих массивов: DL=max(X[i])+max(Y[i]). у

Поскольку здесь дважды приходится находить максиматьный ачемент массива, то, чтобы не повторяться, имеет смысл описать это действие в виде процедуры. Назовем ее МАХ и опишем ее при условии, что начальный адрес массива передается процедуре через регистр ВХ, количество апеменгов в массиве - через регистр СХ, а свой результат процедура возвращает через регистр AL. При этих соглашениях описание процедуры и фрагмент основной программы, решающий поставленную задачу, выглядят так:

;процедура	MAX:	A L = m a x ( W [ 0 . . N - 1 ] ) , г д е		ВХ=нач.адрес W, CX=N
MAX PROC
PUSH	ВХ	; с п а с т и р е г и с т р ы ,
PUSH	СХ	; используемые		в процедуре
MOV	AL, 0	;AL = 0	( н а ч . з н а ч е н и е максимума)
МАХ1: CMP	[ВХ],AL
JLE МАХ2		;W[i]>AL	==> AL:=W[i]
MOV AL,[BX]
MAX 2: INC BX
LOOP MAX1
POP	CX	; в о с с т а н о в и т ь		р е г и с т р ы

					Процедуры	161
POP ВХ
RET		;выход из	процедуры
MAX ENDP
;фрагмент	основной	программы для	вычисления	DLa=max(X[i] )+max( Y [ i ] )
LEA ВХ,Х		;ВХ=нач . адрес массива			X
MOV	СХ,100	;СХв число	элементов	в	X
CALL	MAX	; A L s m a x ( X [ i ] )
MOV	DL,AL	; с п а с т и AL
LEA	BXrY	;ВХ*нач . адрес массива			Y
MOV	СХ,25	;СХ=*число	элементов	в	Y
CALL MAX		;AL=max(Y[i])
ADD DL,AL

9 А. Передача параметров через стек

Передача параметров через регистры - вещь удобная и используется очень часто. Однако делать так можно, только если параметров немного; если же параметров много, то на них попросту не хватит регистров. В таком случае используют иной способ передачи параметров - через стек: основная программа записывает фактические параметры (их значения или адреса) в стек, а процедура затем их оттуда извлекает. Конкретно реализовать эту идею можно по-разному, мы рассмотрим тот способ передачи параметров через стек, который используется транслятором языка Турбо Паскаль.

Пусть процедура Р имеет к параметров: Р(а1,а2,...,ак). Договоримся, чгго перед обращением к процедуре основная программа записывает параметры в стек. В каком порядке? Это решает автор программы. Мы будем считать, что параметры записываются в стек слева направо: сначала записывается 1-й параметр, затем 2-й и т. д. Если для определенности договориться, что каждый параметр имеет размер слова и его не надо вычислять (эти ограничения легко обходятся), тогда команды основной программы, реализующие обращение к процедуре, будут следующими (справа показано состояние стека после выполнения этих команд, т. е. на входе в процедуру):

Теперь начинает работать процедура. И сразу возникает проблема: как ей добраться до параметров? Это проблема доступа к элементам стека без считывания их из стека. Как она решается, мы уже знаем: надо воспользоваться регистром BP, т. е. заслать в него адрес вершины стека (содержимое регистра SP), а затем использовать выражения вида [BP+i] для доступа к параметрам процедуры. Однако здесь есть одно "но": мы портим регистр BP, а он может использоваться в основной программе. Поэтому сначала надо спасти прежнее значение этого

•ДИАЛОГ-МИФИ-

162 Программирование на языке ассемблера IBM PC Глава 1

регистра и только затем уж пересылать в него значение регистра SP. Таким образом, выполнение процедуры должно начинаться со следующих команд, которые называют "входными" действиями процедуры (справа изображено состояние стека после этих команд; для определенности считаем, что процедура близкая, поэтому адрес возврата занимает одно слово в стеке):

Как видно из рисунка, после записи в стек старого значения BP (ВРст) для доступа к параметрам процедуры надо использовать следующие выражения: [ВР+4] - для доступа к последнему параметру, [ВР+6] - для доступа к предпоследнему параметру и т. д. Например, считывание последнего параметра в регистр АХ (АХ:=ак) осуществляется командой MOV АХ,[ВР+4].

Далее идут команды собственно процедуры. После их завершения процедура обязана выполнить действия, которые называются "выходными". Рассмотрим их. Прежде всего отметим, что к этому моменту стек должен быть в том же состоянии, в каком он был после "входных" действий. (Если это не так, то восстановить данное состояние можно командой MOV SP,BP.) Тогда к концу работы процедуры в вершине стека будет находиться старое значение регистра BP. Считываем его и восстанавливаем BP. Теперь в вершине стека окажется адрес возврата. Казалось бы, можно выполнить команду RET и уйти из процедуры, однако это не так - надо еще очистить стек от параметров, которые уже не нужны. Кто должен делать эту очистку - процедура или основная программа? Конечно, это может сделать основная программа, для чего в ней после команды CALL Р надо выполнить команду ADD SP,2*k. Однако лучше, если очистку стека будет делать сама процедура. Дело в том, что обращений к процедуре много, поэтому в основной программе команду ADD придется выписывать многократно, а процедура одна, поэтому в ней такую команду надо выписать только раз. Это общее правило: если что-то может сделать и основная программа, и процедура, то лучше, если это "что-то" будет делать процедура. Так меньше команд получается.

Итак, процедура должна сначала очистить стек от параметров и только затем передать управление по адресу возврата. Чтобы упростить реализацию этой пары действий, в систему команд ПК введен расширенный вариант команды RET - с непосредственным операндом, который трактуется как число без знака:

RET i l 6

По этой команде сначала из стека удаляется адрес возврата, затем стек очищается на указанное операндом число байтов и далее выполняется переход по адресу возврата:

с т е к - > I P , [ с т е к - > C S , ] S P : « S P + i l 6

Процедуры

163

(действие "стек -> CS" выполняется лишь при дальнем возврате).

Сделаем несколько замечаний. Во-первых, команда RET - это на самом деле команда RET 0, т. е. возврат без очистки стека. Во-вторых, операнд команды указывает, на сколько байтов, а не слов надо очищать стек, поэтому для очистки стека от к параметров, каждый из которых имеет размер слова, надо указывать

операнд 2* к,		а не к. В-третьих, в операнде не должен учитываться адрес воз-
врата - команда RET считывает его до очистки стека.
С учетом всего сказанного "выходные" действия процедуры таковы:
;"выходные"		д е й с т в и я процедуры
POP	BP	; в о с с т а н о в и т ь	с т а р о е	значение BP
RET	2*k	; о ч и с т к а с т е к а	от к	п а р а м е т р о в - с л о в и в о з в р а т
Р ENDP

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

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

В качестве конкретного примера опишем процедуру NULL(A,N), которая обнуляет N байтов памяти (в сегменте данных) начиная с адреса А, при условии, что адрес первого параметра (А) и значение второго параметра (N) передаются через стек. Описание процедуры приведено справа, а слева показана реатизация

обращения NULL(X,100), по которому обнуляется				100-байтовый массив X:
X DB 100	DUP(?)	NULL PROC
. . .		PUSH	BP	;"входные"		действия
; в ы з о в NULL(X, 10 0 )		MOV	BP,SP
LEA AX, X		PUSH	ВХ		; с п а с т и ВХ и CX
PUSH AX	; а д р . Х - > с т е к	PUSH	CX		;	("над" ВРст)
MOV AX,100		MOV	CX,[BP+4]		;CX=A
PUSH AX	; 1 0 0 - > с т е к	MOV	BX,[BP+6]		;BX=N
CALL NULL		NULLl: MOV	BYTE	PTR [BX],0	;обнуление
		INC	BX		; A [ 0 . . N - 1 ]
		LOOP NULLl
		POP	CX	; в о с с т а н .		CX	и BX
		POP BX
		POP	BP	;"выходные"			действия
		RET	4
		NULL ENDP

•ДИАЛОГ-МИФИ-

164	Программирование на языке ассемблера IBM PC Глава 1

9J5. Локальные данные процедур

Во многих процедурах не возникает проблемы с хранением локальных данных (величин, нужных только на время выполнения процедуры) - для них достаточно и регистров. Однако если в процедуре много локальных данных, тоща возникает вопрос: где отводить место для них? Конечно, можно выделить место в сегменте данных, но это плохо, т. к. большую часть времени это место памяти будет пропадать зря. Лучше выделять это место в стеке: при входе в процедуру в вершине стека "захватывается" нужное число байтов для локальных данных, а перед выходом это место освобождается. В таком случае место в памяти занимается только на время выполнения процедуры.

Такой "захват" места в стеке можно делать как в случае передачи параметров процедуре через регистры, так и в случае передачи параметров через стек. Для этого надо запомнить в стеке текущее значение регистра BP и затем установить его на вершину стека (при передаче параметров через стек это есть ничто иное, как "входные" действия), после чего надо уменьшить значение указателя стека SP на число "захватываемых" байтов. Например, если некоторой процедуре Р требуется 3 байта (скажем, 2 байта под локальную переменную А и 1 байт под локальную переменную В), тогда указанные действия реализуются следующими командами (справа изображено состояние стека после этих команд):

После этого доступ к локальным данным осуществляется с помощью выраже-

ний вида [ВР-k];		например,	[ВР-2]		- это		адрес	локальной переменной А,
а [ВР-3] - адрес локальной переменной В.
При завершении работы процедуры надо выполнить такие действия:
MOV	SP,BP	; о т к а з от м е с т а		для	локальных			данных
POP	BP	; в о с с т а н о в л е н и е		с т а р о г о		з н а ч е н и я BP
RET		; ( и л и RET n)	-	в о з в р а т		из	процедуры

РENDS

Вкачестве конкретного примера опишем близкую процедуру DIF, которая подсчитывает, сколько различных символов входит в заданную строку (символьный массив), при условии, что начальный адрес строки передается через регистр ВХ, а длина строки - через СХ, а результат возвращается через АХ.

Воспользуемся	следующим	алгоритмом. Заводим в		стеке локальный		массив
из 256 байтов -	по одному	на каждый возможный		символ,	причем	символу
с кодом к поставим в соответствие			байт стека с адресом [ВР-256+k], т. е.
нумеруем элементы этого стекового			массива "сверху вниз", и обнуляем этот
массив. Затем просматриваем заданную строку и для				каждого	входящего в нее

Процедуры

165

с и м в о ла записываем

1 в соответствующий элемент локального массива; тем

самым в этом массиве будут отмечены все символы, к о т о р ы е хотя бы раз

входили

в строку. В конце подсчитываем ч и с л о единиц в локальном массиве .

DIF

PROC

; " в х о д н ы е "

действия

PUSH BP

MOV BP,SP

SUB

SP,256

; з а н я т ь

м е с т о

в

с т е к е

под

л о к .

м а с с и в

PUSH

ВХ

; с п а с т и р е г и с т р ы ,

используемые

в процедуре

PUSH СХ

PUSH

SI

;обнуление

локального м а с с и в а

MOV

AX,СХ

; с о х р а н и т ь

длину

строки

MOV

СХ,256

;длина

л о к а л ь н о г о

массива

MOV

S I , 0

; и н д е к с

в

этом

массиве

( о т 0 до

255)

DIF1:

MOV

BYTE

PTR

[ B P - 2 5 6 + S I ] , О

INC

SI

LOOP

DIF1

MOV

CX,AX

; в о с с т а н о в и т ь

в

CX длину

с т р о к и

;просмотр

строки и

з а п и с ь 1 в локальный

массив

MOV АН,0

; д л я расширения

AL —>

АХ

DIF2:

MOV

AL,[BX]

; к о д о ч е р е д н о г о

символа с т р о к и

MOV

SI,АХ

; п е р е п и с ь

е г о

в

модификатор SI

MOV

BYTE

PTR

[ B P - 2 5 6 + S I ] ,1

; запись

1

в

л о к .

м а с с и в

INC

ВХ

; а д р е с следующего

символа

LOOP

DIF2

; п о д с ч е т числа

1 в

локальном м а с с и в е

MOV

АХ,0

; с ч е т ч и к

единиц

MOV

СХ,256

;длина

л о к а л ь н о г о

массива

MOV

S I , 0

; и н д е к с

в

этом

массиве

DIF3:

CMP

BYTE

PTR

[ B P - 2 5 6 + S I ] , 1

JNE

DIF4

INC AX

DIF4:

INC

SI

LOOP

DIF3

;"выходные"

действия

POP

SI

; в о с с т а н о в и т ь

регистры

POP CX

POP BX

0

MOV

SP,BP

; о с в о б о д и т ь

с т е к

от

л о к .

м а с с и в а

POP

BP

в о с с т а н о в и т ь

с т а р о е

значение BP

RET

DIF

ENDP

•ДИАЛОГ-МИФИ-

166Программирование на языке ассемблера IBM PC Глава 1

9.6.Рекурсивные процедуры

Напомним, что процедура называется рекурсивной, если она обращается сама к себе непосредственно (прямая рекурсия) или через другие процедуры (косвенная рекурсия). Мы не будем объяснять, как следует описывать рекурсивные процедуры (это не тема данной книги), а будем считать, что уже имеется описание рекурсивной процедуры и наша задача - рассмотреть, как это описание реализуется на ЯА. Учитывая, что многие программисты боятся рекурсии, сразу отметим, что ничего сложного в этой реализации нет, надо лишь придерживаться определенных правил, о которых здесь и будет рассказано.

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

Как частный случай, вызываемой процедурой Q может быть сама вызывающая процедура Р (Q=P), и тогда Р окажется рекурсивной процедурой. Таким образом, в рекурсивной процедуре есть команда вызова ее самой, т. е. передача управления на ее начало (мы ограничимся рассмотрением только случая прямой рекурсии):

(На строчки с г пока не обращать внимание.)

Отметим, что рекурсивное (повторное) обращение лучше рассматривать не как вызов самой процедуры, а как вызов ее копии: можно считать, что имеется не один экземпляр процедуры, а много таких экземпляров, и при рекурсивном обращении мы из одного экземпляра вызываем другой экземпляр. Такая трактовка рекурсивных вызовов более наглядна и понятна, ее мы и будем придерживаться в дальнейшем.

Поскольку рекурсивная процедура вызывает саму себя (свою копию), естественно возникает вопрос: а не зациклится ли она, выйдет ли она когда-нибудь из рекурсии? Ответ: не зациклится, если она описана правильно, если в ней есть нерекурсивная ветвь, т. е. такой путь вычисления, на котором рекурсивный вызов обходится, и если при каком-то обращении вычисление пойдет по этой ветви.

Пусть, к примеру, при первом (из основной программы) вызове процедуры Р внутренняя команда CALL сработает, а при втором (рекурсивном) вызове она уже обходится. Тогда происходит следующее: основная программа вызывает первую копию процедуры Р и заносит в стек адрес возврата а (см. рис. б). В этой копии выполняется команда CALL Р, по которой в стек заносится адрес возврата b

Процедуры 167

(см. рис. в) и передается управление на начало второй копии процедуры. Согласно нашему предположению, команда CALL в этой копии не выполняется, поэтому вычисление доходит до команды RET, которая считывает из стека адрес возврата b и передает по нему управление (см. рис. б). Тем самым происходит возврат в первую копию процедуры, и ее работа возобновляется. Команда RET из этой копии считывает из стека адрес возврата а (см. рис. а) и передает по нему управление, в результате чего происходит возврат в основную программу. Зацикливания нет.

Из этого примера видно, что для правильной организации рекурсии очень важно то, что для передачи адресов возврата используется стек. Во-первых, благодаря стеку новый адрес возврата не "забивает" прежний адрес возврата, что было бы, если бы адреса передавались через регистр. Во-вторых, благодаря стеку адреса возврата извлекаются в нужном порядке - первым всегда берется адрес, записанный в стек последним. Важную роль стека для реализации рекурсивных процедур прекрасно понимали создатели ПК, поэтому они и ввели в систему команд ПК команды CALL и RET, которые организуют передачу адресов возврата именно через стек.

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

кое-то новое значение v2. Почему не то	же самое	значение vl?	Вспомним:
и в циклах выполняются одни и те же	команды,	но на каждом	шаге они

оперируют с разными данными. Так и здесь: команда присваивания регистру г - та же самая, но присваиваемое значение может быть другим.

Итак, во второй копии нашей процедуры Р регистру г присваивается новое значение v2. Пусть в этой копии нет рекурсивного вызова, тогда она завершает работу и возвращает управление в первую копию процедуры. Но какое значение теперь будет у регистра г: vl или v2? Ясно, что v2, и это, конечно, нарушит работу первой копии процедуры, т. к. она, скорее всего, рассчитывала, что в г сохранится значение vl. Почему так произошло? А потому, что наша процедура не сохраняет значение регистра г. Если бы процедура на входе сохраняла значение регистра г, а на выходе восстанавливала его, тогда при возврате из второй копии процедуры в регистре г сохранилось бы нужное значение vl и первая копия правильно бы продолжила свою работу.

Таким образом, если нерекурсивная процедура, вообще говоря, может сохранять, а может и не сохранять значения регистров, которые она использует, то рекурсивная

•ДИАЛОГ-МИФИ-

168 Программирование на языке ассемблера IBM PC Глава 1

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

Аналогичная проблема возникает, если процедура пользуется какими-то ячейками памяти для временного хранения своих промежуточных результатов. В этом легко убедиться, если в нашем примере рассматривать г не как регистр, а как ячейку. Поэтому, если рекурсивная процедура пользуется ячейками памяти, то она обязана на входе спасать прежние значения этих ячеек, а на выходе восстанавливать эти прежние значения. А где спасать? В стеке. Но стек - это тоже ячейки памяти. Поэтому, чтобы не было лишних инстанций, рекурсивной процедуре лучше вообще отказаться от хранения своих данных в обычных ячейках памяти и запоминать все нужное сразу в стеке.

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

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

В качестве конкретного примера рекурсивной процедуры опишем функцию F(n), вычисляющую n-е число Фибоначчи (п>=0) по следующему правилу:

Договоримся, что аргумент функции передается через регистр AL, а значение функции возвращается через регистр ВХ. При этих условиях и при соблюдении требований к рекурсивным процедурам получаем такое описание функции:

; BX-F (11)		- чистю	Фибоначчи			с номером		n	(AL=n)
Г	PROC
	CMP AL,1		; n > l	- >	F l
	JA F1
; н е р е к у р с и в н а я в е т в ь
	MOV ВХ,1		; n < = l	- > BX=F(n)=l
	RET
; р е к у р с и в н а я в е т в ь
F l : POSH АХ			; с п а с т и		AX	(будем	менять)
	DEC AL		\AL—п—1
	CALL	F	; B X = F ( n - l )			(AX не	изменится)
	POSH	BX	; с п а с т и		F ( n - l )
	DEC AL		;AL=n-2
	CALL	F	;BX=F(n - 2)
	POP AX		в о с с т а н о в и т ь F ( n - l ) ,					но у х е в		AX
	ADD	BX,AX	; BX=F( n )=F( n - 2 )+F( n - 1 )
	POP AX		в о с с т а н о в и т ь исходное						з н а ч е н и е	AX
	RET
F	ENDP

Глава 10

ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ

В данной главе рассматриваются способы представления и обработки строк переменной длины и списков - структур, размеры которых меняются в процессе выполнения программы.

10.1.Строковые команды. Префиксы повторения

Тех команд, которые мы уже знаем, вполне достаточно, чтобы запрограммировать любые операции над строками (последовательностями символов, байтов). Однако строки - столь важный тип данных, что во многие ЭВМ вводят специальные команды, упрощающие обработку строк. Особенность этих команд, называемых строковыми, в том, что одной или парой таких команд можно выполнить некоторую операцию сразу над всей строкой. Есть такие команды и в ПК, они

ибудут рассмотрены в этом разделе.

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

10.1.1.Команда сравнения строк

Прежде всего отметим, что в строковых командах под "строкой" понимается не только последовательность байтов (символов), но и последовательность слов. В связи с этим каждая строковая операция представлена в ПК двумя командами: одна из них предназначена для обработки строк из байтов, а другая - для обработки строк из слов. В ЯА мнемокоды этих команд различаются тем, что в первом случае указывается буква В (byte), а в другом - буква W (word). Например, в командах сравнения строк (CMPS, compare strings) используются следующие мнемокоды:

CMPSB	-	сравнение	с т р о к	из	б а й т о в
CMPSW	-	с р а в н е н и е	строк	из	с л о в .

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

Команда CMPS записывается без операндов, ее действие можно описать так:

[ D S : S I ] = [ E S : D I ] ? ; S I : = S I + d ; D I : = D I + d ,

где величина d определяется согласно следующей таблице (DF - флаг направления, direction flag):

	DF=0	DF=1
CMPSB	+1	-1
CMPSW	+2	_2

"ДИАЛОГ-МИФИ•