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

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

В предметных областях, в которых ещё не устоялся традиционный набор достаточно универсальных обменных форматов, усилия часто сосредотачиваются на разработке такого формата. В качестве примера можно привести область ГИС и попытку внедрения там формата SDTS. Предполагалось, что каждое приложение ГИС должно было поддержать универсальный обменный формат, после чего проблема обмена данными будет решена. На примере SDTS можно видеть, что такой формат получается очень сложным, поскольку он должен поддерживать все возможности других существующих форматов. Записать информацию в этот формат достаточно легко, поскольку при этом используется его подмножество, соответствующее реализованным в данной системе возможностям, но прочитать оттуда данные гораздо сложнее, поскольку они могут быть записаны в соответствии с не реализованными в данной системе возможностями другой системы.

Ещё более серьёзной сложностью является невозможность заранее предсказать развитие данной предметной области, что может привести к необходимости пересмотра даже самого универсального на данный момент обменного формата. Также существенным недостатком обменных форматов является то, что они, как правило, являются очень громоздкими и сильно уступают в эффективности форматам конкретных систем, порождая файлы очень большого объёма. Хорошим примером для иллюстрации этого факта является формат PostScript: приходилось встречать такие файлы, объём которых превосходит объем полученного из них файла печати с разрешением 300 dpi для лазерного принтера (не PostScript'овского).

В принципе, данный подход можно считать особым подклассом универсальных обменных форматов. Тот же PostScript можно отнести и в этот подкласс: он содержит заголовок с описанием функций и шрифтов, используемых при описании собственно текста, причём, этот заголовок занимает значительную часть файла (а иногда и бó льшую часть) и, как правило, дублируется без изменений во всех созданных одним текстовым редактором файлах.

1. Спецификация интерпретации и спецификация редактирования.

По возможностям работы с описываемыми данными можно различать два уровня языков спецификации данных: спецификация интерпретации и спецификация редактирования.

1. Язык спецификации интерпретации.

Язык спецификации интерпретации должен позволять легко описывать интерпретацию произвольного (в рамках определённых ограничений) класса данных.

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

2. Язык спецификации редактирования.

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

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

2. Требования к языку спецификации.

Слова "легко", "простота" и т.п. часто употребляется при определении понятия "спецификация". Подразумевается, что запись некоторой информации на языке спецификации должна быть проще, чем на обычном языке программирования. Более существенным здесь, по мнению автора, является не субъективное понятие простоты, а отсутствие в спецификации избыточной информации. Т.е. надо стремиться к тому, чтобы в описании данных приходилось давать как можно меньше информации, являющейся следствием ранее заданной (система, читающая описание, должна воспринимать информацию не как тупой студент, которому всё нужно объяснять дважды и без которого, поэтому, проще вообще обойтись, а как грамотный специалист, который всё понимает с полуслова). Также желательно, чтобы не приходилось вдаваться в излишние подробности, например, если на самом деле не важно в каком порядке надо обрабатывать элементы массива, то код, который содержит цикл for i:=0 to N-1 do, можно считать избыточным. Именно поэтому язык спецификации должен быть как можно более декларативным: он должен описывать то, как размещаются данные, а не то, как их надо читать.

3. Идентификация типов данных, как базовая интерпретация данных.

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

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

Элементы данных могут быть составными - в этом случае внутри них можно выделить элементы меньшего размера.

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

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

В данной работе рассматривается язык спецификации данных FlexT (Flexible Types), который позволяет описывать интерпретацию статических данных, в первую очередь - в виде идентификации типов. Данный язык реально используется для описания форматов данных в программе просмотра/дизассемблере различных форматов файлов BinView, а также в дизассемблере программы для просмотра содержимого 32-разрядных исполняемых файлов Windows 95/NT (формат Portable Executable) Portable EXE Explorer.

1. Динамические и статические типы данных.

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

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

Размер элемента данных динамического типа и внутреннее размещение его составляющих могут зависеть от конкретных данных. Далее слово "динамический" будет использоваться именно в этом смысле. Примером динамических типов в традиционных процедурных языках являются строковые константы, как паскалевские, так и ASCIIZ: чтобы определить занимаемый ими размер нужно в первом случае прочитать первый байт, а во втором - просмотреть всю строку в поисках нулевого символа.

Понятно, что динамические типы данных непригодны в качестве типов переменных, по крайней мере, если этот тип изменяемый (в терминах [1]), поскольку присваивание новых значений элементам таких данных может означать изменение размера, а такие операции ни один компилятор не сможет эффективно поддержать. Для полей типов данных, содержащих те же строки или записи с вариантами, память сразу выделяется по максимуму. Примером поддержки компилятором динамического перераспределения памяти, занимаемой значением переменной, являются huge-строки 32-разрядных версий Delphi, память под которые автоматически запрашивается в куче, при этом сами переменные такого типа фактически являются указателями и всегда занимают 4 байта.

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

В качестве примера статических данных в коде программы можно привести RTTI Delphi - способ представления метаинформации о типах данных:

PTypeInfo = ^TTypeInfo;
TTypeInfo = record
  Kind: TTypeKind;
  Name: ShortString;
 {TypeData: TTypeData}
end;

PTypeData = ^TTypeData;
TTypeData = packed record
  case TTypeKind of

{Фрагмент файла TypeInfo.pas [2]}

Комментарий в записи TTypeInfo подсказывает, что поле TypeData идёт непосредственно после последнего символа строкового поля Name, размер которого зависит от длины имени конкретного типа. Поскольку смещение поля TypeData зависит от конкретных данных - имени типа, такую структуру нельзя непосредственно представить на Паскале - приходится писать специальный код для доступа к этому полю (фрагмент того же файла):

function GetTypeData(TypeInfo: PTypeInfo): PTypeData; assembler;
asm
  { ->  EAX Pointer to type info }
  { <-  EAX Pointer to type data }
  {it's really just to skip the kind and the name  }
  XOR  EDX,EDX
  MOV  DL,[EAX].TTypeInfo.Name.Byte[0]
  LEA  EAX,[EAX].TTypeInfo.Name[EDX+1]
end;

Подобные трудности испытывают все авторы книг по форматам файлов данных при попытке описать эти данные, например, на языке C, как в [3].

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

2. Использование механизма определения типов данных.

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

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

3. Необходимые конструкции.

При идентификации типов данных любые физические данные будем рассматривать как набор элементов данных. Каждый такой элемент характеризуется своим адресом, размером и интерпретацией (типом). Составные элементы данных разбиваются на более мелкие элементы.

Всю информацию, которую должна предоставить спецификация идентификации типов данных о каждом элементе данных, можно было бы разбить на набор утверждений о том а) На какие составляющие, каких типов этот элемент разбивается; б) Где находятся эти составляющие (каковы их адреса); в) Сколько места они занимают. При этом из того, что в рассматриваемых данных содержится некоторый элемент составного типа, выводится информация о типах и размещении его составляющих (из которой, в свою очередь, может выводиться информация о размере этого составного элемента).

