Cálculo do comprimento da Base64?

Depois de ler o wiki base64 ...

Estou tentando descobrir como está funcionando a fórmula:

Dada uma string com comprimento de n, o comprimento da base64 será

Qual é : 4*Math.Ceiling(((double)s.Length/3)))

Eu já sei que o comprimento base64 deve ser %4==0para permitir que o decodificador saiba qual era o comprimento do texto original.

O número máximo de preenchimento para uma sequência pode ser =ou ==.

wiki: O número de bytes de saída por byte de entrada é aproximadamente 4/3 (33% de sobrecarga)

Questão:

Como as informações acima se ajustam ao comprimento da saída ?

Cada caractere é usado para representar 6 bits ( log2(64) = 6).

Portanto, 4 caracteres são usados ​​para representar 4 * 6 = 24 bits = 3 bytes.

Portanto, você precisa de 4*(n/3)caracteres para representar nbytes, e isso precisa ser arredondado para um múltiplo de 4.

O número de caracteres de preenchimento não utilizados resultantes do arredondamento para um múltiplo de 4 será obviamente 0, 1, 2 ou 3.

4 * n / 3 fornece comprimento não acolchoado.

E arredondar para o múltiplo mais próximo de 4 para preenchimento e, como 4 é uma potência de 2, pode usar operações lógicas bit a bit.

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

Para referência, a fórmula de comprimento do codificador Base64 é a seguinte:

Como você disse, um codificador Base64 dado nbytes de dados produzirá uma sequência de 4n/3caracteres Base64. Em outras palavras, a cada 3 bytes de dados resultará em 4 caracteres Base64. EDIT : Um comentário indica corretamente que meu gráfico anterior não foi responsável pelo preenchimento; a fórmula correta é Ceiling(4n/3) .

O artigo da Wikipedia mostra exatamente como a string ASCII Man codificada na string Base64 TWFuem seu exemplo. A cadeia de caracteres de entrada é de 3 bytes, ou 24 bits, em tamanho, de modo que a fórmula prevê correctamente a saída será de 4 bytes (ou 32 bits) de comprimento: TWFu. O processo codifica a cada 6 bits de dados em um dos 64 caracteres Base64; portanto, a entrada de 24 bits dividida por 6 resulta em 4 caracteres Base64.

Você pergunta em um comentário qual seria o tamanho da codificação 123456. Tendo em mente que todo caractere dessa string tem 1 byte ou 8 bits de tamanho (assumindo a codificação ASCII / UTF8), estamos codificando 6 bytes, ou 48 bits, de dados. De acordo com a equação, esperamos que o comprimento da saída seja (6 bytes / 3 bytes) * 4 characters = 8 characters.

A inserção 123456em um codificador Base64 cria MTIzNDU2, com 8 caracteres, exatamente como esperávamos.

Inteiros

Geralmente, não queremos usar duplos porque não queremos usar operações de ponto flutuante, erros de arredondamento etc. Eles simplesmente não são necessários.

Para isso, é uma boa idéia lembrar-se de como realizar a divisão do teto: o ceil(x / y)dobro pode ser escrito como (x + y - 1) / y(enquanto evita números negativos, mas cuidado com o excesso).

Legível

Se você busca legibilidade, é claro que também pode programá-lo desta forma (exemplo em Java, para C, você pode usar macro, é claro):

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));
    }
}

Inline

Acolchoado

Sabemos que precisamos de 4 blocos de caracteres por vez para cada 3 bytes (ou menos). Então a fórmula se torna (para x = ne y = 3):

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

ou combinado:

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

seu compilador otimizará o 3 - 1, então deixe assim para manter a legibilidade.

Sem almofada

Menos comum é a variante não-acolchoada, para isso lembramos que cada um de nós precisa de um caractere para cada 6 bits, arredondado para cima:

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

ou combinado:

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

no entanto, ainda podemos dividir por dois (se quisermos):

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

Ilegível

Caso você não confie no seu compilador para fazer as otimizações finais para você (ou se você quiser confundir seus colegas):

Acolchoado

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

Sem almofada

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

Portanto, existem duas formas lógicas de cálculo e não precisamos de ramificações, operações de bits ou operações de módulos - a menos que realmente desejemos.

