Анализ задачи и разработка алгоритма.

Методические указания

для выполнения курсовой работы

«Моделирование программы гипотетической машины с помощью макросредств»

по курсу «Технология программирования»

 

Разработал к.т.н., доцент кафедры ВТ Гафаров Р.М.

 

 

Ижевск 2010

 

Введение.

Курсовая работа «Моделирование программы гипотетической машины с помощью макросредств» выполняется студентами специальности 2201 для закрепления знаний и навыков программирования на языках символического кодирования (ассемблерах), полученных на лекционных занятиях и лабораторных работах. Умение программировать на ассемблере имеет не только самостоятельное значение, но и является актуальным для специальности 2201 как основа для понимания структуры и методов функционирования ЭВМ. Исходные данные для курсовой работы задаются в виде параметров некоторой гипотетической (абстрактной) машины (ГМ):

1. Формат слова fw;
2. Число регистров общего назначения nR;
3. Форматы команд ГМ fk;
4. Количество операндов в команде nOP;
5. Команды ГМ для обязательной реализации 3-5 команд;
6. Задача для программирования средствами ГМ.

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

Выполнение курсовой работы состоит из нескольких этапов:

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

2. Составление программы для ГМ – наиболее ответственный этап проектирования. Во-первых, следует выяснить минимальный набор операций, необходимых для реализации разработанного алгоритма. Во-вторых, реализовать эти операции в виде команд ГМ, учитывая параметры указанные в задании (варианте курсовой работы). Требуется разработать структуры данных и директивы для их описания и форматы конкретных команд.

3. Реализация программы на реальной ЭВМ (РМ). Каждая команда программы для ГМ рассматривается в виде макрокоманды и задача данного этапа состоит в написании для каждой из них соответствующего макроопределения. В макроопределениях макросредствами ассемблера IBM PC реализуются алгоритмы команд ГМ на реальной машине. Основные трудности связаны с согласованием форматов слов двух ЭВМ, в частности с записью в память и выборкой слов ГМ из памяти. Кроме того, должны быть решены вопросы ввода исходных данных (случайные данные, входной файл с данными, ввод с клавиатуры) и вывода результатов. Материалы по макросредствам ассемблера IBM PC приведены в приложении к методическим указаниям.

Далее рассматривается пример разработки и моделирования программы для ГМ одного из вариантов курсовой работы.

 

Пример выполнения курсовой работы.

Задание.

Пусть заданы параметры ГМ:

1. Формат слова ГМ параметр в диапазоне 8..255 бит;

1. Число регистров общего назначения 4;
2. Форматы команд ГМ: RR – регистр-регистр, RS – регистр-память, SI – память-непосредственный операнд;
3. Количество операндов в команде 1,2,3;
4. Команды ГМ для обязательной реализации:

1)команда чтения слова из памяти;

2)команда записи слова в память;

3)команда сравнения двух слов;

Задача. Создать отсортированный линейный односвязный список из n элементов (узлов).

 

Begin

Randomize;

ClrScr; { очистка экрана }

R1:=0; { R1 сч. цикла:= 0 }

R2:=kuz; { к-во узлов -> R2 }

h:= Nil; { h – голова списка, вначале список пустой }

{------------- Цикл создания узлов списка ------------- }

Repeat

R0:= Random (100); { взяли очередной inf -> R0 }

New (s); { создали новый узел, его адрес в s }

s^.i:=R0; { inf -> в новый узел }

t:=h; { t - указатель на текущий узел }

p:= Nil; { p - указатель на предыдущий узел}

{ Цикл поиска и вставки узла в надлежащее место списка }

While t <> Nil Do { пока не достигнут конец списка }

If t^.i > R0 { поиск места вставки }

Then { если место вставки найдено }

If p = Nil { и если р не успел измениться,то}

Then Begin { вставка в начало списка }

s^.l:= t; { соответствующая }

h:= s; { коммутация узлов }

Goto 1; { alles с этим вариантом }

End

Else Begin { вставка в середину списка }

s^.l:= t; { соответствующая }

p^.l:= s; { коммутация узлов }

Goto 1; { alles }

End

Else Begin { место вставки не найдено и переход к след. узлу }

p:= t; { предыдущий становится текущим, }

t:= t^.l; { а текущий - следующим }

End;

{ конец цикла While }

If p= Nil Then Begin { вставка в пустой список }

h:=s; { соответствующая }

s^.l:=Nil; { коммутация узлов}

End

