sys/libkern/memcchr.c

   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  * $FreeBSD: src/sys/libkern/memcchr.c,v 1.1 2012/01/01 20:26:11 ed Exp $
  27  *
  28  */
  29
  30 #include <sys/cdefs.h>
  31
  32 #include <sys/libkern.h>
  33 #include <sys/limits.h>
  34 #include <sys/param.h>
  35
  36 /*
  37  * memcchr(): find first character in buffer not matching `c'.
  38  *
  39  * This function performs the complement of memchr().  To provide decent
  40  * performance, this function compares data from the buffer one word at
  41  * a time.
  42  *
  43  * This code is inspired by libc's strlen(), written by Xin Li.
  44  */
  45
  46 #if LONG_BIT != 32 && LONG_BIT != 64
  47 #error Unsupported word size
  48 #endif
  49
  50 #define LONGPTR_MASK (sizeof(long) - 1)
  51
  52 #define TESTBYTE                                \
  53         do {                                    \
  54                 if (*p != (unsigned char)c)     \
  55                         goto done;              \
  56                 p++;                            \
  57         } while (0)
  58
  59 void *
  60 memcchr(const void *begin, int c, size_t n)
  61 {
  62         const unsigned long *lp;
  63         const unsigned char *p, *end;
  64         unsigned long word;
  65
  66         /* Four or eight repetitions of `c'. */
  67         word = (unsigned char)c;
  68         word |= word << 8;
  69         word |= word << 16;
  70 #if LONG_BIT >= 64
  71         word |= word << 32;
  72 #endif
  73
  74         /* Don't perform memory I/O when passing a zero-length buffer. */
  75         if (n == 0)
  76                 return (NULL);
  77
  78         /*
  79          * First determine whether there is a character unequal to `c'
  80          * in the first word.  As this word may contain bytes before
  81          * `begin', we may execute this loop spuriously.
  82          */
  83         lp = (const unsigned long *)((uintptr_t)begin & ~LONGPTR_MASK);
  84         end = (const unsigned char *)begin + n;
  85         if (*lp++ != word)
  86                 for (p = begin; p < (const unsigned char *)lp;)
  87                         TESTBYTE;
  88
  89         /* Now compare the data one word at a time. */
  90         for (; (const unsigned char *)lp < end; lp++) {
  91                 if (*lp != word) {
  92                         p = (const unsigned char *)lp;
  93                         TESTBYTE;
  94                         TESTBYTE;
  95                         TESTBYTE;
  96 #if LONG_BIT >= 64
  97                         TESTBYTE;
  98                         TESTBYTE;
  99                         TESTBYTE;
 100                         TESTBYTE;
 101 #endif
 102                         goto done;
 103                 }
 104         }
 105
 106         return (NULL);
 107
 108 done:
 109         /*
 110          * If the end of the buffer is not word aligned, the previous
 111          * loops may obtain an address that's beyond the end of the
 112          * buffer.
 113          */
 114         if (p < end)
 115                 return (__DECONST(void *, p));
 116         return (NULL);
 117 }