HOME

TheInfoList



OR:

LZFSE (Lempel–Ziv Finite State Entropy) is an
open source Open source is source code that is made freely available for possible modification and redistribution. Products include permission to use the source code, design documents, or content of the product. The open-source model is a decentralized sof ...
lossless data compression Lossless compression is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistic ...
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
created by
Apple Inc. Apple Inc. is an American multinational technology company headquartered in Cupertino, California, United States. Apple is the largest technology company by revenue (totaling in 2021) and, as of June 2022, is the world's biggest company b ...
It was released with a simpler algorithm called LZVN.


Overview

The name is an acronym for
Lempel–Ziv LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as LZ1 and LZ2 respectively. These two algorithms form the basis for many variations includin ...
and finite-state entropy (implementation of asymmetric numeral systems). LZFSE was introduced by Apple at its Worldwide Developer Conference 2015. It shipped with that year's
iOS 9 iOS 9 is the ninth major release of the iOS mobile operating system developed by Apple Inc., being the successor to iOS 8. It was announced at the company's Worldwide Developers Conference on June 8, 2015, and was released on September 16, 20 ...
and OS X 10.11 releases. Apple claims that LZFSE compresses with a ratio comparable to that of
zlib zlib ( or "zeta-lib", ) is a software library used for data compression. zlib was written by Jean-loup Gailly and Mark Adler and is an abstraction of the DEFLATE compression algorithm used in their gzip file compression program. zlib is also ...
( DEFLATE) and decompresses two to three times faster while using fewer resources, therefore offering higher energy efficiency than zlib. It was aimed for scenarios where decompression speed and rate should be prioritised equally. Part of this energy efficiency was achieved by optimising the algorithm for modern micro-architectures, specifically focusing on
arm64 AArch64 or ARM64 is the 64-bit extension of the ARM architecture family. It was first introduced with the Armv8-A architecture. Arm releases a new extension every year. ARMv8.x and ARMv9.x extensions and features Announced in October 2011, AR ...
. Third-party benchmarking confirms that LZFSE decompresses faster than zlib, but also suggests that many other modern compression algorithms may have more favorable compression algorithm performance characteristics such as density, compression speed and decompression speed by a significant margin. According to the Squash Benchmark, LZFSE is similar in speed to ZSTD (level 6), but has a slightly worse ratio. LZVN is similar in speed to LZ4 level 4, with a slightly worse ratio as well. Neither LZFSE nor LZVN is tunable at runtime, although a few constants can be tweaked at compile time for the usual speed-ratio trade-off.


Implementation

A reference C
library A library is a collection of materials, books or media that are accessible for use and not just for display purposes. A library provides physical (hard copies) or digital access (soft copies) materials, and may be a physical location or a vir ...
written by Eric Bainville was made available under the
3-clause BSD License BSD licenses are a family of permissive free software licenses, imposing minimal restrictions on the use and distribution of covered software. This is in contrast to copyleft licenses, which have share-alike requirements. The original BSD lice ...
after WWDC 2016. It includes an executable to compress and decompress LZFSE streams as well. There are no plans to expose an LZVN API. Apple's LZFSE implementation uses a simpler algorithm called LZVN when the input is smaller than (4096 bytes). This is a LZSS-type algorithm without entropy encoding but with three widths of REP (L,M,D) packets. In the open source reference implementation, Apple explains that LZFSE does not perform as well for small sizes, so LZVN is used instead. This algorithm in libfastCompression.a was discovered earlier as the default kernelcache compression method in Mac OS X Yosemite Developer Preview 1 (2014), replacing the legacy compression from Haruhiko Okumura.


Usage

AppleFSCompression.framework (AFSC), the mechanism for quasi-transparent compression in
HFS Plus HFS Plus or HFS+ (also known as Mac OS Extended or HFS Extended) is a journaling file system developed by Apple Inc. It replaced the Hierarchical File System (HFS) as the primary file system of Apple computers with the 1998 release of Mac OS 8 ...
and
Apple File System Apple File System (APFS) is a proprietary file system developed and deployed by Apple Inc. for macOS Sierra (10.12.4) and later, iOS 10.3 and later, tvOS 10.2 and later, watchOS 3.2 and later, and all versions of iPadOS. It aims to fix co ...
, supports LZFSE and LZVN since OS X 10.9. Apple's
Disk Images A disk image, in computing, is a computer file containing the contents and structure of a disk volume or of an entire data storage device, such as a hard disk drive, tape drive, floppy disk, optical disc, or USB flash drive. A disk image is usua ...
framework has offered an LZFSE-based encoding called since Mac OS X 10.11, accessible via and some third-party image utilities.


See also

*
Zstandard Zstandard, commonly known by the name of its reference implementation zstd, is a lossless data compression algorithm developed by Yann Collet at Facebook. ''Zstd'' is the reference implementation in C. Version 1 of this implementation was r ...
– another combination of LZ77 and FSE, by Yann Collet, the FSE author * LZ4 compression algorithm – a fast member of the LZ77 family, also available on Apple platforms


References


External links

*
Finite State Entropy by Yann Collet (Cyan4973)
the source of the FSE implementation in LZFSE
Discussion on Encode.su
from which the maintainer Eric Bainville has taken suggestions {{Compression Methods Lossless compression algorithms Free computer libraries