Else Begin { вставка в конец списка }

p^.l:=s; { соответствующая }

s^.l:=Nil; { коммутация узлов}

End;

1: R1:=R1+1; { увеличение счетчика цикла }

Until R2 <= R1; { If счетчик < kuz Then на начало цикла}

{ Прохождение и печать списка }

t:=h; { встали на начало списка }

Writeln(' отсортированный список');{ вывели заголовок }

While t<> Nil Do { цикл прохождения списка }

Begin Write(t^.i:3); { печать узла }

t:=t^.l; { переход к след. узлу }

End;

ReadKey; { ожидание нажатия клавиши }

End.

 

В программе реализуется следующей алгоритм создания отсортированного списка. Сначала список пустой и h=nil. Внешний цикл REPEAT UNTIL детерминированного типа управляет числом создаваемых узлов. При каждом повторении этого цикла в динамической памяти создается новый узел с адресом (указателем) s и в его информационное поле s^. i записывается очередное случайное число. Далее, с помощью итерационного цикла WHILE осуществляется поиск места вставки нового узла и его коммутация с соседними так, чтобы список сохранил свойство отсортированности. Отметим, что для коммутации необходимо знать указатель как на текущий узел (узел, перед которым вставляется новый), так и указатель на предыдущий (узел, после которого вставляется новый). Эти указатели обозначены соответственно t и p. Таким образом, при прохождении списка указатель p отстает на один шаг от t. Начальное значение p равно nil, а t равнво h. Следует иметь в виду 4 варианта вставки:

· вставка в пустой список – в этом случае голове списка h присваивается значение указателя s нового узла, а в указательное поле этого узла записывается nil;

· вставка в начало списка – распознается по сохранившемуся после начальной инициализации p=nil; в указательное поле нового узла записывается значение h (s^.l:=h), а новым значением головы списка становится s (h:=s);

· вставка в середину списка – сводится к коммутации нового узла s с узлами p и t; сначала в ссылочное поле нового узла записывается ссылка (адрес) узла t (s^.l:=t), затем адрес s копируется в ссылочное поле узла p (p^.l:=s);

· вставка в конец списка – распознается, когда список пройден до конца (t=nil), а место вставки в цикле WHILE не найдено; узел s коммутируется с последним узлом списка (с узлом p): в ссылочное поле p записывается адрес нового узла (p^.l:=s), а в ссылочное поле s – значение nil (s^.l:=nil).

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

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

1. Будем считать, что ГМ имеет только статическую память. Поэтому список сформируем в массиве целых чисел Spis, в котором для каждого узла отводится два последовательных слова – первое для поля inf, второе для поля link. Причем, с целью упрощения задачи в качестве указателя в поле link будем использовать не абсолютный адрес, а смещение (индекс) соответствующего слова ГМ в Spis, т.е. указатели будут изменяться в диапазоне 0..2*kuz-1. Очевидно, что в данной постановке задачи параметр fw подразумевается равным 16.

2. В программе на Паскале исходные данные для списка поставляются генератором случайных чисел. Поскольку природа происхождения данных для нашей задачи не имеет принципиального значения (лишь бы они носили случайный характер), мы можем в качестве них выбрать содержимое любой области памяти (например, объектный код самой программы сортировки списка). Для удобства обработки эти данные предварительно копируются в непрерывную область памяти Buf. Необходимый размер области Buf в битах определяется количеством узлов списка kuz и форматом слова fw ГМ: Vbuf=kuz*fw. В следующем варианте программы на Паскале исходные данные для списка берутся из области программы начиная с адреса переменной ih.

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

 

Program Prototip2; { второй вариант программы сортировки списка }

Uses Crt;

Label Cycl1, While1, EndWhile, InsUz, NextUz, InsHead, InsMed,

EndCycl1, Empty, InsEnd, Wcycl, endPrn;

Const kuz=10; { кол-во узлов }

Niil=255; { код для Nil }

Var Buf: Array [0..kuz-1] Of Word; { буфер для исх. данных }

Spis: Array [0..2*kuz-1] Of Word; { обл-ть памяти для списка }

h,p,t,s: Word; { переменные для указателей }

R0,R1,R2,R3: Word; { "регистры" ГМ }

Cnil: Word; { переменная для Nil }

ih: Word; {индекс для резервирования нового узла в Spis }

Begin

ClrScr; { очистка экрана }

Move(ih,Buf,SizeOf(Buf)); {заполнение Buf исходными данными}

