← Back to branch summary

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

« back to all changes in this revision

Viewing changes to gmp3/mpn/x86/pentium/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/pentium/dive_1.asm
 
1
dnl  Intel Pentium mpn_divexact_1 -- mpn by limb exact division.
 
2
dnl
 
3
dnl          divisor
 
4
dnl        odd   even
 
5
dnl  P54:  24.5  30.5   cycles/limb
 
6
dnl  P55:  23.0  28.0
 
7
 
 
8
dnl  Copyright 2001 Free Software Foundation, Inc.
 
9
dnl 
 
10
dnl  This file is part of the GNU MP Library.
 
11
dnl 
 
12
dnl  The GNU MP Library is free software; you can redistribute it and/or
 
13
dnl  modify it under the terms of the GNU Lesser General Public License as
 
14
dnl  published by the Free Software Foundation; either version 2.1 of the
 
15
dnl  License, or (at your option) any later version.
 
16
dnl 
 
17
dnl  The GNU MP Library is distributed in the hope that it will be useful,
 
18
dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
19
dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
20
dnl  Lesser General Public License for more details.
 
21
dnl 
 
22
dnl  You should have received a copy of the GNU Lesser General Public
 
23
dnl  License along with the GNU MP Library; see the file COPYING.LIB.  If
 
24
dnl  not, write to the Free Software Foundation, Inc., 59 Temple Place -
 
25
dnl  Suite 330, Boston, MA 02111-1307, USA.
 
