sqlitejdbc/ext/extension-functions.c

   1 /*
   2 This library will provide common mathematical and string functions in
   3 SQL queries using the operating system libraries or provided
   4 definitions.  It includes the following functions:
   5
   6 Math: acos, asin, atan, atn2, atan2, acosh, asinh, atanh, difference,
   7 degrees, radians, cos, sin, tan, cot, cosh, sinh, tanh, coth, exp,
   8 log, log10, power, sign, sqrt, square, ceil, floor, pi.
   9
  10 String: replicate, charindex, leftstr, rightstr, ltrim, rtrim, trim,
  11 replace, reverse, proper, padl, padr, padc, strfilter.
  12
  13 Aggregate: stdev, variance, mode, median, lower_quartile,
  14 upper_quartile.
  15
  16 The string functions ltrim, rtrim, trim, replace are included in
  17 recent versions of SQLite and so by default do not build.
  18
  19 Compilation instructions:
  20  Compile this C source file into a dynamic library as follows:
  21  Linux:
  22    gcc -fPIC -lm -shared extension-functions.c -o libsqlitefunctions.so
  23  Mac OS X:
  24    gcc -fno-common -dynamiclib extension-functions.c -o libsqlitefunctions.dylib
  25  (You may need to add flags
  26   -I /opt/local/include/ -L/opt/local/lib -lsqlite3
  27   if your sqlite3 is installed from Mac ports, or
  28   -I /sw/include/ -L/sw/lib -lsqlite3
  29   if installed with Fink.)
  30
  31 Usage instructions for applications calling the sqlite3 API functions:
  32   In your application, call sqlite3_enable_load_extension(db,1) to
  33   allow loading external libraries.  Then load the library libsqlitefunctions
  34   using sqlite3_load_extension; the third argument should be 0.
  35   See http://www.sqlite.org/cvstrac/wiki?p=LoadableExtensions.
  36   Select statements may now use these functions, as in
  37   SELECT cos(radians(inclination)) FROM satsum WHERE satnum = 25544;
  38
  39 Usage instructions for the sqlite3 program:
  40   If the program is built so that loading extensions is permitted,
  41   the following will work:
  42    sqlite> SELECT load_extension('./libsqlitefunctions.so');
  43    sqlite> select cos(radians(45));
  44    0.707106781186548
  45   Note: Loading extensions is by default prohibited as a
  46   security measure; see "Security Considerations" in
  47   http://www.sqlite.org/cvstrac/wiki?p=LoadableExtensions.
  48   If the sqlite3 program and library are built this
  49   way, you cannot use these functions from the program, you
  50   must write your own program using the sqlite3 API, and call
  51   sqlite3_enable_load_extension as described above, or else
  52   rebuilt the sqlite3 program to allow loadable extensions.
  53
  54 Alterations:
  55 The instructions are for Linux or Mac OS X; users of other OSes may
  56 need to modify this procedure.  In particular, if your math library
  57 lacks one or more of the needed trig or log functions, comment out the
  58 appropriate HAVE_ #define at the top of file.  If you do not
  59 wish to make a loadable module, comment out the define for
  60 COMPILE_SQLITE_EXTENSIONS_AS_LOADABLE_MODULE.  If you are using a
  61 version of SQLite without the trim functions and replace, comment out
  62 the HAVE_TRIM #define.
  63
  64 Liam Healy
  65
  66 History:
  67 2009-06-24 Correct check for argc in properFunc
  68 2008-09-14 Add check that memory was actually allocated after
  69 sqlite3_malloc or sqlite3StrDup, call sqlite3_result_error_nomem if
  70 not.  Thanks to Robert Simpson.
  71 2008-06-13 Change to instructions to indicate use of the math library
  72 and that program might work.
  73 2007-10-01 Minor clarification to instructions.
  74 2007-09-29 Compilation as loadable module is optional with
  75 COMPILE_SQLITE_EXTENSIONS_AS_LOADABLE_MODULE.
  76 2007-09-28 Use sqlite3_extension_init and macros
  77 SQLITE_EXTENSION_INIT1, SQLITE_EXTENSION_INIT2, so that it works with
  78 sqlite3_load_extension.  Thanks to Eric Higashino and Joe Wilson.
  79 New instructions for Mac compilation.
  80 2007-09-17 With help from Joe Wilson and Nuno Luca, made use of
  81 external interfaces so that compilation is no longer dependent on
  82 SQLite source code.  Merged source, header, and README into a single
  83 file.  Added casts so that Mac will compile without warnings (unsigned
  84 and signed char).
  85 2007-09-05 Included some definitions from sqlite 3.3.13 so that this
  86 will continue to work in newer versions of sqlite.  Completed
  87 description of functions available.
  88 2007-03-27 Revised description.
  89 2007-03-23 Small cleanup and a bug fix on the code.  This was mainly
  90 letting errno flag errors encountered in the math library and checking
  91 the result, rather than pre-checking.  This fixes a bug in power that
  92 would cause an error if any non-positive number was raised to any
  93 power.
  94 2007-02-07 posted by Mikey C to sqlite mailing list.
  95 Original code 2006 June 05 by relicoder.
  96
  97 */
  98
  99 //#include "config.h"
 100
 101 //#define COMPILE_SQLITE_EXTENSIONS_AS_LOADABLE_MODULE 1
 102 #define HAVE_ACOSH 1
 103 #define HAVE_ASINH 1
 104 #define HAVE_ATANH 1
 105 #define HAVE_SINH 1
 106 #define HAVE_COSH 1
 107 #define HAVE_TANH 1
 108 #define HAVE_LOG10 1
 109 #define HAVE_ISBLANK 1
 110 #define SQLITE_SOUNDEX 1
 111 #define HAVE_TRIM 1             /* LMH 2007-03-25 if sqlite has trim functions */
 112
 113 #ifdef COMPILE_SQLITE_EXTENSIONS_AS_LOADABLE_MODULE
 114 #include "sqlite3ext.h"
 115 SQLITE_EXTENSION_INIT1
 116 #else
 117 #include "sqlite3.h"
 118 #endif
 119
 120 #include <ctype.h>
 121 /* relicoder */
 122 #include <math.h>
 123 #include <string.h>
 124 #include <stdio.h>
 125 #include <errno.h>              /* LMH 2007-03-25 */
 126
 127 #include <stdlib.h>
 128 #include <assert.h>
 129
 130 #ifndef _MAP_H_
 131 #define _MAP_H_
 132
 133 //#include <stdint.h>
 134
 135 /*
 136 ** Simple binary tree implementation to use in median, mode and quartile calculations
 137 ** Tree is not necessarily balanced. That would require something like red&black trees of AVL
 138 */
 139
 140 typedef int(*cmp_func)(const void *, const void *);
 141 typedef void(*map_iterator)(void*, sqlite_int64, void*);
 142
 143 typedef struct node{
 144   struct node *l;
 145   struct node *r;
 146   void* data;
 147   sqlite_int64 count;
 148 } node;
 149
 150 typedef struct map{
 151   node *base;
 152   cmp_func cmp;
 153   short free;
 154 } map;
 155
 156 /*
 157 ** creates a map given a comparison function
 158 */
 159 map map_make(cmp_func cmp);
 160
 161 /*
 162 ** inserts the element e into map m
 163 */
 164 void map_insert(map *m, void *e);
 165
 166 /*
 167 ** executes function iter over all elements in the map, in key increasing order
 168 */
 169 void map_iterate(map *m, map_iterator iter, void* p);
 170
 171 /*
 172 ** frees all memory used by a map
 173 */
 174 void map_destroy(map *m);
 175
 176 /*
 177 ** compares 2 integers
 178 ** to use with map_make
 179 */
 180 int int_cmp(const void *a, const void *b);
 181
 182 /*
 183 ** compares 2 doubles
 184 ** to use with map_make
 185 */
 186 int double_cmp(const void *a, const void *b);
 187
 188 #endif /* _MAP_H_ */
 189
 190
 191 static char *sqlite3StrDup( const char *z ) {
 192     char *res = sqlite3_malloc( strlen(z)+1 );
 193     return strcpy( res, z );
 194 }
 195
 196 /*
 197 ** These are copied verbatim from fun.c so as to not have the names exported
 198 */
 199
 200 /* LMH from sqlite3 3.3.13 */
 201 /*
 202 ** This table maps from the first byte of a UTF-8 character to the number
 203 ** of trailing bytes expected. A value '4' indicates that the table key
 204 ** is not a legal first byte for a UTF-8 character.
 205 */
 206 static const u8 xtra_utf8_bytes[256]  = {
 207 /* 0xxxxxxx */
 208 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 209 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 210 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 211 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 212 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 213 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 214 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 215 0, 0, 0, 0, 0, 0, 0, 0,     0, 0, 0, 0, 0, 0, 0, 0,
 216
 217 /* 10wwwwww */
 218 4, 4, 4, 4, 4, 4, 4, 4,     4, 4, 4, 4, 4, 4, 4, 4,
 219 4, 4, 4, 4, 4, 4, 4, 4,     4, 4, 4, 4, 4, 4, 4, 4,
 220 4, 4, 4, 4, 4, 4, 4, 4,     4, 4, 4, 4, 4, 4, 4, 4,
 221 4, 4, 4, 4, 4, 4, 4, 4,     4, 4, 4, 4, 4, 4, 4, 4,
 222
 223 /* 110yyyyy */
 224 1, 1, 1, 1, 1, 1, 1, 1,     1, 1, 1, 1, 1, 1, 1, 1,
 225 1, 1, 1, 1, 1, 1, 1, 1,     1, 1, 1, 1, 1, 1, 1, 1,
 226
 227 /* 1110zzzz */
 228 2, 2, 2, 2, 2, 2, 2, 2,     2, 2, 2, 2, 2, 2, 2, 2,
 229
 230 /* 11110yyy */
 231 3, 3, 3, 3, 3, 3, 3, 3,     4, 4, 4, 4, 4, 4, 4, 4,
 232 };
 233
 234
 235 /*
 236 ** This table maps from the number of trailing bytes in a UTF-8 character
 237 ** to an integer constant that is effectively calculated for each character
 238 ** read by a naive implementation of a UTF-8 character reader. The code
 239 ** in the READ_UTF8 macro explains things best.
 240 */
 241 static const int xtra_utf8_bits[] =  {
 242   0,
 243   12416,          /* (0xC0 << 6) + (0x80) */
 244   925824,         /* (0xE0 << 12) + (0x80 << 6) + (0x80) */
 245   63447168        /* (0xF0 << 18) + (0x80 << 12) + (0x80 << 6) + 0x80 */
 246 };
 247
 248 /*
 249 ** If a UTF-8 character contains N bytes extra bytes (N bytes follow
 250 ** the initial byte so that the total character length is N+1) then
 251 ** masking the character with utf8_mask[N] must produce a non-zero
 252 ** result.  Otherwise, we have an (illegal) overlong encoding.
 253 */
 254 static const int utf_mask[] = {
 255   0x00000000,
 256   0xffffff80,
 257   0xfffff800,
 258   0xffff0000,
 259 };
 260
 261 #define EXT_READ_UTF8(zIn, c) { \
 262   int xtra;                                            \
 263   c = *(zIn)++;                                        \
 264   xtra = xtra_utf8_bytes[c];                           \
 265   switch( xtra ){                                      \
 266     case 4: c = (int)0xFFFD; break;                    \
 267     case 3: c = (c<<6) + *(zIn)++;                     \
 268     case 2: c = (c<<6) + *(zIn)++;                     \
 269     case 1: c = (c<<6) + *(zIn)++;                     \
 270     c -= xtra_utf8_bits[xtra];                         \
 271     if( (utf_mask[xtra]&c)==0                          \
 272         || (c&0xFFFFF800)==0xD800                      \
 273         || (c&0xFFFFFFFE)==0xFFFE ){  c = 0xFFFD; }    \
 274   }                                                    \
 275 }
 276
 277 static int sqlite3ReadUtf8(const unsigned char *z){
 278   int c;
 279   EXT_READ_UTF8(z, c);
 280   return c;
 281 }
 282
 283 #define SKIP_UTF8(zIn) {                               \
 284   zIn += (xtra_utf8_bytes[*(u8 *)zIn] + 1);            \
 285 }
 286
 287
 288
 289 /*
 290 ** X is a pointer to the first byte of a UTF-8 character.  Increment
 291 ** X so that it points to the next character.  This only works right
 292 ** if X points to a well-formed UTF-8 string.
 293 */
 294 #define sqliteNextChar(X)  while( (0xc0&*++(X))==0x80 ){}
 295 #define sqliteCharVal(X)   sqlite3ReadUtf8(X)
 296
 297 /*
 298 ** This is a macro that facilitates writting wrappers for math.h functions
 299 ** it creates code for a function to use in SQlite that gets one numeric input
 300 ** and returns a floating point value.
 301 **
 302 ** Could have been implemented using pointers to functions but this way it's inline
 303 ** and thus more efficient. Lower * ranking though...
 304 **
 305 ** Parameters:
 306 ** name:      function name to de defined (eg: sinFunc)
 307 ** function:  function defined in math.h to wrap (eg: sin)
 308 ** domain:    boolean condition that CAN'T happen in terms of the input parameter rVal
 309 **            (eg: rval<0 for sqrt)
 310 */
 311 /* LMH 2007-03-25 Changed to use errno and remove domain; no pre-checking for errors. */
 312 #define GEN_MATH_WRAP_DOUBLE_1(name, function) \
 313 static void name(sqlite3_context *context, int argc, sqlite3_value **argv){\
 314   double rVal = 0.0, val;\
 315   assert( argc==1 );\
 316   switch( sqlite3_value_type(argv[0]) ){\
 317     case SQLITE_NULL: {\
 318       sqlite3_result_null(context);\
 319       break;\
 320     }\
 321     default: {\
 322       rVal = sqlite3_value_double(argv[0]);\
 323       errno = 0;\
 324       val = function(rVal);\
 325       if (errno == 0) {\
 326         sqlite3_result_double(context, val);\
 327       } else {\
 328         sqlite3_result_error(context, strerror(errno), errno);\
 329       }\
 330       break;\
 331     }\
 332   }\
 333 }\
 334
 335
 336 /*
 337 ** Example of GEN_MATH_WRAP_DOUBLE_1 usage
 338 ** this creates function sqrtFunc to wrap the math.h standard function sqrt(x)=x^0.5
 339 */
 340 GEN_MATH_WRAP_DOUBLE_1(sqrtFunc, sqrt)
 341
 342 /* trignometric functions */
 343 GEN_MATH_WRAP_DOUBLE_1(acosFunc, acos)
 344 GEN_MATH_WRAP_DOUBLE_1(asinFunc, asin)
 345 GEN_MATH_WRAP_DOUBLE_1(atanFunc, atan)
 346
 347 /*
 348 ** Many of systems don't have inverse hyperbolic trig functions so this will emulate
 349 ** them on those systems in terms of log and sqrt (formulas are too trivial to demand
 350 ** written proof here)
 351 */
 352
 353 #ifndef HAVE_ACOSH
 354 static double acosh(double x){
 355   return log(x + sqrt(x*x - 1.0));
 356 }
 357 #endif
 358
 359 GEN_MATH_WRAP_DOUBLE_1(acoshFunc, acosh)
 360
 361 #ifndef HAVE_ASINH
 362 static double asinh(double x){
 363   return log(x + sqrt(x*x + 1.0));
 364 }
 365 #endif
 366
 367 GEN_MATH_WRAP_DOUBLE_1(asinhFunc, asinh)
 368
 369 #ifndef HAVE_ATANH
 370 static double atanh(double x){
 371   return (1.0/2.0)*log((1+x)/(1-x)) ;
 372 }
 373 #endif
 374
 375 GEN_MATH_WRAP_DOUBLE_1(atanhFunc, atanh)
 376
 377 /*
 378 ** math.h doesn't require cot (cotangent) so it's defined here
 379 */
 380 static double cot(double x){
 381   return 1.0/tan(x);
 382 }
 383
 384 GEN_MATH_WRAP_DOUBLE_1(sinFunc, sin)
 385 GEN_MATH_WRAP_DOUBLE_1(cosFunc, cos)
 386 GEN_MATH_WRAP_DOUBLE_1(tanFunc, tan)
 387 GEN_MATH_WRAP_DOUBLE_1(cotFunc, cot)
 388
 389 static double coth(double x){
 390   return 1.0/tanh(x);
 391 }
 392
 393 /*
 394 ** Many systems don't have hyperbolic trigonometric functions so this will emulate
 395 ** them on those systems directly from the definition in terms of exp
 396 */
 397 #ifndef HAVE_SINH
 398 static double sinh(double x){
 399   return (exp(x)-exp(-x))/2.0;
 400 }
 401 #endif
 402
 403 GEN_MATH_WRAP_DOUBLE_1(sinhFunc, sinh)
 404
 405 #ifndef HAVE_COSH
 406 static double cosh(double x){
 407   return (exp(x)+exp(-x))/2.0;
 408 }
 409 #endif
 410
 411 GEN_MATH_WRAP_DOUBLE_1(coshFunc, cosh)
 412
 413 #ifndef HAVE_TANH
 414 static double tanh(double x){
 415   return sinh(x)/cosh(x);
 416 }
 417 #endif
 418
 419 GEN_MATH_WRAP_DOUBLE_1(tanhFunc, tanh)
 420
 421 GEN_MATH_WRAP_DOUBLE_1(cothFunc, coth)
 422
 423 /*
 424 ** Some systems lack log in base 10. This will emulate it
 425 */
 426
 427 #ifndef HAVE_LOG10
 428 static double log10(double x){
 429   static double l10 = -1.0;
 430   if( l10<0.0 ){
 431     l10 = log(10.0);
 432   }
 433   return log(x)/l10;
 434 }
 435 #endif
 436
 437 GEN_MATH_WRAP_DOUBLE_1(logFunc, log)
 438 GEN_MATH_WRAP_DOUBLE_1(log10Func, log10)
 439 GEN_MATH_WRAP_DOUBLE_1(expFunc, exp)
 440
 441 /*
 442 ** Fallback for systems where math.h doesn't define M_PI
 443 */
 444 #undef M_PI
 445 #ifndef M_PI
 446 /*
 447 ** static double PI = acos(-1.0);
 448 ** #define M_PI (PI)
 449 */
 450 #define M_PI 3.14159265358979323846
 451 #endif
 452
 453 /* Convert Degrees into Radians */
 454 static double deg2rad(double x){
 455   return x*M_PI/180.0;
 456 }
 457
 458 /* Convert Radians into Degrees */
 459 static double rad2deg(double x){
 460   return 180.0*x/M_PI;
 461 }
 462
 463 GEN_MATH_WRAP_DOUBLE_1(rad2degFunc, rad2deg)
 464 GEN_MATH_WRAP_DOUBLE_1(deg2radFunc, deg2rad)
 465
 466 /* constant function that returns the value of PI=3.1415... */
 467 static void piFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 468   sqlite3_result_double(context, M_PI);
 469 }
 470
 471 /*
 472 ** Implements the sqrt function, it has the peculiarity of returning an integer when the
 473 ** the argument is an integer.
 474 ** Since SQLite isn't strongly typed (almost untyped actually) this is a bit pedantic
 475 */
 476 static void squareFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 477   i64 iVal = 0;
 478   double rVal = 0.0;
 479   assert( argc==2 );
 480   switch( sqlite3_value_type(argv[0]) ){
 481     case SQLITE_INTEGER: {
 482       iVal = sqlite3_value_int64(argv[0]);
 483       sqlite3_result_int64(context, iVal*iVal);
 484       break;
 485     }
 486     case SQLITE_NULL: {
 487       sqlite3_result_null(context);
 488       break;
 489     }
 490     default: {
 491       rVal = sqlite3_value_double(argv[0]);
 492       sqlite3_result_double(context, rVal*rVal);
 493       break;
 494     }
 495   }
 496 }
 497
 498 /*
 499 ** Wraps the pow math.h function
 500 ** When both the base and the exponent are integers the result should be integer
 501 ** (see sqrt just before this). Here the result is always double
 502 */
 503 /* LMH 2007-03-25 Changed to use errno; no pre-checking for errors.  Also removes
 504   but that was present in the pre-checking that called sqlite3_result_error on
 505   a non-positive first argument, which is not always an error. */
 506 static void powerFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 507   double r1 = 0.0;
 508   double r2 = 0.0;
 509   double val;
 510
 511   assert( argc==2 );
 512
 513   if( sqlite3_value_type(argv[0]) == SQLITE_NULL || sqlite3_value_type(argv[1]) == SQLITE_NULL ){
 514     sqlite3_result_null(context);
 515   }else{
 516     r1 = sqlite3_value_double(argv[0]);
 517     r2 = sqlite3_value_double(argv[1]);
 518     errno = 0;
 519     val = pow(r1,r2);
 520     if (errno == 0) {
 521       sqlite3_result_double(context, val);
 522     } else {
 523       sqlite3_result_error(context, strerror(errno), errno);
 524     }
 525   }
 526 }
 527
 528 /*
 529 ** atan2 wrapper
 530 */
 531 static void atn2Func(sqlite3_context *context, int argc, sqlite3_value **argv){
 532   double r1 = 0.0;
 533   double r2 = 0.0;
 534
 535   assert( argc==2 );
 536
 537   if( sqlite3_value_type(argv[0]) == SQLITE_NULL || sqlite3_value_type(argv[1]) == SQLITE_NULL ){
 538     sqlite3_result_null(context);
 539   }else{
 540     r1 = sqlite3_value_double(argv[0]);
 541     r2 = sqlite3_value_double(argv[1]);
 542     sqlite3_result_double(context, atan2(r1,r2));
 543   }
 544 }
 545
 546 /*
 547 ** Implementation of the sign() function
 548 ** return one of 3 possibilities +1,0 or -1 when the argument is respectively
 549 ** positive, 0 or negative.
 550 ** When the argument is NULL the result is also NULL (completly conventional)
 551 */
 552 static void signFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 553   double rVal=0.0;
 554   i64 iVal=0;
 555   assert( argc==1 );
 556   switch( sqlite3_value_type(argv[0]) ){
 557     case SQLITE_INTEGER: {
 558       iVal = sqlite3_value_int64(argv[0]);
 559       iVal = ( iVal > 0) ? 1: ( iVal < 0 ) ? -1: 0;
 560       sqlite3_result_int64(context, iVal);
 561       break;
 562     }
 563     case SQLITE_NULL: {
 564       sqlite3_result_null(context);
 565       break;
 566     }
 567     default: {
 568  /* 2nd change below. Line for abs was: if( rVal<0 ) rVal = rVal * -1.0;  */
 569
 570       rVal = sqlite3_value_double(argv[0]);
 571       rVal = ( rVal > 0) ? 1: ( rVal < 0 ) ? -1: 0;
 572       sqlite3_result_double(context, rVal);
 573       break;
 574     }
 575   }
 576 }
 577
 578
 579 /*
 580 ** smallest integer value not less than argument
 581 */
 582 static void ceilFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 583   double rVal=0.0;
 584   i64 iVal=0;
 585   assert( argc==1 );
 586   switch( sqlite3_value_type(argv[0]) ){
 587     case SQLITE_INTEGER: {
 588       i64 iVal = sqlite3_value_int64(argv[0]);
 589       sqlite3_result_int64(context, iVal);
 590       break;
 591     }
 592     case SQLITE_NULL: {
 593       sqlite3_result_null(context);
 594       break;
 595     }
 596     default: {
 597       rVal = sqlite3_value_double(argv[0]);
 598       sqlite3_result_int64(context, (i64) ceil(rVal));
 599       break;
 600     }
 601   }
 602 }
 603
 604 /*
 605 ** largest integer value not greater than argument
 606 */
 607 static void floorFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 608   double rVal=0.0;
 609   i64 iVal=0;
 610   assert( argc==1 );
 611   switch( sqlite3_value_type(argv[0]) ){
 612     case SQLITE_INTEGER: {
 613       i64 iVal = sqlite3_value_int64(argv[0]);
 614       sqlite3_result_int64(context, iVal);
 615       break;
 616     }
 617     case SQLITE_NULL: {
 618       sqlite3_result_null(context);
 619       break;
 620     }
 621     default: {
 622       rVal = sqlite3_value_double(argv[0]);
 623       sqlite3_result_int64(context, (i64) floor(rVal));
 624       break;
 625     }
 626   }
 627 }
 628
 629 /*
 630 ** Given a string (s) in the first argument and an integer (n) in the second returns the
 631 ** string that constains s contatenated n times
 632 */
 633 static void replicateFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 634   unsigned char *z;        /* input string */
 635   unsigned char *zo;       /* result string */
 636   i64 iCount;              /* times to repeat */
 637   i64 nLen;                /* length of the input string (no multibyte considerations) */
 638   i64 nTLen;               /* length of the result string (no multibyte considerations) */
 639   i64 i=0;
 640
 641   if( argc!=2 || SQLITE_NULL==sqlite3_value_type(argv[0]) )
 642     return;
 643
 644   iCount = sqlite3_value_int64(argv[1]);
 645
 646   if( iCount<0 ){
 647     sqlite3_result_error(context, "domain error", -1);
 648   }else{
 649
 650     nLen  = sqlite3_value_bytes(argv[0]);
 651     nTLen = nLen*iCount;
 652     z=sqlite3_malloc(nTLen+1);
 653     zo=sqlite3_malloc(nLen+1);
 654     if (!z || !zo){
 655       sqlite3_result_error_nomem(context);
 656       if (z) sqlite3_free(z);
 657       if (zo) sqlite3_free(zo);
 658       return;
 659     }
 660     strcpy((char*)zo, (char*)sqlite3_value_text(argv[0]));
 661
 662     for(i=0; i<iCount; ++i){
 663       strcpy((char*)(z+i*nLen), (char*)zo);
 664     }
 665
 666     sqlite3_result_text(context, (char*)z, -1, SQLITE_TRANSIENT);
 667     sqlite3_free(z);
 668     sqlite3_free(zo);
 669   }
 670 }
 671
 672 /*
 673 ** Some systems (win32 among others) don't have an isblank function, this will emulate it.
 674 ** This function is not UFT-8 safe since it only analyses a byte character.
 675 */
 676 #ifndef HAVE_ISBLANK
 677 int isblank(char c){
 678   return( ' '==c || '\t'==c );
 679 }
 680 #endif
 681
 682 static void properFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 683   const unsigned char *z;     /* input string */
 684   unsigned char *zo;          /* output string */
 685   unsigned char *zt;          /* iterator */
 686   char r;
 687   int c=1;
 688
 689   assert( argc==1);
 690   if( SQLITE_NULL==sqlite3_value_type(argv[0]) ){
 691     sqlite3_result_null(context);
 692     return;
 693   }
 694
 695   z = sqlite3_value_text(argv[0]);
 696   zo = (unsigned char *)sqlite3StrDup((char *) z);
 697   if (!zo) {
 698     sqlite3_result_error_nomem(context);
 699     return;
 700   }
 701   zt = zo;
 702
 703   while( (r = *(z++))!=0 ){
 704     if( isblank(r) ){
 705       c=1;
 706     }else{
 707       if( c==1 ){
 708         r = toupper(r);
 709       }else{
 710         r = tolower(r);
 711       }
 712       c=0;
 713     }
 714     *(zt++) = r;
 715   }
 716   *zt = '\0';
 717
 718   sqlite3_result_text(context, (char*)zo, -1, SQLITE_TRANSIENT);
 719   sqlite3_free(zo);
 720 }
 721
 722 /*
 723 ** given an input string (s) and an integer (n) adds spaces at the begining of  s
 724 ** until it has a length of n characters.
 725 ** When s has a length >=n it's a NOP
 726 ** padl(NULL) = NULL
 727 */
 728 static void padlFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 729   i64 ilen;          /* length to pad to */
 730   i64 zl;            /* length of the input string (UTF-8 chars) */
 731   int i = 0;
 732   const char *zi;    /* input string */
 733   char *zo;          /* output string */
 734   char *zt;
 735
 736   assert( argc==2 );
 737
 738   if( sqlite3_value_type(argv[0]) == SQLITE_NULL ){
 739     sqlite3_result_null(context);
 740   }else{
 741     zi = (char *)sqlite3_value_text(argv[0]);
 742     ilen = sqlite3_value_int64(argv[1]);
 743     /* check domain */
 744     if(ilen<0){
 745       sqlite3_result_error(context, "domain error", -1);
 746       return;
 747     }
 748     zl = sqlite3Utf8CharLen(zi, -1);
 749     if( zl>=ilen ){
 750       /* string is longer than the requested pad length, return the same string (dup it) */
 751       zo = sqlite3StrDup(zi);
 752       if (!zo){
 753         sqlite3_result_error_nomem(context);
 754         return;
 755       }
 756       sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 757     }else{
 758       zo = sqlite3_malloc(strlen(zi)+ilen-zl+1);
 759       if (!zo){
 760         sqlite3_result_error_nomem(context);
 761         return;
 762       }
 763       zt = zo;
 764       for(i=1; i+zl<=ilen; ++i){
 765         *(zt++)=' ';
 766       }
 767       /* no need to take UTF-8 into consideration here */
 768       strcpy(zt,zi);
 769     }
 770     sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 771     sqlite3_free(zo);
 772   }
 773 }
 774
 775 /*
 776 ** given an input string (s) and an integer (n) appends spaces at the end of  s
 777 ** until it has a length of n characters.
 778 ** When s has a length >=n it's a NOP
 779 ** padl(NULL) = NULL
 780 */
 781 static void padrFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 782   i64 ilen;          /* length to pad to */
 783   i64 zl;            /* length of the input string (UTF-8 chars) */
 784   i64 zll;           /* length of the input string (bytes) */
 785   int i = 0;
 786   const char *zi;    /* input string */
 787   char *zo;          /* output string */
 788   char *zt;
 789
 790   assert( argc==2 );
 791
 792   if( sqlite3_value_type(argv[0]) == SQLITE_NULL ){
 793     sqlite3_result_null(context);
 794   }else{
 795     zi = (char *)sqlite3_value_text(argv[0]);
 796     ilen = sqlite3_value_int64(argv[1]);
 797     /* check domain */
 798     if(ilen<0){
 799       sqlite3_result_error(context, "domain error", -1);
 800       return;
 801     }
 802     zl = sqlite3Utf8CharLen(zi, -1);
 803     if( zl>=ilen ){
 804       /* string is longer than the requested pad length, return the same string (dup it) */
 805       zo = sqlite3StrDup(zi);
 806       if (!zo){
 807         sqlite3_result_error_nomem(context);
 808         return;
 809       }
 810       sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 811     }else{
 812       zll = strlen(zi);
 813       zo = sqlite3_malloc(zll+ilen-zl+1);
 814       if (!zo){
 815         sqlite3_result_error_nomem(context);
 816         return;
 817       }
 818       zt = strcpy(zo,zi)+zll;
 819       for(i=1; i+zl<=ilen; ++i){
 820         *(zt++) = ' ';
 821       }
 822       *zt = '\0';
 823     }
 824     sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 825     sqlite3_free(zo);
 826   }
 827 }
 828
 829 /*
 830 ** given an input string (s) and an integer (n) appends spaces at the end of  s
 831 ** and adds spaces at the begining of s until it has a length of n characters.
 832 ** Tries to add has many characters at the left as at the right.
 833 ** When s has a length >=n it's a NOP
 834 ** padl(NULL) = NULL
 835 */
 836 static void padcFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 837   i64 ilen;           /* length to pad to */
 838   i64 zl;             /* length of the input string (UTF-8 chars) */
 839   i64 zll;            /* length of the input string (bytes) */
 840   int i = 0;
 841   const char *zi;     /* input string */
 842   char *zo;           /* output string */
 843   char *zt;
 844
 845   assert( argc==2 );
 846
 847   if( sqlite3_value_type(argv[0]) == SQLITE_NULL ){
 848     sqlite3_result_null(context);
 849   }else{
 850     zi = (char *)sqlite3_value_text(argv[0]);
 851     ilen = sqlite3_value_int64(argv[1]);
 852     /* check domain */
 853     if(ilen<0){
 854       sqlite3_result_error(context, "domain error", -1);
 855       return;
 856     }
 857     zl = sqlite3Utf8CharLen(zi, -1);
 858     if( zl>=ilen ){
 859       /* string is longer than the requested pad length, return the same string (dup it) */
 860       zo = sqlite3StrDup(zi);
 861       if (!zo){
 862         sqlite3_result_error_nomem(context);
 863         return;
 864       }
 865       sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 866     }else{
 867       zll = strlen(zi);
 868       zo = sqlite3_malloc(zll+ilen-zl+1);
 869       if (!zo){
 870         sqlite3_result_error_nomem(context);
 871         return;
 872       }
 873       zt = zo;
 874       for(i=1; 2*i+zl<=ilen; ++i){
 875         *(zt++) = ' ';
 876       }
 877       strcpy(zt, zi);
 878       zt+=zll;
 879       for(; i+zl<=ilen; ++i){
 880         *(zt++) = ' ';
 881       }
 882       *zt = '\0';
 883     }
 884     sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 885     sqlite3_free(zo);
 886   }
 887 }
 888
 889 /*
 890 ** given 2 string (s1,s2) returns the string s1 with the characters NOT in s2 removed
 891 ** assumes strings are UTF-8 encoded
 892 */
 893 static void strfilterFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 894   const char *zi1;        /* first parameter string (searched string) */
 895   const char *zi2;        /* second parameter string (vcontains valid characters) */
 896   const char *z1;
 897   const char *z21;
 898   const char *z22;
 899   char *zo;               /* output string */
 900   char *zot;
 901   int c1 = 0;
 902   int c2 = 0;
 903
 904   assert( argc==2 );
 905
 906   if( sqlite3_value_type(argv[0]) == SQLITE_NULL || sqlite3_value_type(argv[1]) == SQLITE_NULL ){
 907     sqlite3_result_null(context);
 908   }else{
 909     zi1 = (char *)sqlite3_value_text(argv[0]);
 910     zi2 = (char *)sqlite3_value_text(argv[1]);
 911     /*
 912     ** maybe I could allocate less, but that would imply 2 passes, rather waste
 913     ** (possibly) some memory
 914     */
 915     zo = sqlite3_malloc(strlen(zi1)+1);
 916     if (!zo){
 917       sqlite3_result_error_nomem(context);
 918       return;
 919     }
 920     zot = zo;
 921     z1 = zi1;
 922     while( (c1=sqliteCharVal((unsigned char *)z1))!=0 ){
 923       z21=zi2;
 924       while( (c2=sqliteCharVal((unsigned char *)z21))!=0 && c2!=c1 ){
 925         sqliteNextChar(z21);
 926       }
 927       if( c2!=0){
 928         z22=z21;
 929         sqliteNextChar(z22);
 930         strncpy(zot, z21, z22-z21);
 931         zot+=z22-z21;
 932       }
 933       sqliteNextChar(z1);
 934     }
 935     *zot = '\0';
 936
 937     sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
 938     sqlite3_free(zo);
 939   }
 940 }
 941
 942 /*
 943 ** Given a string z1, retutns the (0 based) index of it's first occurence
 944 ** in z2 after the first s characters.
 945 ** Returns -1 when there isn't a match.
 946 ** updates p to point to the character where the match occured.
 947 ** This is an auxiliary function.
 948 */
 949 static int _substr(const char* z1, const char* z2, int s, const char** p){
 950   int c = 0;
 951   int rVal=-1;
 952   const char* zt1;
 953   const char* zt2;
 954   int c1,c2;
 955
 956   if( '\0'==*z1 ){
 957     return -1;
 958   }
 959
 960   while( (sqliteCharVal((unsigned char *)z2) != 0) && (c++)<s){
 961     sqliteNextChar(z2);
 962   }
 963
 964   c = 0;
 965   while( (sqliteCharVal((unsigned char *)z2)) != 0 ){
 966     zt1 = z1;
 967     zt2 = z2;
 968
 969     do{
 970       c1 = sqliteCharVal((unsigned char *)zt1);
 971       c2 = sqliteCharVal((unsigned char *)zt2);
 972       sqliteNextChar(zt1);
 973       sqliteNextChar(zt2);
 974     }while( c1 == c2 && c1 != 0 && c2 != 0 );
 975
 976     if( c1 == 0 ){
 977       rVal = c;
 978       break;
 979     }
 980
 981     sqliteNextChar(z2);
 982     ++c;
 983   }
 984   if(p){
 985     *p=z2;
 986   }
 987   return rVal >=0 ? rVal+s : rVal;
 988 }
 989
 990 /*
 991 ** given 2 input strings (s1,s2) and an integer (n) searches from the nth character
 992 ** for the string s1. Returns the position where the match occured.
 993 ** Characters are counted from 1.
 994 ** 0 is returned when no match occurs.
 995 */
 996
 997 static void charindexFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
 998   const u8 *z1;          /* s1 string */
 999   u8 *z2;                /* s2 string */
