Annotation of OpenXM_contrib/gmp/mpn/x86/p6/mod_1.asm, Revision 1.1
1.1 ! ohara 1: dnl Intel P6 mpn_mod_1 -- mpn by limb remainder.
! 2:
! 3: dnl Copyright 1999, 2000, 2002 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: include(`../config.m4')
! 23:
! 24:
! 25: C P6: 21.5 cycles/limb
! 26:
! 27:
! 28: C mp_limb_t mpn_mod_1 (mp_srcptr src, mp_size_t size, mp_limb_t divisor);
! 29: C mp_limb_t mpn_mod_1c (mp_srcptr src, mp_size_t size, mp_limb_t divisor,
! 30: C mp_limb_t carry);
! 31: C mp_limb_t mpn_preinv_mod_1 (mp_srcptr src, mp_size_t size, mp_limb_t divisor,
! 32: C mp_limb_t inverse);
! 33: C
! 34: C The code here is in two parts, a simple divl loop and a mul-by-inverse.
! 35: C The divl is used by mod_1 and mod_1c for small sizes, until the savings in
! 36: C the mul-by-inverse can overcome the time to calculate an inverse.
! 37: C preinv_mod_1 goes straight to the mul-by-inverse.
! 38: C
! 39: C The mul-by-inverse normalizes the divisor (or for preinv_mod_1 it's
! 40: C already normalized). The calculation done is r=a%(d*2^n) followed by a
! 41: C final (r*2^n)%(d*2^n), where a is the dividend, d the divisor, and n is
! 42: C the number of leading zero bits on d. This means there's no bit shifts in
! 43: C the main loop, at the cost of an extra divide step at the end.
! 44: C
! 45: C The simple divl for mod_1 is able to skip one divide step if high<divisor.
! 46: C For mod_1c the carry parameter is the high of the first divide step, and
! 47: C no attempt is make to skip that step since carry==0 will be very rare.
! 48: C
! 49: C The mul-by-inverse always skips one divide step, but then needs an extra
! 50: C step at the end, unless the divisor was already normalized (n==0). This
! 51: C leads to different mul-by-inverse thresholds for normalized and
! 52: C unnormalized divisors, in mod_1 and mod_1c.
! 53: C
! 54: C Alternatives:
! 55: C
! 56: C If n is small then the extra divide step could be done by a few shift and
! 57: C trial subtract steps instead of a full divide. That would probably be 3
! 58: C or 4 cycles/bit, so say up to n=8 might benefit from that over a 21 cycle
! 59: C divide. However it's considered that small divisors, meaning biggish n,
! 60: C are more likely than small n, and that it's not worth the branch
! 61: C mispredicts of a loop.
! 62: C
! 63: C Past:
! 64: C
! 65: C There used to be some MMX based code for P-II and P-III, roughly following
! 66: C the K7 form, but it was slower (about 24.0 c/l) than the code here. That
! 67: C code did have an advantage that mod_1 was able to do one less divide step
! 68: C when high<divisor and the divisor unnormalized, but the speed advantage of
! 69: C the current code soon overcomes that.
! 70: C
! 71: C Future:
! 72: C
! 73: C It's not clear whether what's here is optimal. A rough count of micro-ops
! 74: C on the dependent chain would suggest a couple of cycles could be shaved,
! 75: C perhaps.
! 76:
! 77:
! 78: dnl The following thresholds are the sizes where the multiply by inverse
! 79: dnl method is used instead of plain divl's. Minimum value 2 each.
! 80: dnl
! 81: dnl MUL_NORM_THRESHOLD is for normalized divisors (high bit set),
! 82: dnl MUL_UNNORM_THRESHOLD for unnormalized divisors.
! 83: dnl
! 84: dnl With the divl loop at 39 c/l, and the inverse loop at 21.5 c/l but
! 85: dnl setups for the inverse of about 50, the threshold should be around
! 86: dnl 50/(39-21.5)==2.85. An unnormalized divisor gets an extra divide step
! 87: dnl at the end, so if that's about 25 cycles then that threshold might be
! 88: dnl around (50+25)/(39-21.5) == 4.3.
! 89:
! 90: deflit(MUL_NORM_THRESHOLD, 4)
! 91: deflit(MUL_UNNORM_THRESHOLD, 5)
! 92:
! 93: deflit(MUL_NORM_DELTA, eval(MUL_NORM_THRESHOLD - MUL_UNNORM_THRESHOLD))
! 94:
! 95:
! 96: defframe(PARAM_INVERSE, 16) dnl mpn_preinv_mod_1
! 97: defframe(PARAM_CARRY, 16) dnl mpn_mod_1c
! 98: defframe(PARAM_DIVISOR, 12)
! 99: defframe(PARAM_SIZE, 8)
! 100: defframe(PARAM_SRC, 4)
! 101:
! 102: defframe(SAVE_EBX, -4)
! 103: defframe(SAVE_ESI, -8)
! 104: defframe(SAVE_EDI, -12)
! 105: defframe(SAVE_EBP, -16)
! 106:
! 107: defframe(VAR_NORM, -20)
! 108: defframe(VAR_INVERSE, -24)
! 109:
! 110: deflit(STACK_SPACE, 24)
! 111:
! 112: TEXT
! 113:
! 114: ALIGN(16)
! 115: PROLOGUE(mpn_preinv_mod_1)
! 116: deflit(`FRAME',0)
! 117:
! 118: movl PARAM_SRC, %edx
! 119: subl $STACK_SPACE, %esp FRAME_subl_esp(STACK_SPACE)
! 120:
! 121: movl %ebx, SAVE_EBX
! 122: movl PARAM_SIZE, %ebx
! 123:
! 124: movl %ebp, SAVE_EBP
! 125: movl PARAM_DIVISOR, %ebp
! 126:
! 127: movl %esi, SAVE_ESI
! 128: movl PARAM_INVERSE, %eax
! 129:
! 130: movl %edi, SAVE_EDI
! 131: movl -4(%edx,%ebx,4), %edi C src high limb
! 132:
! 133: movl $0, VAR_NORM
! 134: leal -8(%edx,%ebx,4), %ecx C &src[size-2]
! 135:
! 136: C
! 137:
! 138: movl %edi, %esi
! 139: subl %ebp, %edi C high-divisor
! 140:
! 141: cmovc( %esi, %edi) C restore if underflow
! 142: decl %ebx
! 143: jnz L(preinv_entry)
! 144:
! 145: jmp L(done_edi)
! 146:
! 147: EPILOGUE()
! 148:
! 149:
! 150: ALIGN(16)
! 151: PROLOGUE(mpn_mod_1c)
! 152: deflit(`FRAME',0)
! 153:
! 154: movl PARAM_SIZE, %ecx
! 155: subl $STACK_SPACE, %esp FRAME_subl_esp(STACK_SPACE)
! 156:
! 157: movl %ebp, SAVE_EBP
! 158: movl PARAM_DIVISOR, %eax
! 159:
! 160: movl %esi, SAVE_ESI
! 161: movl PARAM_CARRY, %edx
! 162:
! 163: movl PARAM_SRC, %esi
! 164: orl %ecx, %ecx
! 165: jz L(done_edx) C result==carry if size==0
! 166:
! 167: sarl $31, %eax
! 168: movl PARAM_DIVISOR, %ebp
! 169:
! 170: andl $MUL_NORM_DELTA, %eax
! 171:
! 172: addl $MUL_UNNORM_THRESHOLD, %eax
! 173:
! 174: cmpl %eax, %ecx
! 175: jb L(divide_top)
! 176:
! 177:
! 178: C The carry parameter pretends to be the src high limb.
! 179:
! 180: movl %ebx, SAVE_EBX
! 181: leal 1(%ecx), %ebx C size+1
! 182:
! 183: movl %edx, %eax C carry
! 184: jmp L(mul_by_inverse_1c)
! 185:
! 186: EPILOGUE()
! 187:
! 188:
! 189: ALIGN(16)
! 190: PROLOGUE(mpn_mod_1)
! 191: deflit(`FRAME',0)
! 192:
! 193: movl PARAM_SIZE, %ecx
! 194: subl $STACK_SPACE, %esp FRAME_subl_esp(STACK_SPACE)
! 195: movl $0, %edx C initial carry (if can't skip a div)
! 196:
! 197: movl %esi, SAVE_ESI
! 198: movl PARAM_SRC, %eax
! 199:
! 200: movl %ebp, SAVE_EBP
! 201: movl PARAM_DIVISOR, %ebp
! 202:
! 203: movl PARAM_DIVISOR, %esi
! 204: orl %ecx, %ecx
! 205: jz L(done_edx)
! 206:
! 207: movl -4(%eax,%ecx,4), %eax C src high limb
! 208:
! 209: sarl $31, %ebp
! 210:
! 211: andl $MUL_NORM_DELTA, %ebp
! 212:
! 213: addl $MUL_UNNORM_THRESHOLD, %ebp
! 214: cmpl %esi, %eax C carry flag if high<divisor
! 215:
! 216: cmovc( %eax, %edx) C src high limb as initial carry
! 217: movl PARAM_SRC, %esi
! 218:
! 219: sbbl $0, %ecx C size-1 to skip one div
! 220: jz L(done_eax) C done if had size==1
! 221:
! 222: cmpl %ebp, %ecx
! 223: movl PARAM_DIVISOR, %ebp
! 224: jae L(mul_by_inverse)
! 225:
! 226:
! 227: L(divide_top):
! 228: C eax scratch (quotient)
! 229: C ebx
! 230: C ecx counter, limbs, decrementing
! 231: C edx scratch (remainder)
! 232: C esi src
! 233: C edi
! 234: C ebp divisor
! 235:
! 236: movl -4(%esi,%ecx,4), %eax
! 237:
! 238: divl %ebp
! 239:
! 240: decl %ecx
! 241: jnz L(divide_top)
! 242:
! 243:
! 244: L(done_edx):
! 245: movl %edx, %eax
! 246: L(done_eax):
! 247: movl SAVE_ESI, %esi
! 248:
! 249: movl SAVE_EBP, %ebp
! 250: addl $STACK_SPACE, %esp
! 251:
! 252: ret
! 253:
! 254:
! 255: C -----------------------------------------------------------------------------
! 256:
! 257: L(mul_by_inverse):
! 258: C eax src high limb
! 259: C ebx
! 260: C ecx
! 261: C edx
! 262: C esi src
! 263: C edi
! 264: C ebp divisor
! 265:
! 266: movl %ebx, SAVE_EBX
! 267: movl PARAM_SIZE, %ebx
! 268:
! 269: L(mul_by_inverse_1c):
! 270: bsrl %ebp, %ecx C 31-l
! 271:
! 272: movl %edi, SAVE_EDI
! 273: xorl $31, %ecx C l
! 274:
! 275: movl %ecx, VAR_NORM
! 276: shll %cl, %ebp C d normalized
! 277:
! 278: movl %eax, %edi C src high -> n2
! 279: subl %ebp, %eax
! 280:
! 281: cmovnc( %eax, %edi) C n2-divisor if no underflow
! 282:
! 283: movl $-1, %eax
! 284: movl $-1, %edx
! 285:
! 286: subl %ebp, %edx C (b-d)-1 so edx:eax = b*(b-d)-1
! 287: leal -8(%esi,%ebx,4), %ecx C &src[size-2]
! 288:
! 289: divl %ebp C floor (b*(b-d)-1) / d
! 290:
! 291: L(preinv_entry):
! 292: movl %eax, VAR_INVERSE
! 293:
! 294:
! 295:
! 296: C No special scheduling of loads is necessary in this loop, out of order
! 297: C execution hides the latencies already.
! 298: C
! 299: C The way q1+1 is generated in %ebx and d is moved to %eax for the multiply
! 300: C seems fastest. The obvious change to generate q1+1 in %eax and then just
! 301: C multiply by %ebp (as per mpn/x86/pentium/mod_1.asm in fact) runs 1 cycle
! 302: C slower, for no obvious reason.
! 303:
! 304:
! 305: ALIGN(16)
! 306: L(inverse_top):
! 307: C eax n10 (then scratch)
! 308: C ebx scratch (nadj, q1)
! 309: C ecx src pointer, decrementing
! 310: C edx scratch
! 311: C esi n10
! 312: C edi n2
! 313: C ebp divisor
! 314:
! 315: movl (%ecx), %eax C next src limb
! 316: movl %eax, %esi
! 317:
! 318: sarl $31, %eax C -n1
! 319: movl %ebp, %ebx
! 320:
! 321: andl %eax, %ebx C -n1 & d
! 322: negl %eax C n1
! 323:
! 324: addl %edi, %eax C n2+n1
! 325:
! 326: mull VAR_INVERSE C m*(n2+n1)
! 327:
! 328: addl %esi, %ebx C nadj = n10 + (-n1 & d), ignoring overflow
! 329: subl $4, %ecx
! 330:
! 331: C
! 332:
! 333: addl %ebx, %eax C m*(n2+n1) + nadj, low giving carry flag
! 334: leal 1(%edi), %ebx C n2+1
! 335: movl %ebp, %eax C d
! 336:
! 337: adcl %edx, %ebx C 1 + high(n2<<32 + m*(n2+n1) + nadj) = q1+1
! 338: jz L(q1_ff)
! 339:
! 340: mull %ebx C (q1+1)*d
! 341:
! 342: C
! 343:
! 344: subl %eax, %esi C low n - (q1+1)*d
! 345:
! 346: sbbl %edx, %edi C high n - (q1+1)*d, 0 or -1
! 347:
! 348: andl %ebp, %edi C d if underflow
! 349:
! 350: addl %esi, %edi C remainder with addback if necessary
! 351:
! 352: cmpl PARAM_SRC, %ecx
! 353: jae L(inverse_top)
! 354:
! 355:
! 356: C -----------------------------------------------------------------------------
! 357: L(inverse_loop_done):
! 358:
! 359: C %edi is the remainder modulo d*2^n and now must be reduced to
! 360: C 0<=r<d by calculating r*2^n mod d*2^n and then right shifting by
! 361: C n. If d was already normalized on entry so that n==0 then nothing
! 362: C is needed here. The chance of n==0 is low, but it's true of say
! 363: C PP from gmp-impl.h.
! 364: C
! 365: C eax
! 366: C ebx
! 367: C ecx
! 368: C edx
! 369: C esi
! 370: C edi remainder
! 371: C ebp divisor (normalized)
! 372:
! 373: movl VAR_NORM, %ecx
! 374: movl $0, %esi
! 375:
! 376: orl %ecx, %ecx
! 377: jz L(done_edi)
! 378:
! 379:
! 380: C Here use %edi=n10 and %esi=n2, opposite to the loop above.
! 381: C
! 382: C The q1=0xFFFFFFFF case is handled with an sbbl to adjust q1+1
! 383: C back, rather than q1_ff special case code. This is simpler and
! 384: C costs only 2 uops.
! 385:
! 386: shldl( %cl, %edi, %esi)
! 387:
! 388: shll %cl, %edi
! 389:
! 390: movl %edi, %eax C n10
! 391: movl %ebp, %ebx C d
! 392:
! 393: sarl $31, %eax C -n1
! 394:
! 395: andl %eax, %ebx C -n1 & d
! 396: negl %eax C n1
! 397:
! 398: addl %edi, %ebx C nadj = n10 + (-n1 & d), ignoring overflow
! 399: addl %esi, %eax C n2+n1
! 400:
! 401: mull VAR_INVERSE C m*(n2+n1)
! 402:
! 403: C
! 404:
! 405: addl %ebx, %eax C m*(n2+n1) + nadj, low giving carry flag
! 406: leal 1(%esi), %ebx C n2+1
! 407:
! 408: adcl %edx, %ebx C 1 + high(n2<<32 + m*(n2+n1) + nadj) = q1+1
! 409:
! 410: sbbl $0, %ebx
! 411: movl %ebp, %eax C d
! 412:
! 413: mull %ebx C (q1+1)*d
! 414:
! 415: movl SAVE_EBX, %ebx
! 416:
! 417: C
! 418:
! 419: subl %eax, %edi C low n - (q1+1)*d is remainder
! 420:
! 421: sbbl %edx, %esi C high n - (q1+1)*d, 0 or -1
! 422:
! 423: andl %ebp, %esi
! 424: movl SAVE_EBP, %ebp
! 425:
! 426: leal (%esi,%edi), %eax C remainder
! 427: movl SAVE_ESI, %esi
! 428:
! 429: shrl %cl, %eax C denorm remainder
! 430: movl SAVE_EDI, %edi
! 431: addl $STACK_SPACE, %esp
! 432:
! 433: ret
! 434:
! 435:
! 436: L(done_edi):
! 437: movl SAVE_EBX, %ebx
! 438: movl %edi, %eax
! 439:
! 440: movl SAVE_ESI, %esi
! 441:
! 442: movl SAVE_EDI, %edi
! 443:
! 444: movl SAVE_EBP, %ebp
! 445: addl $STACK_SPACE, %esp
! 446:
! 447: ret
! 448:
! 449:
! 450: C -----------------------------------------------------------------------------
! 451: C
! 452: C Special case for q1=0xFFFFFFFF, giving q=0xFFFFFFFF meaning the low dword
! 453: C of q*d is simply -d and the remainder n-q*d = n10+d.
! 454: C
! 455: C This is reached only very rarely.
! 456:
! 457: L(q1_ff):
! 458: C eax (divisor)
! 459: C ebx (q1+1 == 0)
! 460: C ecx src pointer
! 461: C edx
! 462: C esi n10
! 463: C edi (n2)
! 464: C ebp divisor
! 465:
! 466: leal (%ebp,%esi), %edi C n-q*d remainder -> next n2
! 467:
! 468: cmpl PARAM_SRC, %ecx
! 469: jae L(inverse_top)
! 470:
! 471: jmp L(inverse_loop_done)
! 472:
! 473:
! 474: EPILOGUE()
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to mod_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 / p6