Base85

Base85 (inne nazwy Ascii85, Z85) – rodzaj kodowania transportowego umożliwiającego przekazywanie binarnych danych w środowisku, w którym dopuszczalne jest używanie jedynie znaków ASCII[1].

Opis działania

Strumień danych dzielony jest na bloki podlegające transformacji. W dziedzinie danych binarnych rozmiar bloku to cztery bajty ( b 1   b 2   b 3   b 4 ) . {\displaystyle (b_{1}\ b_{2}\ b_{3}\ b_{4}).} Po stronie ASCII odpowiada im pięć znaków ( c 1   c 2   c 3   c 4   c 5 ) . {\displaystyle (c_{1}\ c_{2}\ c_{3}\ c_{4}\ c_{5}).} Oba zestawy łączy następująca relacja[2]:

b 1 × 256 3 + b 2 × 256 2 + b 3 × 256 + b 4 = c 1 × 85 4 + c 2 × 85 3 + c 3 × 85 2 + c 4 × 85 + c 5 . {\displaystyle b_{1}\times 256^{3}+b_{2}\times 256^{2}+b_{3}\times 256+b_{4}=c_{1}\times 85^{4}+c_{2}\times 85^{3}+c_{3}\times 85^{2}+c_{4}\times 85+c_{5}.}

Proces konwersji wykorzystuje pozycyjny system liczbowy o podstawie 85 {\displaystyle 85} do reprezentacji liczb zapisanych na 32 bitach[3]. Liczby trzydziestodwubitowe można traktować jak czterocyfrowe w systemie o podstawie 256 {\displaystyle 256} [4].

Proces translacji z dziedziny binarnej jest jednoznaczny dzięki relacji[3]:

85 5 > 2 32 {\displaystyle 85^{5}>2^{32}} [a].

ASCII zawiera 95 znaków drukowalnych (wliczając w to odstęp). Do reprezentacji cyfr wykorzystuje się z niego podzbiór 85 znaków[5].

Podstawowa funkcja konwertująca wymaga na wejściu liczb trzydziestodwubitowych. Oznacza to, że strumień danych binarnych powinien mieć całkowitą liczbę bajtów podzielną przez cztery. Sposób obsługi przypadków nie spełniających tego warunku zależy od implementacji. Jednym z rozwiązań jest dodanie brakujących bajtów o wartości zero do ostatniego bloku[3] i skrócenie wyniku o tyle cyfr ile bajtów zostało dodanych[2][b].

Własności

  • Rozmiar danych binarnych do zakodowanych pozostaje w stosunku 4 : 5 {\displaystyle 4:5} [6], czyli kodowanie zwiększa objętość o 25%[7]. Daje to przewagę nad alternatywnym kodowaniem 7-bitowym. Na przykład base16 zwiększa rozmiar w stosunku 1 : 2 {\displaystyle 1:2} [8], natomiast base64 zamienia 24 bity na 4 znaki[9] (stosunek 3 : 4 , {\displaystyle 3:4,} czyli wzrost objętości o 33%).
  • Podstawa o wartości 85 {\displaystyle 85} jest wielkością minimalną aby umożliwić prezentację każdej liczby trzydziestodwubitowej za pomocą pięciu cyfr[c]. Możliwe jest użycie wszystkich 94 znaków ASCII, nie zmienia to jednak minimalnej liczby cyfr potrzebnej do zakodowania informacji[10]. Stosowanie minimalnej bazy pozwala na użycie pozostałych znaków do innych celów[10].
  • Algorytmu nie można poddać optymalizacji polegającej na zdefiniowaniu predefiniowanych tablic mapujących wybrane grupy bitów na odpowiadające im znaki, co jest na przykład osiągalne dla base64[11].

Warianty

Różnice między istniejącymi wariantami polegają głównie na odpowiednim skojarzeniu znaków z wartościami cyfr w systemie o podstawie 85. {\displaystyle 85.}

btoa

