SSE 4 popcount для 16 8-битных значений?

У меня есть следующий код, который компилируется с помощью GCC с использованием флага -msse4, но проблема в том, что счетчик всплывающих окон получает только последние четыре 8 бита преобразованного типа __m128i. По сути, я хочу подсчитать все 16 чисел внутри типа __m128i, но я не уверен, какой встроенный вызов функции сделать после создания переменной popA. Каким-то образом popA должно быть преобразовано в целое число, содержащее все 128 бит информации? Я полагаю, что их _mm_cvtsi128_si64 и используется несколько операций в случайном порядке, но моя ОС 32-разрядная. Есть только метод перемешивания и использование _mm_cvtsi128_si32?

РЕДАКТИРОВАТЬ: Если метод перемешивания является единственным вариантом, мне нужна помощь в его реализации для моей 32-разрядной ОС, пожалуйста.

Вот код.

#include <stdio.h>
#include <smmintrin.h>
#include <emmintrin.h>

int main(void)
{
    int A = 1;
    __m128i popA = _mm_set_epi8( A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A);

    unsigned int integer = _mm_cvtsi128_si32(popA);
    //long long LONG = _mm_cvtsi128_si64(popA);//my OS is 32-bits so no luck here

    printf("integer = %d\n", integer);
    int pop = _mm_popcnt_u32(integer);
    //int popLONG = _mm_popcnt_u64(LONG);
    printf("popcount = %d\n", pop);
    //printf("popcount LONG = %d\n", popLONG);

    return 0;
}

РЕДАКТИРОВАТЬ 2: этот, наконец, запускается (с флагами компилятора GCC -msse -msse2 -msse3 -msse4), хотя я не уверен, что вывод для pop_count1() правильный.

Выход: pop_count1(): 1799 1799 1799 1799 1799 1799 1799 1799

pop_count2():population count for each byte: 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7

  #include <stdio.h>
#include <xmmintrin.h>
#include <emmintrin.h>
#include <mmintrin.h>
#include <stdint.h>
#include <tmmintrin.h>

