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