1dnl PowerPC-32 mpn_modexact_1_odd -- mpn by limb exact remainder. 2 3dnl Copyright 2002, 2003, 2005, 2006 Free Software Foundation, Inc. 4dnl 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 8dnl modify it under the terms of the GNU Lesser General Public License as 9dnl published by the Free Software Foundation; either version 3 of the 10dnl License, or (at your option) any later version. 11dnl 12dnl The GNU MP Library is distributed in the hope that it will be useful, 13dnl but WITHOUT ANY WARRANTY; without even the implied warranty of 14dnl MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15dnl Lesser General Public License for more details. 16dnl 17dnl You should have received a copy of the GNU Lesser General Public License 18dnl along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. 19 20include(`../config.m4') 21 22 23C cycles/limb 24C 603e: ? 25C 604e: 6.0 26C 75x (G3): 6.0-13.0, depending on divisor 27C 7400,7410 (G4): 6.0-13.0, depending on divisor 28C 744x,745x (G4+): 8.0-10.0, depending on divisor 29C power4/ppc970: 12.0 30C power5: 12.0 31 32 33C mp_limb_t mpn_modexact_1_odd (mp_srcptr src, mp_size_t size, 34C mp_limb_t divisor); 35C mp_limb_t mpn_modexact_1c_odd (mp_srcptr src, mp_size_t size, 36C mp_limb_t divisor, mp_limb_t carry); 37C 38C For PIC, the inverse is established arithmetically since it measures about 39C 5 cycles faster than the nonsense needed to access binvert_limb_table in 40C SVR4 or Darwin style PIC. AIX might be better, since it avoids bl/mflr to 41C get at the GOT/TOC/whatever. 42C 43C Using divwu for size==1 measured about 10 cycles slower on 604e, or about 44C 3-5 cycles faster on 750. For now it doesn't seem worth bothering with. 45C 46C The loop allows an early-out on mullw for the inverse, and on mulhwu for 47C the divisor. So the fastest is for instance divisor==1 (inverse==-1), and 48C the slowest is anything giving a full 32-bits in both, such as 49C divisor==0xDEADBEEF (inverse==0x904B300F). These establish the stated 50C range above for 750 and 7400. 51 52 53ASM_START() 54 55EXTERN(binvert_limb_table) 56 57PROLOGUE(mpn_modexact_1_odd) 58 li r6, 0 59 60PROLOGUE(mpn_modexact_1c_odd) 61 62 mtctr r4 C size 63 64ifdef(`PIC_SLOW',` 65C 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 101L(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 108L(two): mullw r7, r7, r4 C q = l * inverse 109L(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 114EPILOGUE(mpn_modexact_1c_odd) 115EPILOGUE(mpn_modexact_1_odd) 116ASM_END() 117