1 /* 2 ** 2013-06-10 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** This file contains a simple command-line utility for converting from 13 ** integers and LogEst values and back again and for doing simple 14 ** arithmetic operations (multiple and add) on LogEst values. 15 ** 16 ** Usage: 17 ** 18 ** ./LogEst ARGS 19 ** 20 ** See the showHelp() routine for a description of valid arguments. 21 ** Examples: 22 ** 23 ** To convert 123 from LogEst to integer: 24 ** 25 ** ./LogEst ^123 26 ** 27 ** To convert 123456 from integer to LogEst: 28 ** 29 ** ./LogEst 123456 30 ** 31 */ 32 #include <stdio.h> 33 #include <stdlib.h> 34 #include <ctype.h> 35 #include <assert.h> 36 #include <string.h> 37 #include "sqlite3.h" 38 39 typedef short int LogEst; /* 10 times log2() */ 40 41 LogEst logEstMultiply(LogEst a, LogEst b){ return a+b; } 42 LogEst logEstAdd(LogEst a, LogEst b){ 43 static const unsigned char x[] = { 44 10, 10, /* 0,1 */ 45 9, 9, /* 2,3 */ 46 8, 8, /* 4,5 */ 47 7, 7, 7, /* 6,7,8 */ 48 6, 6, 6, /* 9,10,11 */ 49 5, 5, 5, /* 12-14 */ 50 4, 4, 4, 4, /* 15-18 */ 51 3, 3, 3, 3, 3, 3, /* 19-24 */ 52 2, 2, 2, 2, 2, 2, 2, /* 25-31 */ 53 }; 54 if( a<b ){ LogEst t = a; a = b; b = t; } 55 if( a>b+49 ) return a; 56 if( a>b+31 ) return a+1; 57 return a+x[a-b]; 58 } 59 LogEst logEstFromInteger(sqlite3_uint64 x){ 60 static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 }; 61 LogEst y = 40; 62 if( x<8 ){ 63 if( x<2 ) return 0; 64 while( x<8 ){ y -= 10; x <<= 1; } 65 }else{ 66 while( x>255 ){ y += 40; x >>= 4; } 67 while( x>15 ){ y += 10; x >>= 1; } 68 } 69 return a[x&7] + y - 10; 70 } 71 static sqlite3_uint64 logEstToInt(LogEst x){ 72 sqlite3_uint64 n; 73 if( x<10 ) return 1; 74 n = x%10; 75 x /= 10; 76 if( n>=5 ) n -= 2; 77 else if( n>=1 ) n -= 1; 78 if( x>=3 ) return (n+8)<<(x-3); 79 return (n+8)>>(3-x); 80 } 81 static LogEst logEstFromDouble(double x){ 82 sqlite3_uint64 a; 83 LogEst e; 84 assert( sizeof(x)==8 && sizeof(a)==8 ); 85 if( x<=0.0 ) return -32768; 86 if( x<0.01 ) return -logEstFromDouble(1.0/x); 87 if( x<1.0 ) return logEstFromDouble(100.0*x) - 66; 88 if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100; 89 if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x); 90 memcpy(&a, &x, 8); 91 e = (a>>52) - 1022; 92 return e*10; 93 } 94 95 int isInteger(const char *z){ 96 while( z[0]>='0' && z[0]<='9' ) z++; 97 return z[0]==0; 98 } 99 100 int isFloat(const char *z){ 101 char c; 102 while( ((c=z[0])>='0' && c<='9') || c=='.' || c=='E' || c=='e' 103 || c=='+' || c=='-' ) z++; 104 return z[0]==0; 105 } 106 107 static void showHelp(const char *zArgv0){ 108 printf("Usage: %s ARGS...\n", zArgv0); 109 printf("Arguments:\n" 110 " NUM Convert NUM from integer to LogEst and push onto the stack\n" 111 " ^NUM Interpret NUM as a LogEst and push onto stack\n" 112 " x Multiple the top two elements of the stack\n" 113 " + Add the top two elements of the stack\n" 114 " dup Dupliate the top element on the stack\n" 115 " inv Take the reciprocal of the top of stack. N = 1/N.\n" 116 " log Find the LogEst of the number on top of stack\n" 117 " nlogn Compute NlogN where N is the top of stack\n" 118 ); 119 exit(1); 120 } 121 122 int main(int argc, char **argv){ 123 int i; 124 int n = 0; 125 LogEst a[100]; 126 for(i=1; i<argc; i++){ 127 const char *z = argv[i]; 128 if( strcmp(z,"+")==0 ){ 129 if( n>=2 ){ 130 a[n-2] = logEstAdd(a[n-2],a[n-1]); 131 n--; 132 } 133 }else if( strcmp(z,"x")==0 ){ 134 if( n>=2 ){ 135 a[n-2] = logEstMultiply(a[n-2],a[n-1]); 136 n--; 137 } 138 }else if( strcmp(z,"dup")==0 ){ 139 if( n>0 ){ 140 a[n] = a[n-1]; 141 n++; 142 } 143 }else if( strcmp(z,"log")==0 ){ 144 if( n>0 ) a[n-1] = logEstFromInteger(a[n-1]) - 33; 145 }else if( strcmp(z,"nlogn")==0 ){ 146 if( n>0 ) a[n-1] += logEstFromInteger(a[n-1]) - 33; 147 }else if( strcmp(z,"inv")==0 ){ 148 if( n>0 ) a[n-1] = -a[n-1]; 149 }else if( z[0]=='^' ){ 150 a[n++] = atoi(z+1); 151 }else if( isInteger(z) ){ 152 a[n++] = logEstFromInteger(atoi(z)); 153 }else if( isFloat(z) && z[0]!='-' ){ 154 a[n++] = logEstFromDouble(atof(z)); 155 }else{ 156 showHelp(argv[0]); 157 } 158 } 159 for(i=n-1; i>=0; i--){ 160 if( a[i]<-40 ){ 161 printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i])); 162 }else if( a[i]<10 ){ 163 printf("%5d (%f)\n", a[i], logEstToInt(a[i]+100)/1024.0); 164 }else{ 165 sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024; 166 printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100); 167 } 168 } 169 return 0; 170 } 171