Любой умный способ извлечь из массива битов?

Question

У меня есть области памяти, которые можно считать «массивом битов». Они эквивалентны

unsigned char arr[256];

Но это было бы лучше думать как

bit arr[2048];

Я обращаюсь к отдельным битам из него с помощью

#define GETBIT(x,in)   ((in)[ ((x)/8) ] & 1<<(7-((x)%8)))

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

дополнительная информация: архитектура: ARM9 (32 бита); GCC / Linux. Физическое представление данных не может быть изменено - оно предоставляется извне или отображается для внешнего использования.

Answer 1

Я так не думаю. Фактически, многие архитектуры ЦП не имеют доступа к битам по отдельности.

На C ++ у вас есть std::bitset<N>. но может не иметь максимальной производительности в зависимости от реализации и оптимизации вашего компилятора.

Кстати, может быть лучше сгруппировать ваш битовый массив как uint32_t[32] (или uint64_t[16]) для выравнивания разыменования (что bitset уже делает для вас).

Answer 2

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

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

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

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

#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_*.

(Я заметил, что биты в ваших байтах хранятся в порядке, обратном тому, что я написал выше. Примените соответствующее преобразование, чтобы соответствовать вашей структуре, если вам нужно.)

Answer 3

Взяв за основу решение Грега:

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, так как вы не хотите иметь тонны этих функций.

Answer 4

#define GETBIT(x,in)   ((in)[ ((x)/8) ] & 1<<(7-((x)%8)))

можно оптимизировать.

1) Используйте стандартный int, который обычно является самым быстрым доступным целочисленным типом данных. Если вам не нужно быть переносимым, вы можете узнать размер int с помощью sizeof и адаптируйте следующий код.

2)

#define GETBIT(x,in)   ((in)[ ((x) >>> 3) ] & 1<<((x) & 7))

Оператор мода% медленнее, чем ANDing. И вам не нужно вычитать, просто настройте вашу процедуру SETBIT.

Answer 5

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

Answer 6

Вместо массива unsigned char и пользовательских макросов вы можете использовать std::vector<bool>. Векторный шаблон класса имеет специальную специализацию шаблона для типа bool. Эта специализация предназначена для оптимизации распределения пространства: в этой специализации шаблона каждый элемент занимает только один бит (что в восемь раз меньше, чем наименьший тип в C ++: char).

Answer 7

Поскольку вопрос помечен C ++, есть ли причина, по которой вы не можете просто использовать стандарт bitset ?

Answer 8

Почему бы не создать свой собственный класс-обертку?

Затем можно добавить биты в «массив», используя оператор, такой как +, и вернуть отдельные биты, используя оператор [].

Ваш макрос может быть улучшен с помощью & 7 вместо% 8, но вполне вероятно, что компилятор все равно выполнит эту оптимизацию за вас.

Я недавно сделал именно то, что вы делаете, и мой поток может состоять из любого количества битов.

Итак, у меня есть что-то вроде следующего:

BitStream< 1 > oneBitBitStream;
BitStream< 2 > twoBitBitStream;

oneBitBitStream += Bit_One;
oneBitBitStream += Bit_Zero;

twoBitBitStream += Bit_Three;
twoBitBitStream += Bit_One;

и т. Д. Это делает для удобного чтения кода, и вы можете предоставить STL-подобный интерфейс для облегчения различий:)