sysdeps/aarch64/strnlen.S

   1 /* strnlen - calculate the length of a string with limit.
   2
   3    Copyright (C) 2013-2020 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 len             x0
  31 #define limit           x1
  32
  33 /* Locals and temporaries.  */
  34 #define src             x2
  35 #define data1           x3
  36 #define data2           x4
  37 #define data2a          x5
  38 #define has_nul1        x6
  39 #define has_nul2        x7
  40 #define tmp1            x8
  41 #define tmp2            x9
  42 #define tmp3            x10
  43 #define tmp4            x11
  44 #define zeroones        x12
  45 #define pos             x13
  46 #define limit_wd        x14
  47
  48 #define dataq           q2
  49 #define datav           v2
  50 #define datab2          b3
  51 #define dataq2          q3
  52 #define datav2          v3
  53 #define REP8_01 0x0101010101010101
  54 #define REP8_7f 0x7f7f7f7f7f7f7f7f
  55 #define REP8_80 0x8080808080808080
  56
  57 ENTRY_ALIGN_AND_PAD (__strnlen, 6, 9)
  58         DELOUSE (0)
  59         DELOUSE (1)
  60         DELOUSE (2)
  61         cbz     limit, L(hit_limit)
  62         mov     zeroones, #REP8_01
  63         bic     src, srcin, #15
  64         ands    tmp1, srcin, #15
  65         b.ne    L(misaligned)
  66         /* Calculate the number of full and partial words -1.  */
  67         sub     limit_wd, limit, #1     /* Limit != 0, so no underflow.  */
  68         lsr     limit_wd, limit_wd, #4  /* Convert to Qwords.  */
  69
  70         /* NUL detection works on the principle that (X - 1) & (~X) & 0x80
  71            (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
  72            can be done in parallel across the entire word.  */
  73         /* The inner loop deals with two Dwords at a time.  This has a
  74            slightly higher start-up cost, but we should win quite quickly,
  75            especially on cores with a high number of issue slots per
  76            cycle, as we get much better parallelism out of the operations.  */
  77
  78         /* Start of critial section -- keep to one 64Byte cache line.  */
  79
  80         ldp     data1, data2, [src], #16
  81 L(realigned):
  82         sub     tmp1, data1, zeroones
  83         orr     tmp2, data1, #REP8_7f
  84         sub     tmp3, data2, zeroones
  85         orr     tmp4, data2, #REP8_7f
  86         bic     has_nul1, tmp1, tmp2
  87         bic     has_nul2, tmp3, tmp4
  88         subs    limit_wd, limit_wd, #1
  89         orr     tmp1, has_nul1, has_nul2
  90         ccmp    tmp1, #0, #0, pl        /* NZCV = 0000  */
  91         b.eq    L(loop)
  92         /* End of critical section -- keep to one 64Byte cache line.  */
  93
  94         orr     tmp1, has_nul1, has_nul2
  95         cbz     tmp1, L(hit_limit)      /* No null in final Qword.  */
  96
  97         /* We know there's a null in the final Qword.  The easiest thing
  98            to do now is work out the length of the string and return
  99            MIN (len, limit).  */
 100
 101         sub     len, src, srcin
 102         cbz     has_nul1, L(nul_in_data2)
 103 #ifdef __AARCH64EB__
 104         mov     data2, data1
 105 #endif
 106         sub     len, len, #8
 107         mov     has_nul2, has_nul1
 108 L(nul_in_data2):
 109 #ifdef __AARCH64EB__
 110         /* For big-endian, carry propagation (if the final byte in the
 111            string is 0x01) means we cannot use has_nul directly.  The
 112            easiest way to get the correct byte is to byte-swap the data
 113            and calculate the syndrome a second time.  */
 114         rev     data2, data2
 115         sub     tmp1, data2, zeroones
 116         orr     tmp2, data2, #REP8_7f
 117         bic     has_nul2, tmp1, tmp2
 118 #endif
 119         sub     len, len, #8
 120         rev     has_nul2, has_nul2
 121         clz     pos, has_nul2
 122         add     len, len, pos, lsr #3           /* Bits to bytes.  */
 123         cmp     len, limit
 124         csel    len, len, limit, ls             /* Return the lower value.  */
 125         RET
 126
 127 L(loop):
 128         ldr     dataq, [src], #16
 129         uminv   datab2, datav.16b
 130         mov     tmp1, datav2.d[0]
 131         subs    limit_wd, limit_wd, #1
 132         ccmp    tmp1, #0, #4, pl        /* NZCV = 0000  */
 133         b.eq    L(loop_end)
 134         ldr     dataq, [src], #16
 135         uminv   datab2, datav.16b
 136         mov     tmp1, datav2.d[0]
 137         subs    limit_wd, limit_wd, #1
 138         ccmp    tmp1, #0, #4, pl        /* NZCV = 0000  */
 139         b.ne    L(loop)
 140 L(loop_end):
 141         /* End of critical section -- keep to one 64Byte cache line.  */
 142
 143         cbnz    tmp1, L(hit_limit)      /* No null in final Qword.  */
 144
 145         /* We know there's a null in the final Qword.  The easiest thing
 146            to do now is work out the length of the string and return
 147            MIN (len, limit).  */
 148
 149 #ifdef __AARCH64EB__
 150         rev64   datav.16b, datav.16b
 151 #endif
 152         /* Set te NULL byte as 0xff and the rest as 0x00, move the data into a
 153            pair of scalars and then compute the length from the earliest NULL
 154            byte.  */
 155
 156         cmeq    datav.16b, datav.16b, #0
 157         mov     data1, datav.d[0]
 158         mov     data2, datav.d[1]
 159         cmp     data1, 0
 160         csel    data1, data1, data2, ne
 161         sub     len, src, srcin
 162         sub     len, len, #16
 163         rev     data1, data1
 164         add     tmp2, len, 8
 165         clz     tmp1, data1
 166         csel    len, len, tmp2, ne
 167         add     len, len, tmp1, lsr 3
 168         cmp     len, limit
 169         csel    len, len, limit, ls             /* Return the lower value.  */
 170         RET
 171
 172 L(misaligned):
 173         /* Deal with a partial first word.
 174            We're doing two things in parallel here;
 175            1) Calculate the number of words (but avoiding overflow if
 176               limit is near ULONG_MAX) - to do this we need to work out
 177               limit + tmp1 - 1 as a 65-bit value before shifting it;
 178            2) Load and mask the initial data words - we force the bytes
 179               before the ones we are interested in to 0xff - this ensures
 180               early bytes will not hit any zero detection.  */
 181         sub     limit_wd, limit, #1
 182         neg     tmp4, tmp1
 183         cmp     tmp1, #8
 184
 185         and     tmp3, limit_wd, #15
 186         lsr     limit_wd, limit_wd, #4
 187         mov     tmp2, #~0
 188
 189         ldp     data1, data2, [src], #16
 190         lsl     tmp4, tmp4, #3          /* Bytes beyond alignment -> bits.  */
 191         add     tmp3, tmp3, tmp1
 192
 193 #ifdef __AARCH64EB__
 194         /* Big-endian.  Early bytes are at MSB.  */
 195         lsl     tmp2, tmp2, tmp4        /* Shift (tmp1 & 63).  */
 196 #else
 197         /* Little-endian.  Early bytes are at LSB.  */
 198         lsr     tmp2, tmp2, tmp4        /* Shift (tmp1 & 63).  */
 199 #endif
 200         add     limit_wd, limit_wd, tmp3, lsr #4
 201
 202         orr     data1, data1, tmp2
 203         orr     data2a, data2, tmp2
 204
 205         csinv   data1, data1, xzr, le
 206         csel    data2, data2, data2a, le
 207         b       L(realigned)
 208
 209 L(hit_limit):
 210         mov     len, limit
 211         RET
 212 END (__strnlen)
 213 libc_hidden_def (__strnlen)
 214 weak_alias (__strnlen, strnlen)
 215 libc_hidden_def (strnlen)