R1:= 0;

R2:= kuz;

h:= Niil;

Cnil:= Niil;

ih:= 0;

Cycl1: {------------- Цикл создания узлов списка ------------- }

R0:= Buf[R1]; { взяли очередной inf -> R0 }

s:= ih; { New(s) - создали новый узел }

Inc(ih); { ih указ-т на следующий новый узел }

Inc(ih);

Spis[s]:= R0; { s^.i:=R0; inf -> в новый узел }

t:= h; { t - указатель на текущий узел }

p:= Niil; { p - указатель на предыдущий узел }

While1: { Цикл поиска и вставки узла в список }

If t = Niil Then Goto EndWhile;

R3:= Spis[t]; { R3:= t^.i }

If R3 > R0 Then Goto InsUz; { поиск места вставки }

NextUz: { переход к след. узлу}

p:= t; { предыдущий становится текущим }

Inc(t); { t:=t+1 для получения доступа в поле link}

t:= Spis[t]; { t:=t^.l переход к след. узлу }

Goto While1;

InsUz: { Реализация различных вариантов вставки }

If p = Niil Then Goto InsHead;

InsMed: { вставка в середину }

Inc(p); { p:=p+1 для получения доступа в поле link }

R0:= Spis[p]; { R0:= p^.l }

Spis[p]:= s; { p^.l:= s }

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= R0; { s^.l:= R0 }

Goto EndCycl1;

InsHead: { вставка в начало списка }

h:= s; { новое начало списка }

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= t; { s^.l:= t }

Goto EndCycl1;

EndWhile: { реализация других вариантов }

If p=Niil Then Goto Empty;

InsEnd: { вставка в конец списка }

Inc(p); { p:=p+1 для получения доступа в поле link }

Spis[p]:= s; { p^.l:= s}

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= Niil; { s^.l:= NIL }

Goto EndCycl1;

Empty: { вставка в пустой список }

h:= s;

Inc(s); { s:=s+1 для получения доступа в поле link }

Spis[s]:= Niil; { s^.l:=NIL }

EndCycl1:

Inc(R1); { увеличение счетчика цикла }

If R2 > R1 Then Goto Cycl1;{ If счетчик < kuz Then на начало цикла }

{----------- Прохождение и печать списка --------------------}

WriteLn(' Отсортированный список'); { вывод заголовка списка}

t:= h; { встали на начало списка }

Wcycl: { цикл прохождения списка }

If t = Niil Then Goto endPrn;{ While t <> NIL Do}

Write(Spis[t]:3); { Печать узла}

Inc(t); { t:=t+1 для получения доступа в поле link}

t:= Spis[t]; { t:=t^.l переход к след.. узлу }

Goto Wcycl;

endPRN:

ReadKey; { ждать нажатия клавиши}

End.

 

Результаты работы программы приведены на рис.3.

 

Отсортированный список

0 0 1 1 3 7 7 1191 6223 7432

Рис.3. Вывод программы Prototip2.

 

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

 

инд. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Spis 0 10 1 4 1 6 3 8 7 18 0 2 6223 16 1191 12 7432 255 7 14

h узел 0 узел 2 узел 3 узел 4 узел 5 узел 1 узел 8 узел 7 узел 9 узел 6

 

Рис.4. Структура массива Spis со списком.

 

Как видно из приведенной программы, она в основном состоит из простейших операторов типа:

· a:=b; где а – одиночная переменная или элемент массива;

b – тоже самое или константа, причем, и а и b

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

· Goto metka;

· If условие Then Goto metka;

· Inc(a);

Остальные операторы описывают достаточно сложные действия и поэтому требуют особого внимания при разработке программы на ГМ. К ним относятся: ClrScr, Move, Write, Writeln, ReadKey.

 

Определение данных.

Разработку программы ГМ начнем с определения данных для нее.

1. DW_ name,n

Директива определения n слов ГМ, первому из них присваивается

имя name. Если n=1, то этот параметр можно не указывать. С помощью

этой директивы могут объявляться массивы,переменные и регистры

общего назначения ГМ.

2. DB_ name,str,n

Директива определения строки символов ГМ с именем name. Если

параметр n не указан, то резервируется память под строку со

значением str, иначе резервируется n слов ГМ, отводимых под

строку, а str интерпретируется как подсторка заполнения этой

строки.

3. DF_ Fl

Директива определения флагового регистра Fl ГМ.

4. CONSTsection

Определение секции констант (псевдодиректива)

