strcasestr.c

["Todd C. Miller" <Todd.Miller@courtesan.com>]

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);
}