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

数学计算

开发平台:

Unix_Linux

  1. dnl  AMD64 mpn_gcd_1 -- mpn by 1 gcd.
  2. dnl  Based on the K7 gcd_1.asm, by Kevin Ryde.  Rehacked for AMD64 by Torbjorn
  3. dnl  Granlund.
  4. dnl  Copyright 2000, 2001, 2002, 2005, 2009 Free Software Foundation, Inc.
  5. dnl  This file is part of the GNU MP Library.
  6. dnl  The GNU MP Library is free software; you can redistribute it and/or modify
  7. dnl  it under the terms of the GNU Lesser General Public License as published
  8. dnl  by the Free Software Foundation; either version 3 of the License, or (at
  9. dnl  your option) any later version.
  10. dnl  The GNU MP Library is distributed in the hope that it will be useful, but
  11. dnl  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12. dnl  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  13. dnl  License for more details.
  14. dnl  You should have received a copy of the GNU Lesser General Public License
  15. dnl  along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.
  16. include(`../config.m4')
  17. C K8: 6.75 cycles/bit (approx)  1x1 gcd
  18. C     10.0 cycles/limb          Nx1 reduction (modexact_1_odd)
  19. dnl  Reduce using x%y if x is more than DIV_THRESHOLD bits bigger than y,
  20. dnl  where x is the larger of the two.  See tune/README for more.
  21. dnl
  22. dnl  div at 80 cycles compared to the gcd at about 7 cycles/bitpair
  23. dnl  suggests 80/7*2=23
  24. deflit(DIV_THRESHOLD, 23)
  25. C ctz_table[n] is the number of trailing zeros on n, or MAXSHIFT if n==0.
  26. deflit(MAXSHIFT, 6)
  27. deflit(MASK, eval((1<<MAXSHIFT)-1))
  28. DEF_OBJECT(ctz_table,64)
  29. .byte MAXSHIFT
  30. forloop(i,1,MASK,
  31. ` .byte m4_count_trailing_zeros(i)
  32. ')
  33. END_OBJECT(ctz_table)
  34. C mp_limb_t mpn_gcd_1 (mp_srcptr up, mp_size_t n, mp_limb_t vlimb);
  35. C INPUT PARAMETERS
  36. define(`up',    `%rdi')
  37. define(`n',     `%rsi')
  38. define(`vlimb', `%rdx')
  39. TEXT
  40. ALIGN(16)
  41. PROLOGUE(mpn_gcd_1)
  42. mov (%rdi), %r8 C src low limb
  43. or %rdx, %r8 C x | y
  44. mov $-1, R32(%rcx)
  45. L(twos):
  46. inc R32(%rcx)
  47. shr %r8
  48. jnc L(twos)
  49. shr R8(%rcx), %rdx
  50. mov R32(%rcx), R32(%r8) C common twos
  51. L(divide_strip_y):
  52. shr %rdx
  53. jnc L(divide_strip_y)
  54. adc %rdx, %rdx
  55. push %r8
  56. push %rdx
  57. sub $8, %rsp C maintain ABI required rsp alignment
  58. CALL( mpn_modexact_1_odd)
  59. add $8, %rsp
  60. pop %rdx
  61. pop %r8
  62. test %rax, %rax
  63. mov %rax, %rcx
  64. jnz L(strip_x)
  65. mov %rdx, %rax
  66. jmp L(done)
  67. L(strip_x):
  68. LEA( ctz_table, %r9)
  69. jmp L(strip_x_top)
  70. ALIGN(16)
  71. L(top):
  72. cmovc %r10, %rcx C if x-y gave carry, use x,y-x 0
  73. cmovc %rax, %rdx C 0
  74. L(strip_x_top):
  75. mov %rcx, %rax C 1
  76. and $MASK, R32(%rcx) C 1
  77. mov (%r9,%rcx), R8(%rcx) C 1
  78. shr R8(%rcx), %rax C 4
  79. cmp $MAXSHIFT, R8(%rcx) C 4
  80. mov %rax, %rcx C 5
  81. mov %rdx, %r10 C 5
  82. je L(strip_x_top) C 5
  83. sub %rax, %r10 C 6
  84. sub %rdx, %rcx C 6
  85. jnz L(top) C 6
  86. L(done):
  87. mov %r8, %rcx
  88. shl R8(%rcx), %rax
  89. ret
  90. EPILOGUE()