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

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

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

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

Ответы

Ответ 1

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

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

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

Изменить: Иллюстрация

Предположим, что у нас есть программа, которая кодирует слова 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.

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

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

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

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

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

Ответ 2

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

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

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

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

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

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

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

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

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

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

Итак, почему поддерживается добавление, даже если кодировка может работать отлично, без пробелов? Прописные символы явно сообщают, что эти дополнительные пятна должны быть пустыми и исключать любую двусмысленность или потенциально неприятные ошибки. Padding позволяет декодировать кодировку 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

Ответ 3

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

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

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

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