Упаковка чисел с нестандартной разрядностью бит в массив

Первое что приходит в голову - составить структуру, кратную 8 по длине.
Второе - читать побайтово и сдвигать каждый раз, чтобы получать отдельное число.

Задача: экономно упаковать числа в массив

hint: если неважна последовательность битов, то по кватрам 8 семибитных чисел очень быстро помещаются в 7 восьмибитных. 8 9-битных в 9 восьмибитных. ну и так далее

экономно упаковать числа в массив

Не там ты экономишь. Сэкономив доли копейки на памяти, ты сильно усложняешь код. То, что ты ищешь называется LEB128.

А оно точно тебе надо? Выигрыш по памяти может оказаться ничтожным и ненужным, зато по скорости будет значительное проседание.

как такой массив инициализировать на этапе компиляции

Через constexpr, например.

Какую структуру? Может union? Взять например такую фигню:

#include <inttypes.h>

typedef union
{
  struct
  {
    uint8_t bit0 : 1;
    uint8_t bit1 : 1;
    uint8_t bit2 : 1;
    uint8_t bit3 : 1;
    uint8_t bit4 : 1;
    uint8_t bit5 : 1;
    uint8_t bit6 : 1;
    uint8_t bit7 : 1;
  } bits;
  uint8_t value;
}getbit;

Только не забывай, что ты сэкономишь всего 1/8 памяти, а код усложнится сильно. Тебе оно надо? Ладно бы там были булевы значения или нибблы...

Дык я не говорю конкретно о записи 7-битных, меня интересует общий случай, ну чтобы и 4-битные, и 3-битные, и 5-битные так упаковывать. 7-битные просто для примера

Упаковывать их все в 8-и битные.

А если у меня числа 11-битные например? А если мне в микроконтроллер с ограниченной ПЗУ нужно это втулить? Не, так не годится

Еще раз — на каждый сэкономленный бит данных ты добавляешь 100 байт лишнего кода на encoder/decoder.

У тебя терабайты данных, которые ты пихаешь в пзу?

Классический trade-off: memory vs. cpu. Серебрянной пули нет.

PS: грануляция пзу не редко dword (16bit) — от этого тогда и надо исходить. И что бы прочесть тоже 11-и битное упакованное число, тебе надо обратится в худшем случае уже к двум ячейкам. А это медленно. Разумнее (проще и быстрее) будет паковать 11 бит в 16 бит и не экономить на спичках.

Еще раз — на каждый сэкономленный бит данных ты добавляешь 100 байт лишнего кода на encoder/decoder.

В контроллерах/процессорах с гарвардской архитектуой данные и код хранятся в разных местах вообще-то, так что если много свободного места в секции кода и мало в секции данных, то подобный «размен» может оказаться вполне полезен. Да и не думаю я, что там наберется 100 байт на encoder/decoder. На ассемблере можно очень компактно это сделать

__attribute__((packed))

а потом у них текстовые редакторы тормозят на 16G памяти и 4ядрах 4GHz

Завести специальный тип для таких N-битных представлений вроде тех, что используются в Boost.Endian, сделать специализацию std::vector наподобии std::vector<bool>. Простой она, конечно, не будет, но пользоваться будет можно удобно.

Я другое имел в виду. Ну да, обвернуть в union.

Кстати, зря ты считаешь что такой подход с упаковкой чисел не нужен. Я нашел ему очень хорошее применение. Речь идет о сжатии изображений и видео. Тут только надо как следует подумать над алгоритмом. Взять например какое-нибудь примитивное greyscale изображение 8 бит на один пиксель. Плавное изменение так легко закодировать в меньше чем 8 бит, если считать разность значений пикселей с соседними по определенным правилам. Например простенький градиентик:

