000001  /*
000002  ** 2001 September 15
000003  **
000004  ** The author disclaims copyright to this source code.  In place of
000005  ** a legal notice, here is a blessing:
000006  **
000007  **    May you do good and not evil.
000008  **    May you find forgiveness for yourself and forgive others.
000009  **    May you share freely, never taking more than you give.
000010  **
000011  *************************************************************************
000012  ** Utility functions used throughout sqlite.
000013  **
000014  ** This file contains functions for allocating memory, comparing
000015  ** strings, and stuff like that.
000016  **
000017  */
000018  #include "sqliteInt.h"
000019  #include <stdarg.h>
000020  #if HAVE_ISNAN || SQLITE_HAVE_ISNAN
000021  # include <math.h>
000022  #endif
000023  
000024  /*
000025  ** Routine needed to support the testcase() macro.
000026  */
000027  #ifdef SQLITE_COVERAGE_TEST
000028  void sqlite3Coverage(int x){
000029    static unsigned dummy = 0;
000030    dummy += (unsigned)x;
000031  }
000032  #endif
000033  
000034  /*
000035  ** Give a callback to the test harness that can be used to simulate faults
000036  ** in places where it is difficult or expensive to do so purely by means
000037  ** of inputs.
000038  **
000039  ** The intent of the integer argument is to let the fault simulator know
000040  ** which of multiple sqlite3FaultSim() calls has been hit.
000041  **
000042  ** Return whatever integer value the test callback returns, or return
000043  ** SQLITE_OK if no test callback is installed.
000044  */
000045  #ifndef SQLITE_UNTESTABLE
000046  int sqlite3FaultSim(int iTest){
000047    int (*xCallback)(int) = sqlite3GlobalConfig.xTestCallback;
000048    return xCallback ? xCallback(iTest) : SQLITE_OK;
000049  }
000050  #endif
000051  
000052  #ifndef SQLITE_OMIT_FLOATING_POINT
000053  /*
000054  ** Return true if the floating point value is Not a Number (NaN).
000055  **
000056  ** Use the math library isnan() function if compiled with SQLITE_HAVE_ISNAN.
000057  ** Otherwise, we have our own implementation that works on most systems.
000058  */
000059  int sqlite3IsNaN(double x){
000060    int rc;   /* The value return */
000061  #if !SQLITE_HAVE_ISNAN && !HAVE_ISNAN
000062    /*
000063    ** Systems that support the isnan() library function should probably
000064    ** make use of it by compiling with -DSQLITE_HAVE_ISNAN.  But we have
000065    ** found that many systems do not have a working isnan() function so
000066    ** this implementation is provided as an alternative.
000067    **
000068    ** This NaN test sometimes fails if compiled on GCC with -ffast-math.
000069    ** On the other hand, the use of -ffast-math comes with the following
000070    ** warning:
000071    **
000072    **      This option [-ffast-math] should never be turned on by any
000073    **      -O option since it can result in incorrect output for programs
000074    **      which depend on an exact implementation of IEEE or ISO 
000075    **      rules/specifications for math functions.
000076    **
000077    ** Under MSVC, this NaN test may fail if compiled with a floating-
000078    ** point precision mode other than /fp:precise.  From the MSDN 
000079    ** documentation:
000080    **
000081    **      The compiler [with /fp:precise] will properly handle comparisons 
000082    **      involving NaN. For example, x != x evaluates to true if x is NaN 
000083    **      ...
000084    */
000085  #ifdef __FAST_MATH__
000086  # error SQLite will not work correctly with the -ffast-math option of GCC.
000087  #endif
000088    volatile double y = x;
000089    volatile double z = y;
000090    rc = (y!=z);
000091  #else  /* if HAVE_ISNAN */
000092    rc = isnan(x);
000093  #endif /* HAVE_ISNAN */
000094    testcase( rc );
000095    return rc;
000096  }
000097  #endif /* SQLITE_OMIT_FLOATING_POINT */
000098  
000099  /*
000100  ** Compute a string length that is limited to what can be stored in
000101  ** lower 30 bits of a 32-bit signed integer.
000102  **
000103  ** The value returned will never be negative.  Nor will it ever be greater
000104  ** than the actual length of the string.  For very long strings (greater
000105  ** than 1GiB) the value returned might be less than the true string length.
000106  */
000107  int sqlite3Strlen30(const char *z){
000108    if( z==0 ) return 0;
000109    return 0x3fffffff & (int)strlen(z);
000110  }
000111  
000112  /*
000113  ** Return the declared type of a column.  Or return zDflt if the column 
000114  ** has no declared type.
000115  **
000116  ** The column type is an extra string stored after the zero-terminator on
000117  ** the column name if and only if the COLFLAG_HASTYPE flag is set.
000118  */
000119  char *sqlite3ColumnType(Column *pCol, char *zDflt){
000120    if( (pCol->colFlags & COLFLAG_HASTYPE)==0 ) return zDflt;
000121    return pCol->zName + strlen(pCol->zName) + 1;
000122  }
000123  
000124  /*
000125  ** Helper function for sqlite3Error() - called rarely.  Broken out into
000126  ** a separate routine to avoid unnecessary register saves on entry to
000127  ** sqlite3Error().
000128  */
000129  static SQLITE_NOINLINE void  sqlite3ErrorFinish(sqlite3 *db, int err_code){
000130    if( db->pErr ) sqlite3ValueSetNull(db->pErr);
000131    sqlite3SystemError(db, err_code);
000132  }
000133  
000134  /*
000135  ** Set the current error code to err_code and clear any prior error message.
000136  ** Also set iSysErrno (by calling sqlite3System) if the err_code indicates
000137  ** that would be appropriate.
000138  */
000139  void sqlite3Error(sqlite3 *db, int err_code){
000140    assert( db!=0 );
000141    db->errCode = err_code;
000142    if( err_code || db->pErr ) sqlite3ErrorFinish(db, err_code);
000143  }
000144  
000145  /*
000146  ** Load the sqlite3.iSysErrno field if that is an appropriate thing
000147  ** to do based on the SQLite error code in rc.
000148  */
000149  void sqlite3SystemError(sqlite3 *db, int rc){
000150    if( rc==SQLITE_IOERR_NOMEM ) return;
000151    rc &= 0xff;
000152    if( rc==SQLITE_CANTOPEN || rc==SQLITE_IOERR ){
000153      db->iSysErrno = sqlite3OsGetLastError(db->pVfs);
000154    }
000155  }
000156  
000157  /*
000158  ** Set the most recent error code and error string for the sqlite
000159  ** handle "db". The error code is set to "err_code".
000160  **
000161  ** If it is not NULL, string zFormat specifies the format of the
000162  ** error string in the style of the printf functions: The following
000163  ** format characters are allowed:
000164  **
000165  **      %s      Insert a string
000166  **      %z      A string that should be freed after use
000167  **      %d      Insert an integer
000168  **      %T      Insert a token
000169  **      %S      Insert the first element of a SrcList
000170  **
000171  ** zFormat and any string tokens that follow it are assumed to be
000172  ** encoded in UTF-8.
000173  **
000174  ** To clear the most recent error for sqlite handle "db", sqlite3Error
000175  ** should be called with err_code set to SQLITE_OK and zFormat set
000176  ** to NULL.
000177  */
000178  void sqlite3ErrorWithMsg(sqlite3 *db, int err_code, const char *zFormat, ...){
000179    assert( db!=0 );
000180    db->errCode = err_code;
000181    sqlite3SystemError(db, err_code);
000182    if( zFormat==0 ){
000183      sqlite3Error(db, err_code);
000184    }else if( db->pErr || (db->pErr = sqlite3ValueNew(db))!=0 ){
000185      char *z;
000186      va_list ap;
000187      va_start(ap, zFormat);
000188      z = sqlite3VMPrintf(db, zFormat, ap);
000189      va_end(ap);
000190      sqlite3ValueSetStr(db->pErr, -1, z, SQLITE_UTF8, SQLITE_DYNAMIC);
000191    }
000192  }
000193  
000194  /*
000195  ** Add an error message to pParse->zErrMsg and increment pParse->nErr.
000196  ** The following formatting characters are allowed:
000197  **
000198  **      %s      Insert a string
000199  **      %z      A string that should be freed after use
000200  **      %d      Insert an integer
000201  **      %T      Insert a token
000202  **      %S      Insert the first element of a SrcList
000203  **
000204  ** This function should be used to report any error that occurs while
000205  ** compiling an SQL statement (i.e. within sqlite3_prepare()). The
000206  ** last thing the sqlite3_prepare() function does is copy the error
000207  ** stored by this function into the database handle using sqlite3Error().
000208  ** Functions sqlite3Error() or sqlite3ErrorWithMsg() should be used
000209  ** during statement execution (sqlite3_step() etc.).
000210  */
000211  void sqlite3ErrorMsg(Parse *pParse, const char *zFormat, ...){
000212    char *zMsg;
000213    va_list ap;
000214    sqlite3 *db = pParse->db;
000215    va_start(ap, zFormat);
000216    zMsg = sqlite3VMPrintf(db, zFormat, ap);
000217    va_end(ap);
000218    if( db->suppressErr ){
000219      sqlite3DbFree(db, zMsg);
000220    }else{
000221      pParse->nErr++;
000222      sqlite3DbFree(db, pParse->zErrMsg);
000223      pParse->zErrMsg = zMsg;
000224      pParse->rc = SQLITE_ERROR;
000225    }
000226  }
000227  
000228  /*
000229  ** Convert an SQL-style quoted string into a normal string by removing
000230  ** the quote characters.  The conversion is done in-place.  If the
000231  ** input does not begin with a quote character, then this routine
000232  ** is a no-op.
000233  **
000234  ** The input string must be zero-terminated.  A new zero-terminator
000235  ** is added to the dequoted string.
000236  **
000237  ** The return value is -1 if no dequoting occurs or the length of the
000238  ** dequoted string, exclusive of the zero terminator, if dequoting does
000239  ** occur.
000240  **
000241  ** 2002-Feb-14: This routine is extended to remove MS-Access style
000242  ** brackets from around identifiers.  For example:  "[a-b-c]" becomes
000243  ** "a-b-c".
000244  */
000245  void sqlite3Dequote(char *z){
000246    char quote;
000247    int i, j;
000248    if( z==0 ) return;
000249    quote = z[0];
000250    if( !sqlite3Isquote(quote) ) return;
000251    if( quote=='[' ) quote = ']';
000252    for(i=1, j=0;; i++){
000253      assert( z[i] );
000254      if( z[i]==quote ){
000255        if( z[i+1]==quote ){
000256          z[j++] = quote;
000257          i++;
000258        }else{
000259          break;
000260        }
000261      }else{
000262        z[j++] = z[i];
000263      }
000264    }
000265    z[j] = 0;
000266  }
000267  
000268  /*
000269  ** Generate a Token object from a string
000270  */
000271  void sqlite3TokenInit(Token *p, char *z){
000272    p->z = z;
000273    p->n = sqlite3Strlen30(z);
000274  }
000275  
000276  /* Convenient short-hand */
000277  #define UpperToLower sqlite3UpperToLower
000278  
000279  /*
000280  ** Some systems have stricmp().  Others have strcasecmp().  Because
000281  ** there is no consistency, we will define our own.
000282  **
000283  ** IMPLEMENTATION-OF: R-30243-02494 The sqlite3_stricmp() and
000284  ** sqlite3_strnicmp() APIs allow applications and extensions to compare
000285  ** the contents of two buffers containing UTF-8 strings in a
000286  ** case-independent fashion, using the same definition of "case
000287  ** independence" that SQLite uses internally when comparing identifiers.
000288  */
000289  int sqlite3_stricmp(const char *zLeft, const char *zRight){
000290    if( zLeft==0 ){
000291      return zRight ? -1 : 0;
000292    }else if( zRight==0 ){
000293      return 1;
000294    }
000295    return sqlite3StrICmp(zLeft, zRight);
000296  }
000297  int sqlite3StrICmp(const char *zLeft, const char *zRight){
000298    unsigned char *a, *b;
000299    int c;
000300    a = (unsigned char *)zLeft;
000301    b = (unsigned char *)zRight;
000302    for(;;){
000303      c = (int)UpperToLower[*a] - (int)UpperToLower[*b];
000304      if( c || *a==0 ) break;
000305      a++;
000306      b++;
000307    }
000308    return c;
000309  }
000310  int sqlite3_strnicmp(const char *zLeft, const char *zRight, int N){
000311    register unsigned char *a, *b;
000312    if( zLeft==0 ){
000313      return zRight ? -1 : 0;
000314    }else if( zRight==0 ){
000315      return 1;
000316    }
000317    a = (unsigned char *)zLeft;
000318    b = (unsigned char *)zRight;
000319    while( N-- > 0 && *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; }
000320    return N<0 ? 0 : UpperToLower[*a] - UpperToLower[*b];
000321  }
000322  
000323  /*
000324  ** Compute 10 to the E-th power.  Examples:  E==1 results in 10.
000325  ** E==2 results in 100.  E==50 results in 1.0e50.
000326  **
000327  ** This routine only works for values of E between 1 and 341.
000328  */
000329  static LONGDOUBLE_TYPE sqlite3Pow10(int E){
000330  #if defined(_MSC_VER)
000331    static const LONGDOUBLE_TYPE x[] = {
000332      1.0e+001,
000333      1.0e+002,
000334      1.0e+004,
000335      1.0e+008,
000336      1.0e+016,
000337      1.0e+032,
000338      1.0e+064,
000339      1.0e+128,
000340      1.0e+256
000341    };
000342    LONGDOUBLE_TYPE r = 1.0;
000343    int i;
000344    assert( E>=0 && E<=307 );
000345    for(i=0; E!=0; i++, E >>=1){
000346      if( E & 1 ) r *= x[i];
000347    }
000348    return r;
000349  #else
000350    LONGDOUBLE_TYPE x = 10.0;
000351    LONGDOUBLE_TYPE r = 1.0;
000352    while(1){
000353      if( E & 1 ) r *= x;
000354      E >>= 1;
000355      if( E==0 ) break;
000356      x *= x;
000357    }
000358    return r; 
000359  #endif
000360  }
000361  
000362  /*
000363  ** The string z[] is an text representation of a real number.
000364  ** Convert this string to a double and write it into *pResult.
000365  **
000366  ** The string z[] is length bytes in length (bytes, not characters) and
000367  ** uses the encoding enc.  The string is not necessarily zero-terminated.
000368  **
000369  ** Return TRUE if the result is a valid real number (or integer) and FALSE
000370  ** if the string is empty or contains extraneous text.  Valid numbers
000371  ** are in one of these formats:
000372  **
000373  **    [+-]digits[E[+-]digits]
000374  **    [+-]digits.[digits][E[+-]digits]
000375  **    [+-].digits[E[+-]digits]
000376  **
000377  ** Leading and trailing whitespace is ignored for the purpose of determining
000378  ** validity.
000379  **
000380  ** If some prefix of the input string is a valid number, this routine
000381  ** returns FALSE but it still converts the prefix and writes the result
000382  ** into *pResult.
000383  */
000384  int sqlite3AtoF(const char *z, double *pResult, int length, u8 enc){
000385  #ifndef SQLITE_OMIT_FLOATING_POINT
000386    int incr;
000387    const char *zEnd = z + length;
000388    /* sign * significand * (10 ^ (esign * exponent)) */
000389    int sign = 1;    /* sign of significand */
000390    i64 s = 0;       /* significand */
000391    int d = 0;       /* adjust exponent for shifting decimal point */
000392    int esign = 1;   /* sign of exponent */
000393    int e = 0;       /* exponent */
000394    int eValid = 1;  /* True exponent is either not used or is well-formed */
000395    double result;
000396    int nDigits = 0;
000397    int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
000398  
000399    assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
000400    *pResult = 0.0;   /* Default return value, in case of an error */
000401  
000402    if( enc==SQLITE_UTF8 ){
000403      incr = 1;
000404    }else{
000405      int i;
000406      incr = 2;
000407      assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
000408      for(i=3-enc; i<length && z[i]==0; i+=2){}
000409      nonNum = i<length;
000410      zEnd = &z[i^1];
000411      z += (enc&1);
000412    }
000413  
000414    /* skip leading spaces */
000415    while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
000416    if( z>=zEnd ) return 0;
000417  
000418    /* get sign of significand */
000419    if( *z=='-' ){
000420      sign = -1;
000421      z+=incr;
000422    }else if( *z=='+' ){
000423      z+=incr;
000424    }
000425  
000426    /* copy max significant digits to significand */
000427    while( z<zEnd && sqlite3Isdigit(*z) && s<((LARGEST_INT64-9)/10) ){
000428      s = s*10 + (*z - '0');
000429      z+=incr; nDigits++;
000430    }
000431  
000432    /* skip non-significant significand digits
000433    ** (increase exponent by d to shift decimal left) */
000434    while( z<zEnd && sqlite3Isdigit(*z) ){ z+=incr; nDigits++; d++; }
000435    if( z>=zEnd ) goto do_atof_calc;
000436  
000437    /* if decimal point is present */
000438    if( *z=='.' ){
000439      z+=incr;
000440      /* copy digits from after decimal to significand
000441      ** (decrease exponent by d to shift decimal right) */
000442      while( z<zEnd && sqlite3Isdigit(*z) ){
000443        if( s<((LARGEST_INT64-9)/10) ){
000444          s = s*10 + (*z - '0');
000445          d--;
000446        }
000447        z+=incr; nDigits++;
000448      }
000449    }
000450    if( z>=zEnd ) goto do_atof_calc;
000451  
000452    /* if exponent is present */
000453    if( *z=='e' || *z=='E' ){
000454      z+=incr;
000455      eValid = 0;
000456  
000457      /* This branch is needed to avoid a (harmless) buffer overread.  The 
000458      ** special comment alerts the mutation tester that the correct answer
000459      ** is obtained even if the branch is omitted */
000460      if( z>=zEnd ) goto do_atof_calc;              /*PREVENTS-HARMLESS-OVERREAD*/
000461  
000462      /* get sign of exponent */
000463      if( *z=='-' ){
000464        esign = -1;
000465        z+=incr;
000466      }else if( *z=='+' ){
000467        z+=incr;
000468      }
000469      /* copy digits to exponent */
000470      while( z<zEnd && sqlite3Isdigit(*z) ){
000471        e = e<10000 ? (e*10 + (*z - '0')) : 10000;
000472        z+=incr;
000473        eValid = 1;
000474      }
000475    }
000476  
000477    /* skip trailing spaces */
000478    while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
000479  
000480  do_atof_calc:
000481    /* adjust exponent by d, and update sign */
000482    e = (e*esign) + d;
000483    if( e<0 ) {
000484      esign = -1;
000485      e *= -1;
000486    } else {
000487      esign = 1;
000488    }
000489  
000490    if( s==0 ) {
000491      /* In the IEEE 754 standard, zero is signed. */
000492      result = sign<0 ? -(double)0 : (double)0;
000493    } else {
000494      /* Attempt to reduce exponent.
000495      **
000496      ** Branches that are not required for the correct answer but which only
000497      ** help to obtain the correct answer faster are marked with special
000498      ** comments, as a hint to the mutation tester.
000499      */
000500      while( e>0 ){                                       /*OPTIMIZATION-IF-TRUE*/
000501        if( esign>0 ){
000502          if( s>=(LARGEST_INT64/10) ) break;             /*OPTIMIZATION-IF-FALSE*/
000503          s *= 10;
000504        }else{
000505          if( s%10!=0 ) break;                           /*OPTIMIZATION-IF-FALSE*/
000506          s /= 10;
000507        }
000508        e--;
000509      }
000510  
000511      /* adjust the sign of significand */
000512      s = sign<0 ? -s : s;
000513  
000514      if( e==0 ){                                         /*OPTIMIZATION-IF-TRUE*/
000515        result = (double)s;
000516      }else{
000517        /* attempt to handle extremely small/large numbers better */
000518        if( e>307 ){                                      /*OPTIMIZATION-IF-TRUE*/
000519          if( e<342 ){                                    /*OPTIMIZATION-IF-TRUE*/
000520            LONGDOUBLE_TYPE scale = sqlite3Pow10(e-308);
000521            if( esign<0 ){
000522              result = s / scale;
000523              result /= 1.0e+308;
000524            }else{
000525              result = s * scale;
000526              result *= 1.0e+308;
000527            }
000528          }else{ assert( e>=342 );
000529            if( esign<0 ){
000530              result = 0.0*s;
000531            }else{
000532  #ifdef INFINITY
000533              result = INFINITY*s;
000534  #else
000535              result = 1e308*1e308*s;  /* Infinity */
000536  #endif
000537            }
000538          }
000539        }else{
000540          LONGDOUBLE_TYPE scale = sqlite3Pow10(e);
000541          if( esign<0 ){
000542            result = s / scale;
000543          }else{
000544            result = s * scale;
000545          }
000546        }
000547      }
000548    }
000549  
000550    /* store the result */
000551    *pResult = result;
000552  
000553    /* return true if number and no extra non-whitespace chracters after */
000554    return z==zEnd && nDigits>0 && eValid && nonNum==0;
000555  #else
000556    return !sqlite3Atoi64(z, pResult, length, enc);
000557  #endif /* SQLITE_OMIT_FLOATING_POINT */
000558  }
000559  
000560  /*
000561  ** Compare the 19-character string zNum against the text representation
000562  ** value 2^63:  9223372036854775808.  Return negative, zero, or positive
000563  ** if zNum is less than, equal to, or greater than the string.
000564  ** Note that zNum must contain exactly 19 characters.
000565  **
000566  ** Unlike memcmp() this routine is guaranteed to return the difference
000567  ** in the values of the last digit if the only difference is in the
000568  ** last digit.  So, for example,
000569  **
000570  **      compare2pow63("9223372036854775800", 1)
000571  **
000572  ** will return -8.
000573  */
000574  static int compare2pow63(const char *zNum, int incr){
000575    int c = 0;
000576    int i;
000577                      /* 012345678901234567 */
000578    const char *pow63 = "922337203685477580";
000579    for(i=0; c==0 && i<18; i++){
000580      c = (zNum[i*incr]-pow63[i])*10;
000581    }
000582    if( c==0 ){
000583      c = zNum[18*incr] - '8';
000584      testcase( c==(-1) );
000585      testcase( c==0 );
000586      testcase( c==(+1) );
000587    }
000588    return c;
000589  }
000590  
000591  /*
000592  ** Convert zNum to a 64-bit signed integer.  zNum must be decimal. This
000593  ** routine does *not* accept hexadecimal notation.
000594  **
000595  ** Returns:
000596  **
000597  **     0    Successful transformation.  Fits in a 64-bit signed integer.
000598  **     1    Excess non-space text after the integer value
000599  **     2    Integer too large for a 64-bit signed integer or is malformed
000600  **     3    Special case of 9223372036854775808
000601  **
000602  ** length is the number of bytes in the string (bytes, not characters).
000603  ** The string is not necessarily zero-terminated.  The encoding is
000604  ** given by enc.
000605  */
000606  int sqlite3Atoi64(const char *zNum, i64 *pNum, int length, u8 enc){
000607    int incr;
000608    u64 u = 0;
000609    int neg = 0; /* assume positive */
000610    int i;
000611    int c = 0;
000612    int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
000613    int rc;          /* Baseline return code */
000614    const char *zStart;
000615    const char *zEnd = zNum + length;
000616    assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
000617    if( enc==SQLITE_UTF8 ){
000618      incr = 1;
000619    }else{
000620      incr = 2;
000621      assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
000622      for(i=3-enc; i<length && zNum[i]==0; i+=2){}
000623      nonNum = i<length;
000624      zEnd = &zNum[i^1];
000625      zNum += (enc&1);
000626    }
000627    while( zNum<zEnd && sqlite3Isspace(*zNum) ) zNum+=incr;
000628    if( zNum<zEnd ){
000629      if( *zNum=='-' ){
000630        neg = 1;
000631        zNum+=incr;
000632      }else if( *zNum=='+' ){
000633        zNum+=incr;
000634      }
000635    }
000636    zStart = zNum;
000637    while( zNum<zEnd && zNum[0]=='0' ){ zNum+=incr; } /* Skip leading zeros. */
000638    for(i=0; &zNum[i]<zEnd && (c=zNum[i])>='0' && c<='9'; i+=incr){
000639      u = u*10 + c - '0';
000640    }
000641    testcase( i==18*incr );
000642    testcase( i==19*incr );
000643    testcase( i==20*incr );
000644    if( u>LARGEST_INT64 ){
000645      /* This test and assignment is needed only to suppress UB warnings
000646      ** from clang and -fsanitize=undefined.  This test and assignment make
000647      ** the code a little larger and slower, and no harm comes from omitting
000648      ** them, but we must appaise the undefined-behavior pharisees. */
000649      *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
000650    }else if( neg ){
000651      *pNum = -(i64)u;
000652    }else{
000653      *pNum = (i64)u;
000654    }
000655    rc = 0;
000656    if( (i==0 && zStart==zNum)     /* No digits */
000657     || nonNum                     /* UTF16 with high-order bytes non-zero */
000658    ){
000659      rc = 1;
000660    }else if( &zNum[i]<zEnd ){     /* Extra bytes at the end */
000661      int jj = i;
000662      do{
000663        if( !sqlite3Isspace(zNum[jj]) ){
000664          rc = 1;          /* Extra non-space text after the integer */
000665          break;
000666        }
000667        jj += incr;
000668      }while( &zNum[jj]<zEnd );
000669    }
000670    if( i<19*incr ){
000671      /* Less than 19 digits, so we know that it fits in 64 bits */
000672      assert( u<=LARGEST_INT64 );
000673      return rc;
000674    }else{
000675      /* zNum is a 19-digit numbers.  Compare it against 9223372036854775808. */
000676      c = i>19*incr ? 1 : compare2pow63(zNum, incr);
000677      if( c<0 ){
000678        /* zNum is less than 9223372036854775808 so it fits */
000679        assert( u<=LARGEST_INT64 );
000680        return rc;
000681      }else{
000682        *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
000683        if( c>0 ){
000684          /* zNum is greater than 9223372036854775808 so it overflows */
000685          return 2;
000686        }else{
000687          /* zNum is exactly 9223372036854775808.  Fits if negative.  The
000688          ** special case 2 overflow if positive */
000689          assert( u-1==LARGEST_INT64 );
000690          return neg ? rc : 3;
000691        }
000692      }
000693    }
000694  }
000695  
000696  /*
000697  ** Transform a UTF-8 integer literal, in either decimal or hexadecimal,
000698  ** into a 64-bit signed integer.  This routine accepts hexadecimal literals,
000699  ** whereas sqlite3Atoi64() does not.
000700  **
000701  ** Returns:
000702  **
000703  **     0    Successful transformation.  Fits in a 64-bit signed integer.
000704  **     1    Excess text after the integer value
000705  **     2    Integer too large for a 64-bit signed integer or is malformed
000706  **     3    Special case of 9223372036854775808
000707  */
000708  int sqlite3DecOrHexToI64(const char *z, i64 *pOut){
000709  #ifndef SQLITE_OMIT_HEX_INTEGER
000710    if( z[0]=='0'
000711     && (z[1]=='x' || z[1]=='X')
000712    ){
000713      u64 u = 0;
000714      int i, k;
000715      for(i=2; z[i]=='0'; i++){}
000716      for(k=i; sqlite3Isxdigit(z[k]); k++){
000717        u = u*16 + sqlite3HexToInt(z[k]);
000718      }
000719      memcpy(pOut, &u, 8);
000720      return (z[k]==0 && k-i<=16) ? 0 : 2;
000721    }else
000722  #endif /* SQLITE_OMIT_HEX_INTEGER */
000723    {
000724      return sqlite3Atoi64(z, pOut, sqlite3Strlen30(z), SQLITE_UTF8);
000725    }
000726  }
000727  
000728  /*
000729  ** If zNum represents an integer that will fit in 32-bits, then set
000730  ** *pValue to that integer and return true.  Otherwise return false.
000731  **
000732  ** This routine accepts both decimal and hexadecimal notation for integers.
000733  **
000734  ** Any non-numeric characters that following zNum are ignored.
000735  ** This is different from sqlite3Atoi64() which requires the
000736  ** input number to be zero-terminated.
000737  */
000738  int sqlite3GetInt32(const char *zNum, int *pValue){
000739    sqlite_int64 v = 0;
000740    int i, c;
000741    int neg = 0;
000742    if( zNum[0]=='-' ){
000743      neg = 1;
000744      zNum++;
000745    }else if( zNum[0]=='+' ){
000746      zNum++;
000747    }
000748  #ifndef SQLITE_OMIT_HEX_INTEGER
000749    else if( zNum[0]=='0'
000750          && (zNum[1]=='x' || zNum[1]=='X')
000751          && sqlite3Isxdigit(zNum[2])
000752    ){
000753      u32 u = 0;
000754      zNum += 2;
000755      while( zNum[0]=='0' ) zNum++;
000756      for(i=0; sqlite3Isxdigit(zNum[i]) && i<8; i++){
000757        u = u*16 + sqlite3HexToInt(zNum[i]);
000758      }
000759      if( (u&0x80000000)==0 && sqlite3Isxdigit(zNum[i])==0 ){
000760        memcpy(pValue, &u, 4);
000761        return 1;
000762      }else{
000763        return 0;
000764      }
000765    }
000766  #endif
000767    if( !sqlite3Isdigit(zNum[0]) ) return 0;
000768    while( zNum[0]=='0' ) zNum++;
000769    for(i=0; i<11 && (c = zNum[i] - '0')>=0 && c<=9; i++){
000770      v = v*10 + c;
000771    }
000772  
000773    /* The longest decimal representation of a 32 bit integer is 10 digits:
000774    **
000775    **             1234567890
000776    **     2^31 -> 2147483648
000777    */
000778    testcase( i==10 );
000779    if( i>10 ){
000780      return 0;
000781    }
000782    testcase( v-neg==2147483647 );
000783    if( v-neg>2147483647 ){
000784      return 0;
000785    }
000786    if( neg ){
000787      v = -v;
000788    }
000789    *pValue = (int)v;
000790    return 1;
000791  }
000792  
000793  /*
000794  ** Return a 32-bit integer value extracted from a string.  If the
000795  ** string is not an integer, just return 0.
000796  */
000797  int sqlite3Atoi(const char *z){
000798    int x = 0;
000799    if( z ) sqlite3GetInt32(z, &x);
000800    return x;
000801  }
000802  
000803  /*
000804  ** The variable-length integer encoding is as follows:
000805  **
000806  ** KEY:
000807  **         A = 0xxxxxxx    7 bits of data and one flag bit
000808  **         B = 1xxxxxxx    7 bits of data and one flag bit
000809  **         C = xxxxxxxx    8 bits of data
000810  **
000811  **  7 bits - A
000812  ** 14 bits - BA
000813  ** 21 bits - BBA
000814  ** 28 bits - BBBA
000815  ** 35 bits - BBBBA
000816  ** 42 bits - BBBBBA
000817  ** 49 bits - BBBBBBA
000818  ** 56 bits - BBBBBBBA
000819  ** 64 bits - BBBBBBBBC
000820  */
000821  
000822  /*
000823  ** Write a 64-bit variable-length integer to memory starting at p[0].
000824  ** The length of data write will be between 1 and 9 bytes.  The number
000825  ** of bytes written is returned.
000826  **
000827  ** A variable-length integer consists of the lower 7 bits of each byte
000828  ** for all bytes that have the 8th bit set and one byte with the 8th
000829  ** bit clear.  Except, if we get to the 9th byte, it stores the full
000830  ** 8 bits and is the last byte.
000831  */
000832  static int SQLITE_NOINLINE putVarint64(unsigned char *p, u64 v){
000833    int i, j, n;
000834    u8 buf[10];
000835    if( v & (((u64)0xff000000)<<32) ){
000836      p[8] = (u8)v;
000837      v >>= 8;
000838      for(i=7; i>=0; i--){
000839        p[i] = (u8)((v & 0x7f) | 0x80);
000840        v >>= 7;
000841      }
000842      return 9;
000843    }    
000844    n = 0;
000845    do{
000846      buf[n++] = (u8)((v & 0x7f) | 0x80);
000847      v >>= 7;
000848    }while( v!=0 );
000849    buf[0] &= 0x7f;
000850    assert( n<=9 );
000851    for(i=0, j=n-1; j>=0; j--, i++){
000852      p[i] = buf[j];
000853    }
000854    return n;
000855  }
000856  int sqlite3PutVarint(unsigned char *p, u64 v){
000857    if( v<=0x7f ){
000858      p[0] = v&0x7f;
000859      return 1;
000860    }
000861    if( v<=0x3fff ){
000862      p[0] = ((v>>7)&0x7f)|0x80;
000863      p[1] = v&0x7f;
000864      return 2;
000865    }
000866    return putVarint64(p,v);
000867  }
000868  
000869  /*
000870  ** Bitmasks used by sqlite3GetVarint().  These precomputed constants
000871  ** are defined here rather than simply putting the constant expressions
000872  ** inline in order to work around bugs in the RVT compiler.
000873  **
000874  ** SLOT_2_0     A mask for  (0x7f<<14) | 0x7f
000875  **
000876  ** SLOT_4_2_0   A mask for  (0x7f<<28) | SLOT_2_0
000877  */
000878  #define SLOT_2_0     0x001fc07f
000879  #define SLOT_4_2_0   0xf01fc07f
000880  
000881  
000882  /*
000883  ** Read a 64-bit variable-length integer from memory starting at p[0].
000884  ** Return the number of bytes read.  The value is stored in *v.
000885  */
000886  u8 sqlite3GetVarint(const unsigned char *p, u64 *v){
000887    u32 a,b,s;
000888  
000889    a = *p;
000890    /* a: p0 (unmasked) */
000891    if (!(a&0x80))
000892    {
000893      *v = a;
000894      return 1;
000895    }
000896  
000897    p++;
000898    b = *p;
000899    /* b: p1 (unmasked) */
000900    if (!(b&0x80))
000901    {
000902      a &= 0x7f;
000903      a = a<<7;
000904      a |= b;
000905      *v = a;
000906      return 2;
000907    }
000908  
000909    /* Verify that constants are precomputed correctly */
000910    assert( SLOT_2_0 == ((0x7f<<14) | (0x7f)) );
000911    assert( SLOT_4_2_0 == ((0xfU<<28) | (0x7f<<14) | (0x7f)) );
000912  
000913    p++;
000914    a = a<<14;
000915    a |= *p;
000916    /* a: p0<<14 | p2 (unmasked) */
000917    if (!(a&0x80))
000918    {
000919      a &= SLOT_2_0;
000920      b &= 0x7f;
000921      b = b<<7;
000922      a |= b;
000923      *v = a;
000924      return 3;
000925    }
000926  
000927    /* CSE1 from below */
000928    a &= SLOT_2_0;
000929    p++;
000930    b = b<<14;
000931    b |= *p;
000932    /* b: p1<<14 | p3 (unmasked) */
000933    if (!(b&0x80))
000934    {
000935      b &= SLOT_2_0;
000936      /* moved CSE1 up */
000937      /* a &= (0x7f<<14)|(0x7f); */
000938      a = a<<7;
000939      a |= b;
000940      *v = a;
000941      return 4;
000942    }
000943  
000944    /* a: p0<<14 | p2 (masked) */
000945    /* b: p1<<14 | p3 (unmasked) */
000946    /* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
000947    /* moved CSE1 up */
000948    /* a &= (0x7f<<14)|(0x7f); */
000949    b &= SLOT_2_0;
000950    s = a;
000951    /* s: p0<<14 | p2 (masked) */
000952  
000953    p++;
000954    a = a<<14;
000955    a |= *p;
000956    /* a: p0<<28 | p2<<14 | p4 (unmasked) */
000957    if (!(a&0x80))
000958    {
000959      /* we can skip these cause they were (effectively) done above
000960      ** while calculating s */
000961      /* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
000962      /* b &= (0x7f<<14)|(0x7f); */
000963      b = b<<7;
000964      a |= b;
000965      s = s>>18;
000966      *v = ((u64)s)<<32 | a;
000967      return 5;
000968    }
000969  
000970    /* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
000971    s = s<<7;
000972    s |= b;
000973    /* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
000974  
000975    p++;
000976    b = b<<14;
000977    b |= *p;
000978    /* b: p1<<28 | p3<<14 | p5 (unmasked) */
000979    if (!(b&0x80))
000980    {
000981      /* we can skip this cause it was (effectively) done above in calc'ing s */
000982      /* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
000983      a &= SLOT_2_0;
000984      a = a<<7;
000985      a |= b;
000986      s = s>>18;
000987      *v = ((u64)s)<<32 | a;
000988      return 6;
000989    }
000990  
000991    p++;
000992    a = a<<14;
000993    a |= *p;
000994    /* a: p2<<28 | p4<<14 | p6 (unmasked) */
000995    if (!(a&0x80))
000996    {
000997      a &= SLOT_4_2_0;
000998      b &= SLOT_2_0;
000999      b = b<<7;
001000      a |= b;
001001      s = s>>11;
001002      *v = ((u64)s)<<32 | a;
001003      return 7;
001004    }
001005  
001006    /* CSE2 from below */
001007    a &= SLOT_2_0;
001008    p++;
001009    b = b<<14;
001010    b |= *p;
001011    /* b: p3<<28 | p5<<14 | p7 (unmasked) */
001012    if (!(b&0x80))
001013    {
001014      b &= SLOT_4_2_0;
001015      /* moved CSE2 up */
001016      /* a &= (0x7f<<14)|(0x7f); */
001017      a = a<<7;
001018      a |= b;
001019      s = s>>4;
001020      *v = ((u64)s)<<32 | a;
001021      return 8;
001022    }
001023  
001024    p++;
001025    a = a<<15;
001026    a |= *p;
001027    /* a: p4<<29 | p6<<15 | p8 (unmasked) */
001028  
001029    /* moved CSE2 up */
001030    /* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
001031    b &= SLOT_2_0;
001032    b = b<<8;
001033    a |= b;
001034  
001035    s = s<<4;
001036    b = p[-4];
001037    b &= 0x7f;
001038    b = b>>3;
001039    s |= b;
001040  
001041    *v = ((u64)s)<<32 | a;
001042  
001043    return 9;
001044  }
001045  
001046  /*
001047  ** Read a 32-bit variable-length integer from memory starting at p[0].
001048  ** Return the number of bytes read.  The value is stored in *v.
001049  **
001050  ** If the varint stored in p[0] is larger than can fit in a 32-bit unsigned
001051  ** integer, then set *v to 0xffffffff.
001052  **
001053  ** A MACRO version, getVarint32, is provided which inlines the 
001054  ** single-byte case.  All code should use the MACRO version as 
001055  ** this function assumes the single-byte case has already been handled.
001056  */
001057  u8 sqlite3GetVarint32(const unsigned char *p, u32 *v){
001058    u32 a,b;
001059  
001060    /* The 1-byte case.  Overwhelmingly the most common.  Handled inline
001061    ** by the getVarin32() macro */
001062    a = *p;
001063    /* a: p0 (unmasked) */
001064  #ifndef getVarint32
001065    if (!(a&0x80))
001066    {
001067      /* Values between 0 and 127 */
001068      *v = a;
001069      return 1;
001070    }
001071  #endif
001072  
001073    /* The 2-byte case */
001074    p++;
001075    b = *p;
001076    /* b: p1 (unmasked) */
001077    if (!(b&0x80))
001078    {
001079      /* Values between 128 and 16383 */
001080      a &= 0x7f;
001081      a = a<<7;
001082      *v = a | b;
001083      return 2;
001084    }
001085  
001086    /* The 3-byte case */
001087    p++;
001088    a = a<<14;
001089    a |= *p;
001090    /* a: p0<<14 | p2 (unmasked) */
001091    if (!(a&0x80))
001092    {
001093      /* Values between 16384 and 2097151 */
001094      a &= (0x7f<<14)|(0x7f);
001095      b &= 0x7f;
001096      b = b<<7;
001097      *v = a | b;
001098      return 3;
001099    }
001100  
001101    /* A 32-bit varint is used to store size information in btrees.
001102    ** Objects are rarely larger than 2MiB limit of a 3-byte varint.
001103    ** A 3-byte varint is sufficient, for example, to record the size
001104    ** of a 1048569-byte BLOB or string.
001105    **
001106    ** We only unroll the first 1-, 2-, and 3- byte cases.  The very
001107    ** rare larger cases can be handled by the slower 64-bit varint
001108    ** routine.
001109    */
001110  #if 1
001111    {
001112      u64 v64;
001113      u8 n;
001114  
001115      p -= 2;
001116      n = sqlite3GetVarint(p, &v64);
001117      assert( n>3 && n<=9 );
001118      if( (v64 & SQLITE_MAX_U32)!=v64 ){
001119        *v = 0xffffffff;
001120      }else{
001121        *v = (u32)v64;
001122      }
001123      return n;
001124    }
001125  
001126  #else
001127    /* For following code (kept for historical record only) shows an
001128    ** unrolling for the 3- and 4-byte varint cases.  This code is
001129    ** slightly faster, but it is also larger and much harder to test.
001130    */
001131    p++;
001132    b = b<<14;
001133    b |= *p;
001134    /* b: p1<<14 | p3 (unmasked) */
001135    if (!(b&0x80))
001136    {
001137      /* Values between 2097152 and 268435455 */
001138      b &= (0x7f<<14)|(0x7f);
001139      a &= (0x7f<<14)|(0x7f);
001140      a = a<<7;
001141      *v = a | b;
001142      return 4;
001143    }
001144  
001145    p++;
001146    a = a<<14;
001147    a |= *p;
001148    /* a: p0<<28 | p2<<14 | p4 (unmasked) */
001149    if (!(a&0x80))
001150    {
001151      /* Values  between 268435456 and 34359738367 */
001152      a &= SLOT_4_2_0;
001153      b &= SLOT_4_2_0;
001154      b = b<<7;
001155      *v = a | b;
001156      return 5;
001157    }
001158  
001159    /* We can only reach this point when reading a corrupt database
001160    ** file.  In that case we are not in any hurry.  Use the (relatively
001161    ** slow) general-purpose sqlite3GetVarint() routine to extract the
001162    ** value. */
001163    {
001164      u64 v64;
001165      u8 n;
001166  
001167      p -= 4;
001168      n = sqlite3GetVarint(p, &v64);
001169      assert( n>5 && n<=9 );
001170      *v = (u32)v64;
001171      return n;
001172    }
001173  #endif
001174  }
001175  
001176  /*
001177  ** Return the number of bytes that will be needed to store the given
001178  ** 64-bit integer.
001179  */
001180  int sqlite3VarintLen(u64 v){
001181    int i;
001182    for(i=1; (v >>= 7)!=0; i++){ assert( i<10 ); }
001183    return i;
001184  }
001185  
001186  
001187  /*
001188  ** Read or write a four-byte big-endian integer value.
001189  */
001190  u32 sqlite3Get4byte(const u8 *p){
001191  #if SQLITE_BYTEORDER==4321
001192    u32 x;
001193    memcpy(&x,p,4);
001194    return x;
001195  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
001196    u32 x;
001197    memcpy(&x,p,4);
001198    return __builtin_bswap32(x);
001199  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
001200    u32 x;
001201    memcpy(&x,p,4);
001202    return _byteswap_ulong(x);
001203  #else
001204    testcase( p[0]&0x80 );
001205    return ((unsigned)p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
001206  #endif
001207  }
001208  void sqlite3Put4byte(unsigned char *p, u32 v){
001209  #if SQLITE_BYTEORDER==4321
001210    memcpy(p,&v,4);
001211  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
001212    u32 x = __builtin_bswap32(v);
001213    memcpy(p,&x,4);
001214  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
001215    u32 x = _byteswap_ulong(v);
001216    memcpy(p,&x,4);
001217  #else
001218    p[0] = (u8)(v>>24);
001219    p[1] = (u8)(v>>16);
001220    p[2] = (u8)(v>>8);
001221    p[3] = (u8)v;
001222  #endif
001223  }
001224  
001225  
001226  
001227  /*
001228  ** Translate a single byte of Hex into an integer.
001229  ** This routine only works if h really is a valid hexadecimal
001230  ** character:  0..9a..fA..F
001231  */
001232  u8 sqlite3HexToInt(int h){
001233    assert( (h>='0' && h<='9') ||  (h>='a' && h<='f') ||  (h>='A' && h<='F') );
001234  #ifdef SQLITE_ASCII
001235    h += 9*(1&(h>>6));
001236  #endif
001237  #ifdef SQLITE_EBCDIC
001238    h += 9*(1&~(h>>4));
001239  #endif
001240    return (u8)(h & 0xf);
001241  }
001242  
001243  #if !defined(SQLITE_OMIT_BLOB_LITERAL) || defined(SQLITE_HAS_CODEC)
001244  /*
001245  ** Convert a BLOB literal of the form "x'hhhhhh'" into its binary
001246  ** value.  Return a pointer to its binary value.  Space to hold the
001247  ** binary value has been obtained from malloc and must be freed by
001248  ** the calling routine.
001249  */
001250  void *sqlite3HexToBlob(sqlite3 *db, const char *z, int n){
001251    char *zBlob;
001252    int i;
001253  
001254    zBlob = (char *)sqlite3DbMallocRawNN(db, n/2 + 1);
001255    n--;
001256    if( zBlob ){
001257      for(i=0; i<n; i+=2){
001258        zBlob[i/2] = (sqlite3HexToInt(z[i])<<4) | sqlite3HexToInt(z[i+1]);
001259      }
001260      zBlob[i/2] = 0;
001261    }
001262    return zBlob;
001263  }
001264  #endif /* !SQLITE_OMIT_BLOB_LITERAL || SQLITE_HAS_CODEC */
001265  
001266  /*
001267  ** Log an error that is an API call on a connection pointer that should
001268  ** not have been used.  The "type" of connection pointer is given as the
001269  ** argument.  The zType is a word like "NULL" or "closed" or "invalid".
001270  */
001271  static void logBadConnection(const char *zType){
001272    sqlite3_log(SQLITE_MISUSE, 
001273       "API call with %s database connection pointer",
001274       zType
001275    );
001276  }
001277  
001278  /*
001279  ** Check to make sure we have a valid db pointer.  This test is not
001280  ** foolproof but it does provide some measure of protection against
001281  ** misuse of the interface such as passing in db pointers that are
001282  ** NULL or which have been previously closed.  If this routine returns
001283  ** 1 it means that the db pointer is valid and 0 if it should not be
001284  ** dereferenced for any reason.  The calling function should invoke
001285  ** SQLITE_MISUSE immediately.
001286  **
001287  ** sqlite3SafetyCheckOk() requires that the db pointer be valid for
001288  ** use.  sqlite3SafetyCheckSickOrOk() allows a db pointer that failed to
001289  ** open properly and is not fit for general use but which can be
001290  ** used as an argument to sqlite3_errmsg() or sqlite3_close().
001291  */
001292  int sqlite3SafetyCheckOk(sqlite3 *db){
001293    u32 magic;
001294    if( db==0 ){
001295      logBadConnection("NULL");
001296      return 0;
001297    }
001298    magic = db->magic;
001299    if( magic!=SQLITE_MAGIC_OPEN ){
001300      if( sqlite3SafetyCheckSickOrOk(db) ){
001301        testcase( sqlite3GlobalConfig.xLog!=0 );
001302        logBadConnection("unopened");
001303      }
001304      return 0;
001305    }else{
001306      return 1;
001307    }
001308  }
001309  int sqlite3SafetyCheckSickOrOk(sqlite3 *db){
001310    u32 magic;
001311    magic = db->magic;
001312    if( magic!=SQLITE_MAGIC_SICK &&
001313        magic!=SQLITE_MAGIC_OPEN &&
001314        magic!=SQLITE_MAGIC_BUSY ){
001315      testcase( sqlite3GlobalConfig.xLog!=0 );
001316      logBadConnection("invalid");
001317      return 0;
001318    }else{
001319      return 1;
001320    }
001321  }
001322  
001323  /*
001324  ** Attempt to add, substract, or multiply the 64-bit signed value iB against
001325  ** the other 64-bit signed integer at *pA and store the result in *pA.
001326  ** Return 0 on success.  Or if the operation would have resulted in an
001327  ** overflow, leave *pA unchanged and return 1.
001328  */
001329  int sqlite3AddInt64(i64 *pA, i64 iB){
001330  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001331    return __builtin_add_overflow(*pA, iB, pA);
001332  #else
001333    i64 iA = *pA;
001334    testcase( iA==0 ); testcase( iA==1 );
001335    testcase( iB==-1 ); testcase( iB==0 );
001336    if( iB>=0 ){
001337      testcase( iA>0 && LARGEST_INT64 - iA == iB );
001338      testcase( iA>0 && LARGEST_INT64 - iA == iB - 1 );
001339      if( iA>0 && LARGEST_INT64 - iA < iB ) return 1;
001340    }else{
001341      testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 1 );
001342      testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 2 );
001343      if( iA<0 && -(iA + LARGEST_INT64) > iB + 1 ) return 1;
001344    }
001345    *pA += iB;
001346    return 0; 
001347  #endif
001348  }
001349  int sqlite3SubInt64(i64 *pA, i64 iB){
001350  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001351    return __builtin_sub_overflow(*pA, iB, pA);
001352  #else
001353    testcase( iB==SMALLEST_INT64+1 );
001354    if( iB==SMALLEST_INT64 ){
001355      testcase( (*pA)==(-1) ); testcase( (*pA)==0 );
001356      if( (*pA)>=0 ) return 1;
001357      *pA -= iB;
001358      return 0;
001359    }else{
001360      return sqlite3AddInt64(pA, -iB);
001361    }
001362  #endif
001363  }
001364  int sqlite3MulInt64(i64 *pA, i64 iB){
001365  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001366    return __builtin_mul_overflow(*pA, iB, pA);
001367  #else
001368    i64 iA = *pA;
001369    if( iB>0 ){
001370      if( iA>LARGEST_INT64/iB ) return 1;
001371      if( iA<SMALLEST_INT64/iB ) return 1;
001372    }else if( iB<0 ){
001373      if( iA>0 ){
001374        if( iB<SMALLEST_INT64/iA ) return 1;
001375      }else if( iA<0 ){
001376        if( iB==SMALLEST_INT64 ) return 1;
001377        if( iA==SMALLEST_INT64 ) return 1;
001378        if( -iA>LARGEST_INT64/-iB ) return 1;
001379      }
001380    }
001381    *pA = iA*iB;
001382    return 0;
001383  #endif
001384  }
001385  
001386  /*
001387  ** Compute the absolute value of a 32-bit signed integer, of possible.  Or 
001388  ** if the integer has a value of -2147483648, return +2147483647
001389  */
001390  int sqlite3AbsInt32(int x){
001391    if( x>=0 ) return x;
001392    if( x==(int)0x80000000 ) return 0x7fffffff;
001393    return -x;
001394  }
001395  
001396  #ifdef SQLITE_ENABLE_8_3_NAMES
001397  /*
001398  ** If SQLITE_ENABLE_8_3_NAMES is set at compile-time and if the database
001399  ** filename in zBaseFilename is a URI with the "8_3_names=1" parameter and
001400  ** if filename in z[] has a suffix (a.k.a. "extension") that is longer than
001401  ** three characters, then shorten the suffix on z[] to be the last three
001402  ** characters of the original suffix.
001403  **
001404  ** If SQLITE_ENABLE_8_3_NAMES is set to 2 at compile-time, then always
001405  ** do the suffix shortening regardless of URI parameter.
001406  **
001407  ** Examples:
001408  **
001409  **     test.db-journal    =>   test.nal
001410  **     test.db-wal        =>   test.wal
001411  **     test.db-shm        =>   test.shm
001412  **     test.db-mj7f3319fa =>   test.9fa
001413  */
001414  void sqlite3FileSuffix3(const char *zBaseFilename, char *z){
001415  #if SQLITE_ENABLE_8_3_NAMES<2
001416    if( sqlite3_uri_boolean(zBaseFilename, "8_3_names", 0) )
001417  #endif
001418    {
001419      int i, sz;
001420      sz = sqlite3Strlen30(z);
001421      for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
001422      if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
001423    }
001424  }
001425  #endif
001426  
001427  /* 
001428  ** Find (an approximate) sum of two LogEst values.  This computation is
001429  ** not a simple "+" operator because LogEst is stored as a logarithmic
001430  ** value.
001431  ** 
001432  */
001433  LogEst sqlite3LogEstAdd(LogEst a, LogEst b){
001434    static const unsigned char x[] = {
001435       10, 10,                         /* 0,1 */
001436        9, 9,                          /* 2,3 */
001437        8, 8,                          /* 4,5 */
001438        7, 7, 7,                       /* 6,7,8 */
001439        6, 6, 6,                       /* 9,10,11 */
001440        5, 5, 5,                       /* 12-14 */
001441        4, 4, 4, 4,                    /* 15-18 */
001442        3, 3, 3, 3, 3, 3,              /* 19-24 */
001443        2, 2, 2, 2, 2, 2, 2,           /* 25-31 */
001444    };
001445    if( a>=b ){
001446      if( a>b+49 ) return a;
001447      if( a>b+31 ) return a+1;
001448      return a+x[a-b];
001449    }else{
001450      if( b>a+49 ) return b;
001451      if( b>a+31 ) return b+1;
001452      return b+x[b-a];
001453    }
001454  }
001455  
001456  /*
001457  ** Convert an integer into a LogEst.  In other words, compute an
001458  ** approximation for 10*log2(x).
001459  */
001460  LogEst sqlite3LogEst(u64 x){
001461    static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
001462    LogEst y = 40;
001463    if( x<8 ){
001464      if( x<2 ) return 0;
001465      while( x<8 ){  y -= 10; x <<= 1; }
001466    }else{
001467  #if GCC_VERSION>=5004000
001468      int i = 60 - __builtin_clzll(x);
001469      y += i*10;
001470      x >>= i;
001471  #else
001472      while( x>255 ){ y += 40; x >>= 4; }  /*OPTIMIZATION-IF-TRUE*/
001473      while( x>15 ){  y += 10; x >>= 1; }
001474  #endif
001475    }
001476    return a[x&7] + y - 10;
001477  }
001478  
001479  #ifndef SQLITE_OMIT_VIRTUALTABLE
001480  /*
001481  ** Convert a double into a LogEst
001482  ** In other words, compute an approximation for 10*log2(x).
001483  */
001484  LogEst sqlite3LogEstFromDouble(double x){
001485    u64 a;
001486    LogEst e;
001487    assert( sizeof(x)==8 && sizeof(a)==8 );
001488    if( x<=1 ) return 0;
001489    if( x<=2000000000 ) return sqlite3LogEst((u64)x);
001490    memcpy(&a, &x, 8);
001491    e = (a>>52) - 1022;
001492    return e*10;
001493  }
001494  #endif /* SQLITE_OMIT_VIRTUALTABLE */
001495  
001496  #if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \
001497      defined(SQLITE_ENABLE_STAT3_OR_STAT4) || \
001498      defined(SQLITE_EXPLAIN_ESTIMATED_ROWS)
001499  /*
001500  ** Convert a LogEst into an integer.
001501  **
001502  ** Note that this routine is only used when one or more of various
001503  ** non-standard compile-time options is enabled.
001504  */
001505  u64 sqlite3LogEstToInt(LogEst x){
001506    u64 n;
001507    n = x%10;
001508    x /= 10;
001509    if( n>=5 ) n -= 2;
001510    else if( n>=1 ) n -= 1;
001511  #if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \
001512      defined(SQLITE_EXPLAIN_ESTIMATED_ROWS)
001513    if( x>60 ) return (u64)LARGEST_INT64;
001514  #else
001515    /* If only SQLITE_ENABLE_STAT3_OR_STAT4 is on, then the largest input
001516    ** possible to this routine is 310, resulting in a maximum x of 31 */
001517    assert( x<=60 );
001518  #endif
001519    return x>=3 ? (n+8)<<(x-3) : (n+8)>>(3-x);
001520  }
001521  #endif /* defined SCANSTAT or STAT4 or ESTIMATED_ROWS */
001522  
001523  /*
001524  ** Add a new name/number pair to a VList.  This might require that the
001525  ** VList object be reallocated, so return the new VList.  If an OOM
001526  ** error occurs, the original VList returned and the
001527  ** db->mallocFailed flag is set.
001528  **
001529  ** A VList is really just an array of integers.  To destroy a VList,
001530  ** simply pass it to sqlite3DbFree().
001531  **
001532  ** The first integer is the number of integers allocated for the whole
001533  ** VList.  The second integer is the number of integers actually used.
001534  ** Each name/number pair is encoded by subsequent groups of 3 or more
001535  ** integers.
001536  **
001537  ** Each name/number pair starts with two integers which are the numeric
001538  ** value for the pair and the size of the name/number pair, respectively.
001539  ** The text name overlays one or more following integers.  The text name
001540  ** is always zero-terminated.
001541  **
001542  ** Conceptually:
001543  **
001544  **    struct VList {
001545  **      int nAlloc;   // Number of allocated slots 
001546  **      int nUsed;    // Number of used slots 
001547  **      struct VListEntry {
001548  **        int iValue;    // Value for this entry
001549  **        int nSlot;     // Slots used by this entry
001550  **        // ... variable name goes here
001551  **      } a[0];
001552  **    }
001553  **
001554  ** During code generation, pointers to the variable names within the
001555  ** VList are taken.  When that happens, nAlloc is set to zero as an 
001556  ** indication that the VList may never again be enlarged, since the
001557  ** accompanying realloc() would invalidate the pointers.
001558  */
001559  VList *sqlite3VListAdd(
001560    sqlite3 *db,           /* The database connection used for malloc() */
001561    VList *pIn,            /* The input VList.  Might be NULL */
001562    const char *zName,     /* Name of symbol to add */
001563    int nName,             /* Bytes of text in zName */
001564    int iVal               /* Value to associate with zName */
001565  ){
001566    int nInt;              /* number of sizeof(int) objects needed for zName */
001567    char *z;               /* Pointer to where zName will be stored */
001568    int i;                 /* Index in pIn[] where zName is stored */
001569  
001570    nInt = nName/4 + 3;
001571    assert( pIn==0 || pIn[0]>=3 );  /* Verify ok to add new elements */
001572    if( pIn==0 || pIn[1]+nInt > pIn[0] ){
001573      /* Enlarge the allocation */
001574      int nAlloc = (pIn ? pIn[0]*2 : 10) + nInt;
001575      VList *pOut = sqlite3DbRealloc(db, pIn, nAlloc*sizeof(int));
001576      if( pOut==0 ) return pIn;
001577      if( pIn==0 ) pOut[1] = 2;
001578      pIn = pOut;
001579      pIn[0] = nAlloc;
001580    }
001581    i = pIn[1];
001582    pIn[i] = iVal;
001583    pIn[i+1] = nInt;
001584    z = (char*)&pIn[i+2];
001585    pIn[1] = i+nInt;
001586    assert( pIn[1]<=pIn[0] );
001587    memcpy(z, zName, nName);
001588    z[nName] = 0;
001589    return pIn;
001590  }
001591  
001592  /*
001593  ** Return a pointer to the name of a variable in the given VList that
001594  ** has the value iVal.  Or return a NULL if there is no such variable in
001595  ** the list
001596  */
001597  const char *sqlite3VListNumToName(VList *pIn, int iVal){
001598    int i, mx;
001599    if( pIn==0 ) return 0;
001600    mx = pIn[1];
001601    i = 2;
001602    do{
001603      if( pIn[i]==iVal ) return (char*)&pIn[i+2];
001604      i += pIn[i+1];
001605    }while( i<mx );
001606    return 0;
001607  }
001608  
001609  /*
001610  ** Return the number of the variable named zName, if it is in VList.
001611  ** or return 0 if there is no such variable.
001612  */
001613  int sqlite3VListNameToNum(VList *pIn, const char *zName, int nName){
001614    int i, mx;
001615    if( pIn==0 ) return 0;
001616    mx = pIn[1];
001617    i = 2;
001618    do{
001619      const char *z = (const char*)&pIn[i+2];
001620      if( strncmp(z,zName,nName)==0 && z[nName]==0 ) return pIn[i];
001621      i += pIn[i+1];
001622    }while( i<mx );
001623    return 0;
001624  }