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