![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gcd_1.asm CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / mpn / x86 / k7|
Return to gcd_1.asm CVS log | Up to [local] / OpenXM_contrib / gmp / mpn / x86 / k7 |
1.1 ohara 1: dnl AMD K7 mpn_gcd_1 -- mpn by 1 gcd.
2:
3: dnl Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
4: dnl
5: dnl This file is part of the GNU MP Library.
6: dnl
7: dnl The GNU MP Library is free software; you can redistribute it and/or
8: dnl modify it under the terms of the GNU Lesser General Public License as
9: dnl published by the Free Software Foundation; either version 2.1 of the
10: dnl License, or (at your option) any later version.
11: dnl
12: dnl The GNU MP Library is distributed in the hope that it will be useful,
13: dnl but WITHOUT ANY WARRANTY; without even the implied warranty of
14: dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15: dnl Lesser General Public License for more details.
16: dnl
17: dnl You should have received a copy of the GNU Lesser General Public
18: dnl License along with the GNU MP Library; see the file COPYING.LIB. If
19: dnl not, write to the Free Software Foundation, Inc., 59 Temple Place -
20: dnl Suite 330, Boston, MA 02111-1307, USA.
21:
22: include(`../config.m4')
23:
24:
25: C K7: 6.75 cycles/bit (approx) 1x1 gcd
26: C 11.0 cycles/limb Nx1 reduction (modexact_1_odd)
27:
28:
29: dnl Reduce using x%y if x is more than DIV_THRESHOLD bits bigger than y,
30: dnl where x is the larger of the two. See tune/README for more.
31: dnl
32: dnl divl at 40 cycles compared to the gcd at about 7 cycles/bitpair
33: dnl suggests 40/7*2=11.4 but 7 seems to be about right.
34:
35: deflit(DIV_THRESHOLD, 7)
36:
37:
38: C table[n] is the number of trailing zeros on n, or MAXSHIFT if n==0.
39: C
40: C This is mixed in with the code, but as per the k7 optimization manual it's
41: C a full cache line and suitably aligned so it won't get swapped between
42: C code and data. Having it in TEXT rather than RODATA saves needing a GOT
43: C entry when PIC.
44: C
45: C Actually, there doesn't seem to be a measurable difference between this in
46: C it's own cache line or plonked in the middle of the code. Presumably
47: C since TEXT is read-only there's no worries about coherency.
48:
49: deflit(MASK, 63)
50: deflit(MAXSHIFT, 6)
51:
52: TEXT
53: ALIGN(64)
54: L(table):
55: .byte MAXSHIFT
56: forloop(i,1,MASK,
57: ` .byte m4_count_trailing_zeros(i)
58: ')
59:
60:
61: C mp_limb_t mpn_gcd_1 (mp_srcptr src, mp_size_t size, mp_limb_t limb);
62: C
63:
64: defframe(PARAM_LIMB, 12)
65: defframe(PARAM_SIZE, 8)
66: defframe(PARAM_SRC, 4)
67:
68: defframe(SAVE_EBX, -4)
69: defframe(SAVE_ESI, -8)
70: defframe(SAVE_EDI, -12)
71: defframe(SAVE_EBP, -16)
72: defframe(CALL_DIVISOR,-20)
73: defframe(CALL_SIZE, -24)
74: defframe(CALL_SRC, -28)
75:
76: deflit(STACK_SPACE, 28)
77:
78: TEXT
79: ALIGN(16)
80:
81: PROLOGUE(mpn_gcd_1)
82: deflit(`FRAME',0)
83:
84: ASSERT(ne, `cmpl $0, PARAM_LIMB') C y!=0
85: ASSERT(ae, `cmpl $1, PARAM_SIZE') C size>=1
86:
87: movl PARAM_SRC, %eax
88: movl PARAM_LIMB, %edx
89: subl $STACK_SPACE, %esp deflit(`FRAME',STACK_SPACE)
90:
91: movl %esi, SAVE_ESI
92: movl %ebx, SAVE_EBX
93:
94: movl (%eax), %esi C src low limb
95:
96: ifdef(`PIC',`
97: movl %edi, SAVE_EDI
98: call L(movl_eip_to_edi)
99: L(here):
100: addl $L(table)-L(here), %edi
101: ')
102:
103: movl %esi, %ebx
104: orl %edx, %esi C x|y
105: movl $-1, %ecx
106:
107: L(twos):
108: incl %ecx
109: shrl %esi
110: jnc L(twos) C 3/4 chance of x or y odd already
111:
112: shrl %cl, %ebx
113: shrl %cl, %edx
114: movl %ecx, %esi C common twos
115:
116: movl PARAM_SIZE, %ecx
117: cmpl $1, %ecx
118: ja L(divide)
119:
120:
121: C eax
122: C ebx x
123: C ecx
124: C edx y
125: C esi common twos
126: C edi [PIC] L(table)
127: C ebp
128:
129: movl %edx, %eax
130: cmpl %ebx, %edx
131:
132: cmovb( %ebx, %eax) C swap to make x bigger than y
133: cmovb( %edx, %ebx)
134:
135:
136: L(strip_y):
137: C eax x
138: C ebx y
139: C ecx
140: C edx
141: C esi common twos
142: C edi [PIC] L(table)
143: C ebp
144:
145: ASSERT(nz,`orl %ebx,%ebx')
146: shrl %ebx
147: jnc L(strip_y)
148: rcll %ebx
149:
150:
151: C eax x
152: C ebx y (odd)
153: C ecx
154: C edx
155: C esi common twos
156: C edi [PIC] L(table)
157: C ebp
158:
159: movl %eax, %ecx
160: movl %ebx, %edx
161: shrl $DIV_THRESHOLD, %eax
162:
163: cmpl %eax, %ebx
164: movl %ecx, %eax
165: ja L(strip_x_entry) C do x%y if x much bigger than y
166:
167:
168: xorl %edx, %edx
169:
170: divl %ebx
171:
172: orl %edx, %edx
173: movl %edx, %eax C remainder -> x
174: movl %ebx, %edx C y
175:
176: jz L(done_ebx)
177: jmp L(strip_x)
178:
179:
180: C Offset 0x9D here for non-PIC. About 0.4 cycles/bit is saved by
181: C ensuring the end of the jnz at the end of this loop doesn't cross
182: C into the next cache line at 0xC0.
183: C
184: C PIC on the other hand is offset 0xAC here and extends to 0xC9, so
185: C it crosses but doesn't suffer any measurable slowdown.
186:
187: L(top):
188: C eax x
189: C ebx y-x
190: C ecx x-y
191: C edx y
192: C esi twos, for use at end
193: C edi [PIC] L(table)
194:
195: cmovc( %ebx, %ecx) C if x-y gave carry, use x and y-x
196: cmovc( %eax, %edx)
197:
198: L(strip_x):
199: movl %ecx, %eax
200: L(strip_x_entry):
201: andl $MASK, %ecx
202:
203: ASSERT(nz, `orl %eax, %eax')
204:
205: ifdef(`PIC',`
206: movb (%ecx,%edi), %cl
207: ',`
208: movb L(table) (%ecx), %cl
209: ')
210:
211: shrl %cl, %eax
212: cmpb $MAXSHIFT, %cl
213:
214: movl %eax, %ecx
215: movl %edx, %ebx
216: je L(strip_x)
217:
218: ASSERT(nz, `testl $1, %eax') C both odd
219: ASSERT(nz, `testl $1, %edx')
220:
221: subl %eax, %ebx
222: subl %edx, %ecx
223: jnz L(top)
224:
225:
226: L(done):
227: movl %esi, %ecx
228: movl SAVE_ESI, %esi
229: ifdef(`PIC',`
230: movl SAVE_EDI, %edi
231: ')
232:
233: shll %cl, %eax
234: movl SAVE_EBX, %ebx
235: addl $FRAME, %esp
236:
237: ret
238:
239:
240:
241: C -----------------------------------------------------------------------------
242: C two or more limbs
243:
244: dnl MODEXACT_THRESHOLD is the size at which it's better to call
245: dnl mpn_modexact_1_odd than do an inline loop.
246:
247: deflit(MODEXACT_THRESHOLD, ifdef(`PIC',6,5))
248:
249: L(divide):
250: C eax src
251: C ebx
252: C ecx size
253: C edx y
254: C esi common twos
255: C edi [PIC] L(table)
256: C ebp
257:
258: L(divide_strip_y):
259: ASSERT(nz,`orl %edx,%edx')
260: shrl %edx
261: jnc L(divide_strip_y)
262: leal 1(%edx,%edx), %ebx C y now odd
263:
264: movl %ebp, SAVE_EBP
265: movl %eax, %ebp
266: movl -4(%eax,%ecx,4), %eax C src high limb
267:
268: cmp $MODEXACT_THRESHOLD, %ecx
269: jae L(modexact)
270:
271: cmpl %ebx, %eax C high cmp divisor
272: movl $0, %edx
273:
274: cmovc( %eax, %edx) C skip a div if high<divisor
275: sbbl $0, %ecx
276:
277:
278: L(divide_top):
279: C eax scratch (quotient)
280: C ebx y
281: C ecx counter (size to 1, inclusive)
282: C edx carry (remainder)
283: C esi common twos
284: C edi [PIC] L(table)
285: C ebp src
286:
287: movl -4(%ebp,%ecx,4), %eax
288:
289: divl %ebx
290:
291: decl %ecx
292: jnz L(divide_top)
293:
294:
295: C eax
296: C ebx y (odd)
297: C ecx
298: C edx x
299: C esi common twos
300: C edi [PIC] L(table)
301: C ebp
302:
303: orl %edx, %edx
304: movl SAVE_EBP, %ebp
305: movl %edx, %eax
306:
307: movl %edx, %ecx
308: movl %ebx, %edx
309: jnz L(strip_x_entry)
310:
311:
312: L(done_ebx):
313: movl %ebx, %eax
314: jmp L(done)
315:
316:
317:
318: L(modexact):
319: C eax
320: C ebx y
321: C ecx size
322: C edx
323: C esi common twos
324: C edi [PIC] L(table)
325: C ebp src
326:
327: ifdef(`PIC',`
328: movl %ebp, CALL_SRC
329: movl %ebx, %ebp C y
330: movl %edi, %ebx C L(table)
331:
332: addl $_GLOBAL_OFFSET_TABLE_+[.-L(table)], %ebx
333: movl %ebp, CALL_DIVISOR
334: movl %ecx, CALL_SIZE
335:
336: call GSYM_PREFIX`'mpn_modexact_1_odd@PLT
337: ',`
338: dnl non-PIC
339: movl %ebx, CALL_DIVISOR
340: movl %ebp, CALL_SRC
341: movl %ecx, CALL_SIZE
342:
343: call GSYM_PREFIX`'mpn_modexact_1_odd
344: ')
345:
346: C eax x
347: C ebx [non-PIC] y
348: C ecx
349: C edx
350: C esi common twos
351: C edi [PIC] L(table)
352: C ebp [PIC] y
353:
354: orl %eax, %eax
355: movl ifdef(`PIC',`%ebp',`%ebx'), %edx
356: movl SAVE_EBP, %ebp
357:
358: movl %eax, %ecx
359: jnz L(strip_x_entry)
360:
361: movl %edx, %eax
362: jmp L(done)
363:
364:
365: ifdef(`PIC', `
366: L(movl_eip_to_edi):
367: movl (%esp), %edi
368: ret
369: ')
370:
371: EPILOGUE()