pombredanne/finitestateentropy

New breed of entropy coder

Finite State Entropy coder

FSE is a new kind of Entropy encoder, based on ANS theory, from Jarek Duda.

It is designed to compete with Huffman encoder and Arithmetic ones.

While huffman is fast but can only represent probabilities in power of 2 (50%, 25%, etc.) arithmetic coding can represent probabilities with much better accuracy, but requires multiplications and divisions.

FSE solve this dilemna by providing precise probabilities, like arithmetic does, but using only additions, masks and shifts.

This makes FSE faster, on par with Huffman speed, and even suitable for low-power CPU environment.

Benchmarks

Benchmarks are run on an Intel Core i5-3340M (oc'ed to 3.0GHz), with Window Seven 64-bits. Source code is compiled using MSVC 2012, 64-bits mode. Core loop results are reported ( FSE_compress_usingCTable() & FSE_decompress_usingDTable() )

Filename	Compressor	Ratio	Compression	Decompression
book1	FSE	1.766	430 MS/s	540 MS/s
win98-lz4-run	FSE	2.688	430 MS/s	540 MS/s
proba70.bin	FSE	6.337	430 MS/s	520 MS/s
proba90.bin	FSE	15.29	430 MS/s	520 MS/s

Speed is provided in MS/s (Millions of Symbols per second). For more detailed results, browse the benchmark results

As an obvious outcome, speed of FSE is stable accross all tested file. By design, Huffman can't break the "1 bit per symbol" limit. FSE is free of such limit, so its performance increase with probability, remaining close to Shannon limit.

Branch Policy

The "master" branch will reflect the status of stable releases of FSE. The "dev" branch is the one where all contributions will be merged. If you plan to propose a patch, please commit into the "dev" branch. Direct commit to "master" are not permitted. Feature branches will also exist, typically to introduce new requirements, and be temporarily available for testing before merge into "dev" branch.