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 ) return (((sqlite3_uint64)0xffffffff)<<32)+(sqlite3_uint64)0xffffffff;
  79   if( x>=3 ) return (n+8)<<(x-3);
  80   return (n+8)>>(3-x);
  81 }
  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
  96 int isInteger(const char *z){
  97   while( z[0]>='0' && z[0]<='9' ) z++;
  98   return z[0]==0;
  99 }
 100
 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
 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
 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 }