IcaBlog

Алгоритм Base64 на Kotlin

 
  • Jul 03, 2020

Не так давно у меня была одна интересная задача на работе. Нужно было переводить массив байт в Base64 строку для отправки на сервер, но было одно НО - проект на Kotlin-Multiplatfrom. Это означает, что общий код нужно писать только на Kotlin. Делать expect нативных реализаций для Android и iOS - тупая идея, подумал я. И нашел реализацию алгоритма на Kotlin в каком то гисте, вроде. Все работало. Но была проблема - меня дико бесит, когда я не понимаю, почему что-то сделано так, а не иначе. Втупую скопировать кусок кода можно, при горящих сроках, но потом будь добр разберись, что за хуйню ты добавил в проект.

Про принцип работы в картинках можно посмотреть ТУТ Хорошие картинки, а вот реализация на JS убогая. Показываю нормальную ->

Итак, тот самый алгоритм.

Привожу полностью, далее разбираю по строчкам, иногда углубляясь.

const val BASE64_ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"
const val BASE64_MASK: Byte = 0x3f
const val BASE64_PAD = '='

private fun Int.toBase64(): Char = BASE64_ALPHABET[this]

fun encode(src: ByteArray): ByteArray {
    fun ByteArray.getOrZero(index: Int): Int = if (index >= size) 0 else get(index).toInt()

    val result = ArrayList<Byte>(4 * src.size / 3) 
    var index = 0
    while (index < src.size) {
        val chunk = (src.getOrZero(index) and 0xff shl 16) or 
                    (src.getOrZero(index + 1) and 0xff shl 8) or
                    (src.getOrZero(index + 2) and 0xff)

        val symbolsLeft = src.size - index
        val padSize = if (symbolsLeft >= 3) 0 else (3 - symbolsLeft) * 8 / 6
        index += 3

        for (i in 3 downTo padSize) {
            val char = (chunk shr (6 * i)) and BASE64_MASK.toInt()
            result.add(char.toBase64().toByte())
        }

        repeat(padSize) { result.add(BASE64_PAD.toByte()) }
    }

    return result.toByteArray()
}

fun encodeToString(src: ByteArray): String {
    val encoded = encode(src)
    return buildString(encoded.size) {
        encoded.forEach { append(it.toChar()) }
    }
}

Теперь подробнее.

Короче говоря, есть стандарт RFC 4648, для кодирования используется строка:

const val BASE64_ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

Нам нужно наши байты преобразовать в символы этой строки. Несостыковка в чем? Байты у нас от 0 до 255, а символов в строке всего 64 + BASE64_PAD, о нем позднее. Получается у нас есть 8 бит, а надо 6. Че делаем? Берем по 3 байта, и делим их поровну по 6. Получается из трех делаем 4.

Создаем список с начальным размером массива 4 * src.size / 3 . Почему, надеюсь, понятно.

val result = ArrayList<Byte>(4 * src.size / 3)

Собираем кусочки

Запускаем шарманку while, тут то и начинается самое интересное.

val chunk = (src.getOrZero(index) and 0xff shl 16) or
(src.getOrZero(index + 1) and 0xff shl 8) or
(src.getOrZero(index + 2) and 0xff)

Тут по порядку.

byteArray.getOrZero(index)

fun ByteArray.getOrZero(index: Int): Int = if (index >= size) 0 else get(index).toInt()

C if (index >= size), думаю, все ясно. А вот какого черта мы кастуем к int каждый байт get(index).toInt(), можно почитать Тык. Да, и в любом случае нам потом двигать биты на 16 позиций, что в byte, явно, не влизает.

shl

Left shift - побитовой здвиг на n позиций влево, тут мы первый кусок сдвигаем на 16 второй на 8, ну и первый оставляем вначале.

Например: у нас было 01101101, 11001100, и 00110011. Стало 110110100000000000000000, 1100110000000000 и 00110011

or

Побитовое “ИЛИ”.

  • 1 or 0 = 1
  • 1 or 1 = 1
  • 0 or 1 = 1
  • 0 or 0 = 0

После этой операции с числами из предидущего примера получается. 011011011100110000110011

0xff а это что за нахер?

Видите ли, byte в Java signed . Это значит, что значения он хранит от -128 до 127. В единица на седьмой позиции(мы же с нуля считаем) означет знак. Например число 11001111 это не 207, а -49. Если Java видит 1 на седьмой позиции, просто заполняет все лидирующие нули дохерлярдом идиниц в byte.toInt()

Тут нам помогут побитовые маски. А конкретно 0xff в союзе с and, побитовым “И”.

Побитовое “И”.

  • 1 and 0 = 0
  • 1 and 1 = 1
  • 0 and 1 = 0
  • 0 and 0 = 0

0xff соответствует значению 255 или 8 единиц 11111111 Когда мы применяем маску к такой херне: 11111111111111111111111111000100 На выходе получаем 00000000000000000000000001000100, то есть 1000100

Подытожим

  1. Берем байт, делаем из него Int
  2. C помощью маски удаляем лишние нули
  3. Двигаем биты с помощью shl
  4. Склеиваем через or

Считаем индексы, ничего интересного

val symbolsLeft = src.size - index
val padSize = if (symbolsLeft >= 3) 0 else (3 - symbolsLeft) * 8 / 6
index += 3

Режем на кусочки

for (i in 3 downTo padSize) {
    val char = (chunk shr (6 * i)) and BASE64_MASK.toInt()
    result.add(char.toBase64().toByte())
}

Тут немного деталей, конечно.

shr

Как shl, только наоборот. Двигает все враво, а то, что за бортом выкидывает.

BASE64_MASK 0x3f

0x3f соответствует значению из 63 или 6 единиц, используется как маска, чтобы отсеить все что больше.

Что происходит то?

Возьмём число из примера 011011 011100 110000 110011. [] - маска

  1. Двигаем на 18 -> [011011]
  2. Двигаем на 12 -> 011011[011100]
  3. Двигаем на 6 -> 011011011100[110000]
  4. Двигаем на 0 -> 011011011100110000[110011]

toBase64()

Далее получившееся значение просто берем по индексу из BASE64_ALPHABET

private fun Int.toBase64(): Char = BASE64_ALPHABET[this]

Вишенка на торте

Если в конце не удалось набрать трех, заполняем специальным символом для таких случаев.

repeat(padSize) { result.add(BASE64_PAD.toByte()) }
Search