1 dnl Intel P5 mpn_rshift -- mpn right shift.
3 dnl P5: 1.75 cycles/limb.
6 dnl Copyright (C) 2000 Free Software Foundation, Inc.
8 dnl This file is part of the GNU MP Library.
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.
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.
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.
26 include(`../config.m4')
29 C mp_limb_t mpn_rshift (mp_ptr dst, mp_srcptr src, mp_size_t size,
32 C Shift src,size right by shift many bits and store the result in dst,size.
33 C Zeros are shifted in at the left. Return the bits shifted out at the
36 C It takes 6 mmx instructions to process 2 limbs, making 1.5 cycles/limb,
37 C and with a 4 limb loop and 1 cycle of loop overhead the total is 1.75 c/l.
39 C Full speed depends on source and destination being aligned. Unaligned mmx
40 C loads and stores on P5 don't pair and have a 2 cycle penalty. Some hairy
41 C setups and finish-ups are done to ensure alignment for the loop.
43 C MMX shifts work out a bit faster even for the simple loop.
45 defframe(PARAM_SHIFT,16)
46 defframe(PARAM_SIZE, 12)
47 defframe(PARAM_SRC, 8)
48 defframe(PARAM_DST, 4)
51 dnl Minimum 5, because the unrolled loop can't handle less.
52 deflit(UNROLL_THRESHOLD, 5)
67 movl PARAM_SHIFT, %ecx
69 cmp $UNROLL_THRESHOLD, %eax
73 movl (%ebx), %edi C src low limb
77 shrdl( %cl, %edi, %eax) C eax was decremented to zero
81 movl %edi, (%edx) C dst low limb
82 popl %edi C risk of data cache bank clash
89 C -----------------------------------------------------------------------------
101 movd (%ebx), %mm5 C src[0]
102 leal (%ebx,%eax,4), %ebx C &src[size-1]
104 movd %ecx, %mm6 C rshift
105 leal -4(%edx,%eax,4), %edx C &dst[size-2]
111 C This loop is 5 or 8 cycles, with every second load unaligned and a wasted
112 C cycle waiting for the mm0 result to be ready. For comparison a shrdl is 4
113 C cycles and would be 8 in a simple loop. Using mmx helps the return value
114 C and last limb calculations too.
117 C eax counter, limbs, negative
126 movq (%ebx,%eax,4), %mm0
131 movd %mm0, (%edx,%eax,4)
136 psrlq %mm6, %mm5 C return value
151 C -----------------------------------------------------------------------------
163 movd (%ebx), %mm5 C src[0]
166 movd %ecx, %mm6 C rshift
170 jz L(start_src_aligned)
173 C src isn't aligned, process low limb separately (marked xxx) and
174 C step src and dst by one limb, making src aligned.
177 C --+-------+-------+-------+
179 C --+-------+-------+-------+
183 C --+-------+-------+
185 C --+-------+-------+
187 movq (%ebx), %mm0 C unaligned load
196 L(start_src_aligned):
202 psrlq %mm6, %mm5 C retval
203 jz L(start_dst_aligned)
205 C dst isn't aligned, add 4 to make it so, and pretend the shift is
206 C 32 bits extra. Low limb of dst (marked xxx) handled here
210 C --+-------+-------+
212 C --+-------+-------+
216 C --+-------+-------+-------+
218 C --+-------+-------+-------+
222 addl $32, %ecx C new shift
230 L(start_dst_aligned):
236 movq %mm3, %mm2 C mm2 src qword
242 leal -12(%ebx,%eax,4), %ebx
243 leal -20(%edx,%eax,4), %edx
246 subl $7, %eax C size-7
248 por %mm1, %mm3 C mm3 ready to store
249 negl %eax C -(size-7)
254 C This loop is the important bit, the rest is just support. Careful
255 C instruction scheduling achieves the claimed 1.75 c/l. The
256 C relevant parts of the pairing rules are:
258 C - mmx loads and stores execute only in the U pipe
259 C - only one mmx shift in a pair
260 C - wait one cycle before storing an mmx register result
261 C - the usual address generation interlock
263 C Two qword calculations are slightly interleaved. The instructions
264 C marked "C" belong to the second qword, and the "C prev" one is for
265 C the second qword from the previous iteration.
269 C eax counter, limbs, negative
278 C mm2 src qword from -8(%ebx,%eax,4)
279 C mm3 dst qword ready to store to -8(%edx,%eax,4)
285 movq (%ebx,%eax,4), %mm0
291 movq %mm3, -8(%edx,%eax,4) C prev
294 movq 8(%ebx,%eax,4), %mm3 C
297 movq %mm0, (%edx,%eax,4)
308 C eax 0 to 3 representing respectively 3 to 0 limbs remaining
314 movq (%ebx,%eax,4), %mm0
320 movq %mm3, -8(%edx,%eax,4) C prev
330 C eax 2 or 3 representing respectively 1 or 0 limbs remaining
332 C mm2 src prev qword, from -8(%ebx,%eax,4)
333 C mm3 dst qword, for -8(%edx,%eax,4)
338 movd %mm5, %eax C retval
342 C One extra limb, destination was aligned.
345 C +-------+---------------+--
347 C +-------+---------------+--
350 C +-------+---------------+---------------+--
352 C +-------+---------------+---------------+--
355 C mm7 = ecx = 64-shift
358 C One extra limb, destination was unaligned.
361 C +-------+---------------+--
363 C +-------+---------------+--
366 C +---------------+---------------+--
368 C +---------------+---------------+--
371 C mm7 = ecx = 64-(shift+32)
374 C In both cases there's one extra limb of src to fetch and combine
375 C with mm2 to make a qword at 8(%edx), and in the aligned case
376 C there's a further extra limb of dst to be formed.
392 jz L(finish_one_unaligned)
394 C dst was aligned, must store one extra limb
396 L(finish_one_unaligned):
407 C No extra limbs, destination was aligned.
410 C +---------------+--
412 C +---------------+--
415 C +---------------+---------------+--
417 C +---------------+---------------+--
420 C mm7 = ecx = 64-shift
423 C No extra limbs, destination was unaligned.
426 C +---------------+--
428 C +---------------+--
431 C +-------+---------------+--
433 C +-------+---------------+--
436 C mm7 = 64-(shift+32)
439 C The movd for the unaligned case is clearly the same data as the
440 C movq for the aligned case, it's just a choice between whether one
441 C or two limbs should be written.
451 jz L(finish_zero_unaligned)
454 L(finish_zero_unaligned):