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 | |
25 | typedef char *(*proto_t) (const void *, size_t, const void *, size_t); |
26 | |
27 | void * |
28 | basic_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 | |
59 | void * |
60 | twoway_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 | |
100 | IMPL (memmem, 1) |
101 | IMPL (twoway_memmem, 0) |
102 | IMPL (basic_memmem, 0) |
103 | |
104 | static void |
105 | do_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 | |
123 | static void |
124 | do_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 | |
141 | static void |
142 | do_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 | |
174 | static const char *const strs[] = |
175 | { |
176 | "00000" , "00112233" , "0123456789" , "0000111100001111" , |
177 | "00000111110000022222" , "012345678901234567890" , |
178 | "abc0" , "aaaa0" , "abcabc0" |
179 | }; |
180 | |
181 | |
182 | int |
183 | test_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 | |