]>
Commit | Line | Data |
---|---|---|
97020474 SP |
1 | /* Measure memmem functions. |
2 | Copyright (C) 2013 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 | <http://www.gnu.org/licenses/>. */ | |
18 | ||
19 | #define TEST_MAIN | |
20 | #define TEST_NAME "memmem" | |
21 | #define BUF1PAGES 20 | |
22 | #define ITERATIONS 500 | |
23 | #include "bench-string.h" | |
24 | ||
25 | typedef char *(*proto_t) (const void *, size_t, const void *, size_t); | |
26 | void *simple_memmem (const void *, size_t, const void *, size_t); | |
27 | ||
28 | IMPL (simple_memmem, 0) | |
29 | IMPL (memmem, 1) | |
30 | ||
31 | void * | |
32 | simple_memmem (const void *haystack, size_t haystack_len, const void *needle, | |
33 | size_t needle_len) | |
34 | { | |
35 | const char *begin; | |
36 | const char *const last_possible | |
37 | = (const char *) haystack + haystack_len - needle_len; | |
38 | ||
39 | if (needle_len == 0) | |
40 | /* The first occurrence of the empty string is deemed to occur at | |
41 | the beginning of the string. */ | |
42 | return (void *) haystack; | |
43 | ||
44 | /* Sanity check, otherwise the loop might search through the whole | |
45 | memory. */ | |
46 | if (__builtin_expect (haystack_len < needle_len, 0)) | |
47 | return NULL; | |
48 | ||
49 | for (begin = (const char *) haystack; begin <= last_possible; ++begin) | |
50 | if (begin[0] == ((const char *) needle)[0] && | |
51 | !memcmp ((const void *) &begin[1], | |
52 | (const void *) ((const char *) needle + 1), | |
53 | needle_len - 1)) | |
54 | return (void *) begin; | |
55 | ||
56 | return NULL; | |
57 | } | |
58 | ||
59 | static void | |
60 | do_one_test (impl_t *impl, const void *haystack, size_t haystack_len, | |
61 | const void *needle, size_t needle_len, const void *expected) | |
62 | { | |
63 | if (HP_TIMING_AVAIL) | |
64 | { | |
65 | hp_timing_t start __attribute ((unused)); | |
66 | hp_timing_t stop __attribute ((unused)); | |
67 | hp_timing_t best_time = ~ (hp_timing_t) 0; | |
68 | size_t i; | |
69 | ||
70 | for (i = 0; i < 32; ++i) | |
71 | { | |
72 | HP_TIMING_NOW (start); | |
73 | CALL (impl, haystack, haystack_len, needle, needle_len); | |
74 | HP_TIMING_NOW (stop); | |
75 | HP_TIMING_BEST (best_time, start, stop); | |
76 | } | |
77 | ||
78 | printf ("\t%zd", (size_t) best_time); | |
79 | } | |
80 | } | |
81 | ||
82 | static void | |
83 | do_test (const char *str, size_t len, size_t idx) | |
84 | { | |
85 | char tmpbuf[len]; | |
86 | ||
87 | memcpy (tmpbuf, buf1 + idx, len); | |
88 | memcpy (buf1 + idx, str, len); | |
89 | ||
90 | if (HP_TIMING_AVAIL) | |
91 | printf ("String %s, offset %zd:", str, idx); | |
92 | ||
93 | FOR_EACH_IMPL (impl, 0) | |
94 | do_one_test (impl, buf1, BUF1PAGES * page_size, str, len, buf1 + idx); | |
95 | ||
96 | memcpy (buf1 + idx, tmpbuf, len); | |
97 | ||
98 | if (HP_TIMING_AVAIL) | |
99 | putchar ('\n'); | |
100 | } | |
101 | ||
102 | static void | |
103 | do_random_tests (void) | |
104 | { | |
105 | for (size_t n = 0; n < ITERATIONS; ++n) | |
106 | { | |
107 | char tmpbuf[32]; | |
108 | ||
109 | size_t shift = random () % 11; | |
110 | size_t rel = random () % ((2 << (shift + 1)) * 64); | |
111 | size_t idx = MIN ((2 << shift) * 64 + rel, BUF1PAGES * page_size - 2); | |
112 | size_t len = random () % (sizeof (tmpbuf) - 1) + 1; | |
113 | len = MIN (len, BUF1PAGES * page_size - idx - 1); | |
114 | memcpy (tmpbuf, buf1 + idx, len); | |
115 | for (size_t i = random () % len / 2 + 1; i > 0; --i) | |
116 | { | |
117 | size_t off = random () % len; | |
118 | char ch = '0' + random () % 10; | |
119 | ||
120 | buf1[idx + off] = ch; | |
121 | } | |
122 | ||
123 | if (HP_TIMING_AVAIL) | |
124 | printf ("String %.*s, offset %zd:", (int) len, buf1 + idx, idx); | |
125 | ||
126 | FOR_EACH_IMPL (impl, 0) | |
127 | do_one_test (impl, buf1, BUF1PAGES * page_size, buf1 + idx, len, | |
128 | buf1 + idx); | |
129 | ||
130 | if (HP_TIMING_AVAIL) | |
131 | putchar ('\n'); | |
132 | ||
133 | memcpy (buf1 + idx, tmpbuf, len); | |
134 | } | |
135 | } | |
136 | ||
137 | static const char *const strs[] = | |
138 | { | |
139 | "00000", "00112233", "0123456789", "0000111100001111", | |
140 | "00000111110000022222", "012345678901234567890", | |
141 | "abc0", "aaaa0", "abcabc0" | |
142 | }; | |
143 | ||
144 | ||
145 | int | |
146 | test_main (void) | |
147 | { | |
148 | size_t i; | |
149 | ||
150 | test_init (); | |
151 | ||
152 | printf ("%23s", ""); | |
153 | FOR_EACH_IMPL (impl, 0) | |
154 | printf ("\t%s", impl->name); | |
155 | putchar ('\n'); | |
156 | ||
157 | for (i = 0; i < BUF1PAGES * page_size; ++i) | |
158 | buf1[i] = 60 + random () % 32; | |
159 | ||
160 | for (i = 0; i < sizeof (strs) / sizeof (strs[0]); ++i) | |
161 | for (size_t j = 0; j < 120; j += 7) | |
162 | { | |
163 | size_t len = strlen (strs[i]); | |
164 | ||
165 | do_test (strs[i], len, j); | |
166 | } | |
167 | ||
168 | do_random_tests (); | |
169 | return ret; | |
170 | } | |
171 | ||
172 | #include "../test-skeleton.c" |