Расчет длины Base64?


после прочтения base64 wiki ...

Я пытаюсь понять как формула работает :

задана строка длиной n, длина base64 будет

что : 4*Math.Ceiling(((double)s.Length/3)))

Я уже знаю, что длина base64 должна быть %4==0 чтобы декодер знал, какова была исходная длина текста.

максимальное количество отступов для последовательности может быть = или ==.

wiki: количество выходных байтов на входной байт составляет примерно 4/3 (33% накладные расходы)

вопрос:

как соответствует ли приведенная выше информация выходной длине ?

11 108

11 ответов:

каждый символ используется для представления 6 бит (log2(64) = 6).

поэтому 4 символа используются для представления 4 * 6 = 24 bits = 3 bytes.

вам нужно 4*(n/3) символы для представления n байт, и это должно быть округлено до кратного 4.

количество неиспользуемых символов заполнения в результате округления до кратного 4, очевидно, будет 0, 1, 2 или 3.

4 * n / 3 дает неупакованную длину.

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

((4 * n / 3) + 3) & ~3

для справки, формула длины кодировщика Base64 выглядит следующим образом:

Base64 encoder's length formula

как вы сказали, кодировщик Base64 задан n байты данных создадут строку 4n/3 Base64 символов. Другими словами, каждые 3 байта данных приведут к 4 символам Base64. EDIT:комментарий правильно указывает, что моя предыдущая графика не учитывала заполнение; правильная формула Ceiling(4n/3).

в статье Википедии показано, как именно строка ASCII Man кодируется в строку Base64 TWFu в своем примере. Входная строка имеет размер 3 байта, или 24 бита, поэтому формула правильно предсказывает, что выход будет иметь длину 4 байта (или 32 бита):TWFu. Процесс кодирует каждые 6 бит данных в один из 64 символов Base64, поэтому 24-битный вход, разделенный на 6, приводит к 4 символам Base64.

вы спрашиваете в комментарии какой размер кодировки 123456 будет. Имея в виду, что каждый символ этой строки имеет размер 1 байт или 8 бит (предполагая кодировку ASCII/UTF8), мы кодируем 6 байт или 48 бит данных. Согласно уравнению, мы ожидаем, что выходная длина будет (6 bytes / 3 bytes) * 4 characters = 8 characters.

положить 123456 в кодировщик Base64 создает MTIzNDU2, что составляет 8 символов, как мы и ожидали.

Я думаю, что данные ответы упускают точку исходного вопроса, которая заключается в том, сколько места нужно выделить, чтобы соответствовать кодировке base64 для данной двоичной строки длиной n байт.

ответ (floor(n / 3) + 1) * 4 + 1

Это включает в себя заполнение и завершающий символ null. Вам может не понадобиться вызов пола, если вы делаете целочисленную арифметику.

включая заполнение, строка base64 требует четыре байта для каждого трехбайтового фрагмента оригинала строка, включая любые частичные куски. Один или два дополнительных байта в конце строки все равно будут преобразованы в четыре байта в строке base64 при добавлении дополнения. Если у вас нет очень конкретного использования, лучше всего добавить дополнение, обычно равный символ. Я добавил дополнительный байт для нулевого символа в C, потому что строки ASCII без этого немного опасны, и вам нужно будет нести длину строки отдельно.

целые числа

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

для этого неплохо вспомнить, как выполнить потолочное деление:ceil(x / y) в двойниках можно писать как (x + y - 1) / y (избегая отрицательных чисел, но остерегайтесь переполнения).

читабельный

если вы идете на читаемость вы можете, конечно, также запрограммировать его так (например, в Java, в C, вы могли бы использовать макрос, конечно):

public static int ceilDiv(int x, int y) {
    return (x + y - 1) / y;
}

public static int paddedBase64(int n) {
    int blocks = ceilDiv(n, 3);
    return blocks * 4;
}

public static int unpaddedBase64(int n) {
    int bits = 8 * n;
    return ceilDiv(bits, 6);
}

// test only
public static void main(String[] args) {
    for (int n = 0; n < 21; n++) {
        System.out.println("Base 64 padded: " + paddedBase64(n));
        System.out.println("Base 64 unpadded: " + unpaddedBase64(n));
    }
}