Program btoa w systemie Unix przydziela cyfrom kolejne kody ASCII począwszy od znaku ! dla cyfry o wartości 0 {\displaystyle 0} i kończywszy na znaku u dla cyfry o wartości 84 {\displaystyle 84} [3]. Znak x oznacza koniec zakodowanych danych, z jest skrótem oznaczającym cztery bajty o wartości zero[3]. Nowsza wersja programu dodała również znak y, który oznacza cztery bajty o wartości 32 (cztery spacje)[7].

PostScript

Implementacja Adobe Inc. na potrzeby języka PostScript wykorzystuje zestaw znaków od ! do u dla cyfr od 0 {\displaystyle 0} do 84 {\displaystyle 84} oraz stosuje skrót z na oznaczenie czterech bajtów o wartości zero. Symbolem końca danych jest sekwencja ~>[2]. Kodowanie to jest określane nazwą ASCII85[12].

Z85

Standard umożliwiający łatwe użycie kodowania bezpośrednio w kodzie źródłowym stosuje następującą kolejność znaków 0–9, a–z, A–Z, . - : + = ^ ! / * ? & < > ( ) [ ] { } @ % $ #[13]. Można go używać w pojedynczych lub podwójnych cudzysłowach oraz przekazywać w linii poleceń. Umieszczenie znaku 0 jako reprezentacji cyfry 0 ułatwia naoczne wyszukiwanie zer binarnych[13].

RFC 1924

Primaaprilisowa specyfikacja z propozycją zwartego zapisu adresów w sieci IPv6 zaleca następującą kolejność znaków dla cyfr o podstawie 85 {\displaystyle 85} : 0–9, A–Z, a–z, ! # $ % & ( ) * + - ; < = > ? @ ^ _ ` { | } ~[10].

Wykluczenie ' i " upraszcza cytowanie, a brak , i . umożliwia tworzenie list i zapis w zdaniu. Znaki / : [ ] mają już zarezerwowane znaczenie w CIDR i IPv6 stąd również nie są używane w kodowaniu. Natomiast znak \ mógłby powodować problemy w niektórych środowiskach, gdyż jest często używany do podawania sekwencji specjalnych[14].

Dodatkową różnicą względem pozostałych wariantów jest brak dzielenia danych na czterobajtowe bloki. Specyfikacja omawia kodowanie w konteście adresów IPv6, które mają rozmiar 128 bitów i traktowane są w całości jako liczby całkowite w celu przekształcenia ich na zakodowaną 20 znakową postać[14]. W ogólnym przypadku taki zapis adresu jest znacząco krótszy niż format standardowy lub skompresowany[15].

Zestaw znaków z tej specyfikacji używany jest przez system kontroli wersji git do generowania łat z danych binarnych[16][17].

XML

Nie ma oficjalnego standardu dla efektywnego kodowania w dokumentach XML. Paul Kwiatkowski zaproponował następujący zestaw: 0–9, A–Z, a–y, ! # $ ( ) * + , - . / : ; = ? @ ^ ` { | } ~ z _[5]. Jednak pozostał on jedynie w fazie propozycji jako INTERNET-DRAFT.

Zestaw unika znaków < > & ' " %, które muszą być zamieniane na sekwencje specjalne w niektórych przypadkach w kodzie XML[18]. Ponadto wykluczone są \ [ ], które również mogłyby stanowić problemy w innych środowiskach[18].

Znak z ma podwójną funkcję. Reprezentuje cyfrę 83 {\displaystyle 83} i na podobieństwo z programem btoa grupę czterech bajtów o wartości zero. Cyfra o wartości 83 {\displaystyle 83} nigdy nie wystąpi na pierwszej pozycji, a to umożliwia jej równoległe zastosowanie do tego celu[19].

Najmniej znacząca cyfra jest kodowana w systemie liczbowym o podstawie 84. {\displaystyle 84.} Umożliwia to przypisanie ostatnim cyfrom kodowanym przez _ drugiej funkcji oznaczającej wyrównanie długości bloku[20].

Zestawienie znaków do kodowania

