Base64 – принцип работы и собственная реализация

Base64 один из тех алгоритмов, которыми приходится пользоваться регулярно. И встречается он повсеместно и на backend и на frontend, но при этом мало кто задумывается как он работает изнутри. В данной статье я покажу, что из себя представляет данный алгоритм и как можно быстро его реализовать на языке C#, а также как можно оптимизировать полученное решение.

Начнём с теории. Base64 – это стандарт кодирования данных используя только 64 символа ASCII, отсюда и название. Используются символы A-Z, a-z и 0-9 и еще 2 символа различаются в зависимости от реализации, наиболее распространён вариант с символами + и /.

Таблица кодировок представляет из себя следующее:

Строка символов: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

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

Алгоритм работы

Изначально на вход поступает массив байт, каждый байт — это число от 0 до 255, то есть максимальное количество бит в числе равно восьми (255 в двоичной системе счисления это 11111111). Необходимо взять 3 байта, это 24 бита, которые разбивают на 4 части – по 6 бит. Число из 6 бит (в десятичной системе) и будет представлять из себя очередной индекс в таблице для получения символа кодирования (6 бит – в двоичном виде 111111, в десятичном виде это число 63). Если размер исходного массива не кратен 3, тогда итоговую строку следует дополнить символом = до размера кратного 3.

В качестве примера, продемонстрирую как происходит кодирование строки "demo". Для начала, необходимо получить массив байт, это будет 4 десятичных числа 100, 101, 109, 111. В двоичном виде это значения 1100100, 1100101, 1101101, 1101111.

Дополним количество бит в числах до 8, и разобьём на группы по 6 бит. Получим значения 011001, 000110, 010101, 101101, 011011, 110000. Переведём в десятичную систему счисления, получим числа 25, 6, 21, 45, 27, 48. Взяв символы из таблицы Base64 символов по данным индексам, получим строку ZGVtbw. Во входящем массиве байт было 4 числа. Четыре не кратно трём, остаток от деления на три будет 1. Если остаток 1, то нужно дополнить двумя символами =, если остаток будет 2, то дополнить одним символом =. В данном случае дополнив имеющуюся строку ==.

Дополнив строку, получаем результат ZGVtbw==. Это и есть Base64 строка, полученная из строки "demo".

Наглядно процесс кодирования можно увидеть ниже:

Декодирование информации из Base64 строки представляет из себя обратный процесс. Нам необходимо разбить строку по 4 символа, получить их значения из таблицы символов Base64, затем полученную группу из 24 бит необходимо разбить на 3 части – получится 3 значения по 8 бит, которые мы помещаем в массив байт. Повторять данный процесс необходимо до конца имеющейся строки. Символ = не будет участвовать в процессе, он будет только показывать, какое количество бит необходимо взять из конца строки.

Демонстрацию процесса декодирования можно увидеть ниже:

Реализация кодирования

Описанный алгоритм очень легко реализуется средствами C#.

Ниже приведён пример реализации без всякой оптимизации. Алгоритм будет выдавать корректное решение, но будет работать неприемлемо долго:

static readonly char[] base64Table = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
													   'P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d',
													   'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s',
													   't','u','v','w','x','y','z','0','1','2','3','4','5','6','7',
													   '8','9','+','/','=' };

public string ToBase64Custom (byte[] data)
{
	var arrayOfBinaryStrings = data.Select(x => Convert.ToString(x, 2).PadLeft(8, '0'));
	var count = arrayOfBinaryStrings.Count();
	var append = count % 3 == 1 ? "==" : count % 3 == 2 ? "=" : "";

	var allBytes = string.Join("", arrayOfBinaryStrings);
	var countOfBytes = allBytes.Count();
	var remOfDivision = countOfBytes % 6;
	var newList = Enumerable.Range(0, countOfBytes / 6).Select(x => allBytes.Substring(x * 6, 6)).ToList();

	if (remOfDivision != 0)
	{
		newList.Add(allBytes.Substring(countOfBytes / 6 * 6, remOfDivision).PadRight(6, '0'));
	}

	return (string.Join("", newList.Select(x => base64Table[Convert.ToByte(x, 2)])) + append);
}

Делается здесь следующее:

var arrayOfBinaryStrings = data.Select(x => Convert.ToString(x, 2).PadLeft(8, '0'));

Каждое число из массива data преобразуется в двоичный вид, так же слева добавляются нули, чтобы сделать каждую строку размером 8 символов.

var append = count % 3 == 1 ? "==" : count % 3 == 2 ? "=" : "";

Определяется, нужно ли добавлять символ = в конце строки, если да, то сколько раз.

var allBytes = string.Join("", arrayOfBinaryStrings);

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

var newList = Enumerable.Range(0, countOfBytes / 6).Select(x => allBytes.Substring(x * 6, 6)).ToList();

