sysdeps/m68k/strchr.S

   1 /* strchr (str, ch) -- Return pointer to first occurrence of CH in STR.
   2    For Motorola 68000.
   3    Copyright (C) 1999, 2003 Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5    Contributed by Andreas Schwab <schwab@gnu.org>.
   6
   7    The GNU C Library is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU Lesser General Public
   9    License as published by the Free Software Foundation; either
  10    version 2.1 of the License, or (at your option) any later version.
  11
  12    The GNU C Library is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    Lesser General Public License for more details.
  16
  17    You should have received a copy of the GNU Lesser General Public
  18    License along with the GNU C Library; if not, write to the Free
  19    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
  20    02111-1307 USA.  */
  21
  22 #include <sysdep.h>
  23 #include "asm-syntax.h"
  24
  25         TEXT
  26 ENTRY(strchr)
  27         /* Save the callee-saved registers we use.  */
  28         movel   R(d2),MEM_PREDEC(sp)
  29         movel   R(d3),MEM_PREDEC(sp)
  30
  31         /* Get string pointer and character.  */
  32         movel   MEM_DISP(sp,12),R(a0)
  33         moveb   MEM_DISP(sp,19),R(d0)
  34
  35         /* Distribute the character to all bytes of a longword.  */
  36         movel   R(d0),R(d1)
  37         lsll    #8,R(d1)
  38         moveb   R(d0),R(d1)
  39         movel   R(d1),R(d0)
  40         swap    R(d0)
  41         movew   R(d1),R(d0)
  42
  43         /* First search for the character one byte at a time until the
  44            pointer is aligned to a longword boundary.  */
  45         movel   R(a0),R(d1)
  46         andw    #3,R(d1)
  47         beq     L(L1)
  48         moveb   MEM(a0),R(d1)
  49         cmpb    R(d0),R(d1)
  50         beq     L(L9)
  51         tstb    R(d1)
  52         beq     L(L3)
  53         addql   #1,R(a0)
  54
  55         movel   R(a0),R(d1)
  56         andw    #3,R(d1)
  57         beq     L(L1)
  58         moveb   MEM(a0),R(d1)
  59         cmpb    R(d0),R(d1)
  60         beq     L(L9)
  61         tstb    R(d1)
  62         beq     L(L3)
  63         addql   #1,R(a0)
  64
  65         movel   R(a0),R(d1)
  66         andw    #3,R(d1)
  67         beq     L(L1)
  68         moveb   MEM(a0),R(d1)
  69         cmpb    R(d0),R(d1)
  70         beq     L(L9)
  71         tstb    R(d1)
  72         beq     L(L3)
  73         addql   #1,R(a0)
  74
  75 L(L1:)
  76         /* Load the magic bits.  Unlike the generic implementation we can
  77            use the carry bit as the fourth hole.  */
  78         movel   #0xfefefeff,R(d3)
  79
  80       /* We exit the loop if adding MAGIC_BITS to LONGWORD fails to
  81          change any of the hole bits of LONGWORD.
  82
  83          1) Is this safe?  Will it catch all the zero bytes?
  84          Suppose there is a byte with all zeros.  Any carry bits
  85          propagating from its left will fall into the hole at its
  86          least significant bit and stop.  Since there will be no
  87          carry from its most significant bit, the LSB of the
  88          byte to the left will be unchanged, and the zero will be
  89          detected.
  90
  91          2) Is this worthwhile?  Will it ignore everything except
  92          zero bytes?  Suppose every byte of LONGWORD has a bit set
  93          somewhere.  There will be a carry into bit 8.  If bit 8
  94          is set, this will carry into bit 16.  If bit 8 is clear,
  95          one of bits 9-15 must be set, so there will be a carry
  96          into bit 16.  Similarly, there will be a carry into bit
  97          24.  If one of bits 24-31 is set, there will be a carry
  98          into bit 32 (=carry flag), so all of the hole bits will
  99          be changed.
 100
 101          3) But wait!  Aren't we looking for C, not zero?
 102          Good point.  So what we do is XOR LONGWORD with a longword,
 103          each of whose bytes is C.  This turns each byte that is C
 104          into a zero.  */
 105
 106 L(L2:)
 107         /* Get the longword in question.  */
 108         movel   MEM_POSTINC(a0),R(d1)
 109         /* XOR with the byte we search for.  */
 110         eorl    R(d0),R(d1)
 111
 112         /* Add the magic value.  We get carry bits reported for each byte
 113            which is not C.  */
 114         movel   R(d3),R(d2)
 115         addl    R(d1),R(d2)
 116
 117         /* Check the fourth carry bit before it is clobbered by the next
 118            XOR.  If it is not set we have a hit.  */
 119         bcc     L(L8)
 120
 121         /* We are only interested in carry bits that change due to the
 122            previous add, so remove original bits.  */
 123         eorl    R(d1),R(d2)
 124
 125         /* Now test for the other three overflow bits.
 126            Set all non-carry bits.  */
 127         orl     R(d3),R(d2)
 128         /* Add 1 to get zero if all carry bits were set.  */
 129         addql   #1,R(d2)
 130
 131         /* If we don't get zero then at least one byte of the word equals
 132            C.  */
 133         bne     L(L8)
 134
 135         /* Next look for a NUL byte.
 136            Restore original longword without reload.  */
 137         eorl    R(d0),R(d1)
 138         /* Add the magic value.  We get carry bits reported for each byte
 139            which is not NUL.  */
 140         movel   R(d3),R(d2)
 141         addl    R(d1),R(d2)
 142
 143         /* Check the fourth carry bit before it is clobbered by the next
 144            XOR.  If it is not set we have a hit, and return NULL.  */
 145         bcc     L(L3)
 146
 147         /* We are only interested in carry bits that change due to the
 148            previous add, so remove original bits.  */
 149         eorl    R(d1),R(d2)
 150
 151         /* Now test for the other three overflow bits.
 152            Set all non-carry bits.  */
 153         orl     R(d3),R(d2)
 154         /* Add 1 to get zero if all carry bits were set.  */
 155         addql   #1,R(d2)
 156
 157         /* If we don't get zero then at least one byte of the word was NUL
 158            and we return NULL.  Otherwise continue with the next longword.  */
 159         bne     L(L3)
 160
 161         /* Get the longword in question.  */
 162         movel   MEM_POSTINC(a0),R(d1)
 163         /* XOR with the byte we search for.  */
 164         eorl    R(d0),R(d1)
 165
 166         /* Add the magic value.  We get carry bits reported for each byte
 167            which is not C.  */
 168         movel   R(d3),R(d2)
 169         addl    R(d1),R(d2)
 170
 171         /* Check the fourth carry bit before it is clobbered by the next
 172            XOR.  If it is not set we have a hit.  */
 173         bcc     L(L8)
 174
 175         /* We are only interested in carry bits that change due to the
 176            previous add, so remove original bits */
 177         eorl    R(d1),R(d2)
 178
 179         /* Now test for the other three overflow bits.
 180            Set all non-carry bits.  */
 181         orl     R(d3),R(d2)
 182         /* Add 1 to get zero if all carry bits were set.  */
 183         addql   #1,R(d2)
 184
 185         /* If we don't get zero then at least one byte of the word equals
 186            C.  */
 187         bne     L(L8)
 188
 189         /* Next look for a NUL byte.
 190            Restore original longword without reload.  */
 191         eorl    R(d0),R(d1)
 192         /* Add the magic value.  We get carry bits reported for each byte
 193            which is not NUL.  */
 194         movel   R(d3),R(d2)
 195         addl    R(d1),R(d2)
 196
 197         /* Check the fourth carry bit before it is clobbered by the next
 198            XOR.  If it is not set we have a hit, and return NULL.  */
 199         bcc     L(L3)
 200
 201         /* We are only interested in carry bits that change due to the
 202            previous add, so remove original bits */
 203         eorl    R(d1),R(d2)
 204
 205         /* Now test for the other three overflow bits.
 206            Set all non-carry bits.  */
 207         orl     R(d3),R(d2)
 208         /* Add 1 to get zero if all carry bits were set.  */
 209         addql   #1,R(d2)
 210
 211         /* If we don't get zero then at least one byte of the word was NUL
 212            and we return NULL.  Otherwise continue with the next longword.  */
 213         beq     L(L2)
 214
 215 L(L3:)
 216         /* Return NULL.  */
 217         clrl    R(d0)
 218         movel   R(d0),R(a0)
 219         movel   MEM_POSTINC(sp),R(d3)
 220         movel   MEM_POSTINC(sp),R(d2)
 221         rts
 222
 223 L(L8:)
 224         /* We have a hit.  Check to see which byte it was.  First
 225            compensate for the autoincrement in the loop.  */
 226         subql   #4,R(a0)
 227
 228         moveb   MEM(a0),R(d1)
 229         cmpb    R(d0),R(d1)
 230         beq     L(L9)
 231         tstb    R(d1)
 232         beq     L(L3)
 233         addql   #1,R(a0)
 234
 235         moveb   MEM(a0),R(d1)
 236         cmpb    R(d0),R(d1)
 237         beq     L(L9)
 238         tstb    R(d1)
 239         beq     L(L3)
 240         addql   #1,R(a0)
 241
 242         moveb   MEM(a0),R(d1)
 243         cmpb    R(d0),R(d1)
 244         beq     L(L9)
 245         tstb    R(d1)
 246         beq     L(L3)
 247         addql   #1,R(a0)
 248
 249         /* Otherwise the fourth byte must equal C.  */
 250 L(L9:)
 251         movel   R(a0),R(d0)
 252         movel   MEM_POSTINC(sp),R(d3)
 253         movel   MEM_POSTINC(sp),R(d2)
 254         rts
 255 END(strchr)
 256
 257 weak_alias (strchr, index)
 258 libc_hidden_builtin_def (strchr)