sysdeps/i386/rawmemchr.S

   1 /* rawmemchr (str, ch) -- Return pointer to first occurrence of CH in STR.
   2    For Intel 80x86, x>=3.
   3    Copyright (C) 1994-2000,2002,2005 Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5    Contributed by Ulrich Drepper <drepper@gnu.ai.mit.edu>
   6    Optimised a little by Alan Modra <Alan@SPRI.Levels.UniSA.Edu.Au>
   7    This version is developed using the same algorithm as the fast C
   8    version which carries the following introduction:
   9    Based on strlen implementation by Torbjorn Granlund (tege@sics.se),
  10    with help from Dan Sahlin (dan@sics.se) and
  11    commentary by Jim Blandy (jimb@ai.mit.edu);
  12    adaptation to memchr suggested by Dick Karpinski (dick@cca.ucsf.edu),
  13    and implemented by Roland McGrath (roland@ai.mit.edu).
  14
  15    The GNU C Library is free software; you can redistribute it and/or
  16    modify it under the terms of the GNU Lesser General Public
  17    License as published by the Free Software Foundation; either
  18    version 2.1 of the License, or (at your option) any later version.
  19
  20    The GNU C Library is distributed in the hope that it will be useful,
  21    but WITHOUT ANY WARRANTY; without even the implied warranty of
  22    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  23    Lesser General Public License for more details.
  24
  25    You should have received a copy of the GNU Lesser General Public
  26    License along with the GNU C Library; if not, see
  27    <http://www.gnu.org/licenses/>.  */
  28
  29 #include <sysdep.h>
  30 #include "asm-syntax.h"
  31 #include "bp-sym.h"
  32 #include "bp-asm.h"
  33
  34 #define PARMS   LINKAGE+4       /* space for 1 saved reg */
  35 #define RTN     PARMS
  36 #define STR     RTN+RTN_SIZE
  37 #define CHR     STR+PTR_SIZE
  38
  39         .text
  40 ENTRY (BP_SYM (__rawmemchr))
  41         ENTER
  42
  43         /* Save callee-safe register used in this function.  */
  44         pushl %edi
  45         cfi_adjust_cfa_offset (4)
  46         cfi_rel_offset (edi, 0)
  47
  48         /* Load parameters into registers.  */
  49         movl STR(%esp), %eax
  50         movl CHR(%esp), %edx
  51         CHECK_BOUNDS_LOW (%eax, STR(%esp))
  52
  53         /* At the moment %edx contains C.  What we need for the
  54            algorithm is C in all bytes of the dword.  Avoid
  55            operations on 16 bit words because these require an
  56            prefix byte (and one more cycle).  */
  57         movb %dl, %dh           /* Now it is 0|0|c|c */
  58         movl %edx, %ecx
  59         shll $16, %edx          /* Now c|c|0|0 */
  60         movw %cx, %dx           /* And finally c|c|c|c */
  61
  62         /* Better performance can be achieved if the word (32
  63            bit) memory access is aligned on a four-byte-boundary.
  64            So process first bytes one by one until boundary is
  65            reached. Don't use a loop for better performance.  */
  66
  67         testb $3, %al           /* correctly aligned ? */
  68         je L(1)                 /* yes => begin loop */
  69         cmpb %dl, (%eax)        /* compare byte */
  70         je L(9)                 /* target found => return */
  71         incl %eax               /* increment source pointer */
  72
  73         testb $3, %al           /* correctly aligned ? */
  74         je L(1)                 /* yes => begin loop */
  75         cmpb %dl, (%eax)        /* compare byte */
  76         je L(9)                 /* target found => return */
  77         incl %eax               /* increment source pointer */
  78
  79         testb $3, %al           /* correctly aligned ? */
  80         je L(1)                 /* yes => begin loop */
  81         cmpb %dl, (%eax)        /* compare byte */
  82         je L(9)                 /* target found => return */
  83         incl %eax               /* increment source pointer */
  84
  85       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
  86          change any of the hole bits of LONGWORD.
  87
  88          1) Is this safe?  Will it catch all the zero bytes?
  89          Suppose there is a byte with all zeros.  Any carry bits
  90          propagating from its left will fall into the hole at its
  91          least significant bit and stop.  Since there will be no
  92          carry from its most significant bit, the LSB of the
  93          byte to the left will be unchanged, and the zero will be
  94          detected.
  95
  96          2) Is this worthwhile?  Will it ignore everything except
  97          zero bytes?  Suppose every byte of LONGWORD has a bit set
  98          somewhere.  There will be a carry into bit 8.  If bit 8
  99          is set, this will carry into bit 16.  If bit 8 is clear,
 100          one of bits 9-15 must be set, so there will be a carry
 101          into bit 16.  Similarly, there will be a carry into bit
 102          24.  If one of bits 24-31 is set, there will be a carry
 103          into bit 32 (=carry flag), so all of the hole bits will
 104          be changed.
 105
 106          3) But wait!  Aren't we looking for C, not zero?
 107          Good point.  So what we do is XOR LONGWORD with a longword,
 108          each of whose bytes is C.  This turns each byte that is C
 109          into a zero.  */
 110
 111
 112         /* Each round the main loop processes 16 bytes.  */
 113         ALIGN (4)
 114
 115 L(1):   movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 116         movl $0xfefefeff, %edi  /* magic value */
 117         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 118                                    are now 0 */
 119         addl %ecx, %edi         /* add the magic value to the word.  We get
 120                                    carry bits reported for each byte which
 121                                    is *not* 0 */
 122
 123         /* According to the algorithm we had to reverse the effect of the
 124            XOR first and then test the overflow bits.  But because the
 125            following XOR would destroy the carry flag and it would (in a
 126            representation with more than 32 bits) not alter then last
 127            overflow, we can now test this condition.  If no carry is signaled
 128            no overflow must have occurred in the last byte => it was 0. */
 129         jnc L(8)
 130
 131         /* We are only interested in carry bits that change due to the
 132            previous add, so remove original bits */
 133         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 134
 135         /* Now test for the other three overflow bits.  */
 136         orl $0xfefefeff, %edi   /* set all non-carry bits */
 137         incl %edi               /* add 1: if one carry bit was *not* set
 138                                    the addition will not result in 0.  */
 139
 140         /* If at least one byte of the word is C we don't get 0 in %edi.  */
 141         jnz L(8)                /* found it => return pointer */
 142
 143         /* This process is unfolded four times for better performance.
 144            we don't increment the source pointer each time.  Instead we
 145            use offsets and increment by 16 in each run of the loop.  But
 146            before probing for the matching byte we need some extra code
 147            (following LL(13) below).  Even the len can be compared with
 148            constants instead of decrementing each time.  */
 149
 150         movl 4(%eax), %ecx      /* get word (= 4 bytes) in question */
 151         movl $0xfefefeff, %edi  /* magic value */
 152         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 153                                    are now 0 */
 154         addl %ecx, %edi         /* add the magic value to the word.  We get
 155                                    carry bits reported for each byte which
 156                                    is *not* 0 */
 157         jnc L(7)                /* highest byte is C => return pointer */
 158         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 159         orl $0xfefefeff, %edi   /* set all non-carry bits */
 160         incl %edi               /* add 1: if one carry bit was *not* set
 161                                    the addition will not result in 0.  */
 162         jnz L(7)                /* found it => return pointer */
 163
 164         movl 8(%eax), %ecx      /* get word (= 4 bytes) in question */
 165         movl $0xfefefeff, %edi  /* magic value */
 166         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 167                                    are now 0 */
 168         addl %ecx, %edi         /* add the magic value to the word.  We get
 169                                    carry bits reported for each byte which
 170                                    is *not* 0 */
 171         jnc L(6)                /* highest byte is C => return pointer */
 172         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 173         orl $0xfefefeff, %edi   /* set all non-carry bits */
 174         incl %edi               /* add 1: if one carry bit was *not* set
 175                                    the addition will not result in 0.  */
 176         jnz L(6)                /* found it => return pointer */
 177
 178         movl 12(%eax), %ecx     /* get word (= 4 bytes) in question */
 179         movl $0xfefefeff, %edi  /* magic value */
 180         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 181                                    are now 0 */
 182         addl %ecx, %edi         /* add the magic value to the word.  We get
 183                                    carry bits reported for each byte which
 184                                    is *not* 0 */
 185         jnc L(5)                /* highest byte is C => return pointer */
 186         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 187         orl $0xfefefeff, %edi   /* set all non-carry bits */
 188         incl %edi               /* add 1: if one carry bit was *not* set
 189                                    the addition will not result in 0.  */
 190         jnz L(5)                /* found it => return pointer */
 191
 192         /* Adjust both counters for a full round, i.e. 16 bytes.  */
 193         addl $16, %eax
 194         jmp L(1)
 195         /* add missing source pointer increments */
 196 L(5):   addl $4, %eax
 197 L(6):   addl $4, %eax
 198 L(7):   addl $4, %eax
 199
 200         /* Test for the matching byte in the word.  %ecx contains a NUL
 201            char in the byte which originally was the byte we are looking
 202            at.  */
 203 L(8):   testb %cl, %cl          /* test first byte in dword */
 204         jz L(9)                 /* if zero => return pointer */
 205         incl %eax               /* increment source pointer */
 206
 207         testb %ch, %ch          /* test second byte in dword */
 208         jz L(9)                 /* if zero => return pointer */
 209         incl %eax               /* increment source pointer */
 210
 211         testl $0xff0000, %ecx   /* test third byte in dword */
 212         jz L(9)                 /* if zero => return pointer */
 213         incl %eax               /* increment source pointer */
 214
 215         /* No further test needed we we know it is one of the four bytes.  */
 216
 217 L(9):
 218         CHECK_BOUNDS_HIGH (%eax, STR(%esp), jb)
 219         RETURN_BOUNDED_POINTER (STR(%esp))
 220         popl %edi               /* pop saved register */
 221         cfi_adjust_cfa_offset (-4)
 222         cfi_restore (edi)
 223
 224         LEAVE
 225         RET_PTR
 226 END (BP_SYM (__rawmemchr))
 227
 228 libc_hidden_def (BP_SYM (__rawmemchr))
 229 weak_alias (BP_SYM (__rawmemchr), BP_SYM (rawmemchr))