Составляющие элемента данных могут размещаться либо на некотором фиксированном смещении от его начала, либо на некотором смещении от конца другой составляющей. Составной элемент некоторого типа может содержать либо фиксированное число составляющих, либо это число может определяться динамически, т.е. отличаться у разных экземпляров одного типа. Если число составляющих фиксировано, то их можно поименовать, в этом случае элемент данных можно описать как запись с полями - составляющими. При динамическом определении набора составляющих можно рассмотреть два основных случая: 1) когда содержание части полей определяет, какие ещё поля (фиксированное число) входят в состав записи - этот случай описывается при помощи вариантов; 2) когда число составляющих определяется динамически - при этом, т.к. размер спецификации конечен, она должна содержать итеративные элементы. Эти итеративные элементы можно выделить в массив. Более сложные случаи могут быть описаны при помощи комбинации массивов и вариантов.

Т.е. можно рассчитывать, что для описания произвольных структурированных составных элементов данных достаточно использовать конструкторы записи, массива и варианта (м.б. это утверждение можно и доказать, как теорему, но мы не будем тратить на это время).

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

4. Основные элементы языка FlexT.

Теперь рассмотрим более подробно особенности предлагаемого механизма определения типов.

1. Описание синтаксиса.

При описании синтаксиса конструкций языка будем пользоваться следующими обозначениями:

<...> - конструкция с именем ... .

<Expr> - выражение.

'...' - ключевые слова и символы берутся в кавычки;

[ ... ] - необязательная часть;

{...|...} - различные варианты продолжения;

{...|...|} - различные варианты продолжения, могут отсутствовать;

{...,'...'}* - последовательность из 0 или более одинаковых конструкций ... с разделителем '...';

{...,'...'}+ - последовательность из 1 или более одинаковых конструкций ... с разделителем '...';

nl - переход на новую строку.

Также следует упомянуть, что в языке FlexT перевод строки является разделителем, если он происходит в месте возможного окончания конструкции и то, что вложенные определения типов можно брать в круглые скобки..

2. Общие особенности.

1) Составляющие переменного размера.

Язык поддерживает поля записей и элементы массивов переменного размера, т.е. размер составляющих составных типов может зависеть от данных конкретного экземпляра этого типа.

2) Выражения, параметры и свойства типов.

Типы данных могут иметь ряд свойств, набор которых зависит от конструктора этого типа, например, размер или число элементов у массива, или номер случая у варианта. Каждый тип имеет свойство Size (Размер). Свойства могут задаваться конкретным значением при определении типа, либо некоторым выражением, которое вычисляет значение данного свойства через значения и/или свойства вложенных элементов данных сложного типа, а также, м.б. через значения параметров типа.

Некоторые правила для вычисления свойства Размер могут автоматически добавляться компилятором, если они не указаны явно, это касается, например, случая, когда известен размер всей записи и всех её полей, кроме последнего.

Параметры в объявлении типа представляют ту информацию, которую необходимо указать дополнительно при использовании (вызове) данного типа.

Выражения в языке оцениваются в ленивом режиме [4], т.е. они вычисляются только при необходимости получения значения параметра или свойства типа. В некоторых случаях это позволяет избежать переполнения стека.

3) Ссылки на свойства в выражениях.

Выражения вычисляются в контексте некоторого типа, ссылка на этот тип в выражении обозначается '@', при этом '@' ':' <Имя> означает ссылку на параметр или свойство <Имя> данного типа. Также в выражениях могут использоваться специальные конструкции:

<Переменная>'@' - ссылка на родительский тип, т.е. на тип, в контексте которого данный тип определён. Пример:

T1 struc
  int Cnt1
  int Cnt2
  array[@.Cnt1] of (array[@@.Cnt2] of word) Tbl
ends

Т.е. выражения для параметра конструктора вычисляются в контексте вызова конструктора, и значение свойства Count конструктора главного массива Tbl вычисляется в контексте типа хозяина T1, а для вложенного массива - в контексте массива Tbl, поэтому требуется написать @@.Cnt2, чтобы сослаться на поле Cnt2.

<Переменная>':' '@' - ссылка на тип-хозяин, т.е. на тип элемента данных, в который вложен рассматриваемый элемент. Т.к. некоторый тип может использоваться в разных составных типах, чтобы воспользоваться этой конструкцией необходим оператор приведения к типу с проверкой: <Переменная> 'AS' <Тип> .

'#' или '@' ':' '#' - номер вложенного элемента данных в содержащем его элементе, например, индекс массива.

4) Блок утверждений.

За определением любого типа, кроме вызова, могут следовать несколько блоков с дополнительной информацией, перед которыми стоит знак ':'. Блок утверждений содержит в скобках '[',']' и через ',' ряд утверждений о значениях свойств определяемого типа и параметров входящих в него элементов.

5) Вызовы типов.

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

При вызове типа параметры могут указываться либо позиционно, либо по имени (как при вызове методов интерфейсов COM).