char arr[5][5] =
{
  {0x00, 0x02, 0x04, 0x06, 0x07},
  {0x01, 0x03, 0x05, 0x07, 0x08},
  {0x02, 0x04, 0x06, 0x08, 0x09},
  {0x03, 0x05, 0x07, 0x09, 0x0A},
  {0x04, 0x06, 0x08, 0x0A, 0x0C},
}

В том примере используется такое правило

0<<<<<...
^^^^^^...
^^^^^^...
.........

хотя можно сделать нечто вроде

.......
.vvvv<.
.>vv<<.
.>>0<<.
.>>^^<.
.>^^^^.
.......

я велосипедирую битовые потоки в таких случаях обычно

struct bitstream {
  char* current_byte;
  int current_bit;
  char bits_left;
}

int read(bitstream*, int bits);
void write(bitstream*, int value, int bits);
void flush_byte(bitstream*);

есть ли уже готовые реализации на C или C++?

посмотри в zlib, там что-то такое должно быть, наверное

экономно

Экономней всего будет сжать поток бит имея обычные границы для чисел.

Есть частный пример тут: http://leptonica.com/border-rep.html

Serializing the data for a compressed file format
...
The chain code can be represented as a sequence of directions for each step. There are 8 directions, so this requires 3 bits of information. Pack 2 steps into each byte. You can do better, putting 8 steps into 3 bytes, but gzip, which works on bytes, will be less successful at compressing such data, and we use gzip on the sequential step data.

c++

vector<bool>, не?

Да, по стандарту в vector<bool> оно значение в битах хранит. Зачем кстати так сделали? Из-за этого с этим vector<bool> нельзя работать как с нормальным vector. sizeof(bool) равен 1, и следуя логике этот vector<bool> должен по одному байту на элемент выделять, но разработчики стандарта плюсов похоже с логикой не очень дружат. Вот даже ссылка нагуглилась http://alenacpp.blogspot.com/2005/06/vector.html

Ладно, фиг с ней с логикой. В любом случае надо поверх этих битиков городить что-то, что могло бы из этих битиков читать в нормальный тип, и писать в них из нормального типа. Как мне кажется, тут с плюсовым вектором лучше вообще не связываться, функции чтения-записи в этот массив-с-нестандартной битности просто сделать на C через сдвиги и битовые маски, сделав это поверх нормального массива из uint8_t uint16_t uint32_t или uint64_t. Надо только понять, какой тип для массива лучше всего подходит тут

поверх нормального массива из uint8_t uint16_t uint32_t или uint64_t

а чем это будет лучше vector<bool>, в котором уже сделаны более-менее удобные методы обращения к n-му биту?

Я бы массив из bool сделал для хранения. Сдвигать, складывать для получения. Ну если хранить только однородные: семибитные, шестибитные и т.д.

Можешь и в 64-битных числах хранить, потом их кастовать в тот же массив.

Тем, что эффективнее брать некий непрерывный кусок битов из одного или двух соседних(если число попало на границу) элементов массива, чем дергать по битику. Например если надо

01010010001011011000101000010001010000100110110101001010
{-8bit-}{-8bit-}{-8bit-}{-8bit-}{-8bit-}{-8bit-}{-8bit-}
{7bit-}{7bit-}{7bit-}{7bit-}{7bit-}{7bit-}{7bit-}{7bit-}
                        ^
                        |
              прочитать это число

Если это делать масками и сдвигами через чтение соседних {-8bit-}, у компилятора больше шансов заоптимизировать это, чем если получать по одному битику и из них уже собирать {7bit-}

Массив из bool (в отличии от плюсового вектора из bool) будет по байту на элемент тратить, а это не то что я хочу. А про вектор из bool и неэффективности считывания числа побитово я уже свои возражения высказал

ну так зафигачь таким образом. лучший вариант, очевидно, — uint64_t, и доставать числа сдвигом.

а готовых решений я не помню для такого. на всякий случай посмотрел в бусте, там не нашёл. возможно есть на какой-нибудь помойке либа от васяна.

Разве? С последними стандартами он также будет в 1 бит. sizeof, по крайней мере, всё верно показывает.

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

