УДК 681.3.06

Организация структур данных с помощью макросредств
ассемблера MACRO-11 СМ ЭВМ

Н.П.Вельдяксов

Описаны макросредства, расширяющие возможности языка ассемблер MACRO-11 СМ ЭВМ по описанию и обработке структур данных. Структуры данных описываются при помощи макрокоманд. Сложные структуры данных строятся иерархически, путем включения в качестве их элементов уже имеющихся структур. Ссылки на последние производятся посредством уникальных имен структур данных, подобно ссылкам на ранее определенные типы данных в языке Паскаль. Допускаются элементарные структуры данных (числовые, символьные, логические, перечислимые) и сложные (множества, массивы, записи). Записи допускаются как обычные, так и с вариантами. Возможны различные суперпозиции массивов и записей. Для обработки структур данных разработаны различные макрокоманды.Входную информацию для них можно задавать как на этапе написания программы, так и во время её выполнения.

В языках высокого уровня, например в Паскале [1], хорошо развит аппарат структур данных. Он позволяет достаточно адекватно отобразить объекты предметной области в информационные объекты программ. Это упрощает процесс разработки программ, повышает их читабельность, модифицируемость и, в конечном счете, повышает производительность труда программиста.

В языке программирования ассемблер MACRO-11 [2] для СМ ЭВМ, как и во многих других машинно-ориентированных языках, подобного аппарата поддержки структур данных нет. Однако в некоторых классах задач для отображения предметной области требуются сложные информационные структуры. При использовании обычных средств ассемблера структуры данных организуются и поддерживаются индивидуально для каждой структуры, что достаточно трудоемко. Такой подход к организации структур данных в MACRO-11, использующий только простейшие возможности языка, имеет определенные недостатки, например:

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

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

Рассматриваемый аппарат структур данных для ассемблера СМ ЭВМ MACRO-11 реализован на основе имеющихся в нем макросредств.

Описание структуры данных производится при помощи макрокоманд, конкретный набор и параметры которых задают вое характеристики структуры данных. Эти описания сами оформляются в виде макросов, в имена которых входят в качестве подстроки уникальные имена структур данных, называемые в дальнейшем ключами структур данных. Например, макрокоманда $S.SD является описанием структуры данных SD.

На этапе трансляции программы макрокоманды описания структур данных формируют по определенным правилам набор символов – имен и их значений, который полностью определяет структуры данных. Для каждой структуры данных имена этих символов уникальны, что достигается вхождением в них ключей структуры данных. Например символы SSD00T , SSD00L и аналогичные им (SSD... ) описывают структуру данных SD. Эти символы используются в программах в определенном для них смысле, что и обеспечивает возможность работы со структурами данных в ассемблере.

Покажем, каким образом описываются структуры данных. Элементарные структуры данных описываются макрокомандой $STER, в которой указываются ключ структуры данных, размер необходимой памяти и тип – характеристика возможных значений. Среди типов допускаются числовой тип, символьный, логический и перечислимый (в терминологии языка Паскаль). Приведем примеры описания элементарных структур данных:

.MACRO 
$S.CB 
;элементарная структура 
$STER 
CB, 2, B, CIS 
;данных CB размером в 
.ENDM 
 
;2 байта, числового типа
 
 
 
.MACRO 
$S.CI 
;элементарная структура 
$STER 
CI, 3, I, CIS 
;данных CI размером в 
.ENDM 
 
;3 бита, числового типа 
 
 
 
.MACRO 
$S.SI 
;элементарная структура 
$STER 
SI, 10, B, SIM 
;данных SI размером в 
.ENDM 
 
;10 байтов, символьного типа 
 
 
 
.MACRO 
$S.LO 
;элементарная структура 
$STER 
LO, 2, B, LOG 
;данных LO размером в 
.ENDM 
 
;2 байта, логического типа 
 
 
 
.MACRO 
$S.PE 
;элементарная структура 
$STER 
PE, 2, B, PER 
;данных PE размером в 
$SEP 
PE, <E1, E2, E3>
;2 байта, перечислимого 
.ENDM 
 
;типа, допускающего три значения 

На основе элементов перечисления можно определить сложный тип данных – множество, например :

.MACRO 
$S.SK 
;сложная структура данных 
$SMNO 
SK, 2, B, SKA 
;SK размером в 2 байта, 
$SEM 
SK, <E1, E2>
;типа множества, максимум 
.ENDM 
 
