Данному образовательному сайту пришлось несколько раз менять свое имя. С 2011 года доступ к нему обеспечивается по URL
http://educomp.runnet.ru

emc.km.ru (2001-2007) ==> educomp.org.ru (2007-2011) ==> educomp.runnet.ru (2011-...)
Более подробно об истории сайта можно прочитать здесь.


Учебные модели компьютера



Модели (software):

"Е14" (parallel !!!)

Модели (hardware):






Награды сайта
Награды сайта

Об образовательных возможностях Debug

(переход к другим статьям из этой серии)

4. Стек

В предыдущей статье автора из серии об изучении фундаментальных основ информатики при помощи отладчика Debug, речь шла о методах адресации данных в памяти компьютера. Было рассмотрено достаточно большое количество методов адресации, но за кадром сознательно был оставлен один очень важный, и, в то же время, весьма специфический метод адресации данных – стековый. И сейчас мы начинаем подробное знакомство с ним.

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

4.1. Теоретический раздел

4.1.1. Принципы организации стека

Стек – это определенный динамический способ хранения данных, при котором в каждый момент времени доступ возможен только к одному из элементов, а именно к тому, который был занесен в стек последним. Часто главный принцип стека называют «первым пришел – последним ушел» (в англоязыкой литературе применяется более строгий термин LIFO: Last In – First Out).

При описании работы стека принято говорить, что он имеет фиксированное основание (нижнюю границу, дно) и подвижную вершину, через которую, собственно, и происходит запись и чтение данных.

устройство стека

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

Над стеком можно определить следующие операции:

  • добавление нового элемента в вершину стека (общепринят термин PUSH – «заталкивать» в стек);
  • извлечение элемента из вершины стека (POP – «выталкивать» из стека);
  • унарные операции по изменению верхнего элемента стека;
  • бинарные операции с двумя извлеченными верхними элементами; результат возвращается обратно в вершину стека.

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

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

Учитывая, что стек может расти как в сторону увеличения, так и в сторону уменьшения адресов, а также существуют равноправные договоренности о последовательности операций при записи/чтении (например, сначала менять адрес, а потом читать данные или наоборот), возможно предложить несколько разных вариантов организации стека в ОЗУ. Тем не менее, несмотря на теоретическое разнообразие, программисты практически всегда строят стек единообразно. А именно, при заполнении стека значение указателя уменьшается, а при извлечении данных – растет. Кроме того, для записи данных используется алгоритм –(R), т.е. сначала значение указателя уменьшается, а затем происходит запись данных. Очевидно, что такой выбор предопределяет алгоритм чтения (R)+, т.е. сперва считываются данные, а затем наращивается указатель стека.

Примечание. Многочисленные рисунки, приводимые в компьютерной литературе, часто по-разному изображают положение «верха» и «низа» стека. Кроме того, и на карте памяти у одних авторов адреса растут снизу вверх, а у других – наоборот! Поэтому следует всегда быть очень внимательным, и в первую очередь обращать внимание именно на рост или убывание адресов, а не на формальное расположение элементов рисунка по вертикали.

На возможности компьютерной реализации стека могут также влиять принципы организации системы команд процессора. Так, в машинах семейства PDP в качестве регистра R для стековой адресации мог использовать любой из регистров процессора (хотя один из них – R6 – был выделен для «аппаратных нужд»), в то время как для процессоров IBM-совместимых компьютеров существует единственный регистр для работы со стеком – SP (Stack Pointer, т.е. указатель стека).

Примеры.
Пусть SP = 206 и мы рассматриваем инструкции для работы с двухбайтовыми данными. Тогда при записи в стек значение SP будет уменьшено до 204, и по этому адресу будет произведена запись требуемых данных. Если теперь считывать данные, то они будут извлечены из адреса 204, а указатель стека увеличится до 206 (фактически это означает возврат в исходное состояние).

4.1.2. Проблема начальной установки указателя

Мы видели из предыдущего описания, что поведение указателя стека однозначно определяется алгоритмом его работы. Тем не менее, начальное значение указателя алгоритмом никак не определяется. Иными словами, установка начального значения является самостоятельной проблемой, а программист должен задумываться, каково это значение и можно ли рассчитывать на то, что оно уже было ранее корректно установлено.

Например, при запуске отладчика Debug адрес, который операционная система заносит в указатель стека SP, соответствует почти самой «верхней» (с максимально возможными адресами) области памяти. Для большинства практических задач этим вполне можно удовлетвориться.

Для инициализации SP в системе команд процессора предусмотрены специальные операции. Простейшей из них является операция переписи MOV SP,<const>, которая просто заносит в указатель стека требуемую константу.

4.1.3. Стек – метод неявной адресации
Как следует из описанных выше принципов, конкретный адрес при обращении к памяти берется из указателя стека. Например, для записи в стек содержимого некоторого регистра Ri достаточно указать команду PUSH Ri, никак не ссылаясь на адрес информации в ОЗУ. Подобные способы обращения к данным, когда адрес данных не указывается, а подразумевается, принято называть неявными.

Стек является одним из образцов неявной адресации, причем очень развитым и необычайно полезным образцом. «Важным преимуществом стека по сравнению с адресной организацией памяти является то, что его элементами можно манипулировать, не адресуясь к ним явно, не называя их имени» [1].

Очевидным преимуществом неявной адресации является короткая форма записи программы и ее практически полная независимость от конкретных адресов ОЗУ (программы, которые способны без изменения исполняться с любого адреса памяти, часто называют перемещаемыми). И хотя это весьма важное с теоретической точки зрения достоинство, истинное значение стекового метода адресации все же не в этом: данный механизм позволяет реализовать многие структуры алгоритмов или данных, которые без него осуществить необычайно сложно. Рассмотрим показательный, хотя и не совсем тривиальный пример из книги Э. Таненбаума [2].

