/* memcmp/wmemcmp 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)

/* memcmp/wmemcmp is implemented as:

   1. For size from 2 to 7 bytes, load as big endian with movbe and bswap

      to avoid branches.

   2. Use overlapping compare to avoid branch.

   3. Use vector compare when size >= 4 bytes for memcmp or size >= 8

      bytes for wmemcmp.

   4. If size is 8 * VEC_SIZE or less, unroll the loop.

   5. Compare 4 * VEC_SIZE at a time with the aligned first memory

      area.

   6. Use 2 vector compares when size is 2 * VEC_SIZE or less.

   7. Use 4 vector compares when size is 4 * VEC_SIZE or less.

   8. Use 8 vector compares when size is 8 * VEC_SIZE or less.  */

# include <sysdep.h>

# ifndef MEMCMP

#  define MEMCMP	__memcmp_avx2_movbe

# endif

# ifdef USE_AS_WMEMCMP

#  define VPCMPEQ	vpcmpeqd

# else

#  define VPCMPEQ	vpcmpeqb

# endif

# ifndef VZEROUPPER

#  define VZEROUPPER	vzeroupper

# endif

# define VEC_SIZE 32

# define VEC_MASK ((1 << VEC_SIZE) - 1)

/* Warning!

           wmemcmp has to use SIGNED comparison for elements.

           memcmp has to use UNSIGNED comparison for elemnts.

*/

	.section .text.avx,"ax",@progbits

ENTRY (MEMCMP)

# ifdef USE_AS_WMEMCMP

	shl	$2, %rdx

# endif

	cmpq	$VEC_SIZE, %rdx

	jb	L(less_vec)

	/* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	cmpq	$(VEC_SIZE * 2), %rdx

	jbe	L(last_vec)

	VPCMPEQ	%ymm0, %ymm0, %ymm0

	/* More than 2 * VEC.  */

	cmpq	$(VEC_SIZE * 8), %rdx

	ja	L(more_8x_vec)

	cmpq	$(VEC_SIZE * 4), %rdx

	jb	L(last_4x_vec)

	/* From 4 * VEC to 8 * VEC, inclusively. */

	vmovdqu	(%rsi), %ymm1

	VPCMPEQ (%rdi), %ymm1, %ymm1

	vmovdqu	VEC_SIZE(%rsi), %ymm2

	VPCMPEQ VEC_SIZE(%rdi), %ymm2, %ymm2

	vmovdqu	(VEC_SIZE * 2)(%rsi), %ymm3

	VPCMPEQ (VEC_SIZE * 2)(%rdi), %ymm3, %ymm3

	vmovdqu	(VEC_SIZE * 3)(%rsi), %ymm4

	VPCMPEQ (VEC_SIZE * 3)(%rdi), %ymm4, %ymm4

	vpand	%ymm1, %ymm2, %ymm5

	vpand	%ymm3, %ymm4, %ymm6

	vpand	%ymm5, %ymm6, %ymm5

	vptest	%ymm0, %ymm5

	jnc	L(4x_vec_end)

	leaq	-(4 * VEC_SIZE)(%rdi, %rdx), %rdi

	leaq	-(4 * VEC_SIZE)(%rsi, %rdx), %rsi

	vmovdqu	(%rsi), %ymm1

	VPCMPEQ (%rdi), %ymm1, %ymm1

	vmovdqu	VEC_SIZE(%rsi), %ymm2

	VPCMPEQ VEC_SIZE(%rdi), %ymm2, %ymm2

	vpand	%ymm2, %ymm1, %ymm5

	vmovdqu	(VEC_SIZE * 2)(%rsi), %ymm3

	VPCMPEQ (VEC_SIZE * 2)(%rdi), %ymm3, %ymm3

	vpand	%ymm3, %ymm5, %ymm5

	vmovdqu	(VEC_SIZE * 3)(%rsi), %ymm4

	VPCMPEQ (VEC_SIZE * 3)(%rdi), %ymm4, %ymm4

	vpand	%ymm4, %ymm5, %ymm5

	vptest	%ymm0, %ymm5

	jnc	L(4x_vec_end)

	xorl	%eax, %eax

	VZEROUPPER

	ret

	.p2align 4

L(last_2x_vec):

	/* From VEC to 2 * VEC.  No branch when size == VEC_SIZE.  */

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

L(last_vec):

	/* Use overlapping loads to avoid branches.  */

	leaq	-VEC_SIZE(%rdi, %rdx), %rdi

	leaq	-VEC_SIZE(%rsi, %rdx), %rsi

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	VZEROUPPER

	ret

	.p2align 4

L(first_vec):

	/* A byte or int32 is different within 16 or 32 bytes.  */

	tzcntl	%eax, %ecx

