sysdeps/aarch64/strchr.S

   1 /* strchr - find a character in a string
   2
   3    Copyright (C) 2014-2019 Free Software Foundation, Inc.
   4
   5    This file is part of the GNU C Library.
   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, see
  19    <https://www.gnu.org/licenses/>.  */
  20
  21 #include <sysdep.h>
  22
  23 /* Assumptions:
  24  *
  25  * ARMv8-a, AArch64
  26  */
  27
  28 /* Arguments and results.  */
  29 #define srcin           x0
  30 #define chrin           w1
  31
  32 #define result          x0
  33
  34 #define src             x2
  35 #define tmp1            x3
  36 #define wtmp2           w4
  37 #define tmp3            x5
  38
  39 #define vrepchr         v0
  40 #define vdata1          v1
  41 #define vdata2          v2
  42 #define vhas_nul1       v3
  43 #define vhas_nul2       v4
  44 #define vhas_chr1       v5
  45 #define vhas_chr2       v6
  46 #define vrepmask_0      v7
  47 #define vrepmask_c      v16
  48 #define vend1           v17
  49 #define vend2           v18
  50
  51         /* Core algorithm.
  52            For each 32-byte hunk we calculate a 64-bit syndrome value, with
  53            two bits per byte (LSB is always in bits 0 and 1, for both big
  54            and little-endian systems).  Bit 0 is set iff the relevant byte
  55            matched the requested character.  Bit 1 is set iff the
  56            relevant byte matched the NUL end of string (we trigger off bit0
  57            for the special case of looking for NUL).  Since the bits
  58            in the syndrome reflect exactly the order in which things occur
  59            in the original string a count_trailing_zeros() operation will
  60            identify exactly which byte is causing the termination, and why.  */
  61
  62 /* Locals and temporaries.  */
  63
  64 ENTRY (strchr)
  65         DELOUSE (0)
  66         mov     wtmp2, #0x0401
  67         movk    wtmp2, #0x4010, lsl #16
  68         dup     vrepchr.16b, chrin
  69         bic     src, srcin, #31
  70         dup     vrepmask_c.4s, wtmp2
  71         ands    tmp1, srcin, #31
  72         add     vrepmask_0.4s, vrepmask_c.4s, vrepmask_c.4s // lsl #1
  73         b.eq    L(loop)
  74
  75         /* Input string is not 32-byte aligned.  Rather than forcing
  76            the padding bytes to a safe value, we calculate the syndrome
  77            for all the bytes, but then mask off those bits of the
  78            syndrome that are related to the padding.  */
  79         ld1     {vdata1.16b, vdata2.16b}, [src], #32
  80         neg     tmp1, tmp1
  81         cmeq    vhas_nul1.16b, vdata1.16b, #0
  82         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
  83         cmeq    vhas_nul2.16b, vdata2.16b, #0
  84         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
  85         and     vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
  86         and     vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
  87         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
  88         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
  89         orr     vend1.16b, vhas_nul1.16b, vhas_chr1.16b
  90         orr     vend2.16b, vhas_nul2.16b, vhas_chr2.16b
  91         lsl     tmp1, tmp1, #1
  92         addp    vend1.16b, vend1.16b, vend2.16b         // 256->128
  93         mov     tmp3, #~0
  94         addp    vend1.16b, vend1.16b, vend2.16b         // 128->64
  95         lsr     tmp1, tmp3, tmp1
  96
  97         mov     tmp3, vend1.2d[0]
  98         bic     tmp1, tmp3, tmp1        // Mask padding bits.
  99         cbnz    tmp1, L(tail)
 100
 101 L(loop):
 102         ld1     {vdata1.16b, vdata2.16b}, [src], #32
 103         cmeq    vhas_nul1.16b, vdata1.16b, #0
 104         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
 105         cmeq    vhas_nul2.16b, vdata2.16b, #0
 106         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
 107         /* Use a fast check for the termination condition.  */
 108         orr     vend1.16b, vhas_nul1.16b, vhas_chr1.16b
 109         orr     vend2.16b, vhas_nul2.16b, vhas_chr2.16b
 110         orr     vend1.16b, vend1.16b, vend2.16b
 111         addp    vend1.2d, vend1.2d, vend1.2d
 112         mov     tmp1, vend1.2d[0]
 113         cbz     tmp1, L(loop)
 114
 115         /* Termination condition found.  Now need to establish exactly why
 116            we terminated.  */
 117         and     vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
 118         and     vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
 119         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
 120         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
 121         orr     vend1.16b, vhas_nul1.16b, vhas_chr1.16b
 122         orr     vend2.16b, vhas_nul2.16b, vhas_chr2.16b
 123         addp    vend1.16b, vend1.16b, vend2.16b         // 256->128
 124         addp    vend1.16b, vend1.16b, vend2.16b         // 128->64
 125
 126         mov     tmp1, vend1.2d[0]
 127 L(tail):
 128         sub     src, src, #32
 129         rbit    tmp1, tmp1
 130         clz     tmp1, tmp1
 131         /* Tmp1 is even if the target charager was found first.  Otherwise
 132            we've found the end of string and we weren't looking for NUL.  */
 133         tst     tmp1, #1
 134         add     result, src, tmp1, lsr #1
 135         csel    result, result, xzr, eq
 136         ret
 137 END (strchr)
 138 libc_hidden_builtin_def (strchr)
 139 weak_alias (strchr, index)