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 ** Arguments: 21 ** 22 ** 'x' Multiple the top two elements of the stack 23 ** '+' Add the top two elements of the stack 24 ** NUM Convert NUM from integer to LogEst and push onto the stack 25 ** ^NUM Interpret NUM as a LogEst and push onto stack. 26 ** 27 ** Examples: 28 ** 29 ** To convert 123 from LogEst to integer: 30 ** 31 ** ./LogEst ^123 32 ** 33 ** To convert 123456 from integer to LogEst: 34 ** 35 ** ./LogEst 123456 36 ** 37 */ 38 #include <stdio.h> 39 #include <stdlib.h> 40 #include <ctype.h> 41 #include <assert.h> 42 #include <string.h> 43 #include "sqlite3.h" 44 45 typedef short int LogEst; /* 10 times log2() */ 46 47 LogEst logEstMultiply(LogEst a, LogEst b){ return a+b; } 48 LogEst logEstAdd(LogEst a, LogEst b){ 49 static const unsigned char x[] = { 50 10, 10, /* 0,1 */ 51 9, 9, /* 2,3 */ 52 8, 8, /* 4,5 */ 53 7, 7, 7, /* 6,7,8 */ 54 6, 6, 6, /* 9,10,11 */ 55 5, 5, 5, /* 12-14 */ 56 4, 4, 4, 4, /* 15-18 */ 57 3, 3, 3, 3, 3, 3, /* 19-24 */ 58 2, 2, 2, 2, 2, 2, 2, /* 25-31 */ 59 }; 60 if( a<b ){ LogEst t = a; a = b; b = t; } 61 if( a>b+49 ) return a; 62 if( a>b+31 ) return a+1; 63 return a+x[a-b]; 64 } 65 LogEst logEstFromInteger(sqlite3_uint64 x){ 66 static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 }; 67 LogEst y = 40; 68 if( x<8 ){ 69 if( x<2 ) return 0; 70 while( x<8 ){ y -= 10; x <<= 1; } 71 }else{ 72 while( x>255 ){ y += 40; x >>= 4; } 73 while( x>15 ){ y += 10; x >>= 1; } 74 } 75 return a[x&7] + y - 10; 76 } 77 static sqlite3_uint64 logEstToInt(LogEst x){ 78 sqlite3_uint64 n; 79 if( x<10 ) return 1; 80 n = x%10; 81 x /= 10; 82 if( n>=5 ) n -= 2; 83 else if( n>=1 ) n -= 1; 84 if( x>=3 ) return (n+8)<<(x-3); 85 return (n+8)>>(3-x); 86 } 87 static LogEst logEstFromDouble(double x){ 88 sqlite3_uint64 a; 89 LogEst e; 90 assert( sizeof(x)==8 && sizeof(a)==8 ); 91 if( x<=0.0 ) return -32768; 92 if( x<1.0 ) return -logEstFromDouble(1/x); 93 if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100; 94 if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x); 95 memcpy(&a, &x, 8); 96 e = (a>>52) - 1022; 97 return e*10; 98 } 99 100 int isFloat(const char *z){ 101 while( z[0] ){ 102 if( z[0]=='.' || z[0]=='E' || z[0]=='e' ) return 1; 103 z++; 104 } 105 return 0; 106 } 107 108 int main(int argc, char **argv){ 109 int i; 110 int n = 0; 111 LogEst a[100]; 112 for(i=1; i<argc; i++){ 113 const char *z = argv[i]; 114 if( z[0]=='+' ){ 115 if( n>=2 ){ 116 a[n-2] = logEstAdd(a[n-2],a[n-1]); 117 n--; 118 } 119 }else if( z[0]=='x' ){ 120 if( n>=2 ){ 121 a[n-2] = logEstMultiply(a[n-2],a[n-1]); 122 n--; 123 } 124 }else if( z[0]=='^' ){ 125 a[n++] = atoi(z+1); 126 }else if( isFloat(z) ){ 127 a[n++] = logEstFromDouble(atof(z)); 128 }else{ 129 a[n++] = logEstFromInteger(atoi(z)); 130 } 131 } 132 for(i=n-1; i>=0; i--){ 133 if( a[i]<0 ){ 134 printf("%d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i])); 135 }else{ 136 sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024; 137 printf("%d (%lld.%02lld)\n", a[i], x/100, x%100); 138 } 139 } 140 return 0; 141 } 142