Поиск байтового шаблона в потоке буферизованных данных - PullRequest
Новая
       82

Поиск байтового шаблона в потоке буферизованных данных

0 голосов
/ 21 марта 2020

Я хочу найти последовательность байтов, которые я получаю порциями (поочередно), как и когда такие данные доступны. Например, шаблон байтов 0xbbffbbffbb. Нет никакой гарантии, что этот шаблон будет получен в полном объеме, поэтому простое выполнение команды не может быть решением. Какой алгоритм я могу использовать для поиска этого шаблона? Мой подход заключается в поиске первого байта (в данном случае 0xbb), затем убедитесь, что у меня есть еще 4 байта, а затем сравните его со строкой. Хотя происходит сбой, если после двух байтов имеются некоторые данные мусора, скажем, 0xbbff01 [bbffbbffbb].

Мой код (извините, если потертый) выглядит так: 

char* pattern_search(char* buff, size_t *bytes_read)
{
    char* ptr = buff;
    uint16_t remaining_length = *bytes_read;

    while(1) {

        // look for one byte in the stream
        char* pattern_start = memmem((void*)ptr, remaining_length, 0xbb, 1);

        if (pattern_start == NULL) {
            // printf("nothing found\n");
            return NULL;
        }

        int pos = pattern_start - ptr;
        remaining_length = remaining_length - pos;
        ptr = pattern_start;

        // see if you have 5 bytes to compare, if not get more
        remaining_length += get_additional_bytes();

        // compare 5 bytes for pattern
        pattern_start = memmem((void*)ptr, remaining_length, start_flag, PATTERN_LEN);
        if (pattern_start == NULL) {
            // move one step and continue search
            ptr++;
            remaining_length--;
            // move these bytes back to beginning of the buffer
            memcpy(buff, ptr, remaining_length);
            ptr = buff;
            *bytes_read = remaining_length;
            if (remaining_length > 0) {
                continue;
            } else {
                return NULL;
            }
        } else {
            // found!
            printf("pattern found!\n");
            ptr = pattern_start;
            break;
        }
    }

    return ptr;
}

1 Ответ

1 голос
/ 22 марта 2020

Здесь можно найти много разных решений. Можно указать:

  • указать шаблон как массив без знака
  • вызов функции 'input_received' с полученными блоками данных и указателем на функцию обратного вызова, которая вызывается всякий раз, когда шаблон найден

Это может выглядеть следующим образом: 

#include <stdio.h>

static unsigned const char PATTERN[] = {0xbb, 0xff, 0xbb, 0xff, 0xbb};

static void found(size_t pos) {
    printf("pattern found at index %zu\n", pos);
}

static void input_received(const unsigned char *const data,
                           int n,
                           void (*callback)(size_t)) {
    static int match_count;
    static size_t position;

    for (int i = 0; i < n; i++, position++) {
        if (data[i] == PATTERN[match_count]) {
            match_count++;
        } else {
            match_count = data[i] == PATTERN[0] ? 1 : 0;
        }
        if (match_count == sizeof PATTERN) {
            (*callback)(position - sizeof PATTERN + 1);
            match_count = 0;
        }
    }
}

int main(void) {

    unsigned char input[] = {0xff, 0x01, 0x02, 0xff, 0x00,
                             0xbb, 0xff, 0xbb, 0xff, 0xbb,
                             0xbb, 0xff, 0xbb, 0xff, 0xbb};

    input_received(input, 2, found);
    input_received(&input[2], 3, found);
    input_received(&input[5], 2, found);
    input_received(&input[7], 2, found);
    input_received(&input[9], 5, found);
    input_received(&input[14], 1, found);

    return 0;
}

Test

После этого в отладке будет выведено следующее консоль: 

pattern found at index 5
pattern found at index 10
...