dnl  PowerPC-32 mpn_mod_34lsub1 -- mpn remainder mod 2^24-1.

dnl  Copyright 2002, 2003, 2005-2007, 2012 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 603e:              -
C 604e:              -
C 75x (G3):          -
C 7400,7410 (G4):    1          simple load-use scheduling results in 0.75
C 744x,745x (G4+):   0.75
C ppc970:            0.75
C power4:            -
C power5:            -

C TODO
C  * Either start using the low-end masking constants, or remove them.
C  * Merge multiple feed-in cases into a parameterized code block.
C  * Reduce register usage.  It should be possible to almost halve it.

define(`up', `r3')
define(`n', `r4')

define(`a0', `v3')
define(`a1', `v4')
define(`a2', `v5')
define(`c0', `v6')
define(`c1', `v7')
define(`c2', `v8')
define(`z',  `v9')
define(`x0', `v10')
define(`x1', `v11')
define(`x2', `v12')
define(`x3', `v13')
define(`pv', `v14')
define(`y0', `v0')
define(`y1', `v1')
define(`y2', `v2')
define(`y3', `v15')

ASM_START()
PROLOGUE(mpn_mod_34lsub1)
	cmpwi	cr0, n, 20		C tuned cutoff point
	bge	L(large)

	li	r9, 0			C result accumulator
	mulli	r10, n, 0xb		C 0xb = ceil(32/3)
	srwi.	r10, r10, 5		C r10 = floor(n/3), n < 32
	beq	L(small_tail)
	mtctr	r10
	lwz	r6, 0(up)
	lwz	r7, 4(up)
	lwzu	r8, 8(up)
	subf	n, r10, n
	subf	n, r10, n
	subf	n, r10, n
	bdz	L(small_end)

	ALIGN(16)
L(los):	rlwinm	r0, r6, 0,8,31
	add	r9, r9, r0		C add 24b from u0
	srwi	r0, r6, 24
	lwz	r6, 4(up)
	rlwimi	r0, r7, 8, 0x00ffff00	C --111100
	add	r9, r9, r0		C add 8b from u0 and 16b from u1
	srwi	r0, r7, 16
	lwz	r7, 8(up)
	rlwimi	r0, r8, 16, 0x00ff0000	C --221111
	add	r9, r9, r0		C add 16b from u1 and 8b from u2
	srwi	r0, r8, 8		C --222222
	lwzu	r8, 12(up)
	add	r9, r9, r0		C add 24b from u2
	bdnz	L(los)
L(small_end):
	rlwinm	r0, r6, 0,8,31
	add	r9, r9, r0		C add 24b from u0
	srwi	r0, r6, 24
	rlwimi	r0, r7, 8, 0x00ffff00	C --111100
	add	r9, r9, r0		C add 8b from u0 and 16b from u1
	srwi	r0, r7, 16
	rlwimi	r0, r8, 16, 0x00ff0000	C --221111
	add	r9, r9, r0		C add 16b from u1 and 8b from u2
	srwi	r0, r8, 8		C --222222
	add	r9, r9, r0		C add 24b from u2

	addi	up, up, 4
	rlwinm	r0, r9, 0,8,31
	srwi	r9, r9, 24
	add	r9, r9, r0

L(small_tail):
	cmpi	cr0, n, 1
	blt	L(ret)

	lwz	r6, 0(up)
	rlwinm	r0, r6, 0,8,31
	srwi	r6, r6, 24
	add	r9, r9, r0
	add	r9, r9, r6

	beq	L(ret)

	lwz	r6, 4(up)
	rlwinm	r0, r6, 8,8,23
	srwi	r6, r6, 16
	add	r9, r9, r0
	add	r9, r9, r6

L(ret):	mr	r3, r9
	blr


L(large):
	stwu	r1, -32(r1)
	mfspr	r10, 256
	oris	r0, r10, 0xffff		C Set VRSAVE bit 0-15
	mtspr	256, r0

	andi.	r7, up, 15
	vxor	a0, v0, v0
	lis	r9, 0xaaaa
	vxor	a1, v0, v0
	ori	r9, r9, 0xaaab
	vxor	a2, v0, v0
	li	r5, 16
	vxor	c0, v0, v0
	li	r6, 32
	vxor	c1, v0, v0
	LEAL(	r11, cnsts)		C CAUTION clobbers r0 for elf, darwin
	vxor	c2, v0, v0
	vxor	z, v0, v0

	beq	L(aligned16)

	cmpwi	cr7, r7, 8
	bge	cr7, L(na4)

	lvx	a2, 0, up
	addi	up, up, 16
	vsldoi	a2, a2, z, 4
	vsldoi	a2, z, a2, 12

	addi	n, n, 9
	mulhwu	r0, n, r9
	srwi	r0, r0, 3		C r0 = floor(n/12)
	mtctr	r0

	mulli	r8, r0, 12
	subf	n, r8, n
	b	L(2)

L(na4):	bne	cr7, L(na8)

	lvx	a1, 0, up
	addi	up, up, -16
	vsldoi	a1, a1, z, 8
	vsldoi	a1, z, a1, 8

	addi	n, n, 6
	mulhwu	r0, n, r9
	srwi	r0, r0, 3		C r0 = floor(n/12)
	mtctr	r0

	mulli	r8, r0, 12
	subf	n, r8, n
	b	L(1)

L(na8):
	lvx	a0, 0, up
	vsldoi	a0, a0, z, 12
	vsldoi	a0, z, a0, 4

	addi	n, n, 3
	mulhwu	r0, n, r9
	srwi	r0, r0, 3		C r0 = floor(n/12)
	mtctr	r0

	mulli	r8, r0, 12
	subf	n, r8, n
	b	L(0)

L(aligned16):
	mulhwu	r0, n, r9
	srwi	r0, r0, 3		C r0 = floor(n/12)
	mtctr	r0

	mulli	r8, r0, 12
	subf	n, r8, n

	lvx	a0, 0, up
L(0):	lvx	a1, r5, up
L(1):	lvx	a2, r6, up
	addi	up, up, 48
L(2):	bdz	L(end)
	li	r12, 256
	li	r9, 288
	ALIGN(32)
L(top):
	lvx	v0, 0, up
	vaddcuw	v10, a0, v0
	vadduwm	a0, a0, v0
	vadduwm	c0, c0, v10

	lvx	v1, r5, up
	vaddcuw	v10, a1, v1
	vadduwm	a1, a1, v1
	vadduwm	c1, c1, v10

	lvx	v2, r6, up
	dcbt	up, r12
	dcbt	up, r9
	addi	up, up, 48
	vaddcuw	v10, a2, v2
	vadduwm	a2, a2, v2
	vadduwm	c2, c2, v10
	bdnz	L(top)

L(end):
C n = 0...11
	cmpwi	cr0, n, 0
	beq	L(sum)
	cmpwi	cr0, n, 4
	ble	L(tail.1..4)
	cmpwi	cr0, n, 8
	ble	L(tail.5..8)

L(tail.9..11):
	lvx	v0, 0, up
	vaddcuw	v10, a0, v0
	vadduwm	a0, a0, v0
	vadduwm	c0, c0, v10

	lvx	v1, r5, up
	vaddcuw	v10, a1, v1
	vadduwm	a1, a1, v1
	vadduwm	c1, c1, v10

	lvx	v2, r6, up

	addi	r8, r11, 96
	rlwinm	r3, n ,4,26,27
	lvx	v11, r3, r8
	vand	v2, v2, v11

	vaddcuw	v10, a2, v2
	vadduwm	a2, a2, v2
	vadduwm	c2, c2, v10
	b	L(sum)

L(tail.5..8):
	lvx	v0, 0, up
	vaddcuw	v10, a0, v0
	vadduwm	a0, a0, v0
	vadduwm	c0, c0, v10

	lvx	v1, r5, up

	addi	r8, r11, 96
	rlwinm	r3, n ,4,26,27
	lvx	v11, r3, r8
	vand	v1, v1, v11

	vaddcuw	v10, a1, v1
	vadduwm	a1, a1, v1
	vadduwm	c1, c1, v10
	b	L(sum)

L(tail.1..4):
	lvx	v0, 0, up

	addi	r8, r11, 96
	rlwinm	r3, n ,4,26,27
	lvx	v11, r3, r8
	vand	v0, v0, v11

	vaddcuw	v10, a0, v0
	vadduwm	a0, a0, v0
	vadduwm	c0, c0, v10

L(sum):	lvx	pv, 0, r11
	vperm	x0, a0, z, pv		C extract 4 24-bit field from a0
	vperm	y0, c2, z, pv
	lvx	pv, r5, r11
	vperm	x1, a1, z, pv		C extract 4 24-bit field from a1
	vperm	y1, c0, z, pv		C extract 4 24-bit field from a1
	lvx	pv, r6, r11
	vperm	x2, a2, z, pv		C extract 4 24-bit field from a1
	vperm	y2, c1, z, pv		C extract 4 24-bit field from a1
	li	r10,  48
	lvx	pv, r10, r11
	vperm	x3, a0, z, pv		C extract remaining/partial a0 fields
	vperm	y3, c2, z, pv		C extract remaining/partial a0 fields
	li	r10,  64
	lvx	pv, r10, r11
	vperm	x3, a1, x3, pv		C insert remaining/partial a1 fields
	vperm	y3, c0, y3, pv		C insert remaining/partial a1 fields
	li	r10,  80
	lvx	pv, r10, r11
	vperm	x3, a2, x3, pv		C insert remaining/partial a2 fields
	vperm	y3, c1, y3, pv		C insert remaining/partial a2 fields

C We now have 4 128-bit accumulators to sum
	vadduwm	x0, x0, x1
	vadduwm	x2, x2, x3
	vadduwm	x0, x0, x2

	vadduwm	y0, y0, y1
	vadduwm	y2, y2, y3
	vadduwm	y0, y0, y2

	vadduwm	x0, x0, y0

C Reduce 32-bit fields
	vsumsws	x0, x0, z

	li	r7, 16
	stvx	x0, r7, r1
	lwz	r3, 28(r1)

	mtspr	256, r10
	addi	r1, r1, 32
	blr
EPILOGUE()

C load	|      v0       |      v1       |      v2       |
C acc	|      a0       |      a1       |      a2       |
C carry	|      c0       |      c1       |      c2       |
C	| 0   1   2   3 | 4   5   6   7 | 8   9  10  11 |  128
C	|---|---|---|---|---|---|---|---|---|---|---|---|   32
C	|  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |   24
C	|     |     |     |     |     |     |     |     |   48

C       $---------------$---------------$---------------$---------------$
C       |   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   |
C       |_______________________________________________________________|
C   |           |           |           |           |           |           |
C       <-hi16-> <--- 24 --> <--- 24 --> <--- 24 --> <--- 24 --> <-lo16->


DEF_OBJECT(cnsts,16)
C Permutation vectors in the order they are used above
C #      00   01   02   03    04   05   06   07    08   09   0a   0b    0c   0d   0e   0f
 .byte 0x10,0x01,0x02,0x03, 0x10,0x06,0x07,0x00, 0x10,0x0b,0x04,0x05, 0x10,0x08,0x09,0x0a C a0
 .byte 0x10,0x07,0x00,0x01, 0x10,0x04,0x05,0x06, 0x10,0x09,0x0a,0x0b, 0x10,0x0e,0x0f,0x08 C a1
 .byte 0x10,0x00,0x01,0x02, 0x10,0x05,0x06,0x07, 0x10,0x0a,0x0b,0x04, 0x10,0x0f,0x08,0x09 C a2
 .byte 0x10,0x0d,0x0e,0x0f, 0x10,0x10,0x10,0x0c, 0x10,0x10,0x10,0x10, 0x10,0x10,0x10,0x10 C part a0
 .byte 0x10,0x11,0x12,0x13, 0x10,0x02,0x03,0x17, 0x10,0x10,0x0c,0x0d, 0x10,0x10,0x10,0x10 C part a1
 .byte 0x10,0x11,0x12,0x13, 0x10,0x15,0x16,0x17, 0x10,0x03,0x1a,0x1b, 0x10,0x0c,0x0d,0x0e C part a2
C Masks for high end of number
 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
 .byte 0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00
 .byte 0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00
C Masks for low end of number
C .byte	0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
C .byte	0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
C .byte	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff
C .byte	0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff
END_OBJECT(cnsts)