AryaWu/sqlite

1/*2** 2013-06-103**4** The author disclaims copyright to this source code.  In place of5** 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 from13** integers and LogEst values and back again and for doing simple14** arithmetic operations (multiple and add) on LogEst values.15**16** Usage:17**18**      ./LogEst ARGS19**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 ^12326**27** To convert 123456 from integer to LogEst:28**29**         ./LogEst 12345630**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 39typedef short int LogEst;  /* 10 times log2() */40 41LogEst logEstMultiply(LogEst a, LogEst b){ return a+b; }42LogEst 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}59LogEst 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}71static 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}82static 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 96int isInteger(const char *z){97  while( z[0]>='0' && z[0]<='9' ) z++;98  return z[0]==0;99}100 101int 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 108static 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 123int 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