842 (algorytm kompresji)

842 , 8-4-2 lub EFT to algorytm kompresji danych . Jest to wariacja na temat Lempel-Ziv z ograniczoną długością słownika. W przypadku typowych danych 842 zapewnia 80 do 90 procent kompresji LZ77 przy znacznie większej przepustowości i mniejszym zużyciu pamięci. Implementacje sprzętowe zapewniają również minimalne zużycie energii i minimalną powierzchnię chipa.

Kompresja 842 może być używana do kompresji pamięci wirtualnej , do baz danych — zwłaszcza magazynów zorientowanych na kolumny , oraz do strumieniowego przesyłania danych wejściowych i wyjściowych — na przykład do tworzenia kopii zapasowych lub zapisywania w plikach dziennika .

Algorytm

Algorytm operuje na blokach po 8 bajtów z podfrazami po 8, 4 i 2 bajty. Skrót każdej frazy jest używany do wyszukiwania tabeli skrótów z przesunięciami do bufora przesuwanego okna z wcześniej zakodowanymi danymi. Dopasowania można zastąpić przesunięciem, więc wynikiem dla każdego bloku może być pewna mieszanka dopasowanych danych i nowych danych literałowych.

Implementacje

IBM dodał akceleratory sprzętowe i instrukcje dotyczące kompresji 842 do swoich procesorów Power począwszy od POWER7+ . Ponadto POWER9 i Power10 dodały akcelerację sprzętową dla algorytmu Deflate RFC 1951 , który jest używany przez zlib i gzip .

Sterownik urządzenia do wspomaganej sprzętowo kompresji 842 na procesorze POWER został dodany do jądra Linuksa w 2011 roku. Niedawno Linux może wrócić do implementacji programowej, która oczywiście jest znacznie wolniejsza. zram , moduł jądra Linuksa dla skompresowanych napędów RAM , można skonfigurować tak, aby używał 842.

Badacze zaimplementowali 842 przy użyciu procesorów graficznych i odkryli około 30-krotnie szybszą dekompresję przy użyciu dedykowanych procesorów graficznych. Biblioteka open source zapewnia 842 dla CUDA i OpenCL . Implementacja FPGA razy lepszą przepustowość niż implementacja programowa.