Практически каждый разработчик так или иначе использует base64. Но каков механизм работы этого алгоритма? Я считаю, что самый простой способ по-настоящему понять, как работает этот алгоритм, — попытаться реализовать его. Этим и займёмся.
Сам алгоритм base64 определяется в RFC 4648. Идея предельно проста: любые входные данные можно представить как битовый поток. Биты разбиваются на байты и группируются по восемь. В base64 происходит то же самое, только биты группируются по 6. Потом с помощью специальной таблицы каждое значение преобразуется в символы a-z, A-Z, 0-9 и + /. Затем в качестве заполнения используется символ =. Но не будем забегать вперёд.
Начнём с определения интерфейса функции base64 для кодирования и написания первого теста. Только будем реализовывать base64 для строк, а не для байтовых потоков.
Вот как выглядит первый тест:
Здесь функция кодирования принимает &str и кодирует строку.
Разделение битов на группы по 6
Сначала перегруппируем байты так, чтобы в каждой группе оказалось по 6 битов. Начинаем с 3 символов ASII, так как они имеют 24 бита в utf-8 (кодировке Rust) и могут перегруппировать их в 4 символа base64. Итак, преобразуем эти символы в байты.
Для получения 4 символов base64 нужно применить битовые маски, удалив ненужную информацию, и переместить символы в правильное положение. Для первой 6-ти битовой группы удаляем 2 последних бита и перемещаем эти 2 бита вправо (на самом деле, достаточно просто переместить их вправо, но я не подумал об этом, когда писал код).
Вторая группа состоит из 2 последних битов первого символа ASII и первых 4 битов второго символа ASII. Удаляем первые 6 битов первого символа ASII и перемещаем их на 4 позиции влево. Затем удаляем последние 4 бита второго символа ASII, сдвигаем их на 4 позиции вправо и пропускаем их вместе через оператор OR.
Для третьей группы нужны последние 4 бита второго символа ASII и первые 2 бита третьего символа ASII. Здесь так же удаляем лишние биты и объединяем релевантную информацию.
Последние 6 битов третьего символа ASII будут последним символом base64. Вы уже знаете, как выглядит код для первых трёх символов base64, поэтому не будем расписывать его снова: он очень простой.
Base64: преобразование символов в строку
Теперь символы base64 нужно преобразовать в символы выводимой строки base64. Здесь BASE64_ALPHABET — это срез, кодирующий таблицу алфавита base64, которая была приведена в начале этой статьи.
Если вернуть base64_output, можно получить наш первый работающий тест. ?
Добавим второй тест, чтобы строка стала длиннее 3 символов.
Для этого надо пройтись по группам из 3 символов в строке и преобразовать их в base64.
После каждой итерации перемещаем указатель вперёд на длину кодируемых байтов, то есть 3.
Кодируем строки с 1 или 2 байтами
Мы рассмотрели кодировку строки, длина которой была кратна 3 байтам. А как кодировать 2 или даже 1 байт? Если бы мы заполняли недостающие символы нулями, декодер не мог бы узнать, отсутствовали эти последние байты или были заняты нулями 0. (Не забывайте, что base64 предназначен не только для строк, но и для любых байтовых потоков.)
Есть умное решение. Если мы кодируем лишь 2 байта, для всей битовой информации нам потребуются 3 символа base64. Добавляя в качестве заполнения символ =, мы даём понять декодеру, что закодированы именно 2 байта, а не 3. Добавим тест, иллюстрирующий всё это:
Таким образом, мы можем извлечь 3 символа base64 и добавить заполнение:
Та же логика применяется при кодировании 1 байта. Этот байт могут нести 2 символа base64, а строку base64 мы можем заполнить символами ==, тем самым сообщая декодеру, как правильно декодировать строку.
Заключение
Идея, заложенная в base64, предельно проста: разделение битовых потоков на группы из шести битов и кодирование значений с помощью таблицы символов. Её легко реализовать, и в ходе реализации можно многому научиться. Лично для меня base64 стал первым реализованным мной алгоритмом с задействованием всей его внутренней логики. Здесь также мне впервые довелось использовать побитовое маскирование.
В статье было реализовано только кодирование. За вами теперь реализация декодирования. Реализация, изложенная в статье, доступна также в репозитории на GitHub repo.
Весь код можно найти на GitHub: https://github.com/niklasbuechner/experiments/blob/bbdb3136293bb2833529a47edcc5d9fa2dc5d405/base64/src/encode.rs
Читайте также:
- 8 базовых алгоритмических задач на собеседованиях
- Алгоритмы машинного обучения простым языком. Часть 1
- Алгоритмы поиска, которые должен знать каждый специалист по обработке и анализу данных
Перевод статьи Niklas Büchner: Implementing Base64 in Rust