5. STACKsection n

Определение стека; n – размер стека.

6. DATAsection

Определение начала секции данных.

7. ENDdata

Определение конца секции данных.

8. CODEsection

Определение начала секции кода.

9. ENDcode

Определение конца секции кода.

 

Определие команд ГМ.

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

1. START

Команда начальной инициализации программы.

2. ClrScr

Команда очистки экрана.

3. Write txt

Команда вывод заданного текста txt на экран.

4. Move dest,source,n

Команда копирования области памяти source в область памяти

dest, n – число копируемых слов ГМ.

5. ClReg R

Команда очистки регистра или переменной.

6. MovI R,%c

Пересылка непосредственного значения c в регистр или

переменную.

7. MovSR R,S,i

Пересылка память-регистр,i индексирует память S(R <- S[i]).

8. MovRS S,R,i

Пересылка регистр-память,i индексирует память S(S[i] <- R).

9. Mov_ v,w

Команда пересылки v <- w, где v и w могут быть регистрами

или одиночными переменными.

10. NEW p

Команда резервирования нового узла. В р возвращается указатель

на вновь созданный узел. Неявно использует и автоматически

модифицирует указатель ih.

11. CMP_ v,w

Команда сравнения и установки флагов. Флаги устанавливаются

по результатам вычитания v-w.

12. JUMP metka

Команда безусловного перехода.

13. gmGT metka

Команда перехода по условию «больше».

14. gmEQ metka

Команда перехода по условию «равно».

15. INC_ R

Команда инкрементирования (R:=R+1), где R – регистр или

одиночная переменная.

16. WriteUz p

Команда вывода узла списка, р – указатель на узел.

17. ReadKey

Команда ожидания нажатия клавиши.

18. FINISH

Команда завершения работы программы

 

Ниже приведена программа для ГМ.

 

; " Создание отсортированного списка"

INCLUDE macros.inc; подключение файла с макросами

InitRealComputer; настройка на реальную ЭВМ

; две предыдущие макрокоманды обеспечивают выполнение программы ГМ на реальной ЭВМ

 

;************* Программа для гипотетической машины ***************

CONSTsection

kuz = 10; к-во узлов списка (kuz=1..127)

maskG = 1; маски для анализа флагового регистра на «больше»,

maskL = 2; «меньше» и

maskE = 4; «равно»

nil = 0FFh; признак конца списка

;---------------------------------------------------------------

STACKsection 100; объявление стека

;---------------------------------------------------------------

 

DATAsection; раздел описания данных ГМ

DW_ R0; R0-R3 -регистры общего назначения ГМ

DW_ R1;

DW_ R2;

DW_ R3;

DW_ Rtmp; рабочий регистр

DW_ h; указатель головы списка

DW_ t; указатель на текущий узел списка

DW_ p; указатель на предыдущий узел

DW_ s; указатель на новый узел

DW_ ih; индекс для резервирования нового узла

DW_ cNIL; переменная для хран-я знач-я NIL

DW_ i; рабочий индекс

DW_ Buf,kuz; буфер - источник информации для списка

DW_ Spis,2*kuz; память под список

DB_ eoLn,EndLine; признак конца строки для вывода

DB_ OutPut,endSTR,2; буфер вывода

DB_ num,'0123456789ABCDEF';табл. перевода в 16с/c

DB_ zag,<' Отсортированный список',EndLine>

DF_ Fl; флаговый регистр ГМ

ENDdata; конец секции данных ГМ

;---------------------------------------------------------------

CODEsection; секция кода ГМ

START; нач. инициализация программы

ClrScr; очистка экрана

Move Buf,Primer,kuz; загрузка буфера исх. инф-ей из сегмента кода

ClReg R1; R1 сч. цикла:= 0

MovI R2,%kuz; к-во узлов -> R2

MovI h,%NIL; h:= NIL

MovI Cnil,%NIL; Cnil:= NIL

ClReg ih; нач. знач-е индекса равно 0

Repeat:; Цикл создания списка

MovSR R0,Buf,R1; очередной inf взяли из Buf -> R0

NEW s; создали новый узел

MovRS Spis,R0,s; s^.i:=R0; inf-> в новый узел

Mov_ t,h; t:=h;

MovI p,%NIL; p:=nil

While1:; Цикл поиска и вставки узла в список

CMP_ t,Cnil; While t<> NIL Do

gmEQ EndWhile;

MovSR R3,Spis,t; R3:= t^.i

