From owner-svn-src-all@FreeBSD.ORG Sun Jan 1 20:26:11 2012 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id CFD2B1065673; Sun, 1 Jan 2012 20:26:11 +0000 (UTC) (envelope-from ed@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id BA2CF8FC0C; Sun, 1 Jan 2012 20:26:11 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id q01KQBAS029160; Sun, 1 Jan 2012 20:26:11 GMT (envelope-from ed@svn.freebsd.org) Received: (from ed@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id q01KQBS5029156; Sun, 1 Jan 2012 20:26:11 GMT (envelope-from ed@svn.freebsd.org) Message-Id: <201201012026.q01KQBS5029156@svn.freebsd.org> From: Ed Schouten Date: Sun, 1 Jan 2012 20:26:11 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r229198 - in head: share/man/man9 sys/conf sys/libkern sys/sys X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 01 Jan 2012 20:26:11 -0000 Author: ed Date: Sun Jan 1 20:26:11 2012 New Revision: 229198 URL: http://svn.freebsd.org/changeset/base/229198 Log: Introducing memcchr(3). It seems two of the file system drivers we have in the tree, namely ufs and ext3, use a function called `skpc()'. The meaning of this function does not seem to be documented in FreeBSD, but it turns out one needs to be a VAX programmer to understand what it does. SPKC is an instruction on the VAX that does the opposite of memchr(). It searches for the non-equal character. Add a new function called memcchr() to the tree that has the following advantages over skpc(): - It has a name that makes more sense than skpc(). Just like strcspn() matches the complement of strspn(), memcchr() is the complement of memchr(). - It is faster than skpc(). Similar to our strlen() in libc, it compares entire words, instead of single bytes. It seems that for this routine this yields a sixfold performance increase on amd64. - It has a man page. Added: head/share/man/man9/memcchr.3 (contents, props changed) head/sys/libkern/memcchr.c (contents, props changed) Modified: head/sys/conf/files head/sys/sys/libkern.h Added: head/share/man/man9/memcchr.3 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/share/man/man9/memcchr.3 Sun Jan 1 20:26:11 2012 (r229198) @@ -0,0 +1,59 @@ +.\" Copyright (c) 2012 Ed Schouten +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" $FreeBSD$ +.\" +.Dd January 1, 2012 +.Dt MEMCCHR 9 +.Os +.Sh NAME +.Nm memcchr +.Nd locate the complement of a byte in byte string +.Sh SYNOPSIS +.In sys/libkern.h +.Ft void * +.Fn memcchr "const void *b" "int c" "size_t len" +.Sh DESCRIPTION +The +.Fn memcchr +function locates the first occurrence of a byte unequal to +.Fa c +(converted to an +.Vt "unsigned char" ) +in string +.Fa b . +.Sh RETURN VALUES +The +.Fn memcchr +function return a pointer to the byte located, or NULL if no such byte +exists within +.Fa len +bytes. +.Sh SEE ALSO +.Xr memchr 3 +.Sh HISTORY +The +.Fn memcchr +function first appeared in +.Fx 10.0 . Modified: head/sys/conf/files ============================================================================== --- head/sys/conf/files Sun Jan 1 20:18:40 2012 (r229197) +++ head/sys/conf/files Sun Jan 1 20:26:11 2012 (r229198) @@ -2557,6 +2557,7 @@ libkern/inet_ntoa.c standard libkern/inet_ntop.c standard libkern/inet_pton.c standard libkern/mcount.c optional profiling-routine +libkern/memcchr.c standard libkern/memcmp.c standard libkern/qsort.c standard libkern/qsort_r.c standard Added: head/sys/libkern/memcchr.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ head/sys/libkern/memcchr.c Sun Jan 1 20:26:11 2012 (r229198) @@ -0,0 +1,115 @@ +/*- + * Copyright (c) 2012 Ed Schouten + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +#include +__FBSDID("$FreeBSD$"); + +#include +#include +#include + +/* + * memcchr(): find first character in buffer not matching `c'. + * + * This function performs the complement of memchr(). To provide decent + * performance, this function compares data from the buffer one word at + * a time. + * + * This code is inspired by libc's strlen(), written by Xin Li. + */ + +#if LONG_BIT != 32 && LONG_BIT != 64 +#error Unsupported word size +#endif + +#define LONGPTR_MASK (sizeof(long) - 1) + +#define TESTBYTE \ + do { \ + if (*p != (unsigned char)c) \ + goto done; \ + p++; \ + } while (0) + +void * +memcchr(const void *begin, int c, size_t n) +{ + const unsigned long *lp; + const unsigned char *p, *end; + unsigned long word; + + /* Four or eight repetitions of `c'. */ + word = (unsigned char)c; + word |= word << 8; + word |= word << 16; +#if LONG_BIT >= 64 + word |= word << 32; +#endif + + /* Don't perform memory I/O when passing a zero-length buffer. */ + if (n == 0) + return (NULL); + + /* + * First determine whether there is a character unequal to `c' + * in the first word. As this word may contain bytes before + * `begin', we may execute this loop spuriously. + */ + lp = (const unsigned long *)((uintptr_t)begin & ~LONGPTR_MASK); + end = (const unsigned char *)begin + n; + if (*lp++ != word) + for (p = begin; p < (const unsigned char *)lp;) + TESTBYTE; + + /* Now compare the data one word at a time. */ + for (; (const unsigned char *)lp < end; lp++) { + if (*lp != word) { + p = (const unsigned char *)lp; + TESTBYTE; + TESTBYTE; + TESTBYTE; +#if LONG_BIT >= 64 + TESTBYTE; + TESTBYTE; + TESTBYTE; + TESTBYTE; +#endif + goto done; + } + } + + return (NULL); + +done: + /* + * If the end of the buffer is not word aligned, the previous + * loops may obtain an address that's beyond the end of the + * buffer. + */ + if (p < end) + return (__DECONST(void *, p)); + return (NULL); +} Modified: head/sys/sys/libkern.h ============================================================================== --- head/sys/sys/libkern.h Sun Jan 1 20:18:40 2012 (r229197) +++ head/sys/sys/libkern.h Sun Jan 1 20:26:11 2012 (r229198) @@ -92,6 +92,7 @@ int flsl(long); int fnmatch(const char *, const char *, int); int locc(int, char *, u_int); void *memchr(const void *s, int c, size_t n); +void *memcchr(const void *s, int c, size_t n); int memcmp(const void *b1, const void *b2, size_t len); void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));