mailing list of musl libc
 help / color / mirror / code / Atom feed
* strcasestr.c
@ 2013-02-14 14:59 Todd C. Miller
  2013-02-14 15:23 ` strcasestr.c Rich Felker
  0 siblings, 1 reply; 12+ messages in thread
From: Todd C. Miller @ 2013-02-14 14:59 UTC (permalink / raw)
  To: musl

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 <string.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>

#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<l) {
		l1 = LOWER(n[ip+k]);
		l2 = LOWER(n[jp+k]);
		if (l1 == l2) {
			if (k == p) {
				jp += p;
				k = 1;
			} else k++;
		} else if (l1 > 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<l) {
		l1 = LOWER(n[ip+k]);
		l2 = LOWER(n[jp+k]);
		if (l1 == l2) {
			if (k == p) {
				jp += p;
				k = 1;
			} else k++;
		} else if (l1 < l2) {
			jp += k;
			k = 1;
			p = jp - ip;
		} else {
			ip = jp++;
			k = p = 1;
		}
	}
	if (ip+1 > 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);
}


^ permalink raw reply	[flat|nested] 12+ messages in thread
end of thread, other threads:[~2013-02-22  5:20 UTC | newest]

Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-02-14 14:59 strcasestr.c Todd C. Miller
2013-02-14 15:23 ` strcasestr.c Rich Felker
2013-02-17 19:04   ` strcasestr.c Rich Felker
2013-02-20 22:28     ` strcasestr.c John Spencer
2013-02-20 23:56       ` strcasestr.c Szabolcs Nagy
2013-02-21  1:03       ` strcasestr.c Rich Felker
2013-02-21  1:30         ` strcasestr.c Kurt H Maier
2013-02-21  1:34           ` strcasestr.c Rich Felker
2013-02-21  6:18         ` strcasestr.c Isaac Dunham
2013-02-21 20:00           ` strcasestr.c John Spencer
2013-02-21 20:13             ` strcasestr.c Szabolcs Nagy
2013-02-22  5:20         ` strcasestr.c Rich Felker

Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).