annotate etc/tune.c @ 282:91fbc376f010 libtommath-orig libtommath-0.35

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