;из двух элементов 

К сложным структурам данных, поддерживаемым этим аппаратом, относятся также массивы и записи. Записи допускаются как обычные, так и с вариантами. Строятся они иерархически, путем указания в описании сложной структуры данных ее подструктур – уже имеющихся структур данных. Ссылки на последние производятся посредством их ключей, подобно ссылкам на ранее определенные типы данных в Паскале.

Проиллюстрируем на примерах средства описания записей, конструируя новые структуры данных из определенных выше:

.MACRO 
$S.Z1 
 
$SZAP 
Z1, C 
;запись Z1 постоянной длины 
$SELM 
Z1, CB, CB, D 
;поле CB – структура данных CB 
$SELM 
Z1, S1, SI, D 
;поле S1 – структура данных SI 
$SELM 
Z1, S2, SI, D 
;поле S2 – структура данных SI 
$SKZAP 
Z1 
;конец описания записи Z1 
.ENDM 
 
 

Здесь запись Z1 обычная без вариантов имеет постоянную длину (это задает параметр C ) и фиксированную структуру. Состоит из трех элементов CB, S1 и S2, являющихся структурами данных CB, SI и SI соответственно. Доступ к элементам осуществляется по их смещению от начала записи (параметр D). Заметим, что ключи полей (элементов) в рамках одной записи должны быть уникальными. Ключи полей вместе с ключом самой записи входят в имена символов, описывающих данные поля. Так, символ SZ1S1S -есть смещение поля S1 в записи Z1.

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

В качестве элементов записи могут выступать и сами записи:

.MACRO
$S.Z2 
 
$SZAP 
Z2, C
;запись Z2 постоянной длины
$SELM 
Z2, SK, SK, D 
;обязательное поле SK
$SELM 
Z2, ZA, Z1, D
;обязательное поле ZA – запись
$SELM 
Z2, SI, SI, D, F 
;необязательное поле SI
$SKZAP
Z2 
;конец описания записи Z2
.ENDM
 
 

Здесь в записи Z2 поля SKи ZA обязательные, а поле SI может отсутствовать (параметр F). Несмотря на это память под поле SI будет резервироваться в каждом экземпляре записи, доступ к полю SI будет осуществляться по постоянному смещению от начала записи SZ2SIS (параметр D). Флаг наличия поля SI расположится по смещению SZ2SIF. Поле ZA записи Z2 само является записью-структурой данных Z1.

Для исключения потерь памяти в случае отсутствия в записи некоторого поля его можно включать в запись о доступом по ссылке (параметр X), а не с доступом по смещению. Например, поле SI в записи Z3 :

.MACRO 
$S.Z3 
 
$SZAP 
Z3, V 
;запись Z3 переменной длины
$SELM 
Z3, SK, SK, D 
;поле SK прямого доступа
$SELM 
Z3, Z1, Z1, D 
;поле Z1 прямого доступа
$SELM 
Z3, SI, SI, X, F 
;поле SI с доступом по ссылке
$SKZAP
Z3 
;конец описания записи Z3
.ENDM 
 
 

Здесь память под необязательное поле SI с доступом по ссылке будет выделяться в записи только в случае его фактического наличия. Запись в этом случае имеет переменную длину (параметр V ). Записи переменной длины состоят из постоянной части, располагаемой в начале записи, и переменной части, располагаемой в конце записи. В постоянной части находятся ссылки на поля из переменной части. Так, в записи Z3 ссылка на поле SI находится по смещению SZ3SIX . Значением ссылки является смещение данного поля от начала данного экземпляра записи. В записях переменной длины организуется служебное поле длины записи.

Отметим, что записи имеют постоянную длину только тогда, когда все их элементы имеют постоянную длину и включены в них с доступом по смещению (параметр D ).

Флаг наличия можно заводить как на отдельное поле,так и на группу полей. Так, в записи Z4 (см.ниже) наличие двух полей Z1 и Z2 отражается одним флагом, находящимся по смещению SZ4FNF от ее начала:

.MACRO 
$S.Z4 
 
$SZAP 
Z4, V
;запись Z4 переменной длины
$SELM 
Z4, C1, CI, D 
;поле C1 прямого доступа
$SELM 
Z4, C2, CI, D 
;поле C2 прямого доступа
$SFLW 
Z4, FN
;флаг наличия для полей Z1, Z2
$SELM 
Z4, Z1, Z1, X 
;поле Z1 с доступом по ссылке
$SELM 
Z4, Z2, Z2, X
;поле Z2 с доступом по ссылке
$SKZAP
Z4 
;конец описания записи Z4
.ENDM 
 
 

