Skip site navigation (1)Skip section navigation (2) 
Date:      Wed, 10 Oct 2001 15:29:00 +0400 (MSD)
From:      "Andrew L. Neporada" <andrew@nas.dgap.mipt.ru>
To:        Mike Barcroft <mike@FreeBSD.ORG>
Cc:        audit@FreeBSD.ORG, freebsd-hackers@FreeBSD.ORG
Subject:   Re: strnstr(3) - New libc function for review
Message-ID:  <Pine.BSF.4.21.0110101522160.50053-200000@nas.dgap.mipt.ru>
In-Reply-To: <20011004215706.B34530@coffee.q9media.com>
next in thread | previous in thread | raw e-mail | index | archive | help 

[-- Attachment #1 --]
I think you should write in ststr.3 that strnstr locates first occurrence
of null-terminated string 'little' in ___null-terminated___ string 'big'.

				Andrew.

P.S. Because str(n)str functions deal with null-terminated strings
(i.e. we don't know sizes of strings), it is impossible to write
algorithm, that will work faster (in average) than current implementation.

P.P.S. In the case of binary strings it is possible to implement faster
search -- see attachment.


On Thu, 4 Oct 2001, Mike Barcroft wrote:

> [BCC'd to -hackers for additional comments.]
> 
> Hello,
> I would appreciate comments/reviews of the following new addition to
> libc.  It is largely based off the current strstr(3) implementation.
> 
> Patch attached and also available at:
> http://people.FreeBSD.org/~mike/patches/strnstr.diff
> 
> 
> Best regards,
> Mike Barcroft
> 

[-- Attachment #2 --]
#include <sys/types.h>
#include <sys/time.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define	STRSZ	(100*1024)
#define	PATSZ	500
#define	TRYS	100

void *
bstrstr(s, slen, p, plen)
	register const void	*s, *p;
	size_t			slen, plen;
{
	register const u_char 	*str, *substr;
	register size_t		i, max_shift, curr_shift;

	size_t			shift[UCHAR_MAX + 1];

	if (s == NULL || p == NULL || plen > slen || slen == 0 || plen == 0)
		return (NULL);

	str = (const u_char *)s;
	substr = (const u_char *)p;

	for (i = 0; i <= UCHAR_MAX; i++) shift[i] = plen + 1;
	for (i = 0; i < plen; i++) shift[substr[i]] = plen - i;

	i = 0;
	max_shift = slen - plen;
	while (i <= max_shift) {
		if (*str == *substr && !memcmp(str + 1, substr + 1, plen -1))
			return ((void *)str);
		curr_shift = shift[str[plen]];
		str += curr_shift;
		i += curr_shift;
	}
	return (NULL);
}

int
main(void)
{
	char		*str;
	struct timeval	before, after;
	size_t		i;


	srandomdev();
	str = (char *)malloc(STRSZ + PATSZ + 1);
	if (!str) {
		printf("no mem\n");
		exit(1);
	}
	for (i = 0; i < STRSZ + PATSZ; i++) {
		str[i] = random() & 0xff;
		if (!str[i]) str[i] = 1;
	}
	str[STRSZ + PATSZ] = 0;

	printf("slen = %d, plen = %d\n", STRSZ + PATSZ, PATSZ);
	gettimeofday(&before, NULL);
	for (i = 0; i < TRYS; i++)
		strstr(str, str + STRSZ);
	gettimeofday(&after, NULL);
	after.tv_sec -= before.tv_sec;
	after.tv_usec -= before.tv_usec;
	printf("Old: %f sec\n", (after.tv_sec + after.tv_usec/1000000.0)/TRYS);

	gettimeofday(&before, NULL);
	for (i = 0; i < TRYS; i++)
		bstrstr(str, STRSZ + PATSZ, str + STRSZ, PATSZ);
	gettimeofday(&after, NULL);
	after.tv_sec -= before.tv_sec;
	after.tv_usec -= before.tv_usec;
	printf("New: %f sec\n", (after.tv_sec + after.tv_usec/1000000.0)/TRYS);
	free(str);
	return (0);
}

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.4.21.0110101522160.50053-200000>