1000   int s=0;
1001   int rVal=0;
1002
1003   assert( argc==3 ||argc==2);
1004
1005   if( SQLITE_NULL==sqlite3_value_type(argv[0]) || SQLITE_NULL==sqlite3_value_type(argv[1])){
1006     sqlite3_result_null(context);
1007     return;
1008   }
1009
1010   z1 = sqlite3_value_text(argv[0]);
1011   if( z1==0 ) return;
1012   z2 = (u8*) sqlite3_value_text(argv[1]);
1013   if(argc==3){
1014     s = sqlite3_value_int(argv[2])-1;
1015     if(s<0){
1016       s=0;
1017     }
1018   }else{
1019     s = 0;
1020   }
1021
1022   rVal = _substr((char *)z1,(char *)z2,s,NULL);
1023   sqlite3_result_int(context, rVal+1);
1024 }
1025
1026 /*
1027 ** given a string (s) and an integer (n) returns the n leftmost (UTF-8) characters
1028 ** if the string has a length<=n or is NULL this function is NOP
1029 */
1030 static void leftFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1031   int c=0;
1032   int cc=0;
1033   int l=0;
1034   const unsigned char *z;       /* input string */
1035   const unsigned char *zt;
1036   unsigned char *rz;            /* output string */
1037
1038   assert( argc==2);
1039
1040   if( SQLITE_NULL==sqlite3_value_type(argv[0]) || SQLITE_NULL==sqlite3_value_type(argv[1])){
1041     sqlite3_result_null(context);
1042     return;
1043   }
1044
1045   z  = sqlite3_value_text(argv[0]);
1046   l  = sqlite3_value_int(argv[1]);
1047   zt = z;
1048
1049   while( sqliteCharVal(zt) && c++<l)
1050     sqliteNextChar(zt);
1051
1052   cc=zt-z;
1053
1054   rz = sqlite3_malloc(zt-z+1);
1055   if (!rz){
1056     sqlite3_result_error_nomem(context);
1057     return;
1058   }
1059   strncpy((char*) rz, (char*) z, zt-z);
1060   *(rz+cc) = '\0';
1061   sqlite3_result_text(context, (char*)rz, -1, SQLITE_TRANSIENT);
1062   sqlite3_free(rz);
1063 }
1064
1065 /*
1066 ** given a string (s) and an integer (n) returns the n rightmost (UTF-8) characters
1067 ** if the string has a length<=n or is NULL this function is NOP
1068 */
1069 static void rightFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1070   int l=0;
1071   int c=0;
1072   int cc=0;
1073   const char *z;
1074   const char *zt;
1075   const char *ze;
1076   char *rz;
1077
1078   assert( argc==2);
1079
1080   if( SQLITE_NULL == sqlite3_value_type(argv[0]) || SQLITE_NULL == sqlite3_value_type(argv[1])){
1081     sqlite3_result_null(context);
1082     return;
1083   }
1084
1085   z  = (char *)sqlite3_value_text(argv[0]);
1086   l  = sqlite3_value_int(argv[1]);
1087   zt = z;
1088
1089   while( sqliteCharVal((unsigned char *)zt)!=0){
1090     sqliteNextChar(zt);
1091     ++c;
1092   }
1093
1094   ze = zt;
1095   zt = z;
1096
1097   cc=c-l;
1098   if(cc<0)
1099     cc=0;
1100
1101   while( cc-- > 0 ){
1102     sqliteNextChar(zt);
1103   }
1104
1105   rz = sqlite3_malloc(ze-zt+1);
1106   if (!rz){
1107     sqlite3_result_error_nomem(context);
1108     return;
1109   }
1110   strcpy((char*) rz, (char*) (zt));
1111   sqlite3_result_text(context, (char*)rz, -1, SQLITE_TRANSIENT);
1112   sqlite3_free(rz);
1113 }
1114
1115 #ifndef HAVE_TRIM
1116 /*
1117 ** removes the whitespaces at the begining of a string.
1118 */
1119 const char* ltrim(const char* s){
1120   while( *s==' ' )
1121     ++s;
1122   return s;
1123 }
1124
1125 /*
1126 ** removes the whitespaces at the end of a string.
1127 ** !mutates the input string!
1128 */
1129 void rtrim(char* s){
1130   char* ss = s+strlen(s)-1;
1131   while( ss>=s && *ss==' ' )
1132     --ss;
1133   *(ss+1)='\0';
1134 }
1135
1136 /*
1137 **  Removes the whitespace at the begining of a string
1138 */
1139 static void ltrimFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1140   const char *z;
1141
1142   assert( argc==1);
1143
1144   if( SQLITE_NULL==sqlite3_value_type(argv[0]) ){
1145     sqlite3_result_null(context);
1146     return;
1147   }
1148   z = sqlite3_value_text(argv[0]);
1149   sqlite3_result_text(context, ltrim(z), -1, SQLITE_TRANSIENT);
1150 }
1151
1152 /*
1153 **  Removes the whitespace at the end of a string
1154 */
1155 static void rtrimFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1156   const char *z;
1157   char *rz;
1158   /* try not to change data in argv */
1159
1160   assert( argc==1);
1161
1162   if( SQLITE_NULL==sqlite3_value_type(argv[0]) ){
1163     sqlite3_result_null(context);
1164     return;
1165   }
1166   z = sqlite3_value_text(argv[0]);
1167   rz = sqlite3StrDup(z);
1168   rtrim(rz);
1169   sqlite3_result_text(context, rz, -1, SQLITE_TRANSIENT);
1170   sqlite3_free(rz);
1171 }
1172
1173 /*
1174 **  Removes the whitespace at the begining and end of a string
1175 */
1176 static void trimFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1177   const char *z;
1178   char *rz;
1179   /* try not to change data in argv */
1180
1181   assert( argc==1);
1182
1183   if( SQLITE_NULL==sqlite3_value_type(argv[0]) ){
1184     sqlite3_result_null(context);
1185     return;
1186   }
1187   z = sqlite3_value_text(argv[0]);
1188   rz = sqlite3StrDup(z);
1189   rtrim(rz);
1190   sqlite3_result_text(context, ltrim(rz), -1, SQLITE_TRANSIENT);
1191   sqlite3_free(rz);
1192 }
1193 #endif
1194
1195 /*
1196 ** given a pointer to a string s1, the length of that string (l1), a new string (s2)
1197 ** and it's length (l2) appends s2 to s1.
1198 ** All lengths in bytes.
1199 ** This is just an auxiliary function
1200 */
1201 // static void _append(char **s1, int l1, const char *s2, int l2){
1202 //   *s1 = realloc(*s1, (l1+l2+1)*sizeof(char));
1203 //   strncpy((*s1)+l1, s2, l2);
1204 //   *(*(s1)+l1+l2) = '\0';
1205 // }
1206
1207 #ifndef HAVE_TRIM
1208
1209 /*
1210 ** given strings s, s1 and s2 replaces occurrences of s1 in s by s2
1211 */
1212 static void replaceFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1213   const char *z1;     /* string s (first parameter) */
1214   const char *z2;     /* string s1 (second parameter) string to look for */
1215   const char *z3;     /* string s2 (third parameter) string to replace occurrences of s1 with */
1216   int lz1;
1217   int lz2;
1218   int lz3;
1219   int lzo=0;
1220   char *zo=0;
1221   int ret=0;
1222   const char *zt1;
1223   const char *zt2;
1224
1225   assert( 3==argc );
1226
1227   if( SQLITE_NULL==sqlite3_value_type(argv[0]) ){
1228     sqlite3_result_null(context);
1229     return;
1230   }
1231
1232   z1 = sqlite3_value_text(argv[0]);
1233   z2 = sqlite3_value_text(argv[1]);
1234   z3 = sqlite3_value_text(argv[2]);
1235   /* handle possible null values */
1236   if( 0==z2 ){
1237     z2="";
1238   }
1239   if( 0==z3 ){
1240     z3="";
1241   }
1242
1243   lz1 = strlen(z1);
1244   lz2 = strlen(z2);
1245   lz3 = strlen(z3);
1246
1247 #if 0
1248   /* special case when z2 is empty (or null) nothing will be changed */
1249   if( 0==lz2 ){
1250     sqlite3_result_text(context, z1, -1, SQLITE_TRANSIENT);
1251     return;
1252   }
1253 #endif
1254
1255   zt1=z1;
1256   zt2=z1;
1257
1258   while(1){
1259     ret=_substr(z2,zt1 , 0, &zt2);
1260
1261     if( ret<0 )
1262       break;
1263
1264     _append(&zo, lzo, zt1, zt2-zt1);
1265     lzo+=zt2-zt1;
1266     _append(&zo, lzo, z3, lz3);
1267     lzo+=lz3;
1268
1269     zt1=zt2+lz2;
1270   }
1271   _append(&zo, lzo, zt1, lz1-(zt1-z1));
1272   sqlite3_result_text(context, zo, -1, SQLITE_TRANSIENT);
1273   sqlite3_free(zo);
1274 }
1275 #endif
1276
1277 /*
1278 ** given a string returns the same string but with the characters in reverse order
1279 */
1280 static void reverseFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1281   const char *z;
1282   const char *zt;
1283   char *rz;
1284   char *rzt;
1285   int l = 0;
1286   int i = 0;
1287
1288   assert( 1==argc );
1289
1290   if( SQLITE_NULL==sqlite3_value_type(argv[0]) ){
1291     sqlite3_result_null(context);
1292     return;
1293   }
1294   z = (char *)sqlite3_value_text(argv[0]);
1295   l = strlen(z);
1296   rz = sqlite3_malloc(l+1);
1297   if (!rz){
1298     sqlite3_result_error_nomem(context);
1299     return;
1300   }
1301   rzt = rz+l;
1302   *(rzt--) = '\0';
1303
1304   zt=z;
1305   while( sqliteCharVal((unsigned char *)zt)!=0 ){
1306     z=zt;
1307     sqliteNextChar(zt);
1308     for(i=1; zt-i>=z; ++i){
1309       *(rzt--)=*(zt-i);
1310     }
1311   }
1312
1313   sqlite3_result_text(context, rz, -1, SQLITE_TRANSIENT);
1314   sqlite3_free(rz);
1315 }
1316
1317 /*
1318 ** An instance of the following structure holds the context of a
1319 ** stdev() or variance() aggregate computation.
1320 ** implementaion of http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Algorithm_II
1321 ** less prone to rounding errors
1322 */
1323 typedef struct StdevCtx StdevCtx;
1324 struct StdevCtx {
1325   double rM;
1326   double rS;
1327   i64 cnt;          /* number of elements */
1328 };
1329
1330 /*
1331 ** An instance of the following structure holds the context of a
1332 ** mode() or median() aggregate computation.
1333 ** Depends on structures defined in map.c (see map & map)
1334 ** These aggregate functions only work for integers and floats although
1335 ** they could be made to work for strings. This is usually considered meaningless.
1336 ** Only usuall order (for median), no use of collation functions (would this even make sense?)
1337 */
1338 typedef struct ModeCtx ModeCtx;
1339 struct ModeCtx {
1340   i64 riM;            /* integer value found so far */
1341   double rdM;         /* double value found so far */
1342   i64 cnt;            /* number of elements so far */
1343   double pcnt;        /* number of elements smaller than a percentile */
1344   i64 mcnt;           /* maximum number of occurrences (for mode) */
1345   i64 mn;             /* number of occurrences (for mode and percentiles) */
1346   i64 is_double;      /* whether the computation is being done for doubles (>0) or integers (=0) */
1347   map* m;             /* map structure used for the computation */
1348   int done;           /* whether the answer has been found */
1349 };
1350
1351 /*
1352 ** called for each value received during a calculation of stdev or variance
1353 */
1354 static void varianceStep(sqlite3_context *context, int argc, sqlite3_value **argv){
1355   StdevCtx *p;
1356
1357   double delta;
1358   double x;
1359
1360   assert( argc==1 );
1361   p = sqlite3_aggregate_context(context, sizeof(*p));
1362   /* only consider non-null values */
1363   if( SQLITE_NULL != sqlite3_value_numeric_type(argv[0]) ){
1364     p->cnt++;
1365     x = sqlite3_value_double(argv[0]);
1366     delta = (x-p->rM);
1367     p->rM += delta/p->cnt;
1368     p->rS += delta*(x-p->rM);
1369   }
1370 }
1371
1372 /*
1373 ** called for each value received during a calculation of mode of median
1374 */
1375 static void modeStep(sqlite3_context *context, int argc, sqlite3_value **argv){
1376   ModeCtx *p;
1377   i64 xi=0;
1378   double xd=0.0;
1379   i64 *iptr;
1380   double *dptr;
1381   int type;
1382
1383   assert( argc==1 );
1384   type = sqlite3_value_numeric_type(argv[0]);
1385
1386   if( type == SQLITE_NULL)
1387     return;
1388
1389   p = sqlite3_aggregate_context(context, sizeof(*p));
1390
1391   if( 0==(p->m) ){
1392     p->m = calloc(1, sizeof(map));
1393     if( type==SQLITE_INTEGER ){
1394       /* map will be used for integers */
1395       *(p->m) = map_make(int_cmp);
1396       p->is_double = 0;
1397     }else{
1398       p->is_double = 1;
1399       /* map will be used for doubles */
1400       *(p->m) = map_make(double_cmp);
1401     }
1402   }
1403
1404   ++(p->cnt);
1405
1406   if( 0==p->is_double ){
1407     xi = sqlite3_value_int64(argv[0]);
1408     iptr = (i64*)calloc(1,sizeof(i64));
1409     *iptr = xi;
1410     map_insert(p->m, iptr);
1411   }else{
1412     xd = sqlite3_value_double(argv[0]);
1413     dptr = (double*)calloc(1,sizeof(double));
1414     *dptr = xd;
1415     map_insert(p->m, dptr);
1416   }
1417 }
1418
1419 /*
1420 **  Auxiliary function that iterates all elements in a map and finds the mode
1421 **  (most frequent value)
1422 */
1423 static void modeIterate(void* e, i64 c, void* pp){
1424   i64 ei;
1425   double ed;
1426   ModeCtx *p = (ModeCtx*)pp;
1427
1428   if( 0==p->is_double ){
1429     ei = *(int*)(e);
1430
1431         if( p->mcnt==c ){
1432       ++p->mn;
1433     }else if( p->mcnt<c ){
1434       p->riM = ei;
1435       p->mcnt = c;
1436           p->mn=1;
1437     }
1438   }else{
1439     ed = *(double*)(e);
1440
1441         if( p->mcnt==c ){
1442       ++p->mn;
1443     }else if(p->mcnt<c){
1444       p->rdM = ed;
1445       p->mcnt = c;
1446           p->mn=1;
1447     }
1448   }
1449 }
1450
1451 /*
1452 **  Auxiliary function that iterates all elements in a map and finds the median
1453 **  (the value such that the number of elements smaller is equal the the number of
1454 **  elements larger)
1455 */
1456 static void medianIterate(void* e, i64 c, void* pp){
1457   i64 ei;
1458   double ed;
1459   double iL;
1460   double iR;
1461   int il;
1462   int ir;
1463   ModeCtx *p = (ModeCtx*)pp;
1464
1465   if(p->done>0)
1466     return;
1467
1468   iL = p->pcnt;
1469   iR = p->cnt - p->pcnt;
1470   il = p->mcnt + c;
1471   ir = p->cnt - p->mcnt;
1472
1473   if( il >= iL ){
1474     if( ir >= iR ){
1475     ++p->mn;
1476       if( 0==p->is_double ){
1477         ei = *(int*)(e);
1478         p->riM += ei;
1479       }else{
1480         ed = *(double*)(e);
1481         p->rdM += ed;
1482       }
1483     }else{
1484       p->done=1;
1485     }
1486   }
1487   p->mcnt+=c;
1488 }
1489
1490 /*
1491 ** Returns the mode value
1492 */
1493 static void modeFinalize(sqlite3_context *context){
1494   ModeCtx *p;
1495   p = sqlite3_aggregate_context(context, 0);
1496   if( p && p->m ){
1497     map_iterate(p->m, modeIterate, p);
1498     map_destroy(p->m);
1499     free(p->m);
1500
1501     if( 1==p->mn ){
1502       if( 0==p->is_double )
1503         sqlite3_result_int64(context, p->riM);
1504       else
1505         sqlite3_result_double(context, p->rdM);
1506     }
1507   }
1508 }
1509
1510 /*
1511 ** auxiliary function for percentiles
1512 */
1513 static void _medianFinalize(sqlite3_context *context){
1514   ModeCtx *p;
1515   p = (ModeCtx*) sqlite3_aggregate_context(context, 0);
1516   if( p && p->m ){
1517     p->done=0;
1518     map_iterate(p->m, medianIterate, p);
1519     map_destroy(p->m);
1520     free(p->m);
1521
1522     if( 0==p->is_double )
1523       if( 1==p->mn )
1524         sqlite3_result_int64(context, p->riM);
1525       else
1526         sqlite3_result_double(context, p->riM*1.0/p->mn);
1527     else
1528       sqlite3_result_double(context, p->rdM/p->mn);
1529   }
1530 }
1531
1532 /*
1533 ** Returns the median value
1534 */
1535 static void medianFinalize(sqlite3_context *context){
1536   ModeCtx *p;
1537   p = (ModeCtx*) sqlite3_aggregate_context(context, 0);
1538   if( p!=0 ){
1539     p->pcnt = (p->cnt)/2.0;
1540     _medianFinalize(context);
1541   }
1542 }
1543
1544 /*
1545 ** Returns the lower_quartile value
1546 */
1547 static void lower_quartileFinalize(sqlite3_context *context){
1548   ModeCtx *p;
1549   p = (ModeCtx*) sqlite3_aggregate_context(context, 0);
1550   if( p!=0 ){
1551     p->pcnt = (p->cnt)/4.0;
1552     _medianFinalize(context);
1553   }
1554 }
1555
1556 /*
1557 ** Returns the upper_quartile value
1558 */
1559 static void upper_quartileFinalize(sqlite3_context *context){
1560   ModeCtx *p;
1561   p = (ModeCtx*) sqlite3_aggregate_context(context, 0);
1562   if( p!=0 ){
1563     p->pcnt = (p->cnt)*3/4.0;
1564     _medianFinalize(context);
1565   }
1566 }
1567
1568 /*
1569 ** Returns the stdev value
1570 */
1571 static void stdevFinalize(sqlite3_context *context){
1572   StdevCtx *p;
1573   p = sqlite3_aggregate_context(context, 0);
1574   if( p && p->cnt>1 ){
1575     sqlite3_result_double(context, sqrt(p->rS/(p->cnt-1)));
1576   }else{
1577     sqlite3_result_double(context, 0.0);
1578   }
1579 }
1580
1581 /*
1582 ** Returns the variance value
1583 */
1584 static void varianceFinalize(sqlite3_context *context){
1585   StdevCtx *p;
1586   p = sqlite3_aggregate_context(context, 0);
1587   if( p && p->cnt>1 ){
1588     sqlite3_result_double(context, p->rS/(p->cnt-1));
1589   }else{
1590     sqlite3_result_double(context, 0.0);
1591   }
1592 }
1593
1594 #ifdef SQLITE_SOUNDEX
1595
1596 /* relicoder factored code */
1597 /*
1598 ** Calculates the soundex value of a string
1599 */
1600
1601 static void soundex(const u8 *zIn, char *zResult){
1602   int i, j;
1603   static const unsigned char iCode[] = {
1604     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1605     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1606     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1607     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1608     0, 0, 1, 2, 3, 0, 1, 2, 0, 0, 2, 2, 4, 5, 5, 0,
1609     1, 2, 6, 2, 3, 0, 1, 0, 2, 0, 2, 0, 0, 0, 0, 0,
1610     0, 0, 1, 2, 3, 0, 1, 2, 0, 0, 2, 2, 4, 5, 5, 0,
1611     1, 2, 6, 2, 3, 0, 1, 0, 2, 0, 2, 0, 0, 0, 0, 0,
1612   };
1613
1614   for(i=0; zIn[i] && !isalpha(zIn[i]); i++){}
1615   if( zIn[i] ){
1616     zResult[0] = toupper(zIn[i]);
1617     for(j=1; j<4 && zIn[i]; i++){
1618       int code = iCode[zIn[i]&0x7f];
1619       if( code>0 ){
1620         zResult[j++] = code + '0';
1621       }
1622     }
1623     while( j<4 ){
1624       zResult[j++] = '0';
1625     }
1626     zResult[j] = 0;
1627   }else{
1628     strcpy(zResult, "?000");
1629   }
1630 }
1631
1632 /*
1633 ** computes the number of different characters between the soundex value fo 2 strings
1634 */
1635 static void differenceFunc(sqlite3_context *context, int argc, sqlite3_value **argv){
1636   char zResult1[8];
1637   char zResult2[8];
1638   char *zR1 = zResult1;
1639   char *zR2 = zResult2;
1640   int rVal = 0;
1641   int i = 0;
1642   const u8 *zIn1;
1643   const u8 *zIn2;
1644
1645   assert( argc==2 );
1646
1647   if( sqlite3_value_type(argv[0])==SQLITE_NULL || sqlite3_value_type(argv[1])==SQLITE_NULL ){
1648     sqlite3_result_null(context);
1649     return;
1650   }
1651
1652   zIn1 = (u8*)sqlite3_value_text(argv[0]);
1653   zIn2 = (u8*)sqlite3_value_text(argv[1]);
1654
1655   soundex(zIn1, zR1);
1656   soundex(zIn2, zR2);
1657
1658   for(i=0; i<4; ++i){
1659     if( sqliteCharVal((unsigned char *)zR1)==sqliteCharVal((unsigned char *)zR2) )
1660       ++rVal;
1661     sqliteNextChar(zR1);
1662     sqliteNextChar(zR2);
1663   }
1664   sqlite3_result_int(context, rVal);
1665 }
1666 #endif
1667
1668 /*
1669 ** This function registered all of the above C functions as SQL
1670 ** functions.  This should be the only routine in this file with
1671 ** external linkage.
1672 */
1673 int RegisterExtensionFunctions(sqlite3 *db){
1674   static const struct FuncDef {
1675      char *zName;
1676      signed char nArg;
1677      u8 argType;           /* 0: none.  1: db  2: (-1) */
1678      u8 eTextRep;          /* 1: UTF-16.  0: UTF-8 */
1679      u8 needCollSeq;
1680      void (*xFunc)(sqlite3_context*,int,sqlite3_value **);
1681   } aFuncs[] = {
1682     /* math.h */
1683     { "acos",               1, 0, SQLITE_UTF8,    0, acosFunc  },
1684     { "asin",               1, 0, SQLITE_UTF8,    0, asinFunc  },
1685     { "atan",               1, 0, SQLITE_UTF8,    0, atanFunc  },
1686     { "atn2",               2, 0, SQLITE_UTF8,    0, atn2Func  },
1687     /* XXX alias */
1688     { "atan2",              2, 0, SQLITE_UTF8,    0, atn2Func  },
1689     { "acosh",              1, 0, SQLITE_UTF8,    0, acoshFunc  },
1690     { "asinh",              1, 0, SQLITE_UTF8,    0, asinhFunc  },
1691     { "atanh",              1, 0, SQLITE_UTF8,    0, atanhFunc  },
1692
1693     { "difference",         2, 0, SQLITE_UTF8,    0, differenceFunc},
1694     { "degrees",            1, 0, SQLITE_UTF8,    0, rad2degFunc  },
1695     { "radians",            1, 0, SQLITE_UTF8,    0, deg2radFunc  },
1696
1697     { "cos",                1, 0, SQLITE_UTF8,    0, cosFunc  },
1698     { "sin",                1, 0, SQLITE_UTF8,    0, sinFunc },
1699     { "tan",                1, 0, SQLITE_UTF8,    0, tanFunc },
1700     { "cot",                1, 0, SQLITE_UTF8,    0, cotFunc },
1701     { "cosh",               1, 0, SQLITE_UTF8,    0, coshFunc  },
1702     { "sinh",               1, 0, SQLITE_UTF8,    0, sinhFunc },
1703     { "tanh",               1, 0, SQLITE_UTF8,    0, tanhFunc },
1704     { "coth",               1, 0, SQLITE_UTF8,    0, cothFunc },
1705
1706     { "exp",                1, 0, SQLITE_UTF8,    0, expFunc  },
1707     { "log",                1, 0, SQLITE_UTF8,    0, logFunc  },
1708     { "log10",              1, 0, SQLITE_UTF8,    0, log10Func  },
1709     { "power",              2, 0, SQLITE_UTF8,    0, powerFunc  },
1710     { "sign",               1, 0, SQLITE_UTF8,    0, signFunc },
1711     { "sqrt",               1, 0, SQLITE_UTF8,    0, sqrtFunc },
1712     { "square",             1, 0, SQLITE_UTF8,    0, squareFunc },
1713
1714     { "ceil",               1, 0, SQLITE_UTF8,    0, ceilFunc },
1715     { "floor",              1, 0, SQLITE_UTF8,    0, floorFunc },
1716
1717     { "pi",                 0, 0, SQLITE_UTF8,    1, piFunc },
1718
1719
1720     /* string */
1721     { "replicate",          2, 0, SQLITE_UTF8,    0, replicateFunc },
1722     { "charindex",          2, 0, SQLITE_UTF8,    0, charindexFunc },
1723     { "charindex",          3, 0, SQLITE_UTF8,    0, charindexFunc },
1724     { "leftstr",            2, 0, SQLITE_UTF8,    0, leftFunc },
1725     { "rightstr",           2, 0, SQLITE_UTF8,    0, rightFunc },
1726 #ifndef HAVE_TRIM
1727     { "ltrim",              1, 0, SQLITE_UTF8,    0, ltrimFunc },
1728     { "rtrim",              1, 0, SQLITE_UTF8,    0, rtrimFunc },
1729     { "trim",               1, 0, SQLITE_UTF8,    0, trimFunc },
1730     { "replace",            3, 0, SQLITE_UTF8,    0, replaceFunc },
1731 #endif
1732     { "reverse",            1, 0, SQLITE_UTF8,    0, reverseFunc },
1733     { "proper",             1, 0, SQLITE_UTF8,    0, properFunc },
1734     { "padl",               2, 0, SQLITE_UTF8,    0, padlFunc },
1735     { "padr",               2, 0, SQLITE_UTF8,    0, padrFunc },
1736     { "padc",               2, 0, SQLITE_UTF8,    0, padcFunc },
1737     { "strfilter",          2, 0, SQLITE_UTF8,    0, strfilterFunc },
1738
1739   };
1740   /* Aggregate functions */
1741   static const struct FuncDefAgg {
1742     char *zName;
1743     signed char nArg;
1744     u8 argType;
1745     u8 needCollSeq;
1746     void (*xStep)(sqlite3_context*,int,sqlite3_value**);
1747     void (*xFinalize)(sqlite3_context*);
1748   } aAggs[] = {
1749     { "stdev",            1, 0, 0, varianceStep, stdevFinalize  },
1750     { "variance",         1, 0, 0, varianceStep, varianceFinalize  },
1751     { "mode",             1, 0, 0, modeStep,     modeFinalize  },
1752     { "median",           1, 0, 0, modeStep,     medianFinalize  },
1753     { "lower_quartile",   1, 0, 0, modeStep,     lower_quartileFinalize  },
1754     { "upper_quartile",   1, 0, 0, modeStep,     upper_quartileFinalize  },
1755   };
1756   int i;
1757
1758   for(i=0; i<sizeof(aFuncs)/sizeof(aFuncs[0]); i++){
1759     void *pArg = 0;
1760     switch( aFuncs[i].argType ){
1761       case 1: pArg = db; break;
1762       case 2: pArg = (void *)(-1); break;
1763     }
1764     //sqlite3CreateFunc
1765     /* LMH no error checking */
1766     sqlite3_create_function(db, aFuncs[i].zName, aFuncs[i].nArg,
1767         aFuncs[i].eTextRep, pArg, aFuncs[i].xFunc, 0, 0);
1768 #if 0
1769     if( aFuncs[i].needCollSeq ){
1770       struct FuncDef *pFunc = sqlite3FindFunction(db, aFuncs[i].zName,
1771           strlen(aFuncs[i].zName), aFuncs[i].nArg, aFuncs[i].eTextRep, 0);
1772       if( pFunc && aFuncs[i].needCollSeq ){
1773         pFunc->needCollSeq = 1;
1774       }
1775     }
1776 #endif
1777   }
1778
1779   for(i=0; i<sizeof(aAggs)/sizeof(aAggs[0]); i++){
1780     void *pArg = 0;
1781     switch( aAggs[i].argType ){
1782       case 1: pArg = db; break;
1783       case 2: pArg = (void *)(-1); break;
1784     }
1785     //sqlite3CreateFunc
1786     /* LMH no error checking */
1787     sqlite3_create_function(db, aAggs[i].zName, aAggs[i].nArg, SQLITE_UTF8,
1788         pArg, 0, aAggs[i].xStep, aAggs[i].xFinalize);
1789 #if 0
1790     if( aAggs[i].needCollSeq ){
1791       struct FuncDefAgg *pFunc = sqlite3FindFunction( db, aAggs[i].zName,
1792           strlen(aAggs[i].zName), aAggs[i].nArg, SQLITE_UTF8, 0);
1793       if( pFunc && aAggs[i].needCollSeq ){
1794         pFunc->needCollSeq = 1;
1795       }
1796     }
1797 #endif
1798   }
1799   return 0;
1800 }
1801
1802 #ifdef COMPILE_SQLITE_EXTENSIONS_AS_LOADABLE_MODULE
1803 int sqlite3_extension_init(
1804     sqlite3 *db, char **pzErrMsg, const sqlite3_api_routines *pApi){
1805   SQLITE_EXTENSION_INIT2(pApi);
1806   RegisterExtensionFunctions(db);
1807   return 0;
1808 }
1809 #endif /* COMPILE_SQLITE_EXTENSIONS_AS_LOADABLE_MODULE */
1810
1811 map map_make(cmp_func cmp){
1812   map r;
1813   r.cmp=cmp;
1814   r.base = 0;
1815
1816   return r;
1817 }
1818
1819 void* xcalloc(size_t nmemb, size_t size, char* s){
1820   void* ret = calloc(nmemb, size);
1821   return ret;
1822 }
1823
1824 void xfree(void* p){
1825   free(p);
1826 }
1827
1828 void node_insert(node** n, cmp_func cmp, void *e){
1829   int c;
1830   node* nn;
1831   if(*n==0){
1832     nn = (node*)xcalloc(1,sizeof(node), "for node");
1833     nn->data = e;
1834     nn->count = 1;
1835     *n=nn;
1836   }else{
1837     c=cmp((*n)->data,e);
1838     if(0==c){
1839       ++((*n)->count);
1840       xfree(e);
1841     }else if(c>0){
1842       /* put it right here */
1843       node_insert(&((*n)->l), cmp, e);
1844     }else{
1845       node_insert(&((*n)->r), cmp, e);
1846     }
1847   }
1848 }
1849
1850 void map_insert(map *m, void *e){
1851   node_insert(&(m->base), m->cmp, e);
1852 }
1853
1854 void node_iterate(node *n, map_iterator iter, void* p){
1855   if(n){
1856     if(n->l)
1857       node_iterate(n->l, iter, p);
1858     iter(n->data, n->count, p);
1859     if(n->r)
1860       node_iterate(n->r, iter, p);
1861   }
1862 }
1863
1864 void map_iterate(map *m, map_iterator iter, void* p){
1865   node_iterate(m->base, iter, p);
1866 }
1867
1868 void node_destroy(node *n){
1869   if(0!=n){
1870     xfree(n->data);
1871     if(n->l)
1872       node_destroy(n->l);
1873     if(n->r)
1874       node_destroy(n->r);
1875
1876     xfree(n);
1877   }
1878 }
1879
1880 void map_destroy(map *m){
1881   node_destroy(m->base);
1882 }
1883
1884 int int_cmp(const void *a, const void *b){
1885   sqlite_int64 aa = *(sqlite_int64 *)(a);
1886   sqlite_int64 bb = *(sqlite_int64 *)(b);
1887   /* printf("cmp %d <=> %d\n",aa,bb); */
1888   if(aa==bb)
1889     return 0;
1890   else if(aa<bb)
1891     return -1;
1892   else
1893     return 1;
1894 }
1895
1896 int double_cmp(const void *a, const void *b){
1897   double aa = *(double *)(a);
1898   double bb = *(double *)(b);
1899   /* printf("cmp %d <=> %d\n",aa,bb); */
1900   if(aa==bb)
1901     return 0;
1902   else if(aa<bb)
1903     return -1;
1904   else
1905     return 1;
1906 }
1907
1908 void print_elem(void *e, sqlite_int64 c, void* p){
1909   int ee = *(int*)(e);
1910   printf("%d => %lld\n", ee,c);
1911 }
1912