Awesome

<a href="https://github.com/rainerzufalldererste/hypersonic-rle-kit"><img src="https://raw.githubusercontent.com/rainerzufalldererste/hypersonic-rle-kit/master/docs/logo.png" alt="hypersonic rle kit logo" style="width: 533pt; max-width: 100%; margin: 50pt auto;"></a> <br>

What is it?

• A collection of 120+ RLE and related codecs optimized for all kinds of different inputs and scenarios.
• Usually the fastest run length en/decoder by far. Single Core Decompression Speeds > 34 GB/s and Compression Speeds > 28 GB/s have been observed with large files. (small files can exceed 120 GB/s decode, 60 GB/s encode)
• Written in C.
• SIMD Variants for AVX-512F, AVX2, AVX, SSE4.1, SSSE3 and SSE2 variants are available for various decoders and encoders. Automatically picked at runtime based on the extensions available on the current platform.
• Variants include: Single RLE Symbol, Short Strings of RLE Symbols, Byte Alignmed, Symbol Aligned, 8 Bit, 16 Bit, 24 Bit, 32 Bit, 48 Bit, 64 Bit, 128 Bit, Different probabilities of reoccuring symbols, ...
• OpenCL variant available for some of the decoders.
• Licensed under Two Clause BSD.

Benchmark

See Full Benchmark with Graphs, the tables below only contain a tiny selection of the 100+ codecs.

<a href="https://rainerzufalldererste.github.io/hypersonic-rle-kit/"><img src="https://raw.githubusercontent.com/rainerzufalldererste/hypersonic-rle-kit/master/docs/screenshot.png" alt="hypersonic rle kit pareto graph screenshot" style="width: 100%;"></a> <br>

• Single-Threaded
• Running on an AMD Ryzen 9 7950X, 32 GB DDR5-6000 CL30 on Windows 11.
• Compiled with Visual Studio 2022.
• Compared to TurboRLE and MRLE (with AVX2 enabled; benchmarking results have been converted from MB/s to MiB/s) (7f6e486, April 2023)
• Contained Codecs w/ Compression / Decompression Speed vs. Ratio Pareto + Notable Entropy Highlighted

video-frame.raw (heavily quantized video frame DCTs, 88,473,600 Bytes)

1034.db (Checkers program "End Game Table Base", 419,225,625 Bytes)

enwik9.bwt (Wikipedia extract enwiki9 encoded using libdivsufsort, 1,000,000,124 Bytes)

The 24 Bit and 48 Bit Variants allow for run length encoding of common data layouts that are usually not covered by RLE implementations:

Pixel Art Bitmap Image (PNG converted to BMP, 123,710,454 Bytes)

Variants

8, 16, 24, 32, 48, 64, 128 Bit (Byte Aligned + Symbol Aligned)

• Extremely Fast.
• Variants for always aligning with the symbol width or allowing byte-wide repeats even for > 8 bit symbols.
• Decoder interprets blocks of data to boil down to a highly optimized memcpy, memset, memcpy, memset (with various different byte-lengths).
• Encoder searches for repeats and their respective lengths using movemask instructions.
• Optional variant for 8 bit single symbol encoding.

8, 16, 24, 32, 48, 64, 128 Bit Packed (Byte Aligned + Symbol Aligned)

• Similar to the base variant, but keeps around the previously used RLE symbol which is usually very beneficial to the compression ratio and tries to pack lengths a bit more optimistically.
• Also Extremely Fast, whilst providing better compression ratio for many inputs
• Also has those variants for always aligning with the symbol width or allowing byte-wide repeats even for > 8 bit symbols.
• Optional variant for 8 bit single symbol encoding (only has the optimistic packing, as it already knows what the next symbol is going to be anyways).

1 Sym LUT / 3 Sym LUT / 3 Sym LUT Short / 7 Sym LUT / 7 Sym LUT Short

• Similar to the base variant, but keeps around one / three / seven of the previously used RLE symbols, usually further improving compression ratios.
• Short Variant: Packs Range & Count Bits to fit the entire RLE command into just one byte for short ranges.

1 Sym LUT Short Greedy / 3 Sym LUT Short Greedy / 7 Sym LUT Short Greedy

• Similar to n-Sym LUT Short (actually uses the exact same decoder), but tries to even compress partial occurences of a symbol if that would save space
• Only available when byte-aligned for 16, 24, 32, 48, 64 Bit Variants
• Comparably slow to en/decode

Low Entropy / Low Entropy Short

• Tries to keep symbol general symbol frequency to improve compression ratio of an entropy encoder that could go after the Run Length Encoding like ANS, Arithmetic Coding or Huffman.
• Parses the output for run-length-encodable symbols, which are specified in the header.
• Has a single-symbol variant, that only encodes the most run-length-encodable symbol (useful for some image codecs).
• Short Variant: Same as Low Entropy, but optimized for shorter strings of run-length-encodable symbols, usually faster, also has a single-symbol variant.

8 Bit RLE + MMTF (Multi Move-To-Front Transformation)

• Runs a block-wide vectorized MTF transform on the input and depending on how many bits this needs to represent a given block (if it's not entirely representable by a variant of memset) uses only the required amount of bits to encode the block.
• Performs well on a wide variety of inputs, but usually doesn't produce the best compression ratios or (de-) compression speeds, as all blocks need to be decoded and cannot simply be memcpyd if they don't contain an encodable symbol.

RLE + Huffman-esque

• Uses a separate header, that contains a huffman-esque instructions to place recent high-prevalence symbols, copy or set a specific symbol to a block.
• Usually very high compression ratios, but comparably slow to en- & decode.

Raw MMTF (Multi Move-To-Front Transformation)

• Simply runs the block-wide vectorized MTF transform on the input to improve compressability for some scenarios.
• Doesn't compress itself.

Setup

git clone https://github.com/rainerzufalldererste/hypersonic-rle-kit.git
cd hypersonic-rle-kit
git submodule update --init --recursive

On Windows

create_project.bat

Choose your preferred compiler toolset

MSBuild /p:Configuration=Release /nologo /v:m

On Linux

premake/premake5 gmake2
config=release_x64 make

How to use it?

#include "rle.h"

uint8_t *pUncompressedData; // Some Data.
uint32_t fileSize; // Some Size.

// Get Compress Bounds.
const uint32_t compressedBufferSize = rle_compress_bounds(fileSize);
uint8_t *pCompressedData = (uint8_t *)malloc(compressedBufferSize);

// Compress.
const uint32_t compressedSize = rle8_multi_compress(pUncompressedData, fileSize, pCompressedData, compressedBufferSize);

// Allocate Output Buffer.
uint8_t *pDecompressedData = (uint8_t *)malloc(fileSize + rle_decompress_additional_size());

// Decompress.
const uint32_t decompressedSize = rle8_decompress(pCompressedData, compressedSize, pDecompressedData, fileSize);

// Cleanup.
free(pCompressedData);
free(pDecompressedData);

License

Two Clause BSD