dnl  x86-32 mpn_mod_1_1p, requiring cmov.

dnl  Contributed to the GNU project by Niels Möller and Torbjorn Granlund.

dnl  Copyright 2010, 2011 Free Software Foundation, Inc.

dnl  This file is part of the GNU MP Library.
dnl
dnl  The GNU MP Library is free software; you can redistribute it and/or modify
dnl  it under the terms of either:
dnl
dnl    * the GNU Lesser General Public License as published by the Free
dnl      Software Foundation; either version 3 of the License, or (at your
dnl      option) any later version.
dnl
dnl  or
dnl
dnl    * the GNU General Public License as published by the Free Software
dnl      Foundation; either version 2 of the License, or (at your option) any
dnl      later version.
dnl
dnl  or both in parallel, as here.
dnl
dnl  The GNU MP Library is distributed in the hope that it will be useful, but
dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
dnl  for more details.
dnl
dnl  You should have received copies of the GNU General Public License and the
dnl  GNU Lesser General Public License along with the GNU MP Library.  If not,
dnl  see https://www.gnu.org/licenses/.

include(`../config.m4')

C			    cycles/limb
C P5				 ?
C P6 model 0-8,10-12		 ?
C P6 model 9  (Banias)		 ?
C P6 model 13 (Dothan)		 ?
C P4 model 0  (Willamette)	 ?
C P4 model 1  (?)		 ?
C P4 model 2  (Northwood)	 ?
C P4 model 3  (Prescott)	 ?
C P4 model 4  (Nocona)		 ?
C AMD K6			 ?
C AMD K7			 7
C AMD K8			 ?

define(`B2mb', `%ebx')
define(`r0', `%esi')
define(`r2', `%ebp')
define(`t0', `%edi')
define(`ap', `%ecx')  C Also shift count

C Stack frame
C	pre	36(%esp)
C	b	32(%esp)
C	n	28(%esp)
C	ap	24(%esp)
C	return	20(%esp)
C	%ebp	16(%esp)
C	%edi	12(%esp)
C	%esi	8(%esp)
C	%ebx	4(%esp)
C	B2mod	(%esp)

define(`B2modb', `(%esp)')
define(`n', `28(%esp)')
define(`b', `32(%esp)')
define(`pre', `36(%esp)')

C mp_limb_t
C mpn_mod_1_1p (mp_srcptr ap, mp_size_t n, mp_limb_t b, mp_limb_t pre[4])
C
C The pre array contains bi, cnt, B1modb, B2modb
C Note: This implementation needs B1modb only when cnt > 0

ASM_START()
	TEXT
	ALIGN(8)
PROLOGUE(mpn_mod_1_1p)
	push	%ebp
	push	%edi
	push	%esi
	push	%ebx
	mov	32(%esp), %ebp		C pre[]

	mov	12(%ebp), %eax		C B2modb
	push	%eax			C Put it on stack

	mov	n, %edx
	mov	24(%esp), ap

	lea	(ap, %edx, 4), ap
	mov	-4(ap), %eax
	cmp	$3, %edx
	jnc	L(first)
	mov	-8(ap), r0
	jmp	L(reduce_two)

L(first):
	C First iteration, no r2
	mull	B2modb
	mov	-12(ap), r0
	add	%eax, r0
	mov	-8(ap), %eax
	adc	%edx, %eax
	sbb	r2, r2
	subl	$3, n
	lea	-16(ap), ap
	jz	L(reduce_three)

	mov	B2modb, B2mb
	sub	b, B2mb
	lea	(B2mb, r0), t0
	jmp	L(mid)

	ALIGN(16)
L(top): C Loopmixed to 7 c/l on k7
	add	%eax, r0
	lea	(B2mb, r0), t0
	mov	r2, %eax
	adc	%edx, %eax
	sbb	r2, r2
L(mid):	mull	B2modb
	and	B2modb, r2
	add	r0, r2
	decl	n
	mov	(ap), r0
	cmovc(	t0, r2)
	lea	-4(ap), ap
	jnz	L(top)

	add	%eax, r0
	mov	r2, %eax
	adc	%edx, %eax
	sbb	r2, r2

L(reduce_three):
	C Eliminate r2
	and	b, r2
	sub	r2, %eax

L(reduce_two):
	mov	pre, %ebp
	movb	4(%ebp), %cl
	test	%cl, %cl
	jz	L(normalized)

	C Unnormalized, use B1modb to reduce to size < B b
	mull	8(%ebp)
	xor	t0, t0
	add	%eax, r0
	adc	%edx, t0
	mov	t0, %eax

	C Left-shift to normalize
	shld	%cl, r0, %eax C Always use shld?

	shl	%cl, r0
	jmp	L(udiv)

L(normalized):
	mov	%eax, t0
	sub	b, t0
	cmovnc(	t0, %eax)

L(udiv):
	lea	1(%eax), t0
	mull	(%ebp)
	mov	b, %ebx		C Needed in register for lea
	add	r0, %eax
	adc	t0, %edx
	imul	%ebx, %edx
	sub	%edx, r0
	cmp	r0, %eax
	lea	(%ebx, r0), %eax
	cmovnc(	r0, %eax)
	cmp	%ebx, %eax
	jnc	L(fix)
L(ok):	shr	%cl, %eax

	add	$4, %esp
	pop	%ebx
	pop	%esi
	pop	%edi
	pop	%ebp

	ret
L(fix):	sub	%ebx, %eax
	jmp	L(ok)
EPILOGUE()

PROLOGUE(mpn_mod_1_1p_cps)
	push	%ebp
	mov	12(%esp), %ebp
	push	%esi
	bsr	%ebp, %ecx
	push	%ebx
	xor	$31, %ecx
	mov	16(%esp), %esi
	sal	%cl, %ebp
	mov	%ebp, %edx
	not	%edx
	mov	$-1, %eax
	div	%ebp			C On K7, invert_limb would be a few cycles faster.
	mov	%eax, (%esi)		C store bi
	mov	%ecx, 4(%esi)		C store cnt
	neg	%ebp
	mov	$1, %edx
	shld	%cl, %eax, %edx
	imul	%ebp, %edx
	shr	%cl, %edx
	imul	%ebp, %eax
	mov	%edx, 8(%esi)		C store B1modb
	mov	%eax, 12(%esi)		C store B2modb
	pop	%ebx
	pop	%esi
	pop	%ebp
	ret
EPILOGUE()