![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rshift.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 / pentium / mmx|
Return to rshift.asm CVS log | Up to [local] / OpenXM_contrib / gmp / mpn / x86 / pentium / mmx |
1.1 ! maekawa 1: dnl Intel P5 mpn_rshift -- mpn right shift.
! 2: dnl
! 3: dnl P5: 1.75 cycles/limb.
! 4:
! 5:
! 6: dnl Copyright (C) 2000 Free Software Foundation, Inc.
! 7: dnl
! 8: dnl This file is part of the GNU MP Library.
! 9: dnl
! 10: dnl The GNU MP Library is free software; you can redistribute it and/or
! 11: dnl modify it under the terms of the GNU Lesser General Public License as
! 12: dnl published by the Free Software Foundation; either version 2.1 of the
! 13: dnl License, or (at your option) any later version.
! 14: dnl
! 15: dnl The GNU MP Library is distributed in the hope that it will be useful,
! 16: dnl but WITHOUT ANY WARRANTY; without even the implied warranty of
! 17: dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
! 18: dnl Lesser General Public License for more details.
! 19: dnl
! 20: dnl You should have received a copy of the GNU Lesser General Public
! 21: dnl License along with the GNU MP Library; see the file COPYING.LIB. If
! 22: dnl not, write to the Free Software Foundation, Inc., 59 Temple Place -
! 23: dnl Suite 330, Boston, MA 02111-1307, USA.
! 24:
! 25:
! 26: include(`../config.m4')
! 27:
! 28:
! 29: C mp_limb_t mpn_rshift (mp_ptr dst, mp_srcptr src, mp_size_t size,
! 30: C unsigned shift);
! 31: C
! 32: C Shift src,size right by shift many bits and store the result in dst,size.
! 33: C Zeros are shifted in at the left. Return the bits shifted out at the
! 34: C right.
! 35: C
! 36: C It takes 6 mmx instructions to process 2 limbs, making 1.5 cycles/limb,
! 37: C and with a 4 limb loop and 1 cycle of loop overhead the total is 1.75 c/l.
! 38: C
! 39: C Full speed depends on source and destination being aligned. Unaligned mmx
! 40: C loads and stores on P5 don't pair and have a 2 cycle penalty. Some hairy
! 41: C setups and finish-ups are done to ensure alignment for the loop.
! 42: C
! 43: C MMX shifts work out a bit faster even for the simple loop.
! 44:
! 45: defframe(PARAM_SHIFT,16)
! 46: defframe(PARAM_SIZE, 12)
! 47: defframe(PARAM_SRC, 8)
! 48: defframe(PARAM_DST, 4)
! 49: deflit(`FRAME',0)
! 50:
! 51: dnl Minimum 5, because the unrolled loop can't handle less.
! 52: deflit(UNROLL_THRESHOLD, 5)
! 53:
! 54: .text
! 55: ALIGN(8)
! 56:
! 57: PROLOGUE(mpn_rshift)
! 58:
! 59: pushl %ebx
! 60: pushl %edi
! 61: deflit(`FRAME',8)
! 62:
! 63: movl PARAM_SIZE, %eax
! 64: movl PARAM_DST, %edx
! 65:
! 66: movl PARAM_SRC, %ebx
! 67: movl PARAM_SHIFT, %ecx
! 68:
! 69: cmp $UNROLL_THRESHOLD, %eax
! 70: jae L(unroll)
! 71:
! 72: decl %eax
! 73: movl (%ebx), %edi C src low limb
! 74:
! 75: jnz L(simple)
! 76:
! 77: shrdl( %cl, %edi, %eax) C eax was decremented to zero
! 78:
! 79: shrl %cl, %edi
! 80:
! 81: movl %edi, (%edx) C dst low limb
! 82: popl %edi C risk of data cache bank clash
! 83:
! 84: popl %ebx
! 85:
! 86: ret
! 87:
! 88:
! 89: C -----------------------------------------------------------------------------
! 90: ALIGN(8)
! 91: L(simple):
! 92: C eax size-1
! 93: C ebx src
! 94: C ecx shift
! 95: C edx dst
! 96: C esi
! 97: C edi
! 98: C ebp
! 99: deflit(`FRAME',8)
! 100:
! 101: movd (%ebx), %mm5 C src[0]
! 102: leal (%ebx,%eax,4), %ebx C &src[size-1]
! 103:
! 104: movd %ecx, %mm6 C rshift
! 105: leal -4(%edx,%eax,4), %edx C &dst[size-2]
! 106:
! 107: psllq $32, %mm5
! 108: negl %eax
! 109:
! 110:
! 111: C This loop is 5 or 8 cycles, with every second load unaligned and a wasted
! 112: C cycle waiting for the mm0 result to be ready. For comparison a shrdl is 4
! 113: C cycles and would be 8 in a simple loop. Using mmx helps the return value
! 114: C and last limb calculations too.
! 115:
! 116: L(simple_top):
! 117: C eax counter, limbs, negative
! 118: C ebx &src[size-1]
! 119: C ecx return value
! 120: C edx &dst[size-2]
! 121: C
! 122: C mm0 scratch
! 123: C mm5 return value
! 124: C mm6 shift
! 125:
! 126: movq (%ebx,%eax,4), %mm0
! 127: incl %eax
! 128:
! 129: psrlq %mm6, %mm0
! 130:
! 131: movd %mm0, (%edx,%eax,4)
! 132: jnz L(simple_top)
! 133:
! 134:
! 135: movd (%ebx), %mm0
! 136: psrlq %mm6, %mm5 C return value
! 137:
! 138: psrlq %mm6, %mm0
! 139: popl %edi
! 140:
! 141: movd %mm5, %eax
! 142: popl %ebx
! 143:
! 144: movd %mm0, 4(%edx)
! 145:
! 146: emms
! 147:
! 148: ret
! 149:
! 150:
! 151: C -----------------------------------------------------------------------------
! 152: ALIGN(8)
! 153: L(unroll):
! 154: C eax size
! 155: C ebx src
! 156: C ecx shift
! 157: C edx dst
! 158: C esi
! 159: C edi
! 160: C ebp
! 161: deflit(`FRAME',8)
! 162:
! 163: movd (%ebx), %mm5 C src[0]
! 164: movl $4, %edi
! 165:
! 166: movd %ecx, %mm6 C rshift
! 167: testl %edi, %ebx
! 168:
! 169: psllq $32, %mm5
! 170: jz L(start_src_aligned)
! 171:
! 172:
! 173: C src isn't aligned, process low limb separately (marked xxx) and
! 174: C step src and dst by one limb, making src aligned.
! 175: C
! 176: C source ebx
! 177: C --+-------+-------+-------+
! 178: C | xxx |
! 179: C --+-------+-------+-------+
! 180: C 4mod8 0mod8 4mod8
! 181: C
! 182: C dest edx
! 183: C --+-------+-------+
! 184: C | | xxx |
! 185: C --+-------+-------+
! 186:
! 187: movq (%ebx), %mm0 C unaligned load
! 188:
! 189: psrlq %mm6, %mm0
! 190: addl $4, %ebx
! 191:
! 192: decl %eax
! 193:
! 194: movd %mm0, (%edx)
! 195: addl $4, %edx
! 196: L(start_src_aligned):
! 197:
! 198:
! 199: movq (%ebx), %mm1
! 200: testl %edi, %edx
! 201:
! 202: psrlq %mm6, %mm5 C retval
! 203: jz L(start_dst_aligned)
! 204:
! 205: C dst isn't aligned, add 4 to make it so, and pretend the shift is
! 206: C 32 bits extra. Low limb of dst (marked xxx) handled here
! 207: C separately.
! 208: C
! 209: C source ebx
! 210: C --+-------+-------+
! 211: C | mm1 |
! 212: C --+-------+-------+
! 213: C 4mod8 0mod8
! 214: C
! 215: C dest edx
! 216: C --+-------+-------+-------+
! 217: C | xxx |
! 218: C --+-------+-------+-------+
! 219: C 4mod8 0mod8 4mod8
! 220:
! 221: movq %mm1, %mm0
! 222: addl $32, %ecx C new shift
! 223:
! 224: psrlq %mm6, %mm0
! 225:
! 226: movd %ecx, %mm6
! 227:
! 228: movd %mm0, (%edx)
! 229: addl $4, %edx
! 230: L(start_dst_aligned):
! 231:
! 232:
! 233: movq 8(%ebx), %mm3
! 234: negl %ecx
! 235:
! 236: movq %mm3, %mm2 C mm2 src qword
! 237: addl $64, %ecx
! 238:
! 239: movd %ecx, %mm7
! 240: psrlq %mm6, %mm1
! 241:
! 242: leal -12(%ebx,%eax,4), %ebx
! 243: leal -20(%edx,%eax,4), %edx
! 244:
! 245: psllq %mm7, %mm3
! 246: subl $7, %eax C size-7
! 247:
! 248: por %mm1, %mm3 C mm3 ready to store
! 249: negl %eax C -(size-7)
! 250:
! 251: jns L(finish)
! 252:
! 253:
! 254: C This loop is the important bit, the rest is just support. Careful
! 255: C instruction scheduling achieves the claimed 1.75 c/l. The
! 256: C relevant parts of the pairing rules are:
! 257: C
! 258: C - mmx loads and stores execute only in the U pipe
! 259: C - only one mmx shift in a pair
! 260: C - wait one cycle before storing an mmx register result
! 261: C - the usual address generation interlock
! 262: C
! 263: C Two qword calculations are slightly interleaved. The instructions
! 264: C marked "C" belong to the second qword, and the "C prev" one is for
! 265: C the second qword from the previous iteration.
! 266:
! 267: ALIGN(8)
! 268: L(unroll_loop):
! 269: C eax counter, limbs, negative
! 270: C ebx &src[size-12]
! 271: C ecx
! 272: C edx &dst[size-12]
! 273: C esi
! 274: C edi
! 275: C
! 276: C mm0
! 277: C mm1
! 278: C mm2 src qword from -8(%ebx,%eax,4)
! 279: C mm3 dst qword ready to store to -8(%edx,%eax,4)
! 280: C
! 281: C mm5 return value
! 282: C mm6 rshift
! 283: C mm7 lshift
! 284:
! 285: movq (%ebx,%eax,4), %mm0
! 286: psrlq %mm6, %mm2
! 287:
! 288: movq %mm0, %mm1
! 289: psllq %mm7, %mm0
! 290:
! 291: movq %mm3, -8(%edx,%eax,4) C prev
! 292: por %mm2, %mm0
! 293:
! 294: movq 8(%ebx,%eax,4), %mm3 C
! 295: psrlq %mm6, %mm1 C
! 296:
! 297: movq %mm0, (%edx,%eax,4)
! 298: movq %mm3, %mm2 C
! 299:
! 300: psllq %mm7, %mm3 C
! 301: addl $4, %eax
! 302:
! 303: por %mm1, %mm3 C
! 304: js L(unroll_loop)
! 305:
! 306:
! 307: L(finish):
! 308: C eax 0 to 3 representing respectively 3 to 0 limbs remaining
! 309:
! 310: testb $2, %al
! 311:
! 312: jnz L(finish_no_two)
! 313:
! 314: movq (%ebx,%eax,4), %mm0
! 315: psrlq %mm6, %mm2
! 316:
! 317: movq %mm0, %mm1
! 318: psllq %mm7, %mm0
! 319:
! 320: movq %mm3, -8(%edx,%eax,4) C prev
! 321: por %mm2, %mm0
! 322:
! 323: movq %mm1, %mm2
! 324: movq %mm0, %mm3
! 325:
! 326: addl $2, %eax
! 327: L(finish_no_two):
! 328:
! 329:
! 330: C eax 2 or 3 representing respectively 1 or 0 limbs remaining
! 331: C
! 332: C mm2 src prev qword, from -8(%ebx,%eax,4)
! 333: C mm3 dst qword, for -8(%edx,%eax,4)
! 334:
! 335: testb $1, %al
! 336: popl %edi
! 337:
! 338: movd %mm5, %eax C retval
! 339: jnz L(finish_zero)
! 340:
! 341:
! 342: C One extra limb, destination was aligned.
! 343: C
! 344: C source ebx
! 345: C +-------+---------------+--
! 346: C | | mm2 |
! 347: C +-------+---------------+--
! 348: C
! 349: C dest edx
! 350: C +-------+---------------+---------------+--
! 351: C | | | mm3 |
! 352: C +-------+---------------+---------------+--
! 353: C
! 354: C mm6 = shift
! 355: C mm7 = ecx = 64-shift
! 356:
! 357:
! 358: C One extra limb, destination was unaligned.
! 359: C
! 360: C source ebx
! 361: C +-------+---------------+--
! 362: C | | mm2 |
! 363: C +-------+---------------+--
! 364: C
! 365: C dest edx
! 366: C +---------------+---------------+--
! 367: C | | mm3 |
! 368: C +---------------+---------------+--
! 369: C
! 370: C mm6 = shift+32
! 371: C mm7 = ecx = 64-(shift+32)
! 372:
! 373:
! 374: C In both cases there's one extra limb of src to fetch and combine
! 375: C with mm2 to make a qword at 8(%edx), and in the aligned case
! 376: C there's a further extra limb of dst to be formed.
! 377:
! 378:
! 379: movd 8(%ebx), %mm0
! 380: psrlq %mm6, %mm2
! 381:
! 382: movq %mm0, %mm1
! 383: psllq %mm7, %mm0
! 384:
! 385: movq %mm3, (%edx)
! 386: por %mm2, %mm0
! 387:
! 388: psrlq %mm6, %mm1
! 389: andl $32, %ecx
! 390:
! 391: popl %ebx
! 392: jz L(finish_one_unaligned)
! 393:
! 394: C dst was aligned, must store one extra limb
! 395: movd %mm1, 16(%edx)
! 396: L(finish_one_unaligned):
! 397:
! 398: movq %mm0, 8(%edx)
! 399:
! 400: emms
! 401:
! 402: ret
! 403:
! 404:
! 405: L(finish_zero):
! 406:
! 407: C No extra limbs, destination was aligned.
! 408: C
! 409: C source ebx
! 410: C +---------------+--
! 411: C | mm2 |
! 412: C +---------------+--
! 413: C
! 414: C dest edx+4
! 415: C +---------------+---------------+--
! 416: C | | mm3 |
! 417: C +---------------+---------------+--
! 418: C
! 419: C mm6 = shift
! 420: C mm7 = ecx = 64-shift
! 421:
! 422:
! 423: C No extra limbs, destination was unaligned.
! 424: C
! 425: C source ebx
! 426: C +---------------+--
! 427: C | mm2 |
! 428: C +---------------+--
! 429: C
! 430: C dest edx+4
! 431: C +-------+---------------+--
! 432: C | | mm3 |
! 433: C +-------+---------------+--
! 434: C
! 435: C mm6 = shift+32
! 436: C mm7 = 64-(shift+32)
! 437:
! 438:
! 439: C The movd for the unaligned case is clearly the same data as the
! 440: C movq for the aligned case, it's just a choice between whether one
! 441: C or two limbs should be written.
! 442:
! 443:
! 444: movq %mm3, 4(%edx)
! 445: psrlq %mm6, %mm2
! 446:
! 447: movd %mm2, 12(%edx)
! 448: andl $32, %ecx
! 449:
! 450: popl %ebx
! 451: jz L(finish_zero_unaligned)
! 452:
! 453: movq %mm2, 12(%edx)
! 454: L(finish_zero_unaligned):
! 455:
! 456: emms
! 457:
! 458: ret
! 459:
! 460: EPILOGUE()