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-2015 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+4     /* space for 1 saved reg */
  33 #define RTN     PARMS
  34 #define STR     RTN
  35 #define CHR     STR+4
  36
  37         .text
  38 ENTRY (__rawmemchr)
  39
  40         /* Save callee-safe register used in this function.  */
  41         pushl %edi
  42         cfi_adjust_cfa_offset (4)
  43         cfi_rel_offset (edi, 0)
  44
  45         /* Load parameters into registers.  */
  46         movl STR(%esp), %eax
  47         movl CHR(%esp), %edx
  48
  49         /* At the moment %edx contains C.  What we need for the
  50            algorithm is C in all bytes of the dword.  Avoid
  51            operations on 16 bit words because these require an
  52            prefix byte (and one more cycle).  */
  53         movb %dl, %dh           /* Now it is 0|0|c|c */
  54         movl %edx, %ecx
  55         shll $16, %edx          /* Now c|c|0|0 */
  56         movw %cx, %dx           /* And finally c|c|c|c */
  57
  58         /* Better performance can be achieved if the word (32
  59            bit) memory access is aligned on a four-byte-boundary.
  60            So process first bytes one by one until boundary is
  61            reached. Don't use a loop for better performance.  */
  62
  63         testb $3, %al           /* correctly aligned ? */
  64         je L(1)                 /* yes => begin loop */
  65         cmpb %dl, (%eax)        /* compare byte */
  66         je L(9)                 /* target found => return */
  67         incl %eax               /* increment source pointer */
  68
  69         testb $3, %al           /* correctly aligned ? */
  70         je L(1)                 /* yes => begin loop */
  71         cmpb %dl, (%eax)        /* compare byte */
  72         je L(9)                 /* target found => return */
  73         incl %eax               /* increment source pointer */
  74
  75         testb $3, %al           /* correctly aligned ? */
  76         je L(1)                 /* yes => begin loop */
  77         cmpb %dl, (%eax)        /* compare byte */
  78         je L(9)                 /* target found => return */
  79         incl %eax               /* increment source pointer */
  80
  81       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
  82          change any of the hole bits of LONGWORD.
  83
  84          1) Is this safe?  Will it catch all the zero bytes?
  85          Suppose there is a byte with all zeros.  Any carry bits
  86          propagating from its left will fall into the hole at its
  87          least significant bit and stop.  Since there will be no
  88          carry from its most significant bit, the LSB of the
  89          byte to the left will be unchanged, and the zero will be
  90          detected.
  91
  92          2) Is this worthwhile?  Will it ignore everything except
  93          zero bytes?  Suppose every byte of LONGWORD has a bit set
  94          somewhere.  There will be a carry into bit 8.  If bit 8
  95          is set, this will carry into bit 16.  If bit 8 is clear,
  96          one of bits 9-15 must be set, so there will be a carry
  97          into bit 16.  Similarly, there will be a carry into bit
  98          24.  If one of bits 24-31 is set, there will be a carry
  99          into bit 32 (=carry flag), so all of the hole bits will
 100          be changed.
 101
 102          3) But wait!  Aren't we looking for C, not zero?
 103          Good point.  So what we do is XOR LONGWORD with a longword,
 104          each of whose bytes is C.  This turns each byte that is C
 105          into a zero.  */
 106
 107
 108         /* Each round the main loop processes 16 bytes.  */
 109         ALIGN (4)
 110
 111 L(1):   movl (%eax), %ecx       /* get word (= 4 bytes) in question */
 112         movl $0xfefefeff, %edi  /* magic value */
 113         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 114                                    are now 0 */
 115         addl %ecx, %edi         /* add the magic value to the word.  We get
 116                                    carry bits reported for each byte which
 117                                    is *not* 0 */
 118
 119         /* According to the algorithm we had to reverse the effect of the
 120            XOR first and then test the overflow bits.  But because the
 121            following XOR would destroy the carry flag and it would (in a
 122            representation with more than 32 bits) not alter then last
 123            overflow, we can now test this condition.  If no carry is signaled
 124            no overflow must have occurred in the last byte => it was 0. */
 125         jnc L(8)
 126
 127         /* We are only interested in carry bits that change due to the
 128            previous add, so remove original bits */
 129         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 130
 131         /* Now test for the other three overflow bits.  */
 132         orl $0xfefefeff, %edi   /* set all non-carry bits */
 133         incl %edi               /* add 1: if one carry bit was *not* set
 134                                    the addition will not result in 0.  */
 135
 136         /* If at least one byte of the word is C we don't get 0 in %edi.  */
 137         jnz L(8)                /* found it => return pointer */
 138
 139         /* This process is unfolded four times for better performance.
 140            we don't increment the source pointer each time.  Instead we
 141            use offsets and increment by 16 in each run of the loop.  But
 142            before probing for the matching byte we need some extra code
 143            (following LL(13) below).  Even the len can be compared with
 144            constants instead of decrementing each time.  */
 145
 146         movl 4(%eax), %ecx      /* get word (= 4 bytes) in question */
 147         movl $0xfefefeff, %edi  /* magic value */
 148         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 149                                    are now 0 */
 150         addl %ecx, %edi         /* add the magic value to the word.  We get
 151                                    carry bits reported for each byte which
 152                                    is *not* 0 */
 153         jnc L(7)                /* highest byte is C => return pointer */
 154         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 155         orl $0xfefefeff, %edi   /* set all non-carry bits */
 156         incl %edi               /* add 1: if one carry bit was *not* set
 157                                    the addition will not result in 0.  */
 158         jnz L(7)                /* found it => return pointer */
 159
 160         movl 8(%eax), %ecx      /* get word (= 4 bytes) in question */
 161         movl $0xfefefeff, %edi  /* magic value */
 162         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 163                                    are now 0 */
 164         addl %ecx, %edi         /* add the magic value to the word.  We get
 165                                    carry bits reported for each byte which
 166                                    is *not* 0 */
 167         jnc L(6)                /* highest byte is C => return pointer */
 168         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 169         orl $0xfefefeff, %edi   /* set all non-carry bits */
 170         incl %edi               /* add 1: if one carry bit was *not* set
 171                                    the addition will not result in 0.  */
 172         jnz L(6)                /* found it => return pointer */
 173
 174         movl 12(%eax), %ecx     /* get word (= 4 bytes) in question */
 175         movl $0xfefefeff, %edi  /* magic value */
 176         xorl %edx, %ecx         /* XOR with word c|c|c|c => bytes of str == c
 177                                    are now 0 */
 178         addl %ecx, %edi         /* add the magic value to the word.  We get
 179                                    carry bits reported for each byte which
 180                                    is *not* 0 */
 181         jnc L(5)                /* highest byte is C => return pointer */
 182         xorl %ecx, %edi         /* ((word^charmask)+magic)^(word^charmask) */
 183         orl $0xfefefeff, %edi   /* set all non-carry bits */
 184         incl %edi               /* add 1: if one carry bit was *not* set
 185                                    the addition will not result in 0.  */
 186         jnz L(5)                /* found it => return pointer */
 187
 188         /* Adjust both counters for a full round, i.e. 16 bytes.  */
 189         addl $16, %eax
 190         jmp L(1)
 191         /* add missing source pointer increments */
 192 L(5):   addl $4, %eax
 193 L(6):   addl $4, %eax
 194 L(7):   addl $4, %eax
 195
 196         /* Test for the matching byte in the word.  %ecx contains a NUL
 197            char in the byte which originally was the byte we are looking
 198            at.  */
 199 L(8):   testb %cl, %cl          /* test first byte in dword */
 200         jz L(9)                 /* if zero => return pointer */
 201         incl %eax               /* increment source pointer */
 202
 203         testb %ch, %ch          /* test second byte in dword */
 204         jz L(9)                 /* if zero => return pointer */
 205         incl %eax               /* increment source pointer */
 206
 207         testl $0xff0000, %ecx   /* test third byte in dword */
 208         jz L(9)                 /* if zero => return pointer */
 209         incl %eax               /* increment source pointer */
 210
 211         /* No further test needed we we know it is one of the four bytes.  */
 212
 213 L(9):
 214         popl %edi               /* pop saved register */
 215         cfi_adjust_cfa_offset (-4)
 216         cfi_restore (edi)
 217
 218         ret
 219 END (__rawmemchr)
 220
 221 libc_hidden_def (__rawmemchr)
 222 weak_alias (__rawmemchr, rawmemchr)