sysdeps/x86_64/multiarch/strlen-sse2.S

   1 /* strlen optimized with SSE2.
   2    Copyright (C) 2017-2023 Free Software Foundation, Inc.
   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 <isa-level.h>
  20
  21 /* ISA level >= 2 for both strlen and wcslen.  wcslen uses `pminud`
  22    which is SSE4.1. strlen doesn't have an ISA level == 2
  23    implementation so the SSE2 implementation must be built with ISA
  24    level == 2.  */
  25 # if ISA_SHOULD_BUILD (2)
  26
  27 # include <sysdep.h>
  28
  29 # ifndef STRLEN
  30 #  define STRLEN        __strlen_sse2
  31 # endif
  32
  33 # ifdef AS_WCSLEN
  34 #  define PMINU         pminud
  35 #  define PCMPEQ                pcmpeqd
  36 #  define SHIFT_RETURN  shrq $2, %rax
  37 # else
  38 #  define PMINU         pminub
  39 #  define PCMPEQ                pcmpeqb
  40 #  define SHIFT_RETURN
  41 # endif
  42
  43 # ifndef SECTION
  44 #  define SECTION(p)    p
  45 # endif
  46
  47 /* Long lived register in strlen(s), strnlen(s, n) are:
  48
  49         %xmm3 - zero
  50         %rdi   - s
  51         %r10  (s+n) & (~(64-1))
  52         %r11   s+n
  53 */
  54
  55
  56         .section SECTION(.text),"ax",@progbits
  57 ENTRY(STRLEN)
  58
  59 /* Test 64 bytes from %rax for zero. Save result as bitmask in %rdx.  */
  60 # define FIND_ZERO      \
  61         PCMPEQ  (%rax), %xmm0;  \
  62         PCMPEQ  16(%rax), %xmm1;        \
  63         PCMPEQ  32(%rax), %xmm2;        \
  64         PCMPEQ  48(%rax), %xmm3;        \
  65         pmovmskb        %xmm0, %esi;    \
  66         pmovmskb        %xmm1, %edx;    \
  67         pmovmskb        %xmm2, %r8d;    \
  68         pmovmskb        %xmm3, %ecx;    \
  69         salq    $16, %rdx;      \
  70         salq    $16, %rcx;      \
  71         orq     %rsi, %rdx;     \
  72         orq     %r8, %rcx;      \
  73         salq    $32, %rcx;      \
  74         orq     %rcx, %rdx;
  75
  76 # ifdef AS_STRNLEN
  77 /* Do not read anything when n==0.  */
  78         test    %RSI_LP, %RSI_LP
  79         jne     L(n_nonzero)
  80         xor     %rax, %rax
  81         ret
  82 L(n_nonzero):
  83 #  ifdef AS_WCSLEN
  84 /* Check for overflow from maxlen * sizeof(wchar_t). If it would
  85    overflow the only way this program doesn't have undefined behavior
  86    is if there is a null terminator in valid memory so wcslen will
  87    suffice.  */
  88         mov     %RSI_LP, %R10_LP
  89         sar     $62, %R10_LP
  90         jnz     OVERFLOW_STRLEN
  91         sal     $2, %RSI_LP
  92 #  endif
  93
  94 /* Initialize long lived registers.  */
  95         add     %RDI_LP, %RSI_LP
  96         mov     %RSI_LP, %R10_LP
  97         and     $-64, %R10_LP
  98         mov     %RSI_LP, %R11_LP
  99 # endif
 100
 101         pxor    %xmm0, %xmm0
 102         pxor    %xmm1, %xmm1
 103         pxor    %xmm2, %xmm2
 104         pxor    %xmm3, %xmm3
 105         movq    %rdi, %rax
 106         movq    %rdi, %rcx
 107         andq    $4095, %rcx
 108 /* Offsets 4032-4047 will be aligned into 4032 thus fit into page.  */
 109         cmpq    $4047, %rcx
 110 /* We cannot unify this branching as it would be ~6 cycles slower.  */
 111         ja      L(cross_page)
 112
 113 # ifdef AS_STRNLEN
 114 /* Test if end is among first 64 bytes.  */
 115 #  define STRNLEN_PROLOG        \
 116         mov     %r11, %rsi;     \
 117         subq    %rax, %rsi;     \
 118         andq    $-64, %rax;     \
 119         testq   $-64, %rsi;     \
 120         je      L(strnlen_ret)
 121 # else
 122 #  define STRNLEN_PROLOG  andq $-64, %rax;
 123 # endif
 124
 125 /* Ignore bits in mask that come before start of string.  */
 126 # define PROLOG(lab)    \
 127         movq    %rdi, %rcx;     \
 128         xorq    %rax, %rcx;     \
 129         STRNLEN_PROLOG; \
 130         sarq    %cl, %rdx;      \
 131         test    %rdx, %rdx;     \
 132         je      L(lab); \
 133         bsfq    %rdx, %rax;     \
 134         SHIFT_RETURN;           \
 135         ret
 136
 137 # ifdef AS_STRNLEN
 138         andq    $-16, %rax
 139         FIND_ZERO
 140 # else
 141         /* Test first 16 bytes unaligned.  */
 142         movdqu  (%rax), %xmm4
 143         PCMPEQ  %xmm0, %xmm4
 144         pmovmskb        %xmm4, %edx
 145         test    %edx, %edx
 146         je      L(next48_bytes)
 147         bsf     %edx, %eax /* If eax is zeroed 16bit bsf can be used.  */
 148         SHIFT_RETURN
 149         ret
 150
 151 L(next48_bytes):
 152 /* Same as FIND_ZERO except we do not check first 16 bytes.  */
 153         andq    $-16, %rax
 154         PCMPEQ 16(%rax), %xmm1
 155         PCMPEQ 32(%rax), %xmm2
 156         PCMPEQ 48(%rax), %xmm3
 157         pmovmskb        %xmm1, %edx
 158         pmovmskb        %xmm2, %r8d
 159         pmovmskb        %xmm3, %ecx
 160         salq    $16, %rdx
 161         salq    $16, %rcx
 162         orq     %r8, %rcx
 163         salq    $32, %rcx
 164         orq     %rcx, %rdx
 165 # endif
 166
 167         /* When no zero byte is found xmm1-3 are zero so we do not have to
 168            zero them.  */
 169         PROLOG(loop)
 170
 171         .p2align 4
 172 L(cross_page):
 173         andq    $-64, %rax
 174         FIND_ZERO
 175         PROLOG(loop_init)
 176
 177 # ifdef AS_STRNLEN
 178 /* We must do this check to correctly handle strnlen (s, -1).  */
 179 L(strnlen_ret):
 180         bts     %rsi, %rdx
 181         sarq    %cl, %rdx
 182         test    %rdx, %rdx
 183         je      L(loop_init)
 184         bsfq    %rdx, %rax
 185         SHIFT_RETURN
 186         ret
 187 # endif
 188         .p2align 4
 189 L(loop_init):
 190         pxor    %xmm1, %xmm1
 191         pxor    %xmm2, %xmm2
 192         pxor    %xmm3, %xmm3
 193 # ifdef AS_STRNLEN
 194         .p2align 4
 195 L(loop):
 196
 197         addq    $64, %rax
 198         cmpq    %rax, %r10
 199         je      L(exit_end)
 200
 201         movdqa  (%rax), %xmm0
 202         PMINU   16(%rax), %xmm0
 203         PMINU   32(%rax), %xmm0
 204         PMINU   48(%rax), %xmm0
 205         PCMPEQ  %xmm3, %xmm0
 206         pmovmskb        %xmm0, %edx
 207         testl   %edx, %edx
 208         jne     L(exit)
 209         jmp     L(loop)
 210
 211         .p2align 4
 212 L(exit_end):
 213         cmp     %rax, %r11
 214         je      L(first) /* Do not read when end is at page boundary.  */
 215         pxor    %xmm0, %xmm0
 216         FIND_ZERO
 217
 218 L(first):
 219         bts     %r11, %rdx
 220         bsfq    %rdx, %rdx
 221         addq    %rdx, %rax
 222         subq    %rdi, %rax
 223         SHIFT_RETURN
 224         ret
 225
 226         .p2align 4
 227 L(exit):
 228         pxor    %xmm0, %xmm0
 229         FIND_ZERO
 230
 231         bsfq    %rdx, %rdx
 232         addq    %rdx, %rax
 233         subq    %rdi, %rax
 234         SHIFT_RETURN
 235         ret
 236
 237 # else
 238
 239         /* Main loop.  Unrolled twice to improve L2 cache performance on core2.  */
 240         .p2align 4
 241 L(loop):
 242
 243         movdqa  64(%rax), %xmm0
 244         PMINU   80(%rax), %xmm0
 245         PMINU   96(%rax), %xmm0
 246         PMINU   112(%rax), %xmm0
 247         PCMPEQ  %xmm3, %xmm0
 248         pmovmskb        %xmm0, %edx
 249         testl   %edx, %edx
 250         jne     L(exit64)
 251
 252         subq    $-128, %rax
 253
 254         movdqa  (%rax), %xmm0
 255         PMINU   16(%rax), %xmm0
 256         PMINU   32(%rax), %xmm0
 257         PMINU   48(%rax), %xmm0
 258         PCMPEQ  %xmm3, %xmm0
 259         pmovmskb        %xmm0, %edx
 260         testl   %edx, %edx
 261         jne     L(exit0)
 262         jmp     L(loop)
 263
 264         .p2align 4
 265 L(exit64):
 266         addq    $64, %rax
 267 L(exit0):
 268         pxor    %xmm0, %xmm0
 269         FIND_ZERO
 270
 271         bsfq    %rdx, %rdx
 272         addq    %rdx, %rax
 273         subq    %rdi, %rax
 274         SHIFT_RETURN
 275         ret
 276
 277 # endif
 278
 279 END(STRLEN)
 280 #endif