Почему для кодирования base64 требуется заполнение, если входная длина не делится на 3?

Question

Какова цель заполнения в кодировке base64.Ниже приводится выдержка из википедии:

"Выделен дополнительный символ пэда, который может использоваться для принудительного преобразования закодированного вывода в целое число, кратное 4 символам (или, что эквивалентно, когда некодированный двоичный текст не кратен3 байта); эти символы дополнения должны затем отбрасываться при декодировании, но все же позволяют вычислять эффективную длину незакодированного текста, когда его входная двоичная длина не будет кратна 3 байтам (последний символ без отступа обычнозакодирован так, что последний 6-битный блок, который он представляет, будет дополнен нулями на его младших значащих битах, в конце закодированного потока может быть не более двух символов дополнения). "

Я написал программу, котораяможет кодировать base64 любую строку и декодировать любую строку в кодировке base64.Какую проблему решает заполнение?

Answer 1

Ваш вывод о том, что отступы не нужны, верен.Всегда можно однозначно определить длину входных данных по длине кодированной последовательности.

Однако заполнение полезно в ситуациях, когда закодированные строки base64 объединяются таким образом, что длины отдельных последовательностей равнытеряется, как, например, в очень простом сетевом протоколе.

Если объединены строки unpadded , восстановить исходные данные невозможно, поскольку информация о количестве нечетных байтов в конце каждой отдельной последовательности теряется.Однако, если используются дополненные последовательности, нет никакой двусмысленности, и последовательность в целом может быть правильно декодирована.

Редактировать: Иллюстрация

Предположим, у нас есть программа, которая кодирует слова base64,объединяет их и отправляет по сети.Он кодирует «I», «AM» и «TJM», сжимает результаты вместе без заполнения и передает их.

• I кодирует в SQ (SQ== с заполнением)
• AM кодирует в QU0 (QU0= с отступом)
• TJM кодирует в VEpN (VEpN с заполнением)

Такпередаваемые данные SQQU0VEpN.Приемник base64-декодирует это как I\x04\x14\xd1Q) вместо намеченного IAMTJM.Результат бессмыслен, поскольку отправитель уничтожил информацию о том, где заканчивается каждое слово в закодированной последовательности.Если бы отправитель вместо этого отправил SQ==QU0=VEpN, получатель мог бы декодировать это как три отдельные последовательности base64, которые объединялись бы, чтобы дать IAMTJM.

Зачем беспокоиться о заполнении?

Почему бы не просторазработать протокол для префикса каждого слова с целой длиной?Тогда получатель сможет правильно декодировать поток, и не будет необходимости в заполнении.

Это отличная идея, если мы знаем длину данных, которые мы кодируем, прежде чем мыначать кодировать это.Но что, если бы вместо слов мы кодировали фрагменты видео с живой камеры?Мы можем заранее не знать длину каждого блока.

Если бы в протоколе использовалось заполнение, не было бы необходимости передавать длину вообще.Данные могут быть закодированы так, как они поступили с камеры, каждый фрагмент завершается заполнением, и получатель сможет правильно декодировать поток.

Очевидно, это очень надуманный пример, но, возможно, он иллюстрирует, почему заполнениеможет быть полезным в некоторых ситуациях.

Answer 2

Что такое символы заполнения?

Символы заполнения помогают удовлетворить требования к длине и не имеют никакого смысла.

Десятичный пример заполнения: Учитывая произвольное требование, все строки имеют длину 8 символов, число 640 может удовлетворить это требование, используя предшествующие 0 в качестве символов заполнения, так как они не имеют значения, "00000640».

Двоичное кодирование

Парадигма байтов: Байт является стандартной единицей измерения де-факто, и любая схема кодирования должна относиться к байтам.

Base256 точно вписывается в эту парадигму.Один байт равен одному символу в base256.

Base16 , шестнадцатеричный или шестнадцатеричный, использует 4 бита для каждого символа.Один байт может представлять два символа base16.

Base64 не вписывается равномерно в байтовую парадигму, в отличие от base256 и base16.Все символы base64 могут быть представлены в 6 битах, на 2 бита меньше полного байта.

Мы можем представить кодировку base64 в сравнении с парадигмой байтов в виде дроби: 6 битов на символ более 8 битов на байт .Сократил эту долю на 3 байта по сравнению с 4 символами.

Это соотношение, 3 байта на каждые 4 символа base64, является правилом, которому мы хотим следовать при кодировании base64. Кодировка Base64 может обещать только измерения с 3-байтовыми пакетами, в отличие от base16 и base256, где каждый байт может стоять самостоятельно.

Так что , почему рекомендуется заполнять, даже есликодирование может работать нормально без дополнительных символов?Символы заполнения явно сообщают, что эти дополнительные места должны быть пустыми и исключают любую двусмысленность или потенциально неприятные ошибки.Заполнение позволяет нам декодировать кодирование base64 с обещанием не потерять биты.Без заполнения больше нет явного подтверждения измерения в трехбайтовых пакетах, и мы больше не можем гарантировать точное воспроизведение оригинального кодирования без дополнительной информации.

Примеры

Вот пример формы RFC 4648 (http://tools.ietf.org/html/rfc4648#section-8)

Каждый символ внутри функции "BASE64" использует один байт (base256). Затем мы переводим это в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.)

Вот кодер, с которым вы можете поиграть: http://www.motobit.com/util/base64-decoder-encoder.asp

Answer 3

Это только моя теория, и я не могу предоставить никаких источников, но я думаю, что символ (ы) дополнения служат только для того, чтобы некоторые реализации алгоритма декодирования мельчайшие немного проще.В частности, если алгоритм помещает закодированную строку во что-то вроде int[], тогда конечное значение иногда будет слишком длинным.

Если заполнение уже присутствует во входных данных, то больше ничего делать не нужно -Алгоритм может просто считывать и декодировать входные данные.

Если алгоритму не разрешено предполагать наличие заполнения, однако, и , он использует int[] -подобную структуру данных, затем ему нужно вручную заполнить конечное целое число перед декодированием или сделать дополнительную бухгалтерию по исходной длине ввода.

Лично я не думаю, что заполнение больше служит какой-либо цели, но обратно, когда процессори оперативной памяти было не так много, как сейчас, возможно, эта небольшая оптимизация имела значение.Я сомневаюсь, что это имело большое значение, хотя ... хорошая реализация все равно должна была бы делать что-то разумное, когда входной сигнал был усечен случайным образом, и это, IMO, давало бы возможность обрабатывать незаполненные входы без дополнительных затрат.