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 shift   x4
  52
  53 /* For the first 32 bytes, NUL detection works on the principle that
  54    (X - 1) & (~X) & 0x80 (=> (X - 1) & ~(X | 0x7f)) is non-zero if a
  55    byte is zero, and can be done in parallel across the entire word.  */
  56
  57 #define REP8_01 0x0101010101010101
  58 #define REP8_7f 0x7f7f7f7f7f7f7f7f
  59
  60 /* To test the page crossing code path more thoroughly, compile with
  61    -DTEST_PAGE_CROSS - this will force all calls through the slower
  62    entry path.  This option is not intended for production use.  */
  63
  64 #ifdef TEST_PAGE_CROSS
  65 # define MIN_PAGE_SIZE 32
  66 #else
  67 # define MIN_PAGE_SIZE 4096
  68 #endif
  69
  70 /* Core algorithm:
  71
  72    Since strings are short on average, we check the first 32 bytes of the
  73    string for a NUL character without aligning the string.  In order to use
  74    unaligned loads safely we must do a page cross check first.
  75
  76    If there is a NUL byte we calculate the length from the 2 8-byte words
  77    using conditional select to reduce branch mispredictions (it is unlikely
  78    strlen will be repeatedly called on strings with the same length).
  79
  80    If the string is longer than 32 bytes, align src so we don't need further
  81    page cross checks, and process 32 bytes per iteration using a fast SIMD
  82    loop.
  83
  84    If the page cross check fails, we read 32 bytes from an aligned address,
  85    and ignore any characters before the string.  If it contains a NUL
  86    character, return the length, if not, continue in the main loop.  */
  87
  88 ENTRY (__strlen_asimd)
  89         PTR_ARG (0)
  90
  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         .p2align 3
 127         /* Look for a NUL byte at offset 16..31 in the string.  */
 128 L(bytes16_31):
 129         ldp     data1, data2, [srcin, 16]
 130 #ifdef __AARCH64EB__
 131         rev     data1, data1
 132         rev     data2, data2
 133 #endif
 134         sub     tmp1, data1, zeroones
 135         orr     tmp2, data1, REP8_7f
 136         sub     tmp3, data2, zeroones
 137         orr     tmp4, data2, REP8_7f
 138         bics    has_nul1, tmp1, tmp2
 139         bic     has_nul2, tmp3, tmp4
 140         ccmp    has_nul2, 0, 0, eq
 141         b.eq    L(loop_entry)
 142
 143         /* Find the exact offset of the first NUL byte at offset 16..31 from
 144            the string start.  Enter with C = has_nul1 == 0.  */
 145         csel    has_nul1, has_nul1, has_nul2, cc
 146         mov     len, 24
 147         rev     has_nul1, has_nul1
 148         mov     tmp3, 16
 149         clz     tmp1, has_nul1
 150         csel    len, tmp3, len, cc
 151         add     len, len, tmp1, lsr 3
 152         ret
 153
 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         tst     synd, 0xffffffff
 170         b.ne    1f
 171         cmeq    maskv.16b, datav2.16b, 0
 172         add     len, len, 16
 173 1:
 174         /* Generate a bitmask and compute correct byte offset.  */
 175 #ifdef __AARCH64EB__
 176         bic     maskv.8h, 0xf0
 177 #else
 178         bic     maskv.8h, 0x0f, lsl 8
 179 #endif
 180         umaxp   maskv.16b, maskv.16b, maskv.16b
 181         fmov    synd, maskd
 182 #ifndef __AARCH64EB__
 183         rbit    synd, synd
 184 #endif
 185         clz     tmp, synd
 186         add     len, len, tmp, lsr 2
 187         ret
 188
 189         .p2align 4
 190
 191 L(page_cross):
 192         bic     src, srcin, 31
 193         mov     tmpw, 0x0c03
 194         movk    tmpw, 0xc030, lsl 16
 195         ld1     {datav1.16b, datav2.16b}, [src]
 196         dup     maskv.4s, tmpw
 197         cmeq    datav1.16b, datav1.16b, 0
 198         cmeq    datav2.16b, datav2.16b, 0
 199         and     datav1.16b, datav1.16b, maskv.16b
 200         and     datav2.16b, datav2.16b, maskv.16b
 201         addp    maskv.16b, datav1.16b, datav2.16b
 202         addp    maskv.16b, maskv.16b, maskv.16b
 203         fmov    synd, maskd
 204         lsl     shift, srcin, 1
 205         lsr     synd, synd, shift
 206         cbz     synd, L(loop)
 207
 208         rbit    synd, synd
 209         clz     len, synd
 210         lsr     len, len, 1
 211         ret
 212
 213 END (__strlen_asimd)
 214 libc_hidden_builtin_def (__strlen_asimd)