Структура записей с вариантами, в отличие от обычных записей, для каждого экземпляра записи зависит от значения определенного перечислимого поля, называемого в данной записи дискриминантом. При описании записей с вариантами приводятся все возможные варианты структуры. Поскольку в одном экземпляре записи присутствует какой-то один вариант, память в постоянной части записи резервируется не на все возможные варианты одновременно, а на основе варианта, требущего ее максимального размера. Поля разных вариантов при этом будут использовать одно и то же пространство записи. Так, в приведенном ниже примере смещения полей SK и Z1 в записи Z5 одинаковы – это поля из разных вариантов, поэтому вместе в одном экземпляре записи они встречаться не могут:

.MACRO 
$S.Z5 
 
$SZAP 
Z5, V
;запись Z5 с вариантами
$SELM 
Z5, CB, CB, D
;поле CB
$SELM 
Z5, PE, PE, D 
;поле PE, дискриминант
$SVAR 
Z5, PE 
;начало вариантной части
$SELM 
Z5, SK, SK, D
;поле SK, вариант 1
$SELM 
Z5, SI, SI, X, F
;поле SI
$SGVAR 
Z5 
;граница вариантов
$SELM 
Z5, Z1, Z1, D
;поле Z1, вариант 2
$SELM 
Z5, Z3, Z3, X
;поле Z3
$SGVAR 
Z5 
;граница вариантов
$SELM 
Z5, Z4, Z4, X
;поле Z4, вариант 3
$SELM 
Z5, LO, LO, D
;поле LO
$SKVAR 
Z5
;конец вариантной части
$SKZAP 
Z5 
;конец описания записи Z5
.ENDM 
 
 

Рассмотрим средства описания массивов. Массивы в описываемом аппарате структур данных допускаются с ограниченным или неограниченным числом элементов. По своей сути они близки к массивам с постоянными или переменными границами языка ПЛ-1 [3]. При описании массива задаются его ключ, ключ структуры данных, являющейся элементом массива, а также информация об ограничении числа элементов, например:

.MACRO 
$S.M1 
;массив M1
$SMAS 
M1, SI, V 
;состоит из элементов SI
.ENDM 
 
;число элементов неограничено
 
 
 
.MACRO 
$S.M2
;массив M2
$SMAS 
M2, CB, C, 10 
;состоит из элементов CB
.ENDM 
 
;число элементов максимум 10

Здесь массивы M1 и M2 состоят из элементарных структур данных, в M1 их число неограничено (параметр V), в M2 – ограничено десятью (параметры C, 10).

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

.MACRO 
$S.M3
;массив M3
$SMAS 
M3, M1, V 
;состоит из массивов M1
.ENDM 
 
 
 
 
 
.MACRO 
$S.M4
;массив M4
$SMAS 
M4, M2, C, 4 
;состоит из массивов M2
.ENDM 
 
 

Элементами массива могут быть также и записи, например:

.MACRO 
$S.M5
;массив M5
$SMAS 
M5, Z3, V 
;состоит из записей Z3
.ENDM 
 
 
 
 
 
.MACRO 
$S.M6
;массив M6
$SMAS 
M5, Z2, C, 3
;состоит из записей Z2
.ENDM 
 
 

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

Массивы могут состоять из записей и записи могут содержать массивы, например:

.MACRO 
$S.Z6 
 
$SZAP 
Z6, C 
;запись Z6 постоянной длины
$SELM 
Z6, SK, SK, D
;поле SK - элементарное
$SELM 
Z6, Z1, Z1, D
;поле Z1 - запись
$SELM 
Z6, M2, M2, D, F
;поле M2 - массив
$SKZAP 
Z6
;конец описания записи Z6
.ENDM 
 
 
 
 
 
.MACRO 
$S.Z7 
 
$SZAP 
Z7, V 
;запись Z7 переменной длины
$SELM 
Z7, PE, PE, D 
;поле PE - элементарное
$SELM 
Z7, Z2, Z2, X, F
;поле Z2 - запись
$SELM 
Z7, M5, M5, X
;поле M5 - массив
$SKZAP 
Z7 
;конец описания записи Z7
.ENDM 
 
 

