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