SSE/AVX寄存器的非零字節索引

Question

如果一個SSE/AVX寄存器的值是所有字節都是0或1，那麼有什麼辦法可以有效地獲得所有非零元素的索引嗎？

例如，如果xmm值是 | r0 = 0 | r1 = 1 | r2 = 0 | r3 = 1 | r4 = 0 | r5 = 1 | r6 = 0 | ... | r14 = 0 | r15 = 1 | 結果應該是（1,3,5，...，15）。結果應放置在另一個_m128i變量或char [16]數組中。

如果有幫助，我們可以假設寄存器的值是所有字節都是0或某個恆定的非零值（不是必需的1）。

我很想知道是否有一個指令，或最好是C/C++內在。在任何SSE或AVX指令集中。

編輯1：

這是正確observed by @zx485是原來的問題還不夠清楚。我正在尋找任何「連續」解決方案。

上面的例子0 1 0 1 0 1 0 1...應導致下列任一：

• 如果我們假設指數從1開始，然後0將是終止字節，其結果可能是

• 如果我們假設負字節是終止字節的結果可能是

001 003 005 007 009 011 013 015爲0xFF 0xFF的0xFF的0xFF的0xFF的0xFF的0xFF的0xFF的

• 什麼，這給出了作爲連續字節，我們可以將其解釋爲原始值中的非零元素的索引

編輯2：

實際上，如@harold和@Peter Cordes建議在註釋到原來的職位，可能的解決方案之一是先創建的掩模（例如與pmovmskb）並在那裏檢查非零指數。但那會導致循環。

Answer 1

如果你想要結果數組是「壓縮的」，你的問題不清楚。我的意思是「壓縮」，結果應該是連續的。因此，例如用於0 1 0 1 0 1 0 1...，有兩種可能性：

非連續：

XMM0：000 001 000 003 000 005 000 007 000 009 000 011 000 013 000 015

連續：

XMM0：001 003 005 007 009 011 013 015 000 000 000 000 000 000 000

連續方法的一個問題是：您如何確定索引0或終止值？

我提供一個簡單的解決方案，第一，非連續的方式，這應該是相當快：

.data 
    ddqZeroToFifteen    db 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 
    ddqTestValue:     db 0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1 
.code 
    movdqa xmm0, xmmword ptr [ddqTestValue] 
    pxor xmm1, xmm1        ; zero XMM1 
    pcmpeqb xmm0, xmm1       ; set to -1 for all matching 
    pandn xmm0, xmmword ptr [ddqZeroToFifteen] ; invert and apply indices 

只是爲了完整起見：第二，連續的方式，不是蓋的在這個答案。

Answer 2

更新回答：新解決方案效率稍高。

您可以使用Bit Manipulation Instruction Set 2, 中的pext指令和其他幾條SSE指令結合使用，而無需循環。

/* 
gcc -O3 -Wall -m64 -mavx2 -march=broadwell ind_nonz_avx.c 
*/ 

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