CMP_ R3,R0; if t^.i > R0

gmGT InsUz; Then InsUz

NextUz:; Else NextUz продолжаем искать место вставки

Mov_ p,t; p:=t

INC_ t; t:=t+1 для получения доступа в поле link

MovSR t,Spis,t; t:=t^.l переход к след. узлу

JUMP While1; повторение цикла поиска

InsUz:; Реализация различных вариантов вставки

CMP_ p,Cnil; If p=Nil Then InsFirst вставка в начало

gmEQ InsFirst; Else InsMed вставка в середину

InsMed:; вставка в середину списка

INC_ p; p:=p+1 для получения доступа в поле link

MovSR R0,Spis,p; R0:= p^.l

MovRS Spis,s,p; p^.l:= s

INC_ s; s:=s+1 для получения доступа в поле link

MovRS Spis,R0,s; s^.l:= R0

JUMP EndRepeat; завершение этого варианта вставки

InsFirst:; вставка в начало списка

Mov_ h,s; h:=s

INC_ s; s:=s+1 для получения доступа в поле link

MovRS Spis,t,s; s^.l:= t

JUMP EndRepeat; завершение этого варианта вставки

EndWhile:; реализация других вариантов

CMP_ p,Cnil; If p=NIL Then Empty - в пустой список

gmEQ Empty; Else InsEnd - в конец списка

InsEnd:; вставка в конец списка

INC_ p; p:=p+1 для получения доступа в поле link

MovRS Spis,s,p; p^.l:= s

INC_ s; s:=s+1 для получения доступа в поле link

MovRS Spis,Cnil,s; s^.l:= NIL

JUMP EndRepeat; завершение этого варианта вставки

Empty:; вставка в пустой список

Mov_ h,s; h:=s

INC_ s; s:=s+1 для получения доступа в поле link

MovRS Spis,Cnil,s; s^.l:=NIL

EndRepeat:

INC_ R1; увеличение счетчика цикла

CMP_ R2,R1; сравнение с kuz

gmGT Repeat; If счетчик < kuz Then Repeat на начало цикла

Write zag; вывод заголовка списка

Mov_ t,h; t:=h

Wcycl:; Прохождение и печать списка

CMP_ t,Cnil; While t <> NIL Do

gmEQ endPRN

WriteUz t; Печать узла

INC_ t; t:=t+1 для получения доступа в поле link

MovSR t,Spis,t; t:=t^.l

JUMP Wcycl; Goto Wcycl

endPRN:

ReadKey; ждать нажатия клавиши

FINISH; завершение программы

ENDcode; конец секции кода

;---------------------------------------------------------------

 

Выборка и запиь слов ГМ.

Чтобы выполнить программу на реальной ЭВМ необходимо для всех ее операторов написать макроопределения. На их сложность и объем в первую очередь влияет величина fw – формат слова ГМ. С методической точки зрения выберем fw как параметр и укажем диапазон его изменения: 8..255. Наиболее сложными операциями (макрокомандами) в такой постановке являются выборка и запись слова ГМ по заданному индексу в массиве. Алгоритмы выборки и записи поясняются ниже. Пусть в качестве исходных данных выбраны значения из некоторой области памяти. Шестнадцатеричные и двоичные коды этой области приведены на рис.5.

 

а)

1E 33 C0 50 B8 BD 13 8E D8 1E 07 B4 06 B0 00 B7 07 BA 4F 18 B9 00 00 CD 10 B4 02 B7 00 BA 00 00 CD 10 06 1E B8 1E 12 33 24 C0 2E 50 0E B8 28 BD 04 13 26 8E 1A D8 FF 1E 46 07 20 B4 32 06 44 B0 16 00 2A B7 36 07 30 BA

б)

00011110 00110011 1100000 0 01010000 10111000 101111 01 00010011 10001110 11011 000 00011110 00000111 1011 0100 00000110 10110000 000 00000 10110111 00000111 10 111010 01001111 00011000 1 0111001 00000000 00000000 11001101 00010000 1011010 0 00000010 10110111 000000 00

Рис.5. Пример исходных данных для списка (объектный код в начале

кодового сегмента)

 

Пусть для примера разрядность ГМ fw выбрана равной 23 бита. Тогда массив слов ГМ можно рассматривать как непрерывную последовательность бит. На рис.5б. выделены слова ГМ с индексами 0,2,4,…

Разберем алгоритм выборки слова ГМ из массива S в регистр или переменную R по заданному индексу i (команда MovSR R,S,i)(рис.6).

 

