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