__m128i nonz_index(__m128i x){ 
    /* Set some constants that will (hopefully) be hoisted out of a loop after inlining. */ 
    uint64_t indx_const = 0xFEDCBA;      /* 16 4-bit integers, all possible indices from 0 o 15               */ 
    __m128i cntr   = _mm_set_epi8(64,60,56,52,48,44,40,36,32,28,24,20,16,12,8,4); 
    __m128i pshufbcnst = _mm_set_epi8(0x80,0x80,0x80,0x80,0x80,0x80,0x80,0x80, 0x0E,0x0C,0x0A,0x08,0x06,0x04,0x02,0x00); 
    __m128i cnst0F  = _mm_set1_epi8(0x0F); 

    __m128i msk   = _mm_cmpeq_epi8(x,_mm_setzero_si128()); /* Generate 16x8 bit mask.                      */ 
      msk   = _mm_srli_epi64(msk,4);     /* Pack 16x8 bit mask to 16x4 bit mask.                   */ 
      msk   = _mm_shuffle_epi8(msk,pshufbcnst);   /* Pack 16x8 bit mask to 16x4 bit mask, continued.                */ 
    uint64_t msk64  = ~ _mm_cvtsi128_si64x(msk);     /* Move to general purpose register and invert 16x4 bit mask.              */ 

                     /* Compute the termination byte nonzmsk separately.                */ 
    int64_t nnz64  = _mm_popcnt_u64(msk64);     /* Count the nonzero bits in msk64.                    */ 
    __m128i nnz   = _mm_set1_epi8(nnz64);      /* May generate vmovd + vpbroadcastb if AVX2 is enabled.               */ 
    __m128i nonzmsk  = _mm_cmpgt_epi8(cntr,nnz);     /* nonzmsk is a mask of the form 0xFF, 0xFF, ..., 0xFF, 0, 0, ...,0 to mark the output positions without an index */ 

    uint64_t indx64  = _pext_u64(indx_const,msk64);    /* parallel bits extract. pext shuffles indx_const such that indx64 contains the nnz64 4-bit indices that we want.*/ 
    __m128i indx   = _mm_cvtsi64x_si128(indx64);    /* Use a few integer instructions to unpack 4-bit integers to 8-bit integers.          */ 
    __m128i indx_024  = indx;          /* Even indices.                         */ 
    __m128i indx_135  = _mm_srli_epi64(indx,4);     /* Odd indices.                         */ 
      indx   = _mm_unpacklo_epi8(indx_024,indx_135);  /* Merge odd and even indices.                     */ 
      indx   = _mm_and_si128(indx,cnst0F);    /* Mask out the high bits 4,5,6,7 of every byte.                 */ 

      return _mm_or_si128(indx,nonzmsk);      /* Merge indx with nonzmsk .                      */ 
} 


int main(){ 
    int i; 
    char w[16],xa[16]; 
    __m128i x; 

    /* Example with bytes 15, 12, 7, 5, 4, 3, 2, 1, 0 set. */ 
    x = _mm_set_epi8(1,0,0,1, 0,0,0,0, 1,0,1,1, 1,1,1,1); 

    /* Other examples. */ 
    /* 
    x = _mm_set_epi8(1,1,1,1, 1,1,1,1, 1,1,1,1, 1,1,1,1); 
    x = _mm_set_epi8(0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0); 
    x = _mm_set_epi8(1,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,0); 
    x = _mm_set_epi8(0,0,0,0, 0,0,0,0, 0,0,0,0, 0,0,0,1); 
    */ 
    __m128i indices = nonz_index(x); 
    _mm_storeu_si128((__m128i *)w,indices); 
    _mm_storeu_si128((__m128i *)xa,x); 

    printf("counter 15..0 ");for (i=15;i>-1;i--) printf(" %2d ",i);  printf("\n\n"); 
    printf("example xmm: ");for (i=15;i>-1;i--) printf(" %2d ",xa[i]); printf("\n"); 
    printf("result in dec ");for (i=15;i>-1;i--) printf(" %2hhd ",w[i]); printf("\n"); 
    printf("result in hex ");for (i=15;i>-1;i--) printf(" %2hhX ",w[i]); printf("\n"); 

    return 0; 
} 

大約需要五條指令才能在不需要的位置得到0xFF（終止字節）。 請注意，函數nonz_index（返回索引並且僅返回終止字節的位置，實際上不插入終止字節）可能會便宜得多，並且可能適合在特定應用程序中使用。 第一個終止字節的位置是nnz64>>2。

結果是：

$ ./a.out 
counter 15..0 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

example xmm: 1 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 
result in dec -1 -1 -1 -1 -1 -1 -1 15 12 7 5 4 3 2 1 0 
result in hex FF FF FF FF FF FF FF F C 7 5 4 3 2 1 0 

的pext指令支持英特爾的Haswell處理器或更新的版本。