Skip to content
Go to file

Latest commit


Git stats


Failed to load latest commit information.
Latest commit message
Commit time

libfor - Fast C Library for Frame of Reference Integer Compression

An ANSI C library with a fast scalar (non-SIMD) implementation for Frame of Reference (FOR) integer compression. It works on Linux, Microsoft Windows and most likely all other sane systems.

FOR can compress sorted and unsorted integer sequences.

In addition, the library can perform operations directly on compressed data:

  • select: returns a value at a specified index
  • linear search: for unsorted sequences, or short sorted sequences
  • lower bound search: based on binary search, for sorted sequences
  • append: appends an integer to a compressed sequence

Simple demo

#define LEN 100
uint32_t in[LEN] = {0};
uint8_t out[512];

// Fill |in| with numbers of your choice
for (int i = 0; i < LEN; i++)
  in[i] = i;

// Now compress; can also use for_compress_sorted() if the numbers
// are sorted. This is slightly faster.
uint32_t size = for_compress_unsorted(&in[0], &out[0], LEN);
printf("compressing %u integers (%u bytes) into %u bytes\n",
        LEN, LEN * 4, size);

// Decompress again
uint32_t decompressed[LEN];
for_uncompress(&out[0], &decompressed[0], LEN);


It can't be more simple:


To run the tests:


Where is this used?

I use this library to compress 32bit integers for upscaledb, a very fast embedded key/value store (see

If you would like me to add your application to this list then please send me a mail at


Apache License, Version 2.0


This library only works with little-endian CPUs.

Tested on Linux and Windows (Visual Studio 2013). Porting it should not be difficult.


This work is based on Daniel Lemire ('s ideas and implementation at

For further information, see

  • Goldstein J, Ramakrishnan R, Shaft U. Compressing relations and indexes. Proceedings of the Fourteenth International Conference on Data Engineering, ICDE ’98, IEEE Computer Society: Washington, DC, USA, 1998; 370–379.
  • Daniel Lemire and Leonid Boytsov, Decoding billions of integers per second through vectorization, Software Practice & Experience 45 (1), 2015.
  • Daniel Lemire, Leonid Boytsov, Nathan Kurz, SIMD Compression and the Intersection of Sorted Integers, Software Practice & Experience (to appear)
  • Jeff Plaisance, Nathan Kurz, Daniel Lemire, Vectorized VByte Decoding, International Symposium on Web Algorithms 2015, 2015.
  • Wayne Xin Zhao, Xudong Zhang, Daniel Lemire, Dongdong Shan, Jian-Yun Nie, Hongfei Yan, Ji-Rong Wen, A General SIMD-based Approach to Accelerating Compression Algorithms, ACM Transactions on Information Systems 33 (3), 2015.


A very fast scalar implementation for Frame Of Reference integer compression.




No releases published


No packages published


You can’t perform that action at this time.