benchtests: Add difficult strstr needle for bruteforce algorithms

Add another difficult needle to strstr that clearly shows the quadratic
complexity of bruteforce algorithms.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

1 files changed, 27 insertions, 0 deletions

diff --git a/benchtests/bench-strstr.c b/benchtests/bench-strstr.c
index 9288ad1..4b07d39 100644
--- a/benchtests/bench-strstr.c
+++ b/benchtests/bench-strstr.c
@@ -352,6 +352,33 @@ test_hard_needle (json_ctx_t *json_ctx, size_t ne_len, size_t hs_len)
     json_array_end (json_ctx);
     json_element_object_end (json_ctx);
   }
+
+  /* Hard needle for bruteforce algorithms that match first few chars.  */
+  {
+    memset (hs, 'a', hs_len);
+    for (int i = ne_len-1; i < hs_len; i += ne_len)
+      hs[i] = 'b';
+    hs[hs_len] = 0;
+
+    memset (ne, 'a', ne_len);
+    ne[ne_len] = 0;
+
+    json_element_object_begin (json_ctx);
+    json_attr_uint (json_ctx, "len_haystack", hs_len);
+    json_attr_uint (json_ctx, "len_needle", ne_len);
+    json_attr_uint (json_ctx, "align_haystack", 0);
+    json_attr_uint (json_ctx, "align_needle", 0);
+    json_attr_uint (json_ctx, "fail", 1);
+    json_attr_string (json_ctx, "desc", "Difficult bruteforce needle");
+
+    json_array_begin (json_ctx, "timings");
+
+    FOR_EACH_IMPL (impl, 0)
+      do_one_test (json_ctx, impl, hs, ne, NULL);
+
+    json_array_end (json_ctx);
+    json_element_object_end (json_ctx);
+  }
 }
 
 static int