algoritmo efficiente per la ricerca di un byte in una matrice di bit

Question

Dato un ByteArray uint8_t data[N] ciò che è un metodo efficace per trovare un byte uint8_t search all'interno di esso anche se non è search ottetto allineati? cioè i primi tre bit di search potrebbero essere in data[i] e i successivi 5 bit in data[i+1].

mio metodo attuale prevede la creazione di una funzione bool get_bit(const uint8_t* src, struct internal_state* state) (struct internal_state contiene una maschera che viene bitshifted destra, & ED con src e restituito, mantenendo size_t src_index < size_t src_len), leftshifting i bit restituiti in un uint8_t my_register e confrontandolo con search ogni volta, e usando state->src_index e state->src_mask per ottenere la posizione del byte corrispondente.

Esiste un metodo migliore per questo?

Answer 1

Non so se sarebbe meglio, ma vorrei usare la finestra scorrevole.

uint counter = 0, feeder = 8; 
uint window = data[0]; 

while (search^(window & 0xff)){ 
    window >>= 1; 
    feeder--; 
    if (feeder < 8){ 
     counter++; 
     if (counter >= data.length) { 
      feeder = 0; 
      break; 
     } 
     window |= data[counter] << feeder; 
     feeder += 8; 
    } 
} 

//Returns index of first bit of first sequence occurrence or -1 if sequence is not found 
return (feeder > 0) ? (counter+1)*8-feeder : -1; 

Anche con alcune modifiche è possibile utilizzare questo metodo per verificare la lunghezza arbitraria (da 1 a 64-array_element_size_in_bits) bit sequenza.

Answer 2

Non credo che si può fare molto meglio di questo in C:

/* 
* Searches for the 8-bit pattern represented by 'needle' in the bit array 
* represented by 'haystack'. 
* 
* Returns the index *in bits* of the first appearance of 'needle', or 
* -1 if 'needle' is not found. 
*/ 
int search(uint8_t needle, int num_bytes, uint8_t haystack[num_bytes]) { 
    if (num_bytes > 0) { 
     uint16_t window = haystack[0]; 

     if (window == needle) return 0; 
     for (int i = 1; i < num_bytes; i += 1) { 
      window = window << 8 + haystack[i]; 

      /* Candidate for unrolling: */ 
      for (int j = 7; j >= 0; j -= 1) { 
       if ((window >> j) & 0xff == needle) { 
        return 8 * i - j; 
       } 
      } 
     } 
    } 
    return -1; 
} 

L'idea principale è quella di gestire il 87,5% dei casi che attraversano il confine tra byte consecutivi da accoppiamento byte un tipo di dati più ampio (uint16_t in questo caso). Potresti regolarlo per usare un tipo di dati ancora più ampio, ma non sono sicuro che otterrebbe qualcosa.

Quello che non si può in modo sicuro o facilmente fare qualcosa che coinvolge fusione parte o di tutto l'array a un tipo intero più ampio tramite un puntatore (cioè (uint16_t *)&haystack[i]). Non è possibile garantire il corretto allineamento per tale cast, né l'ordine dei byte con il quale il risultato potrebbe essere interpretato.

Answer 3

Se si sta cercando un modello a otto bit in un grande array, è possibile implementare una finestra scorrevole su valori a 16 bit per verificare se il modello cercato è parte dei due byte che formano quel valore a 16 bit.

Per essere portatili, è necessario occuparsi dei problemi di endianness che vengono eseguiti dalla mia implementazione costruendo il valore a 16 bit per cercare manualmente il modello. Il byte alto è sempre il byte attualmente iterato e il byte basso è il seguente byte. Se fate una semplice conversione come value = *((unsigned short *)pData) si esegue in difficoltà su processori x86 ...

volta value, cmp e mask sono configurazione cmp e mask sono spostati. Se il pattern non è stato trovato entro hi high byte, il loop continua controllando il byte successivo come byte iniziale.

Qui è la mia implementazione tra cui alcune stampe di debug (la funzione restituisce la posizione del bit o -1 se modello non è stato trovato):

int findPattern(unsigned char *data, int size, unsigned char pattern) 
{ 
    int result = -1; 
    unsigned char *pData; 
    unsigned char *pEnd; 
    unsigned short value; 
    unsigned short mask; 
    unsigned short cmp; 
    int tmpResult; 



    if ((data != NULL) && (size > 0)) 
    { 
     pData = data; 
     pEnd = data + size; 

     while ((pData < pEnd) && (result == -1)) 
     { 
      printf("\n\npData = {%02x, %02x, ...};\n", pData[0], pData[1]); 

      if ((pData + 1) < pEnd) /* still at least two bytes to check? */ 
      { 
       tmpResult = (int)(pData - data) * 8; /* calculate bit offset according to current byte */ 

       /* avoid endianness troubles by "manually" building value! */ 
       value = *pData << 8; 
       pData++; 
       value += *pData; 

       /* create a sliding window to check if search patter is within value */ 
       cmp = pattern << 8; 
       mask = 0xFF00; 
       while (mask > 0x00FF) /* the low byte is checked within next iteration! */ 
       { 
        printf("cmp = %04x, mask = %04x, tmpResult = %d\n", cmp, mask, tmpResult); 

        if ((value & mask) == cmp) 
        { 
         result = tmpResult; 
         break; 
        } 

        tmpResult++; /* count bits! */ 
        mask >>= 1; 
        cmp >>= 1; 
       } 
      } 
      else 
      { 
       /* only one chance left if there is only one byte left to check! */ 
       if (*pData == pattern) 
       { 
        result = (int)(pData - data) * 8; 
       } 

       pData++; 
      } 
     } 
    } 

    return (result); 
} 

Answer 4

Se AVX2 è accettabile (con le versioni precedenti non ha funzionato fuori così bene, ma puoi ancora fare qualcosa lì), puoi cercare in molti posti allo stesso tempo.Non ho potuto testarlo sulla mia macchina (solo compilare) quindi il seguente è più per darti un'idea di come potrebbe essere affrontato che copiare il codice di scrittura &, quindi cercherò di spiegarlo piuttosto che solo il dump del codice .

L'idea principale è quella di leggere uno uint64_t, spostarlo verso destra da tutti i valori che hanno senso (da 0 a 7), quindi per ciascuno di questi 8 nuovi uint64_t, verificare se il byte è lì dentro. Piccola complicazione: per lo uint64_t spostato di più di 0, la posizione più alta non dovrebbe essere conteggiata poiché ha degli zeri spostati in esso che potrebbero non essere nei dati effettivi. Una volta fatto, il prossimo uint64_t dovrebbe essere letto con un offset di 7 rispetto a quello corrente, altrimenti c'è un confine che non viene controllato attraverso. Va bene però, i carichi non allineati non sono più così male, soprattutto se non sono larghi.

Così ora per un po 'di codice (non testato, e incompleta, vedi sotto),

__m256i needle = _mm256_set1_epi8(find); 
size_t i; 
for (i = 0; i < n - 6; i += 7) { 
    // unaligned load here, but that's OK 
    uint64_t d = *(uint64_t*)(data + i); 
    __m256i x = _mm256_set1_epi64x(d); 
    __m256i low = _mm256_srlv_epi64(x, _mm256_set_epi64x(3, 2, 1, 0)); 
    __m256i high = _mm256_srlv_epi64(x, _mm256_set_epi64x(7, 6, 5, 4)); 
    low = _mm256_cmpeq_epi8(low, needle); 
    high = _mm256_cmpeq_epi8(high, needle); 
    // in the qword right-shifted by 0, all positions are valid 
    // otherwise, the top position corresponds to an incomplete byte 
    uint32_t lowmask = 0x7f7f7fffu & _mm256_movemask_epi8(low); 
    uint32_t highmask = 0x7f7f7f7fu & _mm256_movemask_epi8(high); 
    uint64_t mask = lowmask | ((uint64_t)highmask << 32); 
    if (mask) { 
     int bitindex = __builtin_ffsl(mask); 
     // the bit-index and byte-index are swapped 
     return 8 * (i + (bitindex & 7)) + (bitindex >> 3); 
    } 
} 

Il divertente "bit-index e byte-index sono scambiati" cosa è perché la ricerca all'interno di un QWORD è fatto di byte da byte e i risultati di tali confronti finiscono in 8 bit adiacenti, mentre la ricerca di "spostati di 1" finisce negli 8 bit successivi e così via. Quindi nelle maschere risultanti, l'indice del byte che contiene l'1 è un offset di bit, ma l'indice di bit all'interno di quel byte è in realtà l'offset di byte, ad esempio 0x8000 corrisponderebbe alla ricerca del byte al settimo byte di il qword che è stato spostato a destra di 1, quindi l'indice attuale è 8 * 7 + 1.

C'è anche il problema della "coda", la parte dei dati rimasti quando tutti i blocchi di 7 byte sono stati elaborati. Può essere fatto allo stesso modo, ma ora più posizioni contengono byte fasulli. Ora i byte n - i sono rimasti, quindi la maschera deve avere i bit n - i impostati nel byte più basso e uno in meno per tutti gli altri byte (per lo stesso motivo di prima, le altre posizioni hanno gli zero spostati in). Inoltre, se c'è esattamente 1 byte "a sinistra", non è veramente lasciato perché sarebbe già stato testato, ma non importa. Immagino che i dati siano sufficientemente imbottiti che l'accesso fuori limite non ha importanza. Qui si tratta, non testato:

if (i < n - 1) { 
    // make n-i-1 bits, then copy them to every byte 
    uint32_t validh = ((1u << (n - i - 1)) - 1) * 0x01010101; 
    // the lowest position has an extra valid bit, set lowest zero 
    uint32_t validl = (validh + 1) | validh; 
    uint64_t d = *(uint64_t*)(data + i); 
    __m256i x = _mm256_set1_epi64x(d); 
    __m256i low = _mm256_srlv_epi64(x, _mm256_set_epi64x(3, 2, 1, 0)); 
    __m256i high = _mm256_srlv_epi64(x, _mm256_set_epi64x(7, 6, 5, 4)); 
    low = _mm256_cmpeq_epi8(low, needle); 
    high = _mm256_cmpeq_epi8(high, needle); 
    uint32_t lowmask = validl & _mm256_movemask_epi8(low); 
    uint32_t highmask = validh & _mm256_movemask_epi8(high); 
    uint64_t mask = lowmask | ((uint64_t)highmask << 32); 
    if (mask) { 
     int bitindex = __builtin_ffsl(mask); 
     return 8 * (i + (bitindex & 7)) + (bitindex >> 3); 
    } 
} 

Answer 5

Se siete alla ricerca di una grande quantità di memoria e può permettersi un setup costoso, un altro approccio è quello di utilizzare una tabella di ricerca 64K. Per ogni possibile valore a 16 bit, la tabella memorizza un byte contenente l'offset di spostamento del bit a cui si verifica l'ottetto corrispondente (+1, quindi 0 può indicare nessuna corrispondenza). È possibile inizializzare in questo modo:

uint8_t* g_pLookupTable = malloc(65536); 
void initLUT(uint8_t octet) 
{ 
    memset(g_pLookupTable, 0, 65536); // zero out 
    for(int i = 0; i < 65536; i++) 
    {   
     for(int j = 7; j >= 0; j--) 
     { 
      if(((i >> j) & 255) == octet) 
      { 
       g_pLookupTable[i] = j + 1; 
       break; 
      } 
     } 
    } 
} 

Si noti che il caso in cui il valore viene spostato di 8 bit non è incluso (la ragione sarà evidente in un minuto).

Quindi è possibile eseguire la scansione attraverso il vostro array di byte in questo modo:

int findByteMatch(uint8_t* pArray, uint8_t octet, int length) 
{ 
    if(length >= 0) 
    { 
     uint16_t index = (uint16_t)pArray[0]; 
     if(index == octet) 
      return 0; 
     for(int bit, i = 1; i < length; i++) 
     { 
      index = (index << 8) | pArray[i]; 
      if(bit = g_pLookupTable[index]) 
       return (i * 8) - (bit - 1); 
     } 
    } 
    return -1; 
} 

ulteriore ottimizzazione:

• Leggi 32 o comunque molti bit alla volta da Parray in un uint32_t e poi cambiare e E ognuno per ottenere il byte uno alla volta, OPPURE con indice e test, prima di leggerne un altro 4.
• Comprimere il LUT in 32K memorizzando un nybble per ogni indice. Questo potrebbe aiutare a spremere nella cache su alcuni sistemi.

Dipenderà dall'architettura della memoria se è più veloce di un ciclo srotolato che non utilizza una tabella di ricerca.