удалить число

тут вроде говорилось не про динамический массив.

А, ну тогда всё-равно сначала интерфейс с DEFINE-ами или шаблонами(C++), а потом 4 алгоритма - для 1,2,3,4-битных чисел и один алгоритм для 1,2,3,4,8-байтных чисел. Выбор алгоритма - DEFINE-ами или if-ами (для известного на этапе сборки sizeof(MY_TYPE) компилятор должен оптимизировать переходы).

Выигрыш в памяти менее, чем в 2 раза для не кратных 8-ми >5битных чисел кажется сомнительным.

Разве? С последними стандартами он также будет в 1 бит.

Эээ... Не понял. Массив из bool (если речь идет об обычном сишном массиве, без этой плюсовой магии) не может по одному биту на элемент держать т.к. к такому элементу никак нельзя получить нормальный указатель

Ну, если совсем делать нечего, то вот:

#include <stdio.h>
#include <stdint.h>

uint64_t read_array(char* a, int i, int b){
        int o = (b*i)>>3;
        int d = b*i-(o<<3);
        uint64_t mask = 0xffffffffffffffff<<(64-b)>>(64-b)<<d;
        return ((*(int64_t*)(a+o))&mask)>>d;
}

void write_array(char* a, int i, int b, uint64_t value){
        int o = (b*i)>>3;
        int d = b*i-(o<<3);
        uint64_t mask = 0xffffffffffffffff<<(64-b)>>(64-b)<<d;
        (*(int64_t*)(a+o))&=  ~mask;
        (*(int64_t*)(a+o))|=  value<<d;
}


int main(){
        char x[8];
        int i;
        for(i=0; i<10; i++)
                write_array(x, i, 5, i);
        
        for(i=0; i<10; i++)
                printf("%ld\n", read_array(x, i, 5));
}

Непортабельно, зависит от порядка байт и все такое. Если сделать макросом и передавать в качестве b константу, то компилятор даже что-то тут соптимизирует.

Ты хоть как-то бы отреагировал на код =(

Ну раз анонимус хочет, чтобы я на этот код как-то отреагировал...

Не совсем понятно, зачем тут нужны сдвиги на 3 :

int o = (b*i)>>3; int d = b*i-(o<<3);

И не совсем понятно, почему я не вижу операции деления / и нахождения остатка от деления %. Например если взять массив из 8-битных char и упаковывать в него 3-битные числа, то чтобы получить десятое 3-битное число, надо было бы сделать следующее: умножить 3 на 10 (получим 30), разделить 30 на 8 нацело (получим 3) и найти остаток от деления 30 на 8 (получим 6). Это значит что десятое по счету 3-битное число в 3 байте, со сдвигом 6. Если ничего не напутал.

Вот эта вот часть ((*(int64_t*)(a+o))&mask)>>d и (*(int64_t*)(a+o))&= ~mask; наводит меня на мысль, что тут чтение-запись uint64_t может производиться не по выравненным под 8 байт адресам. Для некоторых архитектур (в частности ARM) необходимо, чтобы обращения к памяти имели естественное выравнивание, т.е. адрес памяти должен быть кратен размеру данных (2 для short, 4 для int, 8 для uint64_t и double).

Для некоторых архитектур (в частности ARM) необходимо, чтобы обращения к памяти имели естественное выравнивание, т.е. адрес памяти должен быть кратен размеру данных (2 для short, 4 для int, 8 для uint64_t и double).

Для актуальных процессоров ARM вроде уже не важно, не?

Не проверял. Но точно знаю что существуют процессоры, где это важно. В любом случае подобный каст является UB http://spin.atomicobject.com/2014/05/19/c-undefined-behaviors/ см второй пункт

И не совсем понятно, почему я не вижу операции деления / и нахождения остатка от деления %.

Сдвиг на 3 и есть деление на 8.

Учитывая что там используются uint64_t я ожидал увидеть деление на 64 а не на 8. Да и современные компиляторы умеют оптимизировать подобные деления и нахождения остатоков, так что нет смысла запутывать код этими сдвигами вместо деления и нахождения остатка

Учитывая что там используются uint64_t я ожидал увидеть деление на 64 а не на 8.

Как ты справедливо заметил, там есть плохой каст. Можно было бы и догадаться, почему я делю на 8 =) Я ищу кусок из 64 бит, который содержит интересующий нас элемент массива.

