algorithm to quickly find a pattern in a block

[DiTBho]

Need to find an pattern, array of uint8_t, so it's "hex searching", in a large block.
Looking for the fastest method

Ummm, tempted to reuse what GNU/hexedit does, but first, let's look around ...

[tggzzz]

Need to find an pattern, array of uint8_t, so it's "hex searching", in a large block.
Looking for the fastest method

Ummm, tempted to reuse what GNU/hexedit does, but first, let's look around ...

Simple linear search of contiguous data, or regular expression pattern matching?

Bit/byte/word/etc alignment?

One way or another you will end up with a FSM, whether or not you realise it. Merely by thinking that way will suggest solutions.

[artag]

Are you looking for a specific pattern in terms of a sequence of bytes, or trying to find something unknown but repetitive such as a musical note in a digitised audio sample ?

The first might be a simple search but the second would have attributes of scaling in both amplitude and time and would probably be based on an autocorrelation.

[DiTBho]

Are you looking for a specific pattern in terms of a sequence of bytes,
or trying to find something unknown but repetitive such as a musical note in a digitised audio sample ?

sequence of bytes

[SiliconWizard]

If you don't care for performance, use a naive linear search.
But since your said "quickly", I recommend using what's been used for searching text for a few decades: the Knuth-Morris-Pratt algorithm.

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

[tggzzz]

Are you looking for a specific pattern in terms of a sequence of bytes,
or trying to find something unknown but repetitive such as a musical note in a digitised audio sample ?

sequence of bytes

ABCDE or A?CDE or A*E ?

[DiTBho]

ABCDE or A?CDE or A*E ?

good question, I need both 

it can be implemented with two different algorithms, in two different modules.
It will be part of a firmware I am writing, kind of debugging feature of a "monitor"
It needs to search things into buffer of ram and device buffer.

the bad thing is that they are not always strings
and that often, as you just pointed out, there can be small variations (*)

ABCDE -> A*CDE
(*) means whatever, 1 byte of freedom, covering 0x00 ... 0xff

[SiliconWizard]

KMP can be used on any series of integer values.

Adding wildcards though will require some changes.

[DiTBho]

If you don't care for performance, use a naive linear search.
But since your said "quickly", I recommend using what's been used for searching text for a few decades:
The Knuth-Morris-Pratt algorithm

uhm, I implemented the KMP-algo in my myC text editor myED.
I can reuse some of its code for the monitor/mips(1),
but this time it's not "substring search" but "hex search".
Even worse, with 1 byte of freedom.

(1) guess what for? for the damn rb532a router
hacking and reverse engineering is the only way ...

[tggzzz]

ABCDE or A?CDE or A*E ?

good question, I need both 

it can be implemented with two different algorithms, in two different modules.
It will be part of a firmware I am writing, kind of debugging feature of a "monitor"
It needs to search things into buffer of ram and device buffer.

the bad thing is that they are not always strings
and that often, as you just pointed out, there can be small variations (*)

ABCDE -> A*CDE
(*) means whatever, 1 byte of freedom, covering 0x00 ... 0xff

In many regexp libraries "?"=one, "*"=0 to many. The difference matters, hence the differences between grep, egrep and fgrep utilities.

[spostma]

the Boyer-Moore serach algorithm could be useful for you:
https://www.geeksforgeeks.org/boyer-moore-algorithm-for-pattern-searching/

[Analog Kid]

This is similar to a parsing problem.
My go-to method for parsing is to implement a state machine (technically a finite-state automaton or FSA). Easily coded: you have a loop that fetches the next character from the stream, then a jump table that dispatches to code stubs depending on the character seen (which can either be a single character or a class of characters, like numeric digits).

I use assembly language, but this can be done in any language, like C: it's driven by the jump table which has one row for each state, and columns corresponding to the character (or class of character) just seen.

[DiTBho]

the Boyer-Moore serach algorithm could be useful for you

going to implement it, thanks!

[benseno]

May be, comparing the sum (add here any operation with lowest cost resulting in quasi unique result) of character values within sliding window substring (whose length is equal ot the length of patter) to the sum of characters in the pattern. Fast shifting of sliding window can be done by subtracting the oldest element and adding a newest one.
Above can be applied to the strict patter check.
Utilizing platform dependent asm instructions can also help. And another approach is to use multiple cores for paralleling the task.
You can also check glogg - huge file viewer. It can efficiently search gigabytes big texts. 

[SiliconWizard]

If you don't care for performance, use a naive linear search.
But since your said "quickly", I recommend using what's been used for searching text for a few decades:
The Knuth-Morris-Pratt algorithm

uhm, I implemented the KMP-algo in my myC text editor myED.
I can reuse some of its code for the monitor/mips(1),
but this time it's not "substring search" but "hex search".

It's just a sequence of integers. What exactly do you see as a difference? You may of course have to change the data types but the algorithm is the same.

Even worse, with 1 byte of freedom.

