dnl AMD K7 mpn_rshift -- mpn right shift.
dnl Copyright 1999-2002 Free Software Foundation,
Inc.
dnl
This file is part of the GNU MP Library.
dnl
dnl The GNU MP Library is free software
; you can redistribute it and/or modify
dnl it under the terms of either:
dnl
dnl * the GNU Lesser General
Public License as published by the Free
dnl Software Foundation
; either version 3 of the License, or (at your
dnl
option) any later
version.
dnl
dnl
or
dnl
dnl * the GNU General
Public License as published by the Free Software
dnl Foundation
; either version 2 of the License, or (at your option) any
dnl later
version.
dnl
dnl
or both in parallel, as here.
dnl
dnl The GNU MP Library is distributed in the hope that it will be useful, but
dnl WITHOUT ANY WARRANTY
; without even the implied warranty of MERCHANTABILITY
dnl
or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU General
Public License
dnl
for more details.
dnl
dnl You should have received copies of the GNU General
Public License
and the
dnl GNU Lesser General
Public License along with the GNU MP Library.
If not,
dnl see
https://www.gnu.org/licenses/.
include(`../config.m4
')
C K7: 1.21 cycles/limb (at 16 limbs/loop).
dnl K7: UNROLL_COUNT cycles/limb
dnl 4 1.51
dnl 8 1.26
dnl 16 1.21
dnl 32 1.2
dnl Maximum possible with the current
code is 64.
deflit(UNROLL_COUNT, 16)
C mp_limb_t mpn_rshift (mp_ptr dst, mp_srcptr src, mp_size_t size,
C unsigned shift)
;
C
C Shift src,size right by shift many bits
and store the result in dst,size.
C Zeros are shifted in at the left. The bits shifted out at the right are
C the return value.
C
C
This code uses 64-bit MMX operations, which makes it possible to handle
C two limbs at a
time,
for a theoretical 1.0 cycles/limb. Plain integer
C
code, on the other hand, suffers from shrd being a vector path decode
and
C running at 3 cycles back-to-back.
C
C Full speed depends on source
and destination being aligned,
and some hairy
C setups
and finish-ups are done to arrange
this for the loop.
ifdef(`PIC
',`
deflit(UNROLL_THRESHOLD, 10)
',`
deflit(UNROLL_THRESHOLD, 10)
')
defframe(PARAM_SHIFT,16)
defframe(PARAM_SIZE, 12)
defframe(PARAM_SRC, 8)
defframe(PARAM_DST, 4)
defframe(SAVE_EDI, -4)
defframe(SAVE_ESI, -8)
defframe(SAVE_EBX, -12)
deflit(SAVE_SIZE, 12)
TEXT
ALIGN(32)
PROLOGUE(mpn_rshift)
deflit(`FRAME
',0)
movl PARAM_SIZE, %
eax
movl PARAM_SRC, %
edx
subl $SAVE_SIZE, %
esp
deflit(`FRAME
',SAVE_SIZE)
movl PARAM_SHIFT, %
ecx
movl %
edi, SAVE_EDI
movl PARAM_DST, %
edi
decl %
eax
jnz L(more_than_one_limb)
movl (%
edx), %
edx C src limb
shrdl( %cl, %
edx, %
eax) C
eax was decremented to
zero
shrl %cl, %
edx
movl %
edx, (%
edi) C dst limb
movl SAVE_EDI, %
edi
addl $SAVE_SIZE, %
esp
ret
C -----------------------------------------------------------------------------
L(more_than_one_limb):
C
eax size-1
C ebx
C
ecx shift
C
edx src
C
esi
C
edi dst
C
ebp
movd PARAM_SHIFT, %mm6 C rshift
movd (%
edx), %mm5 C src low limb
cmp $UNROLL_THRESHOLD-1, %
eax
jae L(unroll)
leal (%
edx,%
eax,4), %
edx C &src[size-1]
leal -4(%
edi,%
eax,4), %
edi C &dst[size-2]
movd (%
edx), %mm4 C src high limb
negl %
eax
L(simple_top):
C
eax loop counter, limbs, negative
C ebx
C
ecx shift
C
edx carry
C
edx &src[size-1]
C
edi &dst[size-2]
C
ebp
C
C mm0 scratch
C mm4 src high limb
C mm5 src low limb
C mm6 shift
movq (%
edx,%
eax,4), %mm0
incl %
eax
psrlq %mm6, %mm0
movd %mm0, (%
edi,%
eax,4)
jnz L(simple_top)
psllq $32, %mm5
psrlq %mm6, %mm4
psrlq %mm6, %mm5
movd %mm4, 4(%
edi) C dst high limb
movd %mm5, %
eax C return value
movl SAVE_EDI, %
edi
addl $SAVE_SIZE, %
esp
emms
ret
C -----------------------------------------------------------------------------
ALIGN(16)
L(unroll):
C
eax size-1
C ebx
C
ecx shift
C
edx src
C
esi
C
edi dst
C
ebp
C
C mm5 src low limb
C mm6 rshift
testb $4, %dl
movl %
esi, SAVE_ESI
movl %ebx, SAVE_EBX
psllq $32, %mm5
jz L(start_src_aligned)
C src isn
't aligned, process low limb separately (marked xxx) and
C step src
and dst by one limb, making src aligned.
C
C source
edx
C --+-------+-------+-------+
C | xxx |
C --+-------+-------+-------+
C 4mod8 0mod8 4mod8
C
C dest
edi
C --+-------+-------+
C | | xxx |
C --+-------+-------+
movq (%
edx), %mm0 C src low two limbs
addl $4, %
edx
movl %
eax, PARAM_SIZE C size-1
addl $4, %
edi
decl %
eax C size-2 is new size-1
psrlq %mm6, %mm0
movl %
edi, PARAM_DST C new dst
movd %mm0, -4(%
edi)
L(start_src_aligned):
movq (%
edx), %mm1 C src low two limbs
decl %
eax C size-2, two last limbs handled at
end
testl $4, %
edi
psrlq %mm6, %mm5
jz L(start_dst_aligned)
C dst isn
't aligned, add 4 to make it so, and pretend the shift is
C 32 bits extra. Low limb of dst (marked xxx) handled here separately.
C
C source
edx
C --+-------+-------+
C | mm1 |
C --+-------+-------+
C 4mod8 0mod8
C
C dest
edi
C --+-------+-------+-------+
C | xxx |
C --+-------+-------+-------+
C 4mod8 0mod8 4mod8
movq %mm1, %mm0
psrlq %mm6, %mm1
addl $32, %
ecx C shift+32
movd %mm1, (%
edi)
movq %mm0, %mm1
addl $4, %
edi C new dst
movd %
ecx, %mm6
L(start_dst_aligned):
movq %mm1, %mm2 C copy of src low two limbs
negl %
ecx
andl $-2, %
eax C round size down to
even
movl %
eax, %ebx
negl %
eax
addl $64, %
ecx
andl $UNROLL_MASK, %
eax
decl %ebx
shll %
eax
movd %
ecx, %mm7 C lshift = 64-rshift
ifdef(`PIC
',`
call L(pic_calc)
L(here):
',`
leal L(entry) (%
eax,%
eax,4), %
esi
negl %
eax
')
shrl $UNROLL_LOG2, %ebx C loop counter
leal ifelse(UNROLL_BYTES,256,128+) 8(%
edx,%
eax,2), %
edx
leal ifelse(UNROLL_BYTES,256,128) (%
edi,%
eax,2), %
edi
movl PARAM_SIZE, %
eax C
for use at
end
jmp *%
esi
ifdef(`PIC
',`
L(pic_calc):
C See mpn/x86/README about old gas bugs
leal (%
eax,%
eax,4), %
esi
addl $L(entry)-L(here), %
esi
addl (%
esp), %
esi
negl %
eax
ret_internal
')
C -----------------------------------------------------------------------------
ALIGN(64)
L(top):
C
eax size,
for use at
end
C ebx loop counter
C
ecx lshift
C
edx src
C
esi was computed jump
C
edi dst
C
ebp
C
C mm0 scratch
C mm1 \
carry (alternating)
C mm2 /
C mm6 rshift
C mm7 lshift
C
C 10
code bytes/limb
C
C The two chunks differ in whether mm1
or mm2 hold the
carry.
C The computed jump puts the initial
carry in both mm1
and mm2.
L(entry):
deflit(CHUNK_COUNT, 4)
forloop(i, 0, UNROLL_COUNT/CHUNK_COUNT-1, `
deflit(`disp0
', eval(i*CHUNK_COUNT*4 ifelse(UNROLL_BYTES,256,-128)))
deflit(`disp1
', eval(disp0 + 8))
Zdisp( movq, disp0,(%
edx), %mm0)
psrlq %mm6, %mm2
movq %mm0, %mm1
psllq %mm7, %mm0
por %mm2, %mm0
Zdisp( movq, %mm0, disp0,(%
edi))
Zdisp( movq, disp1,(%
edx), %mm0)
psrlq %mm6, %mm1
movq %mm0, %mm2
psllq %mm7, %mm0
por %mm1, %mm0
Zdisp( movq, %mm0, disp1,(%
edi))
')
addl $UNROLL_BYTES, %
edx
addl $UNROLL_BYTES, %
edi
decl %ebx
jns L(top)
deflit(`disp0
', ifelse(UNROLL_BYTES,256,-128))
deflit(`disp1
', eval(disp0-0 + 8))
testb $1, %al
psrlq %mm6, %mm2 C wanted rshifted in all cases below
movl SAVE_ESI, %
esi
movd %mm5, %
eax C return value
movl SAVE_EBX, %ebx
jz L(end_even)
C Size odd, destination was aligned.
C
C source
C
edx
C +-------+---------------+--
C | | mm2 |
C +-------+---------------+--
C
C dest
edi
C +-------+---------------+---------------+--
C | | | written |
C +-------+---------------+---------------+--
C
C mm6 = shift
C mm7 =
ecx = 64-shift
C Size odd, destination was unaligned.
C
C source
C
edx
C +-------+---------------+--
C | | mm2 |
C +-------+---------------+--
C
C dest
edi
C +---------------+---------------+--
C | | written |
C +---------------+---------------+--
C
C mm6 = shift+32
C mm7 =
ecx = 64-(shift+32)
C In both cases there
's one extra limb of src to fetch and combine
C with mm2 to make a
qword to store,
and in the aligned case there
's
C a further extra limb of dst to be formed.
movd disp0(%
edx), %mm0
movq %mm0, %mm1
psllq %mm7, %mm0
testb $32, %cl
por %mm2, %mm0
psrlq %mm6, %mm1
movq %mm0, disp0(%
edi)
jz L(finish_odd_unaligned)
movd %mm1, disp1(%
edi)
L(finish_odd_unaligned):
movl SAVE_EDI, %
edi
addl $SAVE_SIZE, %
esp
emms
ret
L(end_even):
C Size
even, destination was aligned.
C
C source
C +---------------+--
C | mm2 |
C +---------------+--
C
C dest
edi
C +---------------+---------------+--
C | | mm3 |
C +---------------+---------------+--
C
C mm6 = shift
C mm7 =
ecx = 64-shift
C Size
even, destination was unaligned.
C
C source
C +---------------+--
C | mm2 |
C +---------------+--
C
C dest
edi
C +-------+---------------+--
C | | mm3 |
C +-------+---------------+--
C
C mm6 = shift+32
C mm7 = 64-(shift+32)
C The
movd for the unaligned case is the same
data as the movq
for
C the aligned case, it
's just a choice between whether one or two
C limbs should be written.
testb $32, %cl
movd %mm2, disp0(%
edi)
jz L(end_even_unaligned)
movq %mm2, disp0(%
edi)
L(end_even_unaligned):
movl SAVE_EDI, %
edi
addl $SAVE_SIZE, %
esp
emms
ret
EPILOGUE()
