/* strrchr/wcsrchr optimized with AVX2.
   Copyright (C) 2017-2022 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, see
   <https://www.gnu.org/licenses/>.  */

#include <isa-level.h>

#if ISA_SHOULD_BUILD (3)

# include <sysdep.h>

# ifndef STRRCHR
#  define STRRCHR	__strrchr_avx2
# endif

# ifdef USE_AS_WCSRCHR
#  define VPBROADCAST	vpbroadcastd
#  define VPCMPEQ	vpcmpeqd
#  define VPMIN	vpminud
#  define CHAR_SIZE	4
# else
#  define VPBROADCAST	vpbroadcastb
#  define VPCMPEQ	vpcmpeqb
#  define VPMIN	vpminub
#  define CHAR_SIZE	1
# endif

# ifndef VZEROUPPER
#  define VZEROUPPER	vzeroupper
# endif

# ifndef SECTION
#  define SECTION(p)	p##.avx
# endif

# define VEC_SIZE	32
# define PAGE_SIZE	4096

	.section SECTION(.text), "ax", @progbits
ENTRY(STRRCHR)
	vmovd	%esi, %xmm7
	movl	%edi, %eax
	/* Broadcast CHAR to YMM4.  */
	VPBROADCAST %xmm7, %ymm7
	vpxor	%xmm0, %xmm0, %xmm0

	/* Shift here instead of `andl` to save code size (saves a fetch
	   block).  */
	sall	$20, %eax
	cmpl	$((PAGE_SIZE - VEC_SIZE) << 20), %eax
	ja	L(cross_page)

L(page_cross_continue):
	vmovdqu	(%rdi), %ymm1
	/* Check end of string match.  */
	VPCMPEQ	%ymm1, %ymm0, %ymm6
	vpmovmskb %ymm6, %ecx
	testl	%ecx, %ecx
	jz	L(aligned_more)

	/* Only check match with search CHAR if needed.  */
	VPCMPEQ	%ymm1, %ymm7, %ymm1
	vpmovmskb %ymm1, %eax
	/* Check if match before first zero.  */
	blsmskl	%ecx, %ecx
	andl	%ecx, %eax
	jz	L(ret0)
	bsrl	%eax, %eax
	addq	%rdi, %rax
	/* We are off by 3 for wcsrchr if search CHAR is non-zero. If
	   search CHAR is zero we are correct. Either way `andq
	   -CHAR_SIZE, %rax` gets the correct result.  */
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
L(ret0):
L(return_vzeroupper):
	ZERO_UPPER_VEC_REGISTERS_RETURN

	/* Returns for first vec x1/x2 have hard coded backward search
	   path for earlier matches.  */
	.p2align 4,, 10
L(first_vec_x1):
	VPCMPEQ	%ymm2, %ymm7, %ymm6
	vpmovmskb %ymm6, %eax
	blsmskl	%ecx, %ecx
	andl	%ecx, %eax
	jnz	L(first_vec_x1_return)

	.p2align 4,, 4
L(first_vec_x0_test):
	VPCMPEQ	%ymm1, %ymm7, %ymm6
	vpmovmskb %ymm6, %eax
	testl	%eax, %eax
	jz	L(ret1)
	bsrl	%eax, %eax
	addq	%r8, %rax
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
L(ret1):
	VZEROUPPER_RETURN

	.p2align 4,, 10
L(first_vec_x0_x1_test):
	VPCMPEQ	%ymm2, %ymm7, %ymm6
	vpmovmskb %ymm6, %eax
	/* Check ymm2 for search CHAR match. If no match then check ymm1
	   before returning.  */
	testl	%eax, %eax
	jz	L(first_vec_x0_test)
	.p2align 4,, 4
L(first_vec_x1_return):
	bsrl	%eax, %eax
	leaq	1(%rdi, %rax), %rax
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
	VZEROUPPER_RETURN


	.p2align 4,, 10