«Во всех языках программирования есть понятие процедур с локальными переменными. Эти переменные доступны во время выполнения процедуры, но перестают быть доступными после окончания процедуры. Возникает вопрос: где должны храниться такие переменные?
К сожалению, предоставить каждой переменной абсолютный адрес в памяти невозможно. Проблема заключается в том, что процедура может вызывать себя сама. … Достаточно сказать, что если процедура вызывается дважды, то хранить ее переменные под конкретными адресами в памяти нельзя, поскольку второй вызов нарушит результаты первого.»

Стековая память является простым и весьма эффективным решением сформулированной проблемы.

Более простые, но не менее важные примеры использования стека будут рассмотрены в следующем разделе.

4.1.4. Роль стека в вычислительной технике

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

Использование стека для временного хранения данных. Очень часто некоторые промежуточные результаты необходимо где-то временно сохранить, прежде чем они будут использованы в дальнейшей обработке. Типичная, хотя и не единственная ситуация, заключается в следующем. Пусть некоторому фрагменту программы в машинных командах требуется использовать несколько регистров процессора для хранения промежуточных результатов, которые по окончании его работы уже не будут представлять интереса. Поскольку регистров у процессора не так много, программисты часто стараются не портить их значения без крайней необходимости. Таким образом, с одной стороны регистры нам действительно нужны, а с другой – не хочется менять их значений. Стек предоставляет нам совместить оба этих, казалось бы несовместимых, требования.

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

PUSH BX
PUSH CX
<здесь любые манипуляции с BX и CX>
POP CX
POP BX

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

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

Подобные фрагменты программисты используют настолько часто, что, начиная с процессора INTEL 80286, к системе команд записи в стек была добавлена инструкция PUSHA (push all), сохраняющая в стек сразу все(!) регистры процессора [3].

Использование стека в некоторых алгоритмах. Многие алгоритмы существенно упрощаются при использовании стека для хранения данных. Отличным примером может служить постоянно обсуждаемый в школе алгоритм формирования десятичных цифр произвольного двоичного числа N. Как известно, вычисления ведутся по формулам:

Ci := N mod 10; N := N div 10;
Нетрудно видеть, что алгоритм генерирует цифры Ci «задом наперед», т.е. сначала единицы, потом десятки и т.д., в то время как печатать требуется в строго обратном порядке. Тем не менее, если получающиеся при вычислениях цифры помещать в стек, то при считывании они будут автоматически возвращаться именно в нужной последовательности.

Тем читателям, которых заинтересовала реализация перевода чисел в компьютере IBM PC на языке процессора, автор хотел бы порекомендовать доступную начинающим книгу [4] (см. главу 10).

Использование стека для вычисления выражений. Стек является идеальным средством для вычисления произвольных арифметических и логических выражений. Это вполне самостоятельный вопрос, он многократно обсуждался в литературе, так что мы кратко разберем его на примере. Пусть требуется вычислить выражение 2*(3+4). Ход вычислений с помощью стека иллюстрирует следующая таблица.

командастек
PUSH 22
PUSH 33 2
PUSH 44 3 2
ADD7 2
MUL14

Подчеркнем, что при использовании стековой формы вычислений скобки исчезают, поэтому такую форму записи выражений называют обратной бесскобочной, или часто, подчеркивая происхождение данной нотации – польской: ее автором является известный польский математик Ян Лукасевич (1878-1956). Достоинством польской системы представления арифметических выражений является полная однозначность ее интерпретации, причем без всяких скобок.

В отличие от общепринятой математической формы записи выражений, при польском методе сначала указываются оба операнда и только потом операция (3 + 4 ==> 3 4 +). В итоге при получении любой операционной команды машина-вычислитель способна немедленно ее выполнить. Не случайно такая система ввода выражений использовалась раньше во многих программируемых калькуляторах.

Использование стека для организации механизма подпрограмм. Одним из важнейших предназначений стека является создание возможностей для вызова подпрограмм. Подпрограммой принято называть некоторый функционально законченный участок программы, оформленный так, чтобы им можно было пользоваться из различных точек основной программы. Главной проблемой организации подпрограммы является не столько возможность перехода к ней, сколько создание механизма возврата в ту точку, откуда подпрограмма была вызвана, после окончания работы подпрограммы. Именно здесь стек и оказывается необычайно полезен. Логика работы подпрограмм является стандартной и строится следующим образом. В конце выделенного фрагмента, оформляемого в виде подпрограммы, ставится специальная инструкция возврата RET (сокращение происходит от return – вернуться). А в любом месте программы, где потребуется выполнить подпрограмму, помещается обращение CALL A, где A есть адрес начала подпрограммы. Рассмотрим, как происходит процесс вызова подпрограммы подробнее.

работа подпрограммы

Пусть подпрограмма расположена начиная с адреса A, ее вызов – в адресе C, а следующая за вызовом инструкция (точка возврата) – N.

Примечание. Значения N и С, разумеется, связаны друг с другом: N = С + L, где L – длина команды CALL A. Учитывая, что L может в разных ситуациях иметь разную длину, мы не будем здесь вычислять значение N через С.

В принятых обозначениях для перехода к подпрограмме необходимо выполнить два действия:

  1. сохранить (в стеке) значение N для последующего возврата и
  2. перейти к подпрограмме A.

Смысл производимых действий становится гораздо более понятным, если учесть, что для хранения адреса очередной команды программы процессор использует специальный регистр – счетчик адреса команд [5]. В процессорах Intel этот регистр обозначается IP – Instruction Pointer. В новой терминологии смысл перехода к подпрограмме можно сформулировать короче:

  1. сохранить в стеке IP (“PUSH IP”) и
  2. занести A в IP (“JMP A”)

При возврате из подпрограммы проделывается обратное действие: из стека извлекается адрес возврата и заносится в IP (“POP IP”), что обеспечивает переход к этому адресу.

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

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

