lib/memchr2.c

   1 /* Copyright (C) 1991, 1993, 1996, 1997, 1999, 2000, 2003, 2004, 2006,
   2    2008 Free Software Foundation, Inc.
   3
   4    Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
   5    with help from Dan Sahlin (dan@sics.se) and
   6    commentary by Jim Blandy (jimb@ai.mit.edu);
   7    adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
   8    and implemented in glibc by Roland McGrath (roland@ai.mit.edu).
   9    Extension to memchr2 implemented by Eric Blake (ebb9@byu.net).
  10
  11 This program is free software: you can redistribute it and/or modify it
  12 under the terms of the GNU General Public License as published by the
  13 Free Software Foundation; either version 3 of the License, or any
  14 later version.
  15
  16 This program is distributed in the hope that it will be useful,
  17 but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 GNU General Public License for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  23
  24 #include <config.h>
  25
  26 #include "memchr2.h"
  27
  28 #include <limits.h>
  29 #include <stdint.h>
  30 #include <string.h>
  31
  32 #include "intprops.h"
  33
  34 /* Return the first address of either C1 or C2 (treated as unsigned
  35    char) that occurs within N bytes of the memory region S.  If
  36    neither byte appears, return NULL.  */
  37 void *
  38 memchr2 (void const *s, int c1_in, int c2_in, size_t n)
  39 {
  40   /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
  41      long instead of a 64-bit uintmax_t tends to give better
  42      performance.  On 64-bit hardware, unsigned long is generally 64
  43      bits already.  Change this typedef to experiment with
  44      performance.  */
  45   typedef unsigned long longword;
  46
  47   const unsigned char *char_ptr;
  48   const longword *longword_ptr;
  49   longword longword1;
  50   longword longword2;
  51   longword magic_bits;
  52   longword charmask1;
  53   longword charmask2;
  54   unsigned char c1;
  55   unsigned char c2;
  56   int i;
  57
  58   c1 = (unsigned char) c1_in;
  59   c2 = (unsigned char) c2_in;
  60
  61   if (c1 == c2)
  62     return memchr (s, c1, n);
  63
  64   /* Handle the first few characters by reading one character at a time.
  65      Do this until CHAR_PTR is aligned on a longword boundary.  */
  66   for (char_ptr = (const unsigned char *) s;
  67        n > 0 && (size_t) char_ptr % sizeof longword1 != 0;
  68        --n, ++char_ptr)
  69     if (*char_ptr == c1 || *char_ptr == c2)
  70       return (void *) char_ptr;
  71
  72   /* All these elucidatory comments refer to 4-byte longwords,
  73      but the theory applies equally well to any size longwords.  */
  74
  75   longword_ptr = (const longword *) char_ptr;
  76   magic_bits = 0x01010101;
  77   charmask1 = c1 | (c1 << 8);
  78   charmask2 = c2 | (c2 << 8);
  79   charmask1 |= charmask1 << 16;
  80   charmask2 |= charmask2 << 16;
  81   if (0xffffffffU < TYPE_MAXIMUM (longword))
  82     {
  83       magic_bits |= magic_bits << 31 << 1;
  84       charmask1 |= charmask1 << 31 << 1;
  85       charmask2 |= charmask2 << 31 << 1;
  86       if (8 < sizeof longword1)
  87         for (i = 64; i < sizeof longword1 * 8; i *= 2)
  88           {
  89             magic_bits |= magic_bits << i;
  90             charmask1 |= charmask1 << i;
  91             charmask2 |= charmask2 << i;
  92           }
  93     }
  94
  95   /* Instead of the traditional loop which tests each character,
  96      we will test a longword at a time.  The tricky part is testing
  97      if *any of the four* bytes in the longword in question are zero.
  98
  99      We first use an xor to convert target bytes into a NUL byte,
 100      since the test for a zero byte is more efficient.  For all byte
 101      values except 0x00 and 0x80, subtracting 1 from the byte will
 102      leave the most significant bit unchanged.  So detecting 0 is
 103      simply a matter of subtracting from all bytes in parallel, and
 104      checking for a most significant bit that changed to 1.  */
 105
 106   while (n >= sizeof longword1)
 107     {
 108       longword1 = *longword_ptr ^ charmask1;
 109       longword2 = *longword_ptr ^ charmask2;
 110
 111       if (((((longword1 - magic_bits) & ~longword1)
 112             | ((longword2 - magic_bits) & ~longword2))
 113            & (magic_bits << 7)) != 0)
 114         break;
 115       longword_ptr++;
 116       n -= sizeof longword1;
 117     }
 118
 119   char_ptr = (const unsigned char *) longword_ptr;
 120
 121   while (n-- > 0)
 122     {
 123       if (*char_ptr == c1 || *char_ptr == c2)
 124         return (void *) char_ptr;
 125       ++char_ptr;
 126     }
 127
 128   return NULL;
 129 }