Да и современные компиляторы умеют оптимизировать подобные деления и нахождения остатоков, так что нет смысла запутывать код этими сдвигами вместо деления и нахождения остатка

Ну, не очень-то и запутывать. Это ты видишь сдвиг, а я вижу деление на 8 =)

А про оптимизацию... Я часто видел, что (a<<1)+a работает быстрее, чем 3*a.

Кстати, если разрядность бит, которые нужно упаковать, небольшая, то предлагаю паковать сколько влезет в 64 бит.

Например, если нужно упаковать 90 чисел по 7 бит, то запаковать их по 9 штук в 10 uint64_t.

А про оптимизацию... Я часто видел, что (a<<1)+a работает быстрее, чем 3*a.

Не смеши, ты ни черта не понимаешь в оптимизации. Хорошо хоть, твой компилятор исправляет подобные потуги. Начать хотя бы с того, что самое быстрое целочисленное умножение на 3, 5 и 9 под x86(_64) будет не сдвигом со сложением, а единственной lea с косвенной адресацией.

Не смеши, ты ни черта не понимаешь в оптимизации.

Не хами.

Хорошо хоть, твой компилятор исправляет подобные потуги.

Я лишь говорю о том, что видел. В том конкретном случае (a<<1)+a работало быстрее.

В том конкретном случае (a<<1)+a работало быстрее.

Ты код c -O0 что ли собирал? И как мерил, главное?

int a(int x) { return x * 3; }
int b(int x) { return (x << 1) + x; }

a(int):
	leal	(%rdi,%rdi,2), %eax
	ret
b(int):
	leal	(%rdi,%rdi,2), %eax
	ret

a(int):
	add	r0, r0, r0, lsl #1
	bx	lr
b(int):
	add	r0, r0, r0, lsl #1
	bx	lr

Ты код c -O0 что ли собирал?

Пробовал с -O2 и -O3.

И как мерил, главное?

Там был достаточно большой код, который обрабатывал изображение пару секунд.

Любой человеческий компилятор уже с -O1 знает лучше школо-оптимизаторов.

Не спорю. Могу попробовать поискать тот код на работе.

https://github.com/openssl/openssl/blob/6218a1f57e7e25a6b9a798f00cf5f0e56a02f... разработчики openssl тоже нифига в оптимизации не понимают, раз зачем-то втулили ассемблерную вставку для циклического сдвига. Компилятор такое отлично оптимизирует, к тому же в GCC вродекак builtin есть для этого

Пробовал с -O2 и -O3.

Молодец. Отдавай свой код компилятору на оптимизацию, иначе дико тупить будет.

Компилятор такое отлично оптимизирует

Нет.

к тому же в GCC вродекак builtin есть для этого

Нет.

Компилятор такое отлично оптимизирует

Нет.

Да http://goo.gl/vEzjJ8

к тому же в GCC вродекак builtin есть для этого

Нет.

Есть

$ echo "#include <x86intrin.h>" | cpp | grep ror
__rorb (unsigned char __X, int __C)
  return __builtin_ia32_rorqi (__X, __C);
__rorw (unsigned short __X, int __C)
  return __builtin_ia32_rorhi (__X, __C);
__rord (unsigned int __X, int __C)
__rorq (unsigned long long __X, int __C)

Да, я был неправ. Но забавно, что если бинарное или поменять на сложение, clang уже не справляется. Надо бы зарепортить.