Разработка алгоритма и программы на ассемблере
Введение
Для
полноценного функционирования электронного средства существует необходимость в
решение различных не сложных арифметических и логических функций, но огромное
количество таких задач представляет собой очень трудоемкий и длительный процесс
и его целесообразно выполнять с помощью микропроцессорной техники. Решению
одной из таких задач посвящена данная курсовая работа. В которой будет
разработана программа по вычислению функции 
на языке
программирования ассемблер для микропроцессора Кр580ВМ80.
В
ходе решения данной задачи нам необходимо подробно изучить микропроцессорную
технику на примере однокристальной микро-ЭВМ Кр580ВМ80. Освоить приёмы
программирования на языке низкого уровня - ассемблер. Затем произвести
детальный анализ технического задания и найти пути решения в виде наиболее
привлекательного с точки зрения рациональности алгоритма программы. Составить
всю необходимую документацию к данной программе.
1. Анализ
технического задания
В данной курсовой работе требуется разработать на ассемблере программу
вычисления функции.
Исходные данные
1. Функция 
;
. Тип
микропроцессора КР580ВМ80;
. Рабочая
частота - 2 МГц;
. Исходные
числа целые, положительные, 4-х байтовые, двоичные;
. Специальное
требование - минимизировать объем памяти программы.
Рассмотрим основные ресурсы с точки зрения программирования, которые
предоставляют МП КР580ВМ80. Данный МП представляет собой однокристальный
8-разрядный микропроцессор и включает в себя три основные части: АЛУ, банк
регистров, схему управления. Взаимосвязь между различными блоками
осуществляется с помощью внутренней 8-разрядной шины данных. МП имеет внешнюю
8-и разрядную, двунаправленную шину данных с тремя логическими состояниями и
16-разрядную однонаправленную шину адреса с тремя логическими состояниями.
Такая 16-разрядная шина адреса позволяет адресовать 216 = 65536 ячеек
памяти.
АЛУ МП представляет собой 8-разрядное комбинационное логическое
устройство, предназначенное для выполнения арифметических и логических
операций. Один из операндов, поступающих на АЛУ, всегда размещается в
аккумуляторе, в аккумулятор помещается и результат операции. АЛУ данного МП
выполняет только простейшие операции (сложение, вычитание, сдвиг и.т.д.), более
сложные операции реализуются программно.
Все регистры МП Кр580ВМ80 можно разделить по назначению на две группы:
регистры общего назначения (РОН) и специальные регистры.
МП имеет 8 регистров общего назначения. Из них регистры W и Z программно
недоступны и предназначены для внутренних пересылок информации в МП, в
частности для хранения двух и трехбайтовых команд. Регистры В,С,D,E,Н,L
программно доступны и предназначены для хранения операндов и промежуточных
результатов вычислений. Использование этих регистров в программе позволяет
сократить время выполнения программы и её объём. Эти регистры могут
использоваться как отдельно (как 8-разрядные регистры), так и в парах НL, BC,
DE, при этом они используются для хранения 16-разрядных операндов и адресов.
Пара регистров НL может использоваться для хранения адреса ячейки памяти (М)
при обращении к ней как к регистру.
К специальным регистрам относятся: счетчик команд, указатель стека,
регистр адреса, аккумулятор, регистр признаков.
Из них программно доступными являются счетчик команд, указатель стека,
аккумулятор, регистр признаков.
Счетчик команд Рс представляет собой 16-ти разрядный регистр, содержащий
адрес выполняемой команды.
Указатель стека Sр - 16-разрядный регистр, предназначенный для хранения
адреса вершины стека. Стек располагается в оперативной памяти. Поэтому при
разбивке адресного пространства необходимо в ОЗУ выделить область для стека.
Регистр состояния (регистр признаков) предназначен для хранения информации
о результате операции.
Также МП содержит схема десятичной коррекции предназначена для
автоматической коррекции результата операции сложения при представлении
операндов, в двоично-десятичном коде.
Система команд МП включает команды пересылки, инкремента и декремента,
команды арифметических и логических операций, сдвига, передачи управления,
ввода-вывода и несколько дополнительных команд.
В данном МП нет команд деления и умножения. Поэтому необходимо
разработать алгоритмы программного вычисления данных операций.
По заданию входными числами х1, х2, являются целые, положительные, 4-х
байтные, двоичные числа. 4-х байтное двоичное число может принимать значения от
0 до 232-1 (FFFFFFFF16).
Максимальное значения функция достигает при минимальном значении знаменателя,
то есть при х1=1 и равно (1+232-1+232-1)/(4×1) =2147483647 (7FFFFFFF16). Таким образом, для хранения результата в двоичном виде
необходимо четыре байта.
Для
хранения результата сложения х1, х2 и x
необходимо пять байт, так как
232-1+232-1+232-1=12884901885 (2FFFFFFFD16).
Для
хранения результата умножения 4 на х1 необходимо также пять байт, так как 4×232-1=17179869180 (3FFFFFFFC16).
Отметим,
что областью допустимых значений, удовлетворяющей данной функции, является
выражение 
>
.
Проанализируем
заданную математическую функцию. Она содержит три арифметических действия,
поэтому программу можно логически разделить на три составляющих.
В
первую очередь следует найти сумму . В своём
составе МП Кр580ВМ80 имеет байтовое АЛУ с фиксированным набором команд. В этом
перечне присутствует команда сложения. Так как разрядность процессора равна
восьми, а переменные состоят из нескольких байт сложение будем производить,
побайтно переходя от младшего к старшему с учётом переноса. В начале задаются
счетчик сложений кратный количеству байт чисел, начальные адреса, которыми
являются ячейки памяти с младшими байтами чисел. Далее происходит
непосредственное сложение. После этого необходимо изменить текущие адреса на
следующие. Далее модифицируем счётчик, и если он показывает, что необходимое
количество сложений произошло, выходим из цикла, в противном случае
возвращаемся в блок сложения и повторяем цикл, начиная с него до тех пор, пока
счетчик не достигнет определенного значения.
Для
вычисления выражения 4
необходимо разработать алгоритм программного
умножения. Простейший способ умножения двоичных чисел заключается в
суммировании множимого с накоплением, которое производится m
раз, где m - значение множителя. Основной недостаток данного
способа, почти исключающий его практическое применение, заключается в очень
низком быстродействии. Такого недостатка
лишен второй алгоритм. Он выполняет умножение сдвигом разрядной сетки. Суть
умножения сводится к тому, что один из множителей (второй) всегда должен
сдвигаться вправо (сдвиг разрядной сетки вправо). При этом крайний разряд можно
будет всегда оценивать на признак: ноль или один. Если он будет равен единице,
то в сумму нужно будет добавлять первый множитель. Первый множитель, на каждой
итерации цикла тоже должен изменяться, а, именно, его разрядную сетку нужно
сдвигать влево. Будет получаться, что мы на каждой итерации добавляем ему
справа по нолику. Имеются четыре варианта реализации данного способа, определяемых
тем, начиная с каких цифр - младших или старших - анализируется множитель и что
сдвигается - множимое или частичная сумма.
Данный алгоритм будет занимать гораздо меньше места, поскольку число раз
повторения цикла будет зависеть не от значения числа множителя, а от количества
его разрядов. Применение этого алгоритма особенно удобно при больших числах.
Подобные программистские «выверты» позволили осуществить такие алгоритмы
умножения, при которых задействованы лишь регистры МК, и нет обращений к
внутренней или внешней памяти данных. Благодаря этому скорость выполнения
умножения достаточно высока, т. к. операции с регистрами гораздо быстрее
аналогичных операций с ячейками ОЗУ.
Для деления многобайтных чисел необходимо разработать алгоритм
программного деления. Самый простой способ деления заключается в вычитании из
делимого делителя, пока делимое не станет меньше делителя, и одновременном
увеличении счетчика для нахождения частного. Этот способ не применяется, так
как при большом делимом относительно делителя программа выполняется крайне
медленно, что не соответствует требованию.
Более эффективный способ реализуется методом «вычитание-сдвиг». Так как
частное можно получать, только начиная со старших разрядов, имеются два
варианта деления - со сдвигом остатка влево и со сдвигом делителя вправо.
Второй вариант на практике не применяется из-за необходимости иметь регистры
остатка и делителя удвоенной длины, что сказывается на быстродействии.
При делении целых чисел в отличие от деления правильных дробей приходится
получать целую часть частного и остаток, а округление частного не производится.
После вычитания делителя из сдвинутого положительного остатка информацию об
очередном разряде частного содержит признак переноса. Если делитель больше
остатка, то возникает заем, который фиксируется установкой признака переноса. В
этом случае цифра частного равна нулю и делитель суммируется с результатом
вычитания для восстановления предыдущего положительного остатка. Если при
вычитании делителя заема не возникает и соответственно признак переноса
сброшен, цифра частного равна единице, а положительная разность представляет
собой очередной остаток. Таким образом, цифра частного противоположна значению
признака переноса после вычитания делителя из остатка.
Таким образом, для вычисления функции необходимо выполнить следующие
основные действия (рисунок 1).
Рисунок 1 - Обобщенный алгоритм программы
Основываясь на описанных методах умножения и деления, можно разработать
программу вычисления заданной функции для микропроцессора КР580ВМ80, которая
будет удовлетворять поставленным требованиям.
Рабочая
частота микропроцессора 
. Эти данные предназначены для расчетной части работы,
а именно для нахождения времени выполнения программы из расчета, что время
одного такта процессора вычисляется по формуле (1.1).
(1.1)
Все
числа, которыми мы оперируем в качестве переменных, имеют область определения.
Она ограничена исключительно положительными числами.
. Разработка
алгоритма программы
В анализе ТЗ было указано, что в микропроцессоре КР580ВМ80 отсутствуют
команды многобайтного умножения и деления двоичных чисел. Поэтому были
рассмотрены и выбраны методы программного вычисления данных операций.
Таким образом, исходя из обобщенного алгоритма программы и методов,
описанных в предыдущем разделе, можно разработать алгоритмы, выполняющие
вычисление заданной функции.
Для реализации умножения был выбран метод вычисление произведения при
помощи сдвига множимого и сложения частичных результатов сдвига. Алгоритм
умножения приведен на рисунке 2.
Рисунок
2 - Алгоритм вычисления 25·X1.
В
алгоритме применены следующие обозначения:
X1 - множимое;
P - частичная
сумма (произведение);
S -
промежуточный результат сдвига;
S<< -
сдвиг влево с переносом числа S;
С
- счетчик сдвигов
Для
реализации деления был выбран метод со сдвигом остатка влево.
Алгоритм деления приведен на рисунке 3.
Рисунок 3 - Алгоритм деления двух чисел методом сдвигом остатка влево
В алгоритме применены следующие обозначения: D - частное; K -
остаток от деления; X1 - делимое; X2 - делитель; С - счетчик бит; N - количество бит в делимом; B - текущий бит делимого; E - инвертированный признак займа при
вычитании делителя из остатка.
Для работы вышеописанных алгоритмов, необходимо также разработать
алгоритмы многобайтного сложения, вычитания и сдвига влево.
Алгоритм многобайтного сложения приведен на рисунке 4.
Рисунок
4 - Алгоритм сложения многобайтных чисел X и Y.
В
алгоритме применены следующие обозначения:
Tc - признак
переноса;
N - количество
байт в числе;
Xc - с-ый байт
числа X;
Yc - с-ый байт
числа Y;
С
- счетчик байт;
Алгоритмы многобайтного сдвига влево и вычитания аналогичны алгоритму на
рисунке 4, только вместо операции сложения используются соответственно операции
сдвига и вычитания.
Из общей блок-схемы алгоритма на рисунке 1, а также из блок-схем на
рисунках 2 и 3 видно, что алгоритмы сложения, вычитания и сдвига применяются в
программе несколько раз, поэтому с целью минимизации объема программы, данные
алгоритмы будут реализовываться в виде подпрограмм.
Таким образом, используя разработанные алгоритмы можно составить
структурную схему алгоритма программы для микропроцессора КР580ВМ80.
Первая часть - основная программа, в которой выполняются следующие
действия:
В блоке 1.1 выполняется инициализация указателя стека;
в блоке 1.2 загружается число x1 в переменную tmp1, tmp3 и tmp4;
в блоке 1.3 обнуляется пятый байт переменных tmp1, tmp3 и
tmp4;
в блоке 1.4 загружается число x2 в переменную tmp2 и
обнуляется пятый байт переменной tmp2;
в блоке 1.5 вызывается подпрограмма многобайтного сложения чисел в
переменных tmp4 и tmp2, результат записывается в переменную tmp4;
в блоке 1.5 вызывается подпрограмма умножения чисел в переменных tmp1 и tmp2, результат записывается в переменную tmp3;
блоки 1.6-1.12 соответствуют функциональному алгоритму на рисунке 2 (умножение
x1 на 25):
в блоке 1.6 загружается число сдвигов в регистр C и в блоках 1.7-1.9 выполняется цикл сдвига на 3 разряда с
учетом переноса, сдвиг на один разряд многобайтного числа выполняется при
помощи подпрограммы в блоке 1.7;
в блоке 1.10 выполняется сложение результата сдвига (в переменной tmp1) и числа x1 (в переменной tmp3), результат сохраняется в tmp3;
в блоке 1.11 выполняется еще один сдвиг влево на один разряд числа в tmp1;
в блоке 1.12 вычисляется окончательный результат умножения путем сложения
чисел в tmp1 и tmp3, результат сохраняется в tmp3;
в блоках 1.13-1.22 выполняется деление числа в переменной tmp4 (сумма x1 и x2) на
число в tmp3 (произведение 25 и x1), результат записывается в tmp1: в блоке 1.13 обнуляются переменные
частного tmp1 и остатка tmp2, в регистр С загружается количество бит в делимом
(40) и сбрасывается признак переноса, далее идет цикл деления (блоки
1.14-1.22): делимое сдвигается влево (блок 1.14), остаток сдвигается влево
(блок 1.15), из остатка вычитается делитель (блок 1.16) и если результат меньше
нуля (блок 1.17), остаток восстанавливается (блоки 1.18), далее вычисляется
очередной бит частного (блок 1.19) и частное сдвигается влево (блок 1.20),
уменьшается на один число в регистре С (блок 1.21), выход из цикла происходит
если в регистре С ноль (блок 1.22);
в блоке 1.23 значение функции в переменной tmp1 сохраняется в переменную y.
Вторая часть - подпрограмма сложения двух 5-и байтных двоичных чисел,
адреса которых находятся в регистровых парах HL и DE
соответственно. Результат помещается в ячейках памяти на место первого числа.
В блоке 2.1 сбрасывается признак переноса, в блоке 2.2 в регистр В
загружается количество байт в числах, далее идет цикл сложения (блоки 2.3-2.9):
байт второго числа загружается в аккумулятор (блок 2.3), складывается с первым
числом (блок 2.4) и с признаком переноса, и сохраняется в память (блок 2.5),
увеличиваются адреса байт (блоки 2.6,2.7), уменьшается на один число в регистре
B (блок 2.8), выход из цикла
происходит, если в регистре B ноль
(блок 2.9).
Третья часть - подпрограмма вычитания двух 5-и байтных двоичных чисел,
адреса которых находятся в регистровых парах HL и DE
соответственно. Результат помещается в ячейках памяти на место второго числа.
В блоке 3.1 сбрасывается признак переноса, в блоке 3.2 в регистр В
загружается количество байт в числах, далее идет цикл вычитания (блоки
3.3-3.9): байт второго числа загружается в аккумулятор (блок 3.3), из него
вычитается байт первого числа и признак переноса (блок 3.4), и результат
сохраняется в память (блок 3.5), увеличиваются адреса байт (блоки 3.6,3.7),
уменьшается на один число в регистре B (блок 3.8), выход из цикла происходит, если в регистре B ноль (блок 3.9).
Четвертая часть - подпрограмма сдвига влево с учетом переноса 5-и
байтового двоичного числа, адрес которого находится в регистровой паре HL:
В блоке 4.1 в регистр В загружается количество байт в числе, далее идет
цикл сдвига (блоки 4.2-4.7): байт числа загружается в аккумулятор (блок 4.2),
сдвигается (блок 4.3) и сохраняется в память (блок 4.4), увеличивается адрес
байта (блок 4.5), уменьшается на один число в регистре B (блок 4.6), выход из цикла происходит если в регистре B ноль (блок 4.7).
Таким образом, программа будет состоять из основной программы, и
подпрограмм многобайтного сложения, вычитания и сдвига влево.
3. Разработка
программы на ассемблере
Согласно разработанной в предыдущем разделе структурной схемы программы
была разработана программа на языке ассемблер для микропроцессора КР580ВМ80.
Листинг программы на языке ассемблер приведен в приложении.
Входные числа x1, x2 должны быть расположены в ячейках
памяти, начиная с меток x1, x2, соответственно, и занимают каждое
4 байта. Результат вычисления функции располагается в ячейках памяти, начиная с
метки y, и занимает также 4 байта.
В программе также используются четыре переменные tmp1, tmp2, tmp3, tmp4, которые используются для хранения промежуточных
результатов операций. Каждая переменная занимает пять байт. Переменные
располагаются в ячейках памяти по меткам:
tmp1 -
метки tmp1L, tmp1H, tmp1HH;
tmp2 -
метки tmp2L, tmp2H, tmp2HH;
tmp3 -
метки tmp3L, tmp3H, tmp3HH;
tmp4 -
метка tmp4L, tmp4H, tmp4HH.
Для определения как будут размещаться программа и данные в памяти
необходимо провести распределение адресного пространства.
Адресное пространство КР580ВМ80 составляет 64кБ. В данном пространстве
должна располагаться память программ (ПЗУ) и память данных (ОЗУ). В памяти
данных также должна быть определена область для стека. Так как при включении
или сбросе процессор начинает выполнять команды с адреса 0, память программ
должна начинаться с данного адреса.