mpn/x86_64/gcd_1.asm

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