Привет!
Многие используют Base64 кодирование, реже Base32 и еще реже ZBase32 (вы знаете о таком?), но не все понимают их алгоритмы. В статье я описываю достоинства, недостатки данных кодировок, а также рассказываю о их реализации.
Не так давно у меня возникла необходимость использовать кодированные данные в адресе http-ссылки. Как известно, стандарт http подразумевает регистронезависимые url-адреса и любой прокси-сервер или браузер мог испортить данные в случае использования регистрочувствительного кодирования.
Учитывая указанные требования в качестве алгоритма было выбрано ZBase32-кодирование.
Как оказалось, стандартной реализации в .net нет (в отличие от base64), поэтому пришлось писать самому. К своему удивлению, я столкнулся с трудностями при поиске внятного объяснения Base32 и ZBase32. Были найдены какие-то готовые решения, но я не мог, не разобравшись в алгоритме применять их, а читать магию больших формул, битовых сдвигов было тяжело без словесного описания. Теперь, когда для меня все позади, я хотел бы поделиться с вами небольшим знанием элементарного кодирования. Статья носит академический характер.
Плюсы и минусы
Base64
Позволяет кодировать информацию, представленную набором байт, используя всего 62 символа: A-Z, a-z, 0-9. В конце кодированной последовательности может содержаться несколько спецсимволов (обычно “=”).
Преимущества:
- Позволяет представить последовательность любых байт в печатных символах.
- В сравнении с другими Base-кодировками дает результат, который составляет только 130% от длины исходных данных.
Недостатки:
- Регистрозависимая кодировка.
Base32
Использует только 32 символа: A-Z (или a-z), 2-7. Может содержать в конце кодированной последовательности несколько спецсимволов (по аналогии с base64).
Преимущества:
- Последовательность любых байт переводит в печатные символы.
- Регистронезависимая кодировка.
- Не используются цифры, слишком похожие на буквы (например, 0 похож на О, 1 на l).
Недостатки:
- Размер исходных данных увеличивается на 160%.
ZBase32
Кодировка аналогична Base32, но имеет следующие отличия.
- Человеко-ориентированный алфавит из 32 символов. Наиболее проработанная таблица символов для облегчения написания, произношения и запоминания кодированной информации. Авторы переставили наиболее удобные для человека символы на позиции, которые используются чаще всего. Как они это сделали я не знаю. Алфавит приводится ниже.
- Нет специальных символов в конце результата кодирования.
Подробнее про каждую из кодировок можно почитать в Википедии здесь и здесь, а сейчас я хотел бы остановиться непосредственно на реализации ZBase32.
Описание алгоритма ZBase32 кодирования
Позволю себе при описании алгоритма показывать выкладки на C# для большего понимания.
Итак, имеем 32-х символьный алфавит следующего содержания:
static string EncodingTable = "ybndrfg8ejkmcpqxot1uwisza345h769";
На входе массив байтов (естественно, по 8 бит каждый), который хотелось бы перевести в символы из алфавита.
public static string Encode(byte[] data)
{
Алфавит представляет собой строку из 32-х элементов, а это означает, что каждый из его символов кодируется числом от 0 до 31 (индексы символов в строке). Как известно, любое число от 0 до 31 в бинарной системе счисления можно записать, используя 5 битов байта. Из этого следует, что если представить исходный набор байтов как единый массив битов и разбить его на кусочки по 5 битов (см. рисунок ниже), то мы получим набор координат символов из алфавита. Вот, собственно, и все.
Алгоритмы Base32 и Base64 аналогичны ZBase32, только разные алфавиты (по составу в случае с Base32, по составу и размеру в случае Base64) и размеру “отщипываемых” кусочков бит (6 бит для Base64).
Итак, я предлагаю перед тем, как начать разбиение исходных данных на кусочки по 5 бит, подготовить место куда будет записываться результат. Чтобы не задумываться об индексах в статических массивах, давайте использовать StringBuilder.
var encodedResult = new StringBuilder((int)Math.Ceiling(data.Length * 8.0 / 5.0));
При инициализации сразу задаем размер результирующей строки (чтобы не тратить время на расширение в процессе работы алгоритма).
Теперь осталось пробежать по исходному массиву байтов и разделить его на 5-и битовые кусочки. Для удобства я предлагаю работать с группой по 5 байт, так как это 40 бит — число, кратное длине “кусочков”. Но не забываем, что исходные данные никто для нас не подгонял, поэтому учитываем возможность недостачи.
for (var i = 0; i < data.Length; i += 5)
{
var byteCount = Math.Min(5, data.Length - i);
Так как мы работаем с группой из 5 байт, нам нужен буфер, где будет формироваться сплошной набор битов (всего 40 бит). Заведем переменную типа ulong (64 бита в нашем распоряжении) и поместим туда текущую партию байтов.
ulong buffer = 0;
for (var j = 0; j < byteCount; ++j)
{
buffer = (buffer << 8) | data[i + j];
}
И заключительный этап — это “отщипывание” из того, что получилось, кусочков по 5 бит и формирование результата.
var bitCount = byteCount * 8;
while (bitCount > 0)
{
var index = bitCount >= 5
? (int)(buffer >> (bitCount - 5)) & 0x1f
: (int)(buffer & (ulong)(0x1f >> (5 - bitCount))) << (5 - bitCount);
encodedResult.Append(EncodingTable[index]);
bitCount -= 5;
}
Возможно, в последнем примере кода с первого взгляда не все понятно, но если вы немного сосредоточитесь, то все станет на свои места.
Процесс декодирования происходит аналогично процессу кодирования, только в обратном направлении.
Вы можете посмотреть полную реализацию ZBase32Encoder.
Заключение
И, конечно, в заключение хочется сказать следующее.
4nq7bcgosuemmwcq4gy7ddbcrdeadwcn4napdysttuea6egosmembwfhrdemdwcm4n77bcby4n97bxsozzea9wcn4n67bcby4nhnbwf94n9pbq6oszemxwf74nanhegow8em9wfo4gy7bqgos8emhegos9emyegosmem5wfa4n6pbcgozzemtwfirr
Автор: Denxc
