From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/2796 Path: news.gmane.org!not-for-mail From: "Todd C. Miller" Newsgroups: gmane.linux.lib.musl.general Subject: strcasestr.c Date: Thu, 14 Feb 2013 09:59:56 -0500 Message-ID: <201302141459.r1EExuU3024259@core.courtesan.com> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1360854008 26696 80.91.229.3 (14 Feb 2013 15:00:08 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 14 Feb 2013 15:00:08 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-2797-gllmg-musl=m.gmane.org@lists.openwall.com Thu Feb 14 16:00:30 2013 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1U60IY-0002c4-7b for gllmg-musl@plane.gmane.org; Thu, 14 Feb 2013 16:00:30 +0100 Original-Received: (qmail 9989 invoked by uid 550); 14 Feb 2013 15:00:09 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 9979 invoked from network); 14 Feb 2013 15:00:09 -0000 Xref: news.gmane.org gmane.linux.lib.musl.general:2796 Archived-At: When investigating using the musl strstr.c ofr OpenBSD I noticed that musl only has a stub for strcasestr() that calls strstr(). I was curious whether the twoway algorithm could be adapted to do a case-insensitive search. It turned out to be pretty trivial to just add calls to tolower() in the right places, making sure to avoid sign extension. The changes are mostly mechanical. You might wish to inline _strcasechr() though the compiler will probably do that for you. - todd #include #include #include #include #define LOWER(c) ((unsigned char)tolower((c))) static char *twobyte_strcasestr(const unsigned char *h, const unsigned char *n) { uint16_t nw = LOWER(n[0])<<8 | LOWER(n[1]); uint16_t hw = LOWER(h[0])<<8 | LOWER(h[1]); for (h++; *h && hw != nw; hw = hw<<8 | LOWER(*++h)); return *h ? (char *)h-1 : 0; } static char *threebyte_strcasestr(const unsigned char *h, const unsigned char *n) { uint32_t nw = LOWER(n[0])<<24 | LOWER(n[1])<<16 | LOWER(n[2])<<8; uint32_t hw = LOWER(h[0])<<24 | LOWER(h[1])<<16 | LOWER(h[2])<<8; for (h+=2; *h && hw != nw; hw = (hw|LOWER(*++h))<<8); return *h ? (char *)h-2 : 0; } static char *fourbyte_strcasestr(const unsigned char *h, const unsigned char *n) { uint32_t nw = LOWER(n[0])<<24 | LOWER(n[1])<<16 | LOWER(n[2])<<8 | LOWER(n[3]); uint32_t hw = LOWER(h[0])<<24 | LOWER(h[1])<<16 | LOWER(h[2])<<8 | LOWER(h[3]); for (h+=3; *h && hw != nw; hw = hw<<8 | LOWER(*++h)); return *h ? (char *)h-3 : 0; } #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)<(b)?(a):(b)) #define BITOP(a,b,op) \ ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) static char *twoway_strcasestr(const unsigned char *h, const unsigned char *n) { const unsigned char *z; unsigned char l1, l2; size_t l, ip, jp, k, p, ms, p0, mem, mem0; size_t byteset[32 / sizeof(size_t)] = { 0 }; size_t shift[256]; /* Computing length of needle and fill shift table */ for (l=0; n[l] && h[l]; l++) { l1 = LOWER(n[l]); BITOP(byteset, l1, |=), shift[l1] = l+1; } if (n[l]) return 0; /* hit the end of h */ /* Compute maximal suffix */ ip = -1; jp = 0; k = p = 1; while (jp+k l2) { jp += k; k = 1; p = jp - ip; } else { ip = jp++; k = p = 1; } } ms = ip; p0 = p; /* And with the opposite comparison */ ip = -1; jp = 0; k = p = 1; while (jp+k ms+1) ms = ip; else p = p0; /* Periodic needle? */ for (ip = 0; ip <= ms; ip++) { if (LOWER(n[ip]) != LOWER(n[ip + p])) break; } if (ip <= ms) { mem0 = 0; p = MAX(ms, l-ms-1) + 1; } else mem0 = l-p; mem = 0; /* Initialize incremental end-of-haystack pointer */ z = h; /* Search loop */ for (;;) { /* Update incremental end-of-haystack pointer */ if (z-h < l) { /* Fast estimate for MIN(l,63) */ size_t grow = l | 63; const unsigned char *z2 = memchr(z, 0, grow); if (z2) { z = z2; if (z-h < l) return 0; } else z += grow; } /* Check last byte first; advance by shift on mismatch */ l1 = LOWER(h[l-1]); if (BITOP(byteset, l1, &)) { k = l-shift[l1]; #ifdef DEBUG printf("adv by %zu (on %c) at [%s] (%zu;l=%zu)\n", k, h[l-1], h, shift[h[l-1]], l); #endif if (k) { if (mem0 && mem && k < p) k = l-p; h += k; mem = 0; continue; } } else { h += l; mem = 0; continue; } /* Compare right half */ for (k=MAX(ms+1,mem); n[k] && LOWER(n[k]) == LOWER(h[k]); k++); if (n[k]) { h += k-ms; mem = 0; continue; } /* Compare left half */ for (k=ms+1; k>mem && LOWER(n[k-1]) == LOWER(h[k-1]); k--); if (k == mem) return (char *)h; h += p; mem = mem0; } } static char *_strcasechr(const char *s, int c) { for (;;) { if (tolower((unsigned char)*s) == tolower((unsigned char)c)) return (char *)s; if (!*s++) return NULL; } } char *strcasestr(const char *h, const char *n) { /* Return immediately on empty needle */ if (!n[0]) return (char *)h; /* Use faster algorithms for short needles */ h = _strcasechr(h, *n); if (!h || !n[1]) return (char *)h; if (!h[1]) return 0; if (!n[2]) return twobyte_strcasestr((void *)h, (void *)n); if (!h[2]) return 0; if (!n[3]) return threebyte_strcasestr((void *)h, (void *)n); if (!h[3]) return 0; if (!n[4]) return fourbyte_strcasestr((void *)h, (void *)n); return twoway_strcasestr((void *)h, (void *)n); }