Разрядная упаковка массива целых чисел

Почти любой алгоритм сжатия приблизится к минимальной энтропии, необходимой для кодирования целых чисел, например, кодирование Хаффмана, но доступ к нему как к массиву будет нетривиальным.

Я знаю, что это может показаться очевидным, так как я уверен, что решение действительно есть, но почему бы не использовать меньший тип, например uint8_t (max 255)? или uint16_t (max 65535)? Я уверен, что вы можете манипулировать битами в int64_t, используя определенные значения, операции и тому подобное, но, кроме академического упражнения, зачем?

А если говорить об академических упражнениях, то Bit Twiddling Hacks - хорошее чтение.

Я согласен с keraba, что вам нужно использовать что-то вроде кодирования Хаффмана или, возможно, алгоритма Лемпеля-Зива-Уэлча. Проблема с битовой упаковкой, о которой вы говорите, заключается в том, что у вас есть два варианта:

• Выбрать константу n, такую, чтобы можно было представить наибольшее целое число.
• Позволить n меняться от значения к значению.

Первый вариант относительно прост в реализации, но он действительно будет занимать много места, если только все целые числа не очень маленькие.

Второй вариант имеет тот существенный недостаток, что вам придется как-то передавать изменения n в выходном битовом потоке. Например, каждое значение должно иметь длину, связанную с ним. Это означает, что вы храните два целых числа (хотя и меньших по размеру) для каждого входного значения. Велика вероятность, что при использовании этого метода вы увеличите размер файла.

Преимущество методов Хаффмана или LZW в том, что они создают кодовые книги таким образом, что длина кодов может быть получена из выходного битового потока без фактического хранения длин. Эти методы позволяют очень близко подойти к пределу Шеннона.

Я решил попробовать вашу оригинальную идею (постоянное n, удаление неиспользуемых битов и упаковка) ради забавы, и вот наивная реализация, к которой я пришел:

#include <sys/types.h>
#include <stdio.h>

int pack(int64_t* input, int nin, void* output, int n)
{
    int64_t inmask = 0;
    unsigned char* pout = (unsigned char*)output;
    int obit = 0;
    int nout = 0;
    *pout = 0;

    for(int i=0; i<nin; i++)
    {
        inmask = (int64_t)1 << (n-1);
        for(int k=0; k<n; k++)
        {
            if(obit>7)
            {
                obit = 0;
                pout++;
                *pout = 0;
            }
            *pout |= (((input[i] & inmask) >> (n-k-1)) << (7-obit));
            inmask >>= 1;
            obit++;
            nout++;
        }
    }
    return nout;
}

int unpack(void* input, int nbitsin, int64_t* output, int n)
{
    unsigned char* pin = (unsigned char*)input;
    int64_t* pout = output;
    int nbits = nbitsin;
    unsigned char inmask = 0x80;
    int inbit = 0;
    int nout = 0;
    while(nbits > 0)
    {
        *pout = 0;
        for(int i=0; i<n; i++)
        {
            if(inbit > 7)
            {
                pin++;
                inbit = 0;
            }
            *pout |= ((int64_t)((*pin & (inmask >> inbit)) >> (7-inbit))) << (n-i-1);
            inbit++;
        }
        pout++;
        nbits -= n;
        nout++;
    }
    return nout;
}

int main()
{
    int64_t input[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int64_t output[21];
    unsigned char compressed[21*8];
    int n = 5;

    int nbits = pack(input, 21, compressed, n);
    int nout = unpack(compressed, nbits, output, n);

    for(int i=0; i<=20; i++)
        printf("input: %lld   output: %lld\n", input[i], output[i]);
}

Это очень неэффективно, поскольку выполняется по одному биту за раз, но это был самый простой способ реализовать это без проблем с бесконечностью. Я не тестировал его с широким диапазоном значений, только с теми, что были в тесте. Также нет проверки границ, и предполагается, что выходные буферы достаточно длинные. То есть я хочу сказать, что этот код, вероятно, годится только для образовательных целей, чтобы вы могли начать.

Если у вас фиксированные размеры, например вы знаете, что ваше число - 38 бит, а не 64, вы можете строить структуры, используя битовые спецификации. Забавно, у вас также есть более мелкие элементы, которые можно разместить в оставшемся пространстве.

struct example {
    /* 64bit number cut into 3 different sized sections */
    uint64_t big_num:38;
    uint64_t small_num:16;
    uint64_t itty_num:10;

    /* 8 bit number cut in two */
    uint8_t  nibble_A:4;
    uint8_t  nibble_B:4;
};

Это небезопасно с прямым порядком байтов без некоторых скачков, поэтому может использоваться только в программе, а не в формате экспортируемых данных. Он довольно часто используется для хранения логических значений в отдельных битах без определения сдвигов и масок.

Я не думаю, что вы можете избежать итераций по элементам. AFAIK кодирование Хаффмана требует частот "символов", которые, если вы не знаете статистику "процесса", генерирующего целые числа, вам придется вычислять (путем итерации по каждому элементу).