1dnl  AMD K7 mpn_divexact_1 -- mpn by limb exact division.
2
3dnl  Copyright 2001, 2002, 2004, 2007 Free Software Foundation, Inc.
4
5dnl  This file is part of the GNU MP Library.
6dnl
7dnl  The GNU MP Library is free software; you can redistribute it and/or modify
8dnl  it under the terms of either:
9dnl
10dnl    * the GNU Lesser General Public License as published by the Free
11dnl      Software Foundation; either version 3 of the License, or (at your
12dnl      option) any later version.
13dnl
14dnl  or
15dnl
16dnl    * the GNU General Public License as published by the Free Software
17dnl      Foundation; either version 2 of the License, or (at your option) any
18dnl      later version.
19dnl
20dnl  or both in parallel, as here.
21dnl
22dnl  The GNU MP Library is distributed in the hope that it will be useful, but
23dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
25dnl  for more details.
26dnl
27dnl  You should have received copies of the GNU General Public License and the
28dnl  GNU Lesser General Public License along with the GNU MP Library.  If not,
29dnl  see https://www.gnu.org/licenses/.
30
31include(`../config.m4')
32
33
34C          cycles/limb
35C Athlon:     11.0
36C Hammer:      9.0
37
38
39C void mpn_divexact_1 (mp_ptr dst, mp_srcptr src, mp_size_t size,
40C                      mp_limb_t divisor);
41C
42C The dependent chain is mul+imul+sub for 11 cycles and that speed is
43C achieved with no special effort.  The load and shrld latencies are hidden
44C by out of order execution.
45C
46C It's a touch faster on size==1 to use the mul-by-inverse than divl.
47
48defframe(PARAM_DIVISOR,16)
49defframe(PARAM_SIZE,   12)
50defframe(PARAM_SRC,    8)
51defframe(PARAM_DST,    4)
52
53defframe(SAVE_EBX,     -4)
54defframe(SAVE_ESI,     -8)
55defframe(SAVE_EDI,    -12)
56defframe(SAVE_EBP,    -16)
57defframe(VAR_INVERSE, -20)
58defframe(VAR_DST_END, -24)
59
60deflit(STACK_SPACE, 24)
61
62          TEXT
63
64          ALIGN(16)
65PROLOGUE(mpn_divexact_1)
66deflit(`FRAME',0)
67
68          movl      PARAM_DIVISOR, %eax
69          subl      $STACK_SPACE, %esp  deflit(`FRAME',STACK_SPACE)
70          movl      $-1, %ecx           C shift count
71
72          movl      %ebp, SAVE_EBP
73          movl      PARAM_SIZE, %ebp
74
75          movl      %esi, SAVE_ESI
76          movl      %edi, SAVE_EDI
77
78          C If there's usually only one or two trailing zero bits then this
79          C should be faster than bsfl.
80L(strip_twos):
81          incl      %ecx
82          shrl      %eax
83          jnc       L(strip_twos)
84
85          movl      %ebx, SAVE_EBX
86          leal      1(%eax,%eax), %ebx  C d without twos
87          andl      $127, %eax                    C d/2, 7 bits
88
89ifdef(`PIC',`
90          LEA(      binvert_limb_table, %edx)
91          movzbl    (%eax,%edx), %eax             C inv 8 bits
92',`
93          movzbl    binvert_limb_table(%eax), %eax          C inv 8 bits
94')
95
96          leal      (%eax,%eax), %edx   C 2*inv
97          movl      %ebx, PARAM_DIVISOR C d without twos
98
99          imull     %eax, %eax                    C inv*inv
100
101          movl      PARAM_SRC, %esi
102          movl      PARAM_DST, %edi
103
104          imull     %ebx, %eax                    C inv*inv*d
105
106          subl      %eax, %edx                    C inv = 2*inv - inv*inv*d
107          leal      (%edx,%edx), %eax   C 2*inv
108
109          imull     %edx, %edx                    C inv*inv
110
111          leal      (%esi,%ebp,4), %esi C src end
112          leal      (%edi,%ebp,4), %edi C dst end
113          negl      %ebp                          C -size
114
115          imull     %ebx, %edx                    C inv*inv*d
116
117          subl      %edx, %eax                    C inv = 2*inv - inv*inv*d
118
119          ASSERT(e,`          C expect d*inv == 1 mod 2^GMP_LIMB_BITS
120          pushl     %eax      FRAME_pushl()
121          imull     PARAM_DIVISOR, %eax
122          cmpl      $1, %eax
123          popl      %eax      FRAME_popl()')
124
125          movl      %eax, VAR_INVERSE
126          movl      (%esi,%ebp,4), %eax C src[0]
127
128          incl      %ebp
129          jz        L(one)
130
131          movl      (%esi,%ebp,4), %edx C src[1]
132
133          shrdl(    %cl, %edx, %eax)
134
135          movl      %edi, VAR_DST_END
136          xorl      %ebx, %ebx
137          jmp       L(entry)
138
139          ALIGN(8)
140L(top):
141          C eax     q
142          C ebx     carry bit, 0 or 1
143          C ecx     shift
144          C edx
145          C esi     src end
146          C edi     dst end
147          C ebp     counter, limbs, negative
148
149          mull      PARAM_DIVISOR                 C carry limb in edx
150
151          movl      -4(%esi,%ebp,4), %eax
152          movl      (%esi,%ebp,4), %edi
153
154          shrdl(    %cl, %edi, %eax)
155
156          subl      %ebx, %eax                    C apply carry bit
157          setc      %bl
158          movl      VAR_DST_END, %edi
159
160          subl      %edx, %eax                    C apply carry limb
161          adcl      $0, %ebx
162
163L(entry):
164          imull     VAR_INVERSE, %eax
165
166          movl      %eax, -4(%edi,%ebp,4)
167          incl      %ebp
168          jnz       L(top)
169
170
171          mull      PARAM_DIVISOR                 C carry limb in edx
172
173          movl      -4(%esi), %eax                C src high limb
174          shrl      %cl, %eax
175          movl      SAVE_ESI, %esi
176
177          subl      %ebx, %eax                    C apply carry bit
178          movl      SAVE_EBX, %ebx
179          movl      SAVE_EBP, %ebp
180
181          subl      %edx, %eax                    C apply carry limb
182
183          imull     VAR_INVERSE, %eax
184
185          movl      %eax, -4(%edi)
186          movl      SAVE_EDI, %edi
187          addl      $STACK_SPACE, %esp
188
189          ret
190
191
192L(one):
193          shrl      %cl, %eax
194          movl      SAVE_ESI, %esi
195          movl      SAVE_EBX, %ebx
196
197          imull     VAR_INVERSE, %eax
198
199          movl      SAVE_EBP, %ebp
200          movl      %eax, -4(%edi)
201
202          movl      SAVE_EDI, %edi
203          addl      $STACK_SPACE, %esp
204
205          ret
206
207EPILOGUE()
208ASM_END()
209