C++ library to pack and unpack vectors of integers having a small range of values using a technique called Frame of Reference
APACHE-2.0 License
C++ library to pack and unpack vectors of integers having a small range of values using a technique called Frame of Reference (Goldstein et al. 1998). It should run fast even though it is written in simple C++.
Code from this library is part Apache Arrow and Apache Impala.
Given an array of 32-bit integers, you can compress it as follows:
#include "compression.h"
...
uint32_t * inputdata = ... // length values
uint32_t * compresseddata = ... // enough data
uint32_t *out = compress(inputdata, length, compresseddata);
// compressed data lies between compresseddata and out
uint32_t nvalue = 0;
uint32_t * recoverydata = ... // available buffer with at least length elements
uncompress(compresseddata, recoverydata, nvalue);
// nvalue will be equal to length
There is a similar API with turbocompress
and turbouncompress
with the difference
that compresseddata
uses an uint8_t
pointer type.
#include "turbocompression.h"
...
uint32_t * inputdata = ... // length values
uint8_t * compresseddata = ... // enough data
uint8_t *out = turbocompress(inputdata, length, compresseddata);
// compressed data lies between compresseddata and out
uint32_t nvalue = 0;
uint32_t * recoverydata = ... // available buffer with at least length elements
turbouncompress(compresseddata, recoverydata, nvalue);
// nvalue will be equal to length
We can also compress 64-bit arrays:
#include "turbocompression.h"
...
uint64_t * inputdata = ... // length values
uint8_t * compresseddata = ... // enough data
uint8_t *out = turbocompress64(inputdata, length, compresseddata);
// compressed data lies between compresseddata and out
uint32_t nvalue = 0;
uint64_t * recoverydata = ... // available buffer with at least length elements
turbouncompress64(compresseddata, recoverydata, nvalue);
// nvalue will be equal to length
To run a simple benchmark, do
make
./test sampledata.txt
where sampledata.txt is a text data file with one integer per line.
For a parallelized version, type
make testmp
./testmp sampledata.txt
This requires OpenMP support however.
You need to have cmake
installed and available as a command.
mkdir release
cd release
cmake ..
make
make test
We are assuming that you have a common Windows PC with at least Visual Studio 2015, and an x64 processor.
To build with at least Visual Studio 2015 from the command line:
cmake
be made available from the command line.VisualStudio
.FrameOfReference
in your GitHub repository list, and select Open in Git Shell
, then type cd VisualStudio
in the newly created shell.cmake -DCMAKE_GENERATOR_PLATFORM=x64 ..
in the shell while in the VisualStudio
repository.FrameOfReference.sln
). Open this file in Visual Studio. You should now be able to build the project and run the tests. For example, in the Solution Explorer
window (available from the View
menu), right-click ALL_BUILD
and select Build
. To test the code, still in the Solution Explorer
window, select RUN_TESTS
and select Build
.To build with at least Visual Studio 2017 directly in the IDE:
Visual C++ tools for CMake
optional component when installing the C++ Development Workload within Visual Studio.File > Open > Folder...
to open the FrameOfReference folder.Solution Explorer
and select Build
to build the project.Select Startup Item...
menu and choose one of the tests. Run the test by pressing the button to the left of the dropdown.This was tested with GNU G++ and clang++ After suitable adjustments, it should build under most C++ compilers.