1dnl AMD K6 mpn_divrem_1 -- mpn by limb division. 2 3dnl Copyright 1999-2003, 2007 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 33 34C K6: 20 cycles/limb 35 36 37C mp_limb_t mpn_divrem_1 (mp_ptr dst, mp_size_t xsize, 38C mp_srcptr src, mp_size_t size, mp_limb_t divisor); 39C mp_limb_t mpn_divrem_1c (mp_ptr dst, mp_size_t xsize, 40C mp_srcptr src, mp_size_t size, mp_limb_t divisor, 41C mp_limb_t carry); 42C 43C The code here is basically the same as mpn/x86/divrem_1.asm, but uses loop 44C instead of decl+jnz, since it comes out 2 cycles/limb faster. 45C 46C A test is done to see if the high limb is less than the divisor, and if so 47C one less div is done. A div is 20 cycles, so assuming high<divisor about 48C half the time, then this test saves half that amount. The branch 49C misprediction penalty is less than that. 50C 51C Back-to-back div instructions run at 20 cycles, the same as the loop here, 52C so it seems there's nothing to gain by rearranging the loop. Pairing the 53C mov and loop instructions was found to gain nothing. 54C 55C Enhancements: 56C 57C The low-latency K6 multiply might be thought to suit a mul-by-inverse, but 58C that algorithm has been found to suffer from the relatively poor carry 59C handling on K6 and too many auxiliary instructions. The fractional part 60C however could be done at about 13 c/l, if it mattered enough. 61 62defframe(PARAM_CARRY, 24) 63defframe(PARAM_DIVISOR,20) 64defframe(PARAM_SIZE, 16) 65defframe(PARAM_SRC, 12) 66defframe(PARAM_XSIZE, 8) 67defframe(PARAM_DST, 4) 68 69 TEXT 70 71 ALIGN(32) 72PROLOGUE(mpn_divrem_1c) 73deflit(`FRAME',0) 74 75 movl PARAM_SIZE, %ecx 76 pushl %edi FRAME_pushl() 77 78 movl PARAM_SRC, %edi 79 pushl %esi FRAME_pushl() 80 81 movl PARAM_DIVISOR, %esi 82 pushl %ebx FRAME_pushl() 83 84 movl PARAM_DST, %ebx 85 pushl %ebp FRAME_pushl() 86 87 movl PARAM_XSIZE, %ebp 88 orl %ecx, %ecx C size 89 90 movl PARAM_CARRY, %edx 91 jz L(fraction) C if size==0 92 93 leal -4(%ebx,%ebp,4), %ebx C dst one limb below integer part 94 jmp L(integer_top) 95 96EPILOGUE() 97 98 99 ALIGN(16) 100PROLOGUE(mpn_divrem_1) 101deflit(`FRAME',0) 102 103 movl PARAM_SIZE, %ecx 104 pushl %edi FRAME_pushl() 105 106 movl PARAM_SRC, %edi 107 pushl %esi FRAME_pushl() 108 109 movl PARAM_DIVISOR, %esi 110 orl %ecx,%ecx C size 111 112 jz L(size_zero) 113 pushl %ebx FRAME_pushl() 114 115 movl -4(%edi,%ecx,4), %eax C src high limb 116 xorl %edx, %edx 117 118 movl PARAM_DST, %ebx 119 pushl %ebp FRAME_pushl() 120 121 movl PARAM_XSIZE, %ebp 122 cmpl %esi, %eax 123 124 leal -4(%ebx,%ebp,4), %ebx C dst one limb below integer part 125 jae L(integer_entry) 126 127 128 C high<divisor, so high of dst is zero, and avoid one div 129 130 movl %edx, (%ebx,%ecx,4) 131 decl %ecx 132 133 movl %eax, %edx 134 jz L(fraction) 135 136 137L(integer_top): 138 C eax scratch (quotient) 139 C ebx dst+4*xsize-4 140 C ecx counter 141 C edx scratch (remainder) 142 C esi divisor 143 C edi src 144 C ebp xsize 145 146 movl -4(%edi,%ecx,4), %eax 147L(integer_entry): 148 149 divl %esi 150 151 movl %eax, (%ebx,%ecx,4) 152 loop L(integer_top) 153 154 155L(fraction): 156 orl %ebp, %ecx 157 jz L(done) 158 159 movl PARAM_DST, %ebx 160 161 162L(fraction_top): 163 C eax scratch (quotient) 164 C ebx dst 165 C ecx counter 166 C edx scratch (remainder) 167 C esi divisor 168 C edi 169 C ebp 170 171 xorl %eax, %eax 172 173 divl %esi 174 175 movl %eax, -4(%ebx,%ecx,4) 176 loop L(fraction_top) 177 178 179L(done): 180 popl %ebp 181 movl %edx, %eax 182 popl %ebx 183 popl %esi 184 popl %edi 185 ret 186 187 188L(size_zero): 189deflit(`FRAME',8) 190 movl PARAM_XSIZE, %ecx 191 xorl %eax, %eax 192 193 movl PARAM_DST, %edi 194 195 cld C better safe than sorry, see mpn/x86/README 196 197 rep 198 stosl 199 200 popl %esi 201 popl %edi 202 ret 203EPILOGUE() 204