Я хочу, чтобы упаковать биты на основе произвольной маски

Question

Допустим, что данные 1011 1001 и маска 0111 0110, то у вас есть:

data:    1011 1001 
mask:    0111 0110 
masked data:  0011 0000 
bits selected: -011 -00- 
right packed:  ---0 1100 
result:   0000 1100 (set left `8 - popcount(mask)` bits to zero) 

Таким образом, окончательный вывод 0000 1100 (обратите внимание, что 3 позиции на слева, которые не указаны, заполняются нулями).

Вы можете увидеть, что везде, где бит маски равен 1, то соответствующее значение в data является выбран (в bits selected выше), а затем все выбранные биты упаковываются смежно начал в наименее значимых битов результата (как показано в right packed выше). Наконец, любые самые левые биты, оставшиеся после упаковки, установлены на 0 (там будет 8 - popcount(mask) таких бит).

Очевидный выбор - это поворот и выбор, но он будет потреблять 5 операций, так как маска имеет 5 бит. Могу ли я сделать это за один шаг?

Примечание:

1. Маска может быть что-нибудь с произвольными n битами ON (В примере выше n=5). Все, что вам известно, это количество бит, которые ON в маске и самой маске. Маска будет меняться с n битами ON.

2. В приведенном выше примере я использовал данные и маску из 8 бит, но в реальном использовании это может быть 8, 16, 32, 64 и 128 бит.

Answer 1

Если вы ориентируетесь x86 большинство компиляторов будет иметь instrinsic для pdep (parallel bit deposit) инструкции, которая непосредственно выполняет операцию, которую вы хотите, в аппаратном обеспечении, в размере 1 за один цикл (3 циклов задержки) , на оборудовании Intel, которое его поддерживает. Например, gcc offers it как внутренние функции _pdep_u32 и _pdep_u64.

К сожалению, на AMD Ryzen (единственное оборудование AMD, поддерживающее BMI2) эта операция выполняется очень медленно: одна на 18 циклов. Возможно, вам понадобится отдельный код для поддержки платформ, отличных от Intel, если они важны для вас.

Если вы не на x86, вы можете найти реализации общего назначения этих опций here - конкретной операции вы хотите expand_right - и этот другой раздел, вероятно, будет большой интерес в том, что она специально покрывает простой случай, когда вы имеете дело с элементами размера слова.

На практике, если вы действительно имеете дело с 8-битными данными и значениями маски, вы можете просто использовать предварительно вычисленную таблицу поиска - либо большой 8-битный x 8 бит = 65k, который охватывает все комбинации {data, mask} и который дает вам ответ напрямую или 256-элементный, который охватывает все значения mask и дает вам некоторые коэффициенты для простого вычисления смещения бит или кода на основе умножения.

FWIW, я не уверен, как вы можете сделать это легко с помощью 5 инструкций поворота, потому что кажется, что наивное решение требует 1 команды поворота для каждого бита, независимо от того, установлен он или нет (поэтому для размера слова 8 бит , 7 или 8 вращаются инструкции).

---

Конечно, производительность в принципе зависит от аппаратного обеспечения, но и на всех основных процессоров Intel, которые реализуют его, это 1 цикл пропускная способность, 3 циклов задержки (не уверен, что AMD).

Только 7 вращается, потому что операция «повернуть 0» для бит младшего порядка, очевидно, может быть опущена.