dnl AMD K7 mpn_gcd_1 -- mpn by 1 gcd. dnl Copyright 2000, 2001, 2002 Free Software Foundation, Inc. dnl dnl This file is part of the GNU MP Library. dnl dnl The GNU MP Library is free software; you can redistribute it and/or dnl modify it under the terms of the GNU Lesser General Public License as dnl published by the Free Software Foundation; either version 3 of the dnl License, or (at your option) any later version. dnl dnl The GNU MP Library is distributed in the hope that it will be useful, dnl but WITHOUT ANY WARRANTY; without even the implied warranty of dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU dnl Lesser General Public License for more details. dnl dnl You should have received a copy of the GNU Lesser General Public License dnl along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. include(`../config.m4') C K7: 6.75 cycles/bit (approx) 1x1 gcd C 11.0 cycles/limb Nx1 reduction (modexact_1_odd) dnl Reduce using x%y if x is more than DIV_THRESHOLD bits bigger than y, dnl where x is the larger of the two. See tune/README for more. dnl dnl divl at 40 cycles compared to the gcd at about 7 cycles/bitpair dnl suggests 40/7*2=11.4 but 7 seems to be about right. deflit(DIV_THRESHOLD, 7) C table[n] is the number of trailing zeros on n, or MAXSHIFT if n==0. C C This is mixed in with the code, but as per the k7 optimization manual it's C a full cache line and suitably aligned so it won't get swapped between C code and data. Having it in TEXT rather than RODATA saves needing a GOT C entry when PIC. C C Actually, there doesn't seem to be a measurable difference between this in C it's own cache line or plonked in the middle of the code. Presumably C since TEXT is read-only there's no worries about coherency. deflit(MASK, 63) deflit(MAXSHIFT, 6) TEXT ALIGN(64) L(table): .byte MAXSHIFT forloop(i,1,MASK, ` .byte m4_count_trailing_zeros(i) ') C mp_limb_t mpn_gcd_1 (mp_srcptr src, mp_size_t size, mp_limb_t limb); C defframe(PARAM_LIMB, 12) defframe(PARAM_SIZE, 8) defframe(PARAM_SRC, 4) defframe(SAVE_EBX, -4) defframe(SAVE_ESI, -8) defframe(SAVE_EDI, -12) defframe(SAVE_EBP, -16) defframe(CALL_DIVISOR,-20) defframe(CALL_SIZE, -24) defframe(CALL_SRC, -28) deflit(STACK_SPACE, 28) TEXT ALIGN(16) PROLOGUE(mpn_gcd_1) deflit(`FRAME',0) ASSERT(ne, `cmpl $0, PARAM_LIMB') C y!=0 ASSERT(ae, `cmpl $1, PARAM_SIZE') C size>=1 movl PARAM_SRC, %eax movl PARAM_LIMB, %edx subl $STACK_SPACE, %esp deflit(`FRAME',STACK_SPACE) movl %esi, SAVE_ESI movl %ebx, SAVE_EBX movl (%eax), %esi C src low limb ifdef(`PIC',` movl %edi, SAVE_EDI call L(movl_eip_to_edi) L(here): addl $L(table)-L(here), %edi ') movl %esi, %ebx orl %edx, %esi C x|y movl $-1, %ecx L(twos): incl %ecx shrl %esi jnc L(twos) C 3/4 chance of x or y odd already shrl %cl, %ebx shrl %cl, %edx movl %ecx, %esi C common twos movl PARAM_SIZE, %ecx cmpl $1, %ecx ja L(divide) C eax C ebx x C ecx C edx y C esi common twos C edi [PIC] L(table) C ebp movl %edx, %eax cmpl %ebx, %edx cmovb( %ebx, %eax) C swap to make x bigger than y cmovb( %edx, %ebx) L(strip_y): C eax x C ebx y C ecx C edx C esi common twos C edi [PIC] L(table) C ebp ASSERT(nz,`orl %ebx,%ebx') shrl %ebx jnc L(strip_y) rcll %ebx C eax x C ebx y (odd) C ecx C edx C esi common twos C edi [PIC] L(table) C ebp movl %eax, %ecx movl %ebx, %edx shrl $DIV_THRESHOLD, %eax cmpl %eax, %ebx movl %ecx, %eax ja L(strip_x_entry) C do x%y if x much bigger than y xorl %edx, %edx divl %ebx orl %edx, %edx movl %edx, %eax C remainder -> x movl %ebx, %edx C y jz L(done_ebx) jmp L(strip_x) C Offset 0x9D here for non-PIC. About 0.4 cycles/bit is saved by C ensuring the end of the jnz at the end of this loop doesn't cross C into the next cache line at 0xC0. C C PIC on the other hand is offset 0xAC here and extends to 0xC9, so C it crosses but doesn't suffer any measurable slowdown. L(top): C eax x C ebx y-x C ecx x-y C edx y C esi twos, for use at end C edi [PIC] L(table) cmovc( %ebx, %ecx) C if x-y gave carry, use x and y-x cmovc( %eax, %edx) L(strip_x): movl %ecx, %eax L(strip_x_entry): andl $MASK, %ecx ASSERT(nz, `orl %eax, %eax') ifdef(`PIC',` movb (%ecx,%edi), %cl ',` movb L(table) (%ecx), %cl ') shrl %cl, %eax cmpb $MAXSHIFT, %cl movl %eax, %ecx movl %edx, %ebx je L(strip_x) ASSERT(nz, `testl $1, %eax') C both odd ASSERT(nz, `testl $1, %edx') subl %eax, %ebx subl %edx, %ecx jnz L(top) L(done): movl %esi, %ecx movl SAVE_ESI, %esi ifdef(`PIC',` movl SAVE_EDI, %edi ') shll %cl, %eax movl SAVE_EBX, %ebx addl $FRAME, %esp ret C ----------------------------------------------------------------------------- C two or more limbs dnl MODEXACT_THRESHOLD is the size at which it's better to call dnl mpn_modexact_1_odd than do an inline loop. deflit(MODEXACT_THRESHOLD, ifdef(`PIC',6,5)) L(divide): C eax src C ebx C ecx size C edx y C esi common twos C edi [PIC] L(table) C ebp L(divide_strip_y): ASSERT(nz,`orl %edx,%edx') shrl %edx jnc L(divide_strip_y) leal 1(%edx,%edx), %ebx C y now odd movl %ebp, SAVE_EBP movl %eax, %ebp movl -4(%eax,%ecx,4), %eax C src high limb cmp $MODEXACT_THRESHOLD, %ecx jae L(modexact) cmpl %ebx, %eax C high cmp divisor movl $0, %edx cmovc( %eax, %edx) C skip a div if high