sysdeps/aarch64/strnlen.S

   1 /* strnlen - calculate the length of a string with limit.
   2
   3    Copyright (C) 2013-2017 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  */
  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 REP8_01 0x0101010101010101
  49 #define REP8_7f 0x7f7f7f7f7f7f7f7f
  50 #define REP8_80 0x8080808080808080
  51
  52 ENTRY_ALIGN_AND_PAD (__strnlen, 6, 9)
  53         DELOUSE (0)
  54         DELOUSE (1)
  55         DELOUSE (2)
  56         cbz     limit, L(hit_limit)
  57         mov     zeroones, #REP8_01
  58         bic     src, srcin, #15
  59         ands    tmp1, srcin, #15
  60         b.ne    L(misaligned)
  61         /* Calculate the number of full and partial words -1.  */
  62         sub     limit_wd, limit, #1     /* Limit != 0, so no underflow.  */
  63         lsr     limit_wd, limit_wd, #4  /* Convert to Qwords.  */
  64
  65         /* NUL detection works on the principle that (X - 1) & (~X) & 0x80
  66            (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
  67            can be done in parallel across the entire word.  */
  68         /* The inner loop deals with two Dwords at a time.  This has a
  69            slightly higher start-up cost, but we should win quite quickly,
  70            especially on cores with a high number of issue slots per
  71            cycle, as we get much better parallelism out of the operations.  */
  72
  73         /* Start of critial section -- keep to one 64Byte cache line.  */
  74 L(loop):
  75         ldp     data1, data2, [src], #16
  76 L(realigned):
  77         sub     tmp1, data1, zeroones
  78         orr     tmp2, data1, #REP8_7f
  79         sub     tmp3, data2, zeroones
  80         orr     tmp4, data2, #REP8_7f
  81         bic     has_nul1, tmp1, tmp2
  82         bic     has_nul2, tmp3, tmp4
  83         subs    limit_wd, limit_wd, #1
  84         orr     tmp1, has_nul1, has_nul2
  85         ccmp    tmp1, #0, #0, pl        /* NZCV = 0000  */
  86         b.eq    L(loop)
  87         /* End of critical section -- keep to one 64Byte cache line.  */
  88
  89         orr     tmp1, has_nul1, has_nul2
  90         cbz     tmp1, L(hit_limit)      /* No null in final Qword.  */
  91
  92         /* We know there's a null in the final Qword.  The easiest thing
  93            to do now is work out the length of the string and return
  94            MIN (len, limit).  */
  95
  96         sub     len, src, srcin
  97         cbz     has_nul1, L(nul_in_data2)
  98 #ifdef __AARCH64EB__
  99         mov     data2, data1
 100 #endif
 101         sub     len, len, #8
 102         mov     has_nul2, has_nul1
 103 L(nul_in_data2):
 104 #ifdef __AARCH64EB__
 105         /* For big-endian, carry propagation (if the final byte in the
 106            string is 0x01) means we cannot use has_nul directly.  The
 107            easiest way to get the correct byte is to byte-swap the data
 108            and calculate the syndrome a second time.  */
 109         rev     data2, data2
 110         sub     tmp1, data2, zeroones
 111         orr     tmp2, data2, #REP8_7f
 112         bic     has_nul2, tmp1, tmp2
 113 #endif
 114         sub     len, len, #8
 115         rev     has_nul2, has_nul2
 116         clz     pos, has_nul2
 117         add     len, len, pos, lsr #3           /* Bits to bytes.  */
 118         cmp     len, limit
 119         csel    len, len, limit, ls             /* Return the lower value.  */
 120         RET
 121
 122 L(misaligned):
 123         /* Deal with a partial first word.
 124            We're doing two things in parallel here;
 125            1) Calculate the number of words (but avoiding overflow if
 126               limit is near ULONG_MAX) - to do this we need to work out
 127               limit + tmp1 - 1 as a 65-bit value before shifting it;
 128            2) Load and mask the initial data words - we force the bytes
 129               before the ones we are interested in to 0xff - this ensures
 130               early bytes will not hit any zero detection.  */
 131         sub     limit_wd, limit, #1
 132         neg     tmp4, tmp1
 133         cmp     tmp1, #8
 134
 135         and     tmp3, limit_wd, #15
 136         lsr     limit_wd, limit_wd, #4
 137         mov     tmp2, #~0
 138
 139         ldp     data1, data2, [src], #16
 140         lsl     tmp4, tmp4, #3          /* Bytes beyond alignment -> bits.  */
 141         add     tmp3, tmp3, tmp1
 142
 143 #ifdef __AARCH64EB__
 144         /* Big-endian.  Early bytes are at MSB.  */
 145         lsl     tmp2, tmp2, tmp4        /* Shift (tmp1 & 63).  */
 146 #else
 147         /* Little-endian.  Early bytes are at LSB.  */
 148         lsr     tmp2, tmp2, tmp4        /* Shift (tmp1 & 63).  */
 149 #endif
 150         add     limit_wd, limit_wd, tmp3, lsr #4
 151
 152         orr     data1, data1, tmp2
 153         orr     data2a, data2, tmp2
 154
 155         csinv   data1, data1, xzr, le
 156         csel    data2, data2, data2a, le
 157         b       L(realigned)
 158
 159 L(hit_limit):
 160         mov     len, limit
 161         RET
 162 END (__strnlen)
 163 libc_hidden_def (__strnlen)
 164 weak_alias (__strnlen, strnlen)
 165 libc_hidden_def (strnlen)