Optimize performance of ndpi_strnstr() and possible bugfix (#2494)

3 files changed, 64 insertions, 13 deletions

diff --git a/example/ndpiReader.c b/example/ndpiReader.c
index dd908e5ce..65246c05c 100644
--- a/example/ndpiReader.c
+++ b/example/ndpiReader.c
@@ -5782,6 +5782,13 @@ void strnstrUnitTest(void) {
 
   /* Test 13 */
   assert(ndpi_strnstr("abcdef", "abc", 2) == NULL);
+
+  /* Test 14: zero length */
+  assert(strcmp(ndpi_strnstr("", "", 0), "") == 0);
+  assert(strcmp(ndpi_strnstr("string", "", 0), "string") == 0);
+  assert(ndpi_strnstr("", "str", 0) == NULL);
+  assert(ndpi_strnstr("string", "str", 0) == NULL);
+  assert(ndpi_strnstr("str", "string", 0) == NULL);
 }
 
 /* *********************************************** */
diff --git a/src/lib/ndpi_main.c b/src/lib/ndpi_main.c
index ad07d0f86..fb8c113c9 100644
--- a/src/lib/ndpi_main.c
+++ b/src/lib/ndpi_main.c
@@ -9737,47 +9737,48 @@ void ndpi_dump_risks_score(FILE *risk_out) {
 
 char *ndpi_strnstr(const char *haystack, const char *needle, size_t len)
 {
-  if (!haystack || !needle || len == 0)
+  if (!haystack || !needle)
   {
     return NULL;
   }
 
-  size_t needle_len = strlen(needle);
-  size_t hs_real_len = strnlen(haystack, len);
+  const size_t needle_len = strlen(needle);
 
   if (needle_len == 0)
   {
     return (char *)haystack;
   }
 
-  if (needle_len > hs_real_len)
-  {
-    return NULL;
-  }
+  const size_t hs_real_len = strnlen(haystack, len);
 
   if (needle_len == 1)
   {
     return (char *)memchr(haystack, *needle, hs_real_len);
   }
 
-  const char *current = haystack;
-  const char *haystack_end = haystack + hs_real_len;
+  if (needle_len > hs_real_len)
+  {
+    return NULL;
+  }
 
-  while (current <= haystack_end - needle_len)
+  const char *const end_of_search = haystack + hs_real_len - needle_len + 1;
+
+  const char *current = haystack;
+  while (current < end_of_search)
   {
-    current = (const char *)memchr(current, *needle, haystack_end - current);
+    current = (const char *)memchr(current, *needle, end_of_search - current);
 
     if (!current)
     {
       return NULL;
     }
 
-    if ((current + needle_len <= haystack_end) && memcmp(current, needle, needle_len) == 0)
+    if (memcmp(current, needle, needle_len) == 0)
     {
       return (char *)current;
     }
 
-    current++;
+    ++current;
   }
 
   return NULL;
diff --git a/tests/performance/strnstr.cpp b/tests/performance/strnstr.cpp
index 7c3b3ba7d..e9b01dced 100644
--- a/tests/performance/strnstr.cpp
+++ b/tests/performance/strnstr.cpp
@@ -71,6 +71,48 @@ char *ndpi_strnstr_opt(const char *haystack, const char *needle, size_t len) {
   return NULL;
 }
 
+char* ndpi_strnstr_opt2(const char* haystack, const char* needle, size_t length_limit) {
+  if (!haystack || !needle) {
+    return nullptr;
+  }
+
+  const size_t needle_len = strlen(needle);
+
+  if (needle_len == 0) {
+    return (char*) haystack;
+  }
+
+  const size_t hs_real_len = strnlen(haystack, length_limit);
+
+  if (needle_len == 1) {
+    return (char *)memchr(haystack, *needle, hs_real_len);
+  }
+
+  if (needle_len > hs_real_len) {
+    return nullptr;
+  }
+
+  const char*const end_of_search = haystack + hs_real_len - needle_len + 1;
+
+  const char *current = haystack;
+  while (current < end_of_search) {
+
+    current = (const char*) memchr(current, *needle, end_of_search - current);
+
+    if (!current) {
+      return nullptr;
+    }
+
+    if (memcmp(current, needle, needle_len) == 0) {
+      return (char*) current;
+    }
+
+    ++current;
+  }
+
+  return nullptr;
+}
+
 std::string random_string(size_t length, std::mt19937 &gen) {
   std::uniform_int_distribution<> dis(0, 255);
   std::string str(length, 0);
@@ -133,6 +175,7 @@ int main() {
       strnstr_impls = {
           {"ndpi_strnstr", ndpi_strnstr},
           {"ndpi_strnstr_opt", ndpi_strnstr_opt},
+          {"ndpi_strnstr_opt2", ndpi_strnstr_opt2},
       };
 
   const int iterations = 100000;