Back to index

nagios-plugins  1.4.16
memchr.c
Go to the documentation of this file.
00001 /* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2010
00002    Free Software Foundation, Inc.
00003 
00004    Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
00005    with help from Dan Sahlin (dan@sics.se) and
00006    commentary by Jim Blandy (jimb@ai.mit.edu);
00007    adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
00008    and implemented by Roland McGrath (roland@ai.mit.edu).
00009 
00010 NOTE: The canonical source of this file is maintained with the GNU C Library.
00011 Bugs can be reported to bug-glibc@prep.ai.mit.edu.
00012 
00013 This program is free software: you can redistribute it and/or modify it
00014 under the terms of the GNU General Public License as published by the
00015 Free Software Foundation; either version 3 of the License, or any
00016 later version.
00017 
00018 This program is distributed in the hope that it will be useful,
00019 but WITHOUT ANY WARRANTY; without even the implied warranty of
00020 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00021 GNU General Public License for more details.
00022 
00023 You should have received a copy of the GNU General Public License
00024 along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
00025 
00026 #ifndef _LIBC
00027 # include <config.h>
00028 #endif
00029 
00030 #include <string.h>
00031 
00032 #include <stddef.h>
00033 
00034 #if defined _LIBC
00035 # include <memcopy.h>
00036 #else
00037 # define reg_char char
00038 #endif
00039 
00040 #include <limits.h>
00041 
00042 #if HAVE_BP_SYM_H || defined _LIBC
00043 # include <bp-sym.h>
00044 #else
00045 # define BP_SYM(sym) sym
00046 #endif
00047 
00048 #undef __memchr
00049 #ifdef _LIBC
00050 # undef memchr
00051 #endif
00052 
00053 #ifndef weak_alias
00054 # define __memchr memchr
00055 #endif
00056 
00057 /* Search no more than N bytes of S for C.  */
00058 void *
00059 __memchr (void const *s, int c_in, size_t n)
00060 {
00061   /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
00062      long instead of a 64-bit uintmax_t tends to give better
00063      performance.  On 64-bit hardware, unsigned long is generally 64
00064      bits already.  Change this typedef to experiment with
00065      performance.  */
00066   typedef unsigned long int longword;
00067 
00068   const unsigned char *char_ptr;
00069   const longword *longword_ptr;
00070   longword repeated_one;
00071   longword repeated_c;
00072   unsigned reg_char c;
00073 
00074   c = (unsigned char) c_in;
00075 
00076   /* Handle the first few bytes by reading one byte at a time.
00077      Do this until CHAR_PTR is aligned on a longword boundary.  */
00078   for (char_ptr = (const unsigned char *) s;
00079        n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
00080        --n, ++char_ptr)
00081     if (*char_ptr == c)
00082       return (void *) char_ptr;
00083 
00084   longword_ptr = (const longword *) char_ptr;
00085 
00086   /* All these elucidatory comments refer to 4-byte longwords,
00087      but the theory applies equally well to any size longwords.  */
00088 
00089   /* Compute auxiliary longword values:
00090      repeated_one is a value which has a 1 in every byte.
00091      repeated_c has c in every byte.  */
00092   repeated_one = 0x01010101;
00093   repeated_c = c | (c << 8);
00094   repeated_c |= repeated_c << 16;
00095   if (0xffffffffU < (longword) -1)
00096     {
00097       repeated_one |= repeated_one << 31 << 1;
00098       repeated_c |= repeated_c << 31 << 1;
00099       if (8 < sizeof (longword))
00100         {
00101           size_t i;
00102 
00103           for (i = 64; i < sizeof (longword) * 8; i *= 2)
00104             {
00105               repeated_one |= repeated_one << i;
00106               repeated_c |= repeated_c << i;
00107             }
00108         }
00109     }
00110 
00111   /* Instead of the traditional loop which tests each byte, we will test a
00112      longword at a time.  The tricky part is testing if *any of the four*
00113      bytes in the longword in question are equal to c.  We first use an xor
00114      with repeated_c.  This reduces the task to testing whether *any of the
00115      four* bytes in longword1 is zero.
00116 
00117      We compute tmp =
00118        ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
00119      That is, we perform the following operations:
00120        1. Subtract repeated_one.
00121        2. & ~longword1.
00122        3. & a mask consisting of 0x80 in every byte.
00123      Consider what happens in each byte:
00124        - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
00125          and step 3 transforms it into 0x80.  A carry can also be propagated
00126          to more significant bytes.
00127        - If a byte of longword1 is nonzero, let its lowest 1 bit be at
00128          position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
00129          the byte ends in a single bit of value 0 and k bits of value 1.
00130          After step 2, the result is just k bits of value 1: 2^k - 1.  After
00131          step 3, the result is 0.  And no carry is produced.
00132      So, if longword1 has only non-zero bytes, tmp is zero.
00133      Whereas if longword1 has a zero byte, call j the position of the least
00134      significant zero byte.  Then the result has a zero at positions 0, ...,
00135      j-1 and a 0x80 at position j.  We cannot predict the result at the more
00136      significant bytes (positions j+1..3), but it does not matter since we
00137      already have a non-zero bit at position 8*j+7.
00138 
00139      So, the test whether any byte in longword1 is zero is equivalent to
00140      testing whether tmp is nonzero.  */
00141 
00142   while (n >= sizeof (longword))
00143     {
00144       longword longword1 = *longword_ptr ^ repeated_c;
00145 
00146       if ((((longword1 - repeated_one) & ~longword1)
00147            & (repeated_one << 7)) != 0)
00148         break;
00149       longword_ptr++;
00150       n -= sizeof (longword);
00151     }
00152 
00153   char_ptr = (const unsigned char *) longword_ptr;
00154 
00155   /* At this point, we know that either n < sizeof (longword), or one of the
00156      sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
00157      machines, we could determine the first such byte without any further
00158      memory accesses, just by looking at the tmp result from the last loop
00159      iteration.  But this does not work on big-endian machines.  Choose code
00160      that works in both cases.  */
00161 
00162   for (; n > 0; --n, ++char_ptr)
00163     {
00164       if (*char_ptr == c)
00165         return (void *) char_ptr;
00166     }
00167 
00168   return NULL;
00169 }
00170 #ifdef weak_alias
00171 weak_alias (__memchr, BP_SYM (memchr))
00172 #endif