From 6d9109bf70e2a86537ac3e1f1ea6053aab96132b Mon Sep 17 00:00:00 2001
From: "Yukihiro \"Matz\" Matsumoto" <matz@ruby.or.jp>
Date: Mon, 3 Feb 2020 12:07:54 +0900
Subject: Use simple search for short strings in `mrb_memsearch_qs`; close
 #4940

Differences from the PR #4940:
* Use simple search for short strings only.
* "short" means `m+n` is shorter than `MRB_QS_SHORT_STRING_LENGTH`.
* The current default value for `MRB_QS_SHORT_STRING_LENGTH` is 2048.
---
 src/string.c | 48 ++++++++++++++++++++++++++++++++++--------------
 1 file changed, 34 insertions(+), 14 deletions(-)

(limited to 'src/string.c')

diff --git a/src/string.c b/src/string.c
index c7b9db17a..e6c23618a 100644
--- a/src/string.c
+++ b/src/string.c
@@ -504,25 +504,45 @@ str_index_str_by_char(mrb_state *mrb, mrb_value str, mrb_value sub, mrb_int pos)
 #define str_index_str_by_char(mrb, str, sub, pos) str_index_str(mrb, str, sub, pos)
 #endif
 
+#ifndef MRB_QS_SHORT_STRING_LENGTH
+#define MRB_QS_SHORT_STRING_LENGTH 2048
+#endif
+
 static inline mrb_int
 mrb_memsearch_qs(const unsigned char *xs, mrb_int m, const unsigned char *ys, mrb_int n)
 {
-  const unsigned char *x = xs, *xe = xs + m;
-  const unsigned char *y = ys;
-  int i;
-  ptrdiff_t qstable[256];
+  if (n + m < MRB_QS_SHORT_STRING_LENGTH) {
+    const unsigned char *y = ys;
+    const unsigned char *ye = ys+n-m+1;
 
-  /* Preprocessing */
-  for (i = 0; i < 256; ++i)
-    qstable[i] = m + 1;
-  for (; x < xe; ++x)
-    qstable[*x] = xe - x;
-  /* Searching */
-  for (; y + m <= ys + n; y += *(qstable + y[m])) {
-    if (*xs == *y && memcmp(xs, y, m) == 0)
-      return (mrb_int)(y - ys);
+    for (;;) {
+      y = memchr(y, xs[0], (size_t)(ye-y));
+      if (y == NULL) return -1;
+      if (memcmp(xs, y, m) == 0) {
+        return (mrb_int)(y - ys);
+      }
+      y++;
+    }
+    return -1;
+  }
+  else {
+    const unsigned char *x = xs, *xe = xs + m;
+    const unsigned char *y = ys;
+    int i;
+    ptrdiff_t qstable[256];
+
+    /* Preprocessing */
+    for (i = 0; i < 256; ++i)
+      qstable[i] = m + 1;
+    for (; x < xe; ++x)
+      qstable[*x] = xe - x;
+    /* Searching */
+    for (; y + m <= ys + n; y += *(qstable + y[m])) {
+      if (*xs == *y && memcmp(xs, y, m) == 0)
+        return (mrb_int)(y - ys);
+    }
+    return -1;
   }
-  return -1;
 }
 
 static mrb_int
-- 
cgit v1.2.3