Представленный аппарат структур данных позволяет иметь:

1. Элементарные структуры данных: числовые, символьные, логические, перечислимые.
2. Сложные структуры данных: множества; массивы (одномерные) – с ограниченным и неограниченным числом элементов; записи – обычные и с вариантами.
3. Различные суперпозиции массивов и записей: массивы массивов, массивы записей; записи, содержащие записи и массивы.

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

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

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

Приведем некоторые макрокоманды обработки на примере переноса поля MP записи I0 п поле MP строящейся записи M. .Обе записи – M. и I0 имеют переменную длину. Поля MP включены в них с доступом по ссылке. В записи M. поле MP необязательное, а в записи I0 – обязательное. Пример получен на основе реальной программы – исполнителя директив файловой системы. В ней строится дескриптор определенного объекта (запись M.) на основе параметров директивы, представленных во входной заявке (запись I0). Соответствующий фрагмент листинга программы имеет вид:

.MACRO 
$S.M. 
;описание записи M.
$SZAP 
M., V 
 
$SELM 
M., MP, MP, X, F 
 
$SKZAP
M. 
 
.ENDM 
 
 
 
 
 
.MACRO 
$S.I0 
;описание записи I0
$SZAP 
I0, V 
 
$SELM 
I0, MP, MP, X 
 
$SKZAP 
I0 
 
.ENDM 
 
 
 
 
 
DL=2000 
 
;максимальная длина записи M.
AD: .BLKB DL 
 
;поле для построения записи M.
.LIST MEB 
 
 
 
 
 
$S$CLR 
AD, DL, R1
;предварительная очистка поля
 
MOV #AD, R1 
 
 
CLR (R1)+ 
 
 
CMP R1, #AD+DL 
 
 
BLO .-6 
 
 
 
 
;//R0 
 
;на R0 адрес записи I0
MOV #AD, R1
 
;адрес для построения M.
 
 
 
$S$INV 
R1, M.
;инициализация записи
 
MOV #SM.00V, (R1) 
;начальная длина записи M.
 
 
 
$S$MEV 
R1, R3, M., MP
;найти в M. место для поля MP
 
MOV R1, R3 
 
 
ADD (R1), R3 
;адрес для построения поля MP
 
 
 
$S$NEV 
R0, R2, I0, MP 
;найти в записи I0 поле MP
 
MOV R0, R2 
 
 
ADD SI0MPX(R0), R2 
;адрес поля MP в записи I0
 
 
 
$S$HEV 
AD,DL,R3,M.,MP,METKA,R2
;войдет ли MP в M.?
 
MOV (R2), (SP) 
;длина поля MP
 
ADD R3, (SP) 
;адрес конца строящегося поля
 
CMP (SP), #AD+DL 
;хватит ли места для поля MP?
 
BLO .+6
;да
 
JMP METKA 
;нет
 
 
 
$S$MOV 
R2, R3, MP, R5 
;пересылка поля MP из I0 в M.
 
MOV R3, -(SP) 
;сохранение регистра в стеке
 
MOV (R2), R5 
;длина поля MP в байтах
 
ASR R5 
;длина поля MP в словах
 
MOV (R2)+, (R3)+ 
;перепись MP из I0 в M.
 
SOB R5, .-2 
 
 
MOV (SP)+, R3 
;восстановление регистра
 
 
 
$S$VEV 
R1, R3, M., MP, MP 
;включение поля MP в запись M.
 
COM SM.MPF(R1) 
;установка флага наличия поля
 
MOV R3, -(SP) 
;сохранение регистра в стеке
 
SUB R1, R3 
;смещение поля MP в записи M.
 
MOV R3, SM.MPX(R1) 
;установка ссылки на поле MP
 
MOV (SP)+, R3 
;восстановление регистра
 
ADD (R3), (R1) 
;коррекция поля длины записи M.

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

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

Список литературы

1. Грогоно П.
   Программирование на языке Паскаль.
   М.: Мир, 1982.
2. Вигдорчик Г.В., Воробьев А.Ю., Праченко В.Д.
   Основы программирования на Ассемблере для СМ ЭВМ.
   М.: Финансы и статистика, 1983.
3. Гребенщиков Л.К., Лебедев В.Н.
   Решение задач на ПЛ-1 в ОС ЕС.
   М.: Финансы и статистика, 1981.

   Статья поступила в редколлегию 03.03.88,
   в редакцию 24.10.88.