На главную > Программисту> Статьи > Организация структур данных в ассемблере

Организация структур данных в ассемблере

Журнал ВАНТ

УДК 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
$SKZAPZ2 ;конец описания записи 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 с доступом по ссылке
$SKZAPZ3 ;конец описания записи 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 с доступом по ссылке
$SKZAPZ4 ;конец описания записи 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  
$SKZAPM.  
.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.

Интернет-конкурс Золотой сайт