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
[править | править код]Оригинальная программа btoa всегда кодировала полными группами (последняя дополнялась нулями) и добавляла перед полученным текстом строку «xbtoa Begin», а после — «xbtoa End», за которой следовал размер исходного файла (десятичный и шестнадцатеричный) и три 32-битных контрольных суммы. Раскодировщик использовал информацию об исходной длине, чтобы узнать, сколько дополняющих нулей было вставлено.
В данной программе также поддерживалось специальное значение «z» для кодирования нулей (0x00000000), а также «y» — для группы из четырех пробелов (0x20202020).
Adobe
[править | править код]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.
См. также
[править | править код]Ссылки
[править | править код]- btoa и atob Исходные коды оригинальной программы 1990
- PostScript Language Reference (Adobe) — см. ASCII85Encode Filter
- реализации кодирования и декодирования на разных языках программирования: