Base64 cálculo de longitud?

155

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áingrese la descripción de la imagen aquí

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 ingrese la descripción de la imagen aquí?

Royi Namir
fuente

Respuestas:

210

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.

Paul R
fuente
¿Dónde está el relleno aquí?
Royi Namir
1
Considere si tiene un byte de entrada. Eso producirá cuatro caracteres de salida. Pero solo se necesitan dos caracteres de salida para codificar la entrada. Entonces dos personajes estarán rellenando.
David Schwartz
2
La longitud de salida siempre se redondea a un múltiplo de 4, por lo que 1, 2 o 3 bytes de entrada => 4 caracteres; 4, 5 o 6 bytes de entrada => 8 caracteres; 7, 8 o 9 bytes de entrada => 12 caracteres.
Paul R
55
Expliqué todo esto en la respuesta anterior: (i) cada carácter de salida representa 6 bits de entrada, (ii) 4 caracteres de salida, por lo tanto, representan 4 * 6 = 24 bits , (iii) 24 bits son 3 bytes , (iv) 3 bytes de entrada, por lo tanto, da como resultado 4 caracteres de salida, (v) la relación de caracteres de salida a bytes de entrada es, por lo tanto, 4/3
Paul R
2
@ techie_28: hago 27308 caracteres para 20 * 1024 bytes, pero aún no he tomado café esta mañana.
Paul R
60

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
Ren
fuente
1
¡Tienes razón! -> 4 * n / 3 da longitud sin relleno! Las respuestas anteriores no son correctas. -> ((4 * n / 3) + 3) & ~ 3 devuelve el resultado correcto
Cadburry
No funciona como entrada para la API CryptBinaryToStringA de Windows.
TarmoPikaro
para explicarlo a las personas que usan shell:$(( ((4 * n / 3) + 3) & ~3 ))
starfry
1
4 * n / 3ya falla en n = 1, un byte está codificado con dos caracteres, y el resultado es claramente un carácter.
Maarten Bodewes
1
@Crog Como está escrito si n = 1, entonces obtendrá 4/3 = 1 usando enteros. Como ha indicado, el resultado esperado es 2, no 1.
Maarten Bodewes
25

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

Fórmula de longitud del codificador Base64

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.

David Schwartz
fuente
55
Usando esta fórmula, tenga en cuenta que no da la longitud acolchada. Para que pueda tener una longitud más larga.
Spilarix
Para calcular los bytes decodificados esperados del texto base64, uso la fórmula floor((3 * (length - padding)) / 4). Echa un vistazo a la siguiente esencia .
Kurt Vangraefschepe
13

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).
Maarten Bodewes
fuente
5

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.

Ian Nartowicz
fuente
55
Tu fórmula está mal. Considere n = 3, el resultado esperado (sin relleno nulo) es 4, pero su fórmula devuelve 8.
CodesInChaos
55
También creo que incluir el terminador nulo es una tontería, especialmente porque estamos hablando de .net aquí.
CodesInChaos
Funciona correctamente en Windows, usando CryptBinaryToStringA. Mi voto por esto.
TarmoPikaro
5

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;
}
Pedro Silva
fuente
3

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.

Michael Adams
fuente
1
Tengo algo en contra de los cálculos que requieren mucha memoria y tiempo de CPU, mientras que los cálculos se pueden realizar en 1 ns y uno o dos registros.
Maarten Bodewes
Entonces, cuando intentas lidiar con cantidades desconocidas de datos binarios, ¿cómo ayuda esto?
UKMonkey
La pregunta es sobre fórmulas, que ayudan a calcular el tamaño de salida sin hacer la base64 en sí. Si bien esta respuesta es útil en algunas situaciones, no ayuda con esta pregunta.
Alejandro
3

(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.

nmatt
fuente
Gracias por el análisis detallado
P Satish Patro
2

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

n64 = 4 * (n / 3) + (n % 3 != 0 ? 4 : 0)
Valo
fuente
El relleno cero de Ascii no se tiene en cuenta; no funciona en Windows. (CryptBinaryToStringA)
TarmoPikaro
1

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

Igerard
fuente
1

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;
}
qoomon
fuente
1

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í .

Andreas
fuente
1

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

Crog
fuente
0

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.

TarmoPikaro
fuente
0

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
}
elverde
fuente