string/memchr.c

   1 /* Scan memory for a character.  Generic version
   2    Copyright (C) 1991-2023 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library; if not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 #include <libc-pointer-arith.h>
  20 #include <string-fzb.h>
  21 #include <string-fzc.h>
  22 #include <string-fzi.h>
  23 #include <string-shift.h>
  24 #include <string.h>
  25
  26 #undef memchr
  27
  28 #ifdef MEMCHR
  29 # define __memchr MEMCHR
  30 #endif
  31
  32 static __always_inline const char *
  33 sadd (uintptr_t x, uintptr_t y)
  34 {
  35   return (const char *)(y > UINTPTR_MAX - x ? UINTPTR_MAX : x + y);
  36 }
  37
  38 /* Search no more than N bytes of S for C.  */
  39 void *
  40 __memchr (void const *s, int c_in, size_t n)
  41 {
  42   if (__glibc_unlikely (n == 0))
  43     return NULL;
  44
  45   /* Read the first word, but munge it so that bytes before the array
  46      will not match goal.  */
  47   const op_t *word_ptr = PTR_ALIGN_DOWN (s, sizeof (op_t));
  48   uintptr_t s_int = (uintptr_t) s;
  49
  50   op_t word = *word_ptr;
  51   op_t repeated_c = repeat_bytes (c_in);
  52   /* Compute the address of the last byte taking in consideration possible
  53      overflow.  */
  54   const char *lbyte = sadd (s_int, n - 1);
  55   /* And also the address of the word containing the last byte. */
  56   const op_t *lword = (const op_t *) PTR_ALIGN_DOWN (lbyte, sizeof (op_t));
  57
  58   find_t mask = shift_find (find_eq_all (word, repeated_c), s_int);
  59   if (mask != 0)
  60     {
  61       char *ret = (char *) s + index_first (mask);
  62       return (ret <= lbyte) ? ret : NULL;
  63     }
  64   if (word_ptr == lword)
  65     return NULL;
  66
  67   word = *++word_ptr;
  68   while (word_ptr != lword)
  69     {
  70       if (has_eq (word, repeated_c))
  71         return (char *) word_ptr + index_first_eq (word, repeated_c);
  72       word = *++word_ptr;
  73     }
  74
  75   if (has_eq (word, repeated_c))
  76     {
  77       /* We found a match, but it might be in a byte past the end of the
  78          array.  */
  79       char *ret = (char *) word_ptr + index_first_eq (word, repeated_c);
  80       if (ret <= lbyte)
  81         return ret;
  82     }
  83   return NULL;
  84 }
  85 #ifndef MEMCHR
  86 weak_alias (__memchr, memchr)
  87 libc_hidden_builtin_def (memchr)
  88 #endif