Почему для кодирования base64 требуется заполнение, если входная длина не делится на 3?
Какова цель заполнения в кодировке base64. Вот выдержка из википедии:
"Выделен дополнительный символ дополнения, который можно использовать для преобразования закодированного вывода в целое число, кратное 4 символам (или, что эквивалентно, когда двоичный текст без кодирования не кратен 3 байтам); эти символы дополнения должны затем отбрасываться при декодировании, но по-прежнему позволяют вычислять эффективную длину незашифрованного текста, когда его входная двоичная длина не будет кратна 3 байтам (последний символ без пэда обычно кодируется так, что последний 6-битный блок, который он представляет, будет нулевым - дополняется младшими значащими битами, в конце закодированного потока может встречаться не более двух символов дополнения)."
Я написал программу, которая могла бы кодировать base64 любую строку и декодировать любую строку в кодировке base64. Какую проблему решает заполнение?
5 ответов
Ваш вывод о том, что отступы не нужны, верен. Всегда можно однозначно определить длину входа по длине кодированной последовательности.
Однако заполнение полезно в ситуациях, когда строки, закодированные в 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,
Зачем беспокоиться о Padding?
Почему бы просто не разработать протокол для префикса каждого слова с целой длиной? Тогда приемник мог бы правильно декодировать поток и не было бы необходимости в заполнении.
Это отличная идея, если мы знаем длину данных, которые мы кодируем, прежде чем мы начнем их кодировать. Но что, если бы вместо слов мы кодировали фрагменты видео с живой камеры? Мы можем не знать длину каждого куска заранее.
Если бы в протоколе использовалось заполнение, не было бы необходимости передавать длину вообще. Данные могут быть закодированы, когда они поступают с камеры, каждый фрагмент заканчивается заполнением, и приемник сможет правильно декодировать поток.
Очевидно, это очень надуманный пример, но, возможно, он иллюстрирует, почему в некоторых ситуациях отступы могут быть полезны.
Что такое персонажи?
Заполняющие символы помогают удовлетворить требования по длине и не имеют никакого смысла.
Десятичный пример заполнения: учитывая произвольное требование, все строки имеют длину 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)
Каждый символ внутри функции "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
Это только моя теория, и я не могу предоставить какие-либо источники, но я думаю, что символ (ы) заполнения служат только для того, чтобы сделать некоторые реализации алгоритма декодирования крошечным битом проще. В частности, если алгоритм помещает закодированную строку во что-то вроде int[] тогда окончательное значение иногда будет слишком длинным.
Если заполнение уже присутствует во входных данных, то больше ничего не нужно делать - алгоритм может просто читать и декодировать входные данные.
Если алгоритму не разрешено предполагать наличие заполнения, однако, и он использует int[] Как и в случае структуры данных, перед декодированием необходимо вручную заполнить конечное целое число или выполнить некоторую дополнительную бухгалтерию по исходной длине ввода.
Лично я не думаю, что заполнение больше служит какой-либо цели, но назад, когда ЦП и ОЗУ были не так богаты, как сейчас, эта небольшая оптимизация могла иметь значение. Я сомневаюсь, что это имело большое значение, хотя... хорошая реализация все равно должна была бы делать что-то разумное, когда вводимые данные усекались случайным образом, и это, IMO, давало бы возможность обрабатывать незаполненные входы без дополнительных затрат.
С заполнением строка base64 всегда имеет длину, кратную 4 (если это не так, строка наверняка повреждена), и поэтому код может легко обрабатывать эту строку в цикле, который обрабатывает 4 символа за раз ( всегда преобразует 4 входных символа в три или менее выходных байта). Таким образом, заполнение упрощает проверку работоспособности (length % 4 != 0==> как невозможное с заполнением), и это делает обработку проще и эффективнее.
Я знаю, что подумают люди: даже без заполнения я могу обработать все 4-байтовые фрагменты в цикле, а затем просто добавить специальную обработку для последних 1-3 байтов, если они существуют. Всего несколько дополнительных строк кода, и разница в скорости будет слишком мала, чтобы ее можно было даже измерить. Вероятно, это так, но вы думаете о C (или более высоких языках) и мощном процессоре с большим количеством оперативной памяти. Что, если вам нужно декодировать base64 на аппаратном уровне, используя простой DSP, который имеет очень ограниченную вычислительную мощность, не имеет оперативной памяти, и вам нужно писать код в очень ограниченном микроассемблере? Что, если вы вообще не можете использовать код и все должно делаться только с помощью транзисторов, сложенных вместе (жесткая аппаратная реализация)? С прокладкой это намного проще, чем без.
Заполнение заполняет длину вывода до числа, кратного четырем байтам, определенным образом.