Строку с битами разделяю на группы по 6 символов – это будут числа для получения Base64 символов.

if (remOfDivision != 0)
{
	newList.Add(allBytes.Substring(countOfBytes / 6 * 6, remOfDivision).PadRight(6, '0'));
}

Если имелся остаток от деления на 6, то эта строка добавляется отдельно, дополнив строку нулями до размера 6 символов.

return (string.Join("", newList.Select(x => base64Table[Convert.ToByte(x, 2)])) + append);

Здесь уже идёт преобразование полученных чисел в Base64 символы и объединение в результирующую строку.

Преимущество подобной реализации в простоте, возможности LINQ позволяют быстро писать хорошо читаемый код. За 5-10 минут вы можете продемонстрировать работу алгоритма. Но ни в коем случае не используйте подобное в реальных проектах!

 Чтобы лучше понимать насколько медленно будет работать подобная реализация, я протестировал скорость работы используя BenchmarkDotNet. В качестве входных данных поступала строка размером 5MB. В качестве аналога использовался вызов Convert.ToBase64String Вот какой результат был получен:

Полученный алгоритм работает приблизительно в 215 раз медленнее. Чтобы это исправить, необходимо избавится от LINQ, лишних вызовов и использовать битовые операции. После оптимизации алгоритм стал выглядеть следующим образом:

internal static readonly char[] base64Table = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O',
                                                       'P','Q','R','S','T','U','V','W','X','Y','Z','a','b','c','d',
                                                       'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s',
                                                       't','u','v','w','x','y','z','0','1','2','3','4','5','6','7',
                                                       '8','9','+','/','=' };
public unsafe string ToBase64Custom(byte[] data)
{
    var appendSize = data.Length % 3 == 2 ? 1 : data.Length % 3 == 1 ? 2 : 0;

    var length = (data.Length * 8 + (appendSize * 2)) / 6 + appendSize;

    var result = new string('=', length);

    var clearLenth = (data.Length / 3) * 3;

    var nextValue = 0;

    fixed (char* point = result)
    {
        char* c = point;

        for (int i = 0; i < clearLenth; i += 3)
        {
            fixed (byte* next = &data[i])
            {
                nextValue = *next >> 2;
                *(c++) = base64Table[nextValue];
                nextValue = (*next & 0b00000011) << 4;


                nextValue |= *(next + 1) >> 4;
                *(c++) = base64Table[nextValue];
                nextValue = (*(next + 1) & 0b00001111) << 2;


                nextValue |= (*(next + 2) & 0b11000000) >> 6;
                *(c++) = base64Table[nextValue];

                nextValue = *(next + 2) & 0b00111111;
                *(c++) = base64Table[nextValue];
                nextValue = 0;

            }
        }
        if (appendSize != 0)
        {
            fixed (byte* next = &data[clearLenth])
            {
                nextValue = *next >> 2;
                *(c++) = base64Table[nextValue];
                nextValue = (*next & 0b00000011) << 4;

                if (appendSize == 1)
                {
                    nextValue |= *(next + 1) >> 4;
                    *(c++) = base64Table[nextValue];
                    nextValue = (*(next + 1) & 0b00001111) << 2;
                }
            }
        }

        *c = base64Table[nextValue];
    }

    return result;
}

Читаемость алгоритма, конечно, значительно снизилась, но зато скорость работы стала приемлемой. Вот данные работы бенчмарка:

Оригинальный алгоритм имеет преимущество только в том, что для выделения памяти под строку используется метод string.FastAllocateString, который я могу вызвать, только если воспользовавшись рефлексией, как, например здесь:

var fastAllocate =
                typeof(string).GetMethods(BindingFlags.NonPublic | BindingFlags.Static)
                  .First(x => x.Name == "FastAllocateString");

var result = (string)fastAllocate.Invoke(null, new object[] { length });

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

То, что в реализации Convert.ToBase64String используется именно FastAllocateString я посмотрел через ILSpy, пытаясь понять, чем именно была вызвана разница в скорости работы алгоритма:

Реализация декодирования

Декодирование реализуется гораздо проще. При использовании LINQ без необходимости оптимизаций скорости алгоритм на C# может представлять из себя следующее:

Dictionary<char, int> base64DIctionary = new Dictionary<char, int>()
{
	{'A', 0 },{'B', 1 },{'C', 2 },{'D', 3 },{'E', 4 },{'F', 5 },{'G', 6 },{'H', 7 },{'I', 8 },{'J', 9 },{'K', 10 },{'L', 11 },{'M', 12 },{'N', 13 },{'O', 14 },{'P', 15 },{'Q', 16 },{'R', 17 },{'S', 18 },{'T', 19 },{'U', 20 },{'V', 21 },{'W', 22 },{'X', 23 },{'Y', 24 },{'Z', 25 },{'a', 26 },{'b', 27 },{'c', 28 },{'d', 29 },{'e', 30 },{'f', 31 },{'g', 32 },{'h', 33 },{'i', 34 },{'j', 35 },{'k', 36 },{'l', 37 },{'m', 38 },{'n', 39 },{'o', 40 },{'p', 41 },{'q', 42 },{'r', 43 },{'s', 44 },{'t', 45 },{'u', 46 },{'v', 47 },{'w', 48 },{'x', 49 },{'y', 50 },{'z', 51 },{'0', 52 },{'1', 53 },{'2', 54 },{'3', 55 },{'4', 56 },{'5', 57 },{'6', 58 },{'7', 59 },{'8', 60 },{'9', 61 },{'+', 62 },{'/', 63 },{'=', -1 }
};

