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 байта могут содержать 232 = 4 294 967 296 различных значений. 5 цифр в системе счисления с основанием 85 дают 855 = 4 437 053 125 различных значения, чего вполне достаточно для однозначного представления 32-битных значений. Пять цифр в системе счисления с основанием 84 могут предоставить только 845 = 4 182 119 424 значений. Следовательно 85 является минимальным основанием системы счисления, в которой 4 байта можно закодировать 5-ю цифрами, его и выбираем.

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

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

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

Группа символов, которые при раскодировании дают значение больше чем 232 − 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 адреса — 2128−1 = 74×8519 + 53×8518 + 5×8517 + …, имеет вид =r54lj&NUUO~Hi%c2ym0.

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

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]