Yes, as I mentioned, it's *the* difference: adding wildcards. But from what I get, your wildcards are restricted to 1 character only, so that should make it easier.
? probably means "any value" (but there must be exactly one in that place)
* usually means zero or more values (in your case, it would seem you only want 1 value of "freedom", so does that mean that the * is none, or any value?

[Tation]

https://www.google.fr/url?sa=t&source=web&rct=j&opi=89978449&url=https://igm.univ-mlv.fr/~lecroq/articles/cl2008.pdf&ved=2ahUKEwjpn5PZlsWLAxWITqQEHXWzDAMQFnoECCEQAQ&usg=AOvVaw3UPBGG_I-mK6Th2mO18Z3y

It seems that, from Boyer-Moore up, the "best" algorithm depends on exactly what kind of search is needed (size of alphabet, size of pattern...). The paper does not include the Knuth-Morris-Pratt, though.

In any case I wonder if there's much to gain implementing any of these against using any available search()/find() function in some common library.

[DiTBho]

It's just a sequence of integers. What exactly do you see as a difference?
You may of course have to change the data types but the algorithm is the same.

strings are managed by xx_string_compare(), which considers the special char '\0' has end of string.
hex-arrays should use xx_mem_compare(), which considers a pair of uint8 within a window

[Traceless]

the Boyer-Moore serach algorithm could be useful for you

going to implement it, thanks!

Let me save you some time there just use std::search.

[DiTBho]

It seems that, from Boyer-Moore up, the "best" algorithm depends on exactly what kind of search is needed (size of alphabet, size of pattern...).
The paper does not include the Knuth-Morris-Pratt, though.
In any case I wonder if there's much to gain implementing any of these against using any available search()/find() function in some common library.

eh, there are some constraints I didn't mention.
I'm not using a standard C compiler, but rather myC, myown C-like compiler.
This excludes C++ and existing standard-C libraries, unless they are "adapted".

[DiTBho]

This algo needs to do search from 32kbyte (hw buffer) up to 4Mbyte (rom0)
While the size of searching key is always less than 512byte.

Edit:
The CPU is a single core MIPS32 at 400Mhz, with 8Kbyte of D/I cache.

[Tation]

512 byte patterns are "long" patterns. In this case Backward Oracle Matching (BOM) algorithms and derivatives are thought to be the most efficient.

But I do not think that the benefit over Boyer-Moore (maybe around 50 % in selected cases, definitely not orders of magnitude) worths the effort.

[radiolistener]

Here is AI ChatGPT-4-turbo version (a little bit modified and fixed for better readability)

Code: [Select]

#include <stdio.h>
#include <stdint.h>


int indexOf(uint8_t *buffer, size_t bufferSize, uint8_t *pattern, size_t patternSize) {
    if (patternSize == 0 || bufferSize < patternSize) {
        return -1;
    }
    size_t badChar[256];
    for (size_t i = 0; i < 256; i++) {
        badChar[i] = patternSize;
    }
    for (size_t i = 0; i < patternSize - 1; i++) {
        badChar[pattern[i]] = patternSize - 1 - i;
    }
    size_t i = 0;
    while (i <= bufferSize - patternSize) {
        size_t j = patternSize - 1;
        while (j < patternSize && buffer[i + j] == pattern[j]) {
            if (j == 0) {
                return i; // Pattern found
            }
            j--;
        }
        i += badChar[buffer[i + patternSize - 1]]; // Shift using bad character rule
    }
    return -1; // Pattern not found
}


int main() {
    uint8_t buffer[] = {0x01, 0x02, 0x03, 0x04, 0x05, 0x00, 0x07, 0x08, 0x04, 0x05, 0x06, 0x07, 0x08};
    uint8_t pattern[] = {0x04, 0x05, 0x06};

    int result = indexOf(buffer, sizeof(buffer), pattern, sizeof(pattern));
    if (result < 0) {
        printf("Pattern not found\n");
    } else {
        printf("Pattern found at index: %d\n", result);
    }   

    return 0;
}


[radiolistener]

Here is AI Grok2 version, with no fixes:

Code: [Select]

int indexOf(uint8_t *buffer, size_t bufferSize, uint8_t *pattern, size_t patternSize) {
    if (bufferSize < patternSize) {
        return -1; // Pattern cannot fit in buffer
    }
    for (size_t i = 0; i <= bufferSize - patternSize; ++i) {
        if (memcmp(&buffer[i], pattern, patternSize) == 0) {
            return (int)i; // Match found, return index
        }
    }
    return -1; // Pattern not found
}

The same AI Grok2 with asking to not use memcmp:

Code: [Select]

int indexOf(uint8_t *buffer, size_t bufferSize, uint8_t *pattern, size_t patternSize) {
    if (bufferSize < patternSize) {
        return -1; // Pattern cannot fit in buffer
    }
    for (size_t i = 0; i <= bufferSize - patternSize; ++i) {
        size_t j;
        for (j = 0; j < patternSize; ++j) {
            if (buffer[i + j] != pattern[j]) {
                break; // No match, continue searching
            }
        }
        if (j == patternSize) {
            return (int)i; // Match found, return index
        }
    }
    return -1; // Pattern not found
}


[tggzzz]

Anybody who thinks feels posting LLM responses to technical questions is useful should read these two summaries of the competence of LLMs.

https://www.science.org/content/blog-post/evaluation-deep-research-performance

https://www.bbc.com/news/articles/c0m17d8827ko

[DiTBho]

Not interested in answers from chatGPT&C.
Don't post, please