ndpi_memmem: optimized, fixed bug, added tests (#2499)

2 files changed, 58 insertions, 8 deletions

diff --git a/example/ndpiReader.c b/example/ndpiReader.c
index 65246c05c..1422e3dfb 100644
--- a/example/ndpiReader.c
+++ b/example/ndpiReader.c
@@ -5793,6 +5793,53 @@ void strnstrUnitTest(void) {
 
 /* *********************************************** */
 
+void memmemUnitTest(void) {
+  /* Test 1: null string */
+  assert(ndpi_memmem(NULL, 0, NULL, 0) == NULL);
+  assert(ndpi_memmem(NULL, 0, NULL, 10) == NULL);
+  assert(ndpi_memmem(NULL, 0, "find", 10) == NULL);
+  assert(ndpi_memmem(NULL, 10, "find", 10) == NULL);
+  assert(ndpi_memmem("string", 10, NULL, 0) == NULL);
+  assert(ndpi_memmem("string", 10, NULL, 10) == NULL);
+
+  /* Test 2: zero length */
+  assert(strcmp(ndpi_memmem("", 0, "", 0), "") == 0);
+  assert(strcmp(ndpi_memmem("string", 6, "", 0), "string") == 0);
+  assert(strcmp(ndpi_memmem("string", 0, "", 0), "string") == 0);
+  assert(ndpi_memmem("", 0, "string", 6) == NULL);
+
+  /* Test 3: empty substring */
+  assert(strcmp(ndpi_memmem("string", 6, "", 0), "string") == 0);
+
+  /* Test 4: single character substring */
+  assert(strcmp(ndpi_memmem("string", 6, "r", 1), "ring") == 0);
+  assert(ndpi_memmem("string", 6, "x", 1) == NULL);
+
+  /* Test 5: multiple character substring */
+  assert(strcmp(ndpi_memmem("string", 6, "ing", 3), "ing") == 0);
+  assert(ndpi_memmem("string", 6, "xyz", 3) == NULL);
+
+  /* Test 6: substring equal to the beginning of the string */
+  assert(strcmp(ndpi_memmem("string", 6, "str", 3), "string") == 0);
+
+  /* Test 7: substring at the end of the string */
+  assert(strcmp(ndpi_memmem("string", 6, "ing", 3), "ing") == 0);
+
+  /* Test 8: substring in the middle of the string */
+  assert(strcmp(ndpi_memmem("hello world", strlen("hello world"), "lo wo", strlen("lo wo")), "lo world") == 0);
+
+  /* Test 9: repeated characters in the string */
+  assert(strcmp(ndpi_memmem("aaaaaa", 6, "aaa", 3), "aaaaaa") == 0);
+
+  /* Test 10: substring equal to the string */
+  assert(strcmp(ndpi_memmem("string", 6, "string", 6), "string") == 0);
+
+  /* Test 11: substring longer than the string */
+  assert(ndpi_memmem("string", 6, "stringA", 7) == NULL);
+}
+
+/* *********************************************** */
+
 void filterUnitTest() {
   ndpi_filter* f = ndpi_filter_alloc();
   u_int32_t v, i;
@@ -6160,6 +6207,7 @@ int main(int argc, char **argv) {
     strtonumUnitTest();
     strlcpyUnitTest();
     strnstrUnitTest();
+    memmemUnitTest();
 #endif
   }
 
diff --git a/src/lib/ndpi_main.c b/src/lib/ndpi_main.c
index fb8c113c9..5c1596ba2 100644
--- a/src/lib/ndpi_main.c
+++ b/src/lib/ndpi_main.c
@@ -11437,29 +11437,31 @@ char *ndpi_dump_config(struct ndpi_detection_module_struct *ndpi_str,
 
 void* ndpi_memmem(const void* haystack, size_t haystack_len, const void* needle, size_t needle_len)
 {
-  if (!haystack || !needle || haystack_len < needle_len || needle_len == 0) {
+  if (!haystack || !needle || haystack_len < needle_len) {
     return NULL;
   }
 
+  if (needle_len == 0) {
+    return (void *)haystack;
+  }
+
   if (needle_len == 1) {
     return (void *)memchr(haystack, *(const u_int8_t *)needle, haystack_len);
   }
 
-  const u_int8_t *current = (const u_int8_t *)haystack;
-  const u_int8_t *haystack_end = (const u_int8_t *)haystack + haystack_len;
+  const u_int8_t *const end_of_search = (const u_int8_t *)haystack + haystack_len - needle_len + 1;
 
-  while (current <= haystack_end - needle_len) {
+  const u_int8_t *current = (const u_int8_t *)haystack;
+  while (current < end_of_search) {
     /* Find the first occurrence of the first character from the needle */
-    current = (const u_int8_t *)memchr(current, *(const u_int8_t *)needle,
-                                       haystack_end - current);
+    current = (const u_int8_t *)memchr(current, *(const u_int8_t *)needle, end_of_search - current);
 
     if (!current) {
       return NULL;
     }
 
     /* Check the rest of the needle for a match */
-    if ((current + needle_len <= haystack_end) &&
-        (memcmp(current, needle, needle_len) == 0)) {
+    if (memcmp(current, needle, needle_len) == 0) {
       return (void *)current;
     }