Примечание. Строго говоря, степень вложенности все же ограничена размером ОЗУ, выделенным под стек!

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

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

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

Примечание. Описанный выше механизм требует выделения достаточного объема стековой памяти. При неправильной организации (бесконечной) рекурсии программа «вылетает» именно в связи с достижением границы стека.

Отметим, что переменные-параметры (точнее говоря, их значения или адреса: в первом случае говорят о передаче параметра по значению, а во втором – по ссылке) также передаются при обращении к подпрограмме через стек.

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

Пример.
Вспомним, как записываются вложенные циклы в языке BASIC:

FOR i=1 TO im: FOR j=1 TO jm: FOR k=1 TO km: ... NEXT k: NEXT j: NEXT i
Вложенность конструкций выглядит точно так же, как система открывающихся и закрывающихся скобок, а значит, и здесь стековая память подходит идеально!

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

Возможно построение вычислительной машины на основе стековых принципов (вспомните уже упоминавшиеся выше микрокалькуляторы). Хорошим примером стековой организации может служить виртуальная Java-машина.

4.1.5. Реализация стека

В п.4.1.1 при изложении базовых принципов работы стека было фактически показано, что стек можно организовать программно. Например, если условно принять регистр SI за указатель программно организуемого стека, то полным функциональным эквивалентом для команды PUSH AX станет последовательность инструкций

DEC SI
DEC SI
MOV [SI],AX
а для POP AX –
MOV AX,[SI]
INC SI
INC SI

Команда DEC уменьшает содержимое регистра на единицу, а INC, напротив, уменьшает. Пара инструкций требуется потому, что сохранение значения регистра AX потребует 2 байта памяти.

Тем не менее, гораздо более удобным является аппаратная реализация стека. В этом случае выделяется специальный стековый регистр (в IBM-совестимых и многих других компьютерах его обозначают SP), с которым и работают по умолчанию команды PUSH и POP.

Примечание. Строго говоря, для получения полного значения указателя стека в процессорах Intel еще используется дополнительный сегментный регистр стека SS. Мы не будем его рассматривать по следующим причинам. Во-первых, сегментация свойственна не только адресации стековой информации, но и самой программе, а также ее данным. Так что это не есть особенность стека, который мы сегодня изучаем. Во-вторых, сегментный метод адресации сейчас уже безнадежно устарел: он обеспечивает 20-разрядный адрес, тогда как современные процессоры постепенно переходят от 32-разрядной архитектуры к 64-разрядной.

регистровое окно Наконец, в RISC-процессорах существует еще одна весьма своеобразная и интересная аппаратная реализация некоторой разновидности стека. Ее часто называют регистровым окном. Основная идея состоит в том, что в любой момент времени процессор «видит» только одно регистровое окно, причем регистры в нем всегда пронумерованы единообразно [6]. Окно можно аппаратно переключать на другие регистры с помощью специального регистра CWP (Current Window Pointer) – указателя текущего окна. Например, на рисунке показано, что при установке значения CWP = 24 (новое положение окна показано пунктиром) регистр R24 приобретает имя R0, R25 – R1 и т.д.

Регистровое окно делится на три области:

  • область регистров параметров (R0-R7);
  • область локальных регистров (R8-R23);
  • область временных регистров (R24-R31).

Важно подчеркнуть, что области параметров и временных регистров при переключении окон перекрываются, что дает возможность передавать данные из одного окна в другое. Например, в наших обозначениях, код, занесенный при CWP = 0 в регистр R24, после переключения окна будет доступен под именем R0, а в R31 – в качестве R7. Зато регистры R0-R23 в результате переключения окажутся надежно сохранены, поскольку станут недоступны процессору.

Реальный RISC-процессор (например, SPARC) устроен сложнее [6], но нам описанной картины вполне достаточно. Особо подчеркнем, что описанная процедура переключения регистрового окна, во многом эквивалентна работе стека.

Литература

  1. Бруснецов Н.П. Микрокомпьютеры. М.: Наука, 1985, 208 с.
  2. Таненбаум Э. Архитектура компьютера. СПб.: Питер, 2003, 704 с.
  3. Гук М.Ю. Процессоры Intel от 8086 до Pentium II. СПб.: Питер, 1997, 224 с.
  4. Нортон П., Соухэ Д. Язык ассемблера для IBM PC. М.: Компьютер, 1992, 352 с.
  5. Основы информатики и вычислительной техники. В 2-х ч. Ч. 2. / Под ред. А.П. Ершова и В.М. Монахова. М.: Просвещение, 1986, 143 с.
  6. Столингс В. Структурная организация и архитектура компьютерных систем. М.: Издательский дом «Вильямс», 2002, 896 с.

4.2. Эксперименты со стеком

Пример 1. Использование стека для временного хранения данных

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

Продемонстрируем основные приемы работы со стеком на примере регистров AX и BX, для чего проведем эксперимент, зафиксированный в протоколе 1.

Протокол 1