Wartość btoa[3] Ascii85[2] Z85[13] RFC 1924[10] XML[5]
0 ! ! 0 0 0
1 " " 1 1 1
2 # # 2 2 2
3 $ $ 3 3 3
4 % % 4 4 4
5 & & 5 5 5
6 ' ' 6 6 6
7 ( ( 7 7 7
8 ) ) 8 8 8
9 * * 9 9 9
10 + + a A A
11 , , b B B
12 - - c C C
13 . . d D D
14 / / e E E
15 0 0 f F F
16 1 1 g G G
17 2 2 h H H
18 3 3 i I I
19 4 4 j J J
20 5 5 k K K
21 6 6 l L L
22 7 7 m M M
23 8 8 n N N
24 9 9 o O O
25 : : p P P
26 ; ; q Q Q
27 < < r R R
28 = = s S S
29 > > t T T
30 ? ? u U U
31 @ @ v V V
32 A A w W W
33 B B x X X
34 C C y Y Y
35 D D z Z Z
36 E E A a a
37 F F B b b
38 G G C c c
39 H H D d d
40 I I E e e
41 J J F f f
42 K K G g g
43 L L H h h
44 M M I i i
45 N N J j j
46 O O K k k
47 P P L l l
48 Q Q M m m
49 R R N n n
50 S S O o o
51 T T P p p
52 U U Q q q
53 V V R r r
54 W W S s s
55 X X T t t
56 Y Y U u u
57 Z Z V v v
58 [ [ W w w
59 \ \ X x x
60 ] ] Y y y
61 ^ ^ Z z !
62 _ _ . ! #
63 ` ` - # $
64 a a : $ (
65 b b + % )
66 c c = & *
67 d d ^ ( +
68 e e ! ) ,
69 f f / * -
70 g g * + .
71 h h ? - /
72 i i & ; :
73 j j < < ;
74 k k > = =
75 l l ( > ?
76 m m ) ? @
77 n n [ @ ^
78 o o ] ^ `
79 p p { _ {
80 q q } ` |
81 r r @ { }
82 s s % | ~
83 t t $ } z
84 u u # ~ _
85 cztery zera z z — — z[19]
86 cztery spacje y — — — —
87 koniec x ~> — — —

Uwagi

  1. ↑ 85 5 = 4 437 053 125 , {\displaystyle 85^{5}=4\,437\,053\,125,} natomiast 2 32 = 4 294 967 296 {\displaystyle 2^{32}=4\,294\,967\,296} q.e.d.
  2. ↑ Jeśli zerowe bajty są dodawane na pozycjach mniej znaczących proces dekodowania wymaga „zrekonstruowania” bloku do pełnej pięciocyfrowej postaci przez uzupełnienie znakami cyfry o wartości 84. {\displaystyle 84.} Ostatnia dodana cyfra wprowadza błąd o wartości mniejszej niż nieużywany bajt ( 84 < 255 ) , {\displaystyle (84<255),} dwie dodane cyfry mniejszy niż dwa nieużywane bajty ( 84 2 + 84 < 255 2 + 255 ) , {\displaystyle (84^{2}+84<255^{2}+255),} oraz podobnie dla trzech cyfr. Skoro podczas kodowania były one wyzerowane, nie nastąpi przepełnienie tego obszaru, a pozwoli on odzyskać prawidłową wartość binarną cyfr znaczących.
  3. ↑ 84 5 = 4 182 119 424 {\displaystyle 84^{5}=4\,182\,119\,424} to jest mniej niż 2 32 = 4 294 967 296 {\displaystyle 2^{32}=4\,294\,967\,296} – w systemie o podstawie 84 {\displaystyle 84} do jej zapisania potrzeba 6 cyfr: 1 × 84 5 + 2 × 84 4 + 22 × 84 3 + 33 × 84 2 + 15 × 84 1 + 4 × 84 0 . {\displaystyle \mathbf {1} \times 84^{5}+\mathbf {2} \times 84^{4}+\mathbf {22} \times 84^{3}+\mathbf {33} \times 84^{2}+\mathbf {15} \times 84^{1}+\mathbf {4} \times 84^{0}.}

