Эффективно найти позицию 1 в битовом массиве - PullRequest
5 голосов
/ 15 февраля 2012

Я пишу программу, которая проверяет набор проводов на обрыв или короткое замыкание. Программа, которая работает на AVR, запускает тестовый вектор («1») на проводах и получает результат обратно. Он сравнивает этот результирующий вектор с ожидаемыми данными, которые уже сохранены на SD-карте или внешней EEPROM.

Вот пример, предположим, что у нас есть набор из 8 проводов, все из которых являются прямыми, т.е. они не имеют переходов. Поэтому, если мы едем 0b00000010, мы должны получить 0b00000010.

Предположим, мы получили 0b11000010. Это подразумевает короткое замыкание между проводом 7,8 и проводом 2. Я могу определить, какие интересующие меня биты, по 0b00000010 ^ 0b11000010 = 0b11000000. Это говорит мне о том, что провода 7 и 8 виноваты, но как мне найти расположение этих единиц в большом массиве битов. Это легко сделать всего за 8 проводов, используя битовые маски, но система, которую я разрабатываю, должна обрабатывать до 300 проводов (бит). Прежде чем я начал использовать макросы, подобные приведенным ниже, и тестировать каждый бит в массиве из 300 * 300 бит, я хотел спросить здесь, есть ли более элегантное решение.

 #define BITMASK(b) (1 << ((b) % 8))
 #define BITSLOT(b) ((b / 8))
 #define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))
 #define BITCLEAR(a,b) ((a)[BITSLOT(b)] &= ~BITMASK(b))
 #define BITTEST(a,b) ((a)[BITSLOT(b)] & BITMASK(b))
 #define BITNSLOTS(nb) ((nb + 8 - 1) / 8)

Просто чтобы показать, как обнаружить обрыв цепи. Ожидаемые данные: 0b00000010, полученные данные: 0b00000000 (провод не вытянут высоко). 0b00000010 ^ 0b00000000 = 0b0b00000010 - провод 2 разомкнут.

ПРИМЕЧАНИЕ. Я знаю, что тестирование 300 проводов - это не то, что может обрабатывать крошечный ОЗУ в AVR Mega 1281, поэтому я разделю его на группы, то есть протестирую 50 проводов, сравню, отобразлю результат и затем продвинусь вперед.

Ответы [ 5 ]

3 голосов
/ 15 февраля 2012

Многие архитектуры предоставляют конкретные инструкции для определения местоположения первого установленного бита в слове или для подсчета количества установленных битов. Компиляторы обычно предоставляют встроенные функции для этих операций, поэтому вам не нужно писать встроенную сборку. GCC, например, предоставляет __builtin_ffs, __builtin_ctz, __builtin_popcount и т. Д., Каждый из которых должен соответствовать соответствующей инструкции на целевой архитектуре, используя параллелизм на уровне битов.

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

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

1 голос
/ 16 февраля 2012

Как часто вы ожидаете неисправностей? Если вы не ожидаете их так часто, то, кажется, бессмысленно оптимизировать случай «ошибка существует» - единственная часть, которая действительно будет иметь значение для скорости, - это случай «без ошибок».

Чтобы оптимизировать случай отсутствия ошибок, просто XOR фактического результата с ожидаемым результатом и тест input ^ expected == 0, чтобы увидеть, установлены ли какие-либо биты.

Вы можете использовать аналогичную стратегию для оптимизации случая "нескольких сбоев", если в дальнейшем вы ожидаете, что число сбоев обычно будет небольшим, когда они существуют - замаскируйте значение input ^ expected, чтобы получить только первые 8 битов, только вторые 8 бит и т. д., и сравните каждый из этих результатов с нулем. Затем вам просто нужно найти установленные биты в пределах тех, которые не равны нулю, что должно сузить пространство поиска до чего-то, что можно сделать довольно быстро.

0 голосов
/ 16 февраля 2012

Я думаю, что вам не хватает леса сквозь деревья.Похоже на ложе из гвоздя.Сначала проверьте некоторые предположения: 1) Вы знаете, какие выводы должны быть под напряжением для каждого проверенного / запитанного контакта.2) у вас есть список соединений, переведенный для шага 1 в файл на sd

Если вы работаете как на уровне байтов, так и на битах, это упрощает проблему.Если вы активируете булавку, в вашем файле будет сохранен ожидаемый шаблон.Сначала найдите несоответствующие байты;идентифицировать несовпадающие контакты в байте;наконец, сохраните под напряжением вывод с номерами неисправных выводов.

Вам не нужен массив для поиска или результатов.общая идея:

numwires=300;

numbytes=numwires/8 + (numwires%8)?1:0;

for(unsigned char currbyte=0; currbyte<numbytes; currbyte++)
{
   unsigned char testbyte=inchar(baseaddr+currbyte)
  unsigned char goodbyte=getgoodbyte(testpin,currbyte/*byte offset*/);
  if( testbyte ^ goodbyte){
  // have a mismatch report the pins
    for(j=0, mask=0x01; mask<0x80;mask<<=1, j++){
       if( (mask & testbyte) != (mask & goodbyte)) // for clarity
          logbadpin(testpin, currbyte*8+j/*pin/wirevalue*/, mask & testbyte /*bad value*/);

     }

}
0 голосов
/ 16 февраля 2012

Я думаю, что есть только один способ сделать это:

  • Создать массив из "outdata". Каждый элемент массива может, например, соответствовать 8-битному регистру порта.
  • Отправьте исходные данные по проводам.
  • Считать эти данные как "indata".
  • Сохранение данных в массиве, отображаемом в точности как выходные данные.
  • В цикле XOR каждый байт outdata с каждым байтом indata.

Я бы настоятельно рекомендовал встроенные функции вместо этих макросов.

Почему ваш MCU не может обрабатывать 300 проводов?

300/8 = 37,5 байт. Округлено до 38. Его нужно хранить дважды, outdata и indata, 38 * 2 = 76 байт.

Вы не можете сэкономить 76 байт оперативной памяти?

0 голосов
/ 16 февраля 2012

Вы можете использовать справочную таблицу. Например, таблица поиска log-base-2 из 255 байтов может использоваться для нахождения наиболее значимого 1-битного в байте:

uint8_t bit1 = log2[bit_mask];

где log2 определяется следующим образом:

uint8_t const log2[] = {
   0,               /* not used log2[0] */
   0,               /* log2[0x01] */
   1, 1             /* log2[0x02], log2[0x03] */
   2, 2, 2, 2,      /* log2[0x04],..,log2[0x07] */
   3, 3, 3, 3, 3, 3, 3, 3, /* log2[0x08],..,log2[0x0F */ 
   ... 
} 

На большинстве процессоров таблица поиска, подобная этой, отправляется в ПЗУ. Но AVR - это гарвардская машина, и для размещения данных в кодовом пространстве (ПЗУ) требуется специальное нестандартное расширение, которое зависит от компилятора. Например, компилятору IAR AVR потребуется использовать расширенное ключевое слово __flash. В WinAVR (GNU AVR) вам нужно будет использовать атрибут PROGMEM, но он более сложен, потому что вам также нужно использовать специальные макросы для чтения из пространства программы.

...