S[i] – слово ГМ

S

байт байт байт байт байт байт байт байт

ß адрес

байта S ß

00010000

maskS

ß rotate

ß адрес

байтаR ß

00000001

maskR

ß rotate

R

 

 

fw разрядов

Рис.6. Схема копирования слова ГМ в регистр или переменную.

 

Поскольку значение fw заранее неизвестно, выбираем наиболее универсальный алгоритм побитового копирование S[i] -> R. Выделение и копирование битов ведется от конца к началу с помощью двух двоичных масок maskS и maskR. Вначале maskS настраивается на последний бит S[i] (см. макроопределение InitMov). Адрес этого бита вычисляется по формуле A = fw*(i+1)-1 и представляет величину битового смещения в S, младшие 3 бита которого являются номером бита в байте, а старшие биты – смещением для этого байта. Таким образом, позиция «1» в maskS настраивается на выделение последнего бита слова ГМ в S. Аналогично позиция «1» в maskR соответствует младшему разряду R. После копирования очередного бита maskS и maskR подвергаются циклическому сдвигу влево настраиваясь на следующий бит. Когда биты очередного байта S или R скопированы, происходит уменьшение адреса этого байта. Момент уменьшения адреса определяется по единичному состоянию флага CF, в котором, как известно, дублируется выдвигаемый бит при циклическом сдвиге маски. Очевидно, что в общем случае, уменьшение адреса байта S или R может происходить асинхронно. Алгоритмы выборки и записи слова ГМ во многом совпадают, поэтому их общие части объединены в макрокоманде InitMov. В алгоритме выборки R предварительно обнуляется, поэтому если бит S в «1», то соответствующий бит R устанавливается в «1» командой OR. При записи (макрокоманда MovRS) копирование сводится к инвертированию некоторых бит S. Действительно, если соответствующие биты S и R совпадают, то копирования не нужно. Если же они имеют противоположные значения, то требуется инвертировать бит S. На рис.7 приведены значения слов ГМ после выборки их из области памяти, показанной на рис.5б.

 

0F19E0 142E2F 2271DB 01E07B 203580 02DC1E 749E31 390000 66885A 00ADC0

 

Рис.7. 23-разрядные слова ГМ в 16 с/c после их выборки из массива.

 

Алгоритмы остальных макрокоманд несложные и достаточно подробно прокомментированы в макроопределениях, поэтому предлагается изучить их самостоятельно. Все макроопределения помещены в файл macros.inc и подключаются к головной программе директивой include. Макрокоманда InitRealComputer осуществляет настройку программы ГМ для ее выполнения на реальной ЭВМ.

.286

fw = 23; разряность слова ГМ; fw = 8..255

fb = 8; разряность байта

kByte = fw/fb - ((fw - (fw/fb)*fb) GT 0); к-во байт для хранения 1 слова ГМ

; --2-- 23 ----16----

; -------7--------

; ----- --------true---------- (true= -1, false=0)

;при fw=23 2 - (-1) = 3; kByte=3

EndLine EQU 10,13,'$'; код перевода строки при выводе

EndSTR EQU ' ','$'; признак конца строки

ENDM

;--------------------------------------------------------------

CONSTsection MACRO

ENDM

;--------------------------------------------------------------

STACKsection MACRO n; описание стека

Stack1 SEGMENT STACK

dw n*kByte dup (?)

Stack1 ENDS

ENDM

;--------------------------------------------------------------

DATAsection MACRO; описание сегмента данных

Data1 SEGMENT

ENDM

;--------------------------------------------------------------

ENDdata MACRO; описание конца сегмента данных

Data1 ENDS

ENDM

;--------------------------------------------------------------

CODEsection MACRO; описание сегмента кода

Code1 SEGMENT

ENDM

;--------------------------------------------------------------

FINISH MACRO; описание завершения программы

ret

Primer endp

ENDM

;--------------------------------------------------------------

ENDcode MACRO; описание конца сегмента кода

Code1 ENDS

END Primer

ENDM

;--------------------------------------------------------------

START MACRO; стандартная инициализация EXE-программы

Assume ds:Data1,ss:Stack1,cs:Code1

Primer PROC far

push ds

xor ax,ax

push ax

mov ax,Data1

mov ds,ax

push ds;ds и es будут указывать на наш сегмент данных,

pop es;это необходимо для использования цепочечных команд

ENDM

;--------------------------------------------------------------

