/* strrchr/wcsrchr optimized with AVX2.
   Copyright (C) 2017-2018 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
   <http://www.gnu.org/licenses/>.  */

#if IS_IN (libc)

# include <sysdep.h>

# ifndef STRRCHR
#  define STRRCHR	__strrchr_avx2
# endif

# ifdef USE_AS_WCSRCHR
#  define VPBROADCAST	vpbroadcastd
#  define VPCMPEQ	vpcmpeqd
# else
#  define VPBROADCAST	vpbroadcastb
#  define VPCMPEQ	vpcmpeqb
# endif

# ifndef VZEROUPPER
#  define VZEROUPPER	vzeroupper
# endif

# define VEC_SIZE	32

	.section .text.avx,"ax",@progbits
ENTRY (STRRCHR)
	movd	%esi, %xmm4
	movl	%edi, %ecx
	/* Broadcast CHAR to YMM4.  */
	VPBROADCAST %xmm4, %ymm4
	vpxor	%ymm0, %ymm0, %ymm0

	/* Check if we may cross page boundary with one vector load.  */
	andl	$(2 * VEC_SIZE - 1), %ecx
	cmpl	$VEC_SIZE, %ecx
	ja	L(cros_page_boundary)

	vmovdqu	(%rdi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm2
	VPCMPEQ	%ymm1, %ymm4, %ymm3
	vpmovmskb %ymm2, %ecx
	vpmovmskb %ymm3, %eax
	addq	$VEC_SIZE, %rdi

	testl	%eax, %eax
	jnz	L(first_vec)

	testl	%ecx, %ecx
	jnz	L(return_null)

	andq	$-VEC_SIZE, %rdi
	xorl	%edx, %edx
	jmp	L(aligned_loop)

	.p2align 4
L(first_vec):
	/* Check if there is a nul CHAR.  */
	testl	%ecx, %ecx
	jnz	L(char_and_nul_in_first_vec)

	/* Remember the match and keep searching.  */
	movl	%eax, %edx
	movq	%rdi, %rsi
	andq	$-VEC_SIZE, %rdi
	jmp	L(aligned_loop)

	.p2align 4
L(cros_page_boundary):
	andl	$(VEC_SIZE - 1), %ecx
	andq	$-VEC_SIZE, %rdi
	vmovdqa	(%rdi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm2
	VPCMPEQ	%ymm1, %ymm4, %ymm3
	vpmovmskb %ymm2, %edx
	vpmovmskb %ymm3, %eax
	shrl	%cl, %edx
	shrl	%cl, %eax
	addq	$VEC_SIZE, %rdi

	/* Check if there is a CHAR.  */
	testl	%eax, %eax
	jnz	L(found_char)

	testl	%edx, %edx
	jnz	L(return_null)

	jmp	L(aligned_loop)

	.p2align 4
L(found_char):
	testl	%edx, %edx
	jnz	L(char_and_nul)

	/* Remember the match and keep searching.  */
	movl	%eax, %edx
	leaq	(%rdi, %rcx), %rsi

	.p2align 4
L(aligned_loop):
	vmovdqa	(%rdi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm2
	addq	$VEC_SIZE, %rdi
	VPCMPEQ	%ymm1, %ymm4, %ymm3
	vpmovmskb %ymm2, %ecx
	vpmovmskb %ymm3, %eax
	orl	%eax, %ecx
	jnz	L(char_nor_null)

	vmovdqa	(%rdi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm2
	add	$VEC_SIZE, %rdi
	VPCMPEQ	%ymm1, %ymm4, %ymm3
	vpmovmskb %ymm2, %ecx
	vpmovmskb %ymm3, %eax
	orl	%eax, %ecx
	jnz	L(char_nor_null)

	vmovdqa	(%rdi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm2
	addq	$VEC_SIZE, %rdi
	VPCMPEQ	%ymm1, %ymm4, %ymm3
	vpmovmskb %ymm2, %ecx
	vpmovmskb %ymm3, %eax
	orl	%eax, %ecx
	jnz	L(char_nor_null)

	vmovdqa	(%rdi), %ymm1
	VPCMPEQ	%ymm1, %ymm0, %ymm2
	addq	$VEC_SIZE, %rdi
	VPCMPEQ	%ymm1, %ymm4, %ymm3
	vpmovmskb %ymm2, %ecx
	vpmovmskb %ymm3, %eax
	orl	%eax, %ecx
	jz	L(aligned_loop)

	.p2align 4
L(char_nor_null):
	/* Find a CHAR or a nul CHAR in a loop.  */
	testl	%eax, %eax
	jnz	L(match)
L(return_value):
	testl	%edx, %edx
	jz	L(return_null)
	movl	%edx, %eax
	movq	%rsi, %rdi

# ifdef USE_AS_WCSRCHR
	/* Keep the first bit for each matching CHAR for bsr.  */
	andl	$0x11111111, %eax
# endif
	bsrl	%eax, %eax
	leaq	-VEC_SIZE(%rdi, %rax), %rax
	VZEROUPPER
	ret

	.p2align 4
L(match):
	/* Find a CHAR.  Check if there is a nul CHAR.  */
	vpmovmskb %ymm2, %ecx
	testl	%ecx, %ecx
	jnz	L(find_nul)

	/* Remember the match and keep searching.  */
	movl	%eax, %edx
	movq	%rdi, %rsi
	jmp	L(aligned_loop)

	.p2align 4
L(find_nul):
# ifdef USE_AS_WCSRCHR
	/* Keep the first bit for each matching CHAR for bsr.  */
	andl	$0x11111111, %ecx
	andl	$0x11111111, %eax
# endif
	/* Mask out any matching bits after the nul CHAR.  */
	movl	%ecx, %r8d
	subl	$1, %r8d
	xorl	%ecx, %r8d
	andl	%r8d, %eax
	testl	%eax, %eax
	/* If there is no CHAR here, return the remembered one.  */
	jz	L(return_value)
	bsrl	%eax, %eax
	leaq	-VEC_SIZE(%rdi, %rax), %rax
	VZEROUPPER
	ret

	.p2align 4
L(char_and_nul):
	/* Find both a CHAR and a nul CHAR.  */
	addq	%rcx, %rdi
	movl	%edx, %ecx
L(char_and_nul_in_first_vec):
# ifdef USE_AS_WCSRCHR
	/* Keep the first bit for each matching CHAR for bsr.  */
	andl	$0x11111111, %ecx
	andl	$0x11111111, %eax
# endif
	/* Mask out any matching bits after the nul CHAR.  */
	movl	%ecx, %r8d
	subl	$1, %r8d
	xorl	%ecx, %r8d
	andl	%r8d, %eax
	testl	%eax, %eax
	/* Return null pointer if the nul CHAR comes first.  */
	jz	L(return_null)
	bsrl	%eax, %eax
	leaq	-VEC_SIZE(%rdi, %rax), %rax
	VZEROUPPER
	ret

	.p2align 4
L(return_null):
	xorl	%eax, %eax
	VZEROUPPER
	ret

END (STRRCHR)
#endif