встроенный

мягкий

мы знаем, что нам нужно 4 блока символов в то время для каждого 3 байта (или меньше). Итак, тогда формула становится (для x = n и y = 3):

blocks = (bytes + 3 - 1) / 3
chars = blocks * 4

или в сочетании:

chars = ((bytes + 3 - 1) / 3) * 4

ваш компилятор будет оптимизировать в 3 - 1, так что просто оставьте его так, чтобы поддерживать удобочитаемость.

Unpadded

менее распространен неупакованный вариант, для этого мы помним, что каждый нам нужен символ для каждого 6 бит, округленный:

bits = bytes * 8
chars = (bits + 6 - 1) / 6

или в сочетании:

chars = (bytes * 8 + 6 - 1) / 6

однако мы все еще можем разделить на два (если захотим):

chars = (bytes * 4 + 3 - 1) / 3

нечитаемый

в случае, если вы не доверяете своему компилятору, чтобы сделать окончательные оптимизации для вас (или если вы хотите, чтобы запутать ваш коллеги):

мягкий

((n + 2) / 3) << 2

Unpadded

((n << 2) | 2) / 3

Итак, мы имеем два логических способа вычисления, и нам не нужны никакие ветви, битовые операции или модульные операции-если мы действительно этого не хотим.

Примечания:

  • очевидно, вам может потребоваться добавить 1 к вычислениям, чтобы включить байт завершения null.
  • для Mime вам может понадобиться позаботиться о возможной линии символы завершения и такие (ищите другие ответы для этого).

вот функция для вычисления исходного размера закодированного файла Base 64 в виде строки в КБ:

private Double calcBase64SizeInKBytes(String base64String) {
    Double result = -1.0;
    if(StringUtils.isNotEmpty(base64String)) {
        Integer padding = 0;
        if(base64String.endsWith("==")) {
            padding = 2;
        }
        else {
            if (base64String.endsWith("=")) padding = 1;
        }
        result = (Math.ceil(base64String.length() / 4) * 3 ) - padding;
    }
    return result / 1000;
}

Мне кажется, что правильная формула должна быть:

n64 = 4 * (n / 3) + (n % 3 != 0 ? 4 : 0)

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

$ echo "Including padding, a base64 string requires four bytes for every three-byte chunk of the original string, including any partial chunks. One or two bytes extra at the end of the string will still get converted to four bytes in the base64 string when padding is added. Unless you have a very specific use, it is best to add the padding, usually an equals character. I added an extra byte for a null character in C, because ASCII strings without this are a little dangerous and you'd need to carry the string length separately."| wc -c

525

$ echo "Including padding, a base64 string requires four bytes for every three-byte chunk of the original string, including any partial chunks. One or two bytes extra at the end of the string will still get converted to four bytes in the base64 string when padding is added. Unless you have a very specific use, it is best to add the padding, usually an equals character. I added an extra byte for a null character in C, because ASCII strings without this are a little dangerous and you'd need to carry the string length separately." | base64 | wc -c

710

таким образом, кажется, что формула из 3 байтов, представленных 4 символами base64, кажется правильной.

в windows-я хотел оценить размер буфера размера mime64, но все точные формулы расчета не работали для меня-наконец, я получил приблизительную формулу:

размер выделения строки Mine64 (приблизительный) = (((4 * ((размер двоичного буфера) + 1)) / 3) + 1)

Итак, последний +1-он используется для ascii-ноль-последний символ должен выделяться для хранения нулевого окончания - но почему "размер двоичного буфера" равен + 1 - я подозреваю, что есть некоторый mime64 характер прекращения ? Или может быть это какая-то проблема выравнивания.

простая реализация в javascript

function sizeOfBase64String(base64String) {
    if (!base64String) return 0;
    const padding = (base64String.match(/(=*)$/) || [])[1].length;
    return 4 * Math.ceil((base64String.length / 3)) - padding;
}

Я считаю, что это один точный ответ, если n%3 не ноль, нет ?

    (n + 3-n%3)
4 * ---------
       3

версия Mathematica:

SizeB64[n_] := If[Mod[n, 3] == 0, 4 n/3, 4 (n + 3 - Mod[n, 3])/3]

удачи

ги