Base64 cálculo de longitud?

Después de leer el wiki de base64 ...

Estoy tratando de averiguar cómo funciona la fórmula:

Dada una cadena con una longitud de n, la longitud base64 será

Cual es : 4*Math.Ceiling(((double)s.Length/3)))

Ya sé que la longitud base64 debe ser %4==0para permitir que el decodificador sepa cuál era la longitud del texto original.

El número máximo de relleno para una secuencia puede ser =o ==.

wiki: el número de bytes de salida por byte de entrada es aproximadamente 4/3 (33% de sobrecarga)

Pregunta:

¿ Cómo se establece la información anterior con la longitud de salida ?

Cada carácter se usa para representar 6 bits ( log2(64) = 6).

Por lo tanto, se utilizan 4 caracteres para representar 4 * 6 = 24 bits = 3 bytes.

Por lo tanto, necesita 4*(n/3)caracteres para representar nbytes, y esto debe redondearse a un múltiplo de 4.

El número de caracteres de relleno no utilizados como resultado del redondeo a un múltiplo de 4 obviamente será 0, 1, 2 o 3.

4 * n / 3 da longitud sin relleno.

Y redondee al múltiplo de 4 más cercano para el relleno, y como 4 es una potencia de 2, puede usar operaciones lógicas bit a bit.

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

Como referencia, la fórmula de longitud del codificador Base64 es la siguiente:

Como dijiste, un codificador Base64 dado nbytes de datos producirá una cadena de 4n/3caracteres Base64. Dicho de otra manera, cada 3 bytes de datos generarán 4 caracteres Base64. EDITAR : un comentario señala correctamente que mi gráfico anterior no tenía en cuenta el relleno; La fórmula correcta es Ceiling(4n/3) .

El artículo de Wikipedia muestra exactamente cómo la cadena ASCII Man codificó en la cadena Base64 TWFuen su ejemplo. La cadena de entrada es de 3 bytes o 24 bits, en tamaño, por lo que la fórmula predice correctamente la salida será de 4 bytes (o 32 bits) de largo: TWFu. El proceso codifica cada 6 bits de datos en uno de los 64 caracteres Base64, por lo que la entrada de 24 bits dividida por 6 da como resultado 4 caracteres Base64.

Usted pregunta en un comentario cuál sería el tamaño de la codificación 123456. Teniendo en cuenta que cada carácter de esa cadena tiene 1 byte u 8 bits de tamaño (suponiendo la codificación ASCII / UTF8), estamos codificando 6 bytes, o 48 bits, de datos. De acuerdo con la ecuación, esperamos que la longitud de salida sea (6 bytes / 3 bytes) * 4 characters = 8 characters.

La creación de 123456un codificador Base64 crea MTIzNDU2, que tiene 8 caracteres de longitud, tal como esperábamos.

Enteros

Generalmente no queremos usar dobles porque no queremos usar operaciones de coma flotante, errores de redondeo, etc. Simplemente no son necesarios.

Para esto, es una buena idea recordar cómo realizar la división del techo: ceil(x / y)en dobles se puede escribir como (x + y - 1) / y(evitando números negativos, pero tenga cuidado con el desbordamiento).

Legible

Si opta por la legibilidad, por supuesto, también puede programarlo de esta manera (por ejemplo, en Java, para C podría usar macros, por supuesto):

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

En línea

Acolchado

Sabemos que necesitamos bloques de 4 caracteres a la vez por cada 3 bytes (o menos). Entonces la fórmula se convierte (para x = ny e = 3):

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

o combinado:

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

su compilador optimizará el 3 - 1, así que déjelo así para mantener la legibilidad.

Sin relleno

Menos común es la variante sin relleno, para esto recordamos que cada uno necesitamos un carácter para cada 6 bits, redondeado:

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

o combinado:

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

sin embargo, aún podemos dividir por dos (si queremos):

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

Ilegible

En caso de que no confíe en su compilador para hacer las optimizaciones finales por usted (o si quiere confundir a sus colegas):

Acolchado

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

Sin relleno

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

Así que ahí estamos, dos formas lógicas de cálculo, y no necesitamos ninguna rama, bit-ops u modulo ops, a menos que realmente lo queramos.

