Работа № 4. РЕАЛИЗАЦИЯ ТИПОВЫХ СТРУКТУР АЛГОРИТМОВ

Цель работы: изучение принципов реализации типовых алгоритмических структур на примере ветвлений и циклических программ.

ОСНОВНЫЕ СВЕДЕНИЯ

Любая процедура управления или обработки данных представляет собой совокупность некоторых алгоритмических структур, с помощью которых выполняются требуемые операции. Наиболее распространёнными алгоритмическими структурами являются ветвления (branching) и циклы (loop) [5].

Ветвления используются для выполнения различных частей программы (разделения ветвей алгоритма) в зависимости от некоторых условий.

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

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

1. Блок инициализации (от лат. initium – начало), в котором производится присвоение начальных значений переменным, счётчикам, индексам и указателям. Указатели представляют собой адреса данных в памяти.

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

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

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

Блоки 2 и 3 составляют тело цикла (loop body). Для повышения быстродействия и сокращения размера циклических программ следует разгружать тело цикла от операций, которые могут быть выполнены за его пределами.

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

Команды безусловных переходов JMP, RJMP, IJMP и EIJMP передают управление по указанному в команде адресу памяти программ. Команда JMP (Jump – переход) позволяет передавать управление внутри всего объёма памяти программ. Команда RJMP (Relative Jump – относительный переход) обеспечивает переход в пределах ±2 Кслов (±4 Кбайт) относительно текущего содержимого программного счётчика. По команде IJMP (Indirect Jump – косвенный переход) выполняется косвенный переход по адресу, указанному регистром Z; максимальное смещение составляет 64 Кслов (128 Кбайт). Команда EIJMP (Extended Indirect Jump – расширенный косвенный переход) обеспечивает косвенный переход по всему объёму памяти программ; для расширения программного счётчика используется регистр EIND. При выполнении команд безусловных переходов в программный счётчик загружается адрес ячейки памяти программ, на которую передаётся управление.

Команды условных переходов передают управление по указанному адресу памяти программ в случае выполнения некоторых условий.

Команды BRхх (Branch if … – перейти, если …) выполняют переход на расстояние –64…+63 слова относительно текущего содержимого программного счётчика по результатам проверки разрядов регистра состояния SREG (кодов или флагов условий). Регистр состояния SREG находится в адресном пространстве регистров ввода-вывода. Коды условий (C, Z, N, V, S, H) формируются в регистре состояния при выполнении арифметических, логических команд и команд работы с битами и представляют собой признаки результата операции. Разряд С (carry – перенос) устанавливается, если при выполнении команды был перенос из старшего разряда результата. Разряд Z (zero – нуль) устанавливается, если результат выполнения команды равен нулю. Разряд N (negative – отрицательный результат) устанавливается, если старший значащий разряд результата равен 1 (правильно показывает знак результата, если не было переполнения разрядной сетки числа со знаком). Разряд V (overflow – переполнение) устанавливается, если при выполнении команды произошло переполнение разрядной сетки числа со знаком. Разряд S = N Å V (sign – знак) правильно показывает знак результата при переполнении разрядной сетки числа со знаком. Разряд H (half carry – полуперенос) устанавливается, если при выполнении команды был перенос из третьего разряда результата.

Для организации ветвлений при сравнении операндов команды BRхх используются совместно с командами CP (Compare) сравнения содержимого двух РОН, CPC (Compare with Carry) сравнения с учётом признака переноса и CPI (Compare with Immediate) сравнения с константой. Команды ветвления BRхх отличаются для операндов без знака и со знаком. Числа без знака представляются прямым кодом, числа со знаком – дополнительным кодом.

Команды условных переходов, используемые для ветвлений при сравнении операндов, сведены в табл. 4.

 

Таблица 4

Условие Логическое выражение Команда Операнды
сравнения перехода
Rd > Rr Z×(N Å V) = 0 CP Rr, Rd BRLT со знаком
C + Z = 0 CP Rr, Rd BRLO без знака
Rd ³ Rr (N Å V) = 0 CP Rd, Rr BRGE со знаком
C = 0 CP Rd, Rr BRSH/BRCC без знака
Rd = Rr Z = 1 CP Rd, Rr BREQ со знаком, без знака
Rd ¹ Rr Z = 0 CP Rd, Rr BRNE со знаком, без знака
Rd £ Rr Z + (N Å V) = 1 CP Rr, Rd BRGE со знаком
C + Z = 1 CP Rr, Rd BRSH без знака
Rd < Rr (N Å V) = 1 CP Rd, Rr BRLT со знаком
C = 1 CP Rd, Rr BRLO/BRCS без знака

 

К командам условных переходов также относится команда CPSE (Compare and Skip if Equal – сравнить и пропустить, если равно), которая сравнивает содержимое двух РОН и пропускает следующую за ней команду, если содержимое одинаково.

Команды SBRS, SBRC, SBIS, SBIC (Skip if Bit in Register [I/O Register] is Set [Cleared] – пропустить, если разряд в регистре общего назначения [ввода-вывода] установлен [сброшен]) пропускают следующую команду в случае выполнения соответствующего условия. При обработке массивов в циклических программах эффективно использование косвенной адресации памяти данных с предекрементом и постинкрементом, а также косвенной адресации памяти данных со смещением.

На рис. 22 приведён фрагмент программы, в которой число 100 заносится в ячейки массива из пяти байт. Для проверки условия выхода из цикла и передачи управления используется команда BRNE. Предел повторений цикла равен 5, шаг равен –1, параметр цикла (счётчик) содержится в регистре R16.

ЗАДАНИЕ

1. Дополнить фрагмент программы, приведенный на рис. 22, необходимыми директивами. Изменить число, заносимое в ячейки массива, в соответствии с заданным вариантом (табл. 5). Выполнить программу в пошаговом режиме с помощью симулятора-отладчика.

2. Произвести изменения в программе: заменить команды add (сложение) и SUB (вычитание) на INC (инкремент) и DEC (декремент) соответственно.

 

; ...

array: .byte 5 ; 5 байт для массива array

; ...