1 /* { dg-do run { target { sysconf && mmap } } } */
2 /* { dg-options "-O2 -minline-all-stringops" } */
3
4 #include <stdint.h>
5 #include <string.h>
6 #include <stdlib.h>
7 #include <unistd.h>
8 #include <sys/mman.h>
9 #ifndef MAP_ANON
10 #define MAP_ANON 0
11 #endif
12 #ifndef MAP_FAILED
13 #define MAP_FAILED ((void *)-1)
14 #endif
15
16 uint8_t shift[256];
17
18 static size_t
19 __attribute__ ((noclone, noinline))
hash2(const unsigned char * p)20 hash2(const unsigned char *p)
21 {
22 return (((size_t)(p)[0] - ((size_t)(p)[-1] << 3)) % sizeof (shift));
23 }
24
25 char *
simple_strstr(const char * haystack,const char * needle)26 simple_strstr (const char *haystack, const char *needle)
27 {
28 const unsigned char *hs = (const unsigned char *) haystack;
29 const unsigned char *ne = (const unsigned char *) needle;
30 size_t ne_len = strlen ((const char*)ne);
31 size_t hs_len = strnlen ((const char*)hs, ne_len | 512);
32
33 if (hs_len < ne_len)
34 return NULL;
35
36 if (memcmp (hs, ne, ne_len) == 0)
37 return (char *) hs;
38
39 const unsigned char *end = hs + hs_len - ne_len;
40 size_t tmp, shift1;
41 size_t m1 = ne_len - 1;
42 size_t offset = 0;
43
44 memset (shift, 0, sizeof (shift));
45 for (int i = 1; i < m1; i++)
46 shift[hash2 (ne + i)] = i;
47 shift1 = m1 - shift[hash2 (ne + m1)];
48 shift[hash2 (ne + m1)] = m1;
49
50 while (1)
51 {
52 if (__builtin_expect (hs > end, 0))
53 {
54 end += strnlen ((const char*)end + m1 + 1, 2048);
55 if (hs > end)
56 return NULL;
57 }
58
59 do
60 {
61 hs += m1;
62 tmp = shift[hash2 (hs)];
63 }
64 while (tmp == 0 && hs <= end);
65
66 hs -= tmp;
67 if (tmp < m1)
68 continue;
69
70 if (m1 < 15 || memcmp (hs + offset, ne + offset, 8) == 0)
71 {
72 if (memcmp (hs, ne, m1) == 0)
73 return (void *) hs;
74
75 offset = (offset >= 8 ? offset : m1) - 8;
76 }
77
78 hs += shift1;
79 }
80 }
81
82 static int
check_result(const char * s1,const char * s2,char * exp_result)83 check_result (const char *s1, const char *s2,
84 char *exp_result)
85 {
86 char *result = simple_strstr (s1, s2);
87 if (result != exp_result)
88 return -1;
89
90 return 0;
91 }
92
93 void
94 __attribute__ ((noclone, noinline))
check1(void)95 check1 (void)
96 {
97 const char s1[] =
98 "F_BD_CE_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_C3_88_20_EF_BF_BD_EF_BF_BD_EF_BF_BD_C3_A7_20_EF_BF_BD";
99 const char s2[] = "_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD_EF_BF_BD";
100 char *exp_result;
101
102 exp_result = simple_strstr (s1, s2);
103 if (check_result (s1, s2, exp_result) != 0)
104 abort ();
105 }
106
107 int
main(void)108 main (void)
109 {
110 unsigned char *buf1, *buf2;
111 size_t page_size = 2 * sysconf(_SC_PAGESIZE);
112 buf1 = mmap (0, (1 + 1) * page_size, PROT_READ | PROT_WRITE,
113 MAP_PRIVATE | MAP_ANON, -1, 0);
114 if (buf1 == MAP_FAILED)
115 return -1;
116 if (mprotect (buf1 + 1 * page_size, page_size, PROT_NONE))
117 return -1;
118 buf2 = mmap (0, 2 * page_size, PROT_READ | PROT_WRITE,
119 MAP_PRIVATE | MAP_ANON, -1, 0);
120 if (buf2 == MAP_FAILED)
121 return -1;
122 if (mprotect (buf2 + page_size, page_size, PROT_NONE))
123 return -1;
124
125 memset (buf1, 0xa5, 1 * page_size);
126 memset (buf2, 0x5a, page_size);
127
128 check1 ();
129 return 0;
130 }
131