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