DW_ MACRO Name,n; описание слова ГМ в памяти РМ

IFB <n>; если параметр n не указан,

Name db kByte Dup (0); то резервируется 1 слово ГМ,

ELSE; иначе

Name db n*kByte Dup (0); резервируется n слов ГМ,

ENDIF

ENDM

;--------------------------------------------------------------

DB_ MACRO Name,str,n; описание строки ГМ в памяти РМ

IFB <n>; если параметр n не указан

Name db str; то резервируется строка со значением str

ELSE; иначе

Name db n*kByte Dup (str); резервируется (n*kByte) байт со значением str

ENDIF

ENDM

;--------------------------------------------------------------

DF_ MACRO Name; резервируем слово для флагового

DW_ FF; регистра ГМ и присваиваем имя Name

Name EQU FF+kByte-1; его последнему байту

ENDM

;--------------------------------------------------------------

MovI MACRO R,jj

; пересылка непосредственного значения jj в R ГМ; диапазон jj = 0..255

ClReg R; очистка R

mov byte ptr R+kByte-1,jj;jj -> мл. байт R ГМ

ENDM

;--------------------------------------------------------------

Mov_ MACRO Rd,Rs; пересылка Rs -> Rd

j5=0; j5 играет роль смещения

REPT kByte; цикл копирования

mov al,Rs+j5;

mov Rd+j5,al;

j5=j5+1;

ENDM;

ENDM

;--------------------------------------------------------------

CLReg MACRO Reg; очистка регистра

push di; сохранить di в стеке

; настройка цепочечной команды (ЦК) stosb

lea di,Reg; прм - es:di

cld; флаг направления DF:=0

xor al,al; очистка аккумулятора

mov cx,kByte; cx:=к-во повторения ЦК

REP STOSB; ЦК записи

pop di; восстановление di из стека

ENDM

;---------------------------------------------------------------

CMP_ MACRO Rd,Rs; сравнение Rd с Rs. (Rd-Rs)-> флаги

LOCAL mE,mG,mL,all; описание локальных меткок

; настройка цепочечной команды (ЦК) CMPSB

lea di,Rs; прм es:di

lea si,Rd; ист ds:si

cld; флаг направления DF:=0

mov cx,kByte; cx:=к-во повторений ЦК

mov byte ptr FL,0; обнуление флагового регистра

REP CMPSB; ЦК побайтного сравнения

je mE; If Rd=Rs Then mE

ja mG; If Rd>Rs Then mG Else mL

mL: or FL,maskL; FL:="меньше"

jmp all; завершение сравнения

mE: or FL,maskE; FL:="равно"

jmp all; завершение сравнения

mG: or FL,maskG; FL:="больше"

all:

ENDM

;---------------------------------------------------------------

JUMP MACRO metka; безусловный переход на metka

jmp metka

ENDM

;---------------------------------------------------------------

gmEQ MACRO metka; условный переход по "равно"

LOCAL m1

test FL,maskE; проверка флага "равно"

jz m1; If "равно" Then metka

jmp metka; Else m1

m1:

ENDM

;---------------------------------------------------------------

gmGT MACRO metka; условный переход по "больше"

LOCAL m1

test FL,maskG; проверка флага "больше"

jz m1; If "больше" Then metka

jmp metka; Else m1

m1:

ENDM

;---------------------------------------------------------------

gmGE MACRO metka; условный переход по "больше или равно"

LOCAL m1

test FL,maskE OR maskG; проверка флагов "больше" и "равно"

jz m1; If "больше или равно" Then metka

jmp metka; Else m1

m1:

ENDM

;---------------------------------------------------------------

Move MACRO dest,source,n

;копирование блока памяти source -> dest; n число копируемых слов ГМ

; настройка цепочечной команды (ЦК) MOVSB

push es; сохранение es и ds

push ds;

mov ax,seg dest; сегм. адрес прм -> es

mov es,ax;

mov di,offset dest; прм es:di

mov ax,seg source; сегм. адрес ист -> ds

mov ds,ax;

mov si,offset source; ист ds:si

cld; DF:=0

mov cx,n*kByte; уст-ка сч-ка цикла копирования

REP MOVSB; ЦК копирования

pop ds; восстановление es и ds

pop es;

ENDM

;---------------------------------------------------------------

INC_ MACRO R; инкремент R (R:=R+1)

j1 = kByte-1; j1:= смещение для последнего байта

add R+j1,1; прибавляем 1 к мл. байту; перенос -> CF

