popcount.asm revision 1.1.1.1 
1dnl  ARM64 Neon mpn_popcount -- mpn bit population count.
2
3dnl  Copyright 2013, 2014 Free Software Foundation, Inc.
4
5dnl  This file is part of the GNU MP Library.
6dnl
7dnl  The GNU MP Library is free software; you can redistribute it and/or modify
8dnl  it under the terms of either:
9dnl
10dnl    * the GNU Lesser General Public License as published by the Free
11dnl      Software Foundation; either version 3 of the License, or (at your
12dnl      option) any later version.
13dnl
14dnl  or
15dnl
16dnl    * the GNU General Public License as published by the Free Software
17dnl      Foundation; either version 2 of the License, or (at your option) any
18dnl      later version.
19dnl
20dnl  or both in parallel, as here.
21dnl
22dnl  The GNU MP Library is distributed in the hope that it will be useful, but
23dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
25dnl  for more details.
26dnl
27dnl  You should have received copies of the GNU General Public License and the
28dnl  GNU Lesser General Public License along with the GNU MP Library.  If not,
29dnl  see https://www.gnu.org/licenses/.
30
31include(`../config.m4')
32
33C	     cycles/limb
34C Cortex-A53	 ?
35C Cortex-A57	 ?
36
37C TODO
38C  * Consider greater unrolling.
39C  * Arrange to align the pointer, if that helps performance.  Use the same
40C    read-and-mask trick we use on PCs, for simplicity and performance.  (Sorry
41C    valgrind!)
42C  * Explore if explicit align directives, e.g., "[ptr:128]" help.
43C  * See rth's gmp-devel 2013-02/03 messages about final summation tricks.
44
45changecom(@&*$)
46
47C INPUT PARAMETERS
48define(`ap', x0)
49define(`n',  x1)
50
51C We sum into 16 16-bit counters in v4,v5, but at the end we sum them and end
52C up with 8 16-bit counters.  Therefore, we can sum to 8(2^16-1) bits, or
53C (8*2^16-1)/64 = 0x1fff limbs.  We use a chunksize close to that, but which
54C  allows the huge count code to jump deep into the code (at L(chu)).
55
56define(`maxsize',  0x1fff)
57define(`chunksize',0x1ff0)
58
59ASM_START()
60PROLOGUE(mpn_popcount)
61
62	mov	x11, #maxsize
63	cmp	n, x11
64	b.hi	L(gt8k)
65
66L(lt8k):
67	movi	v4.16b, #0			C clear summation register
68	movi	v5.16b, #0			C clear summation register
69
70	tbz	n, #0, L(xx0)
71	sub	n, n, #1
72	ld1	{v0.1d}, [ap], #8		C load 1 limb
73	cnt	v6.16b, v0.16b
74	uadalp	v4.8h,  v6.16b			C could also splat
75
76L(xx0):	tbz	n, #1, L(x00)
77	sub	n, n, #2
78	ld1	{v0.2d}, [ap], #16		C load 2 limbs
79	cnt	v6.16b, v0.16b
80	uadalp	v4.8h,  v6.16b
81
82L(x00):	tbz	n, #2, L(000)
83	subs	n, n, #4
84	ld1	{v0.2d,v1.2d}, [ap], #32	C load 4 limbs
85	b.ls	L(sum)
86
87L(gt4):	ld1	{v2.2d,v3.2d}, [ap], #32	C load 4 limbs
88	sub	n, n, #4
89	cnt	v6.16b, v0.16b
90	cnt	v7.16b, v1.16b
91	b	L(mid)
92
93L(000):	subs	n, n, #8
94	b.lo	L(e0)
95
96L(chu):	ld1	{v2.2d,v3.2d}, [ap], #32	C load 4 limbs
97	ld1	{v0.2d,v1.2d}, [ap], #32	C load 4 limbs
98	cnt	v6.16b, v2.16b
99	cnt	v7.16b, v3.16b
100	subs	n, n, #8
101	b.lo	L(end)
102
103L(top):	ld1	{v2.2d,v3.2d}, [ap], #32	C load 4 limbs
104	uadalp	v4.8h,  v6.16b
105	cnt	v6.16b, v0.16b
106	uadalp	v5.8h,  v7.16b
107	cnt	v7.16b, v1.16b
108L(mid):	ld1	{v0.2d,v1.2d}, [ap], #32	C load 4 limbs
109	subs	n, n, #8
110	uadalp	v4.8h,  v6.16b
111	cnt	v6.16b, v2.16b
112	uadalp	v5.8h,  v7.16b
113	cnt	v7.16b, v3.16b
114	b.hs	L(top)
115
116L(end):	uadalp	v4.8h,  v6.16b
117	uadalp	v5.8h,  v7.16b
118L(sum):	cnt	v6.16b, v0.16b
119	cnt	v7.16b, v1.16b
120	uadalp	v4.8h,  v6.16b
121	uadalp	v5.8h,  v7.16b
122	add	v4.8h, v4.8h, v5.8h
123					C we have 8 16-bit counts
124L(e0):	uaddlp	v4.4s,  v4.8h		C we have 4 32-bit counts
125	uaddlp	v4.2d,  v4.4s		C we have 2 64-bit counts
126	mov	x0, v4.d[0]
127	mov	x1, v4.d[1]
128	add	x0, x0, x1
129	ret
130
131C Code for count > maxsize.  Splits operand and calls above code.
132define(`ap2', x5)			C caller-saves reg not used above
133L(gt8k):
134	mov	x8, x30
135	mov	x7, n			C full count (caller-saves reg not used above)
136	mov	x4, #0			C total sum  (caller-saves reg not used above)
137	mov	x9, #chunksize*8	C caller-saves reg not used above
138	mov	x10, #chunksize		C caller-saves reg not used above
139
1401:	add	ap2, ap, x9		C point at subsequent block
141	mov	n, #chunksize-8		C count for this invocation, adjusted for entry pt
142	movi	v4.16b, #0		C clear chunk summation register
143	movi	v5.16b, #0		C clear chunk summation register
144	bl	L(chu)			C jump deep inside code
145	add	x4, x4, x0
146	mov	ap, ap2			C put chunk pointer in place for calls
147	sub	x7, x7, x10
148	cmp	x7, x11
149	b.hi	1b
150
151	mov	n, x7			C count for final invocation
152	bl	L(lt8k)
153	add	x0, x4, x0
154	mov	x30, x8
155	ret
156EPILOGUE()
157