Пример из файла FB09.RFI (Описание формата отладочной информации фирмы Borland):

TBaseSrcFilesTbl(Cnt,Base) array[@:Cnt] of PBaseSrcFileInfo(@:Base)

Здесь параметр в тип PBaseSrcFileInfo передаётся позиционно.

Другой пример из того-же файла:

PDebugSubSectionData(Kind,Sz) ^TDebugSubSectionData( @:Kind,@:Sz) - lfaFB09Base  FIXUP OFF;

TDebugSubSection(Sz) struc
    TDebugSubSectionType subsection
    Word iMod
    PDebugSubSectionData(Kind=@.subsection) lfo
    ulong cb
    raw[] rest
ends:[@.lfo:Sz=@.cb]

здесь при описании поля lfo записи TDebugSubSection используется передача фактических параметров по имени, причём параметр Kind передаётся непосредственно в вызове типа PDebugSubSectionData, а значение параметра Sz задаётся в блоке утверждений.

3. Основные конструкторы типов.

1) Целые числа.

Целое число является базовым типом данных, т.к. уметь читать целые числа необходимо, чтобы определять значения параметров всех остальных типов. В языке существует конструктор типов целых чисел:

   'NUM' {'+'|'-'|} '(' <Expr> ')',

который позволяет указать размер типа и является ли число знаковым. Также имеется ряд предопределённых типов: byte, int, long и т.д., которые просто являются предопределёнными вызовами конструктора NUM, например, тип int можно определить, как:

  int NUM-(2)

и т.д..

2) Перечислимый тип.

Позволяет поставить в соответствие некоторым значениям типа имена. Конструктор:

  'ENUM' [<Имя типа>] {'(' {<Имя>['='<Expr>] , ','} ')' |
      <Expr> ';'}

имеет два варианта:

1. В круглых скобках могут перечисляться пары <Имя>=<Expr>, если '=<Expr>' опущено - то имени сопоставляется предыдущее значение +1. Начальное значение = 0.
2. Если круглых скобок нет, то указывается выражения для сопоставления значению строки.

Если <Имя типа> опущено, то используется тип Byte.

3) Запись.

Состоит из фиксированного набора полей. Может содержать поля переменного размера, положение следующего поля определяется положением предыдущего. Синтаксис:

  'STRUC' NL
    {<Определение типа> <Имя поля>,NL}*
  'ENDS'

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

4) Вариант.

Тип составляющей определяется в зависимости от значения его параметра - выбранного случая. Поддерживаются два типа вариантов: с числовыми и со строковыми значениями. Синтаксис:

  'CASE' <Expr> 'OF'
    {<Список констант>':' < Определение типа>,NL}*
 ['ELSE' <Определение типа> NL]
  'ENDC'

где <Список констант> определяется как в традиционных языках программирования.

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

5) Массив.

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

  'ARRAY' [ '['  [<Expr>] ']' ] 'OF' <Определение типа> {'?' <Условие> ['!'<Определение типа>]|','<Значение>|}

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

Если после определения типа элемента массива идёт '?', то далее следует стоп выражение, которое оценивается для каждого элемента массива и равно 0 на последнем элементе. В этом случае тип последнего элемента может отличаться от типа остальных элементов массива, например, вместо целой записи остаётся только поле с некоторым признаком, - тип последнего элемента может быть задан после '!'. Для более простого случая вместо стоп условия можно указать стоп значение.

Здесь следует напомнить, что любое определение типа можно брать в круглые скобки, поэтому можно избежать неоднозначностей при определении массива с элементами- массивами.

6) Сырые данные.

Служат для отображения блока данных, про которые ничего не известно, кроме их размера, в виде шестнадцатеричного дампа. Синтаксис:

  'RAW' '[' [<Value>] ']'

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

7) Выравнивание.

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

  'ALIGN' <Expr>  ['AT' <Expr> ';']

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

8) Абстрактные типы данных.

