Любой умный способ извлечь из массива битов?
У меня есть области памяти, которые можно считать "массивом битов". Они эквивалентны
unsigned char arr[256];
Но это было бы лучше думать как
bit arr[2048];
Я получаю доступ к отдельным битам из этого с
#define GETBIT(x,in) ((in)[ ((x)/8) ] & 1<<(7-((x)%8)))
но я делаю это во многих местах кода, часто в разделах, критичных к производительности, и мне интересно, есть ли более разумные, более оптимальные методы для этого.
дополнительная информация: Архитектура: ARM9 (32 бит); GCC /Linux. Физическое представление данных не может быть изменено - оно предоставляется извне или отображается для внешнего использования.
8 ответов
Для случайного доступа к отдельным битам, предложенный вами макрос так же хорош, как вы собираетесь получить (до тех пор, пока вы включаете оптимизацию в своем компиляторе).
Если к битам, к которым вы обращаетесь, есть какой-то паттерн, то, возможно, вы сможете добиться большего. Например, если вы часто обращаетесь к парам битов, вы можете увидеть некоторое улучшение, предоставив метод, позволяющий получить два бита вместо одного, даже если вы не всегда используете оба бита.
Как и в случае любой проблемы с оптимизацией, вам необходимо хорошо знать поведение вашего кода, в частности, его шаблоны доступа в вашем битовом массиве, чтобы значительно улучшить производительность.
Обновление: так как вы получаете доступ к диапазонам битов, вы, вероятно, можете повысить производительность своих макросов. Например, если вам нужен доступ к четырем битам, у вас могут быть такие макросы:
#define GETBITS_0_4(x,in) (((in)[(x)/8] & 0x0f))
#define GETBITS_1_4(x,in) (((in)[(x)/8] & 0x1e) >> 1)
#define GETBITS_2_4(x,in) (((in)[(x)/8] & 0x3c) >> 2)
#define GETBITS_3_4(x,in) (((in)[(x)/8] & 0x78) >> 3)
#define GETBITS_4_4(x,in) (((in)[(x)/8] & 0xf0) >> 4)
#define GETBITS_5_4(x,in) ((((in)[(x)/8] & 0xe0) >> 5) | (((in)[(x)/8+1] & 0x01)) << 3)
#define GETBITS_6_4(x,in) ((((in)[(x)/8] & 0xc0) >> 6) | (((in)[(x)/8+1] & 0x03)) << 2)
#define GETBITS_7_4(x,in) ((((in)[(x)/8] & 0x80) >> 7) | (((in)[(x)/8+1] & 0x07)) << 1)
// ...etc
Эти макросы вырезают четыре бита из каждой битовой позиции 0, 1, 2 и т. Д. (Чтобы сократить распространение бессмысленных скобок, вы можете использовать встроенные функции для вышеприведенного.) Затем, возможно, определите встроенную функцию, например:
inline int GETBITS_4(int x, unsigned char *in) {
switch (x % 8) {
case 0: return GETBITS_0_4(x,in);
case 1: return GETBITS_1_4(x,in);
case 2: return GETBITS_2_4(x,in);
// ...etc
}
}
Так как это много утомительного стандартного кода, особенно если у вас есть несколько различных значений ширины, вы можете написать программу для генерации всех GETBIT_* функции доступа.
(Я заметил, что биты в ваших байтах хранятся в обратном порядке по сравнению с тем, что я написал выше. Примените соответствующее преобразование, чтобы соответствовать вашей структуре, если вам нужно.)
Я так не думаю. Фактически, многие архитектуры ЦП не имеют доступа к битам по отдельности.
На С ++ у вас есть std::bitset<N>, но может не иметь максимальной производительности в зависимости от реализации и оптимизации вашего компилятора.
Кстати, может быть лучше сгруппировать ваш битовый массив как uint32_t[32] (или же uint64_t[16]) для выравнивания разыменования (которое bitset делает это для вас уже).
Взяв решение Грега за основу:
template<unsigned int n, unsigned int m>
inline unsigned long getbits(unsigned long[] bits) {
const unsigned bitsPerLong = sizeof(unsigned long) * CHAR_BIT
const unsigned int bitsToGet = m - n;
BOOST_STATIC_ASSERT(bitsToGet < bitsPerLong);
const unsigned mask = (1UL << bitsToGet) - 1;
const size_t index0 = n / bitsPerLong;
const size_t index1 = m / bitsPerLong;
// Do the bits to extract straddle a boundary?
if (index0 == index1) {
return (bits[index0] >> (n % bitsPerLong)) & mask;
} else {
return ((bits[index0] >> (n % bitsPerLong)) + (bits[index1] << (bitsPerLong - (m % bitsPerLong)))) & mask;
}
}
Можно получить как минимум 32 бита, даже если они не выровнены. Обратите внимание, что это намеренно inline как вы не хотите иметь тонны этих функций.
Если вы измените порядок бит в 'arr', то вы можете исключить вычитание из макроса. Это лучшее, что я могу сказать, без знания контекста проблемы (как используются биты).
#define GETBIT(x,in) ((in)[ ((x)/8) ] & 1<<(7-((x)%8)))
можно оптимизировать.
1) Используйте стандартный int, который обычно является самым быстрым доступным целочисленным типом данных. Если вам не нужно быть переносимым, вы можете узнать размер int с помощью size of и адаптировать следующий код.
2)
#define GETBIT(x,in) ((in)[ ((x) >>> 3) ] & 1<<((x) & 7))
Оператор мода% медленнее, чем ANDing. И вам не нужно вычитать, просто настройте вашу процедуру SETBIT.
Вместо массива unsigned char и пользовательских макросов вы можете использовать std::vector<bool>, Векторный шаблон класса имеет специальную специализацию шаблона для типа bool. Эта специализация предназначена для оптимизации распределения пространства: в этой специализации шаблонов каждый элемент занимает только один бит (что в восемь раз меньше, чем наименьший тип в C++: char).
Почему бы не создать свой собственный класс оболочки?
Затем вы можете добавить биты в "массив", используя оператор, такой как +, и вернуть отдельные биты, используя оператор [].
Ваш макрос можно улучшить, используя & 7 вместо% 8, но, скорее всего, компилятор все равно выполнит эту оптимизацию за вас.
Я недавно сделал именно то, что вы делаете, и мой поток может состоять из любого количества битов.
Итак, у меня есть что-то вроде следующего:
BitStream< 1 > oneBitBitStream;
BitStream< 2 > twoBitBitStream;
oneBitBitStream += Bit_One;
oneBitBitStream += Bit_Zero;
twoBitBitStream += Bit_Three;
twoBitBitStream += Bit_One;
и так далее. Это делает для хорошего читаемого кода, и вы можете предоставить STL-подобный интерфейс для облегчения несоответствия:)
Поскольку вопрос помечен C++, есть ли причина, по которой вы не можете просто использовать стандартный набор битов?