REPT kByte-1; цикл распространения возможного

j1 = j1 - 1; преноса в старшие байты R

adc R+j1,0; прм:=прм+ист+CF

ENDM

ENDM

;---------------------------------------------------------------

InitMov MACRO R,S,i

;предварит. настройка передачи R <--> S[i]; i - индекс слова ГМ в S

lea di,R+kByte-1; адрес последнего байта R -> di

lea si,S; адрес S -> si

mov al,fw; далее вычисляется адр. байта, содержащего

mov dl,i+kByte-1; последние биты S[i]; i -> dl

inc dl; (i+1) -> dl

mul dl; fw*(i+1) -> ax

dec ax; получили адрес последнего бита слова ГМ

mov bx,ax; в ax мл. 3 разряда определяют № бита в байте

shr bx,3; в bx выделили адрес байта

add si,bx; получаем смещение этого байта в сегм. данных

and al,7; al <- № последнего бита в байте

mov cl,al; далее формируем маску для выделения

mov dl,80h; этого бита

shr dl,cl; maskS -> dl для выделения бит S

mov dh,1; maskR -> dh для выделения бит R

ENDM

;---------------------------------------------------------------

MovSR MACRO R,S,i; пересылка S[i] -> R

;пересылка побитовая, начиная с последних бит S[i] от конца к началу

LOCAL S_to_R,kon,no1,no2; локальные метки

InitMov R,S,i; начальная настройка копирования

CLReg R; 0 -> R

mov cx,fw; fw -> cx к-во копируемых бит

S_to_R:; цикл копирования

test [si],dl; проверили состояние текущ. бита S[i]

jz kon; If S_bit=0 Then goto kon (don't copy)

or [di],dh; Else R_bit:= 1

kon: rol dl,1; циклич. сдвиг маски dl влево

jnc no1; If CF=0 Then адр.тек. байта S[i] не менять

dec si; Else уменьшаем адр. байта S[i]

no1: rol dh,1; циклич. сдвиг маски dh влево

jnc no2; If CF=0 Then адр.текущ. байта R не менять

dec di; Else уменьшаем адр. байта R

no2: loop S_to_R; конец цикла

ENDM

;---------------------------------------------------------------

MovRS MACRO S,R,i; пересылка R -> S[i]

; копирование побитовое, начиная с последних бит R от конца к началу

; если копируемый бит R совпадает с соотв. битом S[i], то нет копирования,

; если биты не совпадают, то инвертируется соотв. бит S[i]

LOCAL R_to_S,kon,m1x,m0x,toXOR,no1,no2; локальные метки

InitMov R,S,i; начальная настройка копирования

mov cx,fw; fw -> cx к-во копируемых бит

R_to_S:; цикл копирования

test [si],dl; проверили состояние текущ. бита S[i]

jz m0x; If S_bit=0 Then m0x

m1x: test [di],dh; Else If R_bit=1 Then goto kon (don't copy)

jnz kon; Else toXor

jmp toXOR;

m0x: test [di],dh; If R_bit=0 Then goto kon (don't copy)

jz kon; Else toXor

toXor: xor [si],dl; инвертирование бита S[i]

kon: rol dl,1; циклич. сдвиг маски dl влево

jnc no1; If CF=0 Then адр.тек.байта S[i]не менять

dec si; Else уменьшаем адр. байта S[i]

no1: rol dh,1; циклич. сдвиг маски dh влево

jnc no2; If CF=0 Then адр.тек. байта R не менять

dec di; Else уменьшаем адр. байта R

no2: loop R_to_S; конец цикла

ENDM

;---------------------------------------------------------------

New MACRO Pointer; возвращает указатель на новое слово ГМ

Mov_ Pointer,ih; индекс ih -> указатель Pointer

INC_ ih; ih:= ih+2 новое знач-е ih

INC_ ih;

ENDM

;--------------------------------------------------------------

Write MACRO txt

lea dx,txt; вывод txt на экран

mov ah,9h

int 21h

ENDM

;--------------------------------------------------------------

WriteUz MACRO t; вывод узла списка на экран (t - указатель)

MovSR Rtmp,Spis,t; тек. узел -> Rtmp

j3=0; j3 - смещение в Rtmp

REPT kByte; цикл перевода Rtmp в 16с/c

xor bx,bx; 0 -> bx

mov bl,Rtmp+j3; взяли текущ. байт в bl

shr bl,4; выделили ст. тетраду