Wikipedia

Base85

kodowanie transportowe

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 edytuj

Strumień danych dzielony jest na bloki podlegające transformacji. W dziedzinie danych binarnych rozmiar bloku to cztery bajty   Po stronie ASCII odpowiada im pięć znaków   Oba zestawy łączy następująca relacja[2]:

 

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

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

 [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 edytuj

  • Rozmiar danych binarnych do zakodowanych pozostaje w stosunku  [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  [8], natomiast base64 zamienia 24 bity na 4 znaki[9] (stosunek   czyli wzrost objętości o 33%).
  • Podstawa o wartości   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 edytuj

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

btoa edytuj

Program btoa w systemie Unix przydziela cyfrom kolejne kody ASCII począwszy od znaku ! dla cyfry o wartości   i kończywszy na znaku u dla cyfry o wartości  [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 edytuj

Implementacja Adobe Inc. na potrzeby języka PostScript wykorzystuje zestaw znaków od ! do u dla cyfr od   do   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 edytuj

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 edytuj

Primaaprilisowa specyfikacja z propozycją zwartego zapisu adresów w sieci IPv6 zaleca następującą kolejność znaków dla cyfr o podstawie  : 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 edytuj

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ę   i na podobieństwo z programem btoa grupę czterech bajtów o wartości zero. Cyfra o wartości   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   Umożliwia to przypisanie ostatnim cyfrom kodowanym przez _ drugiej funkcji oznaczającej wyrównanie długości bloku[20].

Zestawienie znaków do kodowania edytuj

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 # ~ _
cztery zera z z — — z[19]
cztery spacje y — — — —
koniec x ~> — — —

Uwagi edytuj

  1. ↑   natomiast   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   Ostatnia dodana cyfra wprowadza błąd o wartości mniejszej niż nieużywany bajt   dwie dodane cyfry mniejszy niż dwa nieużywane bajty   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. ↑   to jest mniej niż   – w systemie o podstawie   do jej zapisania potrzeba 6 cyfr:  

Przypisy edytuj

  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 C Hamano, [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 edytuj

Linki zewnętrzne edytuj

  • John D. Cook, Base85, Ascii85, and Z85, [w:] John D. Cook Consulting [online], 5 marca 2019 [dostęp 2019-08-04] (ang.).
Źródło: „https://pl.wikipedia.org/w/index.php?title=Base85&oldid=67457722”