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
  27 #include <sys/cdefs.h>
  28 __FBSDID("$FreeBSD$");
  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
  57 void *
  58 memcchr(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
 106 done:
 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 }