Учебный курс. Часть 20. Стек

Автор: xrnd | Рубрика: Учебный курс | 31-05-2010 | Распечатать запись Распечатать запись

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

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

Схема организации стека в процессоре 8086 показана на рисунке:

Стек располагается в оперативной памяти в сегменте стека, и поэтому адресуется относительно сегментного регистра SS. Шириной стека называется размер элементов, которые можно помещать в него или извлекать. В нашем случае ширина стека равна двум байтам или 16 битам. Регистр SP (указатель стека) содержит адрес последнего добавленного элемента. Этот адрес также называется вершиной стека. Противоположный конец стека называется дном :)

Дно стека находится в верхних адресах памяти. При добавлении новых элементов в стек значение регистра SP уменьшается, то есть стек растёт в сторону младших адресов. Как вы помните, для COM-программ данные, код и стек находятся в одном и том же сегменте, поэтому если постараться, стек может разрастись и затереть часть данных и кода (надеюсь, с вами такой беды не случится :)).

Для стека существуют всего две основные операции:

  • добавление элемента на вершину стека (PUSH);
  • извлечение элемента с вершины стека (POP);

Добавление элемента в стек

Выполняется командой PUSH. У этой команды один операнд, который может быть непосредственным значением, 16-битным регистром (в том числе сегментым) или 16-битной переменной в памяти. Команда работает следующим образом:

  1. значение в регистре SP уменьшается на 2 (так как ширина стека — 16 бит или 2 байта);
  2. операнд помещается в память по адресу в SP.

Примеры:

    push -5           ;Поместить -5 в стек
    push ax           ;Поместить AX в стек
    push ds           ;Поместить DS в стек
    push [x]          ;Поместить x в стек (x объявлен как слово)
    push word [bx]    ;Поместить в стек слово по адресу в BX

Существуют ещё 2 команды для добавления в стек. Команда PUSHF помещает в стек содержимое регистра флагов. Команда PUSHA помещает в стек содержимое всех регистров общего назначения в следующем порядке: АХ, СХ, DX, ВХ, SP, BP, SI, DI (значение DI будет на вершине стека). Значение SP помещается то, которое было до выполнения команды. Обе эти команды не имеют операндов.

Извлечение элемента из стека

Выполняется командой POP. У этой команды также один операнд, который может быть 16-битным регистром (в том числе сегментым, но кроме CS) или 16-битной переменной в памяти. Команда работает следующим образом:

  1. операнд читается из памяти по адресу в SP;
  2. значение в регистре SP увеличивается на 2.

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

Примеры:

    pop cx            ;Поместить значение из стека в CX
    pop es            ;Поместить значение из стека в ES
    pop [x]           ;Поместить значение из стека в переменную x
    pop word [di]     ;Поместить значение из стека в слово по адресу в DI

Соответственно, есть ещё 2 команды. POPF помещает значение с вершины стека в регистр флагов. POPA восстанавливает из стека все регистры общего назначения (но при этом значение для SP игнорируется).

Пример программы

Имеется двумерный массив — таблица 16-битных значений со знаком размером n строк на m столбцов. Программа вычисляет сумму элементов каждой строки и сохраняет результат в массиве sum. Первый элемент массива будет содержать сумму элементов первой строки, второй элемент — сумму элементов второй строки и так далее.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
use16                 ;Генерировать 16-битный код
org 100h              ;Программа начинается с адреса 100h
    jmp start         ;Переход к метке start
;----------------------------------------------------------------------
; Данные
n   db 4              ;Количество строк
m   db 5              ;Количество столбцов
;Двумерный массив - таблица c данными
table:
    dw 12,45, 0,82,34
    dw 46,-5,87,11,56
    dw 35,21,77,90,-9
    dw 44,13,-1,99,32
sum rw 4              ;Массив для сумм каждой строки
;----------------------------------------------------------------------
start:
    movzx cx,[n]      ;Счётчик строк
    mov bx,table      ;BX = адрес таблицы
    mov di,sum        ;DI = адрес массива для сумм
    xor si,si         ;SI = смещение элемента от начала таблицы
 
rows:
    xor ax,ax         ;Обнуление AX. В AX будет считаться сумма
    push cx           ;Сохранение значения CX
 
    movzx cx,[m]      ;Инициализация CX для цикла по строке
calc_sum:
    add ax,[bx+si]    ;Прибавление элемента строки
    add si,2          ;SI = смещение следующего элемента
    loop calc_sum     ;Цикл суммирования строки
 
    pop cx            ;Восстановление значения CX
    mov [di],ax       ;Сохранение суммы строки
    add di,2          ;DI = адрес следующей ячейки для суммы строки
    loop rows         ;Цикл по всем строкам таблицы
 
    mov ax,4C00h      ;\
    int 21h           ;/ Завершение программы

Как видите, в программе два вложенных цикла: внешний и внутренний. Внешний цикл — это цикл по строкам таблицы. Внутренний цикл вычисляет сумму элементов строки. Стек здесь используется для временного хранения счётчика внешнего цикла. Перед началом внутреннего цикла CX сохраняется в стеке, а после завершения восстанавливается. Такой приём можно использовать для программирования и большего количества вложенных циклов.

Turbo Debugger

В отладчике Turbo Debugger стек отображается в нижней правой области окна CPU. Левый столбец чисел — адреса, правый — данные. Треугольник указывает на вершину стека, то есть на тот адрес, который содержится в регистре SP. Если запустить программу в отладчике, то можно увидеть, как работают команды «push cx» и «pop cx».

Упражнение

Объявите в программе строку «$!olleH». Напишите код для переворачивания строки с использованием стека (в цикле поместите каждый символ в стек, а затем извлеките в обратном порядке). Выведите полученную строку на экран. Свои результаты пишите в комментариях :)

Следующая часть »

Комментарии:

Ваш комментарий