void print128_num(__m128i var)
{
    uint16_t *val = (uint16_t*) &var;
    printf("pop_count1(): %i %i %i %i %i %i %i %i \n",
           val[0], val[1], val[2], val[3], val[4], val[5],
           val[6], val[7]);
}
static __m128i parallelPopcnt16bytes (__m128i xmm)//for pop_count2
{
    const __m128i mask4 = _mm_set1_epi8 (0x0F);
    const __m128i lookup = _mm_setr_epi8 (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
   __m128i low, high, count;

   low = _mm_and_si128 (mask4, xmm);
   high = _mm_and_si128 (mask4, _mm_srli_epi16 (xmm, 4));
   count = _mm_add_epi8 (_mm_shuffle_epi8 (lookup, low), _mm_shuffle_epi8 (lookup, high));
   return count;
}
void pop_count1()
{
    int A = 1;
    __m128i in = _mm_set_epi8( A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A);
    __m128i bit0 = _mm_set1_epi8( 0x80 );
    __m128i mask0 = _mm_and_si128( in, bit0 );
    __m128i sum = _mm_cmpeq_epi8( mask0, _mm_setzero_si128() );

/* general pattern */
    __m128i bit1 = _mm_set1_epi8( 0x40 );
    __m128i mask1 = _mm_and_si128( in, bit1 );
    mask1 = _mm_cmpeq_epi8( mask1, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask1 );

/* next bit */
    __m128i bit2 = _mm_set1_epi8( 0x20 );
    __m128i mask2 = _mm_and_si128( in, bit2 );
    mask2 = _mm_cmpeq_epi8( mask2, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask2 );

    __m128i bit3 = _mm_set1_epi8( 0x10 );
    __m128i mask3 = _mm_and_si128( in, bit3 );
    mask3 = _mm_cmpeq_epi8( mask3, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask3 );

    __m128i bit4 = _mm_set1_epi8( 0x08 );
    __m128i mask4 = _mm_and_si128( in, bit4 );
    mask4 = _mm_cmpeq_epi8( mask4, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask4 );

    __m128i bit5 = _mm_set1_epi8( 0x04 );
    __m128i mask5 = _mm_and_si128( in, bit5 );
    mask5 = _mm_cmpeq_epi8( mask5, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask5 );

    __m128i bit6 = _mm_set1_epi8( 0x02 );
    __m128i mask6 = _mm_and_si128( in, bit6 );
    mask6 = _mm_cmpeq_epi8( mask6, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask6 );

    __m128i bit7 = _mm_set1_epi8( 0x01 );
    __m128i mask7 = _mm_and_si128( in, bit7 );
    mask7 = _mm_cmpeq_epi8( mask7, _mm_setzero_si128() );
    sum = _mm_add_epi8( sum, mask7 );

/* finish up */
    sum = _mm_sub_epi8( _mm_setzero_si128(), sum );

    print128_num(sum);
}
void pop_count2()
{
    int index;
    __m128i testVector = _mm_set_epi8 (1, 2, 4, 8, 16, 32, 64, 128, 0, 1, 3, 7, 15, 31, 63, 127);
    __m128i counts = parallelPopcnt16bytes (testVector);

    printf ("pop_count2():population count for each byte:");
    for (index = 15; index >= 0; index--)
        {
        uint8_t *bytes = (void *) &counts;
        printf (" %d", bytes [index]);
        }
    printf ("\n");
}
int main(void)
{
    pop_count1();
    pop_count2();

    return 0;
}

person pandoragami    schedule 08.07.2013    source источник
comment
Вам нужен один подсчет населения для всего 128-битного вектора или вы хотите 16 подсчетов населения, по одному для каждого 8-битного элемента?   -  person Paul R    schedule 08.07.2013
comment
Что когда-либо имело бы больше смысла для эффективного использования. Теперь я полагаю, что использование встроенного счетчика всплывающих окон не очень хорошо для набора int, а также бесполезно в 32-разрядной ОС использовать 64-разрядные данные. popcnt — это не швейцарский армейский нож инструкций, который пока находится в зачаточном состоянии. Возможно, к SSE 5 это будет что-то отличное.   -  person pandoragami    schedule 08.07.2013
comment
@PaulR Мне это нужно для 8-битных значений.   -  person pandoragami    schedule 08.07.2013
comment
@ user2555139 Извините, это _mm_and(), а не _mm_andps. И последовательность 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01. На самом деле не имеет значения, в каком порядке вы их делаете, если вы используете каждое значение разряда ровно один раз.   -  person Potatoswatter    schedule 08.07.2013
comment
Я все еще получаю ту же ошибку с этой строкой __m128i mask0 = _mm_and( in, bit0 ); popcount.c|10|error: incompatible types when initializing type '__m128i' using type 'int'. Я добавил флаги -msse -msse2 -msse3 -msse4 и использую заголовки #include <stdio.h> #include <smmintrin.h> #include <emmintrin.h> #include <mmintrin.h> Что еще может быть?   -  person pandoragami    schedule 08.07.2013
comment
Я искал все связанные заголовки для _mm_and, и у них нет ни одного для __m128i, поэтому я думаю, что нет способа замаскировать int этого типа.   -  person pandoragami    schedule 08.07.2013
comment
Вам нужно _mm_and_si128   -  person Paul R    schedule 08.07.2013
comment
@PaulR @Potatoswatter. Я обновил РЕДАКТИРОВАТЬ 2 выше. Теперь он компилируется, хотя я не уверен в выводе суммы. Какие-либо предложения. Я также задавался вопросом, можно ли использовать метод перетасовки, чтобы поменять местами младшие 32 бита (0-31) со следующим (32-63) и выполнить подсчет, а затем поменять местами младшие 64 бита (0-63) с верхним и повторить то же самое для 32-бит? Вызов popcnt может одновременно видеть только самые правые 32 бита, поэтому 96-битные игнорируются во время каждой операции. Не очень эффективно, если вы спросите меня.   -  person pandoragami    schedule 08.07.2013


Ответы (2)


SSE 4 popcount для 16 8-битных значений может быть выполнен параллельно следующим образом:

#include <stdio.h>
#include <stdint.h>
#include <immintrin.h>

//----------------------------------------------------------------------------
//
// parallelPopcnt16bytes - find population count for 8-bit groups in xmm (16 groups)
//                         each byte of xmm result contains a value ranging from 0 to 8
//
static __m128i parallelPopcnt16bytes (__m128i xmm)
   {
    const __m128i mask4 = _mm_set1_epi8 (0x0F);
    const __m128i lookup = _mm_setr_epi8 (0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
   __m128i low, high, count;

   low = _mm_and_si128 (mask4, xmm);
   high = _mm_and_si128 (mask4, _mm_srli_epi16 (xmm, 4));
   count = _mm_add_epi8 (_mm_shuffle_epi8 (lookup, low), _mm_shuffle_epi8 (lookup, high));
   return count;
   }

//----------------------------------------------------------------------------

int main (void)
    {
    int index;
    __m128i testVector = _mm_set_epi8 (1, 2, 4, 8, 16, 32, 64, 128, 0, 1, 3, 7, 15, 31, 63, 127);
    __m128i counts = parallelPopcnt16bytes (testVector);

    printf ("population count for each byte:");
    for (index = 15; index >= 0; index--)
        {
        uint8_t *bytes = (void *) &counts;
        printf (" %d", bytes [index]);
        }
    printf ("\n");
    return 0;
    }

//----------------------------------------------------------------------------
person Community    schedule 08.07.2013
comment
Эта строка count = _mm_add_epi8 (_mm_shuffle_epi8 (lookup, low), _mm_shuffle_epi8 (lookup, high)); дает мне 2 ошибки. error: incompatible type for argument 1 of '_mm_add_epi8'| error: incompatible type for argument 2 of '_mm_add_epi8'| . Мне пришлось добавить #include <tmmintrin.h> с помощью GCC. - person pandoragami; 08.07.2013
comment
Помогло ли решить проблему добавление #include ‹tmmintrin.h›? Я тестировал этот код только с Microsoft VS2012 и mingw + gcc. - person ; 08.07.2013
comment
Очень хорошо - я только что закодировал почти идентичную процедуру, но вы меня опередили. Обратите внимание, что (по крайней мере, на процессорах Intel) для этого требуется только SSSE3 (для PSHUFB), а не SSE4, то есть #include <tmmintrin.h>. - person Paul R; 09.07.2013
comment
Красиво и быстро! Просто в комментарии каждый байт результата xmm содержит значение от 0 до 8. - person Potatoswatter; 09.07.2013
comment
Спасибо и спасибо за поправку. Я считаю, что заслуга в этом алгоритме принадлежит Войцеху Муле. Возможна адаптация AVX2 (notabs.org/blcutil), и она может быть даже быстрее, чем инструкция popcnt в некоторых случаи. - person ; 09.07.2013

popcnt был представлен одновременно с расширением ISA SSE4.2, но не работает с векторными регистрами SSE. Для каждого отдельного результата вам понадобится отдельная инструкция.

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

Вы можете суммировать 8 байтов за раз в 64-битных регистрах, но это не похоже на то, что вам нужно.

Ссылка: Руководство по SSE4 .

Решение SSE2.

Я не проверял это, но вы могли бы И SSE зарегистрироваться с 0x80808080… чтобы получить 16-байтовую маску всех 1 или всех 0. Повторите для всех 8 бит в байте и просуммируйте маски. Поскольку все единицы представляют собой -1 в дополнении до двух, инвертируйте 16 байтов, и вы получите все результаты.

Операции И и сравнения должны выполняться параллельно. Цепочка дополнений зависима, но она все равно должна выполняться достаточно быстро и умещается в 32 инструкции. (Требуется только 7 дополнений.)

/* init */
__m128i bit0 = _mm_set1_epi8( 0x80 );
__m128i mask0 = _mm_and_si128( in, bit0 );
__m128i sum = _mm_cmpeq_epi8( mask0, _mm_setzero_si128() );

/* general pattern */
__m128i bit1 = _mm_set1_epi8( 0x40 );
__m128i mask1 = _mm_and_si128( in, bit1 );
mask1 = _mm_cmpeq_epi8( mask1, _mm_setzero_si128() );
sum = _mm_add_epi8( sum, mask1 );

/* next bit */
__m128i bit2 = _mm_set1_epi8( 0x20 );
__m128i mask2 = _mm_and_si128( in, bit2 );
mask2 = _mm_cmpeq_epi8( mask2, _mm_setzero_si128() );
sum = _mm_add_epi8( sum, mask2 );

...

/* finish up */
sum = _mm_sub_epi8( _mm_setzero_si128(), sum );
person Potatoswatter    schedule 08.07.2013
comment
Это нормально. Думаю, я попробую popcount по-другому. - person pandoragami; 08.07.2013
comment
@ user2555139 8-кратный цикл с and, сравнение с нулем и добавление, а затем отрицание конечного результата должны быть в состоянии дать все 16 результатов за 26 инструкций и менее 26 циклов, поскольку итерации цикла не зависят. - person Potatoswatter; 08.07.2013
comment
Не могли бы вы закодировать эту часть для меня, пожалуйста? Я не совсем уверен, какие встроенные функции использовать. Все еще новичок в этом. - person pandoragami; 08.07.2013
comment
@ user2555139 см. редактирование. На самом деле это ~ 32 гостиницы, но кто считает. Я еще даже не пробовал ничего компилировать, отпишитесь, пожалуйста, работает ли и как быстро. - person Potatoswatter; 08.07.2013
comment
Я старался изо всех сил, см. мой пост выше для ошибок. Извините, я недостаточно компетентен, чтобы разобраться в их причинах. - person pandoragami; 08.07.2013