encoding - divisibilidad - numeros divisibles por 3

¿Por qué la codificación base64 requiere relleno si la longitud de entrada no es divisible por 3?

Question

¿Cuál es el propósito del relleno en la codificación base64? El siguiente es el extracto de wikipedia:

"Se asigna un carácter de relleno adicional que se puede usar para forzar la salida codificada en un múltiplo entero de 4 caracteres (o de manera equivalente cuando el texto binario no codificado no es un múltiplo de 3 bytes); estos caracteres de relleno deben descartarse al descodificar pero todavía permite el cálculo de la longitud efectiva del texto no codificado, cuando su longitud binaria de entrada no sería un múltiplo de 3 bytes (el último carácter no de relleno se codifica normalmente para que el último bloque de 6 bits que representa sea cero) -padeado en sus bits menos significativos, como máximo pueden aparecer dos caracteres de relleno al final de la secuencia codificada) ".

Escribí un programa que podía codificar en base64 cualquier cadena y decodificar cualquier cadena codificada en base64. ¿Qué problema resuelve el relleno?

Answer 1

¿Qué son los personajes de relleno?

Los caracteres de relleno ayudan a satisfacer los requisitos de longitud y no tienen ningún significado.

Ejemplo decimal de relleno: Dado el requisito arbitrario, todas las cadenas deben tener una longitud de 8 caracteres, el número 640 puede cumplir este requisito utilizando los 0 anteriores como caracteres de relleno ya que no tienen ningún significado, "00000640".

Codificación binaria

El paradigma de bytes: el byte es la unidad de medida estándar de facto y cualquier esquema de codificación debe relacionarse con los bytes.

Base256 encaja exactamente en este paradigma. Un byte es igual a un carácter en base256.

Base16 , hexadecimal o hexadecimal, utiliza 4 bits para cada carácter. Un byte puede representar dos caracteres base16.

Base64 no encaja de manera uniforme en el paradigma de bytes, a diferencia de base256 y base16. Todos los caracteres base64 se pueden representar en 6 bits, 2 bits menos que un byte completo.

Podemos representar la codificación base64 frente al paradigma de bytes como una fracción: 6 bits por carácter y 8 bits por byte . Reducida esta fracción es de 3 bytes sobre 4 caracteres.

Esta relación, 3 bytes por cada 4 caracteres base64, es la regla que queremos seguir al codificar base64. La codificación Base64 solo puede prometer la medición incluso con paquetes de 3 bytes, a diferencia de base16 y base256 donde cada byte puede sostenerse por sí solo.

Entonces, ¿ por qué se recomienda el relleno aunque la codificación podría funcionar bien sin los caracteres de relleno? Los caracteres de relleno comunican explícitamente que esos puntos adicionales deben estar vacíos y descarta cualquier ambigüedad o errores potencialmente desagradables. El relleno nos permite descodificar la codificación base64 con la promesa de no perder bits. Sin el relleno, ya no existe el reconocimiento explícito de la medición en paquetes de tres bytes y ya no podemos garantizar la reproducción exacta de la codificación original sin información adicional.

Ejemplos

Aquí está el formulario de ejemplo RFC 4648 ( http://tools.ietf.org/html/rfc4648#section-8 )

Cada carácter dentro de la función "BASE64" usa un byte (base256). Luego lo traducimos a base64.

BASE64("") = "" (No bytes used. 0%3=0.)
BASE64("f") = "Zg==" (One byte used. 1%3=1.)
BASE64("fo") = "Zm8=" (Two bytes. 2%3=2.)
BASE64("foo") = "Zm9v" (Three bytes. 3%3=0.)
BASE64("foob") = "Zm9vYg==" (Four bytes. 4%3=1.)
BASE64("fooba") = "Zm9vYmE=" (Five bytes. 5%3=2.)
BASE64("foobar") = "Zm9vYmFy" (Six bytes. 6%3=0.)

Aquí hay un codificador con el que puedes jugar: http://www.motobit.com/util/base64-decoder-encoder.asp

Answer 2

Esta es solo una teoría mía, y no puedo proporcionar ninguna fuente, pero creo que los caracteres de relleno solo sirven para hacer que algunas implementaciones del algoritmo de decodificación sean un poco más simples. En particular, si el algoritmo coloca la cadena codificada en algo como int[] , el valor final a veces será demasiado largo.

Si el relleno ya está presente en la entrada, entonces no se necesita hacer nada más: el algoritmo puede simplemente leer y decodificar la entrada.

Sin embargo, si no se permite que el algoritmo asuma que el relleno está presente, y utiliza una estructura de datos similar a int[] , entonces debe rellenar manualmente el número entero final antes de decodificar, o hacer una contabilidad adicional en la longitud original de la entrada.

Personalmente, ya no creo que el relleno sirva para ningún propósito, pero cuando la CPU y la RAM no eran tan abundantes como ahora esta pequeña optimización podría haber importado. Sin embargo, dudo que importara mucho ... una buena implementación aún tendría que hacer algo sensato cuando se alimenta una entrada que se trunca al azar, y eso, OMI, le daría la capacidad de procesar entradas sin relleno sin costo adicional.

Answer 3

Tu conclusión de que el relleno es innecesario es correcta. Siempre es posible determinar la longitud de la entrada de forma inequívoca a partir de la longitud de la secuencia codificada.

Sin embargo, el relleno es útil en situaciones donde las cadenas codificadas en base64 se concatenan de tal manera que las longitudes de las secuencias individuales se pierden, como podría ocurrir, por ejemplo, en un protocolo de red muy simple.

Si las cadenas no rellenadas se concatenan, es imposible recuperar los datos originales porque se pierde la información sobre el número de bytes impares al final de cada secuencia individual. Sin embargo, si se usan secuencias rellenadas, no hay ambigüedad y la secuencia en su totalidad puede decodificarse correctamente.

Editar: una ilustración

Supongamos que tenemos un programa que codifica en base a 64 palabras, las concatena y las envía a través de una red. Codifica "I", "AM" y "TJM", une los resultados sin relleno y los transmite.

• Codifico a SQ ( SQ== con relleno)
• AM codifica a QU0 ( QU0= con relleno)
• TJM codifica a VEpN ( VEpN con relleno)

Así que los datos transmitidos son SQQU0VEpN . El receptor base64 decodifica esto como I/x04/x14/xd1Q) lugar del IAMTJM deseado. El resultado no tiene sentido porque el remitente ha destruido información sobre dónde termina cada palabra en la secuencia codificada. Si el remitente hubiera enviado SQ==QU0=VEpN en SQ==QU0=VEpN lugar, el receptor podría haber descodificado esto como tres secuencias base64 separadas que concatenarían para dar IAMTJM .

¿Por qué molestarse con el relleno?

¿Por qué no diseñar el protocolo para prefijar cada palabra con una longitud entera? Entonces, el receptor podría decodificar el flujo correctamente y no habría necesidad de relleno.

Esa es una gran idea, siempre que sepamos la longitud de los datos que estamos codificando antes de comenzar a codificarlos. Pero, ¿y si, en lugar de palabras, estuviéramos codificando fragmentos de video de una cámara en vivo? Es posible que no sepamos de antemano la longitud de cada fragmento.

Si el protocolo utilizara el relleno, no habría necesidad de transmitir una longitud en absoluto. Los datos podrían codificarse a medida que salían de la cámara, cada parte terminaba con relleno y el receptor podría decodificar la transmisión correctamente.

Obviamente, ese es un ejemplo muy artificial, pero quizás ilustra por qué el relleno podría ser útil en algunas situaciones.