Czym jest Base91?
Base91 to sposób zapisu dowolnych bajtów wyłącznie drukowalnymi znakami ASCII — to samo zadanie, co Base64, ale mieszczący więcej bitów w każdym znaku. Zamiast dzielić wejście na grupy po 6 bitów i drukować jeden znak na grupę, zbiera bity, aż ma co najmniej 13, a następnie drukuje dwa znaki, które razem oznaczają wartość tych 13 (lub 14) bitów.
Dwa znaki z alfabetu 91 mogą oznaczać 91 × 91 = 8281 różnych wartości, a 213 = 8192, więc dwa znaki zawsze mają miejsce na 13 bitów — z 89 wartościami zapasu. Na tym polega cała sztuczka: 13 bitów na 2 znaki to 6,5 bita na znak, wobec 6 w Base64, i daje narzut około 23% zamiast 33%.
Wersja na 30 sekund: test zapisuje się jako fPNKd, a Hello, World! jako >OwJh>}AQ;r@@Y?F. Dekodowanie jest dokładnym odwróceniem i wymaga tego samego 91-znakowego alfabetu — inny alfabet da inne wyjście z tych samych bajtów.
Skąd biorą się 13 i 14 bitów
Para znaków może oznaczać 91 × 91 = 8281 wartości, czyli więcej niż 213 = 8192, ale mniej niż 214 = 16384. Para znaków zawsze może więc przenieść 13 bitów, a czasem 14. Koder najpierw próbuje 13 bitów: jeśli wartość 13-bitowa jest większa niż 88, drukuje ją jako dwa znaki; w przeciwnym razie pobiera czternasty bit i drukuje wynikową wartość 14-bitową.
Granica 88 nie jest przypadkowa. Największa wartość, jaką mogą nazwać dwa znaki, to 90 + 91 × 90 = 8280, a 8192 + 89 = 8281 już ją przekracza. Żadna 14-bitowa grupa nie może więc mieć dolnego 13-bitowego okna równego 89 lub więcej, co oznacza, że dekoder rozróżnia oba przypadki, patrząc wyłącznie na samą wartość:
| Co widzi dekoder | Zużyte bity | Dlaczego |
|---|
| wartość & 8191 wynosi od 89 do 8191 | 13 bitów | Wartości od 89 wzwyż mogą pochodzić tylko z gałęzi 13-bitowej, bo 14-bitowa grupa z dolnym 13-bitowym oknem tak wysokim musiałaby wynosić co najmniej 8281 — czego żadna para znaków nie może nazwać. |
| wartość & 8191 wynosi od 0 do 88 | 14 bitów | Koder przechodzi na 14 bitów tylko wtedy, gdy odczyt 13-bitowy wynosił 88 lub mniej, więc ta gałąź jest rozwiązaniem awaryjnym i niczym więcej. |
Wszystko, co zostaje na końcu — od 1 do 13 bitów — drukuje się jako jeden znak, a drugi znak dochodzi, gdy reszta rzeczywiście wymaga więcej niż 7 bitów. Dlatego długość zakodowanego wyniku rośnie co dwa znaki i czasem kończy się na nieparzystej liczbie.
Alfabet i trzy znaki, których nie ma
Drukowalne ASCII ma 94 znaki, od ! (0x21) do ~ (0x7E). Base91 używa 91 z nich, a trzy pominięte to myślnik -, apostrof ' i ukośnik wsteczny \. Litery, cyfry i prawie cała interpunkcja są w alfabecie dokładnie raz, w kolejności pokazanej w tabeli wyżej; 92.–94. drukowalny znak po prostu nie jest adresowalny.
Ponieważ alfabet ma stałą kolejność, znak dla danej wartości to wyszukanie w tabeli, a nie wzór. Dwie implementacje, które ustawiają alfabet w różnej kolejności, będą obie nazywać się „Base91” i nie będą mogły odczytać wyjścia drugiej, co jest najczęstszym źródłem mylących wyników. Ta strona drukuje swój alfabet, aby wyjście zawsze dało się prześledzić do niego.
Base91 obok innych kodowań drukowalnych
| Kodowanie | Bity na znak | Rozmiar względem wejścia | Uwagi |
|---|
| Base16 (hex) | 4 | 200% | Dwa znaki na bajt, łatwe do odczytania, bez alfabetu do sprawdzania. |
| Base32 | 5 | 160% | Bez rozróżniania wielkości liter i bezpieczny przy dyktowaniu, ale najbardziej rozrzutny z grupy. |
| Base58 | ~5,86 | ~137% | Wybrany dla adresów, a nie dla gęstości: unika znaków mylących. |
| Base64 | 6 | 133% | Domyślny wszędzie: 4 znaki na 3 bajty, a 6 nieużywanych bitów ostatniego znaku się marnuje. |
| Ascii85 / Base85 | 6,4 | 125% | 5 znaków na 4 bajty, bez tabeli odwzorowań, ale dzieli przez 85 — zobacz konwerter Ascii85. |
| Base91 | ~6,5 | ~123% | Najgęstszy z nich: 13 bitów na 2 znaki, kosztem grupy 14-bitowej tu i ówdzie. |
Procenty to asymptotyczny koszt każdego kodowania, zaokrąglony; zmierzone liczby znaków dla jednego prawdziwego wejścia 92-bajtowego znajdują się w tabeli wyżej na tej stronie. Base91 jest blisko najlepszego, co kodowanie może zrobić z drukowalnym ASCII: 7 bitów na znak wymagałoby 128 różnych znaków, a zakres drukowalny tego nie zapewnia.
Czym Base91 nie jest
- To nie standard. Nie ma RFC. Implementacja referencyjna to basE91 0.6.0 autorstwa Joachima Henkego, wydana na licencji BSD 3-clause; nazwy „Base91” używa się też dla alfabetów innych niż ten.
- To nie szyfrowanie. Każdy znak to prosta przebudowa bitów wejścia, a każdy, kto zna alfabet, odwróci ją jednym przebiegiem.
- Nie jest bezpieczny dla URL. Alfabet zawiera
#, %, &, /, ? i ", a wszystkie zmieniają znaczenie w URL, dlatego wyjście Base91 trzeba zakodować procentowo przed umieszczeniem w zapytaniu. - Nie jest bezpieczny dla HTML. Zawiera też
<, >, & i ", więc ciąg Base91 wstawiony do znaczników trzeba escapować narzędziem Konwerter encji HTML. - Nie ma stałej długości. Długość wyjścia zależy od wzorca bitów, a nie tylko od liczby bajtów, więc dwa wejścia tego samego rozmiaru mogą różnić się o jeden znak.
Pułapki, które naprawdę gryzą
- Alfabet na tej stronie jest referencyjny. Jeśli inne narzędzie daje inne wyjście dla tego samego wejścia, porównaj jego alfabet, zanim uzna się, że któraś strona jest zepsuta. Te 91 znaków musi występować w tej samej kolejności.
- Jeden błędny znak może zmienić cały koniec. Granice grup są ustalane przez wartości wcześniejsze, więc zmiana na początku ciągu przesuwa wszystko dalej, a koniec dekoduje się tylko z resztą bitów ostatniej grupy.
- Nieparzysta długość wyniku jest normalna. Nie oznacza, że ciąg został ucięty; ostatnia grupa drukuje jeden znak, gdy jej reszta mieści się w 7 bitach lub mniej.
- Opublikowany przykład może zawierać znak nowej linii, którego nie wpisano. Polecenie powłoki dodające koniec wiersza to najczęstszy powód, dla którego znana wartość Base91 jest o jeden znak dłuższa niż ten sam tekst daje tutaj:
echo "Hello, World!" przekazuje koderowi 14 bajtów i drukuje >OwJh>}AQ;r@@Y?FF, podczas gdy same 13 bajtów tekstu drukuje >OwJh>}AQ;r@@Y?F. Obie wartości są poprawne, dla różnej liczby bajtów, a liczba pod polem wyjścia pokazuje, z jaką liczbą bajtów mamy do czynienia. - Dekodowanie danych binarnych jako tekst nie zadziała. Jeśli zdekodowane bajty nie są poprawnym UTF-8, nie ma sensownego tekstu do pokazania, do tego służy tryb wyjścia szesnastkowego.
Krótkie odpowiedzi
„Dlaczego ta strona pokazuje wartość o jeden znak inną niż inne narzędzie Base91?”
Prawie zawsze inny alfabet. Drugą najczęstszą przyczyną jest narzędzie, które używa tylko gałęzi 13-bitowej i nigdy 14-bitowego rozwiązania awaryjnego; ten wariant jest krótszy w kodzie, ale daje inne wyjście niż używany tutaj algorytm referencyjny.
Istnieje też jeden dokładny przypadek, który można rozstrzygnąć przez zliczenie bajtów, i wyjaśnia on najczęściej cytowany przykład: końcowy znak nowej linii. Większość opublikowanych wektorów wytworzono poleceniem powłoki, a powłoka dodaje znak końca wiersza. 13 bajtów Hello, World! drukuje tutaj 16 znaków, a 14 bajtów Hello, World! z nową linią drukuje 17-znakowe >OwJh>}AQ;r@@Y?FF. Wklej którąkolwiek wartość do dekodowania: strona podaje liczbę bajtów, więc oba odczyty można odróżnić zamiast się o nie spierać. Przycisk Przykład wczytuje tę z dwóch wartości, która pasuje do używanego czytnika; podąża za przełącznikiem Koduj / Dekoduj i selektorem Wejście jest / Wyjście jako: czytnik tekstu dostaje wartość 16-znakową, czytnik szesnastkowy 17-znakową z końcowym bajtem 0A na wierzchu, a koder dostaje tekst do zakodowania zamiast ciągu Base91.
„Czy Base91 jest mniejszy niż Base64?”
Tak, o około 8% rozmiaru zakodowanego: 13 bitów na 2 znaki wobec 6 bitów na znak. Dla 92 bajtów tekstu Base64 drukuje 124 znaki, a Base91 drukuje 114.
„Czy mogę to zdekodować dekoderem Base64 albo odwrotnie?”
Nie. Alfabety pokrywają się w literach i cyfrach, więc dekoder Base64 zaakceptuje ciąg Base91 jako „poprawne” znaki i wyprodukuje ciche śmieci. Oba zgadzają się tylko co do kształtu schematu.
„Czy wynik kończy się dopełnieniem jak Base64?”
Nie. Base91 w ogóle nie ma znaku dopełnienia: pozostałe na końcu bity są drukowane jako ostatnia grupa, więc nic nie trzeba dodawać ani usuwać.
„Skąd wiem, że wynik na tej stronie jest poprawny?”
Naciśnij Samotest 0–64 bajty. Koduje i dekoduje 130 wzorców bajtów obejmujących każdą długość, przy której zmienia się podział na 13 i 14 bitów, i porównuje bajty, które wracają, z bajtami, które weszły. Wektory przycisku Przykład są dodatkowo sprawdzane krzyżowo z drugą implementacją przygotowaną na potrzeby narzędzi testowych tej witryny.
Standardy i autorstwo
Ta strona implementuje algorytm referencyjnej implementacji basE91 (wersja 0.6.0) autorstwa Joachima Henkego, rozpowszechnianej na licencji BSD 3-clause, z alfabetem pokazanym wyżej. Dekodowanie akceptuje i ignoruje białe znaki, tak jak narzędzie referencyjne.
Tekst strony został napisany dla tej witryny; algorytm nie został skopiowany skądkolwiek. Wartości przycisku Przykład to jedyny przykład dołączony do pakietu referencyjnego (oznaczony „przykład referencyjny”) oraz wartości wytworzone przez drugą, niezależną implementację przechowywaną w narzędziach testowych tej witryny (oznaczone „weryfikacja krzyżowa”).
