1/* Measure memmem functions.
2 Copyright (C) 2013-2022 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
25typedef char *(*proto_t) (const void *, size_t, const void *, size_t);
26
27void *
28basic_memmem (const void *haystack, size_t hs_len, const void *needle,
29 size_t ne_len)
30{
31 const char *hs = haystack;
32 const char *ne = needle;
33
34 if (ne_len == 0)
35 return (void *)hs;
36 int i;
37 int c = ne[0];
38 const char *end = hs + hs_len - ne_len;
39
40 for ( ; hs <= end; hs++)
41 {
42 if (hs[0] != c)
43 continue;
44 for (i = ne_len - 1; i != 0; i--)
45 if (hs[i] != ne[i])
46 break;
47 if (i == 0)
48 return (void *)hs;
49 }
50
51 return NULL;
52}
53
54#define RETURN_TYPE void *
55#define AVAILABLE(h, h_l, j, n_l) ((j) <= (h_l) - (n_l))
56#define FASTSEARCH(S,C,N) (void*) memchr ((void *)(S), (C), (N))
57#include "../string/str-two-way.h"
58
59void *
60twoway_memmem (const void *haystack_start, size_t haystack_len,
61 const void *needle_start, size_t needle_len)
62{
63 /* Abstract memory is considered to be an array of 'unsigned char' values,
64 not an array of 'char' values. See ISO C 99 section 6.2.6.1. */
65 const unsigned char *haystack = (const unsigned char *) haystack_start;
66 const unsigned char *needle = (const unsigned char *) needle_start;
67
68 if (needle_len == 0)
69 /* The first occurrence of the empty string is deemed to occur at
70 the beginning of the string. */
71 return (void *) haystack;
72
73 /* Sanity check, otherwise the loop might search through the whole
74 memory. */
75 if (__glibc_unlikely (haystack_len < needle_len))
76 return NULL;
77
78 /* Use optimizations in memchr when possible, to reduce the search
79 size of haystack using a linear algorithm with a smaller
80 coefficient. However, avoid memchr for long needles, since we
81 can often achieve sublinear performance. */
82 if (needle_len < LONG_NEEDLE_THRESHOLD)
83 {
84 haystack = memchr (haystack, *needle, haystack_len);
85 if (!haystack || __builtin_expect (needle_len == 1, 0))
86 return (void *) haystack;
87 haystack_len -= haystack - (const unsigned char *) haystack_start;
88 if (haystack_len < needle_len)
89 return NULL;
90 /* Check whether we have a match. This improves performance since we
91 avoid the initialization overhead of the two-way algorithm. */
92 if (memcmp (haystack, needle, needle_len) == 0)
93 return (void *) haystack;
94 return two_way_short_needle (haystack, haystack_len, needle, needle_len);
95 }
96 else
97 return two_way_long_needle (haystack, haystack_len, needle, needle_len);
98}
99
100IMPL (memmem, 1)
101IMPL (twoway_memmem, 0)
102IMPL (basic_memmem, 0)
103
104static void
105do_one_test (impl_t *impl, const void *haystack, size_t haystack_len,
106 const void *needle, size_t needle_len, const void *expected)
107{
108 size_t i, iters = INNER_LOOP_ITERS_SMALL;
109 timing_t start, stop, cur;
110
111 TIMING_NOW (start);
112 for (i = 0; i < iters; ++i)
113 {
114 CALL (impl, haystack, haystack_len, needle, needle_len);
115 }
116 TIMING_NOW (stop);
117
118 TIMING_DIFF (cur, start, stop);
119
120 TIMING_PRINT_MEAN ((double) cur, (double) iters);
121}
122
123static void
124do_test (const char *str, size_t len, size_t idx)
125{
126 char tmpbuf[len];
127
128 memcpy (tmpbuf, buf1 + idx, len);
129 memcpy (buf1 + idx, str, len);
130
131 printf (format: "String %s, offset %zd:", str, idx);
132
133 FOR_EACH_IMPL (impl, 0)
134 do_one_test (impl, haystack: buf1, BUF1PAGES * page_size, needle: str, needle_len: len, expected: buf1 + idx);
135
136 memcpy (buf1 + idx, tmpbuf, len);
137
138 putchar (c: '\n');
139}
140
141static void
142do_random_tests (void)
143{
144 for (size_t n = 0; n < ITERATIONS; ++n)
145 {
146 char tmpbuf[32];
147
148 size_t shift = random () % 11;
149 size_t rel = random () % ((2 << (shift + 1)) * 64);
150 size_t idx = MIN ((2 << shift) * 64 + rel, BUF1PAGES * page_size - 2);
151 size_t len = random () % (sizeof (tmpbuf) - 1) + 1;
152 len = MIN (len, BUF1PAGES * page_size - idx - 1);
153 memcpy (tmpbuf, buf1 + idx, len);
154 for (size_t i = random () % len / 2 + 1; i > 0; --i)
155 {
156 size_t off = random () % len;
157 char ch = '0' + random () % 10;
158
159 buf1[idx + off] = ch;
160 }
161
162 printf (format: "String %.*s, offset %zd:", (int) len, buf1 + idx, idx);
163
164 FOR_EACH_IMPL (impl, 0)
165 do_one_test (impl, haystack: buf1, BUF1PAGES * page_size, needle: buf1 + idx, needle_len: len,
166 expected: buf1 + idx);
167
168 putchar (c: '\n');
169
170 memcpy (buf1 + idx, tmpbuf, len);
171 }
172}
173
174static const char *const strs[] =
175 {
176 "00000", "00112233", "0123456789", "0000111100001111",
177 "00000111110000022222", "012345678901234567890",
178 "abc0", "aaaa0", "abcabc0"
179 };
180
181
182int
183test_main (void)
184{
185 size_t i;
186
187 test_init ();
188
189 printf (format: "%23s", "");
190 FOR_EACH_IMPL (impl, 0)
191 printf (format: "\t%s", impl->name);
192 putchar (c: '\n');
193
194 for (i = 0; i < BUF1PAGES * page_size; ++i)
195 buf1[i] = 60 + random () % 32;
196
197 for (i = 0; i < sizeof (strs) / sizeof (strs[0]); ++i)
198 for (size_t j = 0; j < 120; j += 7)
199 {
200 size_t len = strlen (strs[i]);
201
202 do_test (str: strs[i], len, idx: j);
203 }
204
205 do_random_tests ();
206 return ret;
207}
208
209#include <support/test-driver.c>
210

source code of glibc/benchtests/bench-memmem.c