L(first_vec_x2):
	VPCMPEQ	%ymm3, %ymm7, %ymm6
	vpmovmskb %ymm6, %eax
	blsmskl	%ecx, %ecx
	/* If no in-range search CHAR match in ymm3 then need to check
	   ymm1/ymm2 for an earlier match (we delay checking search
	   CHAR matches until needed).  */
	andl	%ecx, %eax
	jz	L(first_vec_x0_x1_test)
	bsrl	%eax, %eax
	leaq	(VEC_SIZE + 1)(%rdi, %rax), %rax
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
	VZEROUPPER_RETURN


	.p2align 4
L(aligned_more):
	/* Save original pointer if match was in VEC 0.  */
	movq	%rdi, %r8

	/* Align src.  */
	orq	$(VEC_SIZE - 1), %rdi
	vmovdqu	1(%rdi), %ymm2
	VPCMPEQ	%ymm2, %ymm0, %ymm6
	vpmovmskb %ymm6, %ecx
	testl	%ecx, %ecx
	jnz	L(first_vec_x1)

	vmovdqu	(VEC_SIZE + 1)(%rdi), %ymm3
	VPCMPEQ	%ymm3, %ymm0, %ymm6
	vpmovmskb %ymm6, %ecx
	testl	%ecx, %ecx
	jnz	L(first_vec_x2)

	/* Save pointer again before realigning.  */
	movq	%rdi, %rsi
	addq	$(VEC_SIZE + 1), %rdi
	andq	$-(VEC_SIZE * 2), %rdi
	.p2align 4
L(first_aligned_loop):
	/* Do 2x VEC at a time. Any more and the cost of finding the
	   match outweights loop benefit.  */
	vmovdqa	(VEC_SIZE * 0)(%rdi), %ymm4
	vmovdqa	(VEC_SIZE * 1)(%rdi), %ymm5

	VPCMPEQ	%ymm4, %ymm7, %ymm6
	VPMIN	%ymm4, %ymm5, %ymm8
	VPCMPEQ	%ymm5, %ymm7, %ymm10
	vpor	%ymm6, %ymm10, %ymm5
	VPCMPEQ	%ymm8, %ymm0, %ymm8
	vpor	%ymm5, %ymm8, %ymm9

	vpmovmskb %ymm9, %eax
	addq	$(VEC_SIZE * 2), %rdi
	/* No zero or search CHAR.  */
	testl	%eax, %eax
	jz	L(first_aligned_loop)

	/* If no zero CHAR then go to second loop (this allows us to
	   throw away all prior work).  */
	vpmovmskb %ymm8, %ecx
	testl	%ecx, %ecx
	jz	L(second_aligned_loop_prep)

	/* Search char could be zero so we need to get the true match.
	 */
	vpmovmskb %ymm5, %eax
	testl	%eax, %eax
	jnz	L(first_aligned_loop_return)

	.p2align 4,, 4
L(first_vec_x1_or_x2):
	VPCMPEQ	%ymm3, %ymm7, %ymm3
	VPCMPEQ	%ymm2, %ymm7, %ymm2
	vpmovmskb %ymm3, %eax
	vpmovmskb %ymm2, %edx
	/* Use add for macro-fusion.  */
	addq	%rax, %rdx
	jz	L(first_vec_x0_test)
	/* NB: We could move this shift to before the branch and save a
	   bit of code size / performance on the fall through. The
	   branch leads to the null case which generally seems hotter
	   than char in first 3x VEC.  */
	salq	$32, %rax
	addq	%rdx, %rax
	bsrq	%rax, %rax
	leaq	1(%rsi, %rax), %rax
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
	VZEROUPPER_RETURN

	.p2align 4,, 8
L(first_aligned_loop_return):
	VPCMPEQ	%ymm4, %ymm0, %ymm4
	vpmovmskb %ymm4, %edx
	salq	$32, %rcx
	orq	%rdx, %rcx

	vpmovmskb %ymm10, %eax
	vpmovmskb %ymm6, %edx
	salq	$32, %rax
	orq	%rdx, %rax
	blsmskq	%rcx, %rcx
	andq	%rcx, %rax
	jz	L(first_vec_x1_or_x2)

	bsrq	%rax, %rax
	leaq	-(VEC_SIZE * 2)(%rdi, %rax), %rax
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
	VZEROUPPER_RETURN

	/* Search char cannot be zero.  */
	.p2align 4
