Finite State Entropy Library

The finitestateentropy library provides two high-speed entropy coding algorithms designed for modern CPU architectures:

1. Huff0: A Huffman codec optimized for modern CPUs. It utilizes Out-of-Order (OoO) operations across multiple ALUs to achieve extremely high compression and decompression speeds. Note that Huffman coding is subject to the "1 bit per symbol" limit, which may reduce efficiency on highly squeezed distributions.

2. FSE (Finite State Entropy): An entropy encoder based on ANS (Asymmetric Numeral Systems) theory. It provides compression accuracy close to the Shannon limit (similar to Arithmetic coding) while maintaining much higher speeds than traditional arithmetic coders. Unlike Huffman, FSE is not limited by the 1 bit per symbol constraint.

The library is composed of several layers of files. To use the library, you must include the Compulsory files which provide the foundation for all codecs:

• error_public.h: Contains the error list as an enum.
• error_private.h: Handles error management.
• mem.h: Provides low-level memory access routines.
• bitstream.h: Provides the generic read/write bitstream common to all entropy codecs.
• entropy_common.c: Contains common functions required for both compression and decompression.

Finite State Entropy is the base codec. It implements a tANS variant that provides performance similar to arithmetic coding but with significantly higher speed. Compression and decompression can be compiled independently.

Required files:

• fse.h: The public interface.
• fse_compress.c: The compression implementation.
• fse_decompress.c: The decompression implementation.

When choosing between the two codecs, consider the trade-off between speed and compression accuracy:

• Use Huff0 when raw throughput is the priority. It offers significantly higher compression and decompression speeds (e.g., up to 600 MB/s compression and 1350 MB/s decompression in benchmarks) but may lose efficiency on highly squeezed distributions due to the 1 bit per symbol limit.
• Use FSE when you need high compression accuracy. FSE remains close to the Shannon limit in all circumstances, making it more efficient for distributions where Huffman's limitations become apparent, though it typically runs slower than Huff0.

This codec is used when you need to encode alphabets larger than 256 symbols, as it uses 2 bytes per symbol.

Note: This codec requires the base FSE codec to compile properly. Unlike the base FSE, compression and decompression are merged into the same file.

Required files:

• fseU16.h: The public interface.
• fseU16.c: The implementation (contains both compression and decompression).

This is a fast Huffman codec implementation.

Note: It requires the base FSE codec to compress its headers. Compression and decompression can be compiled independently.

Required files:

• huf.h: The public interface.
• huf_compress.c: The compression implementation.
• huf_decompress.c: The decompression implementation.