Notas:

• Obviamente, pode ser necessário adicionar 1 aos cálculos para incluir um byte de terminação nulo.
• Para o Mime, você pode precisar cuidar de possíveis caracteres de terminação de linha e outros (procure outras respostas para isso).

Eu acho que as respostas dadas não atendem ao objetivo da pergunta original, que é a quantidade de espaço que precisa ser alocada para ajustar a codificação base64 para uma determinada seqüência binária de comprimento n bytes.

A resposta é (floor(n / 3) + 1) * 4 + 1

Isso inclui preenchimento e um caractere nulo final. Você pode não precisar da chamada de piso se estiver fazendo aritmética de número inteiro.

Incluindo preenchimento, uma string base64 requer quatro bytes para cada pedaço de três bytes da string original, incluindo todos os pedaços parciais. Um ou dois bytes extras no final da string ainda serão convertidos em quatro bytes na string base64 quando o preenchimento for adicionado. A menos que você tenha um uso muito específico, é melhor adicionar o preenchimento, geralmente um caractere igual. Eu adicionei um byte extra para um caractere nulo em C, porque as strings ASCII sem isso são um pouco perigosas e você precisa carregar o comprimento da string separadamente.

Aqui está uma função para calcular o tamanho original de um arquivo Base 64 codificado como uma String em KB:

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;
}

Enquanto todo mundo está debatendo fórmulas algébricas, prefiro usar o próprio BASE64 para me dizer:

$ 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

Parece que a fórmula de 3 bytes representada por 4 caracteres base64 parece correta.

(Na tentativa de fornecer uma derivação sucinta e completa.)

Cada byte de entrada possui 8 bits, portanto, para n bytes de entrada, obtemos:

n × 8 bits de entrada

A cada 6 bits é um byte de saída, portanto:

ceil ( n × 8/6 ) =  ceil ( n × 4/3 ) bytes de saída

Isso é sem preenchimento.

Com o preenchimento, arredondamos esse número para vários bytes de saída:

teto ( teto ( n × 4/3 ) / 4) × 4 =  teto ( n × 4/3/4 ) × 4 =  teto ( n / 3) × 4 bytes de saída

Consulte Divisões aninhadas (Wikipedia) para obter a primeira equivalência.

Usando aritmética inteira, ceil ( n / m ) pode ser calculado como ( n + m - 1) div m , portanto, obtemos:

( n * 4 + 2) div 3 sem preenchimento

( n + 2) div 3 * 4 com preenchimento

Para ilustração:

 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

Finalmente, no caso da codificação MIME Base64, são necessários dois bytes adicionais (CR LF) a cada 76 bytes de saída, arredondados para cima ou para baixo, dependendo se uma nova linha final é necessária.

Parece-me que a fórmula correta deve ser:

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

Eu acredito que esta é uma resposta exata se n% 3 não zero, não?

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

Versão do Mathematica:

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

Diverta-se

GI

Implementação simples em javascript

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

Para todas as pessoas que falam C, dê uma olhada nessas duas macros:

// 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) 

Retirado daqui .

Não vejo a fórmula simplificada em outras respostas. A lógica é abordada, mas eu queria uma forma mais básica para o meu uso incorporado:

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

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

NOTA: Ao calcular a contagem não preenchida, arredondamos a divisão inteira, ou seja, adicionamos o Divisor-1, que é +2 neste caso

No Windows - eu queria estimar o tamanho do buffer do tamanho mime64, mas todas as fórmulas precisas de cálculo não funcionaram para mim - finalmente, acabei com uma fórmula aproximada como esta:

Tamanho da alocação de sequência do Mine64 (aproximado) = (((4 * ((tamanho do buffer binário) + 1)) / 3) + 1)

Portanto, o último +1 - é usado para ascii-zero - o último caractere precisa ser alocado para armazenar o final zero - mas por que "tamanho do buffer binário" é + 1 - suspeito que haja algum caractere de terminação mime64? Ou pode ser que isso seja algum problema de alinhamento.

Se houver alguém interessado em obter a solução @Pedro Silva em JS, eu apenas portamos a mesma solução:

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
}