# ifdef USE_AS_WMEMCMP

	xorl	%eax, %eax

	movl	(%rdi, %rcx), %edx

	cmpl	(%rsi, %rcx), %edx

L(wmemcmp_return):

	setl	%al

	negl	%eax

	orl	$1, %eax

# else

	movzbl	(%rdi, %rcx), %eax

	movzbl	(%rsi, %rcx), %edx

	sub	%edx, %eax

# endif

	VZEROUPPER

	ret

# ifdef USE_AS_WMEMCMP

	.p2align 4

L(4):

	xorl	%eax, %eax

	movl	(%rdi), %edx

	cmpl	(%rsi), %edx

	jne	L(wmemcmp_return)

	ret

# else

	.p2align 4

L(between_4_7):

	/* Load as big endian with overlapping movbe to avoid branches.  */

	movbe	(%rdi), %eax

	movbe	(%rsi), %ecx

	shlq	$32, %rax

	shlq	$32, %rcx

	movbe	-4(%rdi, %rdx), %edi

	movbe	-4(%rsi, %rdx), %esi

	orq	%rdi, %rax

	orq	%rsi, %rcx

	subq	%rcx, %rax

	je	L(exit)

	sbbl	%eax, %eax

	orl	$1, %eax

	ret

	.p2align 4

L(exit):

	ret

	.p2align 4

L(between_2_3):

	/* Load as big endian to avoid branches.  */

	movzwl	(%rdi), %eax

	movzwl	(%rsi), %ecx

	shll	$8, %eax

	shll	$8, %ecx

	bswap	%eax

	bswap	%ecx

	movb	-1(%rdi, %rdx), %al

	movb	-1(%rsi, %rdx), %cl

	/* Subtraction is okay because the upper 8 bits are zero.  */

	subl	%ecx, %eax

	ret

	.p2align 4

L(1):

	movzbl	(%rdi), %eax

	movzbl	(%rsi), %ecx

	subl	%ecx, %eax

	ret

# endif

	.p2align 4

L(zero):

	xorl	%eax, %eax

	ret

	.p2align 4

L(less_vec):

# ifdef USE_AS_WMEMCMP

	/* It can only be 0, 4, 8, 12, 16, 20, 24, 28 bytes.  */

	cmpb	$4, %dl

	je	L(4)

	jb	L(zero)

# else

	cmpb	$1, %dl

	je	L(1)

	jb	L(zero)

	cmpb	$4, %dl

	jb	L(between_2_3)

	cmpb	$8, %dl

	jb	L(between_4_7)

# endif

	cmpb	$16, %dl

	jae	L(between_16_31)

	/* It is between 8 and 15 bytes.  */

	vmovq	(%rdi), %xmm1

	vmovq	(%rsi), %xmm2

	VPCMPEQ %xmm1, %xmm2, %xmm2

	vpmovmskb %xmm2, %eax

	subl    $0xffff, %eax

	jnz	L(first_vec)

	/* Use overlapping loads to avoid branches.  */

	leaq	-8(%rdi, %rdx), %rdi

	leaq	-8(%rsi, %rdx), %rsi

	vmovq	(%rdi), %xmm1

	vmovq	(%rsi), %xmm2

	VPCMPEQ %xmm1, %xmm2, %xmm2

	vpmovmskb %xmm2, %eax

	subl    $0xffff, %eax

	jnz	L(first_vec)

	ret

	.p2align 4

L(between_16_31):

	/* From 16 to 31 bytes.  No branch when size == 16.  */

	vmovdqu	(%rsi), %xmm2

	VPCMPEQ (%rdi), %xmm2, %xmm2

	vpmovmskb %xmm2, %eax

	subl    $0xffff, %eax

	jnz	L(first_vec)

	/* Use overlapping loads to avoid branches.  */

	leaq	-16(%rdi, %rdx), %rdi

	leaq	-16(%rsi, %rdx), %rsi

	vmovdqu	(%rsi), %xmm2

	VPCMPEQ (%rdi), %xmm2, %xmm2

	vpmovmskb %xmm2, %eax

	subl    $0xffff, %eax

	jnz	L(first_vec)

	ret

	.p2align 4

L(more_8x_vec):

	/* More than 8 * VEC.  Check the first VEC.  */

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	/* Align the first memory area for aligned loads in the loop.

	   Compute how much the first memory area is misaligned.  */

	movq	%rdi, %rcx

	andl	$(VEC_SIZE - 1), %ecx

	/* Get the negative of offset for alignment.  */

	subq	$VEC_SIZE, %rcx

	/* Adjust the second memory area.  */

	subq	%rcx, %rsi

	/* Adjust the first memory area which should be aligned now.  */

	subq	%rcx, %rdi

	/* Adjust length.  */

	addq	%rcx, %rdx

