1140275Sdas#include <wchar.h> 2140275Sdas 3140275Sdas#define MAX(a,b) ((a)>(b)?(a):(b)) 4140275Sdas#define MIN(a,b) ((a)<(b)?(a):(b)) 5140275Sdas 6140275Sdasstatic wchar_t *twoway_wcsstr(const wchar_t *h, const wchar_t *n) 7140275Sdas{ 8140275Sdas const wchar_t *z; 9140275Sdas size_t l, ip, jp, k, p, ms, p0, mem, mem0; 10140275Sdas 11140275Sdas /* Computing length of needle */ 12140275Sdas for (l=0; n[l] && h[l]; l++); 13140275Sdas if (n[l]) return 0; /* hit the end of h */ 14140275Sdas 15140275Sdas /* Compute maximal suffix */ 16140275Sdas ip = -1; jp = 0; k = p = 1; 17140275Sdas while (jp+k<l) { 18140275Sdas if (n[ip+k] == n[jp+k]) { 19140275Sdas if (k == p) { 20140275Sdas jp += p; 21140275Sdas k = 1; 22140275Sdas } else k++; 23140275Sdas } else if (n[ip+k] > n[jp+k]) { 24140275Sdas jp += k; 25140275Sdas k = 1; 26140275Sdas p = jp - ip; 27140275Sdas } else { 28140275Sdas ip = jp++; 29140275Sdas k = p = 1; 30141280Sdas } 31140275Sdas } 32140275Sdas ms = ip; 33192760Sattilio p0 = p; 34140275Sdas 35217108Skib /* And with the opposite comparison */ 36217108Skib 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