sysdeps/aarch64/strrchr.S

   1 /* strrchr: find the last instance of a character in a string.
   2
   3    Copyright (C) 2014-2018 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    <http://www.gnu.org/licenses/>.  */
  20
  21 #include <sysdep.h>
  22
  23 /* Assumptions:
  24  *
  25  * ARMv8-a, AArch64
  26  * Neon Available.
  27  */
  28
  29 /* Arguments and results.  */
  30 #define srcin           x0
  31 #define chrin           w1
  32
  33 #define result          x0
  34
  35 #define src             x2
  36 #define tmp1            x3
  37 #define wtmp2           w4
  38 #define tmp3            x5
  39 #define src_match       x6
  40 #define src_offset      x7
  41 #define const_m1        x8
  42 #define tmp4            x9
  43 #define nul_match       x10
  44 #define chr_match       x11
  45
  46 #define vrepchr         v0
  47 #define vdata1          v1
  48 #define vdata2          v2
  49 #define vhas_nul1       v3
  50 #define vhas_nul2       v4
  51 #define vhas_chr1       v5
  52 #define vhas_chr2       v6
  53 #define vrepmask_0      v7
  54 #define vrepmask_c      v16
  55 #define vend1           v17
  56 #define vend2           v18
  57
  58 /* Core algorithm.
  59
  60    For each 32-byte hunk we calculate a 64-bit syndrome value, with
  61    two bits per byte (LSB is always in bits 0 and 1, for both big
  62    and little-endian systems).  For each tuple, bit 0 is set iff
  63    the relevant byte matched the requested character; bit 1 is set
  64    iff the relevant byte matched the NUL end of string (we trigger
  65    off bit0 for the special case of looking for NUL).  Since the bits
  66    in the syndrome reflect exactly the order in which things occur
  67    in the original string a count_trailing_zeros() operation will
  68    identify exactly which byte is causing the termination, and why.  */
  69
  70 ENTRY(strrchr)
  71         DELOUSE (0)
  72         cbz     x1, L(null_search)
  73         /* Magic constant 0x40100401 to allow us to identify which lane
  74            matches the requested byte.  Magic constant 0x80200802 used
  75            similarly for NUL termination.  */
  76         mov     wtmp2, #0x0401
  77         movk    wtmp2, #0x4010, lsl #16
  78         dup     vrepchr.16b, chrin
  79         bic     src, srcin, #31         /* Work with aligned 32-byte hunks.  */
  80         dup     vrepmask_c.4s, wtmp2
  81         mov     src_offset, #0
  82         ands    tmp1, srcin, #31
  83         add     vrepmask_0.4s, vrepmask_c.4s, vrepmask_c.4s /* equiv: lsl #1 */
  84         b.eq    L(aligned)
  85
  86         /* Input string is not 32-byte aligned.  Rather than forcing
  87            the padding bytes to a safe value, we calculate the syndrome
  88            for all the bytes, but then mask off those bits of the
  89            syndrome that are related to the padding.  */
  90         ld1     {vdata1.16b, vdata2.16b}, [src], #32
  91         neg     tmp1, tmp1
  92         cmeq    vhas_nul1.16b, vdata1.16b, #0
  93         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
  94         cmeq    vhas_nul2.16b, vdata2.16b, #0
  95         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
  96         and     vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
  97         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
  98         and     vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
  99         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
 100         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b     // 256->128
 101         addp    vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b     // 256->128
 102         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b     // 128->64
 103         addp    vhas_chr1.16b, vhas_chr1.16b, vhas_chr1.16b     // 128->64
 104         mov     nul_match, vhas_nul1.2d[0]
 105         lsl     tmp1, tmp1, #1
 106         mov     const_m1, #~0
 107         mov     chr_match, vhas_chr1.2d[0]
 108         lsr     tmp3, const_m1, tmp1
 109
 110         bic     nul_match, nul_match, tmp3      // Mask padding bits.
 111         bic     chr_match, chr_match, tmp3      // Mask padding bits.
 112         cbnz    nul_match, L(tail)
 113
 114 L(loop):
 115         cmp     chr_match, #0
 116         csel    src_match, src, src_match, ne
 117         csel    src_offset, chr_match, src_offset, ne
 118 L(aligned):
 119         ld1     {vdata1.16b, vdata2.16b}, [src], #32
 120         cmeq    vhas_nul1.16b, vdata1.16b, #0
 121         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
 122         cmeq    vhas_nul2.16b, vdata2.16b, #0
 123         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
 124         addp    vend1.16b, vhas_nul1.16b, vhas_nul2.16b // 256->128
 125         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
 126         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
 127         addp    vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b     // 256->128
 128         addp    vend1.16b, vend1.16b, vend1.16b // 128->64
 129         addp    vhas_chr1.16b, vhas_chr1.16b, vhas_chr1.16b     // 128->64
 130         mov     nul_match, vend1.2d[0]
 131         mov     chr_match, vhas_chr1.2d[0]
 132         cbz     nul_match, L(loop)
 133
 134         and     vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
 135         and     vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
 136         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b
 137         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b
 138         mov     nul_match, vhas_nul1.2d[0]
 139
 140 L(tail):
 141         /* Work out exactly where the string ends.  */
 142         sub     tmp4, nul_match, #1
 143         eor     tmp4, tmp4, nul_match
 144         ands    chr_match, chr_match, tmp4
 145         /* And pick the values corresponding to the last match.  */
 146         csel    src_match, src, src_match, ne
 147         csel    src_offset, chr_match, src_offset, ne
 148
 149         /* Count down from the top of the syndrome to find the last match.  */
 150         clz     tmp3, src_offset
 151         /* Src_match points beyond the word containing the match, so we can
 152            simply subtract half the bit-offset into the syndrome.  Because
 153            we are counting down, we need to go back one more character.  */
 154         add     tmp3, tmp3, #2
 155         sub     result, src_match, tmp3, lsr #1
 156         /* But if the syndrome shows no match was found, then return NULL.  */
 157         cmp     src_offset, #0
 158         csel    result, result, xzr, ne
 159
 160         ret
 161 L(null_search):
 162         b       __strchrnul
 163
 164 END(strrchr)
 165 weak_alias (strrchr, rindex)
 166 libc_hidden_builtin_def (strrchr)