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

После прочтения вики base64 ...

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

Учитывая строку с длиной n, длина base64 будет

Который : 4*Math.Ceiling(((double)s.Length/3)))

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

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

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

Вопрос:

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

Каждый символ используется для представления 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 с данными в nбайтах данных создаст строку 4n/3символов Base64. Другими словами, каждые 3 байта данных приведут к 4 символам Base64. РЕДАКТИРОВАТЬ : комментарий правильно указывает, что мой предыдущий рисунок не учитывал отступы; правильная формула 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 символов, как мы и ожидали.

Целые

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

Для этого полезно вспомнить, как выполнить деление потолка: 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, так что просто оставьте его таким, чтобы сохранить читабельность.

без ведущего

Менее распространенным является вариант без дополнения, для этого мы помним, что для каждого нам нужен символ для каждых 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

без ведущего

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

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

Ноты:

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

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

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

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

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

Вот функция для вычисления исходного размера закодированного файла 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;
}

В то время как все остальные обсуждают алгебраические формулы, я бы предпочел просто использовать сам 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, кажется правильной.

(В попытке дать краткое, но полное деривация.)

Каждый входной байт имеет 8 битов, поэтому для n входных байтов мы получаем:

n × 8 входных бит

Каждые 6 битов являются выходными байтами, поэтому:

ceil ( n × 8/6 ) =  ceil ( n × 4/3 ) выходных байтов

Это без дополнения.

С отступом мы округляем это до нескольких из четырех выходных байтов:

ceil ( ceil ( n × 4/3 ) / 4) × 4 =  ceil ( n × 4/3/4 ) × 4 =  ceil ( n / 3) × 4 выходных байта

См. Вложенные подразделения (Wikipedia) для первой эквивалентности.

Использование целочисленной арифметики, CEIL ( п / м ) может быть рассчитано как ( п + т - 1) Div м , следовательно , мы получаем:

( н * 4 + 2) div 3 без отступов

( n + 2) div 3 * 4 с отступом

Для иллюстрации:

 n   with padding    (n + 2) div 3 * 4    without padding   (n * 4 + 2) div 3 
------------------------------------------------------------------------------
 0                           0                                      0
 1   AA==                    4            AA                        2
 2   AAA=                    4            AAA                       3
 3   AAAA                    4            AAAA                      4
 4   AAAAAA==                8            AAAAAA                    6
 5   AAAAAAA=                8            AAAAAAA                   7
 6   AAAAAAAA                8            AAAAAAAA                  8
 7   AAAAAAAAAA==           12            AAAAAAAAAA               10
 8   AAAAAAAAAAA=           12            AAAAAAAAAAA              11
 9   AAAAAAAAAAAA           12            AAAAAAAAAAAA             12
10   AAAAAAAAAAAAAA==       16            AAAAAAAAAAAAAA           14
11   AAAAAAAAAAAAAAA=       16            AAAAAAAAAAAAAAA          15
12   AAAAAAAAAAAAAAAA       16            AAAAAAAAAAAAAAAA         16

Наконец, в случае кодирования MIME Base64 необходимы два дополнительных байта (CR LF) на каждые 76 выходных байтов, округленных в большую или меньшую сторону в зависимости от того, требуется ли завершающий символ новой строки.

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

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

Я считаю, что это точный ответ, если 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]

Радоваться, веселиться

солдат

Простая реализация в JavaScript

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

Для всех людей, которые говорят на C, взгляните на эти два макроса:

// calculate the size of 'output' buffer required for a 'input' buffer of length x during Base64 encoding operation
#define B64ENCODE_OUT_SAFESIZE(x) ((((x) + 3 - 1)/3) * 4 + 1) 

// calculate the size of 'output' buffer required for a 'input' buffer of length x during Base64 decoding operation
#define B64DECODE_OUT_SAFESIZE(x) (((x)*3)/4) 

Взято отсюда .

Я не вижу упрощенной формулы в других ответах. Логика покрыта, но я хотел основную форму для моего встроенного использования:

  Unpadded = ((4 * n) + 2) / 3

  Padded = 4 * ((n + 2) / 3)

ПРИМЕЧАНИЕ. При подсчете количества незаполненных полей мы округляем целочисленное деление, т.е. добавляем делитель-1, который в данном случае равен +2.

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

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

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

Если кто-то заинтересован в достижении решения @Pedro Silva в JS, я просто перенес это решение:

const getBase64Size = (base64) => {
  let padding = base64.length
    ? getBase64Padding(base64)
    : 0
  return ((Math.ceil(base64.length / 4) * 3 ) - padding) / 1000
}

const getBase64Padding = (base64) => {
  return endsWith(base64, '==')
    ? 2
    : 1
}

const endsWith = (str, end) => {
  let charsFromEnd = end.length
  let extractedEnd = str.slice(-charsFromEnd)
  return extractedEnd === end
}