Некоторый элемент данных может быть представлением какого-то более абстрактного типа данных [1]. Простейший пример: тип "индекс" в .obj - файлах [5]:

  if (first_byte & 0x80)
    index_word = (first_byte & 7F) * 0x100 + second_byte;
  else
    index_word = first_byte;

Т.е. для экономии места небольшие (<0x80) целые числа кодируются одним байтом, а числа побольше - двумя. Для описания такого типа данных придётся использовать запись с вариантным полем, но во всей остальной спецификации эти низкоуровневые подробности представления индексов абсолютно неинтересны, и было бы лучше иметь возможность заменять все ссылки на данные типа индекс тем числом, которое эти данные представляют. Для описания абстрактных типов данных предполагается реализовать специальный механизм интерфейсов.

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

9) Адресные пространства, адресные блоки и указатели

Некоторые составляющие компактных блоков могут быть указателями - ссылками на другие элементы данных. В простейшем случае значением указателя может быть смещение от начала файла или какая-то линейная функция от него. В более сложном случае значением указателя может быть виртуальный адрес в некотором адресном пространстве. В это адресное пространство могут входить один или несколько адресных блоков, каждый из которых характеризуется своим начальным виртуальным адресом и виртуальным размером (этот размер нужен для определения неинициализированных данных программ). Пример таких данных - 32-разрядный исполняемый файл Windows 95/NT [6].

Таким образом, элемент данных может являться адресным блоком, при этом может быть указано его адресное пространство, виртуальный адрес в этом пространстве и виртуальный размер. При объявлении типа данных указателя может быть задано адресное пространство, в которое он ссылается (а также смещение и коэффициент).

Синтаксис указателя:

  '^' <Определение типа> [*<Expr>] [{'+'|'-'}<Expr> ] [ 'HIDEREF' ] [ 'FIXUP' {'ON'|'OFF'} ] 
    ['NIL' {'=' <Expr> | ':' <Expr> | '-'}]  ['NEAR' ['=' <Имя типа>] <Ссылка на блок> ] [',' 'REF' '=' <Expr>';']

Первые два выражения должны сразу оцениваться, они задают коэффициент и смещение при вычислении адреса по числовому значению данного типа. Вместо них можно после 'REF' указать более сложное выражения для вычисления адреса. После 'NIL' может, либо указываться конкретное значение '=' <Expr>, соответствующее отсутствию ссылки, либо условие ':' <Expr> для проверки на отсутствие ссылки, либо то, что любое значение надо рассматривать, как ссылку ('-'). По умолчанию в качестве Nil рассматривается значение = 0. 'NEAR' означает, что ссылка идёт в конкретный блок, иначе она рассматривается как виртуальный адрес в текущем адресном пространстве. '=' <Имя типа> означает, что размер указателя равен размеру данного типа.

10) Машинные команды.

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

4. Ограничения предлагаемого подхода.

Даже при наличии развитого механизма спецификации абстрактных типов данных, всё равно возможны ситуации, в которых нельзя обойтись чисто декларативным подходом. Это происходит в тех случаях, когда длина формулы, описывающей зависимость между элементами данных, или между данными и их интерпретацией может неограниченно расти. Например, это относится к упакованным данным, для описания кодирования/декодирования которых необходимо описать алгоритм упаковки/распаковки (использующий для хранения информации достаточно сложные структуры данных), причём, алгоритм распаковки иногда неочевиден, даже если задан алгоритм упаковки. Другой пример - блок машинного кода: для его полного разделения на код и данные может потребоваться моделирование исполнения команд.

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

5. Заключение.

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

