ASCII85

Ascii85 (Также известный как «Base85») — это форма кодирования двоичных данных при помощи текста, разработанная Полом Раттером (Paul E. Rutter) для библиотеки btoa. Благодаря тому, что для кодирования 4 байт данных используется 5 ASCII символов (обработанные данные на ¹⁄₄ больше оригинала, при использовании 8-битных ASCII символов), достигается большая эффективность, чем в случае uuencode или Base64, в которых каждые 3 байта кодируются 4 символами (увеличение на ¹⁄₃ при тех же условиях).

Главным образом применяется в форматах PostScript и Portable Document Format компании Adobe.

Основная идея

Основная потребность в кодировании данных текстом проистекает из необходимости передавать бинарные данные по существующим протоколам, предназначенным исключительно для передачи текста (например, e-mail). Такие протоколы могут гарантированно передавать только 7-битные значения (и при этом нужно избегать использования управляющих символов ASCII), а также могут требовать вставки символа конца строки для ограничения длины строк, к тому же допускают пробельные отступы. В итоге остается только 94 печатных символа, которые можно использовать.

4 байта могут содержать 2³² = 4 294 967 296 различных значений. 5 цифр в системе счисления с основанием 85 дают 85⁵ = 4 437 053 125 различных значения, чего вполне достаточно для однозначного представления 32-битных значений. Пять цифр в системе счисления с основанием 84 могут предоставить только 84⁵ = 4 182 119 424 значений. Следовательно 85 является минимальным основанием системы счисления, в которой 4 байта можно закодировать 5-ю цифрами, его и выбираем.

При кодировании разделяем поток данных на группы по 4 байта, и рассматриваем каждую из них, как 32-битное число, со старшим байтом в начале. Последовательным делением на 85 получаем 5 цифр 85-ричной системы счисления. Далее каждая цифра кодируется печатным символом ASCII и выводится в выходной поток, с сохранением порядка, от старшего разряда к младшему.

Кодирование цифры ASCII символами осуществляется путем увеличением на 33, то есть символами с кодами от 33 («!») до 117 («u»).

Поскольку нулевые значения встречаются не так уж и редко, то ради дополнительного сжатия сделано дополнительное исключение — нулевая четверка байтов кодируется единственным символом «z» вместо «!!!!!».

Группа символов, которые при раскодировании дают значение больше чем 2³² − 1 (кодируемое как «s8W-!») приводят к ошибке раскодировки, равно как и символ «z» внутри группы. Все пробельные отступы между символами игнорируются и могут вставляться произвольно для удобного форматирования.

Единственным недостатком Ascii85 является то, что в полученном тексте будут встречаться символы (такие как слеш и кавычки), которые имеют особые значения в языках программирования и текстовых протоколах.

btoa

Оригинальная программа btoa всегда кодировала полными группами (последняя дополнялась нулями) и добавляла перед полученным текстом строку «xbtoa Begin», а после — «xbtoa End», за которой следовал размер исходного файла (десятичный и шестнадцатеричный) и три 32-битных контрольных суммы. Раскодировщик использовал информацию о исходной длине, чтобы узнать сколько дополняющих нулей было вставлено.

В данной программе также поддерживалось специальное значение «z» для кодирования нулей (0x00000000), а также «y» — для группы их четырех пробелов (0x20202020).

Adobe

Adobe адаптировал кодирование btoa, внеся некоторые изменения, и дав имя Ascii85. В частности, был добавлен разделитель «~>» для обозначения конца закодированной строки и определения, где нужно обрезать раскодированную строку для получения верной длины. Делается это так: Если последний блок содержит меньше 4 байтов, то он перед кодированием дополняется нулевыми байтами, а после кодирования из последней пятерки убирается столько крайних символов, сколько нулей было добавлено.

При декодировании, последний блок дополняется до длинны 5 символом «u» (цифра 84), а после раскодировния столько же байт удаляется (см. пример ниже).

Замечание: Заполняющий символ выбран не случайно. В Base64 при перекодировании, биты просто перегруппировываются, не меняется ни их порядок ни значения (старшие биты исходной последовательности не влияют на младшие биты результата). При преобразовании в систему счисления с основанием 85 (85 не является степенью двойки) значения старших битов исходной последовательности влияют младшие биты в результате (аналогично и при обратном преобразовании). Дополнение минимальным значением (0) при кодировании и максимальным (85) при раскодировании обеспечивает сохранность старших битов.

В блоке текста Ascii85 в любом месте могут быть вставлены пробельные символы и переносы строк, в том числе и внутри пятерок букв. Они должны просто игнорироваться.

Спецификация от Adobe не содержит расширения «y» для четырех пробелов.

Пример

Например, исторический слоган Википедии,

Man is distinguished, not only by his reason, but by this singular passion from other animals, which is a lust of the mind, that by a perseverance of delight in the continued and indefatigable generation of knowledge, exceeds the short vehemence of any carnal pleasure.

будучи закодированным в Ascii85 выглядит следующим образом:

<~9jqo^BlbD-BleB1DJ+*+F(f,q/0JhKF<GL>Cj@.4Gp$d7F!,L7@<6@)/0JDEF<G%<+EV:2F!,
O<DJ+*.@<*K0@<6L(Df-\0Ec5e;DffZ(EZee.Bl.9pF"AGXBPCsi+DGm>@3BB/F*&OCAfu2/AKY
i(DIb:@FD,*)+C]U=@3BN#EcYf8ATD3s@q?d$AftVqCh[NqF<G:8+EV:.+Cf>-FD5W8ARlolDIa
l(DId<j@<?3r@:F%a+D58'ATD4$Bl@l3De:,-DJs`8ARoFb/0JMK@qB4^F!,R<AKZ&-DfTqBG%G
>uD.RTpAKYo'+CT/5+Cei#DII?(E,9)oF*2M7/c~>

Текст	M								a								n																...	s								u								r								e
ASCII	77								97								110								32								...	115								117								114								101
двоичное представление	0	1	0	0	1	1	0	1	0	1	1	0	0	0	0	1	0	1	1	0	1	1	1	0	0	0	1	0	0	0	0	0	...	0	1	1	1	0	0	1	1	0	1	1	1	0	1	0	1	0	1	1	1	0	0	1	0	0	1	1	0	0	1	0	1
десятичное представление	1 298 230 816 = 24×854 + 73×853 + 80×852 + 78×85 + 61																																...	1 937 076 837 = 37×854 + 9×853 + 17×852 + 44×85 + 22
85-ричное представление (+33)	24 (57)						73 (106)							80 (113)						78 (111)							61 (94)						...	37 (70)						9 (42)							17 (50)						44 (77)							22 (55)
ASCII	9						j							q						o							^						...	F						*							2						M							7

Так так последняя четверка не полная, мы должны добить ее нулями:

Текст	.								\0								\0								\0
ASCII	46								0								0								0
двоичное представление	0	0	1	0	1	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
десятичное представление	771 751 936 = 14×854 + 66×853 + 56×852 + 74×85 + 46
85-ричное представление (+33)	14 (47)						66 (99)							56 (89)						74 (107)							46 (79)
ASCII	/						c							Y						k							O

Мы добавили 3 байта при кодировании и должны убрать три последних символа 'YkO' из результата.

Раскодирование абсолютно симметрично, за исключением последней пятерки, которую мы добиваем символами 'u':

ASCII	/						c							u						u							u
85-ричное представление (+33)	14 (47)						66 (99)							84 (117)						84 (117)							84 (117)
десятичное представление	771 955 124 = 14×854 + 66×853 + 84×852 + 84×85 + 84
двоичное представление	0	0	1	0	1	1	1	0	0	0	0	0	0	0	1	1	0	0	0	1	1	0	0	1	1	0	1	1	0	1	0	0
ASCII	46								3								25								180
Текст	.								[ ETX ]								[ EM ]								не определено в ASCII

Так как мы добавили 3 символа 'u', мы должны изъять последние 3 байта из результата. В тоге мы получаем сообщение оригинальной длины.

В исходном примере не было четверки из нулевых байтов, по этому мы не увидели сокращенной записи 'z' в результате.

Совместимость

Кодирование Ascii85 совместимо и с 7 и 8-битными MIME, при этом сопровождается меньшими накладными расходами по объему, чем Base64.

Единственная потенциальная проблема состоит в том, что Ascii85 может содержать символы, которые обязательно должны экранироваться в языках разметки, таких как XML или SGML, например, одинарные и двойные кавычки, угловые скобки, амперсанд («'"<>&»).

RFC 1924

Опубликованный 1 апреля 1996, и, по-видимому, шуточный, информационный RFC 1924: «A Compact Representation of IPv6 Addresses» (компактное представление IPv6 адресов) предлагает кодировать IPv6 адреса как числа в системе счисления по основанию 85 (base-85, по аналогии с base-64). Это предложение отличается от приведенных выше схем тем, что во первых использует набор из других 85 ASCII символов, а во вторых обрабатывает всю группу из 128 бит как единое число, преобразуя его в 20 итоговых символов, а не группами по 32 бита. Также, не допускаются пробелы.

Предложенный набор символов, в порядке возрастания кодов: 0-9, A-Z, a-z и еще 23 символа !#$%&()*+-;<=>?@^_`{|}~. Наибольшее значение, помещающееся в 128 бит IPv6 адреса — 2¹²⁸−1 = 74×85¹⁹ + 53×85¹⁸ + 5×85¹⁷ + …, имеет вид =r54lj&NUUO~Hi%c2ym0.

Набор символов выбран так, чтобы исключить использование наиболее проблемных символов ("',./:[]\), но все также содержит символы, которые нужно экранировать в SGML протоколах, например в XML.

См. также

• Base64

Ссылки

• btoa и atob Исходные коды оригинальной програмы 1990
• PostScript Language Reference (Adobe) — см. ASCII85Encode Filter

• реализации кодирования и декодирования на разных языках программирования:
  • awk
  • C
  • C#
  • F#
  • Java (documentation)
  • Perl
  • Python
  • Another Python implementation
  • Mercurial’s RFC1924-based Python implementation (GPL)
  • Yet another RFC1924/ASCII85/IPv6 Base85 Python implementation (APLv2)