ZBase32, Base32 и Base64 алгоритмы кодирования

в 12:51, , рубрики: base64, Алгоритмы, кодирование, Программирование, метки: ,

Привет!

Многие используют 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).

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

Автор: Denxc

Источник

Поделиться

* - обязательные к заполнению поля