src/util.c

   1 /*
   2 ** 2001 September 15
   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 ** Utility functions used throughout sqlite.
  13 **
  14 ** This file contains functions for allocating memory, comparing
  15 ** strings, and stuff like that.
  16 **
  17 */
  18 #include "sqliteInt.h"
  19 #include <stdarg.h>
  20 #if HAVE_ISNAN || SQLITE_HAVE_ISNAN
  21 # include <math.h>
  22 #endif
  23
  24 /*
  25 ** Routine needed to support the testcase() macro.
  26 */
  27 #ifdef SQLITE_COVERAGE_TEST
  28 void sqlite3Coverage(int x){
  29   static unsigned dummy = 0;
  30   dummy += (unsigned)x;
  31 }
  32 #endif
  33
  34 /*
  35 ** Give a callback to the test harness that can be used to simulate faults
  36 ** in places where it is difficult or expensive to do so purely by means
  37 ** of inputs.
  38 **
  39 ** The intent of the integer argument is to let the fault simulator know
  40 ** which of multiple sqlite3FaultSim() calls has been hit.
  41 **
  42 ** Return whatever integer value the test callback returns, or return
  43 ** SQLITE_OK if no test callback is installed.
  44 */
  45 #ifndef SQLITE_UNTESTABLE
  46 int sqlite3FaultSim(int iTest){
  47   int (*xCallback)(int) = sqlite3GlobalConfig.xTestCallback;
  48   return xCallback ? xCallback(iTest) : SQLITE_OK;
  49 }
  50 #endif
  51
  52 #ifndef SQLITE_OMIT_FLOATING_POINT
  53 /*
  54 ** Return true if the floating point value is Not a Number (NaN).
  55 **
  56 ** Use the math library isnan() function if compiled with SQLITE_HAVE_ISNAN.
  57 ** Otherwise, we have our own implementation that works on most systems.
  58 */
  59 int sqlite3IsNaN(double x){
  60   int rc;   /* The value return */
  61 #if !SQLITE_HAVE_ISNAN && !HAVE_ISNAN
  62   /*
  63   ** Systems that support the isnan() library function should probably
  64   ** make use of it by compiling with -DSQLITE_HAVE_ISNAN.  But we have
  65   ** found that many systems do not have a working isnan() function so
  66   ** this implementation is provided as an alternative.
  67   **
  68   ** This NaN test sometimes fails if compiled on GCC with -ffast-math.
  69   ** On the other hand, the use of -ffast-math comes with the following
  70   ** warning:
  71   **
  72   **      This option [-ffast-math] should never be turned on by any
  73   **      -O option since it can result in incorrect output for programs
  74   **      which depend on an exact implementation of IEEE or ISO
  75   **      rules/specifications for math functions.
  76   **
  77   ** Under MSVC, this NaN test may fail if compiled with a floating-
  78   ** point precision mode other than /fp:precise.  From the MSDN
  79   ** documentation:
  80   **
  81   **      The compiler [with /fp:precise] will properly handle comparisons
  82   **      involving NaN. For example, x != x evaluates to true if x is NaN
  83   **      ...
  84   */
  85 #ifdef __FAST_MATH__
  86 # error SQLite will not work correctly with the -ffast-math option of GCC.
  87 #endif
  88   volatile double y = x;
  89   volatile double z = y;
  90   rc = (y!=z);
  91 #else  /* if HAVE_ISNAN */
  92   rc = isnan(x);
  93 #endif /* HAVE_ISNAN */
  94   testcase( rc );
  95   return rc;
  96 }
  97 #endif /* SQLITE_OMIT_FLOATING_POINT */
  98
  99 /*
 100 ** Compute a string length that is limited to what can be stored in
 101 ** lower 30 bits of a 32-bit signed integer.
 102 **
 103 ** The value returned will never be negative.  Nor will it ever be greater
 104 ** than the actual length of the string.  For very long strings (greater
 105 ** than 1GiB) the value returned might be less than the true string length.
 106 */
 107 int sqlite3Strlen30(const char *z){
 108   if( z==0 ) return 0;
 109   return 0x3fffffff & (int)strlen(z);
 110 }
 111
 112 /*
 113 ** Return the declared type of a column.  Or return zDflt if the column
 114 ** has no declared type.
 115 **
 116 ** The column type is an extra string stored after the zero-terminator on
 117 ** the column name if and only if the COLFLAG_HASTYPE flag is set.
 118 */
 119 char *sqlite3ColumnType(Column *pCol, char *zDflt){
 120   if( (pCol->colFlags & COLFLAG_HASTYPE)==0 ) return zDflt;
 121   return pCol->zName + strlen(pCol->zName) + 1;
 122 }
 123
 124 /*
 125 ** Helper function for sqlite3Error() - called rarely.  Broken out into
 126 ** a separate routine to avoid unnecessary register saves on entry to
 127 ** sqlite3Error().
 128 */
 129 static SQLITE_NOINLINE void  sqlite3ErrorFinish(sqlite3 *db, int err_code){
 130   if( db->pErr ) sqlite3ValueSetNull(db->pErr);
 131   sqlite3SystemError(db, err_code);
 132 }
 133
 134 /*
 135 ** Set the current error code to err_code and clear any prior error message.
 136 ** Also set iSysErrno (by calling sqlite3System) if the err_code indicates
 137 ** that would be appropriate.
 138 */
 139 void sqlite3Error(sqlite3 *db, int err_code){
 140   assert( db!=0 );
 141   db->errCode = err_code;
 142   if( err_code || db->pErr ) sqlite3ErrorFinish(db, err_code);
 143 }
 144
 145 /*
 146 ** Load the sqlite3.iSysErrno field if that is an appropriate thing
 147 ** to do based on the SQLite error code in rc.
 148 */
 149 void sqlite3SystemError(sqlite3 *db, int rc){
 150   if( rc==SQLITE_IOERR_NOMEM ) return;
 151   rc &= 0xff;
 152   if( rc==SQLITE_CANTOPEN || rc==SQLITE_IOERR ){
 153     db->iSysErrno = sqlite3OsGetLastError(db->pVfs);
 154   }
 155 }
 156
 157 /*
 158 ** Set the most recent error code and error string for the sqlite
 159 ** handle "db". The error code is set to "err_code".
 160 **
 161 ** If it is not NULL, string zFormat specifies the format of the
 162 ** error string in the style of the printf functions: The following
 163 ** format characters are allowed:
 164 **
 165 **      %s      Insert a string
 166 **      %z      A string that should be freed after use
 167 **      %d      Insert an integer
 168 **      %T      Insert a token
 169 **      %S      Insert the first element of a SrcList
 170 **
 171 ** zFormat and any string tokens that follow it are assumed to be
 172 ** encoded in UTF-8.
 173 **
 174 ** To clear the most recent error for sqlite handle "db", sqlite3Error
 175 ** should be called with err_code set to SQLITE_OK and zFormat set
 176 ** to NULL.
 177 */
 178 void sqlite3ErrorWithMsg(sqlite3 *db, int err_code, const char *zFormat, ...){
 179   assert( db!=0 );
 180   db->errCode = err_code;
 181   sqlite3SystemError(db, err_code);
 182   if( zFormat==0 ){
 183     sqlite3Error(db, err_code);
 184   }else if( db->pErr || (db->pErr = sqlite3ValueNew(db))!=0 ){
 185     char *z;
 186     va_list ap;
 187     va_start(ap, zFormat);
 188     z = sqlite3VMPrintf(db, zFormat, ap);
 189     va_end(ap);
 190     sqlite3ValueSetStr(db->pErr, -1, z, SQLITE_UTF8, SQLITE_DYNAMIC);
 191   }
 192 }
 193
 194 /*
 195 ** Add an error message to pParse->zErrMsg and increment pParse->nErr.
 196 ** The following formatting characters are allowed:
 197 **
 198 **      %s      Insert a string
 199 **      %z      A string that should be freed after use
 200 **      %d      Insert an integer
 201 **      %T      Insert a token
 202 **      %S      Insert the first element of a SrcList
 203 **
 204 ** This function should be used to report any error that occurs while
 205 ** compiling an SQL statement (i.e. within sqlite3_prepare()). The
 206 ** last thing the sqlite3_prepare() function does is copy the error
 207 ** stored by this function into the database handle using sqlite3Error().
 208 ** Functions sqlite3Error() or sqlite3ErrorWithMsg() should be used
 209 ** during statement execution (sqlite3_step() etc.).
 210 */
 211 void sqlite3ErrorMsg(Parse *pParse, const char *zFormat, ...){
 212   char *zMsg;
 213   va_list ap;
 214   sqlite3 *db = pParse->db;
 215   va_start(ap, zFormat);
 216   zMsg = sqlite3VMPrintf(db, zFormat, ap);
 217   va_end(ap);
 218   if( db->suppressErr ){
 219     sqlite3DbFree(db, zMsg);
 220   }else{
 221     pParse->nErr++;
 222     sqlite3DbFree(db, pParse->zErrMsg);
 223     pParse->zErrMsg = zMsg;
 224     pParse->rc = SQLITE_ERROR;
 225   }
 226 }
 227
 228 /*
 229 ** Convert an SQL-style quoted string into a normal string by removing
 230 ** the quote characters.  The conversion is done in-place.  If the
 231 ** input does not begin with a quote character, then this routine
 232 ** is a no-op.
 233 **
 234 ** The input string must be zero-terminated.  A new zero-terminator
 235 ** is added to the dequoted string.
 236 **
 237 ** The return value is -1 if no dequoting occurs or the length of the
 238 ** dequoted string, exclusive of the zero terminator, if dequoting does
 239 ** occur.
 240 **
 241 ** 2002-02-14: This routine is extended to remove MS-Access style
 242 ** brackets from around identifiers.  For example:  "[a-b-c]" becomes
 243 ** "a-b-c".
 244 */
 245 void sqlite3Dequote(char *z){
 246   char quote;
 247   int i, j;
 248   if( z==0 ) return;
 249   quote = z[0];
 250   if( !sqlite3Isquote(quote) ) return;
 251   if( quote=='[' ) quote = ']';
 252   for(i=1, j=0;; i++){
 253     assert( z[i] );
 254     if( z[i]==quote ){
 255       if( z[i+1]==quote ){
 256         z[j++] = quote;
 257         i++;
 258       }else{
 259         break;
 260       }
 261     }else{
 262       z[j++] = z[i];
 263     }
 264   }
 265   z[j] = 0;
 266 }
 267 void sqlite3DequoteExpr(Expr *p){
 268   assert( sqlite3Isquote(p->u.zToken[0]) );
 269   p->flags |= p->u.zToken[0]=='"' ? EP_Quoted|EP_DblQuoted : EP_Quoted;
 270   sqlite3Dequote(p->u.zToken);
 271 }
 272
 273 /*
 274 ** Generate a Token object from a string
 275 */
 276 void sqlite3TokenInit(Token *p, char *z){
 277   p->z = z;
 278   p->n = sqlite3Strlen30(z);
 279 }
 280
 281 /* Convenient short-hand */
 282 #define UpperToLower sqlite3UpperToLower
 283
 284 /*
 285 ** Some systems have stricmp().  Others have strcasecmp().  Because
 286 ** there is no consistency, we will define our own.
 287 **
 288 ** IMPLEMENTATION-OF: R-30243-02494 The sqlite3_stricmp() and
 289 ** sqlite3_strnicmp() APIs allow applications and extensions to compare
 290 ** the contents of two buffers containing UTF-8 strings in a
 291 ** case-independent fashion, using the same definition of "case
 292 ** independence" that SQLite uses internally when comparing identifiers.
 293 */
 294 int sqlite3_stricmp(const char *zLeft, const char *zRight){
 295   if( zLeft==0 ){
 296     return zRight ? -1 : 0;
 297   }else if( zRight==0 ){
 298     return 1;
 299   }
 300   return sqlite3StrICmp(zLeft, zRight);
 301 }
 302 int sqlite3StrICmp(const char *zLeft, const char *zRight){
 303   unsigned char *a, *b;
 304   int c;
 305   a = (unsigned char *)zLeft;
 306   b = (unsigned char *)zRight;
 307   for(;;){
 308     c = (int)UpperToLower[*a] - (int)UpperToLower[*b];
 309     if( c || *a==0 ) break;
 310     a++;
 311     b++;
 312   }
 313   return c;
 314 }
 315 int sqlite3_strnicmp(const char *zLeft, const char *zRight, int N){
 316   register unsigned char *a, *b;
 317   if( zLeft==0 ){
 318     return zRight ? -1 : 0;
 319   }else if( zRight==0 ){
 320     return 1;
 321   }
 322   a = (unsigned char *)zLeft;
 323   b = (unsigned char *)zRight;
 324   while( N-- > 0 && *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; }
 325   return N<0 ? 0 : UpperToLower[*a] - UpperToLower[*b];
 326 }
 327
 328 /*
 329 ** Compute 10 to the E-th power.  Examples:  E==1 results in 10.
 330 ** E==2 results in 100.  E==50 results in 1.0e50.
 331 **
 332 ** This routine only works for values of E between 1 and 341.
 333 */
 334 static LONGDOUBLE_TYPE sqlite3Pow10(int E){
 335 #if defined(_MSC_VER)
 336   static const LONGDOUBLE_TYPE x[] = {
 337     1.0e+001,
 338     1.0e+002,
 339     1.0e+004,
 340     1.0e+008,
 341     1.0e+016,
 342     1.0e+032,
 343     1.0e+064,
 344     1.0e+128,
 345     1.0e+256
 346   };
 347   LONGDOUBLE_TYPE r = 1.0;
 348   int i;
 349   assert( E>=0 && E<=307 );
 350   for(i=0; E!=0; i++, E >>=1){
 351     if( E & 1 ) r *= x[i];
 352   }
 353   return r;
 354 #else
 355   LONGDOUBLE_TYPE x = 10.0;
 356   LONGDOUBLE_TYPE r = 1.0;
 357   while(1){
 358     if( E & 1 ) r *= x;
 359     E >>= 1;
 360     if( E==0 ) break;
 361     x *= x;
 362   }
 363   return r;
 364 #endif
 365 }
 366
 367 /*
 368 ** The string z[] is an text representation of a real number.
 369 ** Convert this string to a double and write it into *pResult.
 370 **
 371 ** The string z[] is length bytes in length (bytes, not characters) and
 372 ** uses the encoding enc.  The string is not necessarily zero-terminated.
 373 **
 374 ** Return TRUE if the result is a valid real number (or integer) and FALSE
 375 ** if the string is empty or contains extraneous text.  Valid numbers
 376 ** are in one of these formats:
 377 **
 378 **    [+-]digits[E[+-]digits]
 379 **    [+-]digits.[digits][E[+-]digits]
 380 **    [+-].digits[E[+-]digits]
 381 **
 382 ** Leading and trailing whitespace is ignored for the purpose of determining
 383 ** validity.
 384 **
 385 ** If some prefix of the input string is a valid number, this routine
 386 ** returns FALSE but it still converts the prefix and writes the result
 387 ** into *pResult.
 388 */
 389 int sqlite3AtoF(const char *z, double *pResult, int length, u8 enc){
 390 #ifndef SQLITE_OMIT_FLOATING_POINT
 391   int incr;
 392   const char *zEnd = z + length;
 393   /* sign * significand * (10 ^ (esign * exponent)) */
 394   int sign = 1;    /* sign of significand */
 395   i64 s = 0;       /* significand */
 396   int d = 0;       /* adjust exponent for shifting decimal point */
 397   int esign = 1;   /* sign of exponent */
 398   int e = 0;       /* exponent */
 399   int eValid = 1;  /* True exponent is either not used or is well-formed */
 400   double result;
 401   int nDigits = 0;
 402   int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
 403
 404   assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
 405   *pResult = 0.0;   /* Default return value, in case of an error */
 406
 407   if( enc==SQLITE_UTF8 ){
 408     incr = 1;
 409   }else{
 410     int i;
 411     incr = 2;
 412     assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
 413     for(i=3-enc; i<length && z[i]==0; i+=2){}
 414     nonNum = i<length;
 415     zEnd = &z[i^1];
 416     z += (enc&1);
 417   }
 418
 419   /* skip leading spaces */
 420   while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
 421   if( z>=zEnd ) return 0;
 422
 423   /* get sign of significand */
 424   if( *z=='-' ){
 425     sign = -1;
 426     z+=incr;
 427   }else if( *z=='+' ){
 428     z+=incr;
 429   }
 430
 431   /* copy max significant digits to significand */
 432   while( z<zEnd && sqlite3Isdigit(*z) && s<((LARGEST_INT64-9)/10) ){
 433     s = s*10 + (*z - '0');
 434     z+=incr; nDigits++;
 435   }
 436
 437   /* skip non-significant significand digits
 438   ** (increase exponent by d to shift decimal left) */
 439   while( z<zEnd && sqlite3Isdigit(*z) ){ z+=incr; nDigits++; d++; }
 440   if( z>=zEnd ) goto do_atof_calc;
 441
 442   /* if decimal point is present */
 443   if( *z=='.' ){
 444     z+=incr;
 445     /* copy digits from after decimal to significand
 446     ** (decrease exponent by d to shift decimal right) */
 447     while( z<zEnd && sqlite3Isdigit(*z) ){
 448       if( s<((LARGEST_INT64-9)/10) ){
 449         s = s*10 + (*z - '0');
 450         d--;
 451       }
 452       z+=incr; nDigits++;
 453     }
 454   }
 455   if( z>=zEnd ) goto do_atof_calc;
 456
 457   /* if exponent is present */
 458   if( *z=='e' || *z=='E' ){
 459     z+=incr;
 460     eValid = 0;
 461
 462     /* This branch is needed to avoid a (harmless) buffer overread.  The
 463     ** special comment alerts the mutation tester that the correct answer
 464     ** is obtained even if the branch is omitted */
 465     if( z>=zEnd ) goto do_atof_calc;              /*PREVENTS-HARMLESS-OVERREAD*/
 466
 467     /* get sign of exponent */
 468     if( *z=='-' ){
 469       esign = -1;
 470       z+=incr;
 471     }else if( *z=='+' ){
 472       z+=incr;
 473     }
 474     /* copy digits to exponent */
 475     while( z<zEnd && sqlite3Isdigit(*z) ){
 476       e = e<10000 ? (e*10 + (*z - '0')) : 10000;
 477       z+=incr;
 478       eValid = 1;
 479     }
 480   }
 481
 482   /* skip trailing spaces */
 483   while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
 484
 485 do_atof_calc:
 486   /* adjust exponent by d, and update sign */
 487   e = (e*esign) + d;
 488   if( e<0 ) {
 489     esign = -1;
 490     e *= -1;
 491   } else {
 492     esign = 1;
 493   }
 494
 495   if( s==0 ) {
 496     /* In the IEEE 754 standard, zero is signed. */
 497     result = sign<0 ? -(double)0 : (double)0;
 498   } else {
 499     /* Attempt to reduce exponent.
 500     **
 501     ** Branches that are not required for the correct answer but which only
 502     ** help to obtain the correct answer faster are marked with special
 503     ** comments, as a hint to the mutation tester.
 504     */
 505     while( e>0 ){                                       /*OPTIMIZATION-IF-TRUE*/
 506       if( esign>0 ){
 507         if( s>=(LARGEST_INT64/10) ) break;             /*OPTIMIZATION-IF-FALSE*/
 508         s *= 10;
 509       }else{
 510         if( s%10!=0 ) break;                           /*OPTIMIZATION-IF-FALSE*/
 511         s /= 10;
 512       }
 513       e--;
 514     }
 515
 516     /* adjust the sign of significand */
 517     s = sign<0 ? -s : s;
 518
 519     if( e==0 ){                                         /*OPTIMIZATION-IF-TRUE*/
 520       result = (double)s;
 521     }else{
 522       /* attempt to handle extremely small/large numbers better */
 523       if( e>307 ){                                      /*OPTIMIZATION-IF-TRUE*/
 524         if( e<342 ){                                    /*OPTIMIZATION-IF-TRUE*/
 525           LONGDOUBLE_TYPE scale = sqlite3Pow10(e-308);
 526           if( esign<0 ){
 527             result = s / scale;
 528             result /= 1.0e+308;
 529           }else{
 530             result = s * scale;
 531             result *= 1.0e+308;
 532           }
 533         }else{ assert( e>=342 );
 534           if( esign<0 ){
 535             result = 0.0*s;
 536           }else{
 537 #ifdef INFINITY
 538             result = INFINITY*s;
 539 #else
 540             result = 1e308*1e308*s;  /* Infinity */
 541 #endif
 542           }
 543         }
 544       }else{
 545         LONGDOUBLE_TYPE scale = sqlite3Pow10(e);
 546         if( esign<0 ){
 547           result = s / scale;
 548         }else{
 549           result = s * scale;
 550         }
 551       }
 552     }
 553   }
 554
 555   /* store the result */
 556   *pResult = result;
 557
 558   /* return true if number and no extra non-whitespace chracters after */
 559   return z==zEnd && nDigits>0 && eValid && nonNum==0;
 560 #else
 561   return !sqlite3Atoi64(z, pResult, length, enc);
 562 #endif /* SQLITE_OMIT_FLOATING_POINT */
 563 }
 564
 565 /*
 566 ** Compare the 19-character string zNum against the text representation
 567 ** value 2^63:  9223372036854775808.  Return negative, zero, or positive
 568 ** if zNum is less than, equal to, or greater than the string.
 569 ** Note that zNum must contain exactly 19 characters.
 570 **
 571 ** Unlike memcmp() this routine is guaranteed to return the difference
 572 ** in the values of the last digit if the only difference is in the
 573 ** last digit.  So, for example,
 574 **
 575 **      compare2pow63("9223372036854775800", 1)
 576 **
 577 ** will return -8.
 578 */
 579 static int compare2pow63(const char *zNum, int incr){
 580   int c = 0;
 581   int i;
 582                     /* 012345678901234567 */
 583   const char *pow63 = "922337203685477580";
 584   for(i=0; c==0 && i<18; i++){
 585     c = (zNum[i*incr]-pow63[i])*10;
 586   }
 587   if( c==0 ){
 588     c = zNum[18*incr] - '8';
 589     testcase( c==(-1) );
 590     testcase( c==0 );
 591     testcase( c==(+1) );
 592   }
 593   return c;
 594 }
 595
 596 /*
 597 ** Convert zNum to a 64-bit signed integer.  zNum must be decimal. This
 598 ** routine does *not* accept hexadecimal notation.
 599 **
 600 ** Returns:
 601 **
 602 **     0    Successful transformation.  Fits in a 64-bit signed integer.
 603 **     1    Excess non-space text after the integer value
 604 **     2    Integer too large for a 64-bit signed integer or is malformed
 605 **     3    Special case of 9223372036854775808
 606 **
 607 ** length is the number of bytes in the string (bytes, not characters).
 608 ** The string is not necessarily zero-terminated.  The encoding is
 609 ** given by enc.
 610 */
 611 int sqlite3Atoi64(const char *zNum, i64 *pNum, int length, u8 enc){
 612   int incr;
 613   u64 u = 0;
 614   int neg = 0; /* assume positive */
 615   int i;
 616   int c = 0;
 617   int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
 618   int rc;          /* Baseline return code */
 619   const char *zStart;
 620   const char *zEnd = zNum + length;
 621   assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
 622   if( enc==SQLITE_UTF8 ){
 623     incr = 1;
 624   }else{
 625     incr = 2;
 626     assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
 627     for(i=3-enc; i<length && zNum[i]==0; i+=2){}
 628     nonNum = i<length;
 629     zEnd = &zNum[i^1];
 630     zNum += (enc&1);
 631   }
 632   while( zNum<zEnd && sqlite3Isspace(*zNum) ) zNum+=incr;
 633   if( zNum<zEnd ){
 634     if( *zNum=='-' ){
 635       neg = 1;
 636       zNum+=incr;
 637     }else if( *zNum=='+' ){
 638       zNum+=incr;
 639     }
 640   }
 641   zStart = zNum;
 642   while( zNum<zEnd && zNum[0]=='0' ){ zNum+=incr; } /* Skip leading zeros. */
 643   for(i=0; &zNum[i]<zEnd && (c=zNum[i])>='0' && c<='9'; i+=incr){
 644     u = u*10 + c - '0';
 645   }
 646   testcase( i==18*incr );
 647   testcase( i==19*incr );
 648   testcase( i==20*incr );
 649   if( u>LARGEST_INT64 ){
 650     /* This test and assignment is needed only to suppress UB warnings
 651     ** from clang and -fsanitize=undefined.  This test and assignment make
 652     ** the code a little larger and slower, and no harm comes from omitting
 653     ** them, but we must appaise the undefined-behavior pharisees. */
 654     *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
 655   }else if( neg ){
 656     *pNum = -(i64)u;
 657   }else{
 658     *pNum = (i64)u;
 659   }
 660   rc = 0;
 661   if( (i==0 && zStart==zNum)     /* No digits */
 662    || nonNum                     /* UTF16 with high-order bytes non-zero */
 663   ){
 664     rc = 1;
 665   }else if( &zNum[i]<zEnd ){     /* Extra bytes at the end */
 666     int jj = i;
 667     do{
 668       if( !sqlite3Isspace(zNum[jj]) ){
 669         rc = 1;          /* Extra non-space text after the integer */
 670         break;
 671       }
 672       jj += incr;
 673     }while( &zNum[jj]<zEnd );
 674   }
 675   if( i<19*incr ){
 676     /* Less than 19 digits, so we know that it fits in 64 bits */
 677     assert( u<=LARGEST_INT64 );
 678     return rc;
 679   }else{
 680     /* zNum is a 19-digit numbers.  Compare it against 9223372036854775808. */
 681     c = i>19*incr ? 1 : compare2pow63(zNum, incr);
 682     if( c<0 ){
 683       /* zNum is less than 9223372036854775808 so it fits */
 684       assert( u<=LARGEST_INT64 );
 685       return rc;
 686     }else{
 687       *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
 688       if( c>0 ){
 689         /* zNum is greater than 9223372036854775808 so it overflows */
 690         return 2;
 691       }else{
 692         /* zNum is exactly 9223372036854775808.  Fits if negative.  The
 693         ** special case 2 overflow if positive */
 694         assert( u-1==LARGEST_INT64 );
 695         return neg ? rc : 3;
 696       }
 697     }
 698   }
 699 }
 700
 701 /*
 702 ** Transform a UTF-8 integer literal, in either decimal or hexadecimal,
 703 ** into a 64-bit signed integer.  This routine accepts hexadecimal literals,
 704 ** whereas sqlite3Atoi64() does not.
 705 **
 706 ** Returns:
 707 **
 708 **     0    Successful transformation.  Fits in a 64-bit signed integer.
 709 **     1    Excess text after the integer value
 710 **     2    Integer too large for a 64-bit signed integer or is malformed
 711 **     3    Special case of 9223372036854775808
 712 */
 713 int sqlite3DecOrHexToI64(const char *z, i64 *pOut){
 714 #ifndef SQLITE_OMIT_HEX_INTEGER
 715   if( z[0]=='0'
 716    && (z[1]=='x' || z[1]=='X')
 717   ){
 718     u64 u = 0;
 719     int i, k;
 720     for(i=2; z[i]=='0'; i++){}
 721     for(k=i; sqlite3Isxdigit(z[k]); k++){
 722       u = u*16 + sqlite3HexToInt(z[k]);
 723     }
 724     memcpy(pOut, &u, 8);
 725     return (z[k]==0 && k-i<=16) ? 0 : 2;
 726   }else
 727 #endif /* SQLITE_OMIT_HEX_INTEGER */
 728   {
 729     return sqlite3Atoi64(z, pOut, sqlite3Strlen30(z), SQLITE_UTF8);
 730   }
 731 }
 732
 733 /*
 734 ** If zNum represents an integer that will fit in 32-bits, then set
 735 ** *pValue to that integer and return true.  Otherwise return false.
 736 **
 737 ** This routine accepts both decimal and hexadecimal notation for integers.
 738 **
 739 ** Any non-numeric characters that following zNum are ignored.
 740 ** This is different from sqlite3Atoi64() which requires the
 741 ** input number to be zero-terminated.
 742 */
 743 int sqlite3GetInt32(const char *zNum, int *pValue){
 744   sqlite_int64 v = 0;
 745   int i, c;
 746   int neg = 0;
 747   if( zNum[0]=='-' ){
 748     neg = 1;
 749     zNum++;
 750   }else if( zNum[0]=='+' ){
 751     zNum++;
 752   }
 753 #ifndef SQLITE_OMIT_HEX_INTEGER
 754   else if( zNum[0]=='0'
 755         && (zNum[1]=='x' || zNum[1]=='X')
 756         && sqlite3Isxdigit(zNum[2])
 757   ){
 758     u32 u = 0;
 759     zNum += 2;
 760     while( zNum[0]=='0' ) zNum++;
 761     for(i=0; sqlite3Isxdigit(zNum[i]) && i<8; i++){
 762       u = u*16 + sqlite3HexToInt(zNum[i]);
 763     }
 764     if( (u&0x80000000)==0 && sqlite3Isxdigit(zNum[i])==0 ){
 765       memcpy(pValue, &u, 4);
 766       return 1;
 767     }else{
 768       return 0;
 769     }
 770   }
 771 #endif
 772   if( !sqlite3Isdigit(zNum[0]) ) return 0;
 773   while( zNum[0]=='0' ) zNum++;
 774   for(i=0; i<11 && (c = zNum[i] - '0')>=0 && c<=9; i++){
 775     v = v*10 + c;
 776   }
 777
 778   /* The longest decimal representation of a 32 bit integer is 10 digits:
 779   **
 780   **             1234567890
 781   **     2^31 -> 2147483648
 782   */
 783   testcase( i==10 );
 784   if( i>10 ){
 785     return 0;
 786   }
 787   testcase( v-neg==2147483647 );
 788   if( v-neg>2147483647 ){
 789     return 0;
 790   }
 791   if( neg ){
 792     v = -v;
 793   }
 794   *pValue = (int)v;
 795   return 1;
 796 }
 797
 798 /*
 799 ** Return a 32-bit integer value extracted from a string.  If the
 800 ** string is not an integer, just return 0.
 801 */
 802 int sqlite3Atoi(const char *z){
 803   int x = 0;
 804   if( z ) sqlite3GetInt32(z, &x);
 805   return x;
 806 }
 807
 808 /*
 809 ** The variable-length integer encoding is as follows:
 810 **
 811 ** KEY:
 812 **         A = 0xxxxxxx    7 bits of data and one flag bit
 813 **         B = 1xxxxxxx    7 bits of data and one flag bit
 814 **         C = xxxxxxxx    8 bits of data
 815 **
 816 **  7 bits - A
 817 ** 14 bits - BA
 818 ** 21 bits - BBA
 819 ** 28 bits - BBBA
 820 ** 35 bits - BBBBA
 821 ** 42 bits - BBBBBA
 822 ** 49 bits - BBBBBBA
 823 ** 56 bits - BBBBBBBA
 824 ** 64 bits - BBBBBBBBC
 825 */
 826
 827 /*
 828 ** Write a 64-bit variable-length integer to memory starting at p[0].
 829 ** The length of data write will be between 1 and 9 bytes.  The number
 830 ** of bytes written is returned.
 831 **
 832 ** A variable-length integer consists of the lower 7 bits of each byte
 833 ** for all bytes that have the 8th bit set and one byte with the 8th
 834 ** bit clear.  Except, if we get to the 9th byte, it stores the full
 835 ** 8 bits and is the last byte.
 836 */
 837 static int SQLITE_NOINLINE putVarint64(unsigned char *p, u64 v){
 838   int i, j, n;
 839   u8 buf[10];
 840   if( v & (((u64)0xff000000)<<32) ){
 841     p[8] = (u8)v;
 842     v >>= 8;
 843     for(i=7; i>=0; i--){
 844       p[i] = (u8)((v & 0x7f) | 0x80);
 845       v >>= 7;
 846     }
 847     return 9;
 848   }
 849   n = 0;
 850   do{
 851     buf[n++] = (u8)((v & 0x7f) | 0x80);
 852     v >>= 7;
 853   }while( v!=0 );
 854   buf[0] &= 0x7f;
 855   assert( n<=9 );
 856   for(i=0, j=n-1; j>=0; j--, i++){
 857     p[i] = buf[j];
 858   }
 859   return n;
 860 }
 861 int sqlite3PutVarint(unsigned char *p, u64 v){
 862   if( v<=0x7f ){
 863     p[0] = v&0x7f;
 864     return 1;
 865   }
 866   if( v<=0x3fff ){
 867     p[0] = ((v>>7)&0x7f)|0x80;
 868     p[1] = v&0x7f;
 869     return 2;
 870   }
 871   return putVarint64(p,v);
 872 }
 873
 874 /*
 875 ** Bitmasks used by sqlite3GetVarint().  These precomputed constants
 876 ** are defined here rather than simply putting the constant expressions
 877 ** inline in order to work around bugs in the RVT compiler.
 878 **
 879 ** SLOT_2_0     A mask for  (0x7f<<14) | 0x7f
 880 **
 881 ** SLOT_4_2_0   A mask for  (0x7f<<28) | SLOT_2_0
 882 */
 883 #define SLOT_2_0     0x001fc07f
 884 #define SLOT_4_2_0   0xf01fc07f
 885
 886
 887 /*
 888 ** Read a 64-bit variable-length integer from memory starting at p[0].
 889 ** Return the number of bytes read.  The value is stored in *v.
 890 */
 891 u8 sqlite3GetVarint(const unsigned char *p, u64 *v){
 892   u32 a,b,s;
 893
 894   a = *p;
 895   /* a: p0 (unmasked) */
 896   if (!(a&0x80))
 897   {
 898     *v = a;
 899     return 1;
 900   }
 901
 902   p++;
 903   b = *p;
 904   /* b: p1 (unmasked) */
 905   if (!(b&0x80))
 906   {
 907     a &= 0x7f;
 908     a = a<<7;
 909     a |= b;
 910     *v = a;
 911     return 2;
 912   }
 913
 914   /* Verify that constants are precomputed correctly */
 915   assert( SLOT_2_0 == ((0x7f<<14) | (0x7f)) );
 916   assert( SLOT_4_2_0 == ((0xfU<<28) | (0x7f<<14) | (0x7f)) );
 917
 918   p++;
 919   a = a<<14;
 920   a |= *p;
 921   /* a: p0<<14 | p2 (unmasked) */
 922   if (!(a&0x80))
 923   {
 924     a &= SLOT_2_0;
 925     b &= 0x7f;
 926     b = b<<7;
 927     a |= b;
 928     *v = a;
 929     return 3;
 930   }
 931
 932   /* CSE1 from below */
 933   a &= SLOT_2_0;
 934   p++;
 935   b = b<<14;
 936   b |= *p;
 937   /* b: p1<<14 | p3 (unmasked) */
 938   if (!(b&0x80))
 939   {
 940     b &= SLOT_2_0;
 941     /* moved CSE1 up */
 942     /* a &= (0x7f<<14)|(0x7f); */
 943     a = a<<7;
 944     a |= b;
 945     *v = a;
 946     return 4;
 947   }
 948
 949   /* a: p0<<14 | p2 (masked) */
 950   /* b: p1<<14 | p3 (unmasked) */
 951   /* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
 952   /* moved CSE1 up */
 953   /* a &= (0x7f<<14)|(0x7f); */
 954   b &= SLOT_2_0;
 955   s = a;
 956   /* s: p0<<14 | p2 (masked) */
 957
 958   p++;
 959   a = a<<14;
 960   a |= *p;
 961   /* a: p0<<28 | p2<<14 | p4 (unmasked) */
 962   if (!(a&0x80))
 963   {
 964     /* we can skip these cause they were (effectively) done above
 965     ** while calculating s */
 966     /* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
 967     /* b &= (0x7f<<14)|(0x7f); */
 968     b = b<<7;
 969     a |= b;
 970     s = s>>18;
 971     *v = ((u64)s)<<32 | a;
 972     return 5;
 973   }
 974
 975   /* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
 976   s = s<<7;
 977   s |= b;
 978   /* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
 979
 980   p++;
 981   b = b<<14;
 982   b |= *p;
 983   /* b: p1<<28 | p3<<14 | p5 (unmasked) */
 984   if (!(b&0x80))
 985   {
 986     /* we can skip this cause it was (effectively) done above in calc'ing s */
 987     /* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
 988     a &= SLOT_2_0;
 989     a = a<<7;
 990     a |= b;
 991     s = s>>18;
 992     *v = ((u64)s)<<32 | a;
 993     return 6;
 994   }
 995
 996   p++;
 997   a = a<<14;
 998   a |= *p;
 999   /* a: p2<<28 | p4<<14 | p6 (unmasked) */
1000   if (!(a&0x80))
1001   {
1002     a &= SLOT_4_2_0;
1003     b &= SLOT_2_0;
1004     b = b<<7;
1005     a |= b;
1006     s = s>>11;
1007     *v = ((u64)s)<<32 | a;
1008     return 7;
1009   }
1010
1011   /* CSE2 from below */
1012   a &= SLOT_2_0;
1013   p++;
1014   b = b<<14;
1015   b |= *p;
1016   /* b: p3<<28 | p5<<14 | p7 (unmasked) */
1017   if (!(b&0x80))
1018   {
1019     b &= SLOT_4_2_0;
1020     /* moved CSE2 up */
1021     /* a &= (0x7f<<14)|(0x7f); */
1022     a = a<<7;
1023     a |= b;
1024     s = s>>4;
1025     *v = ((u64)s)<<32 | a;
1026     return 8;
1027   }
1028
1029   p++;
1030   a = a<<15;
1031   a |= *p;
1032   /* a: p4<<29 | p6<<15 | p8 (unmasked) */
1033
1034   /* moved CSE2 up */
1035   /* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
1036   b &= SLOT_2_0;
1037   b = b<<8;
1038   a |= b;
1039
1040   s = s<<4;
1041   b = p[-4];
1042   b &= 0x7f;
1043   b = b>>3;
1044   s |= b;
1045
1046   *v = ((u64)s)<<32 | a;
1047
1048   return 9;
1049 }
1050
1051 /*
1052 ** Read a 32-bit variable-length integer from memory starting at p[0].
1053 ** Return the number of bytes read.  The value is stored in *v.
1054 **
1055 ** If the varint stored in p[0] is larger than can fit in a 32-bit unsigned
1056 ** integer, then set *v to 0xffffffff.
1057 **
1058 ** A MACRO version, getVarint32, is provided which inlines the
1059 ** single-byte case.  All code should use the MACRO version as
1060 ** this function assumes the single-byte case has already been handled.
1061 */
1062 u8 sqlite3GetVarint32(const unsigned char *p, u32 *v){
1063   u32 a,b;
1064
1065   /* The 1-byte case.  Overwhelmingly the most common.  Handled inline
1066   ** by the getVarin32() macro */
1067   a = *p;
1068   /* a: p0 (unmasked) */
1069 #ifndef getVarint32
1070   if (!(a&0x80))
1071   {
1072     /* Values between 0 and 127 */
1073     *v = a;
1074     return 1;
1075   }
1076 #endif
1077
1078   /* The 2-byte case */
1079   p++;
1080   b = *p;
1081   /* b: p1 (unmasked) */
1082   if (!(b&0x80))
1083   {
1084     /* Values between 128 and 16383 */
1085     a &= 0x7f;
1086     a = a<<7;
1087     *v = a | b;
1088     return 2;
1089   }
1090
1091   /* The 3-byte case */
1092   p++;
1093   a = a<<14;
1094   a |= *p;
1095   /* a: p0<<14 | p2 (unmasked) */
1096   if (!(a&0x80))
1097   {
1098     /* Values between 16384 and 2097151 */
1099     a &= (0x7f<<14)|(0x7f);
1100     b &= 0x7f;
1101     b = b<<7;
1102     *v = a | b;
1103     return 3;
1104   }
1105
1106   /* A 32-bit varint is used to store size information in btrees.
1107   ** Objects are rarely larger than 2MiB limit of a 3-byte varint.
1108   ** A 3-byte varint is sufficient, for example, to record the size
1109   ** of a 1048569-byte BLOB or string.
1110   **
1111   ** We only unroll the first 1-, 2-, and 3- byte cases.  The very
1112   ** rare larger cases can be handled by the slower 64-bit varint
1113   ** routine.
1114   */
1115 #if 1
1116   {
1117     u64 v64;
1118     u8 n;
1119
1120     p -= 2;
1121     n = sqlite3GetVarint(p, &v64);
1122     assert( n>3 && n<=9 );
1123     if( (v64 & SQLITE_MAX_U32)!=v64 ){
1124       *v = 0xffffffff;
1125     }else{
1126       *v = (u32)v64;
1127     }
1128     return n;
1129   }
1130
1131 #else
1132   /* For following code (kept for historical record only) shows an
1133   ** unrolling for the 3- and 4-byte varint cases.  This code is
1134   ** slightly faster, but it is also larger and much harder to test.
1135   */
1136   p++;
1137   b = b<<14;
1138   b |= *p;
1139   /* b: p1<<14 | p3 (unmasked) */
1140   if (!(b&0x80))
1141   {
1142     /* Values between 2097152 and 268435455 */
1143     b &= (0x7f<<14)|(0x7f);
1144     a &= (0x7f<<14)|(0x7f);
1145     a = a<<7;
1146     *v = a | b;
1147     return 4;
1148   }
1149
1150   p++;
1151   a = a<<14;
1152   a |= *p;
1153   /* a: p0<<28 | p2<<14 | p4 (unmasked) */
1154   if (!(a&0x80))
1155   {
1156     /* Values  between 268435456 and 34359738367 */
1157     a &= SLOT_4_2_0;
1158     b &= SLOT_4_2_0;
1159     b = b<<7;
1160     *v = a | b;
1161     return 5;
1162   }
1163
1164   /* We can only reach this point when reading a corrupt database
1165   ** file.  In that case we are not in any hurry.  Use the (relatively
1166   ** slow) general-purpose sqlite3GetVarint() routine to extract the
1167   ** value. */
1168   {
1169     u64 v64;
1170     u8 n;
1171
1172     p -= 4;
1173     n = sqlite3GetVarint(p, &v64);
1174     assert( n>5 && n<=9 );
1175     *v = (u32)v64;
1176     return n;
1177   }
1178 #endif
1179 }
1180
1181 /*
1182 ** Return the number of bytes that will be needed to store the given
1183 ** 64-bit integer.
1184 */
1185 int sqlite3VarintLen(u64 v){
1186   int i;
1187   for(i=1; (v >>= 7)!=0; i++){ assert( i<10 ); }
1188   return i;
1189 }
1190
1191
1192 /*
1193 ** Read or write a four-byte big-endian integer value.
1194 */
1195 u32 sqlite3Get4byte(const u8 *p){
1196 #if SQLITE_BYTEORDER==4321
1197   u32 x;
1198   memcpy(&x,p,4);
1199   return x;
1200 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
1201   u32 x;
1202   memcpy(&x,p,4);
1203   return __builtin_bswap32(x);
1204 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
1205   u32 x;
1206   memcpy(&x,p,4);
1207   return _byteswap_ulong(x);
1208 #else
1209   testcase( p[0]&0x80 );
1210   return ((unsigned)p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
1211 #endif
1212 }
1213 void sqlite3Put4byte(unsigned char *p, u32 v){
1214 #if SQLITE_BYTEORDER==4321
1215   memcpy(p,&v,4);
1216 #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
1217   u32 x = __builtin_bswap32(v);
1218   memcpy(p,&x,4);
1219 #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
1220   u32 x = _byteswap_ulong(v);
1221   memcpy(p,&x,4);
1222 #else
1223   p[0] = (u8)(v>>24);
1224   p[1] = (u8)(v>>16);
1225   p[2] = (u8)(v>>8);
1226   p[3] = (u8)v;
1227 #endif
1228 }
1229
1230
1231
1232 /*
1233 ** Translate a single byte of Hex into an integer.
1234 ** This routine only works if h really is a valid hexadecimal
1235 ** character:  0..9a..fA..F
1236 */
1237 u8 sqlite3HexToInt(int h){
1238   assert( (h>='0' && h<='9') ||  (h>='a' && h<='f') ||  (h>='A' && h<='F') );
1239 #ifdef SQLITE_ASCII
1240   h += 9*(1&(h>>6));
1241 #endif
1242 #ifdef SQLITE_EBCDIC
1243   h += 9*(1&~(h>>4));
1244 #endif
1245   return (u8)(h & 0xf);
1246 }
1247
1248 #if !defined(SQLITE_OMIT_BLOB_LITERAL) || defined(SQLITE_HAS_CODEC)
1249 /*
1250 ** Convert a BLOB literal of the form "x'hhhhhh'" into its binary
1251 ** value.  Return a pointer to its binary value.  Space to hold the
1252 ** binary value has been obtained from malloc and must be freed by
1253 ** the calling routine.
1254 */
1255 void *sqlite3HexToBlob(sqlite3 *db, const char *z, int n){
1256   char *zBlob;
1257   int i;
1258
1259   zBlob = (char *)sqlite3DbMallocRawNN(db, n/2 + 1);
1260   n--;
1261   if( zBlob ){
1262     for(i=0; i<n; i+=2){
1263       zBlob[i/2] = (sqlite3HexToInt(z[i])<<4) | sqlite3HexToInt(z[i+1]);
1264     }
1265     zBlob[i/2] = 0;
1266   }
1267   return zBlob;
1268 }
1269 #endif /* !SQLITE_OMIT_BLOB_LITERAL || SQLITE_HAS_CODEC */
1270
1271 /*
1272 ** Log an error that is an API call on a connection pointer that should
1273 ** not have been used.  The "type" of connection pointer is given as the
1274 ** argument.  The zType is a word like "NULL" or "closed" or "invalid".
1275 */
1276 static void logBadConnection(const char *zType){
1277   sqlite3_log(SQLITE_MISUSE,
1278      "API call with %s database connection pointer",
1279      zType
1280   );
1281 }
1282
1283 /*
1284 ** Check to make sure we have a valid db pointer.  This test is not
1285 ** foolproof but it does provide some measure of protection against
1286 ** misuse of the interface such as passing in db pointers that are
1287 ** NULL or which have been previously closed.  If this routine returns
1288 ** 1 it means that the db pointer is valid and 0 if it should not be
1289 ** dereferenced for any reason.  The calling function should invoke
1290 ** SQLITE_MISUSE immediately.
1291 **
1292 ** sqlite3SafetyCheckOk() requires that the db pointer be valid for
1293 ** use.  sqlite3SafetyCheckSickOrOk() allows a db pointer that failed to
1294 ** open properly and is not fit for general use but which can be
1295 ** used as an argument to sqlite3_errmsg() or sqlite3_close().
1296 */
1297 int sqlite3SafetyCheckOk(sqlite3 *db){
1298   u32 magic;
1299   if( db==0 ){
1300     logBadConnection("NULL");
1301     return 0;
1302   }
1303   magic = db->magic;
1304   if( magic!=SQLITE_MAGIC_OPEN ){
1305     if( sqlite3SafetyCheckSickOrOk(db) ){
1306       testcase( sqlite3GlobalConfig.xLog!=0 );
1307       logBadConnection("unopened");
1308     }
1309     return 0;
1310   }else{
1311     return 1;
1312   }
1313 }
1314 int sqlite3SafetyCheckSickOrOk(sqlite3 *db){
1315   u32 magic;
1316   magic = db->magic;
1317   if( magic!=SQLITE_MAGIC_SICK &&
1318       magic!=SQLITE_MAGIC_OPEN &&
1319       magic!=SQLITE_MAGIC_BUSY ){
1320     testcase( sqlite3GlobalConfig.xLog!=0 );
1321     logBadConnection("invalid");
1322     return 0;
1323   }else{
1324     return 1;
1325   }
1326 }
1327
1328 /*
1329 ** Attempt to add, substract, or multiply the 64-bit signed value iB against
1330 ** the other 64-bit signed integer at *pA and store the result in *pA.
1331 ** Return 0 on success.  Or if the operation would have resulted in an
1332 ** overflow, leave *pA unchanged and return 1.
1333 */
1334 int sqlite3AddInt64(i64 *pA, i64 iB){
1335 #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
1336   return __builtin_add_overflow(*pA, iB, pA);
1337 #else
1338   i64 iA = *pA;
1339   testcase( iA==0 ); testcase( iA==1 );
1340   testcase( iB==-1 ); testcase( iB==0 );
1341   if( iB>=0 ){
1342     testcase( iA>0 && LARGEST_INT64 - iA == iB );
1343     testcase( iA>0 && LARGEST_INT64 - iA == iB - 1 );
1344     if( iA>0 && LARGEST_INT64 - iA < iB ) return 1;
1345   }else{
1346     testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 1 );
1347     testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 2 );
1348     if( iA<0 && -(iA + LARGEST_INT64) > iB + 1 ) return 1;
1349   }
1350   *pA += iB;
1351   return 0;
1352 #endif
1353 }
1354 int sqlite3SubInt64(i64 *pA, i64 iB){
1355 #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
1356   return __builtin_sub_overflow(*pA, iB, pA);
1357 #else
1358   testcase( iB==SMALLEST_INT64+1 );
1359   if( iB==SMALLEST_INT64 ){
1360     testcase( (*pA)==(-1) ); testcase( (*pA)==0 );
1361     if( (*pA)>=0 ) return 1;
1362     *pA -= iB;
1363     return 0;
1364   }else{
1365     return sqlite3AddInt64(pA, -iB);
1366   }
1367 #endif
1368 }
1369 int sqlite3MulInt64(i64 *pA, i64 iB){
1370 #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
1371   return __builtin_mul_overflow(*pA, iB, pA);
1372 #else
1373   i64 iA = *pA;
1374   if( iB>0 ){
1375     if( iA>LARGEST_INT64/iB ) return 1;
1376     if( iA<SMALLEST_INT64/iB ) return 1;
1377   }else if( iB<0 ){
1378     if( iA>0 ){
1379       if( iB<SMALLEST_INT64/iA ) return 1;
1380     }else if( iA<0 ){
1381       if( iB==SMALLEST_INT64 ) return 1;
1382       if( iA==SMALLEST_INT64 ) return 1;
1383       if( -iA>LARGEST_INT64/-iB ) return 1;
1384     }
1385   }
1386   *pA = iA*iB;
1387   return 0;
1388 #endif
1389 }
1390
1391 /*
1392 ** Compute the absolute value of a 32-bit signed integer, of possible.  Or
1393 ** if the integer has a value of -2147483648, return +2147483647
1394 */
1395 int sqlite3AbsInt32(int x){
1396   if( x>=0 ) return x;
1397   if( x==(int)0x80000000 ) return 0x7fffffff;
1398   return -x;
1399 }
1400
1401 #ifdef SQLITE_ENABLE_8_3_NAMES
1402 /*
1403 ** If SQLITE_ENABLE_8_3_NAMES is set at compile-time and if the database
1404 ** filename in zBaseFilename is a URI with the "8_3_names=1" parameter and
1405 ** if filename in z[] has a suffix (a.k.a. "extension") that is longer than
1406 ** three characters, then shorten the suffix on z[] to be the last three
1407 ** characters of the original suffix.
1408 **
1409 ** If SQLITE_ENABLE_8_3_NAMES is set to 2 at compile-time, then always
1410 ** do the suffix shortening regardless of URI parameter.
1411 **
1412 ** Examples:
1413 **
1414 **     test.db-journal    =>   test.nal
1415 **     test.db-wal        =>   test.wal
1416 **     test.db-shm        =>   test.shm
1417 **     test.db-mj7f3319fa =>   test.9fa
1418 */
1419 void sqlite3FileSuffix3(const char *zBaseFilename, char *z){
1420 #if SQLITE_ENABLE_8_3_NAMES<2
1421   if( sqlite3_uri_boolean(zBaseFilename, "8_3_names", 0) )
1422 #endif
1423   {
1424     int i, sz;
1425     sz = sqlite3Strlen30(z);
1426     for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
1427     if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
1428   }
1429 }
1430 #endif
1431
1432 /*
1433 ** Find (an approximate) sum of two LogEst values.  This computation is
1434 ** not a simple "+" operator because LogEst is stored as a logarithmic
1435 ** value.
1436 **
1437 */
1438 LogEst sqlite3LogEstAdd(LogEst a, LogEst b){
1439   static const unsigned char x[] = {
1440      10, 10,                         /* 0,1 */
1441       9, 9,                          /* 2,3 */
1442       8, 8,                          /* 4,5 */
1443       7, 7, 7,                       /* 6,7,8 */
1444       6, 6, 6,                       /* 9,10,11 */
1445       5, 5, 5,                       /* 12-14 */
1446       4, 4, 4, 4,                    /* 15-18 */
1447       3, 3, 3, 3, 3, 3,              /* 19-24 */
1448       2, 2, 2, 2, 2, 2, 2,           /* 25-31 */
1449   };
1450   if( a>=b ){
1451     if( a>b+49 ) return a;
1452     if( a>b+31 ) return a+1;
1453     return a+x[a-b];
1454   }else{
1455     if( b>a+49 ) return b;
1456     if( b>a+31 ) return b+1;
1457     return b+x[b-a];
1458   }
1459 }
1460
1461 /*
1462 ** Convert an integer into a LogEst.  In other words, compute an
1463 ** approximation for 10*log2(x).
1464 */
1465 LogEst sqlite3LogEst(u64 x){
1466   static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
1467   LogEst y = 40;
1468   if( x<8 ){
1469     if( x<2 ) return 0;
1470     while( x<8 ){  y -= 10; x <<= 1; }
1471   }else{
1472 #if GCC_VERSION>=5004000
1473     int i = 60 - __builtin_clzll(x);
1474     y += i*10;
1475     x >>= i;
1476 #else
1477     while( x>255 ){ y += 40; x >>= 4; }  /*OPTIMIZATION-IF-TRUE*/
1478     while( x>15 ){  y += 10; x >>= 1; }
1479 #endif
1480   }
1481   return a[x&7] + y - 10;
1482 }
1483
1484 #ifndef SQLITE_OMIT_VIRTUALTABLE
1485 /*
1486 ** Convert a double into a LogEst
1487 ** In other words, compute an approximation for 10*log2(x).
1488 */
1489 LogEst sqlite3LogEstFromDouble(double x){
1490   u64 a;
1491   LogEst e;
1492   assert( sizeof(x)==8 && sizeof(a)==8 );
1493   if( x<=1 ) return 0;
1494   if( x<=2000000000 ) return sqlite3LogEst((u64)x);
1495   memcpy(&a, &x, 8);
1496   e = (a>>52) - 1022;
1497   return e*10;
1498 }
1499 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1500
1501 #if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \
1502     defined(SQLITE_ENABLE_STAT3_OR_STAT4) || \
1503     defined(SQLITE_EXPLAIN_ESTIMATED_ROWS)
1504 /*
1505 ** Convert a LogEst into an integer.
1506 **
1507 ** Note that this routine is only used when one or more of various
1508 ** non-standard compile-time options is enabled.
1509 */
1510 u64 sqlite3LogEstToInt(LogEst x){
1511   u64 n;
1512   n = x%10;
1513   x /= 10;
1514   if( n>=5 ) n -= 2;
1515   else if( n>=1 ) n -= 1;
1516 #if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \
1517     defined(SQLITE_EXPLAIN_ESTIMATED_ROWS)
1518   if( x>60 ) return (u64)LARGEST_INT64;
1519 #else
1520   /* If only SQLITE_ENABLE_STAT3_OR_STAT4 is on, then the largest input
1521   ** possible to this routine is 310, resulting in a maximum x of 31 */
1522   assert( x<=60 );
1523 #endif
1524   return x>=3 ? (n+8)<<(x-3) : (n+8)>>(3-x);
1525 }
1526 #endif /* defined SCANSTAT or STAT4 or ESTIMATED_ROWS */
1527
1528 /*
1529 ** Add a new name/number pair to a VList.  This might require that the
1530 ** VList object be reallocated, so return the new VList.  If an OOM
1531 ** error occurs, the original VList returned and the
1532 ** db->mallocFailed flag is set.
1533 **
1534 ** A VList is really just an array of integers.  To destroy a VList,
1535 ** simply pass it to sqlite3DbFree().
1536 **
1537 ** The first integer is the number of integers allocated for the whole
1538 ** VList.  The second integer is the number of integers actually used.
1539 ** Each name/number pair is encoded by subsequent groups of 3 or more
1540 ** integers.
1541 **
1542 ** Each name/number pair starts with two integers which are the numeric
1543 ** value for the pair and the size of the name/number pair, respectively.
1544 ** The text name overlays one or more following integers.  The text name
1545 ** is always zero-terminated.
1546 **
1547 ** Conceptually:
1548 **
1549 **    struct VList {
1550 **      int nAlloc;   // Number of allocated slots
1551 **      int nUsed;    // Number of used slots
1552 **      struct VListEntry {
1553 **        int iValue;    // Value for this entry
1554 **        int nSlot;     // Slots used by this entry
1555 **        // ... variable name goes here
1556 **      } a[0];
1557 **    }
1558 **
1559 ** During code generation, pointers to the variable names within the
1560 ** VList are taken.  When that happens, nAlloc is set to zero as an
1561 ** indication that the VList may never again be enlarged, since the
1562 ** accompanying realloc() would invalidate the pointers.
1563 */
1564 VList *sqlite3VListAdd(
1565   sqlite3 *db,           /* The database connection used for malloc() */
1566   VList *pIn,            /* The input VList.  Might be NULL */
1567   const char *zName,     /* Name of symbol to add */
1568   int nName,             /* Bytes of text in zName */
1569   int iVal               /* Value to associate with zName */
1570 ){
1571   int nInt;              /* number of sizeof(int) objects needed for zName */
1572   char *z;               /* Pointer to where zName will be stored */
1573   int i;                 /* Index in pIn[] where zName is stored */
1574
1575   nInt = nName/4 + 3;
1576   assert( pIn==0 || pIn[0]>=3 );  /* Verify ok to add new elements */
1577   if( pIn==0 || pIn[1]+nInt > pIn[0] ){
1578     /* Enlarge the allocation */
1579     int nAlloc = (pIn ? pIn[0]*2 : 10) + nInt;
1580     VList *pOut = sqlite3DbRealloc(db, pIn, nAlloc*sizeof(int));
1581     if( pOut==0 ) return pIn;
1582     if( pIn==0 ) pOut[1] = 2;
1583     pIn = pOut;
1584     pIn[0] = nAlloc;
1585   }
1586   i = pIn[1];
1587   pIn[i] = iVal;
1588   pIn[i+1] = nInt;
1589   z = (char*)&pIn[i+2];
1590   pIn[1] = i+nInt;
1591   assert( pIn[1]<=pIn[0] );
1592   memcpy(z, zName, nName);
1593   z[nName] = 0;
1594   return pIn;
1595 }
1596
1597 /*
1598 ** Return a pointer to the name of a variable in the given VList that
1599 ** has the value iVal.  Or return a NULL if there is no such variable in
1600 ** the list
1601 */
1602 const char *sqlite3VListNumToName(VList *pIn, int iVal){
1603   int i, mx;
1604   if( pIn==0 ) return 0;
1605   mx = pIn[1];
1606   i = 2;
1607   do{
1608     if( pIn[i]==iVal ) return (char*)&pIn[i+2];
1609     i += pIn[i+1];
1610   }while( i<mx );
1611   return 0;
1612 }
1613
1614 /*
1615 ** Return the number of the variable named zName, if it is in VList.
1616 ** or return 0 if there is no such variable.
1617 */
1618 int sqlite3VListNameToNum(VList *pIn, const char *zName, int nName){
1619   int i, mx;
1620   if( pIn==0 ) return 0;
1621   mx = pIn[1];
1622   i = 2;
1623   do{
1624     const char *z = (const char*)&pIn[i+2];
1625     if( strncmp(z,zName,nName)==0 && z[nName]==0 ) return pIn[i];
1626     i += pIn[i+1];
1627   }while( i<mx );
1628   return 0;
1629 }