В Plan 9, а также ее идейной наследнице Inferno OS, есть одна полезная утилита, которая называется xd. Наша команда подумала, что написание этой утилиты является довольно полезным и интересным упражнением. Давайте сделаем это на D!
Предназначение этой утилиты утилиты простое — она выводит поданные ей файлы в одном из определенных форматов. Формат выбирается пользователем и включает в себя вывод в шестнадцатеричном, восьмеричном и десятичном представлении, а также предлагает выбор в виде каких структурных единиц выводить — байтах, словах, удвоенных словах или же учетверенных. Утилита xd в операционных системах Plan 9 и Inferno OS является штатной и помогает в исследовании бинарных и иных файлов.
Синтаксис у нее достаточно своеобразный, хотя и описан в духе Unix утилит, и выглядит он примерно так:
xd [-u] [-r] [-s] [-a{odx}] [-c|{b1w2l4v8}{odx}] ... file ...Опции означают следующее:
- -u Небуферизованный вывод. После каждого считанного куска файла (chunk, в терминологии xd из Inferno OS) буфер сбрасывается и генерируется новый входной кусок для обработки утилитой. (Честно говоря, автор блога, который работал с описанием утилиты не понял, о чем это они — у них вывод итак буферизованный, с учетом того, что они в буфер утилиты помещают куски файла и иначе утилита не работает — об этом мы расскажем дальше).
- -r Помечает повторяющие куски файла. Первый блок выводится как есть, остальные его повторяющие фрагменты обозначаются звездочками. Остальные фрагменты файла выводятся, как есть.
- -s Инвертировать порядок байтов для каждых 4 байтов из входного куска. (Спорная опция, как нам думается. Могли бы реализовать выбор для скольких байтов проводить инверсию — 2, 4, 8, но о том почему такие числа — расскажем далее).
- -a Формат адреса(в исходном man для xd встречается еще и иной термин — offset, т.е. смещение. Будем использовать оба варианта). Допустимы следующие варианты, которые задаются сразу за этой опцией: o — восьмеричный, d— десятичный и x — шестнадцатеричный. Иных вариантов нет, по умолчанию, формат — десятичный.
- -c|{b1w2l4v8}{odx}Формат для вывода единиц из считанного файла. Сама xd считывает файл в виде 16-байтных кусков (т.н. chunk) и выводит каждый такой фрагмент в строку, но предварительно делается разбиение этих кусков на единицы (т.н. unit) по 2, 4 или 8 байтов перед которыми следует в качестве префикса адрес считанного куска (считается от начала файла). Формат указывает для xd на какие единицы поделить считанные фрагменты и в каком виде их вывести. Допустимые варианты включают в себя следующие: указание одной из цифр (1, 2, 4, 8) и одного из символов формата (совпадают с таковыми из формата адреса: o, d, x — восьмеричное, десятичное или шестнадцатеричное представление). Также разрешено применять следующие синонимичные обозначения вместо цифр (перечислены в порядке следования тех цифр формата, которым синонимичны обозначения): b1 — байтовые единицы, w2 — единицы представлены словами (2 байтными величинами), l4 — в качестве единиц применяются 4-байтные (учетверенные машинные слова) блоки и v8 — единицы являются 8-байтными. После синонимов также должен быть указан формат представления (система счисления — восьмеричная, десятичная или по-умолчанию — шестнадцатеричная). Также есть специальный случай, к которому указание цифр и формата представления неприменимо — это опция -c, которая выводит кусок в виде байтов, но каждый байт выводится не как число, а как символ из таблицы ASCII.
- Самой последней опцией является список файлов, которые будут подвергнуты выводу, и которые выводятся по очереди.
Исходя из описанного, можно вывести, то что xd — является по своей сути специфическим просмотрщиком файлов, который можно настроить с помощью подачи необходимых опций. С учетом того, что утилита обращается к содержимому файла как к потоку байтов, это может быть очень ценным при анализе и проверке различных файлов.
В нашей версии xd, мы попытаемся повторить весь функционал оригинальной утилиты, за исключением некоторых особенностей: мы не делали небуферизованный ввод (т.е. опция -u игнорируется), также мы не делали прием сразу множества форматов в одной строке (т.е. чтобы файл сразу выводился в различных вариантах) и не проверяли эту особенность. Также наша версия в отличии от оригинальной, может принимать опции -b, -w, -l и -v, поскольку на наш взгляд, синонимы выбраны запредельно странно.
В утилите xd мы пошли также несколько иными путями относительно форматов вывода (особенно десятичного и восьмеричного), сделав их не разной ширины, а одинаковой (с учетом дополнения нулями), а также сформировали две функции, реализующие функционал xd. Обе эти функции носят имя xd, но отличаются тем, как принимают аргументы для своей работы: первая версия функции принимает диапазон, форматы вывода кусков файла и адреса, а также флаг, который показывает считаются ли повторения; у второй — набор аргументов почти такой же, но аргументы подаются не в виде специально подготовленных структур, а в виде строк, а также добавляется флаг, который показывает идет ли набор единиц в обратном байтовом порядке.
Первая функция xd является универсальной и может быть частью какой-либо библиотеки (в будущем, скорее всего станет частью библиотеки styx2000), вторая версия является прикладной версией и служит для реализации самой утилиты.
После того, как мы описали строение нашей версии перейдем к реализации специализированных структур, которые нужны для первой версии функции xd. Таких структур 4, и идею для их реализации подсказал сам man для xd из Inferno, и структуры называются WIDTH, STYLE, ORDER и структура, которая объединяет эти три абстракции — XDFORMAT.
Структура WIDTH нужна для представления единиц, на которые будет разбиваться один 16-байтный кусок файла (а точнее, байтового диапазона) и определяет сколько нужно байтов для представления одной единицы. В качестве единиц могут быть: байт (1 байт), слово (2 байта), удвоенное слово (4 байта) и учетверенное слово (8 байт). Сокращения от названия единиц с указанием их размера в байтах и составляют структуру WIDTH:
/// Size of units in chunk
enum WIDTH {
/// 1 byte
BYTE = "1",
/// 2 byte
WORD = "2",
/// 4 byte
DWORD = "4",
/// 8 byte
QWORD = "8"
};Структура STYLE определяет формат в котором будут выводится или адрес в файле или же единицы, которые составляют один кусок файла. Варианты STYLE которые могут быть совпадают с видом представления числовых величин: восьмеричное, десятичное и шестнадцатеричное. Значения внутри этого перечисления служат флагами формата при выводе значений и будут использоваться самой функцией xd для печати.
Само перечисление STYLE описывается так:
/// Number format for values in dump
enum STYLE {
/// Octal representation
OCTAL = "o",
/// Decimal representation
DECIMAL = "d",
/// Hexadecimal representation
HEXADECIMAL = "X"
};Для реализации работы флага обратного порядка байтов (применяется для кусков разбитых на единицы по 4 байта, т.е. на удвоенные слова) применяется перечисление ORDER, которое имеет два значения — LITTLE и BIG, соответственно для указания порядков байтов little-endian и big-endian:
/// Byte order in units
enum ORDER {
/// LE order
LITTLE,
/// BE order
BIG
};Эти три перечисления нужны для реализации структуры, которая будет представлять собой формат для вывода куска файла, и называется эта структура у нас XDFORMAT. Она включает в себя поля width, styleи order, которые хранят значения, выбранные из перечислений, описанных ранее. Помимо этих полей, в структуре есть поле isASCII, которое необходимо для опознавания флага -c утилиты и указания вывода в формате ASCII, если был выбран вывод в виде печатных символов из таблицы ASCII.
Структура XDFORMAT описана так:
/// Format for output dump
struct XDFORMAT
{
/// Default format is 4x
WIDTH width = WIDTH.DWORD;
STYLE style = STYLE.HEXADECIMAL;
ORDER order = ORDER.LITTLE;
/// Special case for format: WIDTH.BYTE
bool isASCII = false;
}После этого, для реализации функций семейства xd нам потребуется ряд утилитарных функций…
Первая такая функция — это приведение значение из перечисления enum, к тому типу, которые был представлен в самом перечислении. Сделать можно это следующим образом:
/// Cast enum to its original type
auto EnumValue(E)(E e) if(is(E == enum))
{
OriginalType!E tmp = e;
return tmp;
}Вторая такая функция — это упаковка потока байтов в соответствующий тип, с учетом некоторых оптимизаций. Данная функция нужна будет для разбивки считанного из файла куска (по умолчанию, 16 байт, но файл по факту может иметь куски меньшего размера) на единицы, и по факту выполняет формирование только одной такой единицы из поданного массива байтов и указанного типа. В качестве указания типов могу фигурировать следующие: ubyte, ushort, uint и ulong, указание любого другого (даже числового типа) приведет к ошибке.
Реализация функции упаковки потока байтов в единицу реализована как шаблон:
/// Pack bytes into value
template packInto(T)
{
T packInto(ubyte[] data)
{
static if (is(T == ubyte))
{
return data[0];
}
else static if (is(T == ushort))
{
if (data.length < 2)
{
return ushort(data[0]);
}
else
{
return (data[0] << 8) | ushort(data[1]);
}
}
else static if ((is(T == uint)) || (is(T == ulong)))
{
T result = 0;
foreach (bytes; data)
{
result = (result << 8) | T(bytes);
}
return result;
}
else
{
static assert(false, "Unsupported type");
}
}
}После этого реализацию первой функции xd (той, которая является универсальной) можно сделать следующим образом:
/// xd - Dump file contents in multiple formats
auto xd(Range)(Range range, XDFORMAT xfmt, STYLE ofmt = STYLE.DECIMAL, bool markRepeatedChunks = false)
{
// xd chunk size (in bytes)
enum XD_CHUNK_SIZE = 16;
// Size of units
auto unitSize = EnumValue(xfmt.width).to!size_t;
// Unit type
auto unitStyle = xfmt.style;
// Base format
string chunkFormat;
// Calculate chunk format
if ((unitStyle == "o") || (unitStyle == "d"))
{
// Oct and Dec dump format
chunkFormat = "%0" ~ format("%d%s ", 3 * unitSize, EnumValue(unitStyle));
}
else
{
// Hex dump format
chunkFormat = "%0" ~ format("%d%s ", unitSize << 1, EnumValue(unitStyle));
}
// Calculate offset format
string offsetFormat = "%016" ~ EnumValue(ofmt) ~ " ";
// Buffer for repeated blocks and its repeatedCounter
ubyte[] repeatedChunk;
ulong repeatedCounter = 0;
// Split byte stream to 16-bytes chunks
foreach (offset, chunk; range.chunks(XD_CHUNK_SIZE).enumerate)
{
// If setted - mark repeated chunk with asterisc
if (markRepeatedChunks)
{
if (chunk == repeatedChunk)
{
repeatedCounter++;
}
else
{
repeatedCounter = 0;
repeatedChunk = chunk.dup;
}
}
// Write offset
writef(offsetFormat, offset);
if (repeatedCounter > 0)
{
write("*");
}
else
{
foreach (unit; chunk.chunks(unitSize))
{
// Set-up byte order
final switch (xfmt.order) with (ORDER)
{
case LITTLE:
break;
case BIG:
unit = unit.retro.array;
break;
}
final switch (xfmt.width) with (WIDTH)
{
case BYTE:
// Special case for ASCII
if (xfmt.isASCII)
{
auto c = char(unit[0]);
// If not printable symbol replace it with dot
if ((c < 0x20) || (c > 0x7E))
{
writef(".");
}
else
{
writef("%c", c);
}
}
else
{
writef(chunkFormat, unit[0]);
}
break;
case WORD:
writef(chunkFormat, packInto!ushort(unit));
break;
case DWORD:
writef(chunkFormat, packInto!uint(unit));
break;
case QWORD:
writef(chunkFormat, packInto!ulong(unit));
break;
}
}
}
writeln;
}
}Сначала внутри функции мы определяем константу XD_CHUNK_SIZE, которая определяет размер куска файла и которая всегда равна 16, так как оригинальная утилита считывает файл кусками по 16 байт. Далее, определяем размер единицы в байтах (нужен будет для последующих вычислений) и формат вывода самой единицы, а также вводим переменную для формирования строки формата для отдельного куска. Если выбранный формат является десятичным или восьмеричным, то для того, чтобы полностью вывести все цифры для выбранной единицы (в зависимости от ее размера) нужно 3 цифры на каждый байт. Для шестнадцатеричного формата нужно меньше цифр на байт, а именно — 2. Поэтому сначала определяем сколько знаков необходимо для представления единицы в зависмости от формата и формируем строку формата, исходя из того какой он, и прописываем ее в переменную chunkFormat, предварительно вставив в нее символы «%0». Это делается для того, чтобы сформировать корректную строку для функций writef/writefln, которая выглядит примерно так: «%0%d%s», где на место %dвстает рассчитанное количество цифр на байт, а на место %s — определенный ранее из перечисления формат.
Далее формируем формат для вывода смещения куска относительно начала файла: тут мы также отступили от каноничной версии, так как не смогли определить как оригинальная xd определяет количество знаков в адресе. И поэтому мы определили сколько надо цифр для представления любого возможного смещения/адреса (их 16) и выставили такой формат для всех типов формата. Также в конце строки адреса был добавлен пробел, так как после этого будут идти отформатированные куски файлов.
Подготовка задает начало для основного цикла, в котором и делается основная работа. В нем идет разбиение байтового потока на 16-байтные куски и нумерация их по порядку через enumerate.
Далее, внутри цикла, если установлен соответствующий флаг учета повторяющих кусков, то проверяется есть ли текущий кусок в буфере, отведенном под хранение соответствующих попадающихся кусков, и если текущий фрагмент есть в буфере, то счетчик увеличивается; если нет — то кусок добавляется в буфер. После этого выводится адрес куска, а затем происходит проверка счетчика повторов и если есть повтор куска (согласно описанной ранее логике), то вместо самого куска выводится знак «*». И для повторяющихся кусков не надо определять формат, так как они выводится в виде этих символов, согласно описанию оригинальной xd.
Если же, кусок не повторяется и счетчик повторений на нуле, то тогда в работу вступает новый цикл, который выполняет разбиение полученного куска на единицы уже вычисленного размера. Цикл обрабатывает сами единицы, для которых выполняется определение порядка байтов (исходя из формата) и определение того, что именно за единица должна быть сформирована. Делается это на основании перечисления WIDTH и функции packInto, которая байтовый поток трансформирует в числовое значение соответствующего типа. А затем происходит печать в соответствующем формате, для которого также определен один особый случай: когда в качестве единицы используется байт, а в качестве формата вывод ASCII. Здесь мы отступили от каноничной версии и сделали так: печатные символы из таблицы ASCII (а это те, что попали в диапазон от 0x20 до 0x7e, спасибо примерам с сайта dlang.org) отображаются как символы таблицы, а непечатные символы отображаются в виде символов «.».
Таким образом, мы рассмотрели основные принципы работы алгоритма xd и реализовали одну из его базовых функций, которая в дальнейшем будет использоваться в качестве основного строительного блока для второй функции xd. На этом рассмотрение xd заканчивается, а во второй части статьи мы погрузимся в более глубокие детали и рассмотрим пример реализации основной функции утилиты xd с обработкой аргументов командной строки.
На этом все, оставайтесь с нами!