How to check if (Sub)Array exists in Array

Question

I need something between strstr and memcmp for checking if an array exists in a range of memory.

Example what I want to achieve:

BYTE a[] = { 0x01, 0x02, 0x03, 0x04 };
BYTE b[] = { 0x02, 0x03 };
if (mem_in_mem(a, b, 4 * sizeof(BYTE)) == 0) {
    printf("b is in memory range of a\n");
}

Any ideas how I can something like that? (Should work with windows)

You could write that function, sure. Why not memcmp and advance a character each time until you've checked the whole buffer? — tadman
– tadman, Commented Mar 7, 2017 at 20:31
Unfortunately, the proposed mem_in_mem function is not told the length of the (Sub)Array it is supposed to match. — Weather Vane
– Weather Vane, Commented Mar 7, 2017 at 20:37
Optimise by checking the first byte before committing to an expensive function call to memcmp. — Weather Vane
– Weather Vane, Commented Mar 7, 2017 at 20:39
At looks like perhaps you want to implement the KMP algorithm. Any way around, though, the function needs a way to know the boundaries of both the target array and the test array. — John Bollinger
– John Bollinger, Commented Mar 7, 2017 at 20:39
@immibis in your library, perhaps, but it still requires a function call which can be avoided if the simple test fails. — Weather Vane
– Weather Vane, Commented Mar 7, 2017 at 20:43

chqrlie · Accepted Answer · 2017-03-07 20:46:35Z

4

The function mem_in_mem should take the size of both arrays. Here is a simplistic implementation:

#include <string.h>

void *mem_in_mem(const void *haystack, size_t n1, const void *needle, size_t n2) {
    const unsigned char *p1 = haystack;
    const unsigned char *p2 = needle;

    if (n2 == 0)
        return (void*)p1;
    if (n2 > n1)
        return NULL;

    const unsigned char *p3 = p1 + n1 - n2 + 1;
    for (const unsigned char *p = p1; (p = memchr(p, *p2, p3 - p)) != NULL; p++) {
        if (!memcmp(p, p2, n2))
            return (void*)p;
    }
    return NULL;
}

You would invoke it this way:

BYTE a[] = { 0x01, 0x02, 0x03, 0x04 };
BYTE b[] = { 0x02, 0x03 };
if (mem_in_mem(a, sizeof a, b, sizeof b)) {
    printf("b is in memory range of a\n");
}

answered Mar 7, 2017 at 20:46

chqrlie

152k12 gold badges145 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

chux Over a year ago

Just as int *ptr = malloc(8); does not need a cast, neither does return (void*)p; Perhaps window's C is picky?

chux Over a year ago

Ah, I see the need for the cast, to discard the const!

Collectives™ on Stack Overflow

How to check if (Sub)Array exists in Array

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related