sysdeps/i386/strchrnul.S

   1 /* strchrnul (str, ch) -- Return pointer to first occurrence of CH in STR
   2    or the final NUL byte.
   3    For Intel 80x86, x>=3.
   4    Copyright (C) 1994, 1995, 1996, 1997, 1999 Free Software Foundation, Inc.
   5    This file is part of the GNU C Library.
   6    Contributed by Ulrich Drepper <drepper@gnu.org>
   7    Some optimisations by Alan Modra <Alan@SPRI.Levels.UniSA.Edu.Au>
   8
   9    The GNU C Library is free software; you can redistribute it and/or
  10    modify it under the terms of the GNU Library General Public License as
  11    published by the Free Software Foundation; either version 2 of the
  12    License, or (at your option) any later version.
  13
  14    The GNU C Library is distributed in the hope that it will be useful,
  15    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  17    Library General Public License for more details.
  18
  19    You should have received a copy of the GNU Library General Public
  20    License along with the GNU C Library; see the file COPYING.LIB.  If not,
  21    write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  22    Boston, MA 02111-1307, USA.  */
  23
  24 #include <sysdep.h>
  25 #include "asm-syntax.h"
  26
  27 /*
  28    INPUT PARAMETERS:
  29    str          (sp + 4)
  30    ch           (sp + 8)
  31 */
  32
  33         .text
  34 ENTRY (__strchrnul)
  35         pushl %edi              /* Save callee-safe registers used here.  */
  36
  37         movl 8(%esp), %eax      /* get string pointer */
  38         movl 12(%esp), %edx     /* get character we are looking for */
  39
  40         /* At the moment %edx contains C.  What we need for the
  41            algorithm is C in all bytes of the dword.  Avoid
  42            operations on 16 bit words because these require an
  43            prefix byte (and one more cycle).  */
  44         movb %dl, %dh           /* now it is 0|0|c|c */
  45         movl %edx, %ecx
  46         shll $16, %edx          /* now it is c|c|0|0 */
  47         movw %cx, %dx           /* and finally c|c|c|c */
  48
  49         /* Before we start with the main loop we process single bytes
  50            until the source pointer is aligned.  This has two reasons:
  51            1. aligned 32-bit memory access is faster
  52            and (more important)
  53            2. we process in the main loop 32 bit in one step although
  54               we don't know the end of the string.  But accessing at
  55               4-byte alignment guarantees that we never access illegal
  56               memory if this would not also be done by the trivial
  57               implementation (this is because all processor inherent
  58               boundaries are multiples of 4.  */
  59
  60         testb $3, %eax          /* correctly aligned ? */
  61         jz L(11)                /* yes => begin loop */
  62         movb (%eax), %cl        /* load byte in question (we need it twice) */
  63         cmpb %cl, %dl           /* compare byte */
  64         je L(6)                 /* target found => return */
  65         testb %cl, %cl          /* is NUL? */
  66         jz L(6)                 /* yes => return NULL */
  67         incl %eax               /* increment pointer */
  68
  69         testb $3, %eax          /* correctly aligned ? */
  70         jz L(11)                /* yes => begin loop */
  71         movb (%eax), %cl        /* load byte in question (we need it twice) */
  72         cmpb %cl, %dl           /* compare byte */
  73         je L(6)                 /* target found => return */
  74         testb %cl, %cl          /* is NUL? */
  75         jz L(6)                 /* yes => return NULL */
  76         incl %eax               /* increment pointer */
  77
  78         testb $3, %eax          /* correctly aligned ? */
  79         jz L(11)                /* yes => begin loop */
  80         movb (%eax), %cl        /* load byte in question (we need it twice) */
  81         cmpb %cl, %dl           /* compare byte */
  82         je L(6)                 /* target found => return */
  83         testb %cl, %cl          /* is NUL? */
  84         jz L(6)                 /* yes => return NULL */
  85         incl %eax               /* increment pointer */
  86
  87         /* No we have reached alignment.  */
  88         jmp L(11)               /* begin loop */
  89
  90       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
  91          change any of the hole bits of LONGWORD.
  92
  93          1) Is this safe?  Will it catch all the zero bytes?
  94          Suppose there is a byte with all zeros.  Any carry bits
  95          propagating from its left will fall into the hole at its
  96          least significant bit and stop.  Since there will be no
  97          carry from its most significant bit, the LSB of the
  98          byte to the left will be unchanged, and the zero will be
  99          detected.
 100
 101          2) Is this worthwhile?  Will it ignore everything except
 102          zero bytes?  Suppose every byte of LONGWORD has a bit set
 103          somewhere.  There will be a carry into bit 8.  If bit 8
 104          is set, this will carry into bit 16.  If bit 8 is clear,
 105          one of bits 9-15 must be set, so there will be a carry
 106          into bit 16.  Similarly, there will be a carry into bit
 107          24.  If one of bits 24-31 is set, there will be a carry
 108          into bit 32 (=carry flag), so all of the hole bits will
 109          be changed.
 110
 111          3) But wait!  Aren't we looking for C, not zero?
 112          Good point.  So what we do is XOR LONGWORD with a longword,
 113          each of whose bytes is C.  This turns each byte that is C
 114          into a zero.  */
 115
 116         /* Each round the main loop processes 16 bytes.  */
 117
 118         ALIGN(4)
 119
 120 L(1):   addl $16, %eax          /* adjust pointer for whole round */
 121
 122 L(11):  movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 123         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 124                                    are now 0 */
 125         movl $0xfefefeff, %edi  /* magic value */
 126         addl %ecx, %edi         /* add the magic value to the word.  We get
 127                                    carry bits reported for each byte which
 128                                    is *not* C */
 129
 130         /* According to the algorithm we had to reverse the effect of the
 131            XOR first and then test the overflow bits.  But because the
 132            following XOR would destroy the carry flag and it would (in a
 133            representation with more than 32 bits) not alter then last
 134            overflow, we can now test this condition.  If no carry is signaled
 135            no overflow must have occurred in the last byte => it was 0. */
 136         jnc L(7)
 137
 138         /* We are only interested in carry bits that change due to the
 139            previous add, so remove original bits */
 140         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 141
 142         /* Now test for the other three overflow bits.  */
 143         orl $0xfefefeff, %edi   /* set all non-carry bits */
 144         incl %edi               /* add 1: if one carry bit was *not* set
 145                                    the addition will not result in 0.  */
 146
 147         /* If at least one byte of the word is C we don't get 0 in %edi.  */
 148         jnz L(7)                /* found it => return pointer */
 149
 150         /* Now we made sure the dword does not contain the character we are
 151            looking for.  But because we deal with strings we have to check
 152            for the end of string before testing the next dword.  */
 153
 154         xorl %edx, %ecx         /* restore original dword without reload */
 155         movl $0xfefefeff, %edi  /* magic value */
 156         addl %ecx, %edi         /* add the magic value to the word.  We get
 157                                    carry bits reported for each byte which
 158                                    is *not* 0 */
 159         jnc L(7)                /* highest byte is NUL => return NULL */
 160         xorl %ecx, %edi         /* (word+magic)^word */
 161         orl $0xfefefeff, %edi   /* set all non-carry bits */
 162         incl %edi               /* add 1: if one carry bit was *not* set
 163                                    the addition will not result in 0.  */
 164         jnz L(7)                /* found NUL => return NULL */
 165
 166         movl 4(%eax), %ecx      /* get word (= 4 bytes) in question */
 167         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 168                                    are now 0 */
 169         movl $0xfefefeff, %edi  /* magic value */
 170         addl %ecx, %edi         /* add the magic value to the word.  We get
 171                                    carry bits reported for each byte which
 172                                    is *not* C */
 173         jnc L(71)               /* highest byte is C => return pointer */
 174         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 175         orl $0xfefefeff, %edi   /* set all non-carry bits */
 176         incl %edi               /* add 1: if one carry bit was *not* set
 177                                    the addition will not result in 0.  */
 178         jnz L(71)               /* found it => return pointer */
 179         xorl %edx, %ecx         /* restore original dword without reload */
 180         movl $0xfefefeff, %edi  /* magic value */
 181         addl %ecx, %edi         /* add the magic value to the word.  We get
 182                                    carry bits reported for each byte which
 183                                    is *not* 0 */
 184         jnc L(71)               /* highest byte is NUL => return NULL */
 185         xorl %ecx, %edi         /* (word+magic)^word */
 186         orl $0xfefefeff, %edi   /* set all non-carry bits */
 187         incl %edi               /* add 1: if one carry bit was *not* set
 188                                    the addition will not result in 0.  */
 189         jnz L(71)               /* found NUL => return NULL */
 190
 191         movl 8(%eax), %ecx      /* get word (= 4 bytes) in question */
 192         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 193                                    are now 0 */
 194         movl $0xfefefeff, %edi  /* magic value */
 195         addl %ecx, %edi         /* add the magic value to the word.  We get
 196                                    carry bits reported for each byte which
 197                                    is *not* C */
 198         jnc L(72)               /* highest byte is C => return pointer */
 199         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 200         orl $0xfefefeff, %edi   /* set all non-carry bits */
 201         incl %edi               /* add 1: if one carry bit was *not* set
 202                                    the addition will not result in 0.  */
 203         jnz L(72)               /* found it => return pointer */
 204         xorl %edx, %ecx         /* restore original dword without reload */
 205         movl $0xfefefeff, %edi  /* magic value */
 206         addl %ecx, %edi         /* add the magic value to the word.  We get
 207                                    carry bits reported for each byte which
 208                                    is *not* 0 */
 209         jnc L(72)               /* highest byte is NUL => return NULL */
 210         xorl %ecx, %edi         /* (word+magic)^word */
 211         orl $0xfefefeff, %edi   /* set all non-carry bits */
 212         incl %edi               /* add 1: if one carry bit was *not* set
 213                                    the addition will not result in 0.  */
 214         jnz L(72)               /* found NUL => return NULL */
 215
 216         movl 12(%eax), %ecx     /* get word (= 4 bytes) in question */
 217         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 218                                    are now 0 */
 219         movl $0xfefefeff, %edi  /* magic value */
 220         addl %ecx, %edi         /* add the magic value to the word.  We get
 221                                    carry bits reported for each byte which
 222                                    is *not* C */
 223         jnc L(73)               /* highest byte is C => 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         jnz L(73)               /* found it => return pointer */
 229         xorl %edx, %ecx         /* restore original dword without reload */
 230         movl $0xfefefeff, %edi  /* magic value */
 231         addl %ecx, %edi         /* add the magic value to the word.  We get
 232                                    carry bits reported for each byte which
 233                                    is *not* 0 */
 234         jnc L(73)               /* highest byte is NUL => return NULL */
 235         xorl %ecx, %edi         /* (word+magic)^word */
 236         orl $0xfefefeff, %edi   /* set all non-carry bits */
 237         incl %edi               /* add 1: if one carry bit was *not* set
 238                                    the addition will not result in 0.  */
 239         jz L(1)                 /* no NUL found => restart loop */
 240
 241 L(73):  addl $4, %eax           /* adjust pointer */
 242 L(72):  addl $4, %eax
 243 L(71):  addl $4, %eax
 244
 245         /* We now scan for the byte in which the character was matched.
 246            But we have to take care of the case that a NUL char is
 247            found before this in the dword.  */
 248
 249 L(7):   testb %cl, %cl          /* is first byte C? */
 250         jz L(6)                 /* yes => return pointer */
 251         cmpb %dl, %cl           /* is first byte NUL? */
 252         je L(6)                 /* yes => return NULL */
 253         incl %eax               /* it's not in the first byte */
 254
 255         testb %ch, %ch          /* is second byte C? */
 256         jz L(6)                 /* yes => return pointer */
 257         cmpb %dl, %ch           /* is second byte NUL? */
 258         je L(6)                 /* yes => return NULL? */
 259         incl %eax               /* it's not in the second byte */
 260
 261         shrl $16, %ecx          /* make upper byte accessible */
 262         testb %cl, %cl          /* is third byte C? */
 263         jz L(6)                 /* yes => return pointer */
 264         cmpb %dl, %cl           /* is third byte NUL? */
 265         je L(6)                 /* yes => return NULL */
 266
 267         /* It must be in the fourth byte and it cannot be NUL.  */
 268         incl %eax
 269
 270 L(6):   popl %edi               /* restore saved register content */
 271
 272         ret
 273 END (__strchrnul)
 274
 275 weak_alias (__strchrnul, strchrnul)