string - online - Cálculo de longitud Base64?

decode string

Question

Después de leer el wiki base64 ...

Estoy intentando descubrir cómo funciona la fórmula:

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

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

Ya sé que la longitud de base64 debe ser %4==0 para 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 de aproximadamente 4/3 (33% de sobrecarga)

Pregunta:

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

Answer 1

Enteros

En general, no queremos usar dobles porque no queremos utilizar 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 de techo: ceil(x / y) en dobles se puede escribir como (x + y - 1) / y (evitando los números negativos, pero tenga cuidado con el desbordamiento).

Legible

Si busca legibilidad, puede, por supuesto, programarlo de esta manera (por ejemplo, en Java, para C puede 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 4 bloques de caracteres en el momento para cada 3 bytes (o menos). Entonces la fórmula se vuelve (para x = n y y = 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 simplemente 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 personaje por cada 6 bits, redondeado hacia arriba:

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 ramas, operaciones de bits o operaciones de módulo, a menos que realmente lo deseemos.

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 posibles caracteres de terminación de línea y demás (busque otras respuestas para eso).

Answer 2

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

Answer 3

Cada caracter se usa para representar 6 bits ( log2(64) = 6 ).

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

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

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

Answer 4

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

Como dijiste, un codificador Base64 dado n bytes de datos producirá una cadena de 4n/3 caracteres Base64. Dicho de otra manera, cada 3 bytes de datos darán como resultado 4 caracteres Base64. EDITAR : un comentario indica correctamente que mi gráfico anterior no tuvo 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 codificada en la cadena Base64 TWFu en su ejemplo. La cadena de entrada tiene un tamaño de 3 bytes o 24 bits, por lo que la fórmula predice correctamente que la salida será de 4 bytes (o 32 bits) de longitud: 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 entre 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 uno de los caracteres de esa cadena es de 1 byte u 8 bits, en tamaño (asumiendo la codificación ASCII / UTF8), estamos codificando 6 bytes, o 48 bits, de datos. Según la ecuación, esperamos que la longitud de salida sea (6 bytes / 3 bytes) * 4 characters = 8 characters .

Al poner 123456 en un codificador Base64, se crea MTIzNDU2 , que tiene 8 caracteres, tal como esperábamos.

Answer 5

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

Answer 6

Creo que las respuestas dadas pierden el sentido de la pregunta original, que es cuánto espacio necesita 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 necesites la llamada al piso si estás haciendo cálculos aritméticos 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 se convertirán en 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 extra 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 cuerda por separado.

Answer 7

En Windows - Quería estimar el tamaño del buffer de tamaño mime64, pero todas las fórmulas de cálculo precisas no me funcionaron - finalmente terminé con una fórmula aproximada como esta:

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

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

Answer 8

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

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

Answer 9

Mientras todos los demás debaten 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 representada por 4 caracteres base64 parece correcta.

Answer 10

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 en modo bit.

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