L(second_aligned_loop_set_furthest_match):
	/* Save VEC and pointer from most recent match.  */
L(second_aligned_loop_prep):
	movq	%rdi, %rsi
	vmovdqu	%ymm6, %ymm2
	vmovdqu	%ymm10, %ymm3

	.p2align 4
L(second_aligned_loop):
	/* Search 2x at at time.  */
	vmovdqa	(VEC_SIZE * 0)(%rdi), %ymm4
	vmovdqa	(VEC_SIZE * 1)(%rdi), %ymm5

	VPCMPEQ	%ymm4, %ymm7, %ymm6
	VPMIN	%ymm4, %ymm5, %ymm1
	VPCMPEQ	%ymm5, %ymm7, %ymm10
	vpor	%ymm6, %ymm10, %ymm5
	VPCMPEQ	%ymm1, %ymm0, %ymm1
	vpor	%ymm5, %ymm1, %ymm9

	vpmovmskb %ymm9, %eax
	addq	$(VEC_SIZE * 2), %rdi
	testl	%eax, %eax
	jz	L(second_aligned_loop)
	vpmovmskb %ymm1, %ecx
	testl	%ecx, %ecx
	jz	L(second_aligned_loop_set_furthest_match)
	vpmovmskb %ymm5, %eax
	testl	%eax, %eax
	jnz	L(return_new_match)

	/* This is the hot patch. We know CHAR is inbounds and that
	   ymm3/ymm2 have latest match.  */
	.p2align 4,, 4
L(return_old_match):
	vpmovmskb %ymm3, %eax
	vpmovmskb %ymm2, %edx
	salq	$32, %rax
	orq	%rdx, %rax
	bsrq	%rax, %rax
	/* Search char cannot be zero so safe to just use lea for
	   wcsrchr.  */
	leaq	(VEC_SIZE * -2 -(CHAR_SIZE - 1))(%rsi, %rax), %rax
	VZEROUPPER_RETURN

	/* Last iteration also potentially has a match.  */
	.p2align 4,, 8
L(return_new_match):
	VPCMPEQ	%ymm4, %ymm0, %ymm4
	vpmovmskb %ymm4, %edx
	salq	$32, %rcx
	orq	%rdx, %rcx

	vpmovmskb %ymm10, %eax
	vpmovmskb %ymm6, %edx
	salq	$32, %rax
	orq	%rdx, %rax
	blsmskq	%rcx, %rcx
	andq	%rcx, %rax
	jz	L(return_old_match)
	bsrq	%rax, %rax
	/* Search char cannot be zero so safe to just use lea for
	   wcsrchr.  */
	leaq	(VEC_SIZE * -2 -(CHAR_SIZE - 1))(%rdi, %rax), %rax
	VZEROUPPER_RETURN

	.p2align 4,, 4
L(cross_page):
	movq	%rdi, %rsi
	andq	$-VEC_SIZE, %rsi
	vmovdqu	(%rsi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm6
	vpmovmskb %ymm6, %ecx
	/* Shift out zero CHAR matches that are before the begining of
	   src (rdi).  */
	shrxl	%edi, %ecx, %ecx
	testl	%ecx, %ecx
	jz	L(page_cross_continue)
	VPCMPEQ	%ymm1, %ymm7, %ymm1
	vpmovmskb %ymm1, %eax

	/* Shift out search CHAR matches that are before the begining of
	   src (rdi).  */
	shrxl	%edi, %eax, %eax
	blsmskl	%ecx, %ecx
	/* Check if any search CHAR match in range.  */
	andl	%ecx, %eax
	jz	L(ret2)
	bsrl	%eax, %eax
	addq	%rdi, %rax
# ifdef USE_AS_WCSRCHR
	andq	$-CHAR_SIZE, %rax
# endif
L(ret2):
	VZEROUPPER_RETURN
END(STRRCHR)
#endif