← Back to branch summary

~ubuntu-branches/ubuntu/quantal/gclcvs/quantal

« back to all changes in this revision

Viewing changes to gmp3/mpn/x86/pentium4/sse2/dive_1.asm

  • Committer: Bazaar Package Importer
  • Author(s): Camm Maguire
  • Date: 2004-06-24 15:13:46 UTC
  • Revision ID: james.westby@ubuntu.com-20040624151346-xh0xaaktyyp7aorc
Tags: 2.7.0-26
C_GC_OFFSET is 2 on m68k-linux

Show diffs side-by-side

added added

removed removed

Lines of Context:
gmp3/mpn/x86/pentium4/sse2/dive_1.asm
 
1
dnl  Intel Pentium-4 mpn_divexact_1 -- mpn by limb exact division.
 
2
dnl
 
3
dnl  P4: 19.0 cycles/limb 
 
4
 
 
5
dnl  Copyright 2001 Free Software Foundation, Inc.
 
6
dnl 
 
7
dnl  This file is part of the GNU MP Library.
 
8
dnl 
 
9
dnl  The GNU MP Library is free software; you can redistribute it and/or
 
10
dnl  modify it under the terms of the GNU Lesser General Public License as
 
11
dnl  published by the Free Software Foundation; either version 2.1 of the
 
12
dnl  License, or (at your option) any later version.
 
13
dnl 
 
14
dnl  The GNU MP Library is distributed in the hope that it will be useful,
 
15
dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
17
dnl  Lesser General Public License for more details.
 
18
dnl 
 
19
dnl  You should have received a copy of the GNU Lesser General Public
 
20
dnl  License along with the GNU MP Library; see the file COPYING.LIB.  If
 
21
dnl  not, write to the Free Software Foundation, Inc., 59 Temple Place -
 
22
dnl  Suite 330, Boston, MA 02111-1307, USA.
 