public byte[] FromBase64Custom(string str)
{
	var allBytes = string.Join("", str.Where(x => x != '=').Select(x => Convert.ToString(base64DIctionary[x], 2).PadLeft(6, '0')));

	var countOfBytes = allBytes.Count();

	return Enumerable.Range(0, countOfBytes / 8).Select(x => allBytes.Substring(x * 8, 8)).Select(x => Convert.ToByte(x, 2)).ToArray();
}

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

Вот что показало тестирование скорости работы в BenchmarkDotNet при сравнении с реализацией в Convert.FromBase64String:

Разница в скорости работы примерно в 60 раз.

Если же опять отказаться от LINQ, добавить работу с битами и убрать лишние вызовы, получится что-то похожее:

public unsafe byte[] FromBase64Custom(string str)
{
    var length = str.Length;
    var countOfEquals = str.EndsWith("==") ? 2 : str.EndsWith("=") ? 1 : 0;
    var arraySize = (length - countOfEquals) * 6 / 8;

    var result = new byte[arraySize];
    var loopLength = (length / 4) * 4;

    var arrayPosition = 0;
    var stringPosition = 0;
    fixed (char* c = str)
    {
        fixed (byte* element = result)
        {
            for (int i = 0; i < loopLength; i += 4)
            {

                var next = base64DIctionary[*(c + stringPosition++)];
                var buf = base64DIctionary[*(c + stringPosition++)];
                next = next << 2;
                next |= (buf >> 4);
                *(element + arrayPosition++) = (byte)next;

                next = (buf & 0b001111) << 4;
                buf = base64DIctionary[*(c + stringPosition++)];
                next |= (buf >> 2);
                *(element + arrayPosition++) = (byte)next;


                next = (buf & 0b000011) << 6;
                buf = base64DIctionary[*(c + stringPosition++)];
                next |= buf;
                *(element + arrayPosition++) = (byte)next;
            }
            if (countOfEquals != 0)
            {
                var cur = loopLength;

                if (stringPosition < str.Length)
                {
                    var next = base64DIctionary[*(c + stringPosition++)] << 2;

                    var buf = base64DIctionary[*(c + stringPosition++)];
                    next |= buf >> 4;
                    *(element + arrayPosition++) = (byte)next;
                    if (countOfEquals == 1)
                    {
                        next = (buf & 0b001111) << 4;
                        buf = base64DIctionary[*(c + stringPosition++)];
                        next |= (buf >> 2);
                        *(element + arrayPosition) = (byte)next;
                    }
                    if (countOfEquals == 2)
                    {
                        next = (buf & 0b001111) << 4;
                        buf = base64DIctionary[*(c + stringPosition++)];
                        next |= (buf >> 2);
                        *(element + arrayPosition) = (byte)next;
                    }
                }
            }
        }
    }
    return result;
}

Данная реализация так же не является оптимальной, но уже гораздо ближе к ней. Ниже приведены результаты работы бенчмарка:

Отставание скорости в 2.5 раза. Здесь я не буду оптимизировать все возможные моменты. Если вы хотите – делитесь своими реализации или оптимизациями в комментариях. Если будет что-то действительно интересное – с меня подарок.

На реальных проектах, используя .NET технологии для разработки, маловероятно, что вам необходимо будет собственная реализация алгоритма Base64. Но понимание того, как он работает, несомненно является большим плюсом, так как идеи, которые используются для реализации могут быть применены в схожих задачах. Например, именно для ваших целей, может быть эффективен некий аналог с названием Base512 (использующий таблицу доступных символов гораздо большего размера, либо меньшего), либо вам нужно будет использовать другую таблицу символов. Со знанием того, как устроен Base64 реализовать подобное не составит труда. Также стоит иметь ввиду, что многие вещи можно реализовать в C# очень быстро, но всегда нужно думать о производительности ваших алгоритмов, чтобы они не стали "бутылочным горлышком" для ваших приложений. LINQ очень приятно использовать, но за использование данной технологии приходится платить скоростью исполнения самих приложений, и в местах, где критична производительности, следует отказаться от их использования, заменив чем-то более эффективным.

А на этом всё.

Приятного программирования.

Добавить комментарий