На языке FlexT с различной степенью завершённости было описано более десятка различных форматов файлов, в основном это были исполняемые и другие файлы, содержащие программный код, что объясняется областью интересов автора. Вот аббревиатуры некоторых из этих форматов: EXE (MZ,NE,LE), ELF, CLA, TPU, OBJ, BGI, TTF, HLP, DBF. Также конструкции языка использовались при декодировании различных программ и описании характерных для конкретных компиляторов форматов данных, например, RTTI Delphi 2.0, 3.0. Некоторые форматы удавалось описать практически с одного прохода, т.е. по мере чтения документации получалось сразу переводить содержащиеся там сведения в конструкции языка FlexT, а при рассмотрении других форматов обнаруживались недостатки языка, некоторые из которых не устранены до сих пор. Развитие языка должно привести к тому, чтобы можно было описывать с ходу достаточно широкий класс форматов данных. При работе с описаниями форматов в редком из них не были обнаружены ошибки. Т.е. переход от описания для человека к описанию для машины, которое можно сразу же проверить на настоящих данных, приводит к существенному повышению достоверности информации, и в этом может состоять один из наиболее важных результатов применения рассматриваемого языка.

Вообще, данную область знаний можно рассматривать, как идеальный полигон для разработки и проверки методов представления и использования точных (а не химических, биологических и т.д.) знаний, поскольку здесь мы уже располагаем исчерпывающей информацией об объекте исследования, и задача состоит лишь в том, чтобы представить эту информацию наилучшим образом для её наиболее полного использования. Например, программа-эмулятор PDP-11 [8], на которой, не хуже чем на настоящем железе, прекрасно загружается операционная система и запускаются все прикладные программы, содержит в себе полную информацию о моделируемой машине, но эта информация похоронена в программном коде, предусматривающем её использование лишь одним определённым способом. Весь вопрос состоит в том, чтобы представить сведения о системе в пригодном для многоцелевого использования виде. Данная работа предлагает подход для решения необходимой для этого подзадачи - описания способов хранения информации.

6. Приложение. Пример спецификации.

В качестве примера применения языка FlexT рассмотрим спецификацию формата файла класса Java-машины [9]. Для данной системы команд кодирование машинных инструкций также легко поддаётся описанию.

1. Спецификация структур данных файла класса Java-машины (cla.rfh).

set byteorder rev
type
  u1 byte
  u2 word
  u4 ulong
  TCPInfoTag enum u1 (
    C_Class = 7,
   ..............
    C_Utf8 = 1
  )
  TConstNDX u2
  TUtf8NDX u2
  TClassNDX u2
  TNameTypeNDX u2
  TRefInfo struc
    TClassNDX class_index
    TNameTypeNDX NameTypeNdx
  ends
  TLongInfo struc
    u4 high_bytes
    u4 low_bytes
  ends
  TNameTypeInfo struc
    TUtf8NDX nameNdx %Utf8
    TUtf8NDX descrNdx %Utf8
  ends
  TUtf8Str struc
    u2 len
    array[@.len] of Char val %Utf-8
  ends
  cp_info struc
    TCPInfoTag Tag
    case @.Tag of
      C_Class: TUtf8NDX %name_index,Utf8
      C_Fieldref,
      C_Methodref,
      C_InterfaceMethodref: TRefInfo
      C_String: TUtf8NDX %string_index
      C_Integer: u4 %Bytes
      C_Float: u4 %Bytes,IEEE 754
      C_Long: TLongInfo
      C_Double: TLongInfo
      C_NameAndType: TNameTypeInfo
      C_Utf8: TUtf8Str
    endc info
  ends
  attribute_info forward
  TFieldAccessFlags set 16 of (
    ACC_PUBLIC =    0, 
   ....................
    ACC_TRANSIENT = 7

  )
  field_info struc
    TFieldAccessFlags access_flags
    TUtf8NDX nameNdx
    TUtf8NDX descrNdx
    u2 attr_count
    array[@.attr_count]of
        attribute_info   attributes
  ends
  TMethodAccessFlags set 16 of (
    ACC_PUBLIC =    0, 
   ...................
    ACC_ABSTRACT = 10
//no implementation 
  )
  method_info struc
    TMethodAccessFlags access_flags
    TUtf8NDX nameNdx
    TUtf8NDX descrNdx
    u2 attr_count
    array[@.attr_count]of 
        attribute_info attributes
  ends
  TClassAccessFlags set 16 of (
    ACC_PUBLIC =    0, 
   ...................
    ACC_ABSTRACT = 10
  )
  TClassFile struc
    u4 magic
    u2 minor_version
    u2 major_version
    u2 C_pool_count
    array[@.C_pool_count-1]of 
            cp_info C_pool
    TClassAccessFlags access_flags
    TClassNDX this_class
    TClassNDX super_class
    u2 interfaces_count
    array[@.interfaces_count]of 
            TClassNDX interfaces
    u2 fields_count
    array[@.fields_count] of 
            field_info fields
    u2 methods_count
    array[@.methods_count]of 
            method_info methods
    u2 attr_count
    array[@.attr_count]of 
            attribute_info attributes
  ends
