1 #include <wchar.h>
2 
3 #define MAX(a, b) ((a) > (b) ? (a) : (b))
4 #define MIN(a, b) ((a) < (b) ? (a) : (b))
5 
twoway_wcsstr(const wchar_t * h,const wchar_t * n)6 static wchar_t* twoway_wcsstr(const wchar_t* h, const wchar_t* n) {
7     const wchar_t* z;
8     size_t l, ip, jp, k, p, ms, p0, mem, mem0;
9 
10     /* Computing length of needle */
11     for (l = 0; n[l] && h[l]; l++)
12         ;
13     if (n[l])
14         return 0; /* hit the end of h */
15 
16     /* Compute maximal suffix */
17     ip = -1;
18     jp = 0;
19     k = p = 1;
20     while (jp + k < l) {
21         if (n[ip + k] == n[jp + k]) {
22             if (k == p) {
23                 jp += p;
24                 k = 1;
25             } else
26                 k++;
27         } else if (n[ip + k] > n[jp + k]) {
28             jp += k;
29             k = 1;
30             p = jp - ip;
31         } else {
32             ip = jp++;
33             k = p = 1;
34         }
35     }
36     ms = ip;
37     p0 = p;
38 
39     /* And with the opposite comparison */
40     ip = -1;
41     jp = 0;
42     k = p = 1;
43     while (jp + k < l) {
44         if (n[ip + k] == n[jp + k]) {
45             if (k == p) {
46                 jp += p;
47                 k = 1;
48             } else
49                 k++;
50         } else if (n[ip + k] < n[jp + k]) {
51             jp += k;
52             k = 1;
53             p = jp - ip;
54         } else {
55             ip = jp++;
56             k = p = 1;
57         }
58     }
59     if (ip + 1 > ms + 1)
60         ms = ip;
61     else
62         p = p0;
63 
64     /* Periodic needle? */
65     if (wmemcmp(n, n + p, ms + 1)) {
66         mem0 = 0;
67         p = MAX(ms, l - ms - 1) + 1;
68     } else
69         mem0 = l - p;
70     mem = 0;
71 
72     /* Initialize incremental end-of-haystack pointer */
73     z = h;
74 
75     /* Search loop */
76     for (;;) {
77         /* Update incremental end-of-haystack pointer */
78         if (z - h < l) {
79             /* Fast estimate for MIN(l,63) */
80             size_t grow = l | 63;
81             const wchar_t* z2 = wmemchr(z, 0, grow);
82             if (z2) {
83                 z = z2;
84                 if (z - h < l)
85                     return 0;
86             } else
87                 z += grow;
88         }
89 
90         /* Compare right half */
91         for (k = MAX(ms + 1, mem); n[k] && n[k] == h[k]; k++)
92             ;
93         if (n[k]) {
94             h += k - ms;
95             mem = 0;
96             continue;
97         }
98         /* Compare left half */
99         for (k = ms + 1; k > mem && n[k - 1] == h[k - 1]; k--)
100             ;
101         if (k <= mem)
102             return (wchar_t*)h;
103         h += p;
104         mem = mem0;
105     }
106 }
107 
wcsstr(const wchar_t * restrict h,const wchar_t * restrict n)108 wchar_t* wcsstr(const wchar_t* restrict h, const wchar_t* restrict n) {
109     /* Return immediately on empty needle or haystack */
110     if (!n[0])
111         return (wchar_t*)h;
112     if (!h[0])
113         return 0;
114 
115     /* Use faster algorithms for short needles */
116     h = wcschr(h, *n);
117     if (!h || !n[1])
118         return (wchar_t*)h;
119     if (!h[1])
120         return 0;
121 
122     return twoway_wcsstr(h, n);
123 }
124