memcchr.c revision 256281
1/*- 2 * Copyright (c) 2012 Ed Schouten <ed@FreeBSD.org> 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24 * SUCH DAMAGE. 25 */ 26 27#include <sys/cdefs.h> 28__FBSDID("$FreeBSD: stable/10/sys/libkern/memcchr.c 229198 2012-01-01 20:26:11Z ed $"); 29 30#include <sys/libkern.h> 31#include <sys/limits.h> 32#include <sys/param.h> 33 34/* 35 * memcchr(): find first character in buffer not matching `c'. 36 * 37 * This function performs the complement of memchr(). To provide decent 38 * performance, this function compares data from the buffer one word at 39 * a time. 40 * 41 * This code is inspired by libc's strlen(), written by Xin Li. 42 */ 43 44#if LONG_BIT != 32 && LONG_BIT != 64 45#error Unsupported word size 46#endif 47 48#define LONGPTR_MASK (sizeof(long) - 1) 49 50#define TESTBYTE \ 51 do { \ 52 if (*p != (unsigned char)c) \ 53 goto done; \ 54 p++; \ 55 } while (0) 56 57void * 58memcchr(const void *begin, int c, size_t n) 59{ 60 const unsigned long *lp; 61 const unsigned char *p, *end; 62 unsigned long word; 63 64 /* Four or eight repetitions of `c'. */ 65 word = (unsigned char)c; 66 word |= word << 8; 67 word |= word << 16; 68#if LONG_BIT >= 64 69 word |= word << 32; 70#endif 71 72 /* Don't perform memory I/O when passing a zero-length buffer. */ 73 if (n == 0) 74 return (NULL); 75 76 /* 77 * First determine whether there is a character unequal to `c' 78 * in the first word. As this word may contain bytes before 79 * `begin', we may execute this loop spuriously. 80 */ 81 lp = (const unsigned long *)((uintptr_t)begin & ~LONGPTR_MASK); 82 end = (const unsigned char *)begin + n; 83 if (*lp++ != word) 84 for (p = begin; p < (const unsigned char *)lp;) 85 TESTBYTE; 86 87 /* Now compare the data one word at a time. */ 88 for (; (const unsigned char *)lp < end; lp++) { 89 if (*lp != word) { 90 p = (const unsigned char *)lp; 91 TESTBYTE; 92 TESTBYTE; 93 TESTBYTE; 94#if LONG_BIT >= 64 95 TESTBYTE; 96 TESTBYTE; 97 TESTBYTE; 98 TESTBYTE; 99#endif 100 goto done; 101 } 102 } 103 104 return (NULL); 105 106done: 107 /* 108 * If the end of the buffer is not word aligned, the previous 109 * loops may obtain an address that's beyond the end of the 110 * buffer. 111 */ 112 if (p < end) 113 return (__DECONST(void *, p)); 114 return (NULL); 115} 116