Blame string/memrchr.c

Packit Service 82fcde
/* memrchr -- find the last occurrence of a byte in a memory block
Packit Service 82fcde
   Copyright (C) 1991-2018 Free Software Foundation, Inc.
Packit Service 82fcde
   This file is part of the GNU C Library.
Packit Service 82fcde
   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
Packit Service 82fcde
   with help from Dan Sahlin (dan@sics.se) and
Packit Service 82fcde
   commentary by Jim Blandy (jimb@ai.mit.edu);
Packit Service 82fcde
   adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
Packit Service 82fcde
   and implemented by Roland McGrath (roland@ai.mit.edu).
Packit Service 82fcde
Packit Service 82fcde
   The GNU C Library is free software; you can redistribute it and/or
Packit Service 82fcde
   modify it under the terms of the GNU Lesser General Public
Packit Service 82fcde
   License as published by the Free Software Foundation; either
Packit Service 82fcde
   version 2.1 of the License, or (at your option) any later version.
Packit Service 82fcde
Packit Service 82fcde
   The GNU C Library is distributed in the hope that it will be useful,
Packit Service 82fcde
   but WITHOUT ANY WARRANTY; without even the implied warranty of
Packit Service 82fcde
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
Packit Service 82fcde
   Lesser General Public License for more details.
Packit Service 82fcde
Packit Service 82fcde
   You should have received a copy of the GNU Lesser General Public
Packit Service 82fcde
   License along with the GNU C Library; if not, see
Packit Service 82fcde
   <http://www.gnu.org/licenses/>.  */
Packit Service 82fcde
Packit Service 82fcde
#include <stdlib.h>
Packit Service 82fcde
Packit Service 82fcde
#ifdef HAVE_CONFIG_H
Packit Service 82fcde
# include <config.h>
Packit Service 82fcde
#endif
Packit Service 82fcde
Packit Service 82fcde
#if defined _LIBC
Packit Service 82fcde
# include <string.h>
Packit Service 82fcde
# include <memcopy.h>
Packit Service 82fcde
#endif
Packit Service 82fcde
Packit Service 82fcde
#if defined HAVE_LIMITS_H || defined _LIBC
Packit Service 82fcde
# include <limits.h>
Packit Service 82fcde
#endif
Packit Service 82fcde
Packit Service 82fcde
#define LONG_MAX_32_BITS 2147483647
Packit Service 82fcde
Packit Service 82fcde
#ifndef LONG_MAX
Packit Service 82fcde
# define LONG_MAX LONG_MAX_32_BITS
Packit Service 82fcde
#endif
Packit Service 82fcde
Packit Service 82fcde
#include <sys/types.h>
Packit Service 82fcde
Packit Service 82fcde
#undef __memrchr
Packit Service 82fcde
#undef memrchr
Packit Service 82fcde
Packit Service 82fcde
#ifndef weak_alias
Packit Service 82fcde
# define __memrchr memrchr
Packit Service 82fcde
#endif
Packit Service 82fcde
Packit Service 82fcde
/* Search no more than N bytes of S for C.  */
Packit Service 82fcde
void *
Packit Service 82fcde
#ifndef MEMRCHR
Packit Service 82fcde
__memrchr
Packit Service 82fcde
#else
Packit Service 82fcde
MEMRCHR
Packit Service 82fcde
#endif
Packit Service 82fcde
     (const void *s, int c_in, size_t n)