L(loop_4x_vec):

	/* Compare 4 * VEC at a time forward.  */

	vmovdqu	(%rsi), %ymm1

	VPCMPEQ (%rdi), %ymm1, %ymm1

	vmovdqu	VEC_SIZE(%rsi), %ymm2

	VPCMPEQ VEC_SIZE(%rdi), %ymm2, %ymm2

	vpand	%ymm2, %ymm1, %ymm5

	vmovdqu	(VEC_SIZE * 2)(%rsi), %ymm3

	VPCMPEQ (VEC_SIZE * 2)(%rdi), %ymm3, %ymm3

	vpand	%ymm3, %ymm5, %ymm5

	vmovdqu	(VEC_SIZE * 3)(%rsi), %ymm4

	VPCMPEQ (VEC_SIZE * 3)(%rdi), %ymm4, %ymm4

	vpand	%ymm4, %ymm5, %ymm5

	vptest	%ymm0, %ymm5

	jnc	L(4x_vec_end)

	addq	$(VEC_SIZE * 4), %rdi

	addq	$(VEC_SIZE * 4), %rsi

	subq	$(VEC_SIZE * 4), %rdx

	cmpq	$(VEC_SIZE * 4), %rdx

	jae	L(loop_4x_vec)

	/* Less than 4 * VEC.  */

	cmpq	$VEC_SIZE, %rdx

	jbe	L(last_vec)

	cmpq	$(VEC_SIZE * 2), %rdx

	jbe	L(last_2x_vec)

L(last_4x_vec):

	/* From 2 * VEC to 4 * VEC. */

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	addq	$VEC_SIZE, %rdi

	addq	$VEC_SIZE, %rsi

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	/* Use overlapping loads to avoid branches.  */

	leaq	-(3 * VEC_SIZE)(%rdi, %rdx), %rdi

	leaq	-(3 * VEC_SIZE)(%rsi, %rdx), %rsi

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	addq	$VEC_SIZE, %rdi

	addq	$VEC_SIZE, %rsi

	vmovdqu	(%rsi), %ymm2

	VPCMPEQ (%rdi), %ymm2, %ymm2

	vpmovmskb %ymm2, %eax

	subl    $VEC_MASK, %eax

	jnz	L(first_vec)

	VZEROUPPER

	ret

	.p2align 4

L(4x_vec_end):

	vpmovmskb %ymm1, %eax

	subl	$VEC_MASK, %eax

	jnz	L(first_vec)

	vpmovmskb %ymm2, %eax

	subl	$VEC_MASK, %eax

	jnz	L(first_vec_x1)

	vpmovmskb %ymm3, %eax

	subl	$VEC_MASK, %eax

	jnz	L(first_vec_x2)

	vpmovmskb %ymm4, %eax

	subl	$VEC_MASK, %eax

	tzcntl	%eax, %ecx

# ifdef USE_AS_WMEMCMP

	xorl	%eax, %eax

	movl	(VEC_SIZE * 3)(%rdi, %rcx), %edx

	cmpl	(VEC_SIZE * 3)(%rsi, %rcx), %edx

	jmp	L(wmemcmp_return)

# else

	movzbl	(VEC_SIZE * 3)(%rdi, %rcx), %eax

	movzbl	(VEC_SIZE * 3)(%rsi, %rcx), %edx

	sub	%edx, %eax

# endif

	VZEROUPPER

	ret

	.p2align 4

L(first_vec_x1):

	tzcntl	%eax, %ecx

# ifdef USE_AS_WMEMCMP

	xorl	%eax, %eax

	movl	VEC_SIZE(%rdi, %rcx), %edx

	cmpl	VEC_SIZE(%rsi, %rcx), %edx

	jmp	L(wmemcmp_return)

# else

	movzbl	VEC_SIZE(%rdi, %rcx), %eax

	movzbl	VEC_SIZE(%rsi, %rcx), %edx

	sub	%edx, %eax

# endif

	VZEROUPPER

	ret

	.p2align 4

L(first_vec_x2):

	tzcntl	%eax, %ecx

# ifdef USE_AS_WMEMCMP

	xorl	%eax, %eax

	movl	(VEC_SIZE * 2)(%rdi, %rcx), %edx

	cmpl	(VEC_SIZE * 2)(%rsi, %rcx), %edx

	jmp	L(wmemcmp_return)

# else

	movzbl	(VEC_SIZE * 2)(%rdi, %rcx), %eax

	movzbl	(VEC_SIZE * 2)(%rsi, %rcx), %edx

	sub	%edx, %eax

# endif

	VZEROUPPER

	ret

END (MEMCMP)

#endif