Ultrapacking: A Layer over Bit-Packing
Ultrapacking: A Layer Over Bit-Packing


As a motivating example, suppose we have \(n = 10\), and we want to compress a sequence of three
values \([9, 0, 5]\). One way we could represent this sequence is using the number \(905\), which we
obtain by concatenating the elements as digits in a number. The maximum possible number in this
scheme is \(999\), which takes \(10\) bits. In other words, any group of \(3\) numbers can be stored
in \(10\) bits. So given a stream of these numbers we can pack them into these \(10\) -bit groups, and then
bitpack those.



This gives an intuition for the compression scheme in its general form: Given an \(n\), take
\(k\) elements from your input stream \(a_1, \dots, a_k\) to form a bundle. Then, compute the number
represented by concatenating the bundle into a base \(n\) number \((a_1a_2\dots a_k)_n\). The computer
will naturally store this number in binary using \(b\) bits, which we can bitpack as normal.



Of course, since memory is byte-addressable, we can't just output \(b\) bits (\(10\) in our example).
Instead, we must always output a multiple of \(8\) bits by compressing multiple bundles into a group.
The number of bits in a group is given by \(LCM(b, 8)\), and so the number of bundles in a group is
\(\frac{LCM(b, 8)}{8}\).



uint64_t Compress_Bundle_N_10_K_3(const uint32_t **input)
{
    constexpr size_t N = 10;
    constexpr size_t K = 3;
    uint64_t bundle = 0;
    for(size_t i = 0; i < K; i++)
    {
        bundle *= N;
        bundle += input[i];
    }
    (*input) += K;
    return bundle;
}

uint64_t Compress_N_10_K_3(const uint32_t *input, size_t n, uint8_t *output)
{
    const uint32_t end = input + n;
    constexpr uint64_t group_length = 4; // LCM(10, 8) = 40 bits = 5 bytes, 4 groups
    constexpr uint64_t group_bytes = 5;

    while(input < end)
    {
        uint64_t group = 0;
        for(size_t i = 0; i < group_length; i++)
            group |= (Compress_Bundle_N_10_K_3(&input) << (10 * i));
        *(uint64_t *)output = group;
        output += group_bytes;
    }
}




Decompression is exactly the inverse process, decomposing a base \(n\) number into its constitutent
digits.



uint64_t Decompress_Bundle_N_10_K_3(uint64_t group, uint32_t **output)
{
    constexpr size_t N = 10;
    constexpr size_t K = 3;
    constexpr uint64_t mask = (1 << N) - 1;
    uint64_t bundle = group & mask;
    for(size_t i = K - 1; i >= 0; i--)
    {
        output[i] = bundle % N;
        bundle /= N;
    }
    return (group >> N);
}

uint64_t Decompress_N_10_K_3(const uint8_t *input, size_t n, uint32_t *output)
{
    const uint32_t end = output + n;
    constexpr uint64_t group_length = 4; // LCM(10, 8) = 40 bits = 5 bytes, 4 groups
    constexpr uint64_t group_bytes = 5;

    while(output < end)
    {
        uint64_t group = *(uint64_t *)input;
        for(size_t i = 0; i < group_length; i++)
            group = Decompress_Bundle_N_10_K_3(group, &output);
        input += group_bytes;
    }
}