data
0000 TClassFile Hdr
type
  TUtf8NDX enum TUtf8NDX
     Hdr.C_pool[@-1].info.C_Utf8.val;
  TClassNDX enum TClassNDX
     Hdr.C_pool[@-1].info.C_Class;
  TNameTypeNDX enum TNameTypeNDX
     Hdr.C_pool[@-1].info.
       C_NameAndType.nameNdx;
  TRefNDX enum u2
     Hdr.C_pool[@-1].info.
       C_Fieldref.NameTypeNdx;
  TFldRefNdx TRefNDX
  TMethRefNdx TRefNDX
  TIMethRefNdx TRefNDX
include java_cod.rfi
type
  TAttrData raw[]
  TCodeExcRec struc
    u2 start_pc
    u2 end_pc
    u2 handler_pc
    TClassNDX catch_type
  ends
  TCodeAttr struc
    u2 max_stack
    u2 max_locals
    u4 CodeLen
    TOpSeries code
    u2 ExcTblLen
    array[@.ExcTblLen]of 
      TCodeExcRec exc_tbl
    u2 AttrCnt
    array[@.AttrCnt]of 
      attribute_info attributes
  ends:[code:Size=@.CodeLen]
  TExcAttr struc
    u2 NumExc
    array[@.NumExc]of TClassNDX ExcNdxTbl
  ends
  TLinNumRec struc
    u2 pc
    u2 l
  ends
  TLinNumAttr struc
    u2 Len
    array[@.Len]of TLinNumRec LinNumTbl
  ends
  TLocVarRec struc
    u2 start_pc
    u2 len
    TUtf8NDX name_index
    TUtf8NDX descr_index
    u2 index
  ends
  TLocVarTblAttr struc
    u2 Len
    array[@.Len]of TLocVarRec LocVarTbl
  ends
  attribute_info struc
    TUtf8NDX name_index %Ult8
    u4 len
    case Hdr.C_pool[@.name_index-1].
         info.C_Utf8.val of
      'SourceFile': TUtf8NDX
      'ConstantValue': TConstNDX
      'Code': TCodeAttr
      'Exceptions': TExcAttr
      'LineNumberTable': TLinNumAttr
      'LocalVariableTable': TLocVarTblAttr
    else
      TAttrData
    endc info
  ends:[info:Size=@.len]

2. Фрагменты спецификации системы команд Java- машины(java_cod.rfi).

type
TOpKind enum u1 (
  aaload = 0x32,
..................
  wide = 0xc4)
TIntSIRec struc
  u1 locndx
  sint c
ends
...............................
TWideOp struc
%modifies index
  TOpKind K
  case @.K of
    iload, fload, aload, lload,
    dload, istore, fstore, astore,
    lstore, dstore, ret: u2
    iinc: TIntIRec
  endc Op
ends
TOp struc
  TOpKind K
  case @.K of
    aload,astore,bipush,dload,
    dstore,fload,fstore,iload,
    istore,lload,lstore,ret: u1
    anewarray,checkcast,
    instanceof: TClassNDX
    getfield,getstatic,putfield,
    putstatic: TFldRefNdx
    invokespecial,invokestatic,
    invokevirtual: TMethRefNdx
...................................
    sipush: int
    wide: TWideOp
  endc Arg
ends:displ=(@.K,' ',@.Arg)
TOpSeries array of TOp

3. Пример программы Java.