23
 
 
24
include(`../config.m4')
 
25
 
 
26
 
 
27
C void mpn_divexact_1 (mp_ptr dst, mp_srcptr src, mp_size_t size,
 
28
C                      mp_limb_t divisor);
 
29
C
 
30
C Pairs of movd's are used to avoid unaligned loads.  Despite the loads not
 
31
C being on the dependent chain and there being plenty of cycles available,
 
32
C using an unaligned movq on every second iteration measured about 23 c/l.
 
33
C
 
34
C Using divl for size==1 seems a touch quicker than mul-by-inverse.  The mul
 
35
C will be about 9+2*4+2*2+10*4+19+12 = 92 cycles latency, though some of
 
36
C that might be hidden by out-of-order execution, whereas divl is around 60.
 
37
C At size==2 an extra 19 for the mul versus 60 for the divl will see the mul
 
38
C faster.
 
39
 
 
40
defframe(PARAM_DIVISOR,16)
 
41
defframe(PARAM_SIZE,   12)
 
42
defframe(PARAM_SRC,    8)
 
43
defframe(PARAM_DST,    4)
 
44
 
 
45
        TEXT
 
46
 
 
47
        ALIGN(16)
 
48
PROLOGUE(mpn_divexact_1)
 
49
deflit(`FRAME',0)
 
50
 
 
51
        movl    PARAM_SIZE, %edx
 
52
 
 
53
        movl    PARAM_SRC, %eax
 
54
 
 
55
        movl    PARAM_DIVISOR, %ecx
 
56
        subl    $1, %edx
 
57
        jnz     L(two_or_more)
 
58
 
 
59
        movl    (%eax), %eax
 
60
        xorl    %edx, %edx
 
61
 
 
62
        divl    %ecx
 
63
        movl    PARAM_DST, %ecx
 
64
 
 
65
        movl    %eax, (%ecx)
 
66
        ret
 
67
 
 
68
 
 
69
L(two_or_more):
 
70
        C eax   src
 
71
        C ebx
 
72
        C ecx   divisor
 
73
        C edx   size-1
 
74
 
 
75
        movl    %ecx, %eax
 
76
        bsfl    %ecx, %ecx              C trailing twos
 
77
 
 
78
        shrl    %cl, %eax               C d = divisor without twos
 
79
        movd    %eax, %mm6
 
80
        movd    %ecx, %mm7              C shift
 
81
 
 
82
        shrl    %eax                    C d/2
 
83
 
 
84
        andl    $127, %eax              C d/2, 7 bits
 
85
 
 
86
ifdef(`PIC',`
 
87
        call    L(movl_eip_ecx)
 
88
 
 
89
        addl    $_GLOBAL_OFFSET_TABLE_, %ecx
 
90
 
 
91
        movl    modlimb_invert_table@GOT(%ecx), %ecx
 
92
        C
 
93
        movzbl  (%eax,%ecx), %eax                       C inv 8 bits
 
94
',`
 
95
dnl non-PIC
 
96
        movzbl  modlimb_invert_table(%eax), %eax        C inv 8 bits
 
97
')
 
98
 
 
99
        C
 
100
 
 
101
        movd    %eax, %mm5              C inv
 
102
 
 
103
        movd    %eax, %mm0              C inv
 
104
 
 
105
        pmuludq %mm5, %mm5              C inv*inv
 
106
 
 
107
        C
 
108
 
 
109
        pmuludq %mm6, %mm5              C inv*inv*d
 
110
        paddd   %mm0, %mm0              C 2*inv
 
111
 
 
112
        C
 
113
 
 
114
        psubd   %mm5, %mm0              C inv = 2*inv - inv*inv*d
 
115
        pxor    %mm5, %mm5
 
116
 
 
117
        paddd   %mm0, %mm5
 
118
        pmuludq %mm0, %mm0              C inv*inv
 
119
 
 
120
        pcmpeqd %mm4, %mm4
 
121
        psrlq   $32, %mm4               C 0x00000000FFFFFFFF
 
122
 
 
123
        C
 
124
 
 
125
        pmuludq %mm6, %mm0              C inv*inv*d
 
126
        paddd   %mm5, %mm5              C 2*inv
 
127
 
 
128
        movl    PARAM_SRC, %eax
 
129
        movl    PARAM_DST, %ecx
 
130
        pxor    %mm1, %mm1              C initial carry limb
 
131
 
 
132
        C
 
133
 
 
134
        psubd   %mm0, %mm5              C inv = 2*inv - inv*inv*d
 
135
 
 
136
        ASSERT(e,`      C expect d*inv == 1 mod 2^BITS_PER_MP_LIMB
 
137
        pushl   %eax    FRAME_pushl()
 
138
        movq    %mm6, %mm0
 
139
        pmuludq %mm5, %mm0
 
140
        movd    %mm0, %eax
 
141
        cmpl    $1, %eax
 
142
        popl    %eax    FRAME_popl()')
 
143
 
 
144
        pxor    %mm0, %mm0              C initial carry bit
 
145
 
 
146
 
 
147
C The dependent chain here is as follows.
 
148
C
 
149
C                                       latency
 
150
C       psubq    s = (src-cbit) - climb    2
 
151
C       pmuludq  q = s*inverse             8
 
152
C       pmuludq  prod = q*divisor          8
 
153
C       psrlq    climb = high(prod)        2
 
154
C                                         --
 
155
C                                         20
 
156
C
 
157
C Yet the loop measures 19.0 c/l, so obviously there's something gained
 
158
C there over a straight reading of the chip documentation.
 
159
 
 
160
L(top):
 
161
        C eax   src, incrementing
 
162
        C ebx
 
163
        C ecx   dst, incrementing
 
164
        C edx   counter, size-1 iterations
 
165
        C
 
166
        C mm0   carry bit
 
167
        C mm1   carry limb
 
168
        C mm4   0x00000000FFFFFFFF
 
169
        C mm5   inverse
 
170
        C mm6   divisor
 
171
        C mm7   shift
 
172
 
 
173
        movd    (%eax), %mm2
 
174
        movd    4(%eax), %mm3
 
175
        addl    $4, %eax
 
176
        punpckldq %mm3, %mm2
 
177
 
 
178
        psrlq   %mm7, %mm2
 
179
        pand    %mm4, %mm2              C src
 
180
        psubq   %mm0, %mm2              C src - cbit
 
181
 
 
182
        psubq   %mm1, %mm2              C src - cbit - climb
 
183
        movq    %mm2, %mm0
 
184
        psrlq   $63, %mm0               C new cbit
 
185
 
 
186
        pmuludq %mm5, %mm2              C s*inverse
 
187
        movd    %mm2, (%ecx)            C q
 
188
        addl    $4, %ecx
 
189
 
 
190
        movq    %mm6, %mm1
 
191
        pmuludq %mm2, %mm1              C q*divisor
 
192
        psrlq   $32, %mm1               C new climb
 
193
 
 
194
        subl    $1, %edx
 
195
        jnz     L(top)
 
196
 
 
197
 
 
198
L(done):
 
199
        movd    (%eax), %mm2
 
200
        psrlq   %mm7, %mm2              C src
 
201
        psubq   %mm0, %mm2              C src - cbit
 
202
 
 
203
        psubq   %mm1, %mm2              C src - cbit - climb
 
204
 
 
205
        pmuludq %mm5, %mm2              C s*inverse
 
206
        movd    %mm2, (%ecx)            C q
 
207
 
 
208
        emms
 
209
        ret
 
210
 
 
211
 
 
212
ifdef(`PIC',`
 
213
L(movl_eip_ecx):
 
214
        movl    (%esp), %ecx
 
215
        ret
 
216
')
 
217
 
 
218
EPILOGUE()