sysdeps/m68k/memchr.S

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