newlib/libc/machine/aarch64/strrchr.S

   1 /*
   2  * strrchr - find last position of a character in a string.
   3  *
   4  * Copyright (c) 2014-2022, Arm Limited.
   5  * SPDX-License-Identifier: MIT OR Apache-2.0 WITH LLVM-exception
   6  */
   7 #if (defined (__OPTIMIZE_SIZE__) || defined (PREFER_SIZE_OVER_SPEED))
   8 /* See strchr-stub.c  */
   9 #else
  10
  11 /* Assumptions:
  12  *
  13  * ARMv8-a, AArch64
  14  * Neon Available.
  15  */
  16
  17 #include "asmdefs.h"
  18
  19 /* Arguments and results.  */
  20 #define srcin           x0
  21 #define chrin           w1
  22
  23 #define result          x0
  24
  25 #define src             x2
  26 #define tmp1            x3
  27 #define wtmp2           w4
  28 #define tmp3            x5
  29 #define src_match       x6
  30 #define src_offset      x7
  31 #define const_m1        x8
  32 #define tmp4            x9
  33 #define nul_match       x10
  34 #define chr_match       x11
  35
  36 #define vrepchr         v0
  37 #define vdata1          v1
  38 #define vdata2          v2
  39 #define vhas_nul1       v3
  40 #define vhas_nul2       v4
  41 #define vhas_chr1       v5
  42 #define vhas_chr2       v6
  43 #define vrepmask_0      v7
  44 #define vrepmask_c      v16
  45 #define vend1           v17
  46 #define vend2           v18
  47
  48 /* Core algorithm.
  49
  50    For each 32-byte hunk we calculate a 64-bit syndrome value, with
  51    two bits per byte (LSB is always in bits 0 and 1, for both big
  52    and little-endian systems).  For each tuple, bit 0 is set iff
  53    the relevant byte matched the requested character; bit 1 is set
  54    iff the relevant byte matched the NUL end of string (we trigger
  55    off bit0 for the special case of looking for NUL).  Since the bits
  56    in the syndrome reflect exactly the order in which things occur
  57    in the original string a count_trailing_zeros() operation will
  58    identify exactly which byte is causing the termination, and why.  */
  59
  60 ENTRY (strrchr)
  61         PTR_ARG (0)
  62         /* Magic constant 0x40100401 to allow us to identify which lane
  63            matches the requested byte.  Magic constant 0x80200802 used
  64            similarly for NUL termination.  */
  65         mov     wtmp2, #0x0401
  66         movk    wtmp2, #0x4010, lsl #16
  67         dup     vrepchr.16b, chrin
  68         bic     src, srcin, #31         /* Work with aligned 32-byte hunks.  */
  69         dup     vrepmask_c.4s, wtmp2
  70         mov     src_offset, #0
  71         ands    tmp1, srcin, #31
  72         add     vrepmask_0.4s, vrepmask_c.4s, vrepmask_c.4s /* equiv: lsl #1 */
  73         b.eq    L(aligned)
  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_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
  87         and     vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
  88         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
  89         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b     // 256->128
  90         addp    vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b     // 256->128
  91         addp    vend1.16b, vhas_nul1.16b, vhas_chr1.16b         // 128->64
  92         mov     nul_match, vend1.d[0]
  93         lsl     tmp1, tmp1, #1
  94         mov     const_m1, #~0
  95         lsr     tmp3, const_m1, tmp1
  96         mov     chr_match, vend1.d[1]
  97
  98         bic     nul_match, nul_match, tmp3      // Mask padding bits.
  99         bic     chr_match, chr_match, tmp3      // Mask padding bits.
 100         cbnz    nul_match, L(tail)
 101
 102         .p2align 4
 103 L(loop):
 104         cmp     chr_match, #0
 105         csel    src_match, src, src_match, ne
 106         csel    src_offset, chr_match, src_offset, ne
 107 L(aligned):
 108         ld1     {vdata1.16b, vdata2.16b}, [src], #32
 109         cmeq    vhas_chr1.16b, vdata1.16b, vrepchr.16b
 110         cmeq    vhas_chr2.16b, vdata2.16b, vrepchr.16b
 111         uminp   vend1.16b, vdata1.16b, vdata2.16b
 112         and     vhas_chr1.16b, vhas_chr1.16b, vrepmask_c.16b
 113         and     vhas_chr2.16b, vhas_chr2.16b, vrepmask_c.16b
 114         cmeq    vend1.16b, vend1.16b, 0
 115         addp    vhas_chr1.16b, vhas_chr1.16b, vhas_chr2.16b     // 256->128
 116         addp    vend1.16b, vend1.16b, vhas_chr1.16b             // 128->64
 117         mov     nul_match, vend1.d[0]
 118         mov     chr_match, vend1.d[1]
 119         cbz     nul_match, L(loop)
 120
 121         cmeq    vhas_nul1.16b, vdata1.16b, #0
 122         cmeq    vhas_nul2.16b, vdata2.16b, #0
 123         and     vhas_nul1.16b, vhas_nul1.16b, vrepmask_0.16b
 124         and     vhas_nul2.16b, vhas_nul2.16b, vrepmask_0.16b
 125         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul2.16b
 126         addp    vhas_nul1.16b, vhas_nul1.16b, vhas_nul1.16b
 127         mov     nul_match, vhas_nul1.d[0]
 128
 129 L(tail):
 130         /* Work out exactly where the string ends.  */
 131         sub     tmp4, nul_match, #1
 132         eor     tmp4, tmp4, nul_match
 133         ands    chr_match, chr_match, tmp4
 134         /* And pick the values corresponding to the last match.  */
 135         csel    src_match, src, src_match, ne
 136         csel    src_offset, chr_match, src_offset, ne
 137
 138         /* Count down from the top of the syndrome to find the last match.  */
 139         clz     tmp3, src_offset
 140         /* Src_match points beyond the word containing the match, so we can
 141            simply subtract half the bit-offset into the syndrome.  Because
 142            we are counting down, we need to go back one more character.  */
 143         add     tmp3, tmp3, #2
 144         sub     result, src_match, tmp3, lsr #1
 145         /* But if the syndrome shows no match was found, then return NULL.  */
 146         cmp     src_offset, #0
 147         csel    result, result, xzr, ne
 148
 149         ret
 150
 151 END (strrchr)
 152 #endif