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