redc_1.asm
上传用户:qaz666999
上传日期:2022-08-06
资源大小:2570k
文件大小:6k
源码类别:

数学计算

开发平台:

Unix_Linux

  1. dnl  AMD64 mpn_redc_1 -- Montgomery reduction with a one-limb modular inverse.
  2. dnl  Copyright 2004, 2008 Free Software Foundation, Inc.
  3. dnl
  4. dnl  This file is part of the GNU MP Library.
  5. dnl
  6. dnl  The GNU MP Library is free software; you can redistribute it and/or
  7. dnl  modify it under the terms of the GNU Lesser General Public License as
  8. dnl  published by the Free Software Foundation; either version 3 of the
  9. dnl  License, or (at your option) any later version.
  10. dnl
  11. dnl  The GNU MP Library is distributed in the hope that it will be useful,
  12. dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14. dnl  Lesser General Public License for more details.
  15. dnl
  16. dnl  You should have received a copy of the GNU Lesser General Public License
  17. dnl  along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.
  18. include(`../config.m4')
  19. C      cycles/limb
  20. C      cycles/limb
  21. C K8,K9:  2.5
  22. C K10:  2.5
  23. C P4:  ?
  24. C P6-15 (Core2): 5.3
  25. C P6-28 (Atom):  ?
  26. C TODO
  27. C  * Handle certain sizes, e.g., 1, 2, 3, 4, 8, with single-loop code.
  28. C    The code for 1, 2, 3, 4 should perhaps be completely register based.
  29. C  * Perhaps align outer loops.
  30. C  * The sub_n at the end leaks side-channel data.  How do we fix that?
  31. C  * Write mpn_add_n_sub_n computing R = A + B - C.  It should run at 2 c/l.
  32. C  * We could software pipeline the IMUL stuff, by putting it before the
  33. C    outer loops and before the end of the outer loops.  The last outer
  34. C    loop iteration would then compute an unneeded product, but it is at
  35. C    least not a stray read from up[], since it is at up[n].
  36. C  * Can we combine both the add_n and sub_n into the loops, somehow?
  37. C INPUT PARAMETERS
  38. define(`rp',   `%rdi')
  39. define(`up',   `%rsi')
  40. define(`param_mp',`%rdx')
  41. define(`n',   `%rcx')
  42. define(`invm',   `%r8')
  43. define(`mp',   `%r13')
  44. define(`i',   `%r11')
  45. define(`nneg',   `%r12')
  46. ASM_START()
  47. TEXT
  48. ALIGN(32)
  49. PROLOGUE(mpn_redc_1)
  50. push %rbp
  51. push %rbx
  52. push %r12
  53. push %r13
  54. push %r14
  55. push n
  56. sub $8, %rsp C maintain ABI required rsp alignment
  57. lea (param_mp,n,8), mp C mp += n
  58. lea (up,n,8), up C up += n
  59. mov n, nneg
  60. neg nneg
  61. mov R32(n), R32(%rax)
  62. and $3, R32(%rax)
  63. jz L(b0)
  64. cmp $2, R32(%rax)
  65. jz L(b2)
  66. jg L(b3)
  67. L(b1): C lea (mp), mp
  68. lea -16(up), up
  69. L(o1): mov nneg, i
  70. mov 16(up,nneg,8), %rbp C up[0]
  71. imul invm, %rbp
  72. mov (mp,i,8), %rax
  73. xor %ebx, %ebx
  74. mul %rbp
  75. add $1, i
  76. jnz 1f
  77. add %rax, 8(up,i,8)
  78. adc $0, %rdx
  79. mov %rdx, %r14
  80. jmp L(n1)
  81. 1: mov %rax, %r9
  82. mov (mp,i,8), %rax
  83. mov %rdx, %r14
  84. jmp L(mi1)
  85. ALIGN(16)
  86. L(lo1): add %r10, (up,i,8)
  87. adc %rax, %r9
  88. mov (mp,i,8), %rax
  89. adc %rdx, %r14
  90. L(mi1): xor %r10d, %r10d
  91. mul %rbp
  92. add %r9, 8(up,i,8)
  93. adc %rax, %r14
  94. adc %rdx, %rbx
  95. mov 8(mp,i,8), %rax
  96. mul %rbp
  97. add %r14, 16(up,i,8)
  98. adc %rax, %rbx
  99. adc %rdx, %r10
  100. mov 16(mp,i,8), %rax
  101. mul %rbp
  102. xor %r9d, %r9d
  103. xor %r14d, %r14d
  104. add %rbx, 24(up,i,8)
  105. adc %rax, %r10
  106. mov 24(mp,i,8), %rax
  107. adc %rdx, %r9
  108. xor %ebx, %ebx
  109. mul %rbp
  110. add $4, i
  111. js L(lo1)
  112. L(ed1): add %r10, (up)
  113. adc %rax, %r9
  114. adc %rdx, %r14
  115. xor %r10d, %r10d
  116. add %r9, 8(up)
  117. adc $0, %r14
  118. L(n1): mov %r14, 16(up,nneg,8) C up[0]
  119. add $8, up
  120. dec n
  121. jnz L(o1)
  122. C lea (mp), mp
  123. lea 16(up), up
  124. jmp L(common)
  125. L(b0): C lea (mp), mp
  126. lea -16(up), up
  127. L(o0): mov nneg, i
  128. mov 16(up,nneg,8), %rbp C up[0]
  129. imul invm, %rbp
  130. mov (mp,i,8), %rax
  131. xor %r10d, %r10d
  132. mul %rbp
  133. mov %rax, %r14
  134. mov %rdx, %rbx
  135. jmp L(mi0)
  136. ALIGN(16)
  137. L(lo0): add %r10, (up,i,8)
  138. adc %rax, %r9
  139. mov (mp,i,8), %rax
  140. adc %rdx, %r14
  141. xor %r10d, %r10d
  142. mul %rbp
  143. add %r9, 8(up,i,8)
  144. adc %rax, %r14
  145. adc %rdx, %rbx
  146. L(mi0): mov 8(mp,i,8), %rax
  147. mul %rbp
  148. add %r14, 16(up,i,8)
  149. adc %rax, %rbx
  150. adc %rdx, %r10
  151. mov 16(mp,i,8), %rax
  152. mul %rbp
  153. xor %r9d, %r9d
  154. xor %r14d, %r14d
  155. add %rbx, 24(up,i,8)
  156. adc %rax, %r10
  157. mov 24(mp,i,8), %rax
  158. adc %rdx, %r9
  159. xor %ebx, %ebx
  160. mul %rbp
  161. add $4, i
  162. js L(lo0)
  163. L(ed0): add %r10, (up)
  164. adc %rax, %r9
  165. adc %rdx, %r14
  166. xor %r10d, %r10d
  167. add %r9, 8(up)
  168. adc $0, %r14
  169. mov %r14, 16(up,nneg,8) C up[0]
  170. add $8, up
  171. dec n
  172. jnz L(o0)
  173. C lea (mp), mp
  174. lea 16(up), up
  175. jmp L(common)
  176. L(b3): lea -8(mp), mp
  177. lea -24(up), up
  178. L(o3): mov nneg, i
  179. mov 24(up,nneg,8), %rbp C up[0]
  180. imul invm, %rbp
  181. mov 8(mp,i,8), %rax
  182. mul %rbp
  183. mov %rax, %rbx
  184. mov %rdx, %r10
  185. jmp L(mi3)
  186. ALIGN(16)
  187. L(lo3): add %r10, (up,i,8)
  188. adc %rax, %r9
  189. mov (mp,i,8), %rax
  190. adc %rdx, %r14
  191. xor %r10d, %r10d
  192. mul %rbp
  193. add %r9, 8(up,i,8)
  194. adc %rax, %r14
  195. adc %rdx, %rbx
  196. mov 8(mp,i,8), %rax
  197. mul %rbp
  198. add %r14, 16(up,i,8)
  199. adc %rax, %rbx
  200. adc %rdx, %r10
  201. L(mi3): mov 16(mp,i,8), %rax
  202. mul %rbp
  203. xor %r9d, %r9d
  204. xor %r14d, %r14d
  205. add %rbx, 24(up,i,8)
  206. adc %rax, %r10
  207. mov 24(mp,i,8), %rax
  208. adc %rdx, %r9
  209. xor %ebx, %ebx
  210. mul %rbp
  211. add $4, i
  212. js L(lo3)
  213. L(ed3): add %r10, 8(up)
  214. adc %rax, %r9
  215. adc %rdx, %r14
  216. xor %r10d, %r10d
  217. add %r9, 16(up)
  218. adc $0, %r14
  219. mov %r14, 24(up,nneg,8) C up[0]
  220. add $8, up
  221. dec n
  222. jnz L(o3)
  223. lea 8(mp), mp
  224. lea 24(up), up
  225. jmp L(common)
  226. L(b2): lea -16(mp), mp
  227. lea -32(up), up
  228. L(o2): mov nneg, i
  229. mov 32(up,nneg,8), %rbp C up[0]
  230. imul invm, %rbp
  231. mov 16(mp,i,8), %rax
  232. mul %rbp
  233. xor %r14d, %r14d
  234. mov %rax, %r10
  235. mov 24(mp,i,8), %rax
  236. mov %rdx, %r9
  237. jmp L(mi2)
  238. ALIGN(16)
  239. L(lo2): add %r10, (up,i,8)
  240. adc %rax, %r9
  241. mov (mp,i,8), %rax
  242. adc %rdx, %r14
  243. xor %r10d, %r10d
  244. mul %rbp
  245. add %r9, 8(up,i,8)
  246. adc %rax, %r14
  247. adc %rdx, %rbx
  248. mov 8(mp,i,8), %rax
  249. mul %rbp
  250. add %r14, 16(up,i,8)
  251. adc %rax, %rbx
  252. adc %rdx, %r10
  253. mov 16(mp,i,8), %rax
  254. mul %rbp
  255. xor %r9d, %r9d
  256. xor %r14d, %r14d
  257. add %rbx, 24(up,i,8)
  258. adc %rax, %r10
  259. mov 24(mp,i,8), %rax
  260. adc %rdx, %r9
  261. L(mi2): xor %ebx, %ebx
  262. mul %rbp
  263. add $4, i
  264. js L(lo2)
  265. L(ed2): add %r10, 16(up)
  266. adc %rax, %r9
  267. adc %rdx, %r14
  268. xor %r10d, %r10d
  269. add %r9, 24(up)
  270. adc $0, %r14
  271. mov %r14, 32(up,nneg,8) C up[0]
  272. add $8, up
  273. dec n
  274. jnz L(o2)
  275. lea 16(mp), mp
  276. lea 32(up), up
  277. L(common):
  278. lea (mp,nneg,8), mp C restore entry mp
  279. C   cy = mpn_add_n (rp, up, up - n, n);
  280. C     rdi rsi  rdx    rcx
  281. lea (up,nneg,8), up C up -= n
  282. lea (up,nneg,8), %rdx C rdx = up - n [up entry value]
  283. mov rp, nneg C preserve rp over first call
  284. mov 8(%rsp), %rcx C pass entry n
  285. C mov rp, %rdi
  286. CALL( mpn_add_n)
  287. test R32(%rax), R32(%rax)
  288. jz L(ret)
  289. C     mpn_sub_n (rp, rp, mp, n);
  290. C  rdi rsi rdx rcx
  291. mov nneg, %rdi
  292. mov nneg, %rsi
  293. mov mp, %rdx
  294. mov 8(%rsp), %rcx C pass entry n
  295. CALL( mpn_sub_n)
  296. L(ret):
  297. add $8, %rsp
  298. pop n C just increment rsp
  299. pop %r14
  300. pop %r13
  301. pop %r12
  302. pop %rbx
  303. pop %rbp
  304. ret
  305. EPILOGUE()