import java.awt.*;
import java.applet.*;
public class Hello extends Applet
  {
   Image art; 
   public void init() {
     art = getImage(getDocumentBase(),
getParameter("image"));
   }
   public void paint(Graphics g)
     {
      Font font = new Font("TimesRoman", Font.BOLD,24);
      g.setFont(font);
      g.drawString("Hello",5,25);
      g.drawImage(art, 100, 100, this);
     }
  }

4. Фрагмент файла результата идентификации типов данных.

0000:Hdr:
TClassFile = (magic:CAFEBABE;
 minor_version:0003; major_version:002D;
 C_pool_count:003A; C_pool:(
  0:(Tag:C_String{08};
info:'image'{001D}),
..........................................
  56:(Tag:C_Utf8{01}; info:(len:000A;
   val:'Hello.java')));
 access_flags:[ACC_PUBLIC];
 this_class:'Hello'{0006};
 super_class:'java/applet/Applet'{0005};
 interfaces_count:0000; interfaces: ();
 fields_count:0001; fields: (
  0:(access_flags:[]; nameNdx:'art'{0023};
   descrNdx:'Ljava/awt/Image;'{0032};
   attr_count:0000; attributes: ()));
 methods_count:0003; methods: (
  0:(access_flags:[ACC_PUBLIC];
   nameNdx:'init'{0028};
descrNdx:'()V'{0038};
   attr_count:0001; attributes: (
    0:(name_index:'Code'{0026}; len:0000002F;
     info:(max_stack:0005; max_locals:0001;
      CodeLen:00000013; code: (
       0:aload_0{2A} ,1:aload_0{2A} ,
       2:aload_0{2A} , 3:invokevirtual{B6}
        'getDocumentBase'{0010},4:aload_0{2A},
       5:ldc{12} 01, 6:invokevirtual{B6}
        'getParameter'{000F},
       7:invokevirtual{B6} 'getImage'{000D},
       8:putfield{B5} 'art'{000A},9:return{B1}
      ); ExcTblLen:0000;
exc_tbl: ();
      AttrCnt:0001; attributes: (
       0:(name_index:'LineNumberTable'{0020};
        len:0000000A; info:(Len:0002;
        LinNumTbl: (0:(pc:0000; l:0009),
         1:(pc:0012; l:0008))))))))),
  1:(access_flags:[ACC_PUBLIC];
   nameNdx:'paint'{0035};
   descrNdx:'(Ljava/awt/Graphics;)V'{001A};
   attr_count:0001; attributes: (
    0:(name_index:'Code'{0026}; len:00000052;
     info:(max_stack:0005; max_locals:0003;
      CodeLen:0000002A; code: (
       0:new{BB} 'java/awt/Font'{0004},
       1:dup{59} ,2:ldc{12} 02,3:iconst_1{04} ,
       4:bipush{10} 18, 5:invokespecial{B7}
        '<init>'{000E}, 6:astore_2{4D} ,
       7:aload_1{2B} ,8:aload_2{2C} ,
       9:invokevirtual{B6} 'setFont'{000C},
       10:aload_1{2B} ,11:ldc{12} 03,
       12:iconst_5{08} ,13:bipush{10} 19,
       14:invokevirtual{B6} 'drawString'{000B},
       15:aload_1{2B} ,16:aload_0{2A} ,
       17:getfield{B4} 'art'{000A},
       18:bipush{10} 64, 19:bipush{10} 64,
       20:aload_0{2A} , 21:invokevirtual{B6}
        'drawImage'{0009}, 22:pop{57},
       23:return{B1} ); ExcTblLen:0000;
      exc_tbl: (); AttrCnt:0001; attributes: (
       0:(name_index:'LineNumberTable'{0020};
.........................................
  2:(access_flags:[ACC_PUBLIC];
   nameNdx:'<init>'{002F};
   descrNdx:'()V'{0038};
  ......................
 attr_count:0001; attributes: (
  0:(name_index:'SourceFile'{0022};
   len:00000002;
info:'Hello.java'{0039})))

7. Литература.