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