Packit Service 82fcde
{
Packit Service 82fcde
  const unsigned char *char_ptr;
Packit Service 82fcde
  const unsigned long int *longword_ptr;
Packit Service 82fcde
  unsigned long int longword, magic_bits, charmask;
Packit Service 82fcde
  unsigned char c;
Packit Service 82fcde
Packit Service 82fcde
  c = (unsigned char) c_in;
Packit Service 82fcde
Packit Service 82fcde
  /* Handle the last few characters by reading one character at a time.
Packit Service 82fcde
     Do this until CHAR_PTR is aligned on a longword boundary.  */
Packit Service 82fcde
  for (char_ptr = (const unsigned char *) s + n;
Packit Service 82fcde
       n > 0 && ((unsigned long int) char_ptr
Packit Service 82fcde
		 & (sizeof (longword) - 1)) != 0;
Packit Service 82fcde
       --n)
Packit Service 82fcde
    if (*--char_ptr == c)
Packit Service 82fcde
      return (void *) char_ptr;
Packit Service 82fcde
Packit Service 82fcde
  /* All these elucidatory comments refer to 4-byte longwords,
Packit Service 82fcde
     but the theory applies equally well to 8-byte longwords.  */
Packit Service 82fcde
Packit Service 82fcde
  longword_ptr = (const unsigned long int *) char_ptr;
Packit Service 82fcde
Packit Service 82fcde
  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
Packit Service 82fcde
     the "holes."  Note that there is a hole just to the left of
Packit Service 82fcde
     each byte, with an extra at the end:
Packit Service 82fcde
Packit Service 82fcde
     bits:  01111110 11111110 11111110 11111111
Packit Service 82fcde
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
Packit Service 82fcde
Packit Service 82fcde
     The 1-bits make sure that carries propagate to the next 0-bit.
Packit Service 82fcde
     The 0-bits provide holes for carries to fall into.  */
Packit Service 82fcde
  magic_bits = -1;
Packit Service 82fcde
  magic_bits = magic_bits / 0xff * 0xfe << 1 >> 1 | 1;
Packit Service 82fcde
Packit Service 82fcde
  /* Set up a longword, each of whose bytes is C.  */
Packit Service 82fcde
  charmask = c | (c << 8);
Packit Service 82fcde
  charmask |= charmask << 16;
Packit Service 82fcde
#if LONG_MAX > LONG_MAX_32_BITS
Packit Service 82fcde
  charmask |= charmask << 32;
Packit Service 82fcde
#endif
Packit Service 82fcde
Packit Service 82fcde
  /* Instead of the traditional loop which tests each character,
Packit Service 82fcde
     we will test a longword at a time.  The tricky part is testing
Packit Service 82fcde
     if *any of the four* bytes in the longword in question are zero.  */
Packit Service 82fcde
  while (n >= sizeof (longword))
Packit Service 82fcde
    {
Packit Service 82fcde
      /* We tentatively exit the loop if adding MAGIC_BITS to
Packit Service 82fcde
	 LONGWORD fails to change any of the hole bits of LONGWORD.
Packit Service 82fcde
Packit Service 82fcde
	 1) Is this safe?  Will it catch all the zero bytes?
Packit Service 82fcde
	 Suppose there is a byte with all zeros.  Any carry bits
Packit Service 82fcde
	 propagating from its left will fall into the hole at its
Packit Service 82fcde
	 least significant bit and stop.  Since there will be no
Packit Service 82fcde
	 carry from its most significant bit, the LSB of the
Packit Service 82fcde
	 byte to the left will be unchanged, and the zero will be
Packit Service 82fcde
	 detected.
Packit Service 82fcde
Packit Service 82fcde
	 2) Is this worthwhile?  Will it ignore everything except
Packit Service 82fcde
	 zero bytes?  Suppose every byte of LONGWORD has a bit set
Packit Service 82fcde
	 somewhere.  There will be a carry into bit 8.  If bit 8
Packit Service 82fcde
	 is set, this will carry into bit 16.  If bit 8 is clear,
Packit Service 82fcde
	 one of bits 9-15 must be set, so there will be a carry
Packit Service 82fcde
	 into bit 16.  Similarly, there will be a carry into bit
Packit Service 82fcde
	 24.  If one of bits 24-30 is set, there will be a carry
Packit Service 82fcde
	 into bit 31, so all of the hole bits will be changed.
Packit Service 82fcde
Packit Service 82fcde
	 The one misfire occurs when bits 24-30 are clear and bit
Packit Service 82fcde
	 31 is set; in this case, the hole at bit 31 is not
Packit Service 82fcde
	 changed.  If we had access to the processor carry flag,
Packit Service 82fcde
	 we could close this loophole by putting the fourth hole
Packit Service 82fcde
	 at bit 32!
Packit Service 82fcde
Packit Service 82fcde
	 So it ignores everything except 128's, when they're aligned
Packit Service 82fcde
	 properly.
Packit Service 82fcde
Packit Service 82fcde
	 3) But wait!  Aren't we looking for C, not zero?
Packit Service 82fcde
	 Good point.  So what we do is XOR LONGWORD with a longword,
Packit Service 82fcde
	 each of whose bytes is C.  This turns each byte that is C
Packit Service 82fcde
	 into a zero.  */
Packit Service 82fcde
Packit Service 82fcde
      longword = *--longword_ptr ^ charmask;
Packit Service 82fcde
Packit Service 82fcde
      /* Add MAGIC_BITS to LONGWORD.  */
Packit Service 82fcde
      if ((((longword + magic_bits)
Packit Service 82fcde
Packit Service 82fcde
	    /* Set those bits that were unchanged by the addition.  */
Packit Service 82fcde
	    ^ ~longword)
Packit Service 82fcde
Packit Service 82fcde
	   /* Look at only the hole bits.  If any of the hole bits
Packit Service 82fcde
	      are unchanged, most likely one of the bytes was a
Packit Service 82fcde
	      zero.  */
Packit Service 82fcde
	   & ~magic_bits) != 0)
Packit Service 82fcde
	{
Packit Service 82fcde
	  /* Which of the bytes was C?  If none of them were, it was
Packit Service 82fcde
	     a misfire; continue the search.  */
Packit Service 82fcde
Packit Service 82fcde
	  const unsigned char *cp = (const unsigned char *) longword_ptr;
Packit Service 82fcde
Packit Service 82fcde
#if LONG_MAX > 2147483647
Packit Service 82fcde
	  if (cp[7] == c)
Packit Service 82fcde
	    return (void *) &cp[7];
Packit Service 82fcde
	  if (cp[6] == c)
Packit Service 82fcde
	    return (void *) &cp[6];
Packit Service 82fcde
	  if (cp[5] == c)
Packit Service 82fcde
	    return (void *) &cp[5];
Packit Service 82fcde
	  if (cp[4] == c)
Packit Service 82fcde
	    return (void *) &cp[4];
Packit Service 82fcde
#endif
Packit Service 82fcde
	  if (cp[3] == c)
Packit Service 82fcde
	    return (void *) &cp[3];
Packit Service 82fcde
	  if (cp[2] == c)
Packit Service 82fcde
	    return (void *) &cp[2];
Packit Service 82fcde
	  if (cp[1] == c)
Packit Service 82fcde
	    return (void *) &cp[1];
Packit Service 82fcde
	  if (cp[0] == c)
Packit Service 82fcde
	    return (void *) cp;
Packit Service 82fcde
	}
Packit Service 82fcde
Packit Service 82fcde
      n -= sizeof (longword);
Packit Service 82fcde
    }
Packit Service 82fcde
Packit Service 82fcde
  char_ptr = (const unsigned char *) longword_ptr;
Packit Service 82fcde
Packit Service 82fcde
  while (n-- > 0)
Packit Service 82fcde
    {
Packit Service 82fcde
      if (*--char_ptr == c)
Packit Service 82fcde
	return (void *) char_ptr;
Packit Service 82fcde
    }
Packit Service 82fcde
Packit Service 82fcde
  return 0;
Packit Service 82fcde
}
Packit Service 82fcde
#ifndef MEMRCHR
Packit Service 82fcde
# ifdef weak_alias
Packit Service 82fcde
weak_alias (__memrchr, memrchr)
Packit Service 82fcde
# endif
Packit Service 82fcde
#endif