tool/logest.c

   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++] = (LogEst)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 }