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
logEstMultiply(LogEst a,LogEst b)41 LogEst logEstMultiply(LogEst a, LogEst b){ return a+b; }
logEstAdd(LogEst a,LogEst 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 }
logEstFromInteger(sqlite3_uint64 x)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 }
logEstToInt(LogEst x)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>60 ) return (((sqlite3_uint64)0xffffffff)<<32)+(sqlite3_uint64)0xffffffff;
79 if( x>=3 ) return (n+8)<<(x-3);
80 return (n+8)>>(3-x);
81 }
logEstFromDouble(double x)82 static LogEst logEstFromDouble(double x){
83 sqlite3_uint64 a;
84 LogEst e;
85 assert( sizeof(x)==8 && sizeof(a)==8 );
86 if( x<=0.0 ) return -32768;
87 if( x<0.01 ) return -logEstFromDouble(1.0/x);
88 if( x<1.0 ) return logEstFromDouble(100.0*x) - 66;
89 if( x<1024.0 ) return logEstFromInteger((sqlite3_uint64)(1024.0*x)) - 100;
90 if( x<=2000000000.0 ) return logEstFromInteger((sqlite3_uint64)x);
91 memcpy(&a, &x, 8);
92 e = (a>>52) - 1022;
93 return e*10;
94 }
95
isInteger(const char * z)96 int isInteger(const char *z){
97 while( z[0]>='0' && z[0]<='9' ) z++;
98 return z[0]==0;
99 }
100
isFloat(const char * z)101 int isFloat(const char *z){
102 char c;
103 while( ((c=z[0])>='0' && c<='9') || c=='.' || c=='E' || c=='e'
104 || c=='+' || c=='-' ) z++;
105 return z[0]==0;
106 }
107
showHelp(const char * zArgv0)108 static void showHelp(const char *zArgv0){
109 printf("Usage: %s ARGS...\n", zArgv0);
110 printf("Arguments:\n"
111 " NUM Convert NUM from integer to LogEst and push onto the stack\n"
112 " ^NUM Interpret NUM as a LogEst and push onto stack\n"
113 " x Multiple the top two elements of the stack\n"
114 " + Add the top two elements of the stack\n"
115 " dup Dupliate the top element on the stack\n"
116 " inv Take the reciprocal of the top of stack. N = 1/N.\n"
117 " log Find the LogEst of the number on top of stack\n"
118 " nlogn Compute NlogN where N is the top of stack\n"
119 );
120 exit(1);
121 }
122
main(int argc,char ** argv)123 int main(int argc, char **argv){
124 int i;
125 int n = 0;
126 LogEst a[100];
127 for(i=1; i<argc; i++){
128 const char *z = argv[i];
129 if( strcmp(z,"+")==0 ){
130 if( n>=2 ){
131 a[n-2] = logEstAdd(a[n-2],a[n-1]);
132 n--;
133 }
134 }else if( strcmp(z,"x")==0 ){
135 if( n>=2 ){
136 a[n-2] = logEstMultiply(a[n-2],a[n-1]);
137 n--;
138 }
139 }else if( strcmp(z,"dup")==0 ){
140 if( n>0 ){
141 a[n] = a[n-1];
142 n++;
143 }
144 }else if( strcmp(z,"log")==0 ){
145 if( n>0 ) a[n-1] = logEstFromInteger(a[n-1]) - 33;
146 }else if( strcmp(z,"nlogn")==0 ){
147 if( n>0 ) a[n-1] += logEstFromInteger(a[n-1]) - 33;
148 }else if( strcmp(z,"inv")==0 ){
149 if( n>0 ) a[n-1] = -a[n-1];
150 }else if( z[0]=='^' ){
151 a[n++] = (LogEst)atoi(z+1);
152 }else if( isInteger(z) ){
153 a[n++] = logEstFromInteger(atoll(z));
154 }else if( isFloat(z) && z[0]!='-' ){
155 a[n++] = logEstFromDouble(atof(z));
156 }else{
157 showHelp(argv[0]);
158 }
159 }
160 for(i=n-1; i>=0; i--){
161 if( a[i]<-40 ){
162 printf("%5d (%f)\n", a[i], 1.0/(double)logEstToInt(-a[i]));
163 }else if( a[i]<10 ){
164 printf("%5d (%f)\n", a[i], logEstToInt(a[i]+100)/1024.0);
165 }else if( a[i]>100 ){
166 printf("%5d (%lld)\n", a[i], logEstToInt(a[i]));
167 }else{
168 sqlite3_uint64 x = logEstToInt(a[i]+100)*100/1024;
169 printf("%5d (%lld.%02lld)\n", a[i], x/100, x%100);
170 }
171 }
172 return 0;
173 }
174