1/* Alternate implementations of binvert_limb to compare speeds. */ 2 3/* 4Copyright 2000, 2002 Free Software Foundation, Inc. 5 6This file is part of the GNU MP Library. 7 8The GNU MP Library is free software; you can redistribute it and/or modify 9it under the terms of either: 10 11 * the GNU Lesser General Public License as published by the Free 12 Software Foundation; either version 3 of the License, or (at your 13 option) any later version. 14 15or 16 17 * the GNU General Public License as published by the Free Software 18 Foundation; either version 2 of the License, or (at your option) any 19 later version. 20 21or both in parallel, as here. 22 23The GNU MP Library is distributed in the hope that it will be useful, but 24WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 25or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 26for more details. 27 28You should have received copies of the GNU General Public License and the 29GNU Lesser General Public License along with the GNU MP Library. If not, 30see https://www.gnu.org/licenses/. */ 31 32#include <stdio.h> 33#include "gmp-impl.h" 34#include "longlong.h" 35#include "speed.h" 36 37 38/* Like the standard version in gmp-impl.h, but with the expressions using a 39 "1-" form. This has the same number of steps, but "1-" is on the 40 dependent chain, whereas the "2*" in the standard version isn't. 41 Depending on the CPU this should be the same or a touch slower. */ 42 43#if GMP_LIMB_BITS <= 32 44#define binvert_limb_mul1(inv,n) \ 45 do { \ 46 mp_limb_t __n = (n); \ 47 mp_limb_t __inv; \ 48 ASSERT ((__n & 1) == 1); \ 49 __inv = binvert_limb_table[(__n&0xFF)/2]; /* 8 */ \ 50 __inv = (1 - __n * __inv) * __inv + __inv; /* 16 */ \ 51 __inv = (1 - __n * __inv) * __inv + __inv; /* 32 */ \ 52 ASSERT (__inv * __n == 1); \ 53 (inv) = __inv; \ 54 } while (0) 55#endif 56 57#if GMP_LIMB_BITS > 32 && GMP_LIMB_BITS <= 64 58#define binvert_limb_mul1(inv,n) \ 59 do { \ 60 mp_limb_t __n = (n); \ 61 mp_limb_t __inv; \ 62 ASSERT ((__n & 1) == 1); \ 63 __inv = binvert_limb_table[(__n&0xFF)/2]; /* 8 */ \ 64 __inv = (1 - __n * __inv) * __inv + __inv; /* 16 */ \ 65 __inv = (1 - __n * __inv) * __inv + __inv; /* 32 */ \ 66 __inv = (1 - __n * __inv) * __inv + __inv; /* 64 */ \ 67 ASSERT (__inv * __n == 1); \ 68 (inv) = __inv; \ 69 } while (0) 70#endif 71 72 73/* The loop based version used in GMP 3.0 and earlier. Usually slower than 74 multiplying, due to the number of steps that must be performed. Much 75 slower when the processor has a good multiply. */ 76 77#define binvert_limb_loop(inv,n) \ 78 do { \ 79 mp_limb_t __v = (n); \ 80 mp_limb_t __v_orig = __v; \ 81 mp_limb_t __make_zero = 1; \ 82 mp_limb_t __two_i = 1; \ 83 mp_limb_t __v_inv = 0; \ 84 \ 85 ASSERT ((__v & 1) == 1); \ 86 \ 87 do \ 88 { \ 89 while ((__two_i & __make_zero) == 0) \ 90 __two_i <<= 1, __v <<= 1; \ 91 __v_inv += __two_i; \ 92 __make_zero -= __v; \ 93 } \ 94 while (__make_zero); \ 95 \ 96 ASSERT (__v_orig * __v_inv == 1); \ 97 (inv) = __v_inv; \ 98 } while (0) 99 100 101/* Another loop based version with conditionals, but doing a fixed number of 102 steps. */ 103 104#define binvert_limb_cond(inv,n) \ 105 do { \ 106 mp_limb_t __n = (n); \ 107 mp_limb_t __rem = (1 - __n) >> 1; \ 108 mp_limb_t __inv = GMP_LIMB_HIGHBIT; \ 109 int __count; \ 110 \ 111 ASSERT ((__n & 1) == 1); \ 112 \ 113 __count = GMP_LIMB_BITS-1; \ 114 do \ 115 { \ 116 __inv >>= 1; \ 117 if (__rem & 1) \ 118 { \ 119 __inv |= GMP_LIMB_HIGHBIT; \ 120 __rem -= __n; \ 121 } \ 122 __rem >>= 1; \ 123 } \ 124 while (-- __count); \ 125 \ 126 ASSERT (__inv * __n == 1); \ 127 (inv) = __inv; \ 128 } while (0) 129 130 131/* Another loop based bitwise version, but purely arithmetic, no 132 conditionals. */ 133 134#define binvert_limb_arith(inv,n) \ 135 do { \ 136 mp_limb_t __n = (n); \ 137 mp_limb_t __rem = (1 - __n) >> 1; \ 138 mp_limb_t __inv = GMP_LIMB_HIGHBIT; \ 139 mp_limb_t __lowbit; \ 140 int __count; \ 141 \ 142 ASSERT ((__n & 1) == 1); \ 143 \ 144 __count = GMP_LIMB_BITS-1; \ 145 do \ 146 { \ 147 __lowbit = __rem & 1; \ 148 __inv = (__inv >> 1) | (__lowbit << (GMP_LIMB_BITS-1)); \ 149 __rem = (__rem - (__n & -__lowbit)) >> 1; \ 150 } \ 151 while (-- __count); \ 152 \ 153 ASSERT (__inv * __n == 1); \ 154 (inv) = __inv; \ 155 } while (0) 156 157 158double 159speed_binvert_limb_mul1 (struct speed_params *s) 160{ 161 SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_mul1); 162} 163double 164speed_binvert_limb_loop (struct speed_params *s) 165{ 166 SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_loop); 167} 168double 169speed_binvert_limb_cond (struct speed_params *s) 170{ 171 SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_cond); 172} 173double 174speed_binvert_limb_arith (struct speed_params *s) 175{ 176 SPEED_ROUTINE_MODLIMB_INVERT (binvert_limb_arith); 177} 178