1 /* $NetBSD: tune.c,v 1.1.1.2 2014/04/24 12:45:39 pettai Exp $ */
2
3 /* Tune the Karatsuba parameters
4 *
5 * Tom St Denis, tomstdenis@gmail.com
6 */
7 #include <tommath.h>
8 #include <time.h>
9
10 /* how many times todo each size mult. Depends on your computer. For slow computers
11 * this can be low like 5 or 10. For fast [re: Athlon] should be 25 - 50 or so
12 */
13 #define TIMES (1UL<<14UL)
14
15 /* RDTSC from Scott Duplichan */
TIMFUNC(void)16 static ulong64 TIMFUNC (void)
17 {
18 #if defined __GNUC__
19 #if defined(__i386__) || defined(__x86_64__)
20 unsigned long long a;
21 __asm__ __volatile__ ("rdtsc\nmovl %%eax,%0\nmovl %%edx,4+%0\n"::"m"(a):"%eax","%edx");
22 return a;
23 #else /* gcc-IA64 version */
24 unsigned long result;
25 __asm__ __volatile__("mov %0=ar.itc" : "=r"(result) :: "memory");
26 while (__builtin_expect ((int) result == -1, 0))
27 __asm__ __volatile__("mov %0=ar.itc" : "=r"(result) :: "memory");
28 return result;
29 #endif
30
31 // Microsoft and Intel Windows compilers
32 #elif defined _M_IX86
33 __asm rdtsc
34 #elif defined _M_AMD64
35 return __rdtsc ();
36 #elif defined _M_IA64
37 #if defined __INTEL_COMPILER
38 #include <ia64intrin.h>
39 #endif
40 return __getReg (3116);
41 #else
42 #error need rdtsc function for this build
43 #endif
44 }
45
46
47 #ifndef X86_TIMER
48
49 /* generic ISO C timer */
50 ulong64 LBL_T;
t_start(void)51 void t_start(void) { LBL_T = TIMFUNC(); }
t_read(void)52 ulong64 t_read(void) { return TIMFUNC() - LBL_T; }
53
54 #else
55 extern void t_start(void);
56 extern ulong64 t_read(void);
57 #endif
58
time_mult(int size,int s)59 ulong64 time_mult(int size, int s)
60 {
61 unsigned long x;
62 mp_int a, b, c;
63 ulong64 t1;
64
65 mp_init (&a);
66 mp_init (&b);
67 mp_init (&c);
68
69 mp_rand (&a, size);
70 mp_rand (&b, size);
71
72 if (s == 1) {
73 KARATSUBA_MUL_CUTOFF = size;
74 } else {
75 KARATSUBA_MUL_CUTOFF = 100000;
76 }
77
78 t_start();
79 for (x = 0; x < TIMES; x++) {
80 mp_mul(&a,&b,&c);
81 }
82 t1 = t_read();
83 mp_clear (&a);
84 mp_clear (&b);
85 mp_clear (&c);
86 return t1;
87 }
88
time_sqr(int size,int s)89 ulong64 time_sqr(int size, int s)
90 {
91 unsigned long x;
92 mp_int a, b;
93 ulong64 t1;
94
95 mp_init (&a);
96 mp_init (&b);
97
98 mp_rand (&a, size);
99
100 if (s == 1) {
101 KARATSUBA_SQR_CUTOFF = size;
102 } else {
103 KARATSUBA_SQR_CUTOFF = 100000;
104 }
105
106 t_start();
107 for (x = 0; x < TIMES; x++) {
108 mp_sqr(&a,&b);
109 }
110 t1 = t_read();
111 mp_clear (&a);
112 mp_clear (&b);
113 return t1;
114 }
115
116 int
main(void)117 main (void)
118 {
119 ulong64 t1, t2;
120 int x, y;
121
122 for (x = 8; ; x += 2) {
123 t1 = time_mult(x, 0);
124 t2 = time_mult(x, 1);
125 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
126 if (t2 < t1) break;
127 }
128 y = x;
129
130 for (x = 8; ; x += 2) {
131 t1 = time_sqr(x, 0);
132 t2 = time_sqr(x, 1);
133 printf("%d: %9llu %9llu, %9llu\n", x, t1, t2, t2 - t1);
134 if (t2 < t1) break;
135 }
136 printf("KARATSUBA_MUL_CUTOFF = %d\n", y);
137 printf("KARATSUBA_SQR_CUTOFF = %d\n", x);
138
139 return 0;
140 }
141
142 /* Source: /cvs/libtom/libtommath/etc/tune.c,v */
143 /* Revision: 1.3 */
144 /* Date: 2006/03/31 14:18:47 */
145