sysdeps/aarch64/multiarch/strlen_asimd.S

   1 /* Optimized strlen implementation using SIMD.
   2    Copyright (C) 2018-2023 Free Software Foundation, Inc.
   3
   4    This file is part of the GNU C Library.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library.  If not, see
  18    <https://www.gnu.org/licenses/>.  */
  19
  20 #include <sysdep.h>
  21
  22 /* Assumptions:
  23  *
  24  * ARMv8-a, AArch64, Advanced SIMD, unaligned accesses.
  25  * Not MTE compatible.
  26  */
  27
  28 #define srcin   x0
  29 #define len     x0
  30
  31 #define src     x1
  32 #define data1   x2
  33 #define data2   x3
  34 #define has_nul1 x4
  35 #define has_nul2 x5
  36 #define tmp1    x4
  37 #define tmp2    x5
  38 #define tmp3    x6
  39 #define tmp4    x7
  40 #define zeroones x8
  41
  42 #define maskv   v0
  43 #define maskd   d0
  44 #define dataq1  q1
  45 #define dataq2  q2
  46 #define datav1  v1
  47 #define datav2  v2
  48 #define tmp     x2
  49 #define tmpw    w2
  50 #define synd    x3
  51 #define syndw   w3
  52 #define shift   x4
  53
  54 /* For the first 32 bytes, NUL detection works on the principle that
  55    (X - 1) & (~X) & 0x80 (=> (X - 1) & ~(X | 0x7f)) is non-zero if a
  56    byte is zero, and can be done in parallel across the entire word.  */
  57
  58 #define REP8_01 0x0101010101010101
  59 #define REP8_7f 0x7f7f7f7f7f7f7f7f
  60
  61 /* To test the page crossing code path more thoroughly, compile with
  62    -DTEST_PAGE_CROSS - this will force all calls through the slower
  63    entry path.  This option is not intended for production use.  */
  64
  65 #ifdef TEST_PAGE_CROSS
  66 # define MIN_PAGE_SIZE 32
  67 #else
  68 # define MIN_PAGE_SIZE 4096
  69 #endif
  70
  71 /* Core algorithm:
  72
  73    Since strings are short on average, we check the first 32 bytes of the
  74    string for a NUL character without aligning the string.  In order to use
  75    unaligned loads safely we must do a page cross check first.
  76
  77    If there is a NUL byte we calculate the length from the 2 8-byte words
  78    using conditional select to reduce branch mispredictions (it is unlikely
  79    strlen will be repeatedly called on strings with the same length).
  80
  81    If the string is longer than 32 bytes, align src so we don't need further
  82    page cross checks, and process 32 bytes per iteration using a fast SIMD
  83    loop.
  84
  85    If the page cross check fails, we read 32 bytes from an aligned address,
  86    and ignore any characters before the string.  If it contains a NUL
  87    character, return the length, if not, continue in the main loop.  */
  88
  89 ENTRY (__strlen_asimd)
  90         PTR_ARG (0)
  91         and     tmp1, srcin, MIN_PAGE_SIZE - 1
  92         cmp     tmp1, MIN_PAGE_SIZE - 32
  93         b.hi    L(page_cross)
  94
  95         /* Look for a NUL byte in the first 16 bytes.  */
  96         ldp     data1, data2, [srcin]
  97         mov     zeroones, REP8_01
  98
  99 #ifdef __AARCH64EB__
 100         /* For big-endian, carry propagation (if the final byte in the
 101            string is 0x01) means we cannot use has_nul1/2 directly.
 102            Since we expect strings to be small and early-exit,
 103            byte-swap the data now so has_null1/2 will be correct.  */
 104         rev     data1, data1
 105         rev     data2, data2
 106 #endif
 107         sub     tmp1, data1, zeroones
 108         orr     tmp2, data1, REP8_7f
 109         sub     tmp3, data2, zeroones
 110         orr     tmp4, data2, REP8_7f
 111         bics    has_nul1, tmp1, tmp2
 112         bic     has_nul2, tmp3, tmp4
 113         ccmp    has_nul2, 0, 0, eq
 114         b.eq    L(bytes16_31)
 115
 116         /* Find the exact offset of the first NUL byte in the first 16 bytes
 117            from the string start.  Enter with C = has_nul1 == 0.  */
 118         csel    has_nul1, has_nul1, has_nul2, cc
 119         mov     len, 8
 120         rev     has_nul1, has_nul1
 121         csel    len, xzr, len, cc
 122         clz     tmp1, has_nul1
 123         add     len, len, tmp1, lsr 3
 124         ret
 125
 126         /* Look for a NUL byte at offset 16..31 in the string.  */
 127 L(bytes16_31):
 128         ldp     data1, data2, [srcin, 16]
 129 #ifdef __AARCH64EB__
 130         rev     data1, data1
 131         rev     data2, data2
 132 #endif
 133         sub     tmp1, data1, zeroones
 134         orr     tmp2, data1, REP8_7f
 135         sub     tmp3, data2, zeroones
 136         orr     tmp4, data2, REP8_7f
 137         bics    has_nul1, tmp1, tmp2
 138         bic     has_nul2, tmp3, tmp4
 139         ccmp    has_nul2, 0, 0, eq
 140         b.eq    L(loop_entry)
 141
 142         /* Find the exact offset of the first NUL byte at offset 16..31 from
 143            the string start.  Enter with C = has_nul1 == 0.  */
 144         csel    has_nul1, has_nul1, has_nul2, cc
 145         mov     len, 24
 146         rev     has_nul1, has_nul1
 147         mov     tmp3, 16
 148         clz     tmp1, has_nul1
 149         csel    len, tmp3, len, cc
 150         add     len, len, tmp1, lsr 3
 151         ret
 152
 153         nop
 154 L(loop_entry):
 155         bic     src, srcin, 31
 156
 157         .p2align 5
 158 L(loop):
 159         ldp     dataq1, dataq2, [src, 32]!
 160         uminp   maskv.16b, datav1.16b, datav2.16b
 161         uminp   maskv.16b, maskv.16b, maskv.16b
 162         cmeq    maskv.8b, maskv.8b, 0
 163         fmov    synd, maskd
 164         cbz     synd, L(loop)
 165
 166         /* Low 32 bits of synd are non-zero if a NUL was found in datav1.  */
 167         cmeq    maskv.16b, datav1.16b, 0
 168         sub     len, src, srcin
 169         cbnz    syndw, 1f
 170         cmeq    maskv.16b, datav2.16b, 0
 171         add     len, len, 16
 172 1:
 173         /* Generate a bitmask and compute correct byte offset.  */
 174         shrn    maskv.8b, maskv.8h, 4
 175         fmov    synd, maskd
 176 #ifndef __AARCH64EB__
 177         rbit    synd, synd
 178 #endif
 179         clz     tmp, synd
 180         add     len, len, tmp, lsr 2
 181         ret
 182
 183 L(page_cross):
 184         bic     src, srcin, 31
 185         mov     tmpw, 0x0c03
 186         movk    tmpw, 0xc030, lsl 16
 187         ld1     {datav1.16b, datav2.16b}, [src]
 188         dup     maskv.4s, tmpw
 189         cmeq    datav1.16b, datav1.16b, 0
 190         cmeq    datav2.16b, datav2.16b, 0
 191         and     datav1.16b, datav1.16b, maskv.16b
 192         and     datav2.16b, datav2.16b, maskv.16b
 193         addp    maskv.16b, datav1.16b, datav2.16b
 194         addp    maskv.16b, maskv.16b, maskv.16b
 195         fmov    synd, maskd
 196         lsl     shift, srcin, 1
 197         lsr     synd, synd, shift
 198         cbz     synd, L(loop)
 199
 200         rbit    synd, synd
 201         clz     len, synd
 202         lsr     len, len, 1
 203         ret
 204
 205 END (__strlen_asimd)
 206 libc_hidden_builtin_def (__strlen_asimd)