842 (compression algorithm)
842, 8-4-2, or EFT is a data compression algorithm. It is a variation on the Lempel-Ziv compression algorithm with a limited dictionary length. With typical data, 842 gives 80 to 90 percent of the compression of LZ77 with much faster throughput and less memory use.[1] Hardware implementations also provide minimal use of energy and minimal chip area.
842 compression can be used for virtual memory compression, for databases — especially column-oriented stores, and when streaming input-output — for example to do backups or to write to log files.
IBM have added hardware accelerators and instructions for 842 compression to their POWER processors from POWER 7+ onward.[2]
Algorithm
The algorithm operates on blocks of 8 bytes with sub-phrases of 8, 4 and 2 bytes. A hash of each phrase is used to look up a hash table with offsets to a sliding window buffer of past encoded data. Matches can be replaced by the offset, so the result for each block can be some mixture of matched data and new literal data.[3][1][4]
References
- ^ a b Plauth, Max; Polze, Andreas. "Towards Improving Data Transfer Efficiencyfor Accelerators using Hardware Compression".
- ^ "POWER NX842 Compression for Db2" (PDF). IBM. Retrieved 2021-07-13.
- ^ Franaszek, Peter A; Lastras-Montaño, Luis A; Peng, Song; Robinson, John T. "Data Compression with Restricted Parsings". IBM Research. IBM. Retrieved 2021-07-13.
- ^ Blaner, B.; Abali, B.; Bass, B. M.; Chari, S.; Kalla, R.; Kunkel, S.; Lauricella, K.; Leavens, R.; Reilly, J. J.; Sandon, P. A. (November 2013). "IBM POWER7+ processor on-chip accelerators for cryptography and active memory expansion". IBM Journal of Research and Development. 57 (6): 3:1–3:16. doi:10.1147/JRD.2013.2280090. Retrieved 2021-07-13.