Notas:

• Obviamente, es posible que deba agregar 1 a los cálculos para incluir un byte de terminación nulo.
• Para Mime, es posible que deba ocuparse de los posibles caracteres de terminación de línea y demás (busque otras respuestas para eso).

Creo que las respuestas dadas pierden el punto de la pregunta original, que es cuánto espacio debe asignarse para ajustarse a la codificación base64 para una cadena binaria dada de longitud n bytes.

La respuesta es (floor(n / 3) + 1) * 4 + 1

Esto incluye relleno y un carácter nulo de terminación. Es posible que no necesite la llamada de piso si está haciendo aritmética de enteros.

Incluyendo el relleno, una cadena base64 requiere cuatro bytes por cada fragmento de tres bytes de la cadena original, incluidos los fragmentos parciales. Uno o dos bytes adicionales al final de la cadena aún se convertirán a cuatro bytes en la cadena base64 cuando se agregue relleno. A menos que tenga un uso muy específico, es mejor agregar el relleno, generalmente un carácter igual. Agregué un byte adicional para un carácter nulo en C, porque las cadenas ASCII sin esto son un poco peligrosas y tendrías que llevar la longitud de la cadena por separado.

Aquí hay una función para calcular el tamaño original de un archivo Base 64 codificado como una Cadena en 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;
}

Mientras que todos los demás están debatiendo fórmulas algebraicas, prefiero usar BASE64 para decirme:

$ 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

Entonces parece que la fórmula de 3 bytes representados por 4 caracteres base64 parece correcta.

(En un intento de dar una derivación sucinta pero completa).

Cada byte de entrada tiene 8 bits, por lo que para n bytes de entrada obtenemos:

n × 8 bits de entrada

Cada 6 bits es un byte de salida, entonces:

ceil ( n × 8/6 ) =  bytes de salida ceil ( n × 4/3 )

Esto es sin relleno.

Con el relleno, redondeamos eso a múltiples de cuatro bytes de salida:

ceil ( ceil ( n × 4/3 ) / 4) × 4 =  ceil ( n × 4/3/4 ) × 4 =  ceil ( n / 3) × 4 bytes de salida

Ver Divisiones anidadas (Wikipedia) para la primera equivalencia.

Usando aritmética de enteros, ceil ( n / m ) se puede calcular como ( n + m - 1) div m , por lo tanto obtenemos:

( n * 4 + 2) div 3 sin relleno

( n + 2) div 3 * 4 con relleno

Por ilustracion:

 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, en el caso de la codificación MIME Base64, se necesitan dos bytes adicionales (CR LF) por cada 76 bytes de salida, redondeados hacia arriba o hacia abajo dependiendo de si se requiere una nueva línea de terminación.

Me parece que la fórmula correcta debería ser:

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

Creo que esta es una respuesta exacta si n% 3 no es cero, ¿no?

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

Versión de Mathematica:

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

Que te diviertas

soldado americano

Implementación simple en javascript

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

Para todas las personas que hablan C, eche un vistazo a estas dos 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) 

Tomado de aquí .

No veo la fórmula simplificada en otras respuestas. La lógica está cubierta pero quería una forma más básica para mi uso incrustado:

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

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

NOTA: Al calcular el recuento sin relleno, redondeamos la división entera, es decir, agregamos Divisor-1, que es +2 en este caso

En Windows, quería estimar el tamaño del búfer de tamaño mime64, pero todas las fórmulas de cálculo precisas no funcionaron para mí, finalmente terminé con una fórmula aproximada como esta:

Tamaño de asignación de cadena de Mine64 (aproximado) = (((4 * ((tamaño del búfer binario) + 1)) / 3) + 1)

Así que el último +1 - se usa para ascii-cero - el último carácter debe asignarse para almacenar la terminación cero - pero ¿por qué el "tamaño del búfer binario" es + 1? Sospecho que hay algún carácter de terminación mime64? O puede ser este es un problema de alineación.

Si hay alguien interesado en lograr la solución @Pedro Silva en JS, acabo de portar esta misma solución:

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
}