1 /* Measure memmem functions.
2 Copyright (C) 2013 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
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.
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.
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/>. */
20 #define TEST_NAME "memmem"
22 #define ITERATIONS 500
23 #include "bench-string.h"
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);
28 IMPL (simple_memmem
, 0)
32 simple_memmem (const void *haystack
, size_t haystack_len
, const void *needle
,
36 const char *const last_possible
37 = (const char *) haystack
+ haystack_len
- needle_len
;
40 /* The first occurrence of the empty string is deemed to occur at
41 the beginning of the string. */
42 return (void *) haystack
;
44 /* Sanity check, otherwise the loop might search through the whole
46 if (__builtin_expect (haystack_len
< needle_len
, 0))
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),
54 return (void *) begin
;
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
)
65 hp_timing_t start
__attribute ((unused
));
66 hp_timing_t stop
__attribute ((unused
));
67 hp_timing_t best_time
= ~ (hp_timing_t
) 0;
70 for (i
= 0; i
< 32; ++i
)
72 HP_TIMING_NOW (start
);
73 CALL (impl
, haystack
, haystack_len
, needle
, needle_len
);
75 HP_TIMING_BEST (best_time
, start
, stop
);
78 printf ("\t%zd", (size_t) best_time
);
83 do_test (const char *str
, size_t len
, size_t idx
)
87 memcpy (tmpbuf
, buf1
+ idx
, len
);
88 memcpy (buf1
+ idx
, str
, len
);
91 printf ("String %s, offset %zd:", str
, idx
);
93 FOR_EACH_IMPL (impl
, 0)
94 do_one_test (impl
, buf1
, BUF1PAGES
* page_size
, str
, len
, buf1
+ idx
);
96 memcpy (buf1
+ idx
, tmpbuf
, len
);
103 do_random_tests (void)
105 for (size_t n
= 0; n
< ITERATIONS
; ++n
)
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
)
117 size_t off
= random () % len
;
118 char ch
= '0' + random () % 10;
120 buf1
[idx
+ off
] = ch
;
124 printf ("String %.*s, offset %zd:", (int) len
, buf1
+ idx
, idx
);
126 FOR_EACH_IMPL (impl
, 0)
127 do_one_test (impl
, buf1
, BUF1PAGES
* page_size
, buf1
+ idx
, len
,
133 memcpy (buf1
+ idx
, tmpbuf
, len
);
137 static const char *const strs
[] =
139 "00000", "00112233", "0123456789", "0000111100001111",
140 "00000111110000022222", "012345678901234567890",
141 "abc0", "aaaa0", "abcabc0"
153 FOR_EACH_IMPL (impl
, 0)
154 printf ("\t%s", impl
->name
);
157 for (i
= 0; i
< BUF1PAGES
* page_size
; ++i
)
158 buf1
[i
] = 60 + random () % 32;
160 for (i
= 0; i
< sizeof (strs
) / sizeof (strs
[0]); ++i
)
161 for (size_t j
= 0; j
< 120; j
+= 7)
163 size_t len
= strlen (strs
[i
]);
165 do_test (strs
[i
], len
, j
);
172 #include "../test-skeleton.c"