sysdeps/i386/memchr.S

   1 /* memchr (str, chr, len) -- Return pointer to first occurrence of CHR in STR
   2          less than LEN.  For Intel 80x86, x>=3.
   3    Copyright (C) 1994-1998, 2000, 2003, 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, write to the Free
  27    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  28    02111-1307 USA.  */
  29
  30 #include <sysdep.h>
  31 #include "asm-syntax.h"
  32 #include "bp-sym.h"
  33 #include "bp-asm.h"
  34
  35 #define PARMS   LINKAGE+8               /* space for 2 saved regs */
  36 #define RTN     PARMS
  37 #define STR     RTN+RTN_SIZE
  38 #define CHR     STR+PTR_SIZE
  39 #define LEN     CHR+4
  40
  41         .text
  42 ENTRY (BP_SYM (__memchr))
  43         ENTER
  44
  45         /* Save callee-safe registers used in this function.  */
  46         pushl %esi
  47         cfi_adjust_cfa_offset (4)
  48         pushl %edi
  49         cfi_adjust_cfa_offset (4)
  50         cfi_rel_offset (edi, 0)
  51
  52         /* Load parameters into registers.  */
  53         movl STR(%esp), %eax    /* str: pointer to memory block.  */
  54         movl CHR(%esp), %edx    /* c: byte we are looking for.  */
  55         movl LEN(%esp), %esi    /* len: length of memory block.  */
  56         cfi_rel_offset (esi, 4)
  57         CHECK_BOUNDS_LOW (%eax, STR(%esp))
  58
  59         /* If my must not test more than three characters test
  60            them one by one.  This is especially true for 0.  */
  61         cmpl $4, %esi
  62         jb L(3)
  63
  64         /* At the moment %edx contains CHR.  What we need for the
  65            algorithm is CHR in all bytes of the dword.  Avoid
  66            operations on 16 bit words because these require an
  67            prefix byte (and one more cycle).  */
  68         movb %dl, %dh           /* Now it is 0|0|c|c */
  69         movl %edx, %ecx
  70         shll $16, %edx          /* Now c|c|0|0 */
  71         movw %cx, %dx           /* And finally c|c|c|c */
  72
  73         /* Better performance can be achieved if the word (32
  74            bit) memory access is aligned on a four-byte-boundary.
  75            So process first bytes one by one until boundary is
  76            reached. Don't use a loop for better performance.  */
  77
  78         testb $3, %al           /* correctly aligned ? */
  79         je L(2)                 /* yes => begin loop */
  80         cmpb %dl, (%eax)        /* compare byte */
  81         je L(9)                 /* target found => return */
  82         incl %eax               /* increment source pointer */
  83         decl %esi               /* decrement length counter */
  84         je L(4)                 /* len==0 => return NULL */
  85
  86         testb $3, %al           /* correctly aligned ? */
  87         je L(2)                 /* yes => begin loop */
  88         cmpb %dl, (%eax)        /* compare byte */
  89         je L(9)                 /* target found => return */
  90         incl %eax               /* increment source pointer */
  91         decl %esi               /* decrement length counter */
  92         je L(4)                 /* len==0 => return NULL */
  93
  94         testb $3, %al           /* correctly aligned ? */
  95         je L(2)                 /* yes => begin loop */
  96         cmpb %dl, (%eax)        /* compare byte */
  97         je L(9)                 /* target found => return */
  98         incl %eax               /* increment source pointer */
  99         decl %esi               /* decrement length counter */
 100         /* no test for len==0 here, because this is done in the
 101            loop head */
 102         jmp L(2)
 103
 104       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
 105          change any of the hole bits of LONGWORD.
 106
 107          1) Is this safe?  Will it catch all the zero bytes?
 108          Suppose there is a byte with all zeros.  Any carry bits
 109          propagating from its left will fall into the hole at its
 110          least significant bit and stop.  Since there will be no
 111          carry from its most significant bit, the LSB of the
 112          byte to the left will be unchanged, and the zero will be
 113          detected.
 114
 115          2) Is this worthwhile?  Will it ignore everything except
 116          zero bytes?  Suppose every byte of LONGWORD has a bit set
 117          somewhere.  There will be a carry into bit 8.  If bit 8
 118          is set, this will carry into bit 16.  If bit 8 is clear,
 119          one of bits 9-15 must be set, so there will be a carry
 120          into bit 16.  Similarly, there will be a carry into bit
 121          24.  If one of bits 24-31 is set, there will be a carry
 122          into bit 32 (=carry flag), so all of the hole bits will
 123          be changed.
 124
 125          3) But wait!  Aren't we looking for CHR, not zero?
 126          Good point.  So what we do is XOR LONGWORD with a longword,
 127          each of whose bytes is CHR.  This turns each byte that is CHR
 128          into a zero.  */
 129
 130
 131         /* Each round the main loop processes 16 bytes.  */
 132
 133         ALIGN (4)
 134
 135 L(1):   movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 136         movl $0xfefefeff, %edi  /* magic value */
 137         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 138                                    are now 0 */
 139         addl %ecx, %edi         /* add the magic value to the word.  We get
 140                                    carry bits reported for each byte which
 141                                    is *not* 0 */
 142
 143         /* According to the algorithm we had to reverse the effect of the
 144            XOR first and then test the overflow bits.  But because the
 145            following XOR would destroy the carry flag and it would (in a
 146            representation with more than 32 bits) not alter then last
 147            overflow, we can now test this condition.  If no carry is signaled
 148            no overflow must have occurred in the last byte => it was 0. */
 149         jnc L(8)
 150
 151         /* We are only interested in carry bits that change due to the
 152            previous add, so remove original bits */
 153         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 154
 155         /* Now test for the other three overflow bits.  */
 156         orl $0xfefefeff, %edi   /* set all non-carry bits */
 157         incl %edi               /* add 1: if one carry bit was *not* set
 158                                    the addition will not result in 0.  */
 159
 160         /* If at least one byte of the word is CHR we don't get 0 in %edi.  */
 161         jnz L(8)                /* found it => return pointer */
 162
 163         /* This process is unfolded four times for better performance.
 164            we don't increment the source pointer each time.  Instead we
 165            use offsets and increment by 16 in each run of the loop.  But
 166            before probing for the matching byte we need some extra code
 167            (following LL(13) below).  Even the len can be compared with
 168            constants instead of decrementing each time.  */
 169
 170         movl 4(%eax), %ecx      /* get word (= 4 bytes) in question */
 171         movl $0xfefefeff, %edi  /* magic value */
 172         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 173                                    are now 0 */
 174         addl %ecx, %edi         /* add the magic value to the word.  We get
 175                                    carry bits reported for each byte which
 176                                    is *not* 0 */
 177         jnc L(7)                /* highest byte is CHR => return pointer */
 178         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 179         orl $0xfefefeff, %edi   /* set all non-carry bits */
 180         incl %edi               /* add 1: if one carry bit was *not* set
 181                                    the addition will not result in 0.  */
 182         jnz L(7)                /* found it => return pointer */
 183
 184         movl 8(%eax), %ecx      /* get word (= 4 bytes) in question */
 185         movl $0xfefefeff, %edi  /* magic value */
 186         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 187                                    are now 0 */
 188         addl %ecx, %edi         /* add the magic value to the word.  We get
 189                                    carry bits reported for each byte which
 190                                    is *not* 0 */
 191         jnc L(6)                /* highest byte is CHR => return pointer */
 192         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 193         orl $0xfefefeff, %edi   /* set all non-carry bits */
 194         incl %edi               /* add 1: if one carry bit was *not* set
 195                                    the addition will not result in 0.  */
 196         jnz L(6)                /* found it => return pointer */
 197
 198         movl 12(%eax), %ecx     /* get word (= 4 bytes) in question */
 199         movl $0xfefefeff, %edi  /* magic value */
 200         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 201                                    are now 0 */
 202         addl %ecx, %edi         /* add the magic value to the word.  We get
 203                                    carry bits reported for each byte which
 204                                    is *not* 0 */
 205         jnc L(5)                /* highest byte is CHR => return pointer */
 206         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 207         orl $0xfefefeff, %edi   /* set all non-carry bits */
 208         incl %edi               /* add 1: if one carry bit was *not* set
 209                                    the addition will not result in 0.  */
 210         jnz L(5)                /* found it => return pointer */
 211
 212         /* Adjust both counters for a full round, i.e. 16 bytes.  */
 213         addl $16, %eax
 214 L(2):   subl $16, %esi
 215         jae L(1)                /* Still more than 16 bytes remaining */
 216
 217         /* Process remaining bytes separately.  */
 218         cmpl $4-16, %esi        /* rest < 4 bytes? */
 219         jb L(3)                 /* yes, than test byte by byte */
 220
 221         movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 222         movl $0xfefefeff, %edi  /* magic value */
 223         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 224                                    are now 0 */
 225         addl %ecx, %edi         /* add the magic value to the word.  We get
 226                                    carry bits reported for each byte which
 227                                    is *not* 0 */
 228         jnc L(8)                /* highest byte is CHR => return pointer */
 229         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 230         orl $0xfefefeff, %edi   /* set all non-carry bits */
 231         incl %edi               /* add 1: if one carry bit was *not* set
 232                                    the addition will not result in 0.  */
 233         jne L(8)                /* found it => return pointer */
 234         addl $4, %eax           /* adjust source pointer */
 235
 236         cmpl $8-16, %esi        /* rest < 8 bytes? */
 237         jb L(3)                 /* yes, than test byte by byte */
 238
 239         movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 240         movl $0xfefefeff, %edi  /* magic value */
 241         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 242                                    are now 0 */
 243         addl %ecx, %edi         /* add the magic value to the word.  We get
 244                                    carry bits reported for each byte which
 245                                    is *not* 0 */
 246         jnc L(8)                /* highest byte is CHR => return pointer */
 247         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 248         orl $0xfefefeff, %edi   /* set all non-carry bits */
 249         incl %edi               /* add 1: if one carry bit was *not* set
 250                                    the addition will not result in 0.  */
 251         jne L(8)                /* found it => return pointer */
 252         addl $4, %eax           /* adjust source pointer */
 253
 254         cmpl $12-16, %esi       /* rest < 12 bytes? */
 255         jb L(3)                 /* yes, than test byte by byte */
 256
 257         movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 258         movl $0xfefefeff, %edi  /* magic value */
 259         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 260                                    are now 0 */
 261         addl %ecx, %edi         /* add the magic value to the word.  We get
 262                                    carry bits reported for each byte which
 263                                    is *not* 0 */
 264         jnc L(8)                /* highest byte is CHR => return pointer */
 265         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 266         orl $0xfefefeff, %edi   /* set all non-carry bits */
 267         incl %edi               /* add 1: if one carry bit was *not* set
 268                                    the addition will not result in 0.  */
 269         jne L(8)                /* found it => return pointer */
 270         addl $4, %eax           /* adjust source pointer */
 271
 272         /* Check the remaining bytes one by one.  */
 273 L(3):   andl $3, %esi           /* mask out uninteresting bytes */
 274         jz L(4)                 /* no remaining bytes => return NULL */
 275
 276         cmpb %dl, (%eax)        /* compare byte with CHR */
 277         je L(9)                 /* equal, than return pointer */
 278         incl %eax               /* increment source pointer */
 279         decl %esi               /* decrement length */
 280         jz L(4)                 /* no remaining bytes => return NULL */
 281
 282         cmpb %dl, (%eax)        /* compare byte with CHR */
 283         je L(9)                 /* equal, than return pointer */
 284         incl %eax               /* increment source pointer */
 285         decl %esi               /* decrement length */
 286         jz L(4)                 /* no remaining bytes => return NULL */
 287
 288         cmpb %dl, (%eax)        /* compare byte with CHR */
 289         je L(9)                 /* equal, than return pointer */
 290
 291 L(4):   /* no byte found => return NULL */
 292         xorl %eax, %eax
 293         jmp L(9)
 294
 295         /* add missing source pointer increments */
 296 L(5):   addl $4, %eax
 297 L(6):   addl $4, %eax
 298 L(7):   addl $4, %eax
 299
 300         /* Test for the matching byte in the word.  %ecx contains a NUL
 301            char in the byte which originally was the byte we are looking
 302            at.  */
 303 L(8):   testb %cl, %cl          /* test first byte in dword */
 304         jz L(9)                 /* if zero => return pointer */
 305         incl %eax               /* increment source pointer */
 306
 307         testb %ch, %ch          /* test second byte in dword */
 308         jz L(9)                 /* if zero => return pointer */
 309         incl %eax               /* increment source pointer */
 310
 311         testl $0xff0000, %ecx   /* test third byte in dword */
 312         jz L(9)                 /* if zero => return pointer */
 313         incl %eax               /* increment source pointer */
 314
 315         /* No further test needed we we know it is one of the four bytes.  */
 316 L(9):
 317 #if __BOUNDED_POINTERS__
 318         CHECK_BOUNDS_HIGH (%eax, STR(%esp), jb)
 319         /* If RTN pointer is phony, don't copy return value into it.  */
 320         movl RTN(%esp), %ecx
 321         testl %ecx, %ecx
 322         jz L(pop)
 323         RETURN_BOUNDED_POINTER (STR(%esp))
 324 #endif
 325 L(pop): popl %edi               /* pop saved registers */
 326         cfi_adjust_cfa_offset (-4)
 327         cfi_restore (edi)
 328         popl %esi
 329         cfi_adjust_cfa_offset (-4)
 330         cfi_restore (esi)
 331
 332         LEAVE
 333         RET_PTR
 334 END (BP_SYM (__memchr))
 335
 336 weak_alias (BP_SYM (__memchr), BP_SYM (memchr))
 337 #if !__BOUNDED_POINTERS__
 338 weak_alias (__memchr, __ubp_memchr)
 339 #endif
 340 libc_hidden_builtin_def (memchr)