1 /* Measure memmem functions.
2 Copyright (C) 2013-2023 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19 #define TEST_MAIN
20 #define TEST_NAME "memmem"
21 #define BUF1PAGES 20
22 #define ITERATIONS 100
23 #include "bench-string.h"
24 #include "json-lib.h"
25
26 typedef char *(*proto_t) (const void *, size_t, const void *, size_t);
27
28 void *
29 basic_memmem (const void *haystack, size_t hs_len, const void *needle,
30 size_t ne_len)
31 {
32 const char *hs = haystack;
33 const char *ne = needle;
34
35 if (ne_len == 0)
36 return (void *)hs;
37 int i;
38 int c = ne[0];
39 const char *end = hs + hs_len - ne_len;
40
41 for ( ; hs <= end; hs++)
42 {
43 if (hs[0] != c)
44 continue;
45 for (i = ne_len - 1; i != 0; i--)
46 if (hs[i] != ne[i])
47 break;
48 if (i == 0)
49 return (void *)hs;
50 }
51
52 return NULL;
53 }
54
55 #define RETURN_TYPE void *
56 #define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
57 #define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N))
58 #include "../string/str-two-way.h"
59
60 void *
61 twoway_memmem (const void *haystack_start, size_t haystack_len,
62 const void *needle_start, size_t needle_len)
63 {
64 /* Abstract memory is considered to be an array of 'unsigned char' values,
65 not an array of 'char' values. See ISO C 99 section 6.2.6.1. */
66 const unsigned char *haystack = (const unsigned char *) haystack_start;
67 const unsigned char *needle = (const unsigned char *) needle_start;
68
69 if (needle_len == 0)
70 /* The first occurrence of the empty string is deemed to occur at
71 the beginning of the string. */
72 return (void *) haystack;
73
74 /* Sanity check, otherwise the loop might search through the whole
75 memory. */
76 if (__glibc_unlikely (haystack_len < needle_len))
77 return NULL;
78
79 /* Use optimizations in memchr when possible, to reduce the search
80 size of haystack using a linear algorithm with a smaller
81 coefficient. However, avoid memchr for long needles, since we
82 can often achieve sublinear performance. */
83 if (needle_len < LONG_NEEDLE_THRESHOLD)
84 {
85 haystack = memchr (haystack, *needle, haystack_len);
86 if (!haystack || __builtin_expect (needle_len == 1, 0))
87 return (void *) haystack;
88 haystack_len -= haystack - (const unsigned char *) haystack_start;
89 if (haystack_len < needle_len)
90 return NULL;
91 /* Check whether we have a match. This improves performance since we
92 avoid the initialization overhead of the two-way algorithm. */
93 if (memcmp (haystack, needle, needle_len) == 0)
94 return (void *) haystack;
95 return two_way_short_needle (haystack, haystack_len, needle, needle_len);
96 }
97 else
98 return two_way_long_needle (haystack, haystack_len, needle, needle_len);
99 }
100
101 IMPL (memmem, 1)
102 IMPL (twoway_memmem, 0)
103 IMPL (basic_memmem, 0)
104
105 static void
106 do_one_test (json_ctx_t *json_ctx, impl_t *impl, const void *haystack,
107 size_t haystack_len, const void *needle, size_t needle_len,
108 const void *expected)
109 {
110 size_t i, iters = INNER_LOOP_ITERS_SMALL;
111 timing_t start, stop, cur;
112 void *res;
113 TIMING_NOW (start);
114 for (i = 0; i < iters; ++i)
115 {
116 res = CALL (impl, haystack, haystack_len, needle, needle_len);
117 }
118 TIMING_NOW (stop);
119
120 TIMING_DIFF (cur, start, stop);
121
122 json_element_double (json_ctx, (double) cur / (double) iters);
123
124 if (res != expected)
125 {
126 error (0, 0, "Wrong result in function (%p != %p) %s(%p, %zu, %p, %zu)",
127 res, expected, impl->name, haystack, haystack_len, needle,
128 needle_len);
129 ret = 1;
130 }
131 }
132
133 static void
134 do_test (json_ctx_t *json_ctx, const char *str, size_t len, size_t idx)
135 {
136 char tmpbuf[len];
137
138 memcpy (tmpbuf, buf1 + idx, len);
139 memcpy (buf1 + idx, str, len);
140
141 json_element_object_begin (json_ctx);
142 json_attr_uint (json_ctx, "len_haystack", BUF1PAGES * page_size);
143 json_attr_uint (json_ctx, "len_needle", len);
144 json_attr_uint (json_ctx, "haystack_ptr", (uintptr_t) buf1);
145 json_attr_uint (json_ctx, "needle_ptr", (uintptr_t) str);
146 json_attr_uint (json_ctx, "fail", 0);
147
148 json_array_begin (json_ctx, "timings");
149
150 FOR_EACH_IMPL (impl, 0)
151 do_one_test (json_ctx, impl, buf1, BUF1PAGES * page_size, str, len,
152 buf1 + idx);
153
154 memcpy (buf1 + idx, tmpbuf, len);
155
156 json_array_end (json_ctx);
157 json_element_object_end (json_ctx);
158 }
159
160 static void
161 do_random_tests (json_ctx_t *json_ctx)
162 {
163 for (size_t n = 0; n < ITERATIONS; ++n)
164 {
165 char tmpbuf[32];
166
167 size_t shift = random () % 11;
168 size_t rel = random () % ((2 << (shift + 1)) * 64);
169 size_t idx = MIN ((2 << shift) * 64 + rel, BUF1PAGES * page_size - 2);
170 size_t len = random () % (sizeof (tmpbuf) - 1) + 1;
171 len = MIN (len, BUF1PAGES * page_size - idx - 1);
172 memcpy (tmpbuf, buf1 + idx, len);
173 for (size_t i = random () % len / 2 + 1; i > 0; --i)
174 {
175 size_t off = random () % len;
176 char ch = '0' + random () % 10;
177
178 buf1[idx + off] = ch;
179 }
180
181 json_element_object_begin (json_ctx);
182 json_attr_uint (json_ctx, "len_haystack", BUF1PAGES * page_size);
183 json_attr_uint (json_ctx, "len_needle", len);
184 json_attr_uint (json_ctx, "haystack_ptr", (uintptr_t) buf1);
185 json_attr_uint (json_ctx, "needle_ptr", (uintptr_t) (buf1 + idx));
186 json_attr_uint (json_ctx, "fail", 0);
187
188 json_array_begin (json_ctx, "timings");
189
190 FOR_EACH_IMPL (impl, 0)
191 do_one_test (json_ctx, impl, buf1, BUF1PAGES * page_size, buf1 + idx,
192 len, buf1 + idx);
193
194 json_array_end (json_ctx);
195 json_element_object_end (json_ctx);
196
197 memcpy (buf1 + idx, tmpbuf, len);
198 }
199 }
200
201 static const char *const strs[] =
202 {
203 "00000", "00112233", "0123456789", "0000111100001111",
204 "00000111110000022222", "012345678901234567890",
205 "abc0", "aaaa0", "abcabc0"
206 };
207
208 int
209 test_main (void)
210 {
211 json_ctx_t json_ctx;
212 size_t i;
213
214 test_init ();
215 json_init (&json_ctx, 0, stdout);
216
217 json_document_begin (&json_ctx);
218 json_attr_string (&json_ctx, "timing_type", TIMING_TYPE);
219
220 json_attr_object_begin (&json_ctx, "functions");
221 json_attr_object_begin (&json_ctx, TEST_NAME);
222 json_attr_string (&json_ctx, "bench-variant", "");
223
224 json_array_begin (&json_ctx, "ifuncs");
225 FOR_EACH_IMPL (impl, 0)
226 json_element_string (&json_ctx, impl->name);
227 json_array_end (&json_ctx);
228
229 json_array_begin (&json_ctx, "results");
230
231 for (i = 0; i < BUF1PAGES * page_size; ++i)
232 buf1[i] = 60 + random () % 32;
233
234 for (i = 0; i < sizeof (strs) / sizeof (strs[0]); ++i)
235 for (size_t j = 0; j < 120; j += 7)
236 {
237 size_t len = strlen (strs[i]);
238
239 do_test (&json_ctx, strs[i], len, j);
240 }
241
242 do_random_tests (&json_ctx);
243
244 json_array_end (&json_ctx);
245 json_attr_object_end (&json_ctx);
246 json_attr_object_end (&json_ctx);
247 json_document_end (&json_ctx);
248 return ret;
249 }
250
251 #include <support/test-driver.c>