mpn/powerpc32/mode1o.asm

   1 dnl  PowerPC-32 mpn_modexact_1_odd -- mpn by limb exact remainder.
   2
   3 dnl  Copyright 2002, 2003, 2005, 2006 Free Software Foundation, Inc.
   4 dnl
   5 dnl  This file is part of the GNU MP Library.
   6 dnl
   7 dnl  The GNU MP Library is free software; you can redistribute it and/or
   8 dnl  modify it under the terms of the GNU Lesser General Public License as
   9 dnl  published by the Free Software Foundation; either version 3 of the
  10 dnl  License, or (at your option) any later version.
  11 dnl
  12 dnl  The GNU MP Library is distributed in the hope that it will be useful,
  13 dnl  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 dnl  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15 dnl  Lesser General Public License for more details.
  16 dnl
  17 dnl  You should have received a copy of the GNU Lesser General Public License
  18 dnl  along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.
  19
  20 include(`../config.m4')
  21
  22
  23 C                cycles/limb
  24 C 603e:             ?
  25 C 604e:             6.0
  26 C 75x (G3):         6.0-13.0, depending on divisor
  27 C 7400,7410 (G4):   6.0-13.0, depending on divisor
  28 C 744x,745x (G4+):  8.0-10.0, depending on divisor
  29 C power4/ppc970:   12.0
  30 C power5:          12.0
  31
  32
  33 C mp_limb_t mpn_modexact_1_odd (mp_srcptr src, mp_size_t size,
  34 C                               mp_limb_t divisor);
  35 C mp_limb_t mpn_modexact_1c_odd (mp_srcptr src, mp_size_t size,
  36 C                                mp_limb_t divisor, mp_limb_t carry);
  37 C
  38 C For PIC, the inverse is established arithmetically since it measures about
  39 C 5 cycles faster than the nonsense needed to access binvert_limb_table in
  40 C SVR4 or Darwin style PIC.  AIX might be better, since it avoids bl/mflr to
  41 C get at the GOT/TOC/whatever.
  42 C
  43 C Using divwu for size==1 measured about 10 cycles slower on 604e, or about
  44 C 3-5 cycles faster on 750.  For now it doesn't seem worth bothering with.
  45 C
  46 C The loop allows an early-out on mullw for the inverse, and on mulhwu for
  47 C the divisor.  So the fastest is for instance divisor==1 (inverse==-1), and
  48 C the slowest is anything giving a full 32-bits in both, such as
  49 C divisor==0xDEADBEEF (inverse==0x904B300F).  These establish the stated
  50 C range above for 750 and 7400.
  51
  52
  53 ASM_START()
  54
  55 EXTERN(binvert_limb_table)
  56
  57 PROLOGUE(mpn_modexact_1_odd)
  58         li      r6, 0
  59
  60 PROLOGUE(mpn_modexact_1c_odd)
  61
  62         mtctr   r4                      C size
  63
  64 ifdef(`PIC_SLOW',`
  65 C Load from our table with PIC is so slow on Linux and Darwin that we avoid it
  66         rlwinm  r7, r5, 1,28,28         C (divisor << 1) & 8
  67         rlwinm  r8, r5, 2,28,28         C (divisor << 2) & 8
  68         xor     r7, r7, r8              C ((divisor << 1) ^ (divisor << 2)) & 8
  69         rlwinm  r4, r5, 0,28,31         C divisor low 4 bits, speedup mullw
  70         xor     r4, r4, r7              C inverse, 4 bits
  71         mullw   r7, r4, r4              C i*i
  72         slwi    r4, r4, 1               C 2*i
  73         rlwinm  r8, r5, 0,24,31         C divisor low 8 bits, speedup mullw
  74         mullw   r7, r7, r8              C i*i*d
  75         sub     r4, r4, r7              C inverse, 8 bits
  76 ',`
  77         LEA(    r7, binvert_limb_table)
  78         rlwinm  r4, r5, 31,25,31        C (divisor/2) & 0x7F
  79         lbzx    r4, r4,r7               C inverse, 8 bits
  80 ')
  81
  82         mullw   r7, r4, r4              C i*i
  83         slwi    r4, r4, 1               C 2*i
  84         mullw   r7, r5, r7              C i*i*d   [i*i is 16 bits, so second operand]
  85         sub     r4, r4, r7              C inverse, 16 bits
  86         mullw   r7, r4, r4              C i*i
  87         slwi    r4, r4, 1               C 2*i
  88         mullw   r7, r7, r5              C i*i*d
  89         lwz     r0, 0(r3)               C src[0]
  90         sub     r4, r4, r7              C inverse, 32 bits
  91         subfc   r7, r6, r0              C l = src[0] - carry
  92
  93         mullw   r7, r7, r4              C q = l * inverse
  94         bdz     L(one)
  95
  96         lwzu    r0, 4(r3)               C src[1]
  97         mulhwu  r6, r7, r5              C carry = high(q*divisor)
  98         subfe   r7, r6, r0              C l = src[1] - carry
  99         bdz     L(two)
 100
 101 L(top):
 102         mullw   r7, r7, r4              C q = l * inverse
 103         lwzu    r0, 4(r3)               C src[i]
 104         mulhwu  r6, r7, r5              C carry = high(q*divisor)
 105         subfe   r7, r6, r0              C l = src[i] - carry
 106         bdnz    L(top)
 107
 108 L(two): mullw   r7, r7, r4              C q = l * inverse
 109 L(one): subfe   r3, r3, r3              C ca 0 or -1
 110         mulhwu  r6, r7, r5              C carry = high(q*divisor)
 111         subf    r3, r3, r6              C carry + ca
 112         blr
 113
 114 EPILOGUE(mpn_modexact_1c_odd)
 115 EPILOGUE(mpn_modexact_1_odd)
 116 ASM_END()