-rax
AX 0000
:1111
-rbx
BX 0000
:2222
-rsp
SP FFEE
:170
-r
AX=1111  BX=2222  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=0100   NV UP EI PL NZ NA PO NC
1429:0100 0000          ADD     [BX+SI],AL                         DS:2222=00
-a
1429:0100 push ax
1429:0101 push bx
1429:0102 mov ax,3333
1429:0105 mov bx,4444
1429:0108 pop bx
1429:0109 pop ax
1429:010A
-u
1429:0100 50            PUSH    AX
1429:0101 53            PUSH    BX
1429:0102 B83333        MOV     AX,3333
1429:0105 BB4444        MOV     BX,4444
1429:0108 5B            POP     BX
1429:0109 58            POP     AX
1429:010A 0000          ADD     [BX+SI],AL
...
-d
1429:0100  50 53 B8 33 33 BB 44 44-5B 58 00 00 00 00 00 00   PS.33.DD[X......
1429:0110  00 00 00 00 00 00 00 00-00 00 00 00 34 00 18 14   ............4...
...
1429:0160  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
1429:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t4

AX=1111  BX=2222  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=0101   NV UP EI PL NZ NA PO NC
1429:0101 53            PUSH    BX

AX=1111  BX=2222  CX=0000  DX=0000  SP=016C  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=0102   NV UP EI PL NZ NA PO NC
1429:0102 B83333        MOV     AX,3333

AX=3333  BX=2222  CX=0000  DX=0000  SP=016C  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=0105   NV UP EI PL NZ NA PO NC
1429:0105 BB4444        MOV     BX,4444

AX=3333  BX=4444  CX=0000  DX=0000  SP=016C  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=0108   NV UP EI PL NZ NA PO NC
1429:0108 5B            POP     BX
-d100
1429:0100  50 53 B8 33 33 BB 44 44-5B 58 00 00 00 00 00 00   PS.33.DD[X......
1429:0110  00 00 00 00 00 00 00 00-00 00 00 00 34 00 18 14   ............4...
...
1429:0160  00 00 33 33 00 00 08 01-29 14 76 0E 22 22 11 11   ..33....).v.""..
1429:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t

AX=3333  BX=2222  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=0109   NV UP EI PL NZ NA PO NC
1429:0109 58            POP     AX
-d100
1429:0100  50 53 B8 33 33 BB 44 44-5B 58 00 00 00 00 00 00   PS.33.DD[X......
1429:0110  00 00 00 00 00 00 00 00-00 00 00 00 34 00 18 14   ............4...
...
1429:0160  00 00 33 33 33 33 00 00-09 01 29 14 76 0E 11 11   ..3333....).v...
1429:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t

AX=1111  BX=2222  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1429  ES=1429  SS=1429  CS=1429  IP=010A   NV UP EI PL NZ NA PO NC
1429:010A 0000          ADD     [BX+SI],AL                         DS:2222=00
-d100
1429:0100  50 53 B8 33 33 BB 44 44-5B 58 00 00 00 00 00 00   PS.33.DD[X......
1429:0110  00 00 00 00 00 00 00 00-00 00 00 00 34 00 18 14   ............4...
...
1429:0160  00 00 33 33 33 33 11 11-00 00 0A 01 29 14 76 0E   ..3333......).v.
1429:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................

Начнем с установки начальных значений: придадим выбранным регистрам произвольные, но легко узнаваемые значения 1111 и 2222, а указатель стека SP перенесем с конца выделенного нам операционной системой сегмента на адрес 170. Цель последнего действия – сделать изменения в стековой области памяти удобно наблюдаемыми.

Проверив, что значения регистров AX, BX и SP установлены нужным образом (как всегда, характерные места протокола, на которые следует обязательно обратить внимание, подчеркнуты!), наберем некоторую несложную программу. Она абсолютно демонстрационная, и лишена какого-либо функционального смысла: сначала двумя командами PUSH в стек последовательно сохраняются значения AX и BX, затем они сознательно «портятся» и восстанавливаются командами POP (что очень важно, в обратном порядке!) Далее командой u проверяется правильность набора, а командой d мы убеждаемся, что в области адресов ниже 170 (в протоколе подчеркнута), отведенной под стек, пока никакой информации нет (во всяком случае, в моих экспериментах там при старте всегда оказывались нули).

Запускаем программу на исполнение командой t4, после чего внимательно изучаем результаты каждой из четырех выполненных команд. В первых двух стоит обратить внимание на уменьшение значения SP – идет запись в стек (его состояние мы просмотрим чуть позднее), а две последующих очевидным образом меняют содержимое регистров AX и BX на 3333 и 4444 соответственно.

Теперь самый интересный момент: командой d100 посмотрим, что в стековой области. Учтем, что она заполняется в сторону уменьшения адресов, так что в пару байт с адреса 16E заносится наше 1111, а с 16C – 2222. Нижележащие ячейки стека тоже изменились, но разговор об этом отложим на потом.

Итак, в стеке надежно сохранены значения регистров, причем SP показывает на последнее из них.

По следующей команде t восстанавливается 2222 в BX (обязательно обратите внимание на тот факт, что в стеке этого значения больше нет – в результате работы отладчика оно «стерлось»; в теории оно должно было сохраниться, но поскольку данная ячейка стека освободилась, Debug нашел ей новое применение). Наконец, последняя команда POP восстановила первоначальное AX и никакого воспоминания о промежуточных значениях 3333 и 4444 больше не сохранилось.

Таким образом мы видели, как согласованные между собой пары команд PUSH и POP обеспечили кажущуюся(!) неприкосновенность наших «подопытных» регистров.

В заключение обсудим, каково происхождение дополнительной информации, которую мы наблюдали в стеке. Дело в том, что на самом деле помимо нашей коротенькой тестовой программы стеком пользуется сам Debug, что и порождает наблюдаемые изменения. Что именно сохраняет отладчик в стеке, нас не интересует; гораздо важнее обратить внимание на тот факт, что как только ячейка стека освободилась, ее содержимое использовать больше нельзя, т.к. оно может стать каким угодно. Из теоретических рассуждений кажется, что освободившееся значение продолжает по-прежнему лежать в стеке, но секрет в том, что стеком может воспользоваться некоторая «внешняя» (по отношению к нашей) программа. Отсюда следует важный вывод: сохранение в стековой памяти уже считанных значений не гарантируется!

Задания для самостоятельной работы

1. Убедитесь, что если команды POP BX и POP AX поменять местами, то мы получим простой алгоритм обмена значениями для двух регистров. Для проверки напишите программу обмена при посредстве стека содержимого nрегистров CX и DX и с помощью Debug проверьте, что она работает.

2. Переделайте нашу тестовую программу так, чтобы она сохраняла значения регистров AX, BX, CX и DX, а затем восстанавливала.

3. С помощью Debug разберитесь, как работает следующая последовательность команд:

MOV SP,172
PUSH AX
PUSH BX
MOV SP,170
POP BX

Пример 2. Использование стека для вызова подпрограмм

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

Итак, опишем две примитивные подпрограммы, первая из которых задает значение регистра AX, а вторая – BX, и вызовем их.

Последовательность действий по реализации задачи продемонстрирована в протоколе 2.

Протокол 2

-a
1423:0100 jmp 100
1423:0102 mov bx,1111
1423:0105 ret
1423:0106 mov ax,2222
1423:0109 ret
1423:010A call 102
1423:010D call 106
1423:0110 int 20
1423:0112
-a100
1423:0100 jmp 10a
1423:0102
-u
1423:0100 EB08          JMP     010A
1423:0102 BB1111        MOV     BX,1111
1423:0105 C3            RET
1423:0106 B82222        MOV     AX,2222
1423:0109 C3            RET
1423:010A E8F5FF        CALL    0102
1423:010D E8F6FF        CALL    0106
1423:0110 CD20          INT     20
1423:0112 0000          ADD     [BX+SI],AL
...
-rsp
SP FFEE
:170
-r
AX=0000  BX=0000  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0100   NV UP EI PL NZ NA PO NC
1423:0100 EB08          JMP     010A
-d
1423:0100  EB 08 BB 11 11 C3 B8 22-22 C3 E8 F5 FF E8 F6 FF   ......."".......
1423:0110  CD 20 00 00 00 00 00 00-00 00 00 00 34 00 12 14   . ..........4...
...
1423:0160  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
1423:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t3

AX=0000  BX=0000  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=010A   NV UP EI PL NZ NA PO NC
1423:010A E8F5FF        CALL    0102

AX=0000  BX=0000  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0102   NV UP EI PL NZ NA PO NC
1423:0102 BB1111        MOV     BX,1111

AX=0000  BX=1111  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0105   NV UP EI PL NZ NA PO NC
1423:0105 C3            RET
-d100
1423:0100  EB 08 BB 11 11 C3 B8 22-22 C3 E8 F5 FF E8 F6 FF   ......."".......
1423:0110  CD 20 00 00 00 00 00 00-00 00 00 00 34 00 12 14   . ..........4...
...
1423:0160  00 00 00 00 00 00 00 00-05 01 23 14 70 0E 0D 01   ..........#.p...
1423:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t

AX=0000  BX=1111  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=010D   NV UP EI PL NZ NA PO NC
1423:010D E8F6FF        CALL    0106
-d100
1423:0100  EB 08 BB 11 11 C3 B8 22-22 C3 E8 F5 FF E8 F6 FF   ......."".......
1423:0110  CD 20 00 00 00 00 00 00-00 00 00 00 34 00 12 14   . ..........4...
...
1423:0160  00 00 00 00 00 00 00 00-00 00 0D 01 23 14 70 0E   ............#.p.
1423:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t2

AX=0000  BX=1111  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0106   NV UP EI PL NZ NA PO NC
1423:0106 B82222        MOV     AX,2222

AX=2222  BX=1111  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0109   NV UP EI PL NZ NA PO NC
1423:0109 C3            RET
-d100
1423:0100  EB 08 BB 11 11 C3 B8 22-22 C3 E8 F5 FF E8 F6 FF   ......."".......
1423:0110  CD 20 00 00 00 00 00 00-00 00 00 00 34 00 12 14   . ..........4...
...
1423:0160  00 00 00 00 22 22 00 00-09 01 23 14 70 0E 10 01   ....""....#.p...
1423:0170  00 00 00 00 00 00 00-00 00 00 00 00 00 00 00 00   ................
-t

AX=2222  BX=1111  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0110   NV UP EI PL NZ NA PO NC
1423:0110 CD20          INT     20
-d100
1423:0100  EB 08 BB 11 11 C3 B8 22-22 C3 E8 F5 FF E8 F6 FF   ......."".......
1423:0110  CD 20 00 00 00 00 00 00-00 00 00 00 34 00 12 14   . ..........4...
...
1423:0160  00 00 00 00 22 22 22 22-00 00 10 01 23 14 70 0E   ....""""....#.p.
1423:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................

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

Далее с адреса 102 вводится подпрограмма задания значения регистра BX. Она завершается инструкцией RET (от английского return – возвращаться), которая обеспечит возврат в нужное место основной программы. Аналогично с адреса 106 набирается программа, определяющая AX.

Основная программа начинается с адреса 10a, на который необходимо будет не забыть перенастроить самую первую инструкцию нашей программы. Собственно основная программа состоит из вызова описанных выше подпрограмм с помощью инструкции CALL (переводится как вызов). Последняя инструкция выхода в операционную систему INT 20 поставлена для целей страховки – реально мы не будем ее исполнять.

Командой a100 исправим переход на начало программы и потом проверим правильность набора. Как и в первом примере, установим указатель стека SP на 170, чтобы легче было анализировать содержимое стека. Командами r и d проконтролируем текущее состояние регистров и стековой области памяти. Все готово к проведению эксперимента.

Выполним первые три команды программы – jmp 10a, call 102 и mov bx,1111. Учитывая уже накопленный опыт работы с Debug, подробно опишем только интересующую нас сейчас команду вызова подпрограммы; остальное проверьте по протоколу 2 самостоятельно. Как следует из теоретического описания, вызов подпрограммы выполняет два важных действия: запоминание в стек адреса возврата в вызывающую программу и переход на начало вызываемой подпрограммы. Проконтролируем по протоколу: указатель стека уменьшился на 2, т.е. в стек занесен двухбайтовый адрес возврата. Распечатав на экране область стека, что в «верхушке» стека лежат байты 0d 01, что после необходимой перестановки (байты процессор Intel сохраняет в обратном порядке!) дает адрес 10d. Взглянув на имеющуюся у нас распечатку, убедимся, что это действительно адрес следующей за командой call 102 инструкции. Итак, в стеке запомнен адрес возврата (по сути дела, процессор выполнил команду PUSH IP, где IP – это счетчик адреса текущей команды программы; сравните с PUSH AX). Теперь, когда IP надежно сохранен, остается занести в него адрес начала подпрограммы 102, что и было сделано, как свидетельствует протокол 2.

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

Вернемся к протоколу 2. Мы остановились перед выполнением инструкции RET, которая призвана обеспечить возврат из подпрограммы. Введем команду трассировки t и проанализируем, что произойдет. Указатель стека SP вернулся в исходное состояние, следовательно, хранившееся в стеке значение адреса возврата было считано. Куда именно – разумеется, в счетчик IP, который действительно указывает на хорошо известный нам адрес 10d. Фактически процессор выполнил действие POP IP, хотя в таком виде инструкцию никогда не пишут. Для нас важно подчеркнуть, что восстановление счетчика IP мало чем отличается от восстановления из стека регистра AX, которое разбиралось в предыдущем примере.

Итак, благодаря сохраненной в стеке информации, процессор вернулся строго в то место, откуда «ушел» в подпрограмму (точнее говоря, на следующую после вызова подпрограммы инструкцию).

Работа подпрограммы 106 происходит аналогично, в чем предлагаем читателям убедиться самостоятельно.

Задания для самостоятельной работы

1. Переделайте обсуждаемую выше программу так, чтобы вторая подпрограмма (определяющая AX) вызывалась не из основной программы, а из подпрограммы 102 (так называемые вложенные подпрограммы). Пронаблюдайте, как в стеке в некоторый момент времени оказываются оба адреса возврата.

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

3. Проделайте то же самое упражнение для суммирования BX и CX, а сумму верните в DX. Новая проблема здесь заключается в том, что все арифметические операции производятся только в AX. Поэтому рекомендуемое решение может иметь следующий вид:

PUSH AX
MOV AX,CX
ADD AX,BX
MOV DX,AX
POP AX

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

Пример 3. Использование стека для передачи параметров подпрограмме

Известно, что процедуры или функции языков высокого уровня, как правило, имеют параметры. Поставим перед собой вопрос, как можно передавать параметры подпрограмме? В простейшем случае – через регистры, подобно тому, как вы это делали в ходе самостоятельных упражнений к предыдущему примеру. Но такой способ подходит не всегда (например, представьте себе, что параметром служит строка из 32 символов – тут уж никаких регистров не хватит!)

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

Рассмотрим пример, приведенный в протоколе 3. Простой демонстрационной подпрограмме передаются два параметра, которые она помещает в регистры DX и CX.

передача параметров через стек Организуем передачу параметров в стеке согласно следующему рисунку.

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

Проанализируем подпрограмму повнимательнее. Она начинается инструкцией MOV BX,SP, которая копирует содержимое указателя стека в регистр BX. Проконсультировавшись с рисунком, убедимся, что BX указывает на адрес возврата, BX+2 – на второй параметр (для CX), а BX+4 – на первый (для DX). Если учесть, что в квадратных скобках в ассемблере принято указывать содержимое памяти, адрес которого определяется при помощи регистра, то становится понятным назначение двух следующих команд: они заносят значения параметров из стека в соответствующие регистры. Подчеркнем, что поскольку доступ к стековой области мы ведем «не стековыми», а «обычными» методами, указатель SP при этом не смещается. Данный прием лишний раз подтверждает тот факт, что стековая память не есть что-то самостоятельное, напротив, она часть обычного ОЗУ.

Подпрограмма завершается инструкцией RET 4, которая помимо возврата дополнительно обеспечивает очистку четырех байт памяти (2 параметра). Технически данная константа 4 просто прибавляется к SP: 16C + 4 = 170, т.е. указатель стека возвращается в начальное положение SP0.

Разобравшись с основными идеями приема параметров, обратимся к последовательности действий, описываемых в протоколе 3.

Протокол 3

-a
1423:0100 jmp 100
1423:0102 mov bx,sp
1423:0104 mov cx,[bx+2]
1423:0107 mov dx,[bx+4]
1423:010A ret 4
1423:010D mov ax,1111
1423:0110 push ax
1423:0111 mov ax,2222
1423:0114 push ax
1423:0115 call 102
1423:0118 int 20
1423:011A
-a100
1423:0100 jmp 10d
1423:0102
-u
1423:0100 EB0B          JMP     010D
1423:0102 89E3          MOV     BX,SP
1423:0104 8B4F02        MOV     CX,[BX+02]
1423:0107 8B5704        MOV     DX,[BX+04]
1423:010A C20400        RET     0004
1423:010D B81111        MOV     AX,1111
1423:0110 50            PUSH    AX
1423:0111 B82222        MOV     AX,2222
1423:0114 50            PUSH    AX
1423:0115 E8EAFF        CALL    0102
1423:0118 CD20          INT     20
1423:011A 0000          ADD     [BX+SI],AL
...
-rsp
SP FFE8
:170
-t6

AX=0000  BX=0000  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=010D   NV UP EI PL NZ NA PO NC
1423:010D B81111        MOV     AX,1111

AX=1111  BX=0000  CX=0000  DX=0000  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0110   NV UP EI PL NZ NA PO NC
1423:0110 50            PUSH    AX

AX=1111  BX=0000  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0111   NV UP EI PL NZ NA  NC
1423:0111 B82222        MOV     AX,2222

AX=2222  BX=0000  CX=0000  DX=0000  SP=016E  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0114   NV UP EI PL NZ NA PO NC
1423:0114 50            PUSH    AX

AX=2222  BX=0000  CX=0000  DX=0000  SP=016C  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0115   NV UP EI PL NZ NA PO NC
1423:0115 E8EAFF        CALL    0102

AX=2222  BX=0000  CX=0000  DX=0000  SP=016A  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0102   NV UP EI PL NZ NA PO NC
1423:0102 89E3          MOV     BX,SP
-d
1423:0100  EB 0B 89 E3 8B 4F 02 8B-57 04 C2 04 00 B8 11 11   .....O..W.......
1423:0110  50 B8 22 22 50 E8 EA FF-CD 20 00 00 34 00 12 14   P.""P.... ..4...
...
1423:0160  22 22 00 00 02 01 23 14-70 0E 18 01 22 22 11 11   ""....#.p...""..
1423:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-t4

AX=2222  BX=016A  CX=0000  DX=0000  SP=016A  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0104   NV UP EI PL NZ NA PO NC
1423:0104 8B4F02        MOV     CX,[BX+02]                         DS:016C=2222

AX=2222  BX=016A  CX=2222  DX=0000  SP=016A  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0107   NV UP EI PL NZ NA PO NC
1423:0107 8B5704        MOV     DX,[BX+04]                         DS:016E=1111

AX=2222  BX=016A  CX=2222  DX=1111  SP=016A  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=010A   NV UP EI PL NZ NA PO NC
1423:010A C20400        RET     0004

AX=2222  BX=016A  CX=2222  DX=1111  SP=0170  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=0118   NV UP EI PL NZ NA PO NC
1423:0118 CD20          INT     20

Сначала обычным образом вводится программа, корректируется переход на начало и проверяется правильность набора. SP традиционно устанавливается на 170. Далее по директиве t6 выполняется шесть первых команд программы. В результате в стек командой PUSH заносятся два параметра, и вызывается подпрограмма 102. Анализ содержимого стека показывает, что оно соответствует приведенному выше рисунку, т.е. пока все работает правильно.

Директива t4 выполняет следующие четыре команды, которые образуют подпрограмму. Здесь тоже все проходит «в штатном режиме»: параметры помещаются в регистры и при возврате из подпрограммы SP восстанавливается. Таким образом, эксперимент полностью подтверждает теоретические принципы передачи параметров подпрограмме, описанные выше.

Задания для самостоятельной работы

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

MOV BX,SP
MOV SI,[BX+4]
MOV [SI],AX

Здесь для временного хранения адреса переменной использован дополнительный регистр процессора SI.

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

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

PROCEDURE test(x: integer; var y: integer);
BEGIN y := x+1
END

Занесите в ячейку, выбранную под переменную x, начальное значение, организуйте вызов процедуры и добейтесь, чтобы в y появился требуемый ответ.

Пример 4. Комплексное использование стека

В примере 2 показано, как стек работает при вызове подпрограммы. В примере 3 стек дополнительно применяется для передачи данных. Становится очевидным, насколько стек универсален: он может хранить и адреса возвратов, и данные. Более того, «с машинной точки зрения» принципиальной разницы между числом или адресом, хранящимся в стеке, вообще не существует. Убедимся в этом в ходе следующего эксперимента.

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

Обратимся к протоколу 4.

Протокол 4

-a
1423:0100 jmp 100
1423:0102 mov bx,sp
1423:0104 mov bx,[bx]
1423:0106 ret
1423:0107 call 102
1423:010A add bx,0
1423:010D mov ax,[bx]
1423:010F int 20
1423:0111 dw 1111
1423:0113
-a100
1423:0100 jmp 107
1423:0102
-a10a
1423:010A add bx,7
1423:010D
-u
1423:0100 EB05          JMP     0107
1423:0102 89E3          MOV     BX,SP
1423:0104 8B1F          MOV     BX,[BX]
1423:0106 C3            RET
1423:0107 E8F8FF        CALL    0102
1423:010A 83C307        ADD     BX,+07
1423:010D 8B07          MOV     AX,[BX]
1423:010F CD20          INT     20
1423:0111 1111          ADC     [BX+DI],DX
...
-g=100 10f

AX=1111  BX=0111  CX=0000  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=010F   NV UP EI PL NZ AC PE NC
1423:010F CD20          INT     20
-m100,113,200
-u200
1423:0200 EB05          JMP     0207
1423:0202 89E3          MOV     BX,SP
1423:0204 8B1F          MOV     BX,[BX]
1423:0206 C3            RET
1423:0207 E8F8FF        CALL    0202
1423:020A 83C307        ADD     BX,+07
1423:020D 8B07          MOV     AX,[BX]
1423:020F CD20          INT     20
1423:0211 1111          ADC     [BX+DI],DX
...
-g=200 20f

AX=1111  BX=0211  CX=0000  DX=0000  SP=FFEE  BP=0000  SI=0000  DI=0000
DS=1423  ES=1423  SS=1423  CS=1423  IP=020F   NV UP EI PL NZ AC PE NC
1423:020F CD20          INT     20

Сначала вводится подпрограмма, извлекающая в BX копию адреса возврата, а затем, как обычно, по инструкции RET, передающая управление основной программе. Последняя, зная значение адреса, вычисляет местоположение находящихся внутри нее данных, и извлекает их в регистр AX. Как видно из протокола 4, данные оказываются по адресу 111, что на 7 больше, чем адрес точки выхода из подпрограммы 10a. Предлагаем читателям внимательно разобрать протокол ввода и коррекции программы самостоятельно.

Далее по директиве g=100 10f запустим программу с адреса 100, обеспечивая ее останов в точке 10f. Убедимся, что в регистре AX действительно оказывается требуемое значение.

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

Для проверки данного утверждения выполним директиву m100,113,200, которая скопирует нашу программу целиком в другую область памяти, начинающуюся с адреса 200 (проверка u200 подтвердит этот факт). Но самое интересное, что и в этом месте ОЗУ программа по-прежнему будет правильно работать!

Задание для самостоятельной работы

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

Пример 5. Как устроен WRITELN?

В качестве последнего примера работы со стеком покажем, как реализовать подпрограмму, которая выводит расположенный «следом за обращением к ней» текст. Иными словами, попробуем свои силы в реализации простейшего оператора Паскаля WRITELN(‘HELLO!’).

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

 Программа: A$="HELLO!": FOR I=1 TO LEN(A$): PRINT HEX$(ASC(MID$(A$,I,1)));" ";: NEXT I

 Результат: 48 45 4C 4C 4F 21

Перейдем к рассмотрению протокола 5.

Протокол 5

-a
1423:0100 jmp 100
1423:0102 pop bx
1423:0103 xor ch,ch
1423:0105 mov cl,[bx]
1423:0107 inc bx
1423:0108 mov al,[bx]
1423:010A inc bx
1423:010B mov ah,e
1423:010D int 10
1423:010F loop 108
1423:0111 jmp bx
1423:0113 call 102
1423:0116 db 6 48 45 4c 4c 4f 21
1423:011D int 20
1423:011F
-a100
1423:0100 jmp 113
1423:0102
-u
1423:0100 EB11          JMP     0113
1423:0102 5B            POP     BX
1423:0103 30ED          XOR     CH,CH
1423:0105 8A0F          MOV     CL,[BX]
1423:0107 43            INC     BX
1423:0108 8A07          MOV     AL,[BX]
1423:010A 43            INC     BX
1423:010B B40E          MOV     AH,0E
1423:010D CD10          INT     10
1423:010F E2F7          LOOP    0108
1423:0111 FFE3          JMP     BX
1423:0113 E8ECFF        CALL    0102
1423:0116 06            PUSH    ES
1423:0117 48            DEC     AX
1423:0118 45            INC     BP
1423:0119 4C            DEC     SP
1423:011A 4C            DEC     SP
1423:011B 4F            DEC     DI
1423:011C 21CD          AND     BP,CX
1423:011E 2014          AND     [SI],DL
-d
1423:0100  EB 11 5B 30 ED 8A 0F 43-8A 07 43 B4 0E CD 10 E2   ..[0...C..C.....
1423:0110  F7 FF E3 E8 EC FF 06 48-45 4C 4C 4F 21 CD 20 14   .......HELLO!. .
1423:0120  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
...
-g
HELLO!
Программа завершилась нормально
-m100,11f,200
-u200
1423:0200 EB11          JMP     0213
1423:0202 5B            POP     BX
1423:0203 30ED          XOR     CH,CH
1423:0205 8A0F          MOV     CL,[BX]
1423:0207 43            INC     BX
1423:0208 8A07          MOV     AL,[BX]
1423:020A 43            INC     BX
1423:020B B40E          MOV     AH,0E
1423:020D CD10          INT     10
1423:020F E2F7          LOOP    0208
1423:0211 FFE3          JMP     BX
1423:0213 E8ECFF        CALL    0202
1423:0216 06            PUSH    ES
1423:0217 48            DEC     AX
1423:0218 45            INC     BP
1423:0219 4C            DEC     SP
1423:021A 4C            DEC     SP
1423:021B 4F            DEC     DI
1423:021C 21CD          AND     BP,CX
1423:021E 2014          AND     [SI],DL
-g=200
HELLO!
Программа завершилась нормально

В программе есть несколько неочевидных моментов, поэтому разберем ее подробнее.

Инструкция POP BX в традиционном для наших экспериментов стиле сделает регистр BX местом хранения адреса возврата. Однако, в отличие от примера 4, где этот адрес просто копировался без нарушения указателя стека, здесь использован стандартный метод извлечения из стека с потерей его содержимого. Почему? В силу специфики нашей задачи! В самом деле, когда мы вызовем нашу подпрограмму, то счетчик будет установлен на следующий за вызовом адрес. Но в нашей задаче – это адрес начала текста, т.е. скорее адрес данных, чем адрес возврата. Именно поэтому мы смело «берем инициативу на себя», но тем самым «обязуемся» осуществить возврат из подпрограммы самостоятельно.

Итак, в BX – адрес выводимого текста. Теперь подготовим для цикла вывода количество символов в нем в регистре CX. Старшую часть этого регистра обнулим командой XOR CH,CH (читателям предлагается доказать, что результат операции «исключающее или» любой произвольной константы «с самой собой» всегда равен нулю!), а в младшую считаем первый байт, на который указывает регистр BX. Тем самым мы предполагаем, что перед текстом лежит количество байт в нем; это очень важно вспомнить при занесении кодов символов текста в память. Увеличим значение регистра-указателя BX на единицу, установив его тем самым на первую букву текста. Теперь к реализации цикла вывода на экран все подготовлено.

Далее следует короткий (из 5 машинных инструкций) цикл. В AL извлекается очередной символ и BX тут же наращивается, чтобы подготовиться к выводу следующего. В AH заносится номер функции символа на экран и следует обращение к ней по инструкции INT 10. В результате извлеченный из памяти символ оказывается на экране. Завершается цикл командой LOOP (в переводе с английского – «петля»), которая вычитает из CX единицу и сравнивает результат с нулем: если осталось ноль символов, то все уже напечатано и цикл завершается, иначе – повторяется начиная с команды 108.

А теперь самое интересное. Регистр BX синхронно «скользил» вдоль текста, отслеживая его символы. Куда он указывает, когда весь текст закончился? Правильно, на инструкцию программы, которую необходимо выполнить следующей. Поэтому команда JMP BX и обеспечивает фактически завершение подпрограммы и возврат к нужному месту основной программы.

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


© Е.А.Еремин, 2008
Публикация:
Еремин Е.А. Стек. "Информатика", 2008, N 2, с.37-38; N 3, с.42-44; N4, с.41-44; N 6, с.43-45;

(к другим статьям из этой серии)


Автор сайта - Евгений Александрович Еремин (Пермский государственный педагогический университет). e_eremin@yahoo.com