← 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/sqr_basecase.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/sqr_basecase.asm
 
1
dnl  Intel Pentium-4 mpn_sqr_basecase -- square an mpn number.
 
2
dnl 
 
3
dnl  P4: approx 3.5 cycles per crossproduct, or 7 cycles per triangular
 
4
dnl  product, at around 30x30 limbs.
 
5
 
 
6
dnl  Copyright 2001 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
include(`../config.m4')
 
26
 
 
27
 
 
28
C void mpn_sqr_basecase (mp_ptr dst, mp_srcptr src, mp_size_t size);
 
29
C
 
30
C The algorithm is basically the same as mpn/generic/sqr_basecase.c, but a
 
31
C lot of function call overheads are avoided, especially when the size is
 
32
C small.
 
33
C
 
34
C On small sizes there's only a small speedup over mpn_mul_basecase,
 
35
C presumably branch mispredictions are a bigger fraction of the work done.
 
36
C It's not clear how to help this.
 
37
 
 
38
defframe(PARAM_SIZE,12)
 
39
defframe(PARAM_SRC, 8)
 
40
defframe(PARAM_DST, 4)
 
41
 
 
42
        TEXT
 
43
        ALIGN(8)
 
44
PROLOGUE(mpn_sqr_basecase)
 
45
deflit(`FRAME',0)
 
46
 
 
47
        movl    PARAM_SIZE, %edx
 
48
        movl    PARAM_SRC, %eax
 
49
        movl    PARAM_DST, %ecx
 
50
 
 
51
        cmpl    $2, %edx
 
52
 
 
53
        je      L(two_limbs)
 
54
        ja      L(three_or_more)
 
55
 
 
56
C -----------------------------------------------------------------------------
 
57
C one limb only
 
58
        C eax   src
 
59
        C ebx
 
60
        C ecx   dst
 
61
        C edx
 
62
 
 
63
        movl    (%eax), %eax
 
64
        mull    %eax
 
65
 
 
66
        movl    %eax, (%ecx)
 
67
        movl    %edx, 4(%ecx)
 
68
 
 
69
        ret
 
70
 
 
71
C -----------------------------------------------------------------------------
 
72
L(two_limbs):
 
73
        C eax   src
 
74
        C ebx
 
75
        C ecx   dst
 
76
        C edx   size
 
77
 
 
78
        movd    (%eax), %mm1
 
79
        movd    4(%eax), %mm0
 
80
        pmuludq %mm1, %mm0              C src[0]*src[1]
 
81
 
 
82
        pmuludq %mm1, %mm1              C src[0]^2
 
83
 
 
84
        movd    4(%eax), %mm2
 
85
        pmuludq %mm2, %mm2              C src[1]^2
 
86
 
 
87
        movd    %mm1, (%ecx)            C dst[0]
 
88
        psrlq   $32, %mm1
 
89
 
 
90
        pcmpeqd %mm3, %mm3
 
91
        psrlq   $32, %mm3               C 0x00000000FFFFFFFF
 
92
        pand    %mm0, %mm3              C low(src[0]*src[1])
 
93
        psrlq   $32, %mm0               C high(src[0]*src[1])
 
94
 
 
95
        psllq   $1, %mm3                C 2*low(src[0]*src[1])
 
96
        paddq   %mm3, %mm1              C high(src[0]^2)
 
97
        movd    %mm1, 4(%ecx)           C dst[1]
 
98
 
 
99
        pcmpeqd %mm4, %mm4
 
100
        psrlq   $32, %mm4               C 0x00000000FFFFFFFF
 
101
        pand    %mm2, %mm4              C low(src[1]^2)
 
102
        psrlq   $32, %mm2               C high(src[1]^2)
 
103
 
 
104
        psllq   $1, %mm0                C 2*high(src[0]*src[1])
 
105
        psrlq   $32, %mm1               C carry
 
106
        paddq   %mm1, %mm0
 
107
        paddq   %mm4, %mm0              C low(src[1]^2)
 
108
        movd    %mm0, 8(%ecx)           C dst[2]
 
109
 
 
110
        psrlq   $32, %mm0               C carry
 
111
        paddq   %mm2, %mm0              C high(src[1]^2)
 
112
        movd    %mm0, 12(%ecx)          C dst[3]
 
113
 
 
114
        ASSERT(z,`
 
115
        psrlq   $32, %mm0
 
116
        movd    %mm0, %eax
 
117
        orl     %eax, %eax')
 
118
 
 
119
        emms
 
120
        ret
 
121
 
 
122
 
 
123
C -----------------------------------------------------------------------------
 
124
L(three_or_more):
 
125
 
 
126
        C eax   src
 
127
        C ebx
 
128
        C ecx   dst
 
129
        C edx   size
 
130
        C esi
 
131
        C edi
 
132
        C ebp
 
133
        C
 
134
        C First multiply src[0]*src[1..size-1] and store at dst[1..size].
 
135
 
 
136
defframe(SAVE_ESI,  -4)
 
137
defframe(SAVE_EDI,  -8)
 
138
defframe(SAVE_EBP, -12)
 
139
deflit(STACK_SPACE, 12)
 
140
 
 
141
        subl    $STACK_SPACE, %esp      FRAME_subl_esp(STACK_SPACE)
 
142
        pxor    %mm0, %mm0              C initial carry
 
143
        movd    (%eax), %mm7            C multiplier
 
144
 
 
145
        movl    %esi, SAVE_ESI
 
146
        movl    %edi, SAVE_EDI
 
147
        movl    %ebp, SAVE_EBP
 
148
 
 
149
 
 
150
        movl    %eax, %esi
 
151
        movl    %ecx, %edi
 
152
        subl    $1, %edx
 
153
 
 
154
        C First multiply src[0]*src[1..size-1] and store at dst[1..size].
 
155
L(mul1):
 
156
        C eax   src, incrementing
 
157
        C ebx
 
158
        C ecx   dst, incrementing
 
159
        C edx   counter, size-1 iterations
 
160
        C esi   src
 
161
        C edi   dst
 
162
        C ebp
 
163
        C
 
164
        C mm0   carry limb
 
165
        C mm7   multiplier
 
166
 
 
167
        movd    4(%eax), %mm1
 
168
        addl    $4, %eax
 
169
        pmuludq %mm7, %mm1
 
170
        paddq   %mm1, %mm0
 
171
        movd    %mm0, 4(%ecx)
 
172
        addl    $4, %ecx
 
173
        psrlq   $32, %mm0
 
174
        subl    $1, %edx
 
175
        jnz     L(mul1)
 
176
 
 
177
 
 
178
        movl    PARAM_SIZE, %ebp
 
179
        subl    $3, %ebp
 
180
        jz      L(corner)
 
181
 
 
182
 
 
183
        C Add products src[n]*src[n+1..size-1] at dst[2*n-1...], for
 
184
        C n=1..size-2.  The last two products, which are the end corner of
 
185
        C the product triangle, are handled separately to save looping
 
186
        C overhead.
 
187
 
 
188
L(outer):
 
189
        C eax
 
190
        C ebx
 
191
        C ecx
 
192
        C edx
 
193
        C esi   src, incrementing
 
194
        C edi   dst, incrementing
 
195
        C ebp   size, decrementing
 
196
        C
 
197
        C mm0   prev carry
 
198
 
 
199
        movd    4(%esi), %mm7           C multiplier
 
200
        movd    %mm0, 4(%ecx)           C prev carry
 
201
 
 
202
        leal    8(%esi), %eax           C next src
 
203
        addl    $4, %esi
 
204
 
 
205
        leal    8(%edi), %ecx           C next dst
 
206
        addl    $8, %edi
 
207
 
 
208
        leal    1(%ebp), %edx           C counter
 
209
 
 
210
        pxor    %mm0, %mm0              C initial carry limb, clear carry flag
 
211
 
 
212
L(inner):
 
213
        C eax   src, incrementing
 
214
        C edx
 
215
        C ecx   dst, incrementing
 
216
        C edx   counter
 
217
        C esi   outer src
 
218
        C edi   outer dst
 
219
        C ebp   outer size
 
220
        C
 
221
        C mm0   carry
 
222
 
 
223
        movd    (%eax), %mm1
 
224
        leal    4(%eax), %eax
 
225
        movd    4(%ecx),%mm2
 
226
        pmuludq %mm7, %mm1
 
227
        paddq   %mm2, %mm1
 
228
        paddq   %mm1, %mm0
 
229
        subl    $1, %edx
 
230
        movd    %mm0, 4(%ecx)
 
231
        psrlq   $32, %mm0
 
232
        leal    4(%ecx), %ecx
 
233
        jnz     L(inner)
 
234
 
 
235
        subl    $1, %ebp
 
236
        jnz     L(outer)
 
237
 
 
238
 
 
239
L(corner):
 
240
        C esi   &src[size-3]
 
241
        C edi   &dst[2*size-6]
 
242
        C mm0   carry
 
243
        C
 
244
        C       +-----+-----+--
 
245
        C       | mm0 | dst so far
 
246
        C       +-----+-----+--
 
247
        C +-----+-----+
 
248
        C |     |     |  src[size-2]*src[size-1]
 
249
        C +-----+-----+
 
250
 
 
251
        movd    4(%esi), %mm1
 
252
        movd    8(%esi), %mm2
 
253
        pmuludq %mm2, %mm1              C src[size-1]*src[size-2]
 
254
 
 
255
        movl    PARAM_SRC, %eax
 
256
        movd    (%eax), %mm2
 
257
        pmuludq %mm2, %mm2              C src[0]^2
 
258
 
 
259
        pcmpeqd %mm7, %mm7
 
260
        psrlq   $32, %mm7
 
261
 
 
262
        movl    PARAM_DST, %edx
 
263
        movd    4(%edx), %mm3           C dst[1]
 
264
 
 
265
        paddq   %mm1, %mm0
 
266
        movd    %mm0, 12(%edi)          C dst[2*size-3]
 
267
 
 
268
        psrlq   $32, %mm0
 
269
        movd    %mm0, 16(%edi)          C dst[2*size-2]
 
270
 
 
271
        movd    %mm2, (%edx)            C dst[0]
 
272
        psrlq   $32, %mm2
 
273
 
 
274
        psllq   $1, %mm3                C 2*dst[1]
 
275
        paddq   %mm3, %mm2
 
276
        movd    %mm2, 4(%edx)
 
277
        psrlq   $32, %mm2
 
278
 
 
279
        movl    PARAM_SIZE, %ecx
 
280
        subl    $2, %ecx
 
281
 
 
282
        C Now form squares on the diagonal src[0]^2,...,src[size-1]^2, and
 
283
        C add to the triangular parts dst[1..2*size-2] with those left
 
284
        C shifted by 1 bit.
 
285
 
 
286
L(diag):
 
287
        C eax   src, incrementing
 
288
        C ebx
 
289
        C ecx   counter, size-2 iterations
 
290
        C edx   dst, incrementing
 
291
        C esi
 
292
        C edi
 
293
        C ebp
 
294
        C
 
295
        C mm2   carry
 
296
        C mm7   0x00000000FFFFFFFF
 
297
 
 
298
        movd    4(%eax), %mm0   C src limb
 
299
        addl    $4, %eax
 
300
        pmuludq %mm0, %mm0
 
301
        movq    %mm7, %mm1
 
302
        pand    %mm0, %mm1      C diagonal low
 
303
        psrlq   $32, %mm0       C diagonal high
 
304
 
 
305
        movd    8(%edx), %mm3
 
306
        psllq   $1, %mm3        C 2*dst[i]
 
307
        paddq   %mm3, %mm1
 
308
        paddq   %mm1, %mm2
 
309
        movd    %mm2, 8(%edx)
 
310
        psrlq   $32, %mm2
 
311
 
 
312
        movd    12(%edx), %mm3
 
313
        psllq   $1, %mm3        C 2*dst[i+1]
 
314
        paddq   %mm3, %mm0
 
315
        paddq   %mm0, %mm2
 
316
        movd    %mm2, 12(%edx)
 
317
        addl    $8, %edx
 
318
        psrlq   $32, %mm2
 
319
 
 
320
        subl    $1, %ecx
 
321
        jnz     L(diag)
 
322
 
 
323
 
 
324
        movd    4(%eax), %mm0   C src[size-1]
 
325
        pmuludq %mm0, %mm0
 
326
        pand    %mm0, %mm7      C diagonal low
 
327
        psrlq   $32, %mm0       C diagonal high
 
328
 
 
329
        movd    8(%edx), %mm3   C dst[2*size-2]
 
330
        psllq   $1, %mm3
 
331
        paddq   %mm3, %mm7
 
332
        paddq   %mm7, %mm2
 
333
        movd    %mm2, 8(%edx)
 
334
        psrlq   $32, %mm2
 
335
 
 
336
        paddq   %mm0, %mm2
 
337
        movd    %mm2, 12(%edx)  C dst[2*size-1]
 
338
 
 
339
        ASSERT(z,`      C no further carry
 
340
        psrlq   $32, %mm2
 
341
        movd    %mm2, %eax
 
342
        orl     %eax, %eax')
 
343
 
 
344
 
 
345
        movl    SAVE_ESI, %esi
 
346
        movl    SAVE_EDI, %edi
 
347
        movl    SAVE_EBP, %ebp
 
348
        addl    $STACK_SPACE, %esp
 
349
        emms
 
350
        ret
 
351
 
 
352
EPILOGUE()