1#include <wchar.h>
2
3#define MAX(a, b) ((a) > (b) ? (a) : (b))
4#define MIN(a, b) ((a) < (b) ? (a) : (b))
5
6static 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
108wchar_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