1 1.1 mrg dnl ARM Neon mpn_popcount -- mpn bit population count. 2 1.1 mrg 3 1.1 mrg dnl Copyright 2013 Free Software Foundation, Inc. 4 1.1 mrg 5 1.1 mrg dnl This file is part of the GNU MP Library. 6 1.1 mrg dnl 7 1.1 mrg dnl The GNU MP Library is free software; you can redistribute it and/or modify 8 1.1 mrg dnl it under the terms of either: 9 1.1 mrg dnl 10 1.1 mrg dnl * the GNU Lesser General Public License as published by the Free 11 1.1 mrg dnl Software Foundation; either version 3 of the License, or (at your 12 1.1 mrg dnl option) any later version. 13 1.1 mrg dnl 14 1.1 mrg dnl or 15 1.1 mrg dnl 16 1.1 mrg dnl * the GNU General Public License as published by the Free Software 17 1.1 mrg dnl Foundation; either version 2 of the License, or (at your option) any 18 1.1 mrg dnl later version. 19 1.1 mrg dnl 20 1.1 mrg dnl or both in parallel, as here. 21 1.1 mrg dnl 22 1.1 mrg dnl The GNU MP Library is distributed in the hope that it will be useful, but 23 1.1 mrg dnl WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 24 1.1 mrg dnl or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 25 1.1 mrg dnl for more details. 26 1.1 mrg dnl 27 1.1 mrg dnl You should have received copies of the GNU General Public License and the 28 1.1 mrg dnl GNU Lesser General Public License along with the GNU MP Library. If not, 29 1.1 mrg dnl see https://www.gnu.org/licenses/. 30 1.1 mrg 31 1.1 mrg include(`../config.m4') 32 1.1 mrg 33 1.1 mrg C cycles/limb 34 1.1 mrg C StrongARM: - 35 1.1 mrg C XScale - 36 1.1 mrg C Cortex-A7 ? 37 1.1 mrg C Cortex-A8 ? 38 1.1 mrg C Cortex-A9 1.125 39 1.1 mrg C Cortex-A15 0.56 40 1.1 mrg 41 1.1 mrg C TODO 42 1.1 mrg C * Explore using vldr and vldm. Does it help on A9? (These loads do 43 1.1 mrg C 64-bits-at-a-time, which will mess up in big-endian mode. Except not for 44 1.1 mrg C popcount. Except perhaps also for popcount for the edge loads.) 45 1.1 mrg C * Arrange to align the pointer, if that helps performance. Use the same 46 1.1 mrg C read-and-mask trick we use on PCs, for simplicity and performance. (Sorry 47 1.1 mrg C valgrind!) 48 1.1 mrg C * Explore if explicit align directives, e.g., "[ptr:128]" help. 49 1.1 mrg C * See rth's gmp-devel 2013-02/03 messages about final summation tricks. 50 1.1 mrg 51 1.1 mrg C INPUT PARAMETERS 52 1.1 mrg define(`ap', r0) 53 1.1 mrg define(`n', r1) 54 1.1 mrg 55 1.1 mrg C We sum into 16 16-bit counters in q8,q9, but at the end we sum them and end 56 1.1 mrg C up with 8 16-bit counters. Therefore, we can sum to 8(2^16-1) bits, or 57 1.1 mrg C (8*2^16-1)/32 = 0x3fff limbs. We use a chunksize close to that, but which 58 1.1 mrg C can be represented as a 8-bit ARM constant. 59 1.1 mrg C 60 1.1 mrg define(`chunksize',0x3f80) 61 1.1 mrg 62 1.1 mrg ASM_START() 63 1.1 mrg PROLOGUE(mpn_popcount) 64 1.1 mrg 65 1.1 mrg cmp n, #chunksize 66 1.1 mrg bhi L(gt16k) 67 1.1 mrg 68 1.1 mrg L(lt16k): 69 1.1 mrg vmov.i64 q8, #0 C clear summation register 70 1.1 mrg vmov.i64 q9, #0 C clear summation register 71 1.1 mrg 72 1.1 mrg tst n, #1 73 1.1 mrg beq L(xxx0) 74 1.1 mrg vmov.i64 d0, #0 75 1.1 mrg sub n, n, #1 76 1.1 mrg vld1.32 {d0[0]}, [ap]! C load 1 limb 77 1.1 mrg vcnt.8 d24, d0 78 1.1 mrg vpadal.u8 d16, d24 C d16/q8 = 0; could just splat 79 1.1 mrg 80 1.1 mrg L(xxx0):tst n, #2 81 1.1 mrg beq L(xx00) 82 1.1 mrg sub n, n, #2 83 1.1 mrg vld1.32 {d0}, [ap]! C load 2 limbs 84 1.1 mrg vcnt.8 d24, d0 85 1.1 mrg vpadal.u8 d16, d24 86 1.1 mrg 87 1.1 mrg L(xx00):tst n, #4 88 1.1 mrg beq L(x000) 89 1.1 mrg sub n, n, #4 90 1.1 mrg vld1.32 {q0}, [ap]! C load 4 limbs 91 1.1 mrg vcnt.8 q12, q0 92 1.1 mrg vpadal.u8 q8, q12 93 1.1 mrg 94 1.1 mrg L(x000):tst n, #8 95 1.1 mrg beq L(0000) 96 1.1 mrg 97 1.1 mrg subs n, n, #8 98 1.1 mrg vld1.32 {q0,q1}, [ap]! C load 8 limbs 99 1.1 mrg bls L(sum) 100 1.1 mrg 101 1.1 mrg L(gt8): vld1.32 {q2,q3}, [ap]! C load 8 limbs 102 1.1 mrg sub n, n, #8 103 1.1 mrg vcnt.8 q12, q0 104 1.1 mrg vcnt.8 q13, q1 105 1.1 mrg b L(mid) 106 1.1 mrg 107 1.1 mrg L(0000):subs n, n, #16 108 1.1 mrg blo L(e0) 109 1.1 mrg 110 1.1 mrg vld1.32 {q2,q3}, [ap]! C load 8 limbs 111 1.1 mrg vld1.32 {q0,q1}, [ap]! C load 8 limbs 112 1.1 mrg vcnt.8 q12, q2 113 1.1 mrg vcnt.8 q13, q3 114 1.1 mrg subs n, n, #16 115 1.1 mrg blo L(end) 116 1.1 mrg 117 1.1 mrg L(top): vld1.32 {q2,q3}, [ap]! C load 8 limbs 118 1.1 mrg vpadal.u8 q8, q12 119 1.1 mrg vcnt.8 q12, q0 120 1.1 mrg vpadal.u8 q9, q13 121 1.1 mrg vcnt.8 q13, q1 122 1.1 mrg L(mid): vld1.32 {q0,q1}, [ap]! C load 8 limbs 123 1.1 mrg subs n, n, #16 124 1.1 mrg vpadal.u8 q8, q12 125 1.1 mrg vcnt.8 q12, q2 126 1.1 mrg vpadal.u8 q9, q13 127 1.1 mrg vcnt.8 q13, q3 128 1.1 mrg bhs L(top) 129 1.1 mrg 130 1.1 mrg L(end): vpadal.u8 q8, q12 131 1.1 mrg vpadal.u8 q9, q13 132 1.1 mrg L(sum): vcnt.8 q12, q0 133 1.1 mrg vcnt.8 q13, q1 134 1.1 mrg vpadal.u8 q8, q12 135 1.1 mrg vpadal.u8 q9, q13 136 1.1 mrg vadd.i16 q8, q8, q9 137 1.1 mrg C we have 8 16-bit counts 138 1.1 mrg L(e0): vpaddl.u16 q8, q8 C we have 4 32-bit counts 139 1.1 mrg vpaddl.u32 q8, q8 C we have 2 64-bit counts 140 1.1 mrg vmov.32 r0, d16[0] 141 1.1 mrg vmov.32 r1, d17[0] 142 1.1 mrg add r0, r0, r1 143 1.1 mrg bx lr 144 1.1 mrg 145 1.1 mrg C Code for large count. Splits operand and calls above code. 146 1.1 mrg define(`ap2', r2) C caller-saves reg not used above 147 1.1 mrg L(gt16k): 148 1.1 mrg push {r4,r14} 149 1.1 mrg mov ap2, ap 150 1.1 mrg mov r3, n C full count 151 1.1 mrg mov r4, #0 C total sum 152 1.1 mrg 153 1.1 mrg 1: mov n, #chunksize C count for this invocation 154 1.1 mrg bl L(lt16k) C could jump deep inside code 155 1.1 mrg add ap2, ap2, #chunksize*4 C point at next chunk 156 1.1 mrg add r4, r4, r0 157 1.1 mrg mov ap, ap2 C put chunk pointer in place for call 158 1.1 mrg sub r3, r3, #chunksize 159 1.1 mrg cmp r3, #chunksize 160 1.1 mrg bhi 1b 161 1.1 mrg 162 1.1 mrg mov n, r3 C count for final invocation 163 1.1 mrg bl L(lt16k) 164 1.1 mrg add r0, r4, r0 165 1.1 mrg pop {r4,pc} 166 1.1 mrg EPILOGUE() 167
Indexes created Tue Oct 06 00:26:07 UTC 2026