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  ** The string z[] is an text representation of a real number.
000325  ** Convert this string to a double and write it into *pResult.
000326  **
000327  ** The string z[] is length bytes in length (bytes, not characters) and
000328  ** uses the encoding enc.  The string is not necessarily zero-terminated.
000329  **
000330  ** Return TRUE if the result is a valid real number (or integer) and FALSE
000331  ** if the string is empty or contains extraneous text.  Valid numbers
000332  ** are in one of these formats:
000333  **
000334  **    [+-]digits[E[+-]digits]
000335  **    [+-]digits.[digits][E[+-]digits]
000336  **    [+-].digits[E[+-]digits]
000337  **
000338  ** Leading and trailing whitespace is ignored for the purpose of determining
000339  ** validity.
000340  **
000341  ** If some prefix of the input string is a valid number, this routine
000342  ** returns FALSE but it still converts the prefix and writes the result
000343  ** into *pResult.
000344  */
000345  int sqlite3AtoF(const char *z, double *pResult, int length, u8 enc){
000346  #ifndef SQLITE_OMIT_FLOATING_POINT
000347    int incr;
000348    const char *zEnd = z + length;
000349    /* sign * significand * (10 ^ (esign * exponent)) */
000350    int sign = 1;    /* sign of significand */
000351    i64 s = 0;       /* significand */
000352    int d = 0;       /* adjust exponent for shifting decimal point */
000353    int esign = 1;   /* sign of exponent */
000354    int e = 0;       /* exponent */
000355    int eValid = 1;  /* True exponent is either not used or is well-formed */
000356    double result;
000357    int nDigits = 0;
000358    int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
000359  
000360    assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
000361    *pResult = 0.0;   /* Default return value, in case of an error */
000362  
000363    if( enc==SQLITE_UTF8 ){
000364      incr = 1;
000365    }else{
000366      int i;
000367      incr = 2;
000368      assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
000369      for(i=3-enc; i<length && z[i]==0; i+=2){}
000370      nonNum = i<length;
000371      zEnd = &z[i^1];
000372      z += (enc&1);
000373    }
000374  
000375    /* skip leading spaces */
000376    while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
000377    if( z>=zEnd ) return 0;
000378  
000379    /* get sign of significand */
000380    if( *z=='-' ){
000381      sign = -1;
000382      z+=incr;
000383    }else if( *z=='+' ){
000384      z+=incr;
000385    }
000386  
000387    /* copy max significant digits to significand */
000388    while( z<zEnd && sqlite3Isdigit(*z) && s<((LARGEST_INT64-9)/10) ){
000389      s = s*10 + (*z - '0');
000390      z+=incr, nDigits++;
000391    }
000392  
000393    /* skip non-significant significand digits
000394    ** (increase exponent by d to shift decimal left) */
000395    while( z<zEnd && sqlite3Isdigit(*z) ) z+=incr, nDigits++, d++;
000396    if( z>=zEnd ) goto do_atof_calc;
000397  
000398    /* if decimal point is present */
000399    if( *z=='.' ){
000400      z+=incr;
000401      /* copy digits from after decimal to significand
000402      ** (decrease exponent by d to shift decimal right) */
000403      while( z<zEnd && sqlite3Isdigit(*z) ){
000404        if( s<((LARGEST_INT64-9)/10) ){
000405          s = s*10 + (*z - '0');
000406          d--;
000407        }
000408        z+=incr, nDigits++;
000409      }
000410    }
000411    if( z>=zEnd ) goto do_atof_calc;
000412  
000413    /* if exponent is present */
000414    if( *z=='e' || *z=='E' ){
000415      z+=incr;
000416      eValid = 0;
000417  
000418      /* This branch is needed to avoid a (harmless) buffer overread.  The 
000419      ** special comment alerts the mutation tester that the correct answer
000420      ** is obtained even if the branch is omitted */
000421      if( z>=zEnd ) goto do_atof_calc;              /*PREVENTS-HARMLESS-OVERREAD*/
000422  
000423      /* get sign of exponent */
000424      if( *z=='-' ){
000425        esign = -1;
000426        z+=incr;
000427      }else if( *z=='+' ){
000428        z+=incr;
000429      }
000430      /* copy digits to exponent */
000431      while( z<zEnd && sqlite3Isdigit(*z) ){
000432        e = e<10000 ? (e*10 + (*z - '0')) : 10000;
000433        z+=incr;
000434        eValid = 1;
000435      }
000436    }
000437  
000438    /* skip trailing spaces */
000439    while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
000440  
000441  do_atof_calc:
000442    /* adjust exponent by d, and update sign */
000443    e = (e*esign) + d;
000444    if( e<0 ) {
000445      esign = -1;
000446      e *= -1;
000447    } else {
000448      esign = 1;
000449    }
000450  
000451    if( s==0 ) {
000452      /* In the IEEE 754 standard, zero is signed. */
000453      result = sign<0 ? -(double)0 : (double)0;
000454    } else {
000455      /* Attempt to reduce exponent.
000456      **
000457      ** Branches that are not required for the correct answer but which only
000458      ** help to obtain the correct answer faster are marked with special
000459      ** comments, as a hint to the mutation tester.
000460      */
000461      while( e>0 ){                                       /*OPTIMIZATION-IF-TRUE*/
000462        if( esign>0 ){
000463          if( s>=(LARGEST_INT64/10) ) break;             /*OPTIMIZATION-IF-FALSE*/
000464          s *= 10;
000465        }else{
000466          if( s%10!=0 ) break;                           /*OPTIMIZATION-IF-FALSE*/
000467          s /= 10;
000468        }
000469        e--;
000470      }
000471  
000472      /* adjust the sign of significand */
000473      s = sign<0 ? -s : s;
000474  
000475      if( e==0 ){                                         /*OPTIMIZATION-IF-TRUE*/
000476        result = (double)s;
000477      }else{
000478        LONGDOUBLE_TYPE scale = 1.0;
000479        /* attempt to handle extremely small/large numbers better */
000480        if( e>307 ){                                      /*OPTIMIZATION-IF-TRUE*/
000481          if( e<342 ){                                    /*OPTIMIZATION-IF-TRUE*/
000482            while( e%308 ) { scale *= 1.0e+1; e -= 1; }
000483            if( esign<0 ){
000484              result = s / scale;
000485              result /= 1.0e+308;
000486            }else{
000487              result = s * scale;
000488              result *= 1.0e+308;
000489            }
000490          }else{ assert( e>=342 );
000491            if( esign<0 ){
000492              result = 0.0*s;
000493            }else{
000494  #ifdef INFINITY
000495              result = INFINITY*s;
000496  #else
000497              result = 1e308*1e308*s;  /* Infinity */
000498  #endif
000499            }
000500          }
000501        }else{
000502          /* 1.0e+22 is the largest power of 10 than can be 
000503          ** represented exactly. */
000504          while( e%22 ) { scale *= 1.0e+1; e -= 1; }
000505          while( e>0 ) { scale *= 1.0e+22; e -= 22; }
000506          if( esign<0 ){
000507            result = s / scale;
000508          }else{
000509            result = s * scale;
000510          }
000511        }
000512      }
000513    }
000514  
000515    /* store the result */
000516    *pResult = result;
000517  
000518    /* return true if number and no extra non-whitespace chracters after */
000519    return z==zEnd && nDigits>0 && eValid && nonNum==0;
000520  #else
000521    return !sqlite3Atoi64(z, pResult, length, enc);
000522  #endif /* SQLITE_OMIT_FLOATING_POINT */
000523  }
000524  
000525  /*
000526  ** Compare the 19-character string zNum against the text representation
000527  ** value 2^63:  9223372036854775808.  Return negative, zero, or positive
000528  ** if zNum is less than, equal to, or greater than the string.
000529  ** Note that zNum must contain exactly 19 characters.
000530  **
000531  ** Unlike memcmp() this routine is guaranteed to return the difference
000532  ** in the values of the last digit if the only difference is in the
000533  ** last digit.  So, for example,
000534  **
000535  **      compare2pow63("9223372036854775800", 1)
000536  **
000537  ** will return -8.
000538  */
000539  static int compare2pow63(const char *zNum, int incr){
000540    int c = 0;
000541    int i;
000542                      /* 012345678901234567 */
000543    const char *pow63 = "922337203685477580";
000544    for(i=0; c==0 && i<18; i++){
000545      c = (zNum[i*incr]-pow63[i])*10;
000546    }
000547    if( c==0 ){
000548      c = zNum[18*incr] - '8';
000549      testcase( c==(-1) );
000550      testcase( c==0 );
000551      testcase( c==(+1) );
000552    }
000553    return c;
000554  }
000555  
000556  /*
000557  ** Convert zNum to a 64-bit signed integer.  zNum must be decimal. This
000558  ** routine does *not* accept hexadecimal notation.
000559  **
000560  ** Returns:
000561  **
000562  **     0    Successful transformation.  Fits in a 64-bit signed integer.
000563  **     1    Excess text after the integer value
000564  **     2    Integer too large for a 64-bit signed integer or is malformed
000565  **     3    Special case of 9223372036854775808
000566  **
000567  ** length is the number of bytes in the string (bytes, not characters).
000568  ** The string is not necessarily zero-terminated.  The encoding is
000569  ** given by enc.
000570  */
000571  int sqlite3Atoi64(const char *zNum, i64 *pNum, int length, u8 enc){
000572    int incr;
000573    u64 u = 0;
000574    int neg = 0; /* assume positive */
000575    int i;
000576    int c = 0;
000577    int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
000578    int rc;          /* Baseline return code */
000579    const char *zStart;
000580    const char *zEnd = zNum + length;
000581    assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
000582    if( enc==SQLITE_UTF8 ){
000583      incr = 1;
000584    }else{
000585      incr = 2;
000586      assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
000587      for(i=3-enc; i<length && zNum[i]==0; i+=2){}
000588      nonNum = i<length;
000589      zEnd = &zNum[i^1];
000590      zNum += (enc&1);
000591    }
000592    while( zNum<zEnd && sqlite3Isspace(*zNum) ) zNum+=incr;
000593    if( zNum<zEnd ){
000594      if( *zNum=='-' ){
000595        neg = 1;
000596        zNum+=incr;
000597      }else if( *zNum=='+' ){
000598        zNum+=incr;
000599      }
000600    }
000601    zStart = zNum;
000602    while( zNum<zEnd && zNum[0]=='0' ){ zNum+=incr; } /* Skip leading zeros. */
000603    for(i=0; &zNum[i]<zEnd && (c=zNum[i])>='0' && c<='9'; i+=incr){
000604      u = u*10 + c - '0';
000605    }
000606    if( u>LARGEST_INT64 ){
000607      *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
000608    }else if( neg ){
000609      *pNum = -(i64)u;
000610    }else{
000611      *pNum = (i64)u;
000612    }
000613    testcase( i==18 );
000614    testcase( i==19 );
000615    testcase( i==20 );
000616    if( &zNum[i]<zEnd              /* Extra bytes at the end */
000617     || (i==0 && zStart==zNum)     /* No digits */
000618     || nonNum                     /* UTF16 with high-order bytes non-zero */
000619    ){
000620      rc = 1;
000621    }else{
000622      rc = 0;
000623    }
000624    if( i>19*incr ){                /* Too many digits */
000625      /* zNum is empty or contains non-numeric text or is longer
000626      ** than 19 digits (thus guaranteeing that it is too large) */
000627      return 2;
000628    }else if( i<19*incr ){
000629      /* Less than 19 digits, so we know that it fits in 64 bits */
000630      assert( u<=LARGEST_INT64 );
000631      return rc;
000632    }else{
000633      /* zNum is a 19-digit numbers.  Compare it against 9223372036854775808. */
000634      c = compare2pow63(zNum, incr);
000635      if( c<0 ){
000636        /* zNum is less than 9223372036854775808 so it fits */
000637        assert( u<=LARGEST_INT64 );
000638        return rc;
000639      }else if( c>0 ){
000640        /* zNum is greater than 9223372036854775808 so it overflows */
000641        return 2;
000642      }else{
000643        /* zNum is exactly 9223372036854775808.  Fits if negative.  The
000644        ** special case 2 overflow if positive */
000645        assert( u-1==LARGEST_INT64 );
000646        return neg ? rc : 3;
000647      }
000648    }
000649  }
000650  
000651  /*
000652  ** Transform a UTF-8 integer literal, in either decimal or hexadecimal,
000653  ** into a 64-bit signed integer.  This routine accepts hexadecimal literals,
000654  ** whereas sqlite3Atoi64() does not.
000655  **
000656  ** Returns:
000657  **
000658  **     0    Successful transformation.  Fits in a 64-bit signed integer.
000659  **     1    Excess text after the integer value
000660  **     2    Integer too large for a 64-bit signed integer or is malformed
000661  **     3    Special case of 9223372036854775808
000662  */
000663  int sqlite3DecOrHexToI64(const char *z, i64 *pOut){
000664  #ifndef SQLITE_OMIT_HEX_INTEGER
000665    if( z[0]=='0'
000666     && (z[1]=='x' || z[1]=='X')
000667    ){
000668      u64 u = 0;
000669      int i, k;
000670      for(i=2; z[i]=='0'; i++){}
000671      for(k=i; sqlite3Isxdigit(z[k]); k++){
000672        u = u*16 + sqlite3HexToInt(z[k]);
000673      }
000674      memcpy(pOut, &u, 8);
000675      return (z[k]==0 && k-i<=16) ? 0 : 2;
000676    }else
000677  #endif /* SQLITE_OMIT_HEX_INTEGER */
000678    {
000679      return sqlite3Atoi64(z, pOut, sqlite3Strlen30(z), SQLITE_UTF8);
000680    }
000681  }
000682  
000683  /*
000684  ** If zNum represents an integer that will fit in 32-bits, then set
000685  ** *pValue to that integer and return true.  Otherwise return false.
000686  **
000687  ** This routine accepts both decimal and hexadecimal notation for integers.
000688  **
000689  ** Any non-numeric characters that following zNum are ignored.
000690  ** This is different from sqlite3Atoi64() which requires the
000691  ** input number to be zero-terminated.
000692  */
000693  int sqlite3GetInt32(const char *zNum, int *pValue){
000694    sqlite_int64 v = 0;
000695    int i, c;
000696    int neg = 0;
000697    if( zNum[0]=='-' ){
000698      neg = 1;
000699      zNum++;
000700    }else if( zNum[0]=='+' ){
000701      zNum++;
000702    }
000703  #ifndef SQLITE_OMIT_HEX_INTEGER
000704    else if( zNum[0]=='0'
000705          && (zNum[1]=='x' || zNum[1]=='X')
000706          && sqlite3Isxdigit(zNum[2])
000707    ){
000708      u32 u = 0;
000709      zNum += 2;
000710      while( zNum[0]=='0' ) zNum++;
000711      for(i=0; sqlite3Isxdigit(zNum[i]) && i<8; i++){
000712        u = u*16 + sqlite3HexToInt(zNum[i]);
000713      }
000714      if( (u&0x80000000)==0 && sqlite3Isxdigit(zNum[i])==0 ){
000715        memcpy(pValue, &u, 4);
000716        return 1;
000717      }else{
000718        return 0;
000719      }
000720    }
000721  #endif
000722    if( !sqlite3Isdigit(zNum[0]) ) return 0;
000723    while( zNum[0]=='0' ) zNum++;
000724    for(i=0; i<11 && (c = zNum[i] - '0')>=0 && c<=9; i++){
000725      v = v*10 + c;
000726    }
000727  
000728    /* The longest decimal representation of a 32 bit integer is 10 digits:
000729    **
000730    **             1234567890
000731    **     2^31 -> 2147483648
000732    */
000733    testcase( i==10 );
000734    if( i>10 ){
000735      return 0;
000736    }
000737    testcase( v-neg==2147483647 );
000738    if( v-neg>2147483647 ){
000739      return 0;
000740    }
000741    if( neg ){
000742      v = -v;
000743    }
000744    *pValue = (int)v;
000745    return 1;
000746  }
000747  
000748  /*
000749  ** Return a 32-bit integer value extracted from a string.  If the
000750  ** string is not an integer, just return 0.
000751  */
000752  int sqlite3Atoi(const char *z){
000753    int x = 0;
000754    if( z ) sqlite3GetInt32(z, &x);
000755    return x;
000756  }
000757  
000758  /*
000759  ** The variable-length integer encoding is as follows:
000760  **
000761  ** KEY:
000762  **         A = 0xxxxxxx    7 bits of data and one flag bit
000763  **         B = 1xxxxxxx    7 bits of data and one flag bit
000764  **         C = xxxxxxxx    8 bits of data
000765  **
000766  **  7 bits - A
000767  ** 14 bits - BA
000768  ** 21 bits - BBA
000769  ** 28 bits - BBBA
000770  ** 35 bits - BBBBA
000771  ** 42 bits - BBBBBA
000772  ** 49 bits - BBBBBBA
000773  ** 56 bits - BBBBBBBA
000774  ** 64 bits - BBBBBBBBC
000775  */
000776  
000777  /*
000778  ** Write a 64-bit variable-length integer to memory starting at p[0].
000779  ** The length of data write will be between 1 and 9 bytes.  The number
000780  ** of bytes written is returned.
000781  **
000782  ** A variable-length integer consists of the lower 7 bits of each byte
000783  ** for all bytes that have the 8th bit set and one byte with the 8th
000784  ** bit clear.  Except, if we get to the 9th byte, it stores the full
000785  ** 8 bits and is the last byte.
000786  */
000787  static int SQLITE_NOINLINE putVarint64(unsigned char *p, u64 v){
000788    int i, j, n;
000789    u8 buf[10];
000790    if( v & (((u64)0xff000000)<<32) ){
000791      p[8] = (u8)v;
000792      v >>= 8;
000793      for(i=7; i>=0; i--){
000794        p[i] = (u8)((v & 0x7f) | 0x80);
000795        v >>= 7;
000796      }
000797      return 9;
000798    }    
000799    n = 0;
000800    do{
000801      buf[n++] = (u8)((v & 0x7f) | 0x80);
000802      v >>= 7;
000803    }while( v!=0 );
000804    buf[0] &= 0x7f;
000805    assert( n<=9 );
000806    for(i=0, j=n-1; j>=0; j--, i++){
000807      p[i] = buf[j];
000808    }
000809    return n;
000810  }
000811  int sqlite3PutVarint(unsigned char *p, u64 v){
000812    if( v<=0x7f ){
000813      p[0] = v&0x7f;
000814      return 1;
000815    }
000816    if( v<=0x3fff ){
000817      p[0] = ((v>>7)&0x7f)|0x80;
000818      p[1] = v&0x7f;
000819      return 2;
000820    }
000821    return putVarint64(p,v);
000822  }
000823  
000824  /*
000825  ** Bitmasks used by sqlite3GetVarint().  These precomputed constants
000826  ** are defined here rather than simply putting the constant expressions
000827  ** inline in order to work around bugs in the RVT compiler.
000828  **
000829  ** SLOT_2_0     A mask for  (0x7f<<14) | 0x7f
000830  **
000831  ** SLOT_4_2_0   A mask for  (0x7f<<28) | SLOT_2_0
000832  */
000833  #define SLOT_2_0     0x001fc07f
000834  #define SLOT_4_2_0   0xf01fc07f
000835  
000836  
000837  /*
000838  ** Read a 64-bit variable-length integer from memory starting at p[0].
000839  ** Return the number of bytes read.  The value is stored in *v.
000840  */
000841  u8 sqlite3GetVarint(const unsigned char *p, u64 *v){
000842    u32 a,b,s;
000843  
000844    a = *p;
000845    /* a: p0 (unmasked) */
000846    if (!(a&0x80))
000847    {
000848      *v = a;
000849      return 1;
000850    }
000851  
000852    p++;
000853    b = *p;
000854    /* b: p1 (unmasked) */
000855    if (!(b&0x80))
000856    {
000857      a &= 0x7f;
000858      a = a<<7;
000859      a |= b;
000860      *v = a;
000861      return 2;
000862    }
000863  
000864    /* Verify that constants are precomputed correctly */
000865    assert( SLOT_2_0 == ((0x7f<<14) | (0x7f)) );
000866    assert( SLOT_4_2_0 == ((0xfU<<28) | (0x7f<<14) | (0x7f)) );
000867  
000868    p++;
000869    a = a<<14;
000870    a |= *p;
000871    /* a: p0<<14 | p2 (unmasked) */
000872    if (!(a&0x80))
000873    {
000874      a &= SLOT_2_0;
000875      b &= 0x7f;
000876      b = b<<7;
000877      a |= b;
000878      *v = a;
000879      return 3;
000880    }
000881  
000882    /* CSE1 from below */
000883    a &= SLOT_2_0;
000884    p++;
000885    b = b<<14;
000886    b |= *p;
000887    /* b: p1<<14 | p3 (unmasked) */
000888    if (!(b&0x80))
000889    {
000890      b &= SLOT_2_0;
000891      /* moved CSE1 up */
000892      /* a &= (0x7f<<14)|(0x7f); */
000893      a = a<<7;
000894      a |= b;
000895      *v = a;
000896      return 4;
000897    }
000898  
000899    /* a: p0<<14 | p2 (masked) */
000900    /* b: p1<<14 | p3 (unmasked) */
000901    /* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
000902    /* moved CSE1 up */
000903    /* a &= (0x7f<<14)|(0x7f); */
000904    b &= SLOT_2_0;
000905    s = a;
000906    /* s: p0<<14 | p2 (masked) */
000907  
000908    p++;
000909    a = a<<14;
000910    a |= *p;
000911    /* a: p0<<28 | p2<<14 | p4 (unmasked) */
000912    if (!(a&0x80))
000913    {
000914      /* we can skip these cause they were (effectively) done above
000915      ** while calculating s */
000916      /* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
000917      /* b &= (0x7f<<14)|(0x7f); */
000918      b = b<<7;
000919      a |= b;
000920      s = s>>18;
000921      *v = ((u64)s)<<32 | a;
000922      return 5;
000923    }
000924  
000925    /* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
000926    s = s<<7;
000927    s |= b;
000928    /* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
000929  
000930    p++;
000931    b = b<<14;
000932    b |= *p;
000933    /* b: p1<<28 | p3<<14 | p5 (unmasked) */
000934    if (!(b&0x80))
000935    {
000936      /* we can skip this cause it was (effectively) done above in calc'ing s */
000937      /* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
000938      a &= SLOT_2_0;
000939      a = a<<7;
000940      a |= b;
000941      s = s>>18;
000942      *v = ((u64)s)<<32 | a;
000943      return 6;
000944    }
000945  
000946    p++;
000947    a = a<<14;
000948    a |= *p;
000949    /* a: p2<<28 | p4<<14 | p6 (unmasked) */
000950    if (!(a&0x80))
000951    {
000952      a &= SLOT_4_2_0;
000953      b &= SLOT_2_0;
000954      b = b<<7;
000955      a |= b;
000956      s = s>>11;
000957      *v = ((u64)s)<<32 | a;
000958      return 7;
000959    }
000960  
000961    /* CSE2 from below */
000962    a &= SLOT_2_0;
000963    p++;
000964    b = b<<14;
000965    b |= *p;
000966    /* b: p3<<28 | p5<<14 | p7 (unmasked) */
000967    if (!(b&0x80))
000968    {
000969      b &= SLOT_4_2_0;
000970      /* moved CSE2 up */
000971      /* a &= (0x7f<<14)|(0x7f); */
000972      a = a<<7;
000973      a |= b;
000974      s = s>>4;
000975      *v = ((u64)s)<<32 | a;
000976      return 8;
000977    }
000978  
000979    p++;
000980    a = a<<15;
000981    a |= *p;
000982    /* a: p4<<29 | p6<<15 | p8 (unmasked) */
000983  
000984    /* moved CSE2 up */
000985    /* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
000986    b &= SLOT_2_0;
000987    b = b<<8;
000988    a |= b;
000989  
000990    s = s<<4;
000991    b = p[-4];
000992    b &= 0x7f;
000993    b = b>>3;
000994    s |= b;
000995  
000996    *v = ((u64)s)<<32 | a;
000997  
000998    return 9;
000999  }
001000  
001001  /*
001002  ** Read a 32-bit variable-length integer from memory starting at p[0].
001003  ** Return the number of bytes read.  The value is stored in *v.
001004  **
001005  ** If the varint stored in p[0] is larger than can fit in a 32-bit unsigned
001006  ** integer, then set *v to 0xffffffff.
001007  **
001008  ** A MACRO version, getVarint32, is provided which inlines the 
001009  ** single-byte case.  All code should use the MACRO version as 
001010  ** this function assumes the single-byte case has already been handled.
001011  */
001012  u8 sqlite3GetVarint32(const unsigned char *p, u32 *v){
001013    u32 a,b;
001014  
001015    /* The 1-byte case.  Overwhelmingly the most common.  Handled inline
001016    ** by the getVarin32() macro */
001017    a = *p;
001018    /* a: p0 (unmasked) */
001019  #ifndef getVarint32
001020    if (!(a&0x80))
001021    {
001022      /* Values between 0 and 127 */
001023      *v = a;
001024      return 1;
001025    }
001026  #endif
001027  
001028    /* The 2-byte case */
001029    p++;
001030    b = *p;
001031    /* b: p1 (unmasked) */
001032    if (!(b&0x80))
001033    {
001034      /* Values between 128 and 16383 */
001035      a &= 0x7f;
001036      a = a<<7;
001037      *v = a | b;
001038      return 2;
001039    }
001040  
001041    /* The 3-byte case */
001042    p++;
001043    a = a<<14;
001044    a |= *p;
001045    /* a: p0<<14 | p2 (unmasked) */
001046    if (!(a&0x80))
001047    {
001048      /* Values between 16384 and 2097151 */
001049      a &= (0x7f<<14)|(0x7f);
001050      b &= 0x7f;
001051      b = b<<7;
001052      *v = a | b;
001053      return 3;
001054    }
001055  
001056    /* A 32-bit varint is used to store size information in btrees.
001057    ** Objects are rarely larger than 2MiB limit of a 3-byte varint.
001058    ** A 3-byte varint is sufficient, for example, to record the size
001059    ** of a 1048569-byte BLOB or string.
001060    **
001061    ** We only unroll the first 1-, 2-, and 3- byte cases.  The very
001062    ** rare larger cases can be handled by the slower 64-bit varint
001063    ** routine.
001064    */
001065  #if 1
001066    {
001067      u64 v64;
001068      u8 n;
001069  
001070      p -= 2;
001071      n = sqlite3GetVarint(p, &v64);
001072      assert( n>3 && n<=9 );
001073      if( (v64 & SQLITE_MAX_U32)!=v64 ){
001074        *v = 0xffffffff;
001075      }else{
001076        *v = (u32)v64;
001077      }
001078      return n;
001079    }
001080  
001081  #else
001082    /* For following code (kept for historical record only) shows an
001083    ** unrolling for the 3- and 4-byte varint cases.  This code is
001084    ** slightly faster, but it is also larger and much harder to test.
001085    */
001086    p++;
001087    b = b<<14;
001088    b |= *p;
001089    /* b: p1<<14 | p3 (unmasked) */
001090    if (!(b&0x80))
001091    {
001092      /* Values between 2097152 and 268435455 */
001093      b &= (0x7f<<14)|(0x7f);
001094      a &= (0x7f<<14)|(0x7f);
001095      a = a<<7;
001096      *v = a | b;
001097      return 4;
001098    }
001099  
001100    p++;
001101    a = a<<14;
001102    a |= *p;
001103    /* a: p0<<28 | p2<<14 | p4 (unmasked) */
001104    if (!(a&0x80))
001105    {
001106      /* Values  between 268435456 and 34359738367 */
001107      a &= SLOT_4_2_0;
001108      b &= SLOT_4_2_0;
001109      b = b<<7;
001110      *v = a | b;
001111      return 5;
001112    }
001113  
001114    /* We can only reach this point when reading a corrupt database
001115    ** file.  In that case we are not in any hurry.  Use the (relatively
001116    ** slow) general-purpose sqlite3GetVarint() routine to extract the
001117    ** value. */
001118    {
001119      u64 v64;
001120      u8 n;
001121  
001122      p -= 4;
001123      n = sqlite3GetVarint(p, &v64);
001124      assert( n>5 && n<=9 );
001125      *v = (u32)v64;
001126      return n;
001127    }
001128  #endif
001129  }
001130  
001131  /*
001132  ** Return the number of bytes that will be needed to store the given
001133  ** 64-bit integer.
001134  */
001135  int sqlite3VarintLen(u64 v){
001136    int i;
001137    for(i=1; (v >>= 7)!=0; i++){ assert( i<10 ); }
001138    return i;
001139  }
001140  
001141  
001142  /*
001143  ** Read or write a four-byte big-endian integer value.
001144  */
001145  u32 sqlite3Get4byte(const u8 *p){
001146  #if SQLITE_BYTEORDER==4321
001147    u32 x;
001148    memcpy(&x,p,4);
001149    return x;
001150  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
001151    u32 x;
001152    memcpy(&x,p,4);
001153    return __builtin_bswap32(x);
001154  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
001155    u32 x;
001156    memcpy(&x,p,4);
001157    return _byteswap_ulong(x);
001158  #else
001159    testcase( p[0]&0x80 );
001160    return ((unsigned)p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
001161  #endif
001162  }
001163  void sqlite3Put4byte(unsigned char *p, u32 v){
001164  #if SQLITE_BYTEORDER==4321
001165    memcpy(p,&v,4);
001166  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
001167    u32 x = __builtin_bswap32(v);
001168    memcpy(p,&x,4);
001169  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
001170    u32 x = _byteswap_ulong(v);
001171    memcpy(p,&x,4);
001172  #else
001173    p[0] = (u8)(v>>24);
001174    p[1] = (u8)(v>>16);
001175    p[2] = (u8)(v>>8);
001176    p[3] = (u8)v;
001177  #endif
001178  }
001179  
001180  
001181  
001182  /*
001183  ** Translate a single byte of Hex into an integer.
001184  ** This routine only works if h really is a valid hexadecimal
001185  ** character:  0..9a..fA..F
001186  */
001187  u8 sqlite3HexToInt(int h){
001188    assert( (h>='0' && h<='9') ||  (h>='a' && h<='f') ||  (h>='A' && h<='F') );
001189  #ifdef SQLITE_ASCII
001190    h += 9*(1&(h>>6));
001191  #endif
001192  #ifdef SQLITE_EBCDIC
001193    h += 9*(1&~(h>>4));
001194  #endif
001195    return (u8)(h & 0xf);
001196  }
001197  
001198  #if !defined(SQLITE_OMIT_BLOB_LITERAL) || defined(SQLITE_HAS_CODEC)
001199  /*
001200  ** Convert a BLOB literal of the form "x'hhhhhh'" into its binary
001201  ** value.  Return a pointer to its binary value.  Space to hold the
001202  ** binary value has been obtained from malloc and must be freed by
001203  ** the calling routine.
001204  */
001205  void *sqlite3HexToBlob(sqlite3 *db, const char *z, int n){
001206    char *zBlob;
001207    int i;
001208  
001209    zBlob = (char *)sqlite3DbMallocRawNN(db, n/2 + 1);
001210    n--;
001211    if( zBlob ){
001212      for(i=0; i<n; i+=2){
001213        zBlob[i/2] = (sqlite3HexToInt(z[i])<<4) | sqlite3HexToInt(z[i+1]);
001214      }
001215      zBlob[i/2] = 0;
001216    }
001217    return zBlob;
001218  }
001219  #endif /* !SQLITE_OMIT_BLOB_LITERAL || SQLITE_HAS_CODEC */
001220  
001221  /*
001222  ** Log an error that is an API call on a connection pointer that should
001223  ** not have been used.  The "type" of connection pointer is given as the
001224  ** argument.  The zType is a word like "NULL" or "closed" or "invalid".
001225  */
001226  static void logBadConnection(const char *zType){
001227    sqlite3_log(SQLITE_MISUSE, 
001228       "API call with %s database connection pointer",
001229       zType
001230    );
001231  }
001232  
001233  /*
001234  ** Check to make sure we have a valid db pointer.  This test is not
001235  ** foolproof but it does provide some measure of protection against
001236  ** misuse of the interface such as passing in db pointers that are
001237  ** NULL or which have been previously closed.  If this routine returns
001238  ** 1 it means that the db pointer is valid and 0 if it should not be
001239  ** dereferenced for any reason.  The calling function should invoke
001240  ** SQLITE_MISUSE immediately.
001241  **
001242  ** sqlite3SafetyCheckOk() requires that the db pointer be valid for
001243  ** use.  sqlite3SafetyCheckSickOrOk() allows a db pointer that failed to
001244  ** open properly and is not fit for general use but which can be
001245  ** used as an argument to sqlite3_errmsg() or sqlite3_close().
001246  */
001247  int sqlite3SafetyCheckOk(sqlite3 *db){
001248    u32 magic;
001249    if( db==0 ){
001250      logBadConnection("NULL");
001251      return 0;
001252    }
001253    magic = db->magic;
001254    if( magic!=SQLITE_MAGIC_OPEN ){
001255      if( sqlite3SafetyCheckSickOrOk(db) ){
001256        testcase( sqlite3GlobalConfig.xLog!=0 );
001257        logBadConnection("unopened");
001258      }
001259      return 0;
001260    }else{
001261      return 1;
001262    }
001263  }
001264  int sqlite3SafetyCheckSickOrOk(sqlite3 *db){
001265    u32 magic;
001266    magic = db->magic;
001267    if( magic!=SQLITE_MAGIC_SICK &&
001268        magic!=SQLITE_MAGIC_OPEN &&
001269        magic!=SQLITE_MAGIC_BUSY ){
001270      testcase( sqlite3GlobalConfig.xLog!=0 );
001271      logBadConnection("invalid");
001272      return 0;
001273    }else{
001274      return 1;
001275    }
001276  }
001277  
001278  /*
001279  ** Attempt to add, substract, or multiply the 64-bit signed value iB against
001280  ** the other 64-bit signed integer at *pA and store the result in *pA.
001281  ** Return 0 on success.  Or if the operation would have resulted in an
001282  ** overflow, leave *pA unchanged and return 1.
001283  */
001284  int sqlite3AddInt64(i64 *pA, i64 iB){
001285  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001286    return __builtin_add_overflow(*pA, iB, pA);
001287  #else
001288    i64 iA = *pA;
001289    testcase( iA==0 ); testcase( iA==1 );
001290    testcase( iB==-1 ); testcase( iB==0 );
001291    if( iB>=0 ){
001292      testcase( iA>0 && LARGEST_INT64 - iA == iB );
001293      testcase( iA>0 && LARGEST_INT64 - iA == iB - 1 );
001294      if( iA>0 && LARGEST_INT64 - iA < iB ) return 1;
001295    }else{
001296      testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 1 );
001297      testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 2 );
001298      if( iA<0 && -(iA + LARGEST_INT64) > iB + 1 ) return 1;
001299    }
001300    *pA += iB;
001301    return 0; 
001302  #endif
001303  }
001304  int sqlite3SubInt64(i64 *pA, i64 iB){
001305  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001306    return __builtin_sub_overflow(*pA, iB, pA);
001307  #else
001308    testcase( iB==SMALLEST_INT64+1 );
001309    if( iB==SMALLEST_INT64 ){
001310      testcase( (*pA)==(-1) ); testcase( (*pA)==0 );
001311      if( (*pA)>=0 ) return 1;
001312      *pA -= iB;
001313      return 0;
001314    }else{
001315      return sqlite3AddInt64(pA, -iB);
001316    }
001317  #endif
001318  }
001319  int sqlite3MulInt64(i64 *pA, i64 iB){
001320  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001321    return __builtin_mul_overflow(*pA, iB, pA);
001322  #else
001323    i64 iA = *pA;
001324    if( iB>0 ){
001325      if( iA>LARGEST_INT64/iB ) return 1;
001326      if( iA<SMALLEST_INT64/iB ) return 1;
001327    }else if( iB<0 ){
001328      if( iA>0 ){
001329        if( iB<SMALLEST_INT64/iA ) return 1;
001330      }else if( iA<0 ){
001331        if( iB==SMALLEST_INT64 ) return 1;
001332        if( iA==SMALLEST_INT64 ) return 1;
001333        if( -iA>LARGEST_INT64/-iB ) return 1;
001334      }
001335    }
001336    *pA = iA*iB;
001337    return 0;
001338  #endif
001339  }
001340  
001341  /*
001342  ** Compute the absolute value of a 32-bit signed integer, of possible.  Or 
001343  ** if the integer has a value of -2147483648, return +2147483647
001344  */
001345  int sqlite3AbsInt32(int x){
001346    if( x>=0 ) return x;
001347    if( x==(int)0x80000000 ) return 0x7fffffff;
001348    return -x;
001349  }
001350  
001351  #ifdef SQLITE_ENABLE_8_3_NAMES
001352  /*
001353  ** If SQLITE_ENABLE_8_3_NAMES is set at compile-time and if the database
001354  ** filename in zBaseFilename is a URI with the "8_3_names=1" parameter and
001355  ** if filename in z[] has a suffix (a.k.a. "extension") that is longer than
001356  ** three characters, then shorten the suffix on z[] to be the last three
001357  ** characters of the original suffix.
001358  **
001359  ** If SQLITE_ENABLE_8_3_NAMES is set to 2 at compile-time, then always
001360  ** do the suffix shortening regardless of URI parameter.
001361  **
001362  ** Examples:
001363  **
001364  **     test.db-journal    =>   test.nal
001365  **     test.db-wal        =>   test.wal
001366  **     test.db-shm        =>   test.shm
001367  **     test.db-mj7f3319fa =>   test.9fa
001368  */
001369  void sqlite3FileSuffix3(const char *zBaseFilename, char *z){
001370  #if SQLITE_ENABLE_8_3_NAMES<2
001371    if( sqlite3_uri_boolean(zBaseFilename, "8_3_names", 0) )
001372  #endif
001373    {
001374      int i, sz;
001375      sz = sqlite3Strlen30(z);
001376      for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
001377      if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
001378    }
001379  }
001380  #endif
001381  
001382  /* 
001383  ** Find (an approximate) sum of two LogEst values.  This computation is
001384  ** not a simple "+" operator because LogEst is stored as a logarithmic
001385  ** value.
001386  ** 
001387  */
001388  LogEst sqlite3LogEstAdd(LogEst a, LogEst b){
001389    static const unsigned char x[] = {
001390       10, 10,                         /* 0,1 */
001391        9, 9,                          /* 2,3 */
001392        8, 8,                          /* 4,5 */
001393        7, 7, 7,                       /* 6,7,8 */
001394        6, 6, 6,                       /* 9,10,11 */
001395        5, 5, 5,                       /* 12-14 */
001396        4, 4, 4, 4,                    /* 15-18 */
001397        3, 3, 3, 3, 3, 3,              /* 19-24 */
001398        2, 2, 2, 2, 2, 2, 2,           /* 25-31 */
001399    };
001400    if( a>=b ){
001401      if( a>b+49 ) return a;
001402      if( a>b+31 ) return a+1;
001403      return a+x[a-b];
001404    }else{
001405      if( b>a+49 ) return b;
001406      if( b>a+31 ) return b+1;
001407      return b+x[b-a];
001408    }
001409  }
001410  
001411  /*
001412  ** Convert an integer into a LogEst.  In other words, compute an
001413  ** approximation for 10*log2(x).
001414  */
001415  LogEst sqlite3LogEst(u64 x){
001416    static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
001417    LogEst y = 40;
001418    if( x<8 ){
001419      if( x<2 ) return 0;
001420      while( x<8 ){  y -= 10; x <<= 1; }
001421    }else{
001422  #if GCC_VERSION>=5004000
001423      int i = 60 - __builtin_clzll(x);
001424      y += i*10;
001425      x >>= i;
001426  #else
001427      while( x>255 ){ y += 40; x >>= 4; }  /*OPTIMIZATION-IF-TRUE*/
001428      while( x>15 ){  y += 10; x >>= 1; }
001429  #endif
001430    }
001431    return a[x&7] + y - 10;
001432  }
001433  
001434  #ifndef SQLITE_OMIT_VIRTUALTABLE
001435  /*
001436  ** Convert a double into a LogEst
001437  ** In other words, compute an approximation for 10*log2(x).
001438  */
001439  LogEst sqlite3LogEstFromDouble(double x){
001440    u64 a;
001441    LogEst e;
001442    assert( sizeof(x)==8 && sizeof(a)==8 );
001443    if( x<=1 ) return 0;
001444    if( x<=2000000000 ) return sqlite3LogEst((u64)x);
001445    memcpy(&a, &x, 8);
001446    e = (a>>52) - 1022;
001447    return e*10;
001448  }
001449  #endif /* SQLITE_OMIT_VIRTUALTABLE */
001450  
001451  #if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \
001452      defined(SQLITE_ENABLE_STAT3_OR_STAT4) || \
001453      defined(SQLITE_EXPLAIN_ESTIMATED_ROWS)
001454  /*
001455  ** Convert a LogEst into an integer.
001456  **
001457  ** Note that this routine is only used when one or more of various
001458  ** non-standard compile-time options is enabled.
001459  */
001460  u64 sqlite3LogEstToInt(LogEst x){
001461    u64 n;
001462    n = x%10;
001463    x /= 10;
001464    if( n>=5 ) n -= 2;
001465    else if( n>=1 ) n -= 1;
001466  #if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \
001467      defined(SQLITE_EXPLAIN_ESTIMATED_ROWS)
001468    if( x>60 ) return (u64)LARGEST_INT64;
001469  #else
001470    /* If only SQLITE_ENABLE_STAT3_OR_STAT4 is on, then the largest input
001471    ** possible to this routine is 310, resulting in a maximum x of 31 */
001472    assert( x<=60 );
001473  #endif
001474    return x>=3 ? (n+8)<<(x-3) : (n+8)>>(3-x);
001475  }
001476  #endif /* defined SCANSTAT or STAT4 or ESTIMATED_ROWS */
001477  
001478  /*
001479  ** Add a new name/number pair to a VList.  This might require that the
001480  ** VList object be reallocated, so return the new VList.  If an OOM
001481  ** error occurs, the original VList returned and the
001482  ** db->mallocFailed flag is set.
001483  **
001484  ** A VList is really just an array of integers.  To destroy a VList,
001485  ** simply pass it to sqlite3DbFree().
001486  **
001487  ** The first integer is the number of integers allocated for the whole
001488  ** VList.  The second integer is the number of integers actually used.
001489  ** Each name/number pair is encoded by subsequent groups of 3 or more
001490  ** integers.
001491  **
001492  ** Each name/number pair starts with two integers which are the numeric
001493  ** value for the pair and the size of the name/number pair, respectively.
001494  ** The text name overlays one or more following integers.  The text name
001495  ** is always zero-terminated.
001496  **
001497  ** Conceptually:
001498  **
001499  **    struct VList {
001500  **      int nAlloc;   // Number of allocated slots 
001501  **      int nUsed;    // Number of used slots 
001502  **      struct VListEntry {
001503  **        int iValue;    // Value for this entry
001504  **        int nSlot;     // Slots used by this entry
001505  **        // ... variable name goes here
001506  **      } a[0];
001507  **    }
001508  **
001509  ** During code generation, pointers to the variable names within the
001510  ** VList are taken.  When that happens, nAlloc is set to zero as an 
001511  ** indication that the VList may never again be enlarged, since the
001512  ** accompanying realloc() would invalidate the pointers.
001513  */
001514  VList *sqlite3VListAdd(
001515    sqlite3 *db,           /* The database connection used for malloc() */
001516    VList *pIn,            /* The input VList.  Might be NULL */
001517    const char *zName,     /* Name of symbol to add */
001518    int nName,             /* Bytes of text in zName */
001519    int iVal               /* Value to associate with zName */
001520  ){
001521    int nInt;              /* number of sizeof(int) objects needed for zName */
001522    char *z;               /* Pointer to where zName will be stored */
001523    int i;                 /* Index in pIn[] where zName is stored */
001524  
001525    nInt = nName/4 + 3;
001526    assert( pIn==0 || pIn[0]>=3 );  /* Verify ok to add new elements */
001527    if( pIn==0 || pIn[1]+nInt > pIn[0] ){
001528      /* Enlarge the allocation */
001529      int nAlloc = (pIn ? pIn[0]*2 : 10) + nInt;
001530      VList *pOut = sqlite3DbRealloc(db, pIn, nAlloc*sizeof(int));
001531      if( pOut==0 ) return pIn;
001532      if( pIn==0 ) pOut[1] = 2;
001533      pIn = pOut;
001534      pIn[0] = nAlloc;
001535    }
001536    i = pIn[1];
001537    pIn[i] = iVal;
001538    pIn[i+1] = nInt;
001539    z = (char*)&pIn[i+2];
001540    pIn[1] = i+nInt;
001541    assert( pIn[1]<=pIn[0] );
001542    memcpy(z, zName, nName);
001543    z[nName] = 0;
001544    return pIn;
001545  }
001546  
001547  /*
001548  ** Return a pointer to the name of a variable in the given VList that
001549  ** has the value iVal.  Or return a NULL if there is no such variable in
001550  ** the list
001551  */
001552  const char *sqlite3VListNumToName(VList *pIn, int iVal){
001553    int i, mx;
001554    if( pIn==0 ) return 0;
001555    mx = pIn[1];
001556    i = 2;
001557    do{
001558      if( pIn[i]==iVal ) return (char*)&pIn[i+2];
001559      i += pIn[i+1];
001560    }while( i<mx );
001561    return 0;
001562  }
001563  
001564  /*
001565  ** Return the number of the variable named zName, if it is in VList.
001566  ** or return 0 if there is no such variable.
001567  */
001568  int sqlite3VListNameToNum(VList *pIn, const char *zName, int nName){
001569    int i, mx;
001570    if( pIn==0 ) return 0;
001571    mx = pIn[1];
001572    i = 2;
001573    do{
001574      const char *z = (const char*)&pIn[i+2];
001575      if( strncmp(z,zName,nName)==0 && z[nName]==0 ) return pIn[i];
001576      i += pIn[i+1];
001577    }while( i<mx );
001578    return 0;
001579  }