Портативная эффективная альтернатива PDEP без использования BMI2?

Документация для инструкции по параллельному депонированию (PDEP) в наборе инструкций Intel по управлению битами 2 ( BMI2) описывает следующую последовательную реализацию инструкции (C-подобный псевдокод):

U64 _pdep_u64(U64 val, U64 mask) {
  U64 res = 0;
  for (U64 bb = 1; mask; bb += bb) {
    if (val & bb)
      res |= mask & -mask;
    mask &= mask - 1;
  }
  return res;
}

См. также pdep insn ref, вводимые вручную в Intel.

Этот алгоритм - O (n), где n - количество установленных битов в mask, что, очевидно, имеет наихудший случай O (k), где k - общее количество битов в mask.

Возможен ли более эффективный алгоритм наихудшего случая?

Можно ли сделать более быструю версию, предполагающую, что val имеет не более одного установленного бита, то есть либо равно 0, либо равно 1<<r для некоторого значения r от 0 до 63?


x86 algorithm assembly bit-manipulation bmi
person markt1964    schedule 14.08.2016    source источник
comment
Генри Уоррен, Hacker's Delight, 2-е изд., Глава 7-5 дает алгоритм параллельного суффикса для общей 32-битной операции deposit и утверждает, что для этого требуется около 160 инструкций (точное количество будет зависеть от особенности набора команд процессора). Если я правильно понимаю ваш второй вопрос об особом случае 1-битного депозита, он сводится к быстрой изоляции r -го 1-го бита mask.   -  person njuffa    schedule 14.08.2016
comment
Для вашего особого случая 1-битного депозита r будет известно заранее, или нам нужно сначала найти r, исследуя val, прежде чем изолировать r-й 1-бит в mask?   -  person njuffa    schedule 14.08.2016
comment
r можно легко найти, если он еще не известен. Допустим, это известно.   -  person markt1964    schedule 14.08.2016

Ответы (1)


arrow_upward
4
arrow_downward

Вторая часть вопроса, касающаяся особого случая 1-битного депозита, требует двух шагов. На первом этапе нам нужно определить битовый индекс r одиночного 1-бита в val с подходящим ответом в случае, если val равно нулю. Это может быть легко выполнено с помощью функции POSIX ffs или, если r известен, другими способами, как указано в комментариях спрашивающего. На втором этапе нам нужно определить битовый индекс i r-го 1-го бита в mask, если он существует. Затем мы можем поместить r-й бит val в бит i.

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

Следующий C-код демонстрирует это с использованием 64-битных данных. Будет ли это на самом деле быстрее, чем итерационный метод, будет во многом зависеть от типичных значений mask и val.

#include <stdint.h>

/* Find the index of the n-th 1-bit in mask, n >= 0
   The index of the least significant bit is 0 
   Return -1 if there is no such bit
*/
int find_nth_set_bit (uint64_t mask, int n)
{
    int t, i = n, r = 0;
    const uint64_t m1 = 0x5555555555555555ULL; // even bits
    const uint64_t m2 = 0x3333333333333333ULL; // even 2-bit groups
    const uint64_t m4 = 0x0f0f0f0f0f0f0f0fULL; // even nibbles
    const uint64_t m8 = 0x00ff00ff00ff00ffULL; // even bytes
    uint64_t c1 = mask;
    uint64_t c2 = c1 - ((c1 >> 1) & m1);
    uint64_t c4 = ((c2 >> 2) & m2) + (c2 & m2);
    uint64_t c8 = ((c4 >> 4) + c4) & m4;
    uint64_t c16 = ((c8 >> 8) + c8) & m8;
    uint64_t c32 = (c16 >> 16) + c16;
    int c64 = (int)(((c32 >> 32) + c32) & 0x7f);
    t = (c32    ) & 0x3f; if (i >= t) { r += 32; i -= t; }
    t = (c16>> r) & 0x1f; if (i >= t) { r += 16; i -= t; }
    t = (c8 >> r) & 0x0f; if (i >= t) { r +=  8; i -= t; }
    t = (c4 >> r) & 0x07; if (i >= t) { r +=  4; i -= t; }
    t = (c2 >> r) & 0x03; if (i >= t) { r +=  2; i -= t; }
    t = (c1 >> r) & 0x01; if (i >= t) { r +=  1;         }
    if (n >= c64) r = -1;
    return r; 
}

/* val is either zero or has a single 1-bit.
   Return -1 if val is zero, otherwise the index of the 1-bit
   The index of the least significant bit is 0
*/
int find_bit_index (uint64_t val)
{
    return ffsll (val) - 1;
}

uint64_t deposit_single_bit (uint64_t val, uint64_t mask)
{
    uint64_t res = (uint64_t)0;
    int r = find_bit_index (val);
    if (r >= 0) {
        int i = find_nth_set_bit (mask, r);
        if (i >= 0) res = (uint64_t)1 << i;
    } 
    return res;
}
person njuffa    schedule 14.08.2016
comment
Это круто. Однако в find_nth_set_bit есть несколько магических чисел ... поэтому я не уверен, что хочу расширять его до целого числа более 32 бит ... скажем, 64, 128 или даже 256 бит. - person markt1964; 14.08.2016
comment
@ markt1964 Я изменил код на 64-битную реализацию и использовал именованные маски, чтобы было понятнее, что эти маски делают. - person njuffa; 14.08.2016