1
dnl AMD64 mpn_modexact_1_odd -- exact division style remainder.
3
dnl Copyright 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software
6
dnl This file is part of the GNU MP Library.
8
dnl The GNU MP Library is free software; you can redistribute it and/or
9
dnl modify it under the terms of the GNU Lesser General Public License as
10
dnl published by the Free Software Foundation; either version 2.1 of the
11
dnl License, or (at your option) any later version.
13
dnl The GNU MP Library is distributed in the hope that it will be useful,
14
dnl but WITHOUT ANY WARRANTY; without even the implied warranty of
15
dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16
dnl Lesser General Public License for more details.
18
dnl You should have received a copy of the GNU Lesser General Public
19
dnl License along with the GNU MP Library; see the file COPYING.LIB. If
20
dnl not, write to the Free Software Foundation, Inc., 51 Franklin Street,
21
dnl Fifth Floor, Boston, MA 02110-1301, USA.
23
include(`../config.m4')
31
C mp_limb_t mpn_modexact_1_odd (mp_srcptr src, mp_size_t size,
33
C mp_limb_t mpn_modexact_1c_odd (mp_srcptr src, mp_size_t size,
34
C mp_limb_t divisor, mp_limb_t carry);
37
C The dependent chain in the main loop is
46
C The movq load from src seems to need to be scheduled back before the jz to
47
C achieve this speed, out-of-order execution apparently can't completely
48
C hide the latency otherwise.
50
C The l=src[i]-cbit step is rotated back too, since that allows us to avoid
51
C it for the first iteration (where there's no cbit).
53
C The code alignment used (32-byte) for the loop also seems necessary.
54
C Without that the non-PIC case has adcq crossing the 0x60 offset,
55
C apparently making it run at 11 cycles instead of 10.
59
C divq for size==1 was measured at about 79 cycles, compared to the inverse
60
C at about 25 cycles (both including function call overheads), so that's not
65
C For PIC, we shouldn't really need the GOT fetch for modlimb_invert_table,
66
C it'll be in rodata or text in libgmp.so and can be accessed directly %rip
67
C relative. This would be for small model only (something we don't
68
C presently detect, but which is all that gcc 3.3.3 supports), since 8-byte
69
C PC-relative relocations are apparently not available. Some rough
70
C experiments with binutils 2.13 looked worrylingly like it might come out
71
C with an unwanted text segment relocation though, even with ".protected".
77
PROLOGUE(mpn_modexact_1_odd)
81
PROLOGUE(mpn_modexact_1c_odd)
91
movq modlimb_invert_table@GOTPCREL(%rip), %r9
93
movabsq $modlimb_invert_table, %r9
97
movq %rcx, %r10 C initial carry
99
movzbl (%r9,%rdx), %edx C inv 8 bits
101
movq (%rdi), %rax C src[0]
102
leaq (%rdi,%rsi,8), %r11 C src end
103
movq %r8, %rdi C d, made available to imull
105
leal (%rdx,%rdx), %ecx C 2*inv
106
imull %edx, %edx C inv*inv
110
imull %edi, %edx C inv*inv*d
112
subl %edx, %ecx C inv = 2*inv - inv*inv*d, 16 bits
114
leal (%rcx,%rcx), %edx C 2*inv
115
imull %ecx, %ecx C inv*inv
117
imull %edi, %ecx C inv*inv*d
119
subl %ecx, %edx C inv = 2*inv - inv*inv*d, 32 bits
120
xorl %ecx, %ecx C initial cbit
122
leaq (%rdx,%rdx), %r9 C 2*inv
123
imulq %rdx, %rdx C inv*inv
125
imulq %r8, %rdx C inv*inv*d
127
subq %rdx, %r9 C inv = 2*inv - inv*inv*d, 64 bits
128
movq %r10, %rdx C initial climb
130
ASSERT(e,` C d*inv == 1 mod 2^64
141
C rax l = src[i]-cbit
142
C rcx new cbit, 0 or 1
143
C rdx climb, high of last product
144
C rsi counter, limbs, negative
150
subq %rdx, %rax C l = src[i]-cbit - climb
152
adcq $0, %rcx C more cbit
153
imulq %r9, %rax C q = l * inverse
155
mulq %r8 C climb = high (q * d)
157
movq (%r11,%rsi,8), %rax C src[i+1]
158
subq %rcx, %rax C next l = src[i+1] - cbit
166
subq %rdx, %rax C l = src[i]-cbit - climb
168
adcq $0, %rcx C more cbit
169
imulq %r9, %rax C q = l * inverse
171
mulq %r8 C climb = high (q * d)
173
leaq (%rcx,%rdx), %rax C climb+cbit
176
EPILOGUE(mpn_modexact_1c_odd)
177
EPILOGUE(mpn_modexact_1_odd)
added
removed
src/gmp/mpn/x86_64/mode1o.asm
