Ignore:
Timestamp:
Sep 19, 2024, 2:34:43 AM (10 months ago)
Author:
bird
Message:

src/sed: Merged in changes between 4.1.5 and 4.9 from the vendor branch. (svn merge /vendor/sed/4.1.5 /vendor/sed/current .)

Location:
trunk/src/sed
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/sed

  • trunk/src/sed/lib/memchr.c

    r599 r3613  
    1 /* Copyright (C) 1991, 1993, 1996, 1997 Free Software Foundation, Inc.
     1/* Copyright (C) 1991, 1993, 1996-1997, 1999-2000, 2003-2004, 2006, 2008-2022
     2   Free Software Foundation, Inc.
     3
    24   Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
    35   with help from Dan Sahlin (dan@sics.se) and
    … …  
    79
    810   NOTE: The canonical source of this file is maintained with the GNU C Library.
    9    Bugs can be reported to bug-glibc@gnu.org.
     11   Bugs can be reported to bug-glibc@prep.ai.mit.edu.
    1012
    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 2, or (at your option) any
    14    later version.
     13   This file is free software: you can redistribute it and/or modify
     14   it under the terms of the GNU Lesser General Public License as
     15   published by the Free Software Foundation; either version 2.1 of the
     16   License, or (at your option) any later version.
    1517
    16    This program is distributed in the hope that it will be useful,
     18   This file is distributed in the hope that it will be useful,
    1719   but WITHOUT ANY WARRANTY; without even the implied warranty of
    1820   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    19    GNU General Public License for more details.
     21   GNU Lesser General Public License for more details.
    2022
    21    You should have received a copy of the GNU General Public License
    22    along with this program; if not, write to the Free Software
    23    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    24    USA.  */
     23   You should have received a copy of the GNU Lesser General Public License
     24   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
    2525
    26 #ifdef HAVE_CONFIG_H
    27 #include <config.h>
     26#ifndef _LIBC
     27# include <config.h>
    2828#endif
    2929
    30 #undef __ptr_t
    31 #if defined (__cplusplus) || (defined (__STDC__) && __STDC__)
    32 # define __ptr_t void *
    33 #else /* Not C++ or ANSI C.  */
    34 # define __ptr_t char *
    35 #endif /* C++ or ANSI C.  */
     30#include <string.h>
    3631
    37 #if defined (_LIBC)
    38 # include <string.h>
     32#include <stddef.h>
     33
     34#if defined _LIBC
     35# include <memcopy.h>
     36#else
     37# define reg_char char
    3938#endif
    4039
    41 #if defined (HAVE_LIMITS_H) || defined (_LIBC)
    42 # include <limits.h>
     40#include <limits.h>
     41
     42#if HAVE_BP_SYM_H || defined _LIBC
     43# include <bp-sym.h>
     44#else
     45# define BP_SYM(sym) sym
    4346#endif
    4447
    45 #define LONG_MAX_32_BITS 2147483647
    46 
    47 #ifndef LONG_MAX
    48 #define LONG_MAX LONG_MAX_32_BITS
     48#undef __memchr
     49#ifdef _LIBC
     50# undef memchr
    4951#endif
    5052
    51 #include <sys/types.h>
    52 
    53 #undef memchr
    54 
     53#ifndef weak_alias
     54# define __memchr memchr
     55#endif
    5556
    5657/* Search no more than N bytes of S for C.  */
    57 __ptr_t
    58 memchr (s, c, n)
    59      const __ptr_t s;
    60      int c;
    61      size_t n;
     58void *
     59__memchr (void const *s, int c_in, size_t n)
    6260{
     61  /* On 32-bit hardware, choosing longword to be a 32-bit unsigned
     62     long instead of a 64-bit uintmax_t tends to give better
     63     performance.  On 64-bit hardware, unsigned long is generally 64
     64     bits already.  Change this typedef to experiment with
     65     performance.  */
     66  typedef unsigned long int longword;
     67
    6368  const unsigned char *char_ptr;
    64   const unsigned long int *longword_ptr;
    65   unsigned long int longword, magic_bits, charmask;
     69  const longword *longword_ptr;
     70  longword repeated_one;
     71  longword repeated_c;
     72  unsigned reg_char c;
    6673
    67   c = (unsigned char) c;
     74  c = (unsigned char) c_in;
    6875
    69   /* Handle the first few characters by reading one character at a time.
     76  /* Handle the first few bytes by reading one byte at a time.
    7077     Do this until CHAR_PTR is aligned on a longword boundary.  */
    7178  for (char_ptr = (const unsigned char *) s;
    72        n > 0 && ((unsigned long int) char_ptr
    73                  & (sizeof (longword) - 1)) != 0;
     79       n > 0 && (size_t) char_ptr % sizeof (longword) != 0;
    7480       --n, ++char_ptr)
    7581    if (*char_ptr == c)
    76       return (__ptr_t) char_ptr;
     82      return (void *) char_ptr;
     83
     84  longword_ptr = (const longword *) char_ptr;
    7785
    7886  /* All these elucidatory comments refer to 4-byte longwords,
    79      but the theory applies equally well to 8-byte longwords.  */
     87     but the theory applies equally well to any size longwords.  */
    8088
    81   longword_ptr = (unsigned long int *) char_ptr;
     89  /* Compute auxiliary longword values:
     90     repeated_one is a value which has a 1 in every byte.
     91     repeated_c has c in every byte.  */
     92  repeated_one = 0x01010101;
     93  repeated_c = c | (c << 8);
     94  repeated_c |= repeated_c << 16;
     95  if (0xffffffffU < (longword) -1)
     96    {
     97      repeated_one |= repeated_one << 31 << 1;
     98      repeated_c |= repeated_c << 31 << 1;
     99      if (8 < sizeof (longword))
     100        {
     101          size_t i;
    82102
    83   /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
    84      the "holes."  Note that there is a hole just to the left of
    85      each byte, with an extra at the end:
     103          for (i = 64; i < sizeof (longword) * 8; i *= 2)
     104            {
     105              repeated_one |= repeated_one << i;
     106              repeated_c |= repeated_c << i;
     107            }
     108        }
     109    }
    86110
    87      bits:  01111110 11111110 11111110 11111111
    88      bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
     111  /* Instead of the traditional loop which tests each byte, we will test a
     112     longword at a time.  The tricky part is testing if *any of the four*
     113     bytes in the longword in question are equal to c.  We first use an xor
     114     with repeated_c.  This reduces the task to testing whether *any of the
     115     four* bytes in longword1 is zero.
    89116
    90      The 1-bits make sure that carries propagate to the next 0-bit.
    91      The 0-bits provide holes for carries to fall into.  */
     117     We compute tmp =
     118       ((longword1 - repeated_one) & ~longword1) & (repeated_one << 7).
     119     That is, we perform the following operations:
     120       1. Subtract repeated_one.
     121       2. & ~longword1.
     122       3. & a mask consisting of 0x80 in every byte.
     123     Consider what happens in each byte:
     124       - If a byte of longword1 is zero, step 1 and 2 transform it into 0xff,
     125         and step 3 transforms it into 0x80.  A carry can also be propagated
     126         to more significant bytes.
     127       - If a byte of longword1 is nonzero, let its lowest 1 bit be at
     128         position k (0 <= k <= 7); so the lowest k bits are 0.  After step 1,
     129         the byte ends in a single bit of value 0 and k bits of value 1.
     130         After step 2, the result is just k bits of value 1: 2^k - 1.  After
     131         step 3, the result is 0.  And no carry is produced.
     132     So, if longword1 has only non-zero bytes, tmp is zero.
     133     Whereas if longword1 has a zero byte, call j the position of the least
     134     significant zero byte.  Then the result has a zero at positions 0, ...,
     135     j-1 and a 0x80 at position j.  We cannot predict the result at the more
     136     significant bytes (positions j+1..3), but it does not matter since we
     137     already have a non-zero bit at position 8*j+7.
    92138
    93   if (sizeof (longword) != 4 && sizeof (longword) != 8)
    94     abort ();
     139     So, the test whether any byte in longword1 is zero is equivalent to
     140     testing whether tmp is nonzero.  */
    95141
    96 #if LONG_MAX <= LONG_MAX_32_BITS
    97   magic_bits = 0x7efefeff;
    98 #else
    99   magic_bits = ((unsigned long int) 0x7efefefe << 32) | 0xfefefeff;
    100 #endif
    101 
    102   /* Set up a longword, each of whose bytes is C.  */
    103   charmask = c | (c << 8);
    104   charmask |= charmask << 16;
    105 #if LONG_MAX > LONG_MAX_32_BITS
    106   charmask |= charmask << 32;
    107 #endif
    108 
    109   /* Instead of the traditional loop which tests each character,
    110      we will test a longword at a time.  The tricky part is testing
    111      if *any of the four* bytes in the longword in question are zero.  */
    112142  while (n >= sizeof (longword))
    113143    {
    114       /* We tentatively exit the loop if adding MAGIC_BITS to
    115          LONGWORD fails to change any of the hole bits of LONGWORD.
     144      longword longword1 = *longword_ptr ^ repeated_c;
    116145
    117          1) Is this safe?  Will it catch all the zero bytes?
    118          Suppose there is a byte with all zeros.  Any carry bits
    119          propagating from its left will fall into the hole at its
    120          least significant bit and stop.  Since there will be no
    121          carry from its most significant bit, the LSB of the
    122          byte to the left will be unchanged, and the zero will be
    123          detected.
    124 
    125          2) Is this worthwhile?  Will it ignore everything except
    126          zero bytes?  Suppose every byte of LONGWORD has a bit set
    127          somewhere.  There will be a carry into bit 8.  If bit 8
    128          is set, this will carry into bit 16.  If bit 8 is clear,
    129          one of bits 9-15 must be set, so there will be a carry
    130          into bit 16.  Similarly, there will be a carry into bit
    131          24.  If one of bits 24-30 is set, there will be a carry
    132          into bit 31, so all of the hole bits will be changed.
    133 
    134          The one misfire occurs when bits 24-30 are clear and bit
    135          31 is set; in this case, the hole at bit 31 is not
    136          changed.  If we had access to the processor carry flag,
    137          we could close this loophole by putting the fourth hole
    138          at bit 32!
    139 
    140          So it ignores everything except 128's, when they're aligned
    141          properly.
    142 
    143          3) But wait!  Aren't we looking for C, not zero?
    144          Good point.  So what we do is XOR LONGWORD with a longword,
    145          each of whose bytes is C.  This turns each byte that is C
    146          into a zero.  */
    147 
    148       longword = *longword_ptr++ ^ charmask;
    149 
    150       /* Add MAGIC_BITS to LONGWORD.  */
    151       if ((((longword + magic_bits)
    152 
    153             /* Set those bits that were unchanged by the addition.  */
    154             ^ ~longword)
    155 
    156            /* Look at only the hole bits.  If any of the hole bits
    157               are unchanged, most likely one of the bytes was a
    158               zero.  */
    159            & ~magic_bits) != 0)
    160         {
    161           /* Which of the bytes was C?  If none of them were, it was
    162              a misfire; continue the search.  */
    163 
    164           const unsigned char *cp = (const unsigned char *) (longword_ptr - 1);
    165 
    166           if (cp[0] == c)
    167             return (__ptr_t) cp;
    168           if (cp[1] == c)
    169             return (__ptr_t) &cp[1];
    170           if (cp[2] == c)
    171             return (__ptr_t) &cp[2];
    172           if (cp[3] == c)
    173             return (__ptr_t) &cp[3];
    174 #if LONG_MAX > 2147483647
    175           if (cp[4] == c)
    176             return (__ptr_t) &cp[4];
    177           if (cp[5] == c)
    178             return (__ptr_t) &cp[5];
    179           if (cp[6] == c)
    180             return (__ptr_t) &cp[6];
    181           if (cp[7] == c)
    182             return (__ptr_t) &cp[7];
    183 #endif
    184         }
    185 
     146      if ((((longword1 - repeated_one) & ~longword1)
     147           & (repeated_one << 7)) != 0)
     148        break;
     149      longword_ptr++;
    186150      n -= sizeof (longword);
    187151    }
    … …  
    189153  char_ptr = (const unsigned char *) longword_ptr;
    190154
    191   while (n-- > 0)
     155  /* At this point, we know that either n < sizeof (longword), or one of the
     156     sizeof (longword) bytes starting at char_ptr is == c.  On little-endian
     157     machines, we could determine the first such byte without any further
     158     memory accesses, just by looking at the tmp result from the last loop
     159     iteration.  But this does not work on big-endian machines.  Choose code
     160     that works in both cases.  */
     161
     162  for (; n > 0; --n, ++char_ptr)
    192163    {
    193164      if (*char_ptr == c)
    194         return (__ptr_t) char_ptr;
    195       else
    196         ++char_ptr;
     165        return (void *) char_ptr;
    197166    }
    198167
    199   return 0;
     168  return NULL;
    200169}
     170#ifdef weak_alias
     171weak_alias (__memchr, BP_SYM (memchr))
     172#endif
Note: See TracChangeset for help on using the changeset viewer.