sysdeps/aarch64/strncmp.S

   1 /* Copyright (C) 2013-2017 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    <http://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
  53 ENTRY_ALIGN_AND_PAD (strncmp, 6, 7)
  54         DELOUSE (0)
  55         DELOUSE (1)
  56         DELOUSE (2)
  57         cbz     limit, L(ret0)
  58         eor     tmp1, src1, src2
  59         mov     zeroones, #REP8_01
  60         tst     tmp1, #7
  61         b.ne    L(misaligned8)
  62         ands    tmp1, src1, #7
  63         b.ne    L(mutual_align)
  64         /* Calculate the number of full and partial words -1.  */
  65         sub     limit_wd, limit, #1     /* limit != 0, so no underflow.  */
  66         lsr     limit_wd, limit_wd, #3  /* Convert to Dwords.  */
  67
  68         /* NUL detection works on the principle that (X - 1) & (~X) & 0x80
  69            (=> (X - 1) & ~(X | 0x7f)) is non-zero iff a byte is zero, and
  70            can be done in parallel across the entire word.  */
  71         /* Start of performance-critical section  -- one 64B cache line.  */
  72 L(loop_aligned):
  73         ldr     data1, [src1], #8
  74         ldr     data2, [src2], #8
  75 L(start_realigned):
  76         subs    limit_wd, limit_wd, #1
  77         sub     tmp1, data1, zeroones
  78         orr     tmp2, data1, #REP8_7f
  79         eor     diff, data1, data2      /* Non-zero if differences found.  */
  80         csinv   endloop, diff, xzr, pl  /* Last Dword or differences.  */
  81         bics    has_nul, tmp1, tmp2     /* Non-zero if NUL terminator.  */
  82         ccmp    endloop, #0, #0, eq
  83         b.eq    L(loop_aligned)
  84         /* End of performance-critical section  -- one 64B cache line.  */
  85
  86         /* Not reached the limit, must have found the end or a diff.  */
  87         tbz     limit_wd, #63, L(not_limit)
  88
  89         /* Limit % 8 == 0 => all bytes significant.  */
  90         ands    limit, limit, #7
  91         b.eq    L(not_limit)
  92
  93         lsl     limit, limit, #3        /* Bits -> bytes.  */
  94         mov     mask, #~0
  95 #ifdef __AARCH64EB__
  96         lsr     mask, mask, limit
  97 #else
  98         lsl     mask, mask, limit
  99 #endif
 100         bic     data1, data1, mask
 101         bic     data2, data2, mask
 102
 103         /* Make sure that the NUL byte is marked in the syndrome.  */
 104         orr     has_nul, has_nul, mask
 105
 106 L(not_limit):
 107         orr     syndrome, diff, has_nul
 108
 109 #ifndef __AARCH64EB__
 110         rev     syndrome, syndrome
 111         rev     data1, data1
 112         /* The MS-non-zero bit of the syndrome marks either the first bit
 113            that is different, or the top bit of the first zero byte.
 114            Shifting left now will bring the critical information into the
 115            top bits.  */
 116         clz     pos, syndrome
 117         rev     data2, data2
 118         lsl     data1, data1, pos
 119         lsl     data2, data2, pos
 120         /* But we need to zero-extend (char is unsigned) the value and then
 121            perform a signed 32-bit subtraction.  */
 122         lsr     data1, data1, #56
 123         sub     result, data1, data2, lsr #56
 124         RET
 125 #else
 126         /* For big-endian we cannot use the trick with the syndrome value
 127            as carry-propagation can corrupt the upper bits if the trailing
 128            bytes in the string contain 0x01.  */
 129         /* However, if there is no NUL byte in the dword, we can generate
 130            the result directly.  We can't just subtract the bytes as the
 131            MSB might be significant.  */
 132         cbnz    has_nul, 1f
 133         cmp     data1, data2
 134         cset    result, ne
 135         cneg    result, result, lo
 136         RET
 137 1:
 138         /* Re-compute the NUL-byte detection, using a byte-reversed value.  */
 139         rev     tmp3, data1
 140         sub     tmp1, tmp3, zeroones
 141         orr     tmp2, tmp3, #REP8_7f
 142         bic     has_nul, tmp1, tmp2
 143         rev     has_nul, has_nul
 144         orr     syndrome, diff, has_nul
 145         clz     pos, syndrome
 146         /* The MS-non-zero bit of the syndrome marks either the first bit
 147            that is different, or the top bit of the first zero byte.
 148            Shifting left now will bring the critical information into the
 149            top bits.  */
 150         lsl     data1, data1, pos
 151         lsl     data2, data2, pos
 152         /* But we need to zero-extend (char is unsigned) the value and then
 153            perform a signed 32-bit subtraction.  */
 154         lsr     data1, data1, #56
 155         sub     result, data1, data2, lsr #56
 156         RET
 157 #endif
 158
 159 L(mutual_align):
 160         /* Sources are mutually aligned, but are not currently at an
 161            alignment boundary.  Round down the addresses and then mask off
 162            the bytes that precede the start point.
 163            We also need to adjust the limit calculations, but without
 164            overflowing if the limit is near ULONG_MAX.  */
 165         bic     src1, src1, #7
 166         bic     src2, src2, #7
 167         ldr     data1, [src1], #8
 168         neg     tmp3, tmp1, lsl #3      /* 64 - bits(bytes beyond align). */
 169         ldr     data2, [src2], #8
 170         mov     tmp2, #~0
 171         sub     limit_wd, limit, #1     /* limit != 0, so no underflow.  */
 172 #ifdef __AARCH64EB__
 173         /* Big-endian.  Early bytes are at MSB.  */
 174         lsl     tmp2, tmp2, tmp3        /* Shift (tmp1 & 63).  */
 175 #else
 176         /* Little-endian.  Early bytes are at LSB.  */
 177         lsr     tmp2, tmp2, tmp3        /* Shift (tmp1 & 63).  */
 178 #endif
 179         and     tmp3, limit_wd, #7
 180         lsr     limit_wd, limit_wd, #3
 181         /* Adjust the limit. Only low 3 bits used, so overflow irrelevant.  */
 182         add     limit, limit, tmp1
 183         add     tmp3, tmp3, tmp1
 184         orr     data1, data1, tmp2
 185         orr     data2, data2, tmp2
 186         add     limit_wd, limit_wd, tmp3, lsr #3
 187         b       L(start_realigned)
 188
 189 L(ret0):
 190         mov     result, #0
 191         RET
 192
 193         .p2align 6
 194 L(misaligned8):
 195         sub     limit, limit, #1
 196 1:
 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, cs      /* NZCV = 0b0000.  */
 202         ccmp    data1w, data2w, #0, cs  /* NZCV = 0b0000.  */
 203         b.eq    1b
 204         sub     result, data1, data2
 205         RET
 206 END (strncmp)
 207 libc_hidden_builtin_def (strncmp)