Przypisy

  1. ↑ Technical Note #5603 ↓, s. 17.
  2. ↑ a b c d PDF Manual ↓, s. 45.
  3. ↑ a b c d e f Rutter i Orost ↓.
  4. ↑ Salomon 2007 ↓, s. 929.
  5. ↑ a b c Kwiatkowski 2004 ↓, s. 2.
  6. ↑ Technical Note #5115 ↓, s. 7.
  7. ↑ a b Rutter, Orost i Parmark ↓.
  8. ↑ PDF Manual ↓, s. 44.
  9. ↑ RFC 4648 ↓, s. 5.
  10. ↑ a b c d RFC 1924 ↓, s. 3.
  11. ↑ He i in. 2010 ↓, s. 3.
  12. ↑ Technical Note #5603 ↓, s. 11.
  13. ↑ a b c Hintjens ↓.
  14. ↑ a b RFC 1924 ↓, s. 4.
  15. ↑ Loshin 2004 ↓, s. 145.
  16. ↑ Junio CJ.C. Hamano Junio CJ.C., [PATCH] binary patch [online], 5 maja 2006 [dostęp 2019-09-24]  (ang.).
  17. ↑ [kod źródłowy base85.c w programie git] [online], github.com [dostęp 2019-09-24] .
  18. ↑ a b Kwiatkowski 2004 ↓, s. 3.
  19. ↑ a b Kwiatkowski 2004 ↓, s. 5.
  20. ↑ Kwiatkowski 2004 ↓, s. 4.

Bibliografia

  • R.R. Elz R.R., A Compact Representation of IPv6 Addresses, RFC 1924, IETF, 1 kwietnia 1996, DOI: 10.17487/RFC1924, ISSN 2070-1721, OCLC 943595667  (ang.).
  • DakeD. He DakeD. i inni, A Proposal of Substitute for Base85/64 – Base91, [w:] CCCT SUMMER 2010 [online], 2010 [dostęp 2019-08-05]  (ang.).
  • PieterP. Hintjens PieterP., 32/Z85 · ZeroMQ RFC [online] [dostęp 2019-08-04]  (ang.).
  • S.S. Josefsson S.S., The Base16, Base32, and Base64 Data Encodings, RFC 4648, IETF, październik 2006, DOI: 10.17487/RFC4648, ISSN 2070-1721, OCLC 943595667  (ang.).
  • PaulP. Kwiatkowski PaulP., A Base-85 Encoding Suitable for XML., [w:] INTERNET-DRAFT [online], maj 2004 [dostęp 2019-08-03]  (ang.).
  • PeterP. Loshin PeterP., IPv6: Theory, Protocol, and Practice, Second Edition, Elsevier, 2004, ISBN 1-55860-810-9 .
  • PaulP. Rutter PaulP., JoeJ. Orost JoeJ., [kod źródłowy btoa, wersja 4.0] [online] [dostęp 2019-08-03]  (ang.).
  • P.P. Rutter P.P., J.J. Orost J.J., S.S. Parmark S.S., [kod źródłowy btoa, wersja 5.2] [online] [dostęp 2019-08-03]  (ang.).
  • DavidD. Salomon DavidD., Data Compression. The complete reference, Fouth Edition, London: Springer, 2007, ISBN 978-1-84628-602-5 .
  • Portable Document Format. Reference Manual. Version 1.3, Adobe Systems Incorporated, 11 marca 1999 [dostęp 2019-08-03]  (ang.).
  • Supporting Data Compression in PostScript Level 2 and the filter Operator. Technical Note #5115, Adobe Systems Incorporated, 31 marca 1992 [dostęp 2019-08-03]  (ang.).
  • Filters and Reusable Streams. Technical Note #5603, Adobe Systems Incorporated, 9 października 1997 [dostęp 2019-08-03]  (ang.).

Linki zewnętrzne

  • John D.J.D. Cook John D.J.D., Base85, Ascii85, and Z85, [w:] John D. Cook Consulting [online], 5 marca 2019 [dostęp 2019-08-04]  (ang.).