Алгоритмы Кодирования Zbase32, Base32 И Base64

Привет! Многие используют кодировку Base64, реже Base32 и еще реже.

ZBase32 (вы знаете об этом?), но не все понимают их алгоритмы.

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

Не так давно у меня возникла необходимость использовать закодированные данные в адресе http-ссылки.

Как вы знаете, стандарт http чувствителен к регистру.

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

Учитывая эти требования, в качестве алгоритма было выбрано кодирование ZBase32. Как оказалось, в .

net нет стандартной реализации (в отличие от base64), поэтому мне пришлось писать ее самому.

К моему удивлению, мне было трудно найти четкое объяснение Base32 и ZBase32. Были найдены какие-то готовые решения, но применить их без понимания алгоритма я не мог, а магию больших формул и битовых сдвигов без словесного описания прочитать было сложно.

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

Статья носит академический характер.

Преимущества и недостатки

База64

Позволяет кодировать информацию, представленную набором байтов, используя всего 64 символа: A-Z, a-z, 0-9, /, +.

Конец закодированной последовательности может содержать несколько специальных символов (обычно «=»).

Преимущества:

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

Недостатки:

Кодировка с учетом регистра.

База32

Использует только 32 символа: A-Z (или a-z), 2-7. Может содержать несколько специальных символов в конце закодированной последовательности (аналогично base64).

Преимущества:

Последовательность любых байтов преобразуется в печатные символы.
Кодировка без учета регистра.
Числа, слишком похожие на буквы, не используются (например, 0 похож на О, 1 похож на л).

Недостатки:

Закодированные данные составляют 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 бит для База64).

Алгоритмы кодирования ZBase32, Base32 и 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

Теги: #кодирование #base32 #zbase32 #base64 #программирование #.

NET #Алгоритмы