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 байта можно закодировать пятью цифрами, потому оно и выбрано.

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

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

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

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

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

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

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

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

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

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

В блоке текста 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 для записи IPv6 адресов

[править | править код]

Опубликованный 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.

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