26
 
 
27
include(`../config.m4')
 
28
 
 
29
 
 
30
C void mpn_divexact_1 (mp_ptr dst, mp_srcptr src, mp_size_t size,
 
31
C                      mp_limb_t divisor);
 
32
C
 
33
C Plain divl is used for small sizes, since the inverse takes a while to
 
34
C setup.  Multiplying works out faster for size>=3 when the divisor is odd,
 
35
C or size>=4 when the divisor is even.  Actually on P55 size==2 for odd or
 
36
C size==3 for even are about the same speed for both divl or mul, but the
 
37
C former is used since it will use up less code cache.
 
38
C
 
39
C The P55 speeds noted above, 23 cycles odd or 28 cycles even, are as
 
40
C expected.  On P54 in the even case the shrdl pairing nonsense (see
 
41
C mpn/x86/pentium/README) costs 1 cycle, but it's not clear why there's a
 
42
C further 1.5 slowdown for both odd and even.
 
43
 
 
44
defframe(PARAM_DIVISOR,16)
 
45
defframe(PARAM_SIZE,   12)
 
46
defframe(PARAM_SRC,    8)
 
47
defframe(PARAM_DST,    4)
 
48
 
 
49
dnl  re-use parameter space
 
50
define(VAR_INVERSE,`PARAM_DST')
 
51
 
 
52
        TEXT
 
53
 
 
54
        ALIGN(32)
 
55
PROLOGUE(mpn_divexact_1)
 
56
deflit(`FRAME',0)
 
57
 
 
58
        movl    PARAM_DIVISOR, %eax
 
59
        movl    PARAM_SIZE, %ecx
 
60
 
 
61
        pushl   %esi            FRAME_pushl()
 
62
        push    %edi            FRAME_pushl()
 
63
 
 
64
        movl    PARAM_SRC, %esi
 
65
        andl    $1, %eax
 
66
 
 
67
        movl    PARAM_DST, %edi
 
68
        addl    %ecx, %eax      C size if even, size+1 if odd
 
69
 
 
70
        cmpl    $4, %eax
 
71
        jae     L(mul_by_inverse)
 
72
 
 
73
 
 
74
        xorl    %edx, %edx
 
75
L(div_top):
 
76
        movl    -4(%esi,%ecx,4), %eax
 
77
 
 
78
        divl    PARAM_DIVISOR
 
79
 
 
80
        movl    %eax, -4(%edi,%ecx,4)
 
81
        decl    %ecx
 
82
 
 
83
        jnz     L(div_top)
 
84
 
 
85
        popl    %edi
 
86
        popl    %esi
 
87
 
 
88
        ret
 
89
 
 
90
 
 
91
 
 
92
L(mul_by_inverse):
 
93
        movl    PARAM_DIVISOR, %eax
 
94
        movl    $-1, %ecx
 
95
 
 
96
L(strip_twos):
 
97
        ASSERT(nz, `orl %eax, %eax')
 
98
        shrl    %eax
 
99
        incl    %ecx                    C shift count
 
100
 
 
101
        jnc     L(strip_twos)
 
102
 
 
103
        leal    1(%eax,%eax), %edx      C d
 
104
        andl    $127, %eax              C d/2, 7 bits
 
105
 
 
106
        pushl   %ebx            FRAME_pushl()
 
107
        pushl   %ebp            FRAME_pushl()
 
108
 
 
109
ifdef(`PIC',`
 
110
        call    L(here)
 
111
L(here):
 
112
        popl    %ebp                    C eip
 
113
 
 
114
        addl    $_GLOBAL_OFFSET_TABLE_+[.-L(here)], %ebp
 
115
        C AGI
 
116
        movl    modlimb_invert_table@GOT(%ebp), %ebp
 
117
        C AGI
 
118
        movzbl  (%eax,%ebp), %eax
 
119
',`
 
120
 
 
121
dnl non-PIC
 
122
        movzbl  modlimb_invert_table(%eax), %eax        C inv 8 bits
 
123
')
 
124
 
 
125
        movl    %eax, %ebp              C inv
 
126
        addl    %eax, %eax              C 2*inv
 
127
 
 
128
        imull   %ebp, %ebp              C inv*inv
 
129
 
 
130
        imull   %edx, %ebp              C inv*inv*d
 
131
 
 
132
        subl    %ebp, %eax              C inv = 2*inv - inv*inv*d
 
133
        movl    PARAM_SIZE, %ebx
 
134
 
 
135
        movl    %eax, %ebp
 
136
        addl    %eax, %eax              C 2*inv
 
137
 
 
138
        imull   %ebp, %ebp              C inv*inv
 
139
 
 
140
        imull   %edx, %ebp              C inv*inv*d
 
141
 
 
142
        subl    %ebp, %eax              C inv = 2*inv - inv*inv*d
 
143
        movl    %edx, PARAM_DIVISOR     C d without twos
 
144
 
 
145
        leal    (%esi,%ebx,4), %esi     C src end
 
146
        leal    (%edi,%ebx,4), %edi     C dst end
 
147
 
 
148
        negl    %ebx                    C -size
 
149
 
 
150
        ASSERT(e,`      C expect d*inv == 1 mod 2^BITS_PER_MP_LIMB
 
151
        pushl   %eax    FRAME_pushl()
 
152
        imull   PARAM_DIVISOR, %eax
 
153
        cmpl    $1, %eax
 
154
        popl    %eax    FRAME_popl()')
 
155
 
 
156
        movl    %eax, VAR_INVERSE
 
157
        xorl    %ebp, %ebp              C initial carry bit
 
158
 
 
159
        movl    (%esi,%ebx,4), %eax     C src low limb
 
160
        orl     %ecx, %ecx              C shift
 
161
 
 
162
        movl    4(%esi,%ebx,4), %edx    C src second limb (for even)
 
163
        jz      L(odd_entry)
 
164
 
 
165
        shrdl(  %cl, %edx, %eax)
 
166
 
 
167
        incl    %ebx
 
168
        jmp     L(even_entry)
 
169
 
 
170
 
 
171
        ALIGN(8)
 
172
L(odd_top):
 
173
        C eax   scratch
 
174
        C ebx   counter, limbs, negative
 
175
        C ecx
 
176
        C edx
 
177
        C esi   src end
 
178
        C edi   dst end
 
179
        C ebp   carry bit, 0 or -1
 
180
 
 
181
        mull    PARAM_DIVISOR
 
182
 
 
183
        movl    (%esi,%ebx,4), %eax
 
184
        subl    %ebp, %edx
 
185
 
 
186
        subl    %edx, %eax
 
187
 
 
188
        sbbl    %ebp, %ebp
 
189
 
 
190
L(odd_entry):
 
191
        imull   VAR_INVERSE, %eax
 
192
 
 
193
        movl    %eax, (%edi,%ebx,4)
 
194
 
 
195
        incl    %ebx
 
196
        jnz     L(odd_top)
 
197
 
 
198
 
 
199
        popl    %ebp
 
200
        popl    %ebx
 
201
 
 
202
        popl    %edi
 
203
        popl    %esi
 
204
 
 
205
        ret
 
206
 
 
207
 
 
208
L(even_top):
 
209
        C eax   scratch
 
210
        C ebx   counter, limbs, negative
 
211
        C ecx   twos
 
212
        C edx
 
213
        C esi   src end
 
214
        C edi   dst end
 
215
        C ebp   carry bit, 0 or -1
 
216
 
 
217
        mull    PARAM_DIVISOR
 
218
 
 
219
        subl    %ebp, %edx              C carry bit
 
220
        movl    -4(%esi,%ebx,4), %eax   C src limb
 
221
 
 
222
        movl    (%esi,%ebx,4), %ebp     C and one above it
 
223
 
 
224
        shrdl(  %cl, %ebp, %eax)
 
225
 
 
226
        subl    %edx, %eax              C carry limb
 
227
 
 
228
        sbbl    %ebp, %ebp
 
229
 
 
230
L(even_entry):
 
231
        imull   VAR_INVERSE, %eax
 
232
 
 
233
        movl    %eax, -4(%edi,%ebx,4)
 
234
        incl    %ebx
 
235
 
 
236
        jnz     L(even_top)
 
237
 
 
238
 
 
239
 
 
240
        mull    PARAM_DIVISOR
 
241
 
 
242
        movl    -4(%esi), %eax          C src high limb
 
243
        subl    %ebp, %edx
 
244
 
 
245
        shrl    %cl, %eax
 
246
 
 
247
        subl    %edx, %eax              C no carry if division is exact
 
248
 
 
249
        imull   VAR_INVERSE, %eax
 
250
 
 
251
        movl    %eax, -4(%edi)          C dst high limb
 
252
        nop                             C protect against cache bank clash
 
253
 
 
254
        popl    %ebp
 
255
        popl    %ebx
 
256
 
 
257
        popl    %edi
 
258
        popl    %esi
 
259
 
 
260
        ret
 
261
 
 
262
EPILOGUE()