sysdeps/aarch64/strncmp.S

   1 /* Copyright (C) 2013-2019 Free Software Foundation, Inc.
   2
   3    This file is part of the GNU C Library.
   4
   5    The GNU C Library is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU Lesser General Public
   7    License as published by the Free Software Foundation; either
   8    version 2.1 of the License, or (at your option) any later version.
   9
  10    The GNU C Library is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    Lesser General Public License for more details.
  14
  15    You should have received a copy of the GNU Lesser General Public
  16    License along with the GNU C Library.  If not, see
  17    <https://www.gnu.org/licenses/>.  */
  18
  19 #include <sysdep.h>
  20
  21 /* Assumptions:
  22  *
  23  * ARMv8-a, AArch64
  24  */
  25
  26 #define REP8_01 0x0101010101010101
  27 #define REP8_7f 0x7f7f7f7f7f7f7f7f
  28 #define REP8_80 0x8080808080808080
  29
  30 /* Parameters and result.  */
  31 #define src1            x0
  32 #define src2            x1
  33 #define limit           x2
  34 #define result          x0
  35
  36 /* Internal variables.  */
  37 #define data1           x3
  38 #define data1w          w3
  39 #define data2           x4
  40 #define data2w          w4
  41 #define has_nul         x5
  42 #define diff            x6
  43 #define syndrome        x7
  44 #define tmp1            x8
  45 #define tmp2            x9
  46 #define tmp3            x10
  47 #define zeroones        x11
  48 #define pos             x12
  49 #define limit_wd        x13
  50 #define mask            x14
  51 #define endloop         x15
  52 #define count           mask
  53
  54 ENTRY_ALIGN_AND_PAD (strncmp, 6, 7)
  55         DELOUSE (0)
  56         DELOUSE (1)
  57         DELOUSE (2)
  58         cbz     limit, L(ret0)
  59         eor     tmp1, src1, src2
  60         mov     zeroones, #REP8_01
  61         tst     tmp1, #7
  62         and     count, src1, #7
  63         b.ne    L(misaligned8)
  64         cbnz    count, L(mutual_align)
  65         /* Calculate the number of full and partial words -1.  */
  66         sub     limit_wd, limit, #1     /* limit != 0, so no underflow.  */
  67         lsr     limit_wd, limit_wd, #3  /* Convert to Dwords.  */
  68
  69         /* NUL detection works on the principle that (X - 1) & (~X) & 0x80
  70            (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
  71            can be done in parallel across the entire word.  */
  72         /* Start of performance-critical section  -- one 64B cache line.  */
  73 L(loop_aligned):
  74         ldr     data1, [src1], #8
  75         ldr     data2, [src2], #8
  76 L(start_realigned):
  77         subs    limit_wd, limit_wd, #1
  78         sub     tmp1, data1, zeroones
  79         orr     tmp2, data1, #REP8_7f
  80         eor     diff, data1, data2      /* Non-zero if differences found.  */
  81         csinv   endloop, diff, xzr, pl  /* Last Dword or differences.  */
  82         bics    has_nul, tmp1, tmp2     /* Non-zero if NUL terminator.  */
  83         ccmp    endloop, #0, #0, eq
  84         b.eq    L(loop_aligned)
  85         /* End of performance-critical section  -- one 64B cache line.  */
  86
  87         /* Not reached the limit, must have found the end or a diff.  */
  88         tbz     limit_wd, #63, L(not_limit)
  89
  90         /* Limit % 8 == 0 => all bytes significant.  */
  91         ands    limit, limit, #7
  92         b.eq    L(not_limit)
  93
  94         lsl     limit, limit, #3        /* Bits -> bytes.  */
  95         mov     mask, #~0
  96 #ifdef __AARCH64EB__
  97         lsr     mask, mask, limit
  98 #else
  99         lsl     mask, mask, limit
 100 #endif
 101         bic     data1, data1, mask
 102         bic     data2, data2, mask
 103
 104         /* Make sure that the NUL byte is marked in the syndrome.  */
 105         orr     has_nul, has_nul, mask
 106
 107 L(not_limit):
 108         orr     syndrome, diff, has_nul
 109
 110 #ifndef __AARCH64EB__
 111         rev     syndrome, syndrome
 112         rev     data1, data1
 113         /* The MS-non-zero bit of the syndrome marks either the first bit
 114            that is different, or the top bit of the first zero byte.
 115            Shifting left now will bring the critical information into the
 116            top bits.  */
 117         clz     pos, syndrome
 118         rev     data2, data2
 119         lsl     data1, data1, pos
 120         lsl     data2, data2, pos
 121         /* But we need to zero-extend (char is unsigned) the value and then
 122            perform a signed 32-bit subtraction.  */
 123         lsr     data1, data1, #56
 124         sub     result, data1, data2, lsr #56
 125         RET
 126 #else
 127         /* For big-endian we cannot use the trick with the syndrome value
 128            as carry-propagation can corrupt the upper bits if the trailing
 129            bytes in the string contain 0x01.  */
 130         /* However, if there is no NUL byte in the dword, we can generate
 131            the result directly.  We can't just subtract the bytes as the
 132            MSB might be significant.  */
 133         cbnz    has_nul, 1f
 134         cmp     data1, data2
 135         cset    result, ne
 136         cneg    result, result, lo
 137         RET
 138 1:
 139         /* Re-compute the NUL-byte detection, using a byte-reversed value.  */
 140         rev     tmp3, data1
 141         sub     tmp1, tmp3, zeroones
 142         orr     tmp2, tmp3, #REP8_7f
 143         bic     has_nul, tmp1, tmp2
 144         rev     has_nul, has_nul
 145         orr     syndrome, diff, has_nul
 146         clz     pos, syndrome
 147         /* The MS-non-zero bit of the syndrome marks either the first bit
 148            that is different, or the top bit of the first zero byte.
 149            Shifting left now will bring the critical information into the
 150            top bits.  */
 151         lsl     data1, data1, pos
 152         lsl     data2, data2, pos
 153         /* But we need to zero-extend (char is unsigned) the value and then
 154            perform a signed 32-bit subtraction.  */
 155         lsr     data1, data1, #56
 156         sub     result, data1, data2, lsr #56
 157         RET
 158 #endif
 159
 160 L(mutual_align):
 161         /* Sources are mutually aligned, but are not currently at an
 162            alignment boundary.  Round down the addresses and then mask off
 163            the bytes that precede the start point.
 164            We also need to adjust the limit calculations, but without
 165            overflowing if the limit is near ULONG_MAX.  */
 166         bic     src1, src1, #7
 167         bic     src2, src2, #7
 168         ldr     data1, [src1], #8
 169         neg     tmp3, count, lsl #3     /* 64 - bits(bytes beyond align). */
 170         ldr     data2, [src2], #8
 171         mov     tmp2, #~0
 172         sub     limit_wd, limit, #1     /* limit != 0, so no underflow.  */
 173 #ifdef __AARCH64EB__
 174         /* Big-endian.  Early bytes are at MSB.  */
 175         lsl     tmp2, tmp2, tmp3        /* Shift (count & 63).  */
 176 #else
 177         /* Little-endian.  Early bytes are at LSB.  */
 178         lsr     tmp2, tmp2, tmp3        /* Shift (count & 63).  */
 179 #endif
 180         and     tmp3, limit_wd, #7
 181         lsr     limit_wd, limit_wd, #3
 182         /* Adjust the limit. Only low 3 bits used, so overflow irrelevant.  */
 183         add     limit, limit, count
 184         add     tmp3, tmp3, count
 185         orr     data1, data1, tmp2
 186         orr     data2, data2, tmp2
 187         add     limit_wd, limit_wd, tmp3, lsr #3
 188         b       L(start_realigned)
 189
 190         .p2align 6
 191         /* Don't bother with dwords for up to 16 bytes.  */
 192 L(misaligned8):
 193         cmp     limit, #16
 194         b.hs    L(try_misaligned_words)
 195
 196 L(byte_loop):
 197         /* Perhaps we can do better than this.  */
 198         ldrb    data1w, [src1], #1
 199         ldrb    data2w, [src2], #1
 200         subs    limit, limit, #1
 201         ccmp    data1w, #1, #0, hi      /* NZCV = 0b0000.  */
 202         ccmp    data1w, data2w, #0, cs  /* NZCV = 0b0000.  */
 203         b.eq    L(byte_loop)
 204 L(done):
 205         sub     result, data1, data2
 206         RET
 207
 208         /* Align the SRC1 to a dword by doing a bytewise compare and then do
 209            the dword loop.  */
 210 L(try_misaligned_words):
 211         lsr     limit_wd, limit, #3
 212         cbz     count, L(do_misaligned)
 213
 214         neg     count, count
 215         and     count, count, #7
 216         sub     limit, limit, count
 217         lsr     limit_wd, limit, #3
 218
 219 L(page_end_loop):
 220         ldrb    data1w, [src1], #1
 221         ldrb    data2w, [src2], #1
 222         cmp     data1w, #1
 223         ccmp    data1w, data2w, #0, cs  /* NZCV = 0b0000.  */
 224         b.ne    L(done)
 225         subs    count, count, #1
 226         b.hi    L(page_end_loop)
 227
 228 L(do_misaligned):
 229         /* Prepare ourselves for the next page crossing.  Unlike the aligned
 230            loop, we fetch 1 less dword because we risk crossing bounds on
 231            SRC2.  */
 232         mov     count, #8
 233         subs    limit_wd, limit_wd, #1
 234         b.lo    L(done_loop)
 235 L(loop_misaligned):
 236         and     tmp2, src2, #0xff8
 237         eor     tmp2, tmp2, #0xff8
 238         cbz     tmp2, L(page_end_loop)
 239
 240         ldr     data1, [src1], #8
 241         ldr     data2, [src2], #8
 242         sub     tmp1, data1, zeroones
 243         orr     tmp2, data1, #REP8_7f
 244         eor     diff, data1, data2      /* Non-zero if differences found.  */
 245         bics    has_nul, tmp1, tmp2     /* Non-zero if NUL terminator.  */
 246         ccmp    diff, #0, #0, eq
 247         b.ne    L(not_limit)
 248         subs    limit_wd, limit_wd, #1
 249         b.pl    L(loop_misaligned)
 250
 251 L(done_loop):
 252         /* We found a difference or a NULL before the limit was reached.  */
 253         and     limit, limit, #7
 254         cbz     limit, L(not_limit)
 255         /* Read the last word.  */
 256         sub     src1, src1, 8
 257         sub     src2, src2, 8
 258         ldr     data1, [src1, limit]
 259         ldr     data2, [src2, limit]
 260         sub     tmp1, data1, zeroones
 261         orr     tmp2, data1, #REP8_7f
 262         eor     diff, data1, data2      /* Non-zero if differences found.  */
 263         bics    has_nul, tmp1, tmp2     /* Non-zero if NUL terminator.  */
 264         ccmp    diff, #0, #0, eq
 265         b.ne    L(not_limit)
 266
 267 L(ret0):
 268         mov     result, #0
 269         RET
 270
 271 END (strncmp)
 272 libc_hidden_builtin_def (strncmp)