Annotation of OpenXM_contrib/gmp/mpn/x86/divrem_1.asm, Revision 1.1
1.1 ! maekawa 1: dnl x86 mpn_divrem_1 -- mpn by limb division extending to fractional quotient.
! 2:
! 3: dnl Copyright (C) 1999, 2000 Free Software Foundation, Inc.
! 4: dnl
! 5: dnl This file is part of the GNU MP Library.
! 6: dnl
! 7: dnl The GNU MP Library is free software; you can redistribute it and/or
! 8: dnl modify it under the terms of the GNU Lesser General Public License as
! 9: dnl published by the Free Software Foundation; either version 2.1 of the
! 10: dnl License, or (at your option) any later version.
! 11: dnl
! 12: dnl The GNU MP Library is distributed in the hope that it will be useful,
! 13: dnl but WITHOUT ANY WARRANTY; without even the implied warranty of
! 14: dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
! 15: dnl Lesser General Public License for more details.
! 16: dnl
! 17: dnl You should have received a copy of the GNU Lesser General Public
! 18: dnl License along with the GNU MP Library; see the file COPYING.LIB. If
! 19: dnl not, write to the Free Software Foundation, Inc., 59 Temple Place -
! 20: dnl Suite 330, Boston, MA 02111-1307, USA.
! 21:
! 22:
! 23: dnl cycles/limb
! 24: dnl K6 20
! 25: dnl P5 44
! 26: dnl P6 39
! 27: dnl 486 approx 43 maybe
! 28: dnl
! 29: dnl
! 30: dnl The following have their own optimized divrem_1 implementations, but
! 31: dnl for reference the code here runs as follows.
! 32: dnl
! 33: dnl cycles/limb
! 34: dnl P6MMX 39
! 35: dnl K7 42
! 36:
! 37:
! 38: include(`../config.m4')
! 39:
! 40:
! 41: C mp_limb_t mpn_divrem_1 (mp_ptr dst, mp_size_t xsize,
! 42: C mp_srcptr src, mp_size_t size, mp_limb_t divisor);
! 43: C mp_limb_t mpn_divrem_1c (mp_ptr dst, mp_size_t xsize,
! 44: C mp_srcptr src, mp_size_t size, mp_limb_t divisor);
! 45: C
! 46: C Divide src,size by divisor and store the quotient in dst+xsize,size.
! 47: C Extend the division to fractional quotient limbs in dst,xsize. Return the
! 48: C remainder. Either or both xsize and size can be 0.
! 49: C
! 50: C mpn_divrem_1c takes a carry parameter which is an initial high limb,
! 51: C effectively one extra limb at the top of src,size. Must have
! 52: C carry<divisor.
! 53: C
! 54: C
! 55: C Essentially the code is the same as the division based part of
! 56: C mpn/generic/divrem_1.c, but has the following advantages.
! 57: C
! 58: C - If gcc isn't being used then divrem_1.c will get the generic C
! 59: C udiv_qrnnd() and be rather slow.
! 60: C
! 61: C - On K6, using the loop instruction is a 10% speedup, but gcc doesn't
! 62: C generate that instruction (as of gcc 2.95.2 at least).
! 63: C
! 64: C A test is done to see if the high limb is less the the divisor, and if so
! 65: C one less div is done. A div is between 20 and 40 cycles on the various
! 66: C x86s, so assuming high<divisor about half the time, then this test saves
! 67: C half that amount. The branch misprediction penalty on each chip is less
! 68: C than half a div.
! 69: C
! 70: C
! 71: C K6: Back-to-back div instructions run at 20 cycles, the same as the loop
! 72: C here, so it seems there's nothing to gain by rearranging the loop.
! 73: C Pairing the mov and loop instructions was found to gain nothing. (The
! 74: C same is true of the mpn/x86/mod_1.asm loop.)
! 75: C
! 76: C With a "decl/jnz" rather than a "loop" this code runs at 22 cycles.
! 77: C The loop_or_decljnz macro is an easy way to get a 10% speedup.
! 78: C
! 79: C The fast K6 multiply might be thought to suit a multiply-by-inverse,
! 80: C but that algorithm has been found to suffer from the releatively poor
! 81: C carry handling on K6 and too many auxiliary instructions. The
! 82: C fractional part however could be done at about 13 c/l.
! 83: C
! 84: C P5: Moving the load down to pair with the store might save 1 cycle, but
! 85: C that doesn't seem worth bothering with, since it'd be only a 2.2%
! 86: C saving.
! 87: C
! 88: C Again here the auxiliary instructions hinder a multiply-by-inverse,
! 89: C though there might be a 10-15% speedup available
! 90:
! 91:
! 92: defframe(PARAM_CARRY, 24)
! 93: defframe(PARAM_DIVISOR,20)
! 94: defframe(PARAM_SIZE, 16)
! 95: defframe(PARAM_SRC, 12)
! 96: defframe(PARAM_XSIZE, 8)
! 97: defframe(PARAM_DST, 4)
! 98:
! 99: .text
! 100: ALIGN(16)
! 101:
! 102: PROLOGUE(mpn_divrem_1c)
! 103: deflit(`FRAME',0)
! 104:
! 105: movl PARAM_SIZE, %ecx
! 106: pushl %edi FRAME_pushl()
! 107:
! 108: movl PARAM_SRC, %edi
! 109: pushl %esi FRAME_pushl()
! 110:
! 111: movl PARAM_DIVISOR, %esi
! 112: pushl %ebx FRAME_pushl()
! 113:
! 114: movl PARAM_DST, %ebx
! 115: pushl %ebp FRAME_pushl()
! 116:
! 117: movl PARAM_XSIZE, %ebp
! 118: orl %ecx, %ecx
! 119:
! 120: movl PARAM_CARRY, %edx
! 121: jz LF(mpn_divrem_1,fraction)
! 122:
! 123: leal -4(%ebx,%ebp,4), %ebx C dst one limb below integer part
! 124: jmp LF(mpn_divrem_1,integer_top)
! 125:
! 126: EPILOGUE()
! 127:
! 128:
! 129: PROLOGUE(mpn_divrem_1)
! 130: deflit(`FRAME',0)
! 131:
! 132: movl PARAM_SIZE, %ecx
! 133: pushl %edi FRAME_pushl()
! 134:
! 135: movl PARAM_SRC, %edi
! 136: pushl %esi FRAME_pushl()
! 137:
! 138: movl PARAM_DIVISOR, %esi
! 139: orl %ecx,%ecx
! 140:
! 141: jz L(size_zero)
! 142: pushl %ebx FRAME_pushl()
! 143:
! 144: movl -4(%edi,%ecx,4), %eax C src high limb
! 145: xorl %edx, %edx
! 146:
! 147: movl PARAM_DST, %ebx
! 148: pushl %ebp FRAME_pushl()
! 149:
! 150: movl PARAM_XSIZE, %ebp
! 151: cmpl %esi, %eax
! 152:
! 153: leal -4(%ebx,%ebp,4), %ebx C dst one limb below integer part
! 154: jae L(integer_entry)
! 155:
! 156:
! 157: C high<divisor, so high of dst is zero, and avoid one div
! 158:
! 159: movl %edx, (%ebx,%ecx,4)
! 160: decl %ecx
! 161:
! 162: movl %eax, %edx
! 163: jz L(fraction)
! 164:
! 165:
! 166: L(integer_top):
! 167: C eax scratch (quotient)
! 168: C ebx dst+4*xsize-4
! 169: C ecx counter
! 170: C edx scratch (remainder)
! 171: C esi divisor
! 172: C edi src
! 173: C ebp xsize
! 174:
! 175: movl -4(%edi,%ecx,4), %eax
! 176: L(integer_entry):
! 177:
! 178: divl %esi
! 179:
! 180: movl %eax, (%ebx,%ecx,4)
! 181: loop_or_decljnz L(integer_top)
! 182:
! 183:
! 184: L(fraction):
! 185: orl %ebp, %ecx
! 186: jz L(done)
! 187:
! 188: movl PARAM_DST, %ebx
! 189:
! 190:
! 191: L(fraction_top):
! 192: C eax scratch (quotient)
! 193: C ebx dst
! 194: C ecx counter
! 195: C edx scratch (remainder)
! 196: C esi divisor
! 197: C edi
! 198: C ebp
! 199:
! 200: xorl %eax, %eax
! 201:
! 202: divl %esi
! 203:
! 204: movl %eax, -4(%ebx,%ecx,4)
! 205: loop_or_decljnz L(fraction_top)
! 206:
! 207:
! 208: L(done):
! 209: popl %ebp
! 210: movl %edx, %eax
! 211: popl %ebx
! 212: popl %esi
! 213: popl %edi
! 214: ret
! 215:
! 216:
! 217: L(size_zero):
! 218: deflit(`FRAME',8)
! 219: movl PARAM_XSIZE, %ecx
! 220: xorl %eax, %eax
! 221:
! 222: movl PARAM_DST, %edi
! 223:
! 224: cld C better safe than sorry, see mpn/x86/README.family
! 225:
! 226: rep
! 227: stosl
! 228:
! 229: popl %esi
! 230: popl %edi
! 231: ret
! 232: EPILOGUE()
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to divrem_1.asm CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / mpn / x86