Po przeczytaniu wiki base64 ...
Próbuję dowiedzieć się, jak działa ta formuła:
Biorąc pod uwagę ciąg o długości n
, długość base64 będzie wynosić
Który jest : 4*Math.Ceiling(((double)s.Length/3)))
Wiem już, że długość base64 musi być taka, %4==0
aby dekoder wiedział, jaka była oryginalna długość tekstu.
Maksymalna liczba wypełnienia sekwencji może wynosić =
lub ==
.
wiki: Liczba bajtów wyjściowych na bajt wejściowy wynosi około 4/3 (33% narzut)
Pytanie:
Jak powyższe informacje są zgodne z długością wyjściową ?
4 * n / 3
daje nieusztywnioną długość.I zaokrąglij w górę do najbliższej wielokrotności 4 w celu wypełnienia, a ponieważ 4 to potęga 2, może używać bitowych operacji logicznych.
źródło
$(( ((4 * n / 3) + 3) & ~3 ))
4 * n / 3
już się nie powiedzien = 1
, jeden bajt jest kodowany przy użyciu dwóch znaków, a wynikiem jest wyraźnie jeden znak.Dla porównania, formuła długości kodera Base64 wygląda następująco:
Jak powiedziałeś, koder Base64 z podanymi
n
bajtami danych wygeneruje ciąg znaków4n/3
Base64. Innymi słowy, każde 3 bajty danych dadzą 4 znaki Base64. EDYCJA : komentarz poprawnie wskazuje, że moja poprzednia grafika nie uwzględniała wypełnienia; poprawna formuła toCeiling(4n/3)
.Artykuł w Wikipedii pokazuje dokładnie, jak łańcuch ASCII został
Man
zakodowany w łańcuchu Base64TWFu
w jego przykładzie. Łańcuch wejściowy 3 bajty, lub 24 bitów, w wielkości, a więc o wzorze prawidłowo przewiduje, że wyniki będą 4 bajty (32 bity) lub długi:TWFu
. Proces koduje każde 6 bitów danych na jeden z 64 znaków Base64, więc 24-bitowe wejście podzielone przez 6 daje w wyniku 4 znaki Base64.Pytasz w komentarzu, jaki
123456
byłby rozmiar kodowania . Mając na uwadze, że każdy znak tego ciągu ma rozmiar 1 bajtu lub 8 bitów (zakładając kodowanie ASCII / UTF8), kodujemy 6 bajtów lub 48 bitów danych. Zgodnie z równaniem oczekujemy, że długość wyjściowa będzie wynosić(6 bytes / 3 bytes) * 4 characters = 8 characters
.Wprowadzenie
123456
do kodera Base64 tworzyMTIzNDU2
8 znaków, tak jak oczekiwaliśmy.źródło
floor((3 * (length - padding)) / 4)
. Sprawdź następującą istotę .Liczby całkowite
Generalnie nie chcemy używać podwójnych, ponieważ nie chcemy używać operacji zmiennoprzecinkowych, błędów zaokrągleń itp. Po prostu nie są one potrzebne.
W tym celu warto pamiętać, jak wykonać podział sufitu:
ceil(x / y)
w podwójnych można zapisać jako(x + y - 1) / y
(unikając liczb ujemnych, ale uważaj na przepełnienie).Czytelny
Jeśli zależy Ci na czytelności, możesz oczywiście zaprogramować ją w ten sposób (na przykład w Javie, dla C możesz oczywiście użyć makr):
Podszewka
Watowany
Wiemy, że potrzebujemy jednocześnie 4 bloków znaków na każde 3 bajty (lub mniej). Zatem wzór wygląda następująco (dla x = n i y = 3):
lub połączone:
Twój kompilator zoptymalizuje plik
3 - 1
, więc zostaw to tak, aby zachować czytelność.Miękki
Mniej powszechny jest wariant bez wypełnienia, w tym celu pamiętamy, że każdy potrzebujemy znaku na każde 6 bitów, zaokrąglone w górę:
lub połączone:
możemy jednak jeszcze podzielić przez dwa (jeśli chcemy):
Nieczytelne
W przypadku, gdy nie ufasz swojemu kompilatorowi, który wykona za Ciebie ostateczne optymalizacje (lub jeśli chcesz zmylić kolegów):
Watowany
Miękki
Mamy więc dwa logiczne sposoby obliczania i nie potrzebujemy żadnych gałęzi, operacji bit-op lub modulo - chyba, że naprawdę tego chcemy.
Uwagi:
źródło
Myślę, że podane odpowiedzi pomijają sens pierwotnego pytania, czyli ile miejsca należy przydzielić, aby dopasować kodowanie base64 dla danego ciągu binarnego o długości n bajtów.
Odpowiedź to
(floor(n / 3) + 1) * 4 + 1
Obejmuje to dopełnienie i kończący znak null. Możesz nie potrzebować wywołania piętra, jeśli wykonujesz arytmetykę liczb całkowitych.
Uwzględniając dopełnienie, ciąg base64 wymaga czterech bajtów na każdy trzy-bajtowy fragment oryginalnego ciągu, w tym wszystkie częściowe fragmenty. Jeden lub dwa dodatkowe bajty na końcu ciągu będą nadal konwertowane na cztery bajty w ciągu base64 po dodaniu wypełnienia. O ile nie masz bardzo konkretnego zastosowania, najlepiej jest dodać dopełnienie, zwykle znak równości. Dodałem dodatkowy bajt dla znaku null w C, ponieważ ciągi ASCII bez tego są trochę niebezpieczne i trzeba by było oddzielnie przenosić długość łańcucha.
źródło
Oto funkcja obliczająca oryginalny rozmiar zakodowanego pliku Base 64 jako ciąg w KB:
źródło
Podczas gdy wszyscy inni debatują nad wzorami algebraicznymi, wolałbym po prostu użyć samego BASE64, aby mi powiedzieć:
525
710
Wygląda więc na to, że formuła 3 bajtów reprezentowanych przez 4 znaki base64 wydaje się poprawna.
źródło
(Próbując podać zwięzłe, ale pełne wyprowadzenie.)
Każdy bajt wejściowy ma 8 bitów, więc dla n bajtów wejściowych otrzymujemy:
Każde 6 bitów to bajt wyjściowy, więc:
To jest bez wypełnienia.
Z dopełnieniem zaokrąglamy to do wielokrotności czterech bajtów wyjściowych:
Zobacz Zagnieżdżone podziały (Wikipedia), aby zapoznać się z pierwszym odpowiednikiem.
Używając arytmetyki liczb całkowitych, ceil ( n / m ) można obliczyć jako ( n + m - 1) div m , stąd otrzymujemy:
Na przykład:
Wreszcie, w przypadku kodowania MIME Base64, potrzebne są dwa dodatkowe bajty (CR LF) na każde 76 bajtów wyjściowych, zaokrąglone w górę lub w dół, w zależności od tego, czy wymagany jest kończący znak nowej linii.
źródło
Wydaje mi się, że właściwą formułą powinno być:
źródło
Uważam, że to jest dokładna odpowiedź, jeśli n% 3 nie jest zerem, nie?
Wersja Mathematica:
baw się dobrze
żołnierz amerykański
źródło
Prosta implementacja w javascript
źródło
Wszystkim osobom, które mówią w C, spójrz na te dwa makra:
Zaczerpnięte stąd .
źródło
Nie widzę uproszczonej formuły w innych odpowiedziach. Logika jest omówiona, ale chciałem mieć najbardziej podstawową formę do mojego użytku osadzonego:
UWAGA: Obliczając niezmienianą liczbę zaokrąglamy w górę dzielenie liczb całkowitych, tj. Dodajemy dzielnik-1, który w tym przypadku wynosi +2
źródło
W oknach - chciałem oszacować rozmiar bufora o rozmiarze mime64, ale żadne precyzyjne formuły obliczeniowe nie działały dla mnie - w końcu otrzymałem przybliżony wzór taki:
Rozmiar alokacji ciągów Mine64 (przybliżony) = (((4 * ((rozmiar bufora binarnego) + 1)) / 3) + 1)
Więc ostatnie +1 - jest używane dla ascii-zero - ostatni znak musi być przydzielony do przechowywania zakończenia zerowego - ale dlaczego „binarny rozmiar bufora” to + 1 - podejrzewam, że jest jakiś znak kończący mime64? A może jest to jakiś problem z wyrównaniem.
źródło
Jeśli jest ktoś zainteresowany osiągnięciem rozwiązania @Pedro Silva w JS, właśnie przeportowałem do niego to samo rozwiązanie:
źródło