thuật toán hiệu quả cho việc tìm kiếm một byte trong một mảng bit

Question

Cho một bytearray uint8_t data[N] một phương pháp hiệu quả để tìm một byte uint8_t search bên trong nó ngay cả khi search không được octet thẳng hàng là gì? tức là ba bit đầu tiên của search có thể ở số data[i] và 5 bit tiếp theo trong data[i+1].

phương pháp hiện tại của tôi liên quan đến việc tạo ra một hàm bool get_bit(const uint8_t* src, struct internal_state* state) (struct internal_state chứa một mặt nạ được bitshifted đúng, & ed với src và trở về, duy trì size_t src_index < size_t src_len), leftshifting các bit trở thành một uint8_t my_register và so sánh nó với search mọi thời gian, và sử dụng state->src_index và state->src_mask để nhận vị trí của byte phù hợp.

Có phương pháp nào tốt hơn cho điều này không?

Answer 1

Tôi không biết nếu nó sẽ tốt hơn, nhưng tôi sẽ sử dụng cửa sổ trượt.

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; 

Ngoài ra với một số thay đổi, bạn có thể sử dụng phương pháp này để tìm chuỗi bit dài tùy ý (1 đến 64-array_element_size_in_bits).

Answer 2

Tôi không nghĩ rằng bạn có thể làm tốt hơn nhiều so với điều này trong 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; 
} 

Ý tưởng chính là để xử lý 87,5% các trường hợp vượt qua biên giới giữa các byte liên tiếp bởi cặp byte trong loại dữ liệu rộng hơn (uint16_t trong trường hợp này). Bạn có thể điều chỉnh nó để sử dụng một loại dữ liệu rộng hơn, nhưng tôi không chắc chắn rằng sẽ đạt được bất cứ điều gì.

Điều bạn không thể làm một cách an toàn hoặc dễ dàng là bất kỳ thứ gì liên quan đến truyền một phần hoặc toàn bộ mảng của bạn sang loại số nguyên rộng hơn thông qua con trỏ (ví dụ: (uint16_t *)&haystack[i]). Bạn không thể đảm bảo sự liên kết thích hợp cho một dàn diễn viên như vậy, cũng không phải thứ tự byte mà kết quả có thể được diễn giải.

Answer 3

Nếu bạn đang tìm kiếm mẫu tám bit trong một mảng lớn, bạn có thể triển khai cửa sổ trượt trên giá trị 16 bit để kiểm tra xem mẫu tìm kiếm có phải là một phần của hai byte tạo thành giá trị 16 bit đó không.

Để di động, bạn phải quan tâm đến các vấn đề về cuối cùng được thực hiện bởi việc triển khai của tôi bằng cách tạo giá trị 16 bit để tìm kiếm mẫu theo cách thủ công. Byte cao luôn là byte được lặp hiện tại và byte thấp là byte sau. Nếu bạn làm một chuyển đổi đơn giản như value = *((unsigned short *)pData) bạn sẽ chạy vào rắc rối trên các bộ xử lý x86 ...

Khi value, cmp và mask được thiết lập cmp và mask được thay đổi. Nếu mẫu không được tìm thấy trong byte cao hi thì vòng lặp tiếp tục bằng cách kiểm tra byte tiếp theo dưới dạng byte bắt đầu.

Đây là thực hiện của tôi trong đó có một số bản in debug (hàm trả về vị trí bit hoặc -1 nếu mẫu không được tìm thấy):

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

Nếu AVX2 là chấp nhận được (với các phiên bản trước đó nó đã không làm việc ra rất tốt, nhưng bạn vẫn có thể làm điều gì đó ở đó), bạn có thể tìm kiếm ở rất nhiều địa điểm cùng một lúc.Tôi không thể kiểm tra điều này trên máy của tôi (chỉ biên dịch) vì vậy sau đây là nhiều hơn để cung cấp cho bạn một ý tưởng về cách nó có thể được tiếp cận hơn sao chép & dán mã, vì vậy tôi sẽ cố gắng giải thích nó hơn là chỉ mã-dump .

