Сдвиг замаскированных битов в lsb

Когда вы and некоторые данные с маской, вы получаете некоторый результат, который имеет тот же размер, что и данные/маска. То, что я хочу сделать, - это взять замаскированные биты в результате (там, где в маске было 1) и сдвинуть их вправо, чтобы они были рядом друг с другом, и я могу выполнить CTZ (Count Trailing Zeroes) на них.

Я не знал, как назвать такую процедуру, чтобы Google не удался. Операция должна предпочтительно не быть петлевым решением, это должно быть как можно быстрее.

И вот невероятное изображение, сделанное в MS Paint.

Ответ 1

Эта операция называется сжатие справа. Он реализован как часть BMI2 в качестве инструкции PEXT в процессорах Intel по сравнению с Haswell.

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

unsigned compress(unsigned x, unsigned m) {
   unsigned r, s, b;    // Result, shift, mask bit. 

   r = 0; 
   s = 0; 
   do {
      b = m & 1; 
      r = r | ((x & b) << s); 
      s = s + b; 
      x = x >> 1; 
      m = m >> 1; 
   } while (m != 0); 
   return r; 
}

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

unsigned compress(unsigned x, unsigned m) {
   unsigned mk, mp, mv, t; 
   int i; 

   x = x & m;           // Clear irrelevant bits. 
   mk = ~m << 1;        // We will count 0 to right. 

   for (i = 0; i < 5; i++) {
      mp = mk ^ (mk << 1);             // Parallel prefix. 
      mp = mp ^ (mp << 2); 
      mp = mp ^ (mp << 4); 
      mp = mp ^ (mp << 8); 
      mp = mp ^ (mp << 16); 
      mv = mp & m;                     // Bits to move. 
      m = m ^ mv | (mv >> (1 << i));   // Compress m. 
      t = x & mv; 
      x = x ^ t | (t >> (1 << i));     // Compress x. 
      mk = mk & ~mp; 
   } 
   return x; 
}

Обратите внимание, что многие значения зависят только от m. Поскольку у вас есть только 512 различных масок, вы можете прекомпилировать их и упростить код до чего-то вроде этого (не тестировалось).

unsigned compress(unsigned x, int maskindex) {
   unsigned t; 
   int i; 

   x = x & masks[maskindex][0];

   for (i = 0; i < 5; i++) {
      t = x & masks[maskindex][i + 1]; 
      x = x ^ t | (t >> (1 << i));
   } 
   return x; 
}

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

Ответ 2

Вы можете использовать метод пакетного умножения, аналогичный описанному здесь. Таким образом, вам не нужен какой-либо цикл.

Например, с маской 0b10101001 == 0xA9, как указано выше, и 8-битными данными abcdefgh (с a-h - 8 бит), вы можете использовать приведенное ниже выражение для получения 0000aceh

unsigned compress_maskA9(unsigned x)
{
    const unsigned mask  = 0xA9;
    const unsigned mask1 = mask & 0xF0;
    const unsigned mask2 = mask & 0x0F;
    return (((x & mask1)*0x03000000 >> 28) & 0x0C) | ((x & mask2)*0x50000000 >> 30);
}

В этом случае есть несколько перекрытий из 4 бит при умножении, поэтому я разделяю их на 2 части, первый извлекает бит a и c, тогда e и h будут извлечены во второй части.

Вы можете увидеть его результаты по сравнению с функцией Гарольда жить на ideone

Если вы хотите, чтобы бит результата был отменен, вы можете легко изменить магическое число соответственно.

unsigned compress_maskA9_reversed1(unsigned x)
{
    // result: he00 | 00ca;
    return (((x & 0x09)*0x88000000 >> 28) & 0x0C) | (((x & 0xA0)*0x04800000) >> 30);
}

или вы можете извлечь 3 бита e, c и a одновременно, оставив h отдельно из-за некоторых бит перекрытия:

unsigned compress_maskA9_reversed(unsigned x)
{
    return ((x & 0xA8)*0x12400000 >> 29) | (x & 0x01) << 3; // result: 0eca | h000
}

Проверка правильности: http://ideone.com/PYUkty

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

Объяснение

Имеем abcdefgh & mask1 = a0c00000

     ........................a0c00000
 x   00000011000000000000000000000000 (magic1 = 0x03000000)
 __________________________________________________________________
     a0c00000........................
 +  a0c00000......................... (the leading "a" bit is outside int range so it'll be truncated
     ↓↓ 
 __________________________________________________________________    
r1 = acc.............................

=> (r1 >> 28) & 0x0C = 0000ac00

Аналогично abcdefgh & mask2 = 0000e00h

        ........................0000e00h
x       01010000000000000000000000000000 (magic2 = 0x50000000)
__________________________________________________________________
    0000e00h............................
+ 0000e00h..............................
        ↓↓  
__________________________________________________________________    
   r2 = eh..............................

=> (r2 >> 30) = 000000eh

Поэтому

((r1 >> 28) & 0x0C) | (r2 >> 30) = 0000aceh