Gli indici di byte diversi da zero di un registro SSE/AVX

Question

Se un valore del registro SSE/AVX è tale che tutti i suoi byte sono 0 o 1, esiste un modo per ottenere in modo efficiente gli indici di tutti gli elementi diversi da zero?

Ad esempio, se il valore xmm è | r0 = 0 | r1 = 1 | r2 = 0 | r3 = 1 | r4 = 0 | r5 = 1 | r6 = 0 | ... | r14 = 0 | r15 = 1 | il risultato dovrebbe essere qualcosa come (1, 3, 5, ..., 15). Il risultato dovrebbe essere inserito in un'altra variabile _m128i o char [16].

Se aiuta, possiamo presumere che il valore del registro sia tale che tutti i byte siano 0 o qualche valore diverso da zero costante (non necessario 1).

Mi chiedo se ci sia un'istruzione per questo o preferibilmente C/C++ intrinseco. In qualsiasi serie di istruzioni SSE o AVX.

EDIT 1:

E 'stato correttamente observed by @zx485 che domanda iniziale non era abbastanza chiaro. Stavo cercando una soluzione "consecutiva".

L'esempio 0 1 0 1 0 1 0 1... sopra dovrebbe comportare una delle seguenti operazioni:

• Se assumiamo che indici iniziano da 1, quindi 0 sarebbe un byte di terminazione e il risultato potrebbe essere

• Se assumiamo che byte negativo è una terminazione byte il risultato potrebbe essere

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

• Tutto , che fornisce come byte consecutivi che possiamo interpretare come indici di elementi diversi da zero nel valore originale

EDIT 2:

Infatti, come @harold e @Peter Cordes suggeriscono nei commenti al post originale, una delle possibili soluzioni consiste nel creare una maschera prima (ad esempio con pmovmskb) e controllare gli indici diversi da zero lì. Ma questo porterà ad un ciclo.

Answer 1

La domanda non è chiara per quanto riguarda l'aspetto se si desidera che l'array di risultati sia "compresso". Quello che intendo per "compresso" è che il risultato dovrebbe essere consecutivo.Così, ad esempio per 0 1 0 1 0 1 0 1..., ci sono due possibilità:

non consecutivi:

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

consecutiva:

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

Un problema dell'approccio successivo è: come si decide se è indice 0 o un valore di terminazione?

sto offrendo una soluzione semplice per il primo approccio non consecutive, che dovrebbe essere abbastanza veloce:

.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 

Solo per ragioni di completezza: il secondo, l'approccio consecutiva, non è coperto in questa risposta.

Answer 2

Risposta aggiornata: la nuova soluzione è leggermente più efficiente.

È possibile eseguire questa operazione senza un ciclo utilizzando l'istruzione pext da Bit Manipulation Instruction Set 2, in combinazione con poche altre istruzioni 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; 
} 

Sono necessarie circa cinque istruzioni per ottenere 0xFF (il byte di terminazione) nelle posizioni indesiderate. Si noti che una funzione nonz_index che restituisce gli indici e solo la posizione del byte di terminazione, senza effettivamente inserendo i byte di terminazione, sarebbe molto più economica da calcolare e potrebbe essere adatta in una particolare applicazione. La posizione del primo byte di terminazione è nnz64>>2.

Il risultato è:

$ ./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 

L'istruzione pext è supportato su processori Intel Haswell o più recente.