高效的算法在給定一個字節組<code>uint8_t data[N]</code>有點陣列

Question

找到一個字節是什麼內找到它的一個字節uint8_t search即使search沒有被字節對齊的有效方法？即search的前三位可以在data[i]和data[i+1]的接下來的5位中。

我的當前方法包括創建一個bool get_bit(const uint8_t* src, struct internal_state* state)函數（struct internal_state包含被bitshifted右，&版用src和返回的掩模，保持size_t src_index < size_t src_len），leftshifting返回的位轉換成uint8_t my_register和每次它與search進行比較，以及使用state->src_index和state->src_mask來獲取匹配字節的位置。

有沒有更好的方法呢？

Answer 1

我不知道是否會更好，但我會使用滑動窗口。

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; 

還與一些改動就可以使用該方法來搜索任意長度（1至64 array_element_size_in_bits）位序列。

Answer 2

我不認爲你可以在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; 
} 

的主要思想是，以處理由配對在字節跨連續字節之間的邊界案件的87.5％更寬的數據類型（在這種情況下爲uint16_t）。您可以調整它以使用更寬的數據類型，但我不確定這會獲得什麼。

你不能安全或容易地做的是涉及的任何事情通過指針（即(uint16_t *)&haystack[i]）將部分或全部數組轉換爲更寬的整數類型。無法保證這種演員陣容的正確對齊方式，也不能保證結果可能被解釋的字節順序。

Answer 3

如果您要在大型數組中搜索一個八位模式，您可以實現一個超過16位值的滑動窗口，以檢查搜索的模式是否構成該16位值的兩個字節的一部分。

爲了便於攜帶，您必須注意通過構建16位值來手動搜索模式來實現的排序問題。高字節總是當前迭代的字節，低字節是下一個字節。如果你做一個簡單的轉換像value = *((unsigned short *)pData)你會遇到的x86處理器上的麻煩......

一旦value，cmp和mask是建立cmp和mask移位。如果在hi高位字節中找不到模式，則循環繼續檢查下一個字節作爲起始字節。

這裏是我的執行，包括一些調試打印（該函數返回的位位置，或-1，如果沒有被發現模式）：

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

如果AVX2是可以接受的（與早期版本中，它沒有發揮出來如此好，但你仍然可以在那裏做點什麼），你可以同時在很多地方搜索。我無法在我的機器上進行測試（僅編譯），因此以下內容更多的是給你一個關於如何接近它的想法，而不是複製&粘貼代碼，所以我會試着解釋它，而不僅僅是代碼轉儲。

其主要思想是讀取一個uint64_t，通過所有有意義的值（0到7）將其右移，然後對於這8個新的uint64_t中的每一個，測試該字節是否在那裏。小併發症：對於uint64_t的偏移超過0，最高位置不應該被計數，因爲它有零位移入其中，可能不在實際數據中。一旦完成，下一個uint64_t應該在與當前偏移量相差7的位置處讀取，否則會有一個未檢查的邊界。這很好，但未對齊的負載不再那麼糟糕，特別是如果它們不寬的話。

所以現在對一些（未經測試，和不完整的，見下文）的代碼，

__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); 
    } 
} 

有趣「位索引和字節索引被交換」的事情是因爲四字內搜索是通過完成字節字節，並且這些比較的結果以8個相鄰位結束，而對於「移位1」的搜索結束於接下來的8個位中，依此類推。因此，在生成的掩碼中，包含1的字節索引是一個位偏移量，但該字節內的位索引實際上是字節偏移量，例如0x8000將對應於查找第7個字節的字節被右移1的qword，所以實際的索引是8 * 7 + 1。

還有一個「尾部」的問題，即所有7個字節的塊已經被處理時遺留的部分數據。它可以以相同的方式完成，但現在更多的位置包含假字節。現在剩下n - i個字節，所以掩碼必須在最低字節中設置n - i位，並且對於所有其他字節（由於與之前相同的原因，其他位置的位移爲零），一個字節要少一個。另外，如果確切地有1個字節「左」，它不會真的留下，因爲它已經被測試過了，但這並不重要。我會假設數據足夠填充以便訪問出界不重要。這是未經測試：

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

如果您正在尋找大量的內存，並且可以負擔得起昂貴的設置，另一種方法是使用一個64K的查找表。對於每個可能的16位值，該表存儲一個字節，其中包含發生匹配字節的位移位偏移量（+1，因此0可以表示不匹配）。你可以像這樣初始化：

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; 
      } 
     } 
    } 
} 

注意，其中值被轉移8位的情況下，不包括（之所以會在一分鐘內明顯）。

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; 
} 

進一步優化：

• 讀32或然而，許多位在同一時間從粒子陣列爲uint32_t的再移位和

  然後你可以通過你的字節數組這樣的掃描並且每次讀取第一個字節，或者進行索引和測試，然後讀取另一個4.

• 通過爲每個索引存儲一個nybble，將LUT包裝爲32K。這可能會幫助它擠入某些系統的緩存。

這將取決於您的內存架構，這是否比不使用查找表的展開循環更快。