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