В одной из статей по Icon, я уже показывал как написать такую программу, которая превращает исходный файл (формат файла значения не имеет) в код UUE, использовавшийся в некогда популярной сети Фидонет, однако, я не объяснял деталей того, как именно функционирует данная программа. Более того, мне любопытно взглянуть иногда назад, чтобы посмотреть, как далеко я ушел в своих изысканиях, а алгоритм положенный в утилиту на Icon кажется мне несколько непрактичным и слишком наивным.
Именно по этой причине, я решился взяться за старое, но с новыми инструментами.
Формат UUE довольно прост и интересен, хотя сейчас его нигде и не встретишь. Суть в том, что из некоторого файла берутся данные по три байта (если в конце файла остается меньше трех байт, то добавляются нулевые байты), а затем полученный блок трехбайтных данных разбивается на четыре группы по 6 бит в каждой. Эти шестибитные группы используются далее в алгоритме кодирования, который к каждой группе прибавляет число 32. Дело в том, что обычный файл, при открытии в любом простом текстовом редакторе, отображается в виде символов, большая часть из которых представляет собой символы, которые не видны при печати. Прибавление 32 к каждой группе позволяет это исправить, создавая таким образом группу из четырех печатных символов ASCII, и следовательно дает возможность передать файл в виде обычного текста.
Схема кодирования (для строки Cat) выглядит следующим образом:
Исходные символы | C | a | t | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
ASCII коды (десятич.) | 67 | 97 | 116 | |||||||||||||||||||||
ASCII (двоичн.) | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
Новые десятичные значения | 16 | 54 | 5 | 52 | ||||||||||||||||||||
+32 | 48 | 86 | 37 | 84 | ||||||||||||||||||||
Символы UUE | 0 | V | % | T |
Помимо этого, UUE имеет заголовок и окончание, которые представляют собой обычные текстовые маркеры. Начало UUE-файла представляет собой строку вида:
begin 644 <имя_файла>;
а окончание файла содержит обычный перевод строки и строку-маркер end.
Также единичная строка UUE (исключая конечно текстовые маркеры для заголовка и окончания) содержит в своем начале и индикатор длины в байтах, который состоит из одного символа, к которому также прибавлено число 32. Обычно, одна строка UUE содержит 60 символов, что соответствует 45 байтам и символу M, предваряющим такую строку, однако, последняя строка файла может быть короче 60 символов, и тогда ее длина в байтах будет соответствовать количеству символов в такой строке, деленному на 4 и умноженному на 3 ( а чтобы получить символ, надо к полученному результату прибавить 32 и перевести в char).
(Хм, при объяснении формата UUE не описывается формат последней строки с данными, но рассказанный выше факт легко вывести самостоятельно исходя из принципа устройства UUE: символы в строке — это количество четырехбитных групп, поэтому мы и делим на 4, чтобы узнать общее количество трехбайтных групп, а затем это количество умножаем на 3, чтобы узнать количество байтов в строке)
Из вышеописанного легко построить алгоритм работы программы по кодированию в UUE в функциональном стиле:
- Берем некий файл под преобразование и переводим его в массив беззнаковых байтов;
- В случае, если длина массива не делится на три без остатка, дополняем полученный массив нулевыми байтами до тех пор, пока его длина не станет кратна трем;
- Разрезаем массив на куски по три байта в каждом;
- Превращаем отдельно взятый кусок в символы UUE в строковом представлении;
- Склеиваем полученные группы по четыре символа UUE в одну очень большую строку;
- Полученную строку разрезаем на блоки по 60 символов в каждом (исключением из этого может быть последний блок — в нем может оказаться меньше 60 символов);
- К каждому куску в строковом представлении добавляем символ его размера, закодированный в UUE (как было описано выше);
- Склеиваем результат предыдущего шага в одну строку таким образом, что каждый из блоков по 60 символов оказался на новой строке;
- Добавляем заголовок и окончание формата UUE;
- Выводим в стандартный поток вывода
Код, который осуществляет вышеописанный алгоритм выглядит так:
module uue; import std.algorithm; import std.conv; import std.file; import std.path; import std.range; import std.stdio; import std.string; void main() { /// количество байтов в группе enum NUMBER_OF_UUE_BYTES = 3; /// количество символов UUE в строке enum UUE_SYMBOLS_PER_LINE = 60; immutable filename = `/home/aquareji/Pictures/Lenna_full.png`; (cast(ubyte[]) std.file.read(filename)) .appendNullBytes .chunks(NUMBER_OF_UUE_BYTES) .map!(a => a.array.toUUE) .joiner .chunks(UUE_SYMBOLS_PER_LINE) .map!(a => a.to!string.formatUUELine) .join("\n") .formatUUE(filename) .writeln; }
Осталось дело за малым, а именно, определить самим функции appendNullBytes, toUUE, formatUUELine, formatUUE.
Самое простое — это определить appendNullBytes, которая добавляет нулевые байты к массиву из беззнаковых байтов (байт без знака, потому что нам не нужны проблемы с весьма несложной арифметикой, да и хранить нам нужно в байтах лишь значения, попавшие в таблицу ASCII). Такая функция будет добавлять нули тогда и только тогда, когда длина массива не кратна трем, поскольку дальнейшая выборка будет производится кусками по три байта. Осуществить реализацию можно следующим, местами нетривиальным образом:
/// добавить нулевые байты если необходимо auto appendNullBytes(ubyte[] bytes) { immutable modulus = bytes.length % 3; if (modulus != 0) { auto diff = (3 - modulus); // количество нулевых байт необходимое для того, чтобы размер байтого массива был кратен 3 bytes ~= new ubyte[diff]; } return bytes; }
Обычно, дополнение какими-то элементами осуществляется циклом while, в котором указывается условие наращивания массива (в нашем случае, это условие звучит так «пока остаток от деления длины массива на три не равен нулю»), но я придумал кое-что поинтереснее…
Оказывается, можно практически сразу узнать сколько элементов нужно добавить в массив байтов, чтобы его длина оказалось кратна тройке: для этого нужно вычислить остаток от деления длины массива на три, а затем вычесть его из трех — полученное число и будет тем количеством элементов, которых так не хватает (к сожалению, я открыл это методом статистического эксперимента, и не имею строгого математического доказательства своей правоты, но я полагаю, что это возможно обобщить. Если вы, уважаемый читатель, знаете как доказать мое утверждение, то любезно прошу написать об этом мне или в нашу группу, буду очень признателен). Этот факт мы и используем, создавая нужное количество элементов без цикла и практически в один ход.
Функция toUUE представляет собой сердце алгоритма, поскольку именно она выполняет одну из самых элементарных операций в нем, а именно, превращает набор из трех байтов в группу из четырех символов UUE. Сама функция выглядит достаточно жестко, особенно для тех, кто пришел в D не из C/C++/Rust и подобных языков, близких к железу, вот ее код:
/// три байта превратить в UUE auto toUUE(ubyte[] bytes) { uint block = 0x0; // скомбинировать в один блок block |= bytes[2]; block |= (bytes[1] << 8); block |= (bytes[0] << 16); // разбиение на 4 шестибитные группы + добавление 32 к каждой из них string accumulator; accumulator ~= ((block & 0x00fc0000) >> 18) + 32; accumulator ~= ((block >> 0x0003f000) >> 12) + 32; accumulator ~= ((block & 0x00000fc0) >> 6) + 32; accumulator ~= (block & 0x003f) + 32; return accumulator; }
На самом деле тут все достаточно просто, особенно, если под рукой бумага и ручка для ручного прохода всех битовых операций. Сначала мы три байта с помощью операций сдвига влево и побитового ИЛИ, размещаем в обратном порядке, в единственном целочисленном значении uint. Сами числа в операциях сдвига, показывают, что идет размещение в пределах байта (для первого числа сдвиг не нужен, так как оно заняло последние 8 бит uint; далее происходит сдвиг следующего байта на 8 бит, поскольку последние 8 бит уже заняты байтом; а затем — сдвиг следующего на 16 бит, так как уже два байта размещены. Самые первые, т.е. левые 8 бит uint, нам не нужны и поэтому их мы не трогаем). Потом по тому же принципу происходит выделение шестибитных групп, но поскольку 6 не является степенью двойки, то тут потребуется применение битовых масок и побитового И, а также сдвигов вправо, т.к. необходимо вычленение небольшого числа из uint, которое как вы поняли, соответствует группе из 6 битов.
Также, я произвел комбинирование с операцией прибавления 32 и не стал использовать сторонний массив-аккумулятор для полученных чисел, а сразу решил накопить результаты битовых манипуляций в строку, воспользовавшись неявным приведением к символьному типу.
В общем, для осмысления работы кода, рекомендую проделать его вручную с бумагой и ручкой, и даже без компьютера.
Функция formatUUELine использует то, что я рассказал, как дополнительный факт про UUE, а именно то, как пересчитать количество символов в строке в количество в ней байтов исходного файла, и выполняя такой пересчет для готовой строки с UUE, добавляет к результату 32 и превращает в печатаемый символ типа char, соединяя с взятой строкой-аргументом:
/// форматирование UUE auto formatUUELine(const string uueLine) { return (cast(char) ((uueLine.length / 4) * 3 + 32)) ~ uueLine; }
Функция formatUUE создает уже готовый результат в его окончательном виде с точки зрения описанного формата UUE: используя format, данная функция размещает заголовок и подставляет в него имя файла (осуществляется с помощью выделения самого имени файла из его пути посредством baseName из std.path), результат кодирования и окончание:
/// добавление заголовка и окончания + имя файла auto formatUUE(const string uue, const string filepath) { return format( `begin 644 %s %s end`, baseName(filepath), uue ); }
Весьма мощно, не так ли?
А теперь проведем тестирование, для чего возьмем уже поднадоевший нам в обработке изображений файл Lenna и запустим нашу программу, переадресовав ее вывод в файл:
rdmd uue > test.uue
(Файл с результатом можно скачать здесь)
Проверим, а сработало ли преобразование в UUE, для чего воспользуемся онлайн-конвертером: в поле Input type выбираем File, затем нажимаем кнопку Browse, после нажатия которой, откроется диалоговое окно с выбором файла и в нем мы выбираем полученный файл test.uue. Нжимаем кнопку Decode, ждем когда файл загрузится и сконвертируется, после чего внизу под окном Decoded Input ищем маленькую зеленую надпись в квадратных скобках Download as a binary file и любуемся результатом декодирования:

Полный код примера:
module uue; import std.algorithm; import std.conv; import std.file; import std.path; import std.range; import std.stdio; import std.string; /// три байта превратить в UUE auto toUUE(ubyte[] bytes) { uint block = 0x0; // скомбинировать в один блок block |= bytes[2]; block |= (bytes[1] << 8); block |= (bytes[0] << 16); // разбиение на 4 шестибитные группы + добавление 32 к каждой из них string accumulator; accumulator ~= ((block & 0x00fc0000) >> 18) + 32; accumulator ~= ((block & 0x0003f000) >> 12) + 32; accumulator ~= ((block & 0x00000fc0) >> 6) + 32; accumulator ~= (block & 0x003f) + 32; return accumulator; } /// добавить нулевые байты если необходимо auto appendNullBytes(ubyte[] bytes) { immutable modulus = bytes.length % 3; if (modulus != 0) { auto diff = (3 - modulus); // количество нулевых байт необходимое для того, чтобы размер байтого массива был кратен 3 bytes ~= new ubyte[diff]; } return bytes; } /// форматирование UUE auto formatUUELine(const string uueLine) { return (cast(char) ((uueLine.length / 4) * 3 + 32)) ~ uueLine; } /// добавление заголовка и окончания + имя файла auto formatUUE(const string uue, const string filepath) { return format( `begin 644 %s %s end`, baseName(filepath), uue ); } void main() { /// количество байтов в группе enum NUMBER_OF_UUE_BYTES = 3; /// количество символов UUE в строке enum UUE_SYMBOLS_PER_LINE = 60; immutable filename = `/home/aquareji/Pictures/Lenna_full.png`; (cast(ubyte[]) std.file.read(filename)) .appendNullBytes .chunks(NUMBER_OF_UUE_BYTES) .map!(a => a.array.toUUE) .joiner .chunks(UUE_SYMBOLS_PER_LINE) .map!(a => a.to!string.formatUUELine) .join("\n") .formatUUE(filename) .writeln; }
Как видите, иногда бывает полезно вспомнить былое, и безусловно мне очень жаль, что я уже не в Фидо…