Кодируем файл в UUE

В одной из статей по Icon, я уже показывал как написать такую программу, которая превращает исходный файл (формат файла значения не имеет) в код UUE, использовавшийся в некогда популярной сети Фидонет, однако, я не объяснял деталей того, как именно функционирует данная программа. Более того, мне любопытно взглянуть иногда назад, чтобы посмотреть, как далеко я ушел в своих изысканиях, а алгоритм положенный в утилиту на Icon кажется мне несколько непрактичным и слишком наивным.

Именно по этой причине, я решился взяться за старое, но с новыми инструментами.

Формат UUE довольно прост и интересен, хотя сейчас его нигде и не встретишь. Суть в том, что из некоторого файла берутся данные по три байта (если в конце файла остается меньше трех байт, то добавляются нулевые байты), а затем полученный блок трехбайтных данных разбивается на четыре группы по 6 бит в каждой. Эти шестибитные группы используются далее в алгоритме кодирования, который к каждой группе прибавляет число 32. Дело в том, что обычный файл, при открытии в любом простом текстовом редакторе, отображается в виде символов, большая часть из которых представляет собой символы, которые не видны при печати. Прибавление 32 к каждой группе позволяет это исправить, создавая таким образом группу из четырех печатных символов ASCII, и следовательно дает возможность передать файл в виде обычного текста.

Схема кодирования (для строки Cat) выглядит следующим образом:

Помимо этого, 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;
}

Как видите, иногда бывает полезно вспомнить былое, и безусловно мне очень жаль, что я уже не в Фидо…