Ý tưởng chính là đọc uint64_t, dịch chuyển sang phải bởi tất cả các giá trị có ý nghĩa (0 đến 7), sau đó cho mỗi 8 giá trị mới uint64_t, kiểm tra xem byte có ở đó không. Biến chứng nhỏ: đối với sự thay đổi của uint64_t nhiều hơn 0, vị trí cao nhất sẽ không được tính vì nó có các số 0 được chuyển vào trong đó có thể không có trong dữ liệu thực tế. Một khi điều này được thực hiện, các uint64_t tiếp theo nên được đọc tại một bù đắp của 7 từ hiện tại, nếu không có một ranh giới không được kiểm tra trên. Đó là tốt mặc dù, tải trọng không phải là xấu như vậy nữa, đặc biệt là nếu họ không rộng.

Vì vậy, ngay bây giờ cho một số (chưa được kiểm tra, và không đầy đủ, xem dưới đây) mã,

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

Các funny "chút-index và byte-index đang hoán đổi" Vấn đề là vì tìm kiếm trong một qword được thực hiện byte bởi byte và kết quả của những so sánh đó kết thúc trong 8 bit liền kề, trong khi tìm kiếm "shifted by 1" kết thúc trong 8 bit tiếp theo và cứ tiếp tục như vậy. Vì vậy, trong các mặt nạ kết quả, chỉ mục của byte chứa 1 là bit-offset, nhưng bit-index trong byte đó thực sự là byte-offset, ví dụ 0x8000 sẽ tương ứng với việc tìm byte tại byte thứ 7 của qword đã được dịch chuyển sang phải 1, vì vậy chỉ số thực tế là 8 * 7 + 1.

Ngoài ra còn có vấn đề về "đuôi", phần dữ liệu còn lại khi tất cả các khối 7 byte đã được xử lý. Nó có thể được thực hiện nhiều theo cùng một cách, nhưng bây giờ nhiều vị trí hơn chứa các byte không có thật. Bây giờ n - i byte bị bỏ lại, vì vậy mặt nạ phải có n - i bit được đặt trong byte thấp nhất và ít hơn cho tất cả các byte khác (vì lý do tương tự như trước đó, các vị trí khác có số 0 được chuyển vào). Ngoài ra, nếu có chính xác 1 byte "trái", nó không thực sự còn lại bởi vì nó đã được thử nghiệm rồi, nhưng điều đó không thực sự quan trọng. Tôi sẽ giả sử dữ liệu đủ đệm để truy cập ngoài ranh giới không quan trọng. Tại đây, chưa được kiểm tra:

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

Nếu bạn đang tìm kiếm một lượng lớn bộ nhớ và có khả năng thiết lập đắt tiền, cách tiếp cận khác là sử dụng bảng tra cứu 64K. Đối với mỗi giá trị 16 bit có thể, bảng lưu trữ một byte chứa bit lệch bù mà tại đó octet phù hợp xảy ra (+1, do đó 0 có thể biểu thị không khớp). Bạn có thể khởi tạo nó như thế này:

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

Lưu ý rằng trường hợp giá trị được chuyển 8 bit không được bao gồm (lý do sẽ được rõ ràng trong một phút).

Sau đó, bạn có thể quét qua mảng của bạn byte như thế này:

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

Tiếp tục tối ưu hóa:

• đọc 32 hoặc tuy nhiên nhiêu bit tại một thời điểm từ PArray thành một uint32_t và sau đó thay đổi và VÀ mỗi lần lấy byte một lần, HOẶC có chỉ số và kiểm tra, trước khi đọc một số khác 4.
• Đóng gói LUT thành 32K bằng cách lưu trữ một nybble cho mỗi chỉ mục. Điều này có thể giúp nó ép vào bộ nhớ đệm trên một số hệ thống.

Nó sẽ phụ thuộc vào kiến ​​trúc bộ nhớ của bạn cho dù điều này nhanh hơn vòng lặp chưa được kiểm soát không sử dụng bảng tra cứu hay không.