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  #ifndef SQLITE_OMIT_FLOATING_POINT
000021  #include <math.h>
000022  #endif
000023  
000024  /*
000025  ** Calls to sqlite3FaultSim() are used to simulate a failure during testing,
000026  ** or to bypass normal error detection during testing in order to let
000027  ** execute proceed further downstream.
000028  **
000029  ** In deployment, sqlite3FaultSim() *always* return SQLITE_OK (0).  The
000030  ** sqlite3FaultSim() function only returns non-zero during testing.
000031  **
000032  ** During testing, if the test harness has set a fault-sim callback using
000033  ** a call to sqlite3_test_control(SQLITE_TESTCTRL_FAULT_INSTALL), then
000034  ** each call to sqlite3FaultSim() is relayed to that application-supplied
000035  ** callback and the integer return value form the application-supplied
000036  ** callback is returned by sqlite3FaultSim().
000037  **
000038  ** The integer argument to sqlite3FaultSim() is a code to identify which
000039  ** sqlite3FaultSim() instance is being invoked. Each call to sqlite3FaultSim()
000040  ** should have a unique code.  To prevent legacy testing applications from
000041  ** breaking, the codes should not be changed or reused.
000042  */
000043  #ifndef SQLITE_UNTESTABLE
000044  int sqlite3FaultSim(int iTest){
000045    int (*xCallback)(int) = sqlite3GlobalConfig.xTestCallback;
000046    return xCallback ? xCallback(iTest) : SQLITE_OK;
000047  }
000048  #endif
000049  
000050  #ifndef SQLITE_OMIT_FLOATING_POINT
000051  /*
000052  ** Return true if the floating point value is Not a Number (NaN).
000053  **
000054  ** Use the math library isnan() function if compiled with SQLITE_HAVE_ISNAN.
000055  ** Otherwise, we have our own implementation that works on most systems.
000056  */
000057  int sqlite3IsNaN(double x){
000058    int rc;   /* The value return */
000059  #if !SQLITE_HAVE_ISNAN && !HAVE_ISNAN
000060    u64 y;
000061    memcpy(&y,&x,sizeof(y));
000062    rc = IsNaN(y);
000063  #else
000064    rc = isnan(x);
000065  #endif /* HAVE_ISNAN */
000066    testcase( rc );
000067    return rc;
000068  }
000069  #endif /* SQLITE_OMIT_FLOATING_POINT */
000070  
000071  /*
000072  ** Compute a string length that is limited to what can be stored in
000073  ** lower 30 bits of a 32-bit signed integer.
000074  **
000075  ** The value returned will never be negative.  Nor will it ever be greater
000076  ** than the actual length of the string.  For very long strings (greater
000077  ** than 1GiB) the value returned might be less than the true string length.
000078  */
000079  int sqlite3Strlen30(const char *z){
000080    if( z==0 ) return 0;
000081    return 0x3fffffff & (int)strlen(z);
000082  }
000083  
000084  /*
000085  ** Return the declared type of a column.  Or return zDflt if the column
000086  ** has no declared type.
000087  **
000088  ** The column type is an extra string stored after the zero-terminator on
000089  ** the column name if and only if the COLFLAG_HASTYPE flag is set.
000090  */
000091  char *sqlite3ColumnType(Column *pCol, char *zDflt){
000092    if( pCol->colFlags & COLFLAG_HASTYPE ){
000093      return pCol->zCnName + strlen(pCol->zCnName) + 1;
000094    }else if( pCol->eCType ){
000095      assert( pCol->eCType<=SQLITE_N_STDTYPE );
000096      return (char*)sqlite3StdType[pCol->eCType-1];
000097    }else{
000098      return zDflt;
000099    }
000100  }
000101  
000102  /*
000103  ** Helper function for sqlite3Error() - called rarely.  Broken out into
000104  ** a separate routine to avoid unnecessary register saves on entry to
000105  ** sqlite3Error().
000106  */
000107  static SQLITE_NOINLINE void  sqlite3ErrorFinish(sqlite3 *db, int err_code){
000108    if( db->pErr ) sqlite3ValueSetNull(db->pErr);
000109    sqlite3SystemError(db, err_code);
000110  }
000111  
000112  /*
000113  ** Set the current error code to err_code and clear any prior error message.
000114  ** Also set iSysErrno (by calling sqlite3System) if the err_code indicates
000115  ** that would be appropriate.
000116  */
000117  void sqlite3Error(sqlite3 *db, int err_code){
000118    assert( db!=0 );
000119    db->errCode = err_code;
000120    if( err_code || db->pErr ){
000121      sqlite3ErrorFinish(db, err_code);
000122    }else{
000123      db->errByteOffset = -1;
000124    }
000125  }
000126  
000127  /*
000128  ** The equivalent of sqlite3Error(db, SQLITE_OK).  Clear the error state
000129  ** and error message.
000130  */
000131  void sqlite3ErrorClear(sqlite3 *db){
000132    assert( db!=0 );
000133    db->errCode = SQLITE_OK;
000134    db->errByteOffset = -1;
000135    if( db->pErr ) sqlite3ValueSetNull(db->pErr);
000136  }
000137  
000138  /*
000139  ** Load the sqlite3.iSysErrno field if that is an appropriate thing
000140  ** to do based on the SQLite error code in rc.
000141  */
000142  void sqlite3SystemError(sqlite3 *db, int rc){
000143    if( rc==SQLITE_IOERR_NOMEM ) return;
000144  #if defined(SQLITE_USE_SEH) && !defined(SQLITE_OMIT_WAL)
000145    if( rc==SQLITE_IOERR_IN_PAGE ){
000146      int ii;
000147      int iErr;
000148      sqlite3BtreeEnterAll(db);
000149      for(ii=0; ii<db->nDb; ii++){
000150        if( db->aDb[ii].pBt ){
000151          iErr = sqlite3PagerWalSystemErrno(sqlite3BtreePager(db->aDb[ii].pBt));
000152          if( iErr ){
000153            db->iSysErrno = iErr;
000154          }
000155        }
000156      }
000157      sqlite3BtreeLeaveAll(db);
000158      return;
000159    }
000160  #endif
000161    rc &= 0xff;
000162    if( rc==SQLITE_CANTOPEN || rc==SQLITE_IOERR ){
000163      db->iSysErrno = sqlite3OsGetLastError(db->pVfs);
000164    }
000165  }
000166  
000167  /*
000168  ** Set the most recent error code and error string for the sqlite
000169  ** handle "db". The error code is set to "err_code".
000170  **
000171  ** If it is not NULL, string zFormat specifies the format of the
000172  ** error string.  zFormat and any string tokens that follow it are
000173  ** assumed to be encoded in UTF-8.
000174  **
000175  ** To clear the most recent error for sqlite handle "db", sqlite3Error
000176  ** should be called with err_code set to SQLITE_OK and zFormat set
000177  ** to NULL.
000178  */
000179  void sqlite3ErrorWithMsg(sqlite3 *db, int err_code, const char *zFormat, ...){
000180    assert( db!=0 );
000181    db->errCode = err_code;
000182    sqlite3SystemError(db, err_code);
000183    if( zFormat==0 ){
000184      sqlite3Error(db, err_code);
000185    }else if( db->pErr || (db->pErr = sqlite3ValueNew(db))!=0 ){
000186      char *z;
000187      va_list ap;
000188      va_start(ap, zFormat);
000189      z = sqlite3VMPrintf(db, zFormat, ap);
000190      va_end(ap);
000191      sqlite3ValueSetStr(db->pErr, -1, z, SQLITE_UTF8, SQLITE_DYNAMIC);
000192    }
000193  }
000194  
000195  /*
000196  ** Check for interrupts and invoke progress callback.
000197  */
000198  void sqlite3ProgressCheck(Parse *p){
000199    sqlite3 *db = p->db;
000200    if( AtomicLoad(&db->u1.isInterrupted) ){
000201      p->nErr++;
000202      p->rc = SQLITE_INTERRUPT;
000203    }
000204  #ifndef SQLITE_OMIT_PROGRESS_CALLBACK
000205    if( db->xProgress ){
000206      if( p->rc==SQLITE_INTERRUPT ){
000207        p->nProgressSteps = 0;
000208      }else if( (++p->nProgressSteps)>=db->nProgressOps ){
000209        if( db->xProgress(db->pProgressArg) ){
000210          p->nErr++;
000211          p->rc = SQLITE_INTERRUPT;
000212        }
000213        p->nProgressSteps = 0;
000214      }
000215    }
000216  #endif
000217  }
000218  
000219  /*
000220  ** Add an error message to pParse->zErrMsg and increment pParse->nErr.
000221  **
000222  ** This function should be used to report any error that occurs while
000223  ** compiling an SQL statement (i.e. within sqlite3_prepare()). The
000224  ** last thing the sqlite3_prepare() function does is copy the error
000225  ** stored by this function into the database handle using sqlite3Error().
000226  ** Functions sqlite3Error() or sqlite3ErrorWithMsg() should be used
000227  ** during statement execution (sqlite3_step() etc.).
000228  */
000229  void sqlite3ErrorMsg(Parse *pParse, const char *zFormat, ...){
000230    char *zMsg;
000231    va_list ap;
000232    sqlite3 *db = pParse->db;
000233    assert( db!=0 );
000234    assert( db->pParse==pParse || db->pParse->pToplevel==pParse );
000235    db->errByteOffset = -2;
000236    va_start(ap, zFormat);
000237    zMsg = sqlite3VMPrintf(db, zFormat, ap);
000238    va_end(ap);
000239    if( db->errByteOffset<-1 ) db->errByteOffset = -1;
000240    if( db->suppressErr ){
000241      sqlite3DbFree(db, zMsg);
000242      if( db->mallocFailed ){
000243        pParse->nErr++;
000244        pParse->rc = SQLITE_NOMEM;
000245      }
000246    }else{
000247      pParse->nErr++;
000248      sqlite3DbFree(db, pParse->zErrMsg);
000249      pParse->zErrMsg = zMsg;
000250      pParse->rc = SQLITE_ERROR;
000251      pParse->pWith = 0;
000252    }
000253  }
000254  
000255  /*
000256  ** If database connection db is currently parsing SQL, then transfer
000257  ** error code errCode to that parser if the parser has not already
000258  ** encountered some other kind of error.
000259  */
000260  int sqlite3ErrorToParser(sqlite3 *db, int errCode){
000261    Parse *pParse;
000262    if( db==0 || (pParse = db->pParse)==0 ) return errCode;
000263    pParse->rc = errCode;
000264    pParse->nErr++;
000265    return errCode;
000266  }
000267  
000268  /*
000269  ** Convert an SQL-style quoted string into a normal string by removing
000270  ** the quote characters.  The conversion is done in-place.  If the
000271  ** input does not begin with a quote character, then this routine
000272  ** is a no-op.
000273  **
000274  ** The input string must be zero-terminated.  A new zero-terminator
000275  ** is added to the dequoted string.
000276  **
000277  ** The return value is -1 if no dequoting occurs or the length of the
000278  ** dequoted string, exclusive of the zero terminator, if dequoting does
000279  ** occur.
000280  **
000281  ** 2002-02-14: This routine is extended to remove MS-Access style
000282  ** brackets from around identifiers.  For example:  "[a-b-c]" becomes
000283  ** "a-b-c".
000284  */
000285  void sqlite3Dequote(char *z){
000286    char quote;
000287    int i, j;
000288    if( z==0 ) return;
000289    quote = z[0];
000290    if( !sqlite3Isquote(quote) ) return;
000291    if( quote=='[' ) quote = ']';
000292    for(i=1, j=0;; i++){
000293      assert( z[i] );
000294      if( z[i]==quote ){
000295        if( z[i+1]==quote ){
000296          z[j++] = quote;
000297          i++;
000298        }else{
000299          break;
000300        }
000301      }else{
000302        z[j++] = z[i];
000303      }
000304    }
000305    z[j] = 0;
000306  }
000307  void sqlite3DequoteExpr(Expr *p){
000308    assert( !ExprHasProperty(p, EP_IntValue) );
000309    assert( sqlite3Isquote(p->u.zToken[0]) );
000310    p->flags |= p->u.zToken[0]=='"' ? EP_Quoted|EP_DblQuoted : EP_Quoted;
000311    sqlite3Dequote(p->u.zToken);
000312  }
000313  
000314  /*
000315  ** If the input token p is quoted, try to adjust the token to remove
000316  ** the quotes.  This is not always possible:
000317  **
000318  **     "abc"     ->   abc
000319  **     "ab""cd"  ->   (not possible because of the interior "")
000320  **
000321  ** Remove the quotes if possible.  This is a optimization.  The overall
000322  ** system should still return the correct answer even if this routine
000323  ** is always a no-op.
000324  */
000325  void sqlite3DequoteToken(Token *p){
000326    unsigned int i;
000327    if( p->n<2 ) return;
000328    if( !sqlite3Isquote(p->z[0]) ) return;
000329    for(i=1; i<p->n-1; i++){
000330      if( sqlite3Isquote(p->z[i]) ) return;
000331    }
000332    p->n -= 2;
000333    p->z++;
000334  }
000335  
000336  /*
000337  ** Generate a Token object from a string
000338  */
000339  void sqlite3TokenInit(Token *p, char *z){
000340    p->z = z;
000341    p->n = sqlite3Strlen30(z);
000342  }
000343  
000344  /* Convenient short-hand */
000345  #define UpperToLower sqlite3UpperToLower
000346  
000347  /*
000348  ** Some systems have stricmp().  Others have strcasecmp().  Because
000349  ** there is no consistency, we will define our own.
000350  **
000351  ** IMPLEMENTATION-OF: R-30243-02494 The sqlite3_stricmp() and
000352  ** sqlite3_strnicmp() APIs allow applications and extensions to compare
000353  ** the contents of two buffers containing UTF-8 strings in a
000354  ** case-independent fashion, using the same definition of "case
000355  ** independence" that SQLite uses internally when comparing identifiers.
000356  */
000357  int sqlite3_stricmp(const char *zLeft, const char *zRight){
000358    if( zLeft==0 ){
000359      return zRight ? -1 : 0;
000360    }else if( zRight==0 ){
000361      return 1;
000362    }
000363    return sqlite3StrICmp(zLeft, zRight);
000364  }
000365  int sqlite3StrICmp(const char *zLeft, const char *zRight){
000366    unsigned char *a, *b;
000367    int c, x;
000368    a = (unsigned char *)zLeft;
000369    b = (unsigned char *)zRight;
000370    for(;;){
000371      c = *a;
000372      x = *b;
000373      if( c==x ){
000374        if( c==0 ) break;
000375      }else{
000376        c = (int)UpperToLower[c] - (int)UpperToLower[x];
000377        if( c ) break;
000378      }
000379      a++;
000380      b++;
000381    }
000382    return c;
000383  }
000384  int sqlite3_strnicmp(const char *zLeft, const char *zRight, int N){
000385    register unsigned char *a, *b;
000386    if( zLeft==0 ){
000387      return zRight ? -1 : 0;
000388    }else if( zRight==0 ){
000389      return 1;
000390    }
000391    a = (unsigned char *)zLeft;
000392    b = (unsigned char *)zRight;
000393    while( N-- > 0 && *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; }
000394    return N<0 ? 0 : UpperToLower[*a] - UpperToLower[*b];
000395  }
000396  
000397  /*
000398  ** Compute an 8-bit hash on a string that is insensitive to case differences
000399  */
000400  u8 sqlite3StrIHash(const char *z){
000401    u8 h = 0;
000402    if( z==0 ) return 0;
000403    while( z[0] ){
000404      h += UpperToLower[(unsigned char)z[0]];
000405      z++;
000406    }
000407    return h;
000408  }
000409  
000410  /* Double-Double multiplication.  (x[0],x[1]) *= (y,yy)
000411  **
000412  ** Reference:
000413  **   T. J. Dekker, "A Floating-Point Technique for Extending the
000414  **   Available Precision".  1971-07-26.
000415  */
000416  static void dekkerMul2(volatile double *x, double y, double yy){
000417    /*
000418    ** The "volatile" keywords on parameter x[] and on local variables
000419    ** below are needed force intermediate results to be truncated to
000420    ** binary64 rather than be carried around in an extended-precision
000421    ** format.  The truncation is necessary for the Dekker algorithm to
000422    ** work.  Intel x86 floating point might omit the truncation without
000423    ** the use of volatile. 
000424    */
000425    volatile double tx, ty, p, q, c, cc;
000426    double hx, hy;
000427    u64 m;
000428    memcpy(&m, (void*)&x[0], 8);
000429    m &= 0xfffffffffc000000LL;
000430    memcpy(&hx, &m, 8);
000431    tx = x[0] - hx;
000432    memcpy(&m, &y, 8);
000433    m &= 0xfffffffffc000000LL;
000434    memcpy(&hy, &m, 8);
000435    ty = y - hy;
000436    p = hx*hy;
000437    q = hx*ty + tx*hy;
000438    c = p+q;
000439    cc = p - c + q + tx*ty;
000440    cc = x[0]*yy + x[1]*y + cc;
000441    x[0] = c + cc;
000442    x[1] = c - x[0];
000443    x[1] += cc;
000444  }
000445  
000446  /*
000447  ** The string z[] is an text representation of a real number.
000448  ** Convert this string to a double and write it into *pResult.
000449  **
000450  ** The string z[] is length bytes in length (bytes, not characters) and
000451  ** uses the encoding enc.  The string is not necessarily zero-terminated.
000452  **
000453  ** Return TRUE if the result is a valid real number (or integer) and FALSE
000454  ** if the string is empty or contains extraneous text.  More specifically
000455  ** return
000456  **      1          =>  The input string is a pure integer
000457  **      2 or more  =>  The input has a decimal point or eNNN clause
000458  **      0 or less  =>  The input string is not a valid number
000459  **     -1          =>  Not a valid number, but has a valid prefix which
000460  **                     includes a decimal point and/or an eNNN clause
000461  **
000462  ** Valid numbers are in one of these formats:
000463  **
000464  **    [+-]digits[E[+-]digits]
000465  **    [+-]digits.[digits][E[+-]digits]
000466  **    [+-].digits[E[+-]digits]
000467  **
000468  ** Leading and trailing whitespace is ignored for the purpose of determining
000469  ** validity.
000470  **
000471  ** If some prefix of the input string is a valid number, this routine
000472  ** returns FALSE but it still converts the prefix and writes the result
000473  ** into *pResult.
000474  */
000475  #if defined(_MSC_VER)
000476  #pragma warning(disable : 4756)
000477  #endif
000478  int sqlite3AtoF(const char *z, double *pResult, int length, u8 enc){
000479  #ifndef SQLITE_OMIT_FLOATING_POINT
000480    int incr;
000481    const char *zEnd;
000482    /* sign * significand * (10 ^ (esign * exponent)) */
000483    int sign = 1;    /* sign of significand */
000484    u64 s = 0;       /* significand */
000485    int d = 0;       /* adjust exponent for shifting decimal point */
000486    int esign = 1;   /* sign of exponent */
000487    int e = 0;       /* exponent */
000488    int eValid = 1;  /* True exponent is either not used or is well-formed */
000489    int nDigit = 0;  /* Number of digits processed */
000490    int eType = 1;   /* 1: pure integer,  2+: fractional  -1 or less: bad UTF16 */
000491  
000492    assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
000493    *pResult = 0.0;   /* Default return value, in case of an error */
000494    if( length==0 ) return 0;
000495  
000496    if( enc==SQLITE_UTF8 ){
000497      incr = 1;
000498      zEnd = z + length;
000499    }else{
000500      int i;
000501      incr = 2;
000502      length &= ~1;
000503      assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
000504      testcase( enc==SQLITE_UTF16LE );
000505      testcase( enc==SQLITE_UTF16BE );
000506      for(i=3-enc; i<length && z[i]==0; i+=2){}
000507      if( i<length ) eType = -100;
000508      zEnd = &z[i^1];
000509      z += (enc&1);
000510    }
000511  
000512    /* skip leading spaces */
000513    while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
000514    if( z>=zEnd ) return 0;
000515  
000516    /* get sign of significand */
000517    if( *z=='-' ){
000518      sign = -1;
000519      z+=incr;
000520    }else if( *z=='+' ){
000521      z+=incr;
000522    }
000523  
000524    /* copy max significant digits to significand */
000525    while( z<zEnd && sqlite3Isdigit(*z) ){
000526      s = s*10 + (*z - '0');
000527      z+=incr; nDigit++;
000528      if( s>=((LARGEST_UINT64-9)/10) ){
000529        /* skip non-significant significand digits
000530        ** (increase exponent by d to shift decimal left) */
000531        while( z<zEnd && sqlite3Isdigit(*z) ){ z+=incr; d++; }
000532      }
000533    }
000534    if( z>=zEnd ) goto do_atof_calc;
000535  
000536    /* if decimal point is present */
000537    if( *z=='.' ){
000538      z+=incr;
000539      eType++;
000540      /* copy digits from after decimal to significand
000541      ** (decrease exponent by d to shift decimal right) */
000542      while( z<zEnd && sqlite3Isdigit(*z) ){
000543        if( s<((LARGEST_UINT64-9)/10) ){
000544          s = s*10 + (*z - '0');
000545          d--;
000546          nDigit++;
000547        }
000548        z+=incr;
000549      }
000550    }
000551    if( z>=zEnd ) goto do_atof_calc;
000552  
000553    /* if exponent is present */
000554    if( *z=='e' || *z=='E' ){
000555      z+=incr;
000556      eValid = 0;
000557      eType++;
000558  
000559      /* This branch is needed to avoid a (harmless) buffer overread.  The
000560      ** special comment alerts the mutation tester that the correct answer
000561      ** is obtained even if the branch is omitted */
000562      if( z>=zEnd ) goto do_atof_calc;              /*PREVENTS-HARMLESS-OVERREAD*/
000563  
000564      /* get sign of exponent */
000565      if( *z=='-' ){
000566        esign = -1;
000567        z+=incr;
000568      }else if( *z=='+' ){
000569        z+=incr;
000570      }
000571      /* copy digits to exponent */
000572      while( z<zEnd && sqlite3Isdigit(*z) ){
000573        e = e<10000 ? (e*10 + (*z - '0')) : 10000;
000574        z+=incr;
000575        eValid = 1;
000576      }
000577    }
000578  
000579    /* skip trailing spaces */
000580    while( z<zEnd && sqlite3Isspace(*z) ) z+=incr;
000581  
000582  do_atof_calc:
000583    /* Zero is a special case */
000584    if( s==0 ){
000585      *pResult = sign<0 ? -0.0 : +0.0;
000586      goto atof_return;
000587    }
000588  
000589    /* adjust exponent by d, and update sign */
000590    e = (e*esign) + d;
000591  
000592    /* Try to adjust the exponent to make it smaller */
000593    while( e>0 && s<(LARGEST_UINT64/10) ){
000594      s *= 10;
000595      e--;
000596    }
000597    while( e<0 && (s%10)==0 ){
000598      s /= 10;
000599      e++;
000600    }
000601  
000602    if( e==0 ){
000603      *pResult = s;
000604    }else if( sqlite3Config.bUseLongDouble ){
000605      LONGDOUBLE_TYPE r = (LONGDOUBLE_TYPE)s;
000606      if( e>0 ){
000607        while( e>=100  ){ e-=100; r *= 1.0e+100L; }
000608        while( e>=10   ){ e-=10;  r *= 1.0e+10L;  }
000609        while( e>=1    ){ e-=1;   r *= 1.0e+01L;  }
000610      }else{
000611        while( e<=-100 ){ e+=100; r *= 1.0e-100L; }
000612        while( e<=-10  ){ e+=10;  r *= 1.0e-10L;  }
000613        while( e<=-1   ){ e+=1;   r *= 1.0e-01L;  }
000614      }
000615      assert( r>=0.0 );
000616      if( r>+1.7976931348623157081452742373e+308L ){
000617  #ifdef INFINITY
000618        *pResult = +INFINITY;
000619  #else
000620        *pResult = 1.0e308*10.0;
000621  #endif
000622      }else{
000623        *pResult = (double)r;
000624      }
000625    }else{
000626      double rr[2];
000627      u64 s2;
000628      rr[0] = (double)s;
000629      s2 = (u64)rr[0];
000630  #if defined(_MSC_VER) && _MSC_VER<1700
000631      if( s2==0x8000000000000000LL ){ s2 = 2*(u64)(0.5*rr[0]); }
000632  #endif
000633      rr[1] = s>=s2 ? (double)(s - s2) : -(double)(s2 - s);
000634      if( e>0 ){
000635        while( e>=100  ){
000636          e -= 100;
000637          dekkerMul2(rr, 1.0e+100, -1.5902891109759918046e+83);
000638        }
000639        while( e>=10   ){
000640          e -= 10;
000641          dekkerMul2(rr, 1.0e+10, 0.0);
000642        }
000643        while( e>=1    ){
000644          e -= 1;
000645          dekkerMul2(rr, 1.0e+01, 0.0);
000646        }
000647      }else{
000648        while( e<=-100 ){
000649          e += 100;
000650          dekkerMul2(rr, 1.0e-100, -1.99918998026028836196e-117);
000651        }
000652        while( e<=-10  ){
000653          e += 10;
000654          dekkerMul2(rr, 1.0e-10, -3.6432197315497741579e-27);
000655        }
000656        while( e<=-1   ){
000657          e += 1;
000658          dekkerMul2(rr, 1.0e-01, -5.5511151231257827021e-18);
000659        }
000660      }
000661      *pResult = rr[0]+rr[1];
000662      if( sqlite3IsNaN(*pResult) ) *pResult = 1e300*1e300;
000663    }
000664    if( sign<0 ) *pResult = -*pResult;
000665    assert( !sqlite3IsNaN(*pResult) );
000666  
000667  atof_return:
000668    /* return true if number and no extra non-whitespace characters after */
000669    if( z==zEnd && nDigit>0 && eValid && eType>0 ){
000670      return eType;
000671    }else if( eType>=2 && (eType==3 || eValid) && nDigit>0 ){
000672      return -1;
000673    }else{
000674      return 0;
000675    }
000676  #else
000677    return !sqlite3Atoi64(z, pResult, length, enc);
000678  #endif /* SQLITE_OMIT_FLOATING_POINT */
000679  }
000680  #if defined(_MSC_VER)
000681  #pragma warning(default : 4756)
000682  #endif
000683  
000684  /*
000685  ** Render an signed 64-bit integer as text.  Store the result in zOut[] and
000686  ** return the length of the string that was stored, in bytes.  The value
000687  ** returned does not include the zero terminator at the end of the output
000688  ** string.
000689  **
000690  ** The caller must ensure that zOut[] is at least 21 bytes in size.
000691  */
000692  int sqlite3Int64ToText(i64 v, char *zOut){
000693    int i;
000694    u64 x;
000695    char zTemp[22];
000696    if( v<0 ){
000697      x = (v==SMALLEST_INT64) ? ((u64)1)<<63 : (u64)-v;
000698    }else{
000699      x = v;
000700    }
000701    i = sizeof(zTemp)-2;
000702    zTemp[sizeof(zTemp)-1] = 0;
000703    while( 1 /*exit-by-break*/ ){
000704      zTemp[i] = (x%10) + '0';
000705      x = x/10;
000706      if( x==0 ) break;
000707      i--;
000708    };
000709    if( v<0 ) zTemp[--i] = '-';
000710    memcpy(zOut, &zTemp[i], sizeof(zTemp)-i);
000711    return sizeof(zTemp)-1-i;
000712  }
000713  
000714  /*
000715  ** Compare the 19-character string zNum against the text representation
000716  ** value 2^63:  9223372036854775808.  Return negative, zero, or positive
000717  ** if zNum is less than, equal to, or greater than the string.
000718  ** Note that zNum must contain exactly 19 characters.
000719  **
000720  ** Unlike memcmp() this routine is guaranteed to return the difference
000721  ** in the values of the last digit if the only difference is in the
000722  ** last digit.  So, for example,
000723  **
000724  **      compare2pow63("9223372036854775800", 1)
000725  **
000726  ** will return -8.
000727  */
000728  static int compare2pow63(const char *zNum, int incr){
000729    int c = 0;
000730    int i;
000731                      /* 012345678901234567 */
000732    const char *pow63 = "922337203685477580";
000733    for(i=0; c==0 && i<18; i++){
000734      c = (zNum[i*incr]-pow63[i])*10;
000735    }
000736    if( c==0 ){
000737      c = zNum[18*incr] - '8';
000738      testcase( c==(-1) );
000739      testcase( c==0 );
000740      testcase( c==(+1) );
000741    }
000742    return c;
000743  }
000744  
000745  /*
000746  ** Convert zNum to a 64-bit signed integer.  zNum must be decimal. This
000747  ** routine does *not* accept hexadecimal notation.
000748  **
000749  ** Returns:
000750  **
000751  **    -1    Not even a prefix of the input text looks like an integer
000752  **     0    Successful transformation.  Fits in a 64-bit signed integer.
000753  **     1    Excess non-space text after the integer value
000754  **     2    Integer too large for a 64-bit signed integer or is malformed
000755  **     3    Special case of 9223372036854775808
000756  **
000757  ** length is the number of bytes in the string (bytes, not characters).
000758  ** The string is not necessarily zero-terminated.  The encoding is
000759  ** given by enc.
000760  */
000761  int sqlite3Atoi64(const char *zNum, i64 *pNum, int length, u8 enc){
000762    int incr;
000763    u64 u = 0;
000764    int neg = 0; /* assume positive */
000765    int i;
000766    int c = 0;
000767    int nonNum = 0;  /* True if input contains UTF16 with high byte non-zero */
000768    int rc;          /* Baseline return code */
000769    const char *zStart;
000770    const char *zEnd = zNum + length;
000771    assert( enc==SQLITE_UTF8 || enc==SQLITE_UTF16LE || enc==SQLITE_UTF16BE );
000772    if( enc==SQLITE_UTF8 ){
000773      incr = 1;
000774    }else{
000775      incr = 2;
000776      length &= ~1;
000777      assert( SQLITE_UTF16LE==2 && SQLITE_UTF16BE==3 );
000778      for(i=3-enc; i<length && zNum[i]==0; i+=2){}
000779      nonNum = i<length;
000780      zEnd = &zNum[i^1];
000781      zNum += (enc&1);
000782    }
000783    while( zNum<zEnd && sqlite3Isspace(*zNum) ) zNum+=incr;
000784    if( zNum<zEnd ){
000785      if( *zNum=='-' ){
000786        neg = 1;
000787        zNum+=incr;
000788      }else if( *zNum=='+' ){
000789        zNum+=incr;
000790      }
000791    }
000792    zStart = zNum;
000793    while( zNum<zEnd && zNum[0]=='0' ){ zNum+=incr; } /* Skip leading zeros. */
000794    for(i=0; &zNum[i]<zEnd && (c=zNum[i])>='0' && c<='9'; i+=incr){
000795      u = u*10 + c - '0';
000796    }
000797    testcase( i==18*incr );
000798    testcase( i==19*incr );
000799    testcase( i==20*incr );
000800    if( u>LARGEST_INT64 ){
000801      /* This test and assignment is needed only to suppress UB warnings
000802      ** from clang and -fsanitize=undefined.  This test and assignment make
000803      ** the code a little larger and slower, and no harm comes from omitting
000804      ** them, but we must appease the undefined-behavior pharisees. */
000805      *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
000806    }else if( neg ){
000807      *pNum = -(i64)u;
000808    }else{
000809      *pNum = (i64)u;
000810    }
000811    rc = 0;
000812    if( i==0 && zStart==zNum ){    /* No digits */
000813      rc = -1;
000814    }else if( nonNum ){            /* UTF16 with high-order bytes non-zero */
000815      rc = 1;
000816    }else if( &zNum[i]<zEnd ){     /* Extra bytes at the end */
000817      int jj = i;
000818      do{
000819        if( !sqlite3Isspace(zNum[jj]) ){
000820          rc = 1;          /* Extra non-space text after the integer */
000821          break;
000822        }
000823        jj += incr;
000824      }while( &zNum[jj]<zEnd );
000825    }
000826    if( i<19*incr ){
000827      /* Less than 19 digits, so we know that it fits in 64 bits */
000828      assert( u<=LARGEST_INT64 );
000829      return rc;
000830    }else{
000831      /* zNum is a 19-digit numbers.  Compare it against 9223372036854775808. */
000832      c = i>19*incr ? 1 : compare2pow63(zNum, incr);
000833      if( c<0 ){
000834        /* zNum is less than 9223372036854775808 so it fits */
000835        assert( u<=LARGEST_INT64 );
000836        return rc;
000837      }else{
000838        *pNum = neg ? SMALLEST_INT64 : LARGEST_INT64;
000839        if( c>0 ){
000840          /* zNum is greater than 9223372036854775808 so it overflows */
000841          return 2;
000842        }else{
000843          /* zNum is exactly 9223372036854775808.  Fits if negative.  The
000844          ** special case 2 overflow if positive */
000845          assert( u-1==LARGEST_INT64 );
000846          return neg ? rc : 3;
000847        }
000848      }
000849    }
000850  }
000851  
000852  /*
000853  ** Transform a UTF-8 integer literal, in either decimal or hexadecimal,
000854  ** into a 64-bit signed integer.  This routine accepts hexadecimal literals,
000855  ** whereas sqlite3Atoi64() does not.
000856  **
000857  ** Returns:
000858  **
000859  **     0    Successful transformation.  Fits in a 64-bit signed integer.
000860  **     1    Excess text after the integer value
000861  **     2    Integer too large for a 64-bit signed integer or is malformed
000862  **     3    Special case of 9223372036854775808
000863  */
000864  int sqlite3DecOrHexToI64(const char *z, i64 *pOut){
000865  #ifndef SQLITE_OMIT_HEX_INTEGER
000866    if( z[0]=='0'
000867     && (z[1]=='x' || z[1]=='X')
000868    ){
000869      u64 u = 0;
000870      int i, k;
000871      for(i=2; z[i]=='0'; i++){}
000872      for(k=i; sqlite3Isxdigit(z[k]); k++){
000873        u = u*16 + sqlite3HexToInt(z[k]);
000874      }
000875      memcpy(pOut, &u, 8);
000876      if( k-i>16 ) return 2;
000877      if( z[k]!=0 ) return 1;
000878      return 0;
000879    }else
000880  #endif /* SQLITE_OMIT_HEX_INTEGER */
000881    {
000882      int n = (int)(0x3fffffff&strspn(z,"+- \n\t0123456789"));
000883      if( z[n] ) n++;
000884      return sqlite3Atoi64(z, pOut, n, SQLITE_UTF8);
000885    }
000886  }
000887  
000888  /*
000889  ** If zNum represents an integer that will fit in 32-bits, then set
000890  ** *pValue to that integer and return true.  Otherwise return false.
000891  **
000892  ** This routine accepts both decimal and hexadecimal notation for integers.
000893  **
000894  ** Any non-numeric characters that following zNum are ignored.
000895  ** This is different from sqlite3Atoi64() which requires the
000896  ** input number to be zero-terminated.
000897  */
000898  int sqlite3GetInt32(const char *zNum, int *pValue){
000899    sqlite_int64 v = 0;
000900    int i, c;
000901    int neg = 0;
000902    if( zNum[0]=='-' ){
000903      neg = 1;
000904      zNum++;
000905    }else if( zNum[0]=='+' ){
000906      zNum++;
000907    }
000908  #ifndef SQLITE_OMIT_HEX_INTEGER
000909    else if( zNum[0]=='0'
000910          && (zNum[1]=='x' || zNum[1]=='X')
000911          && sqlite3Isxdigit(zNum[2])
000912    ){
000913      u32 u = 0;
000914      zNum += 2;
000915      while( zNum[0]=='0' ) zNum++;
000916      for(i=0; i<8 && sqlite3Isxdigit(zNum[i]); i++){
000917        u = u*16 + sqlite3HexToInt(zNum[i]);
000918      }
000919      if( (u&0x80000000)==0 && sqlite3Isxdigit(zNum[i])==0 ){
000920        memcpy(pValue, &u, 4);
000921        return 1;
000922      }else{
000923        return 0;
000924      }
000925    }
000926  #endif
000927    if( !sqlite3Isdigit(zNum[0]) ) return 0;
000928    while( zNum[0]=='0' ) zNum++;
000929    for(i=0; i<11 && (c = zNum[i] - '0')>=0 && c<=9; i++){
000930      v = v*10 + c;
000931    }
000932  
000933    /* The longest decimal representation of a 32 bit integer is 10 digits:
000934    **
000935    **             1234567890
000936    **     2^31 -> 2147483648
000937    */
000938    testcase( i==10 );
000939    if( i>10 ){
000940      return 0;
000941    }
000942    testcase( v-neg==2147483647 );
000943    if( v-neg>2147483647 ){
000944      return 0;
000945    }
000946    if( neg ){
000947      v = -v;
000948    }
000949    *pValue = (int)v;
000950    return 1;
000951  }
000952  
000953  /*
000954  ** Return a 32-bit integer value extracted from a string.  If the
000955  ** string is not an integer, just return 0.
000956  */
000957  int sqlite3Atoi(const char *z){
000958    int x = 0;
000959    sqlite3GetInt32(z, &x);
000960    return x;
000961  }
000962  
000963  /*
000964  ** Decode a floating-point value into an approximate decimal
000965  ** representation.
000966  **
000967  ** Round the decimal representation to n significant digits if
000968  ** n is positive.  Or round to -n signficant digits after the
000969  ** decimal point if n is negative.  No rounding is performed if
000970  ** n is zero.
000971  **
000972  ** The significant digits of the decimal representation are
000973  ** stored in p->z[] which is a often (but not always) a pointer
000974  ** into the middle of p->zBuf[].  There are p->n significant digits.
000975  ** The p->z[] array is *not* zero-terminated.
000976  */
000977  void sqlite3FpDecode(FpDecode *p, double r, int iRound, int mxRound){
000978    int i;
000979    u64 v;
000980    int e, exp = 0;
000981    p->isSpecial = 0;
000982    p->z = p->zBuf;
000983  
000984    /* Convert negative numbers to positive.  Deal with Infinity, 0.0, and
000985    ** NaN. */
000986    if( r<0.0 ){
000987      p->sign = '-';
000988      r = -r;
000989    }else if( r==0.0 ){
000990      p->sign = '+';
000991      p->n = 1;
000992      p->iDP = 1;
000993      p->z = "0";
000994      return;
000995    }else{
000996      p->sign = '+';
000997    }
000998    memcpy(&v,&r,8);
000999    e = v>>52;
001000    if( (e&0x7ff)==0x7ff ){
001001      p->isSpecial = 1 + (v!=0x7ff0000000000000LL);
001002      p->n = 0;
001003      p->iDP = 0;
001004      return;
001005    }
001006  
001007    /* Multiply r by powers of ten until it lands somewhere in between
001008    ** 1.0e+19 and 1.0e+17.
001009    */
001010    if( sqlite3Config.bUseLongDouble ){
001011      LONGDOUBLE_TYPE rr = r;
001012      if( rr>=1.0e+19 ){
001013        while( rr>=1.0e+119L ){ exp+=100; rr *= 1.0e-100L; }
001014        while( rr>=1.0e+29L  ){ exp+=10;  rr *= 1.0e-10L;  }
001015        while( rr>=1.0e+19L  ){ exp++;    rr *= 1.0e-1L;   }
001016      }else{
001017        while( rr<1.0e-97L   ){ exp-=100; rr *= 1.0e+100L; }
001018        while( rr<1.0e+07L   ){ exp-=10;  rr *= 1.0e+10L;  }
001019        while( rr<1.0e+17L   ){ exp--;    rr *= 1.0e+1L;   }
001020      }
001021      v = (u64)rr;
001022    }else{
001023      /* If high-precision floating point is not available using "long double",
001024      ** then use Dekker-style double-double computation to increase the
001025      ** precision.
001026      **
001027      ** The error terms on constants like 1.0e+100 computed using the
001028      ** decimal extension, for example as follows:
001029      **
001030      **   SELECT decimal_exp(decimal_sub('1.0e+100',decimal(1.0e+100)));
001031      */
001032      double rr[2];
001033      rr[0] = r;
001034      rr[1] = 0.0;
001035      if( rr[0]>9.223372036854774784e+18 ){
001036        while( rr[0]>9.223372036854774784e+118 ){
001037          exp += 100;
001038          dekkerMul2(rr, 1.0e-100, -1.99918998026028836196e-117);
001039        }
001040        while( rr[0]>9.223372036854774784e+28 ){
001041          exp += 10;
001042          dekkerMul2(rr, 1.0e-10, -3.6432197315497741579e-27);
001043        }
001044        while( rr[0]>9.223372036854774784e+18 ){
001045          exp += 1;
001046          dekkerMul2(rr, 1.0e-01, -5.5511151231257827021e-18);
001047        }
001048      }else{
001049        while( rr[0]<9.223372036854774784e-83  ){
001050          exp -= 100;
001051          dekkerMul2(rr, 1.0e+100, -1.5902891109759918046e+83);
001052        }
001053        while( rr[0]<9.223372036854774784e+07  ){
001054          exp -= 10;
001055          dekkerMul2(rr, 1.0e+10, 0.0);
001056        }
001057        while( rr[0]<9.22337203685477478e+17  ){
001058          exp -= 1;
001059          dekkerMul2(rr, 1.0e+01, 0.0);
001060        }
001061      }
001062      v = rr[1]<0.0 ? (u64)rr[0]-(u64)(-rr[1]) : (u64)rr[0]+(u64)rr[1];
001063    }
001064  
001065  
001066    /* Extract significant digits. */
001067    i = sizeof(p->zBuf)-1;
001068    assert( v>0 );
001069    while( v ){  p->zBuf[i--] = (v%10) + '0'; v /= 10; }
001070    assert( i>=0 && i<sizeof(p->zBuf)-1 );
001071    p->n = sizeof(p->zBuf) - 1 - i;
001072    assert( p->n>0 );
001073    assert( p->n<sizeof(p->zBuf) );
001074    p->iDP = p->n + exp;
001075    if( iRound<=0 ){
001076      iRound = p->iDP - iRound;
001077      if( iRound==0 && p->zBuf[i+1]>='5' ){
001078        iRound = 1;
001079        p->zBuf[i--] = '0';
001080        p->n++;
001081        p->iDP++;
001082      }
001083    }
001084    if( iRound>0 && (iRound<p->n || p->n>mxRound) ){
001085      char *z = &p->zBuf[i+1];
001086      if( iRound>mxRound ) iRound = mxRound;
001087      p->n = iRound;
001088      if( z[iRound]>='5' ){
001089        int j = iRound-1;
001090        while( 1 /*exit-by-break*/ ){
001091          z[j]++;
001092          if( z[j]<='9' ) break;
001093          z[j] = '0';
001094          if( j==0 ){
001095            p->z[i--] = '1';
001096            p->n++;
001097            p->iDP++;
001098            break;
001099          }else{
001100            j--;
001101          }
001102        }
001103      }
001104    }
001105    p->z = &p->zBuf[i+1];
001106    assert( i+p->n < sizeof(p->zBuf) );
001107    while( ALWAYS(p->n>0) && p->z[p->n-1]=='0' ){ p->n--; }
001108  }
001109  
001110  /*
001111  ** Try to convert z into an unsigned 32-bit integer.  Return true on
001112  ** success and false if there is an error.
001113  **
001114  ** Only decimal notation is accepted.
001115  */
001116  int sqlite3GetUInt32(const char *z, u32 *pI){
001117    u64 v = 0;
001118    int i;
001119    for(i=0; sqlite3Isdigit(z[i]); i++){
001120      v = v*10 + z[i] - '0';
001121      if( v>4294967296LL ){ *pI = 0; return 0; }
001122    }
001123    if( i==0 || z[i]!=0 ){ *pI = 0; return 0; }
001124    *pI = (u32)v;
001125    return 1;
001126  }
001127  
001128  /*
001129  ** The variable-length integer encoding is as follows:
001130  **
001131  ** KEY:
001132  **         A = 0xxxxxxx    7 bits of data and one flag bit
001133  **         B = 1xxxxxxx    7 bits of data and one flag bit
001134  **         C = xxxxxxxx    8 bits of data
001135  **
001136  **  7 bits - A
001137  ** 14 bits - BA
001138  ** 21 bits - BBA
001139  ** 28 bits - BBBA
001140  ** 35 bits - BBBBA
001141  ** 42 bits - BBBBBA
001142  ** 49 bits - BBBBBBA
001143  ** 56 bits - BBBBBBBA
001144  ** 64 bits - BBBBBBBBC
001145  */
001146  
001147  /*
001148  ** Write a 64-bit variable-length integer to memory starting at p[0].
001149  ** The length of data write will be between 1 and 9 bytes.  The number
001150  ** of bytes written is returned.
001151  **
001152  ** A variable-length integer consists of the lower 7 bits of each byte
001153  ** for all bytes that have the 8th bit set and one byte with the 8th
001154  ** bit clear.  Except, if we get to the 9th byte, it stores the full
001155  ** 8 bits and is the last byte.
001156  */
001157  static int SQLITE_NOINLINE putVarint64(unsigned char *p, u64 v){
001158    int i, j, n;
001159    u8 buf[10];
001160    if( v & (((u64)0xff000000)<<32) ){
001161      p[8] = (u8)v;
001162      v >>= 8;
001163      for(i=7; i>=0; i--){
001164        p[i] = (u8)((v & 0x7f) | 0x80);
001165        v >>= 7;
001166      }
001167      return 9;
001168    }   
001169    n = 0;
001170    do{
001171      buf[n++] = (u8)((v & 0x7f) | 0x80);
001172      v >>= 7;
001173    }while( v!=0 );
001174    buf[0] &= 0x7f;
001175    assert( n<=9 );
001176    for(i=0, j=n-1; j>=0; j--, i++){
001177      p[i] = buf[j];
001178    }
001179    return n;
001180  }
001181  int sqlite3PutVarint(unsigned char *p, u64 v){
001182    if( v<=0x7f ){
001183      p[0] = v&0x7f;
001184      return 1;
001185    }
001186    if( v<=0x3fff ){
001187      p[0] = ((v>>7)&0x7f)|0x80;
001188      p[1] = v&0x7f;
001189      return 2;
001190    }
001191    return putVarint64(p,v);
001192  }
001193  
001194  /*
001195  ** Bitmasks used by sqlite3GetVarint().  These precomputed constants
001196  ** are defined here rather than simply putting the constant expressions
001197  ** inline in order to work around bugs in the RVT compiler.
001198  **
001199  ** SLOT_2_0     A mask for  (0x7f<<14) | 0x7f
001200  **
001201  ** SLOT_4_2_0   A mask for  (0x7f<<28) | SLOT_2_0
001202  */
001203  #define SLOT_2_0     0x001fc07f
001204  #define SLOT_4_2_0   0xf01fc07f
001205  
001206  
001207  /*
001208  ** Read a 64-bit variable-length integer from memory starting at p[0].
001209  ** Return the number of bytes read.  The value is stored in *v.
001210  */
001211  u8 sqlite3GetVarint(const unsigned char *p, u64 *v){
001212    u32 a,b,s;
001213  
001214    if( ((signed char*)p)[0]>=0 ){
001215      *v = *p;
001216      return 1;
001217    }
001218    if( ((signed char*)p)[1]>=0 ){
001219      *v = ((u32)(p[0]&0x7f)<<7) | p[1];
001220      return 2;
001221    }
001222  
001223    /* Verify that constants are precomputed correctly */
001224    assert( SLOT_2_0 == ((0x7f<<14) | (0x7f)) );
001225    assert( SLOT_4_2_0 == ((0xfU<<28) | (0x7f<<14) | (0x7f)) );
001226  
001227    a = ((u32)p[0])<<14;
001228    b = p[1];
001229    p += 2;
001230    a |= *p;
001231    /* a: p0<<14 | p2 (unmasked) */
001232    if (!(a&0x80))
001233    {
001234      a &= SLOT_2_0;
001235      b &= 0x7f;
001236      b = b<<7;
001237      a |= b;
001238      *v = a;
001239      return 3;
001240    }
001241  
001242    /* CSE1 from below */
001243    a &= SLOT_2_0;
001244    p++;
001245    b = b<<14;
001246    b |= *p;
001247    /* b: p1<<14 | p3 (unmasked) */
001248    if (!(b&0x80))
001249    {
001250      b &= SLOT_2_0;
001251      /* moved CSE1 up */
001252      /* a &= (0x7f<<14)|(0x7f); */
001253      a = a<<7;
001254      a |= b;
001255      *v = a;
001256      return 4;
001257    }
001258  
001259    /* a: p0<<14 | p2 (masked) */
001260    /* b: p1<<14 | p3 (unmasked) */
001261    /* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
001262    /* moved CSE1 up */
001263    /* a &= (0x7f<<14)|(0x7f); */
001264    b &= SLOT_2_0;
001265    s = a;
001266    /* s: p0<<14 | p2 (masked) */
001267  
001268    p++;
001269    a = a<<14;
001270    a |= *p;
001271    /* a: p0<<28 | p2<<14 | p4 (unmasked) */
001272    if (!(a&0x80))
001273    {
001274      /* we can skip these cause they were (effectively) done above
001275      ** while calculating s */
001276      /* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
001277      /* b &= (0x7f<<14)|(0x7f); */
001278      b = b<<7;
001279      a |= b;
001280      s = s>>18;
001281      *v = ((u64)s)<<32 | a;
001282      return 5;
001283    }
001284  
001285    /* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
001286    s = s<<7;
001287    s |= b;
001288    /* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
001289  
001290    p++;
001291    b = b<<14;
001292    b |= *p;
001293    /* b: p1<<28 | p3<<14 | p5 (unmasked) */
001294    if (!(b&0x80))
001295    {
001296      /* we can skip this cause it was (effectively) done above in calc'ing s */
001297      /* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
001298      a &= SLOT_2_0;
001299      a = a<<7;
001300      a |= b;
001301      s = s>>18;
001302      *v = ((u64)s)<<32 | a;
001303      return 6;
001304    }
001305  
001306    p++;
001307    a = a<<14;
001308    a |= *p;
001309    /* a: p2<<28 | p4<<14 | p6 (unmasked) */
001310    if (!(a&0x80))
001311    {
001312      a &= SLOT_4_2_0;
001313      b &= SLOT_2_0;
001314      b = b<<7;
001315      a |= b;
001316      s = s>>11;
001317      *v = ((u64)s)<<32 | a;
001318      return 7;
001319    }
001320  
001321    /* CSE2 from below */
001322    a &= SLOT_2_0;
001323    p++;
001324    b = b<<14;
001325    b |= *p;
001326    /* b: p3<<28 | p5<<14 | p7 (unmasked) */
001327    if (!(b&0x80))
001328    {
001329      b &= SLOT_4_2_0;
001330      /* moved CSE2 up */
001331      /* a &= (0x7f<<14)|(0x7f); */
001332      a = a<<7;
001333      a |= b;
001334      s = s>>4;
001335      *v = ((u64)s)<<32 | a;
001336      return 8;
001337    }
001338  
001339    p++;
001340    a = a<<15;
001341    a |= *p;
001342    /* a: p4<<29 | p6<<15 | p8 (unmasked) */
001343  
001344    /* moved CSE2 up */
001345    /* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
001346    b &= SLOT_2_0;
001347    b = b<<8;
001348    a |= b;
001349  
001350    s = s<<4;
001351    b = p[-4];
001352    b &= 0x7f;
001353    b = b>>3;
001354    s |= b;
001355  
001356    *v = ((u64)s)<<32 | a;
001357  
001358    return 9;
001359  }
001360  
001361  /*
001362  ** Read a 32-bit variable-length integer from memory starting at p[0].
001363  ** Return the number of bytes read.  The value is stored in *v.
001364  **
001365  ** If the varint stored in p[0] is larger than can fit in a 32-bit unsigned
001366  ** integer, then set *v to 0xffffffff.
001367  **
001368  ** A MACRO version, getVarint32, is provided which inlines the
001369  ** single-byte case.  All code should use the MACRO version as
001370  ** this function assumes the single-byte case has already been handled.
001371  */
001372  u8 sqlite3GetVarint32(const unsigned char *p, u32 *v){
001373    u64 v64;
001374    u8 n;
001375  
001376    /* Assume that the single-byte case has already been handled by
001377    ** the getVarint32() macro */
001378    assert( (p[0] & 0x80)!=0 );
001379  
001380    if( (p[1] & 0x80)==0 ){
001381      /* This is the two-byte case */
001382      *v = ((p[0]&0x7f)<<7) | p[1];
001383      return 2;
001384    }
001385    if( (p[2] & 0x80)==0 ){
001386      /* This is the three-byte case */
001387      *v = ((p[0]&0x7f)<<14) | ((p[1]&0x7f)<<7) | p[2];
001388      return 3;
001389    }
001390    /* four or more bytes */
001391    n = sqlite3GetVarint(p, &v64);
001392    assert( n>3 && n<=9 );
001393    if( (v64 & SQLITE_MAX_U32)!=v64 ){
001394      *v = 0xffffffff;
001395    }else{
001396      *v = (u32)v64;
001397    }
001398    return n;
001399  }
001400  
001401  /*
001402  ** Return the number of bytes that will be needed to store the given
001403  ** 64-bit integer.
001404  */
001405  int sqlite3VarintLen(u64 v){
001406    int i;
001407    for(i=1; (v >>= 7)!=0; i++){ assert( i<10 ); }
001408    return i;
001409  }
001410  
001411  
001412  /*
001413  ** Read or write a four-byte big-endian integer value.
001414  */
001415  u32 sqlite3Get4byte(const u8 *p){
001416  #if SQLITE_BYTEORDER==4321
001417    u32 x;
001418    memcpy(&x,p,4);
001419    return x;
001420  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
001421    u32 x;
001422    memcpy(&x,p,4);
001423    return __builtin_bswap32(x);
001424  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
001425    u32 x;
001426    memcpy(&x,p,4);
001427    return _byteswap_ulong(x);
001428  #else
001429    testcase( p[0]&0x80 );
001430    return ((unsigned)p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
001431  #endif
001432  }
001433  void sqlite3Put4byte(unsigned char *p, u32 v){
001434  #if SQLITE_BYTEORDER==4321
001435    memcpy(p,&v,4);
001436  #elif SQLITE_BYTEORDER==1234 && GCC_VERSION>=4003000
001437    u32 x = __builtin_bswap32(v);
001438    memcpy(p,&x,4);
001439  #elif SQLITE_BYTEORDER==1234 && MSVC_VERSION>=1300
001440    u32 x = _byteswap_ulong(v);
001441    memcpy(p,&x,4);
001442  #else
001443    p[0] = (u8)(v>>24);
001444    p[1] = (u8)(v>>16);
001445    p[2] = (u8)(v>>8);
001446    p[3] = (u8)v;
001447  #endif
001448  }
001449  
001450  
001451  
001452  /*
001453  ** Translate a single byte of Hex into an integer.
001454  ** This routine only works if h really is a valid hexadecimal
001455  ** character:  0..9a..fA..F
001456  */
001457  u8 sqlite3HexToInt(int h){
001458    assert( (h>='0' && h<='9') ||  (h>='a' && h<='f') ||  (h>='A' && h<='F') );
001459  #ifdef SQLITE_ASCII
001460    h += 9*(1&(h>>6));
001461  #endif
001462  #ifdef SQLITE_EBCDIC
001463    h += 9*(1&~(h>>4));
001464  #endif
001465    return (u8)(h & 0xf);
001466  }
001467  
001468  #if !defined(SQLITE_OMIT_BLOB_LITERAL)
001469  /*
001470  ** Convert a BLOB literal of the form "x'hhhhhh'" into its binary
001471  ** value.  Return a pointer to its binary value.  Space to hold the
001472  ** binary value has been obtained from malloc and must be freed by
001473  ** the calling routine.
001474  */
001475  void *sqlite3HexToBlob(sqlite3 *db, const char *z, int n){
001476    char *zBlob;
001477    int i;
001478  
001479    zBlob = (char *)sqlite3DbMallocRawNN(db, n/2 + 1);
001480    n--;
001481    if( zBlob ){
001482      for(i=0; i<n; i+=2){
001483        zBlob[i/2] = (sqlite3HexToInt(z[i])<<4) | sqlite3HexToInt(z[i+1]);
001484      }
001485      zBlob[i/2] = 0;
001486    }
001487    return zBlob;
001488  }
001489  #endif /* !SQLITE_OMIT_BLOB_LITERAL */
001490  
001491  /*
001492  ** Log an error that is an API call on a connection pointer that should
001493  ** not have been used.  The "type" of connection pointer is given as the
001494  ** argument.  The zType is a word like "NULL" or "closed" or "invalid".
001495  */
001496  static void logBadConnection(const char *zType){
001497    sqlite3_log(SQLITE_MISUSE,
001498       "API call with %s database connection pointer",
001499       zType
001500    );
001501  }
001502  
001503  /*
001504  ** Check to make sure we have a valid db pointer.  This test is not
001505  ** foolproof but it does provide some measure of protection against
001506  ** misuse of the interface such as passing in db pointers that are
001507  ** NULL or which have been previously closed.  If this routine returns
001508  ** 1 it means that the db pointer is valid and 0 if it should not be
001509  ** dereferenced for any reason.  The calling function should invoke
001510  ** SQLITE_MISUSE immediately.
001511  **
001512  ** sqlite3SafetyCheckOk() requires that the db pointer be valid for
001513  ** use.  sqlite3SafetyCheckSickOrOk() allows a db pointer that failed to
001514  ** open properly and is not fit for general use but which can be
001515  ** used as an argument to sqlite3_errmsg() or sqlite3_close().
001516  */
001517  int sqlite3SafetyCheckOk(sqlite3 *db){
001518    u8 eOpenState;
001519    if( db==0 ){
001520      logBadConnection("NULL");
001521      return 0;
001522    }
001523    eOpenState = db->eOpenState;
001524    if( eOpenState!=SQLITE_STATE_OPEN ){
001525      if( sqlite3SafetyCheckSickOrOk(db) ){
001526        testcase( sqlite3GlobalConfig.xLog!=0 );
001527        logBadConnection("unopened");
001528      }
001529      return 0;
001530    }else{
001531      return 1;
001532    }
001533  }
001534  int sqlite3SafetyCheckSickOrOk(sqlite3 *db){
001535    u8 eOpenState;
001536    eOpenState = db->eOpenState;
001537    if( eOpenState!=SQLITE_STATE_SICK &&
001538        eOpenState!=SQLITE_STATE_OPEN &&
001539        eOpenState!=SQLITE_STATE_BUSY ){
001540      testcase( sqlite3GlobalConfig.xLog!=0 );
001541      logBadConnection("invalid");
001542      return 0;
001543    }else{
001544      return 1;
001545    }
001546  }
001547  
001548  /*
001549  ** Attempt to add, subtract, or multiply the 64-bit signed value iB against
001550  ** the other 64-bit signed integer at *pA and store the result in *pA.
001551  ** Return 0 on success.  Or if the operation would have resulted in an
001552  ** overflow, leave *pA unchanged and return 1.
001553  */
001554  int sqlite3AddInt64(i64 *pA, i64 iB){
001555  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001556    return __builtin_add_overflow(*pA, iB, pA);
001557  #else
001558    i64 iA = *pA;
001559    testcase( iA==0 ); testcase( iA==1 );
001560    testcase( iB==-1 ); testcase( iB==0 );
001561    if( iB>=0 ){
001562      testcase( iA>0 && LARGEST_INT64 - iA == iB );
001563      testcase( iA>0 && LARGEST_INT64 - iA == iB - 1 );
001564      if( iA>0 && LARGEST_INT64 - iA < iB ) return 1;
001565    }else{
001566      testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 1 );
001567      testcase( iA<0 && -(iA + LARGEST_INT64) == iB + 2 );
001568      if( iA<0 && -(iA + LARGEST_INT64) > iB + 1 ) return 1;
001569    }
001570    *pA += iB;
001571    return 0;
001572  #endif
001573  }
001574  int sqlite3SubInt64(i64 *pA, i64 iB){
001575  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001576    return __builtin_sub_overflow(*pA, iB, pA);
001577  #else
001578    testcase( iB==SMALLEST_INT64+1 );
001579    if( iB==SMALLEST_INT64 ){
001580      testcase( (*pA)==(-1) ); testcase( (*pA)==0 );
001581      if( (*pA)>=0 ) return 1;
001582      *pA -= iB;
001583      return 0;
001584    }else{
001585      return sqlite3AddInt64(pA, -iB);
001586    }
001587  #endif
001588  }
001589  int sqlite3MulInt64(i64 *pA, i64 iB){
001590  #if GCC_VERSION>=5004000 && !defined(__INTEL_COMPILER)
001591    return __builtin_mul_overflow(*pA, iB, pA);
001592  #else
001593    i64 iA = *pA;
001594    if( iB>0 ){
001595      if( iA>LARGEST_INT64/iB ) return 1;
001596      if( iA<SMALLEST_INT64/iB ) return 1;
001597    }else if( iB<0 ){
001598      if( iA>0 ){
001599        if( iB<SMALLEST_INT64/iA ) return 1;
001600      }else if( iA<0 ){
001601        if( iB==SMALLEST_INT64 ) return 1;
001602        if( iA==SMALLEST_INT64 ) return 1;
001603        if( -iA>LARGEST_INT64/-iB ) return 1;
001604      }
001605    }
001606    *pA = iA*iB;
001607    return 0;
001608  #endif
001609  }
001610  
001611  /*
001612  ** Compute the absolute value of a 32-bit signed integer, of possible.  Or
001613  ** if the integer has a value of -2147483648, return +2147483647
001614  */
001615  int sqlite3AbsInt32(int x){
001616    if( x>=0 ) return x;
001617    if( x==(int)0x80000000 ) return 0x7fffffff;
001618    return -x;
001619  }
001620  
001621  #ifdef SQLITE_ENABLE_8_3_NAMES
001622  /*
001623  ** If SQLITE_ENABLE_8_3_NAMES is set at compile-time and if the database
001624  ** filename in zBaseFilename is a URI with the "8_3_names=1" parameter and
001625  ** if filename in z[] has a suffix (a.k.a. "extension") that is longer than
001626  ** three characters, then shorten the suffix on z[] to be the last three
001627  ** characters of the original suffix.
001628  **
001629  ** If SQLITE_ENABLE_8_3_NAMES is set to 2 at compile-time, then always
001630  ** do the suffix shortening regardless of URI parameter.
001631  **
001632  ** Examples:
001633  **
001634  **     test.db-journal    =>   test.nal
001635  **     test.db-wal        =>   test.wal
001636  **     test.db-shm        =>   test.shm
001637  **     test.db-mj7f3319fa =>   test.9fa
001638  */
001639  void sqlite3FileSuffix3(const char *zBaseFilename, char *z){
001640  #if SQLITE_ENABLE_8_3_NAMES<2
001641    if( sqlite3_uri_boolean(zBaseFilename, "8_3_names", 0) )
001642  #endif
001643    {
001644      int i, sz;
001645      sz = sqlite3Strlen30(z);
001646      for(i=sz-1; i>0 && z[i]!='/' && z[i]!='.'; i--){}
001647      if( z[i]=='.' && ALWAYS(sz>i+4) ) memmove(&z[i+1], &z[sz-3], 4);
001648    }
001649  }
001650  #endif
001651  
001652  /*
001653  ** Find (an approximate) sum of two LogEst values.  This computation is
001654  ** not a simple "+" operator because LogEst is stored as a logarithmic
001655  ** value.
001656  **
001657  */
001658  LogEst sqlite3LogEstAdd(LogEst a, LogEst b){
001659    static const unsigned char x[] = {
001660       10, 10,                         /* 0,1 */
001661        9, 9,                          /* 2,3 */
001662        8, 8,                          /* 4,5 */
001663        7, 7, 7,                       /* 6,7,8 */
001664        6, 6, 6,                       /* 9,10,11 */
001665        5, 5, 5,                       /* 12-14 */
001666        4, 4, 4, 4,                    /* 15-18 */
001667        3, 3, 3, 3, 3, 3,              /* 19-24 */
001668        2, 2, 2, 2, 2, 2, 2,           /* 25-31 */
001669    };
001670    if( a>=b ){
001671      if( a>b+49 ) return a;
001672      if( a>b+31 ) return a+1;
001673      return a+x[a-b];
001674    }else{
001675      if( b>a+49 ) return b;
001676      if( b>a+31 ) return b+1;
001677      return b+x[b-a];
001678    }
001679  }
001680  
001681  /*
001682  ** Convert an integer into a LogEst.  In other words, compute an
001683  ** approximation for 10*log2(x).
001684  */
001685  LogEst sqlite3LogEst(u64 x){
001686    static LogEst a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
001687    LogEst y = 40;
001688    if( x<8 ){
001689      if( x<2 ) return 0;
001690      while( x<8 ){  y -= 10; x <<= 1; }
001691    }else{
001692  #if GCC_VERSION>=5004000
001693      int i = 60 - __builtin_clzll(x);
001694      y += i*10;
001695      x >>= i;
001696  #else
001697      while( x>255 ){ y += 40; x >>= 4; }  /*OPTIMIZATION-IF-TRUE*/
001698      while( x>15 ){  y += 10; x >>= 1; }
001699  #endif
001700    }
001701    return a[x&7] + y - 10;
001702  }
001703  
001704  /*
001705  ** Convert a double into a LogEst
001706  ** In other words, compute an approximation for 10*log2(x).
001707  */
001708  LogEst sqlite3LogEstFromDouble(double x){
001709    u64 a;
001710    LogEst e;
001711    assert( sizeof(x)==8 && sizeof(a)==8 );
001712    if( x<=1 ) return 0;
001713    if( x<=2000000000 ) return sqlite3LogEst((u64)x);
001714    memcpy(&a, &x, 8);
001715    e = (a>>52) - 1022;
001716    return e*10;
001717  }
001718  
001719  /*
001720  ** Convert a LogEst into an integer.
001721  */
001722  u64 sqlite3LogEstToInt(LogEst x){
001723    u64 n;
001724    n = x%10;
001725    x /= 10;
001726    if( n>=5 ) n -= 2;
001727    else if( n>=1 ) n -= 1;
001728    if( x>60 ) return (u64)LARGEST_INT64;
001729    return x>=3 ? (n+8)<<(x-3) : (n+8)>>(3-x);
001730  }
001731  
001732  /*
001733  ** Add a new name/number pair to a VList.  This might require that the
001734  ** VList object be reallocated, so return the new VList.  If an OOM
001735  ** error occurs, the original VList returned and the
001736  ** db->mallocFailed flag is set.
001737  **
001738  ** A VList is really just an array of integers.  To destroy a VList,
001739  ** simply pass it to sqlite3DbFree().
001740  **
001741  ** The first integer is the number of integers allocated for the whole
001742  ** VList.  The second integer is the number of integers actually used.
001743  ** Each name/number pair is encoded by subsequent groups of 3 or more
001744  ** integers.
001745  **
001746  ** Each name/number pair starts with two integers which are the numeric
001747  ** value for the pair and the size of the name/number pair, respectively.
001748  ** The text name overlays one or more following integers.  The text name
001749  ** is always zero-terminated.
001750  **
001751  ** Conceptually:
001752  **
001753  **    struct VList {
001754  **      int nAlloc;   // Number of allocated slots
001755  **      int nUsed;    // Number of used slots
001756  **      struct VListEntry {
001757  **        int iValue;    // Value for this entry
001758  **        int nSlot;     // Slots used by this entry
001759  **        // ... variable name goes here
001760  **      } a[0];
001761  **    }
001762  **
001763  ** During code generation, pointers to the variable names within the
001764  ** VList are taken.  When that happens, nAlloc is set to zero as an
001765  ** indication that the VList may never again be enlarged, since the
001766  ** accompanying realloc() would invalidate the pointers.
001767  */
001768  VList *sqlite3VListAdd(
001769    sqlite3 *db,           /* The database connection used for malloc() */
001770    VList *pIn,            /* The input VList.  Might be NULL */
001771    const char *zName,     /* Name of symbol to add */
001772    int nName,             /* Bytes of text in zName */
001773    int iVal               /* Value to associate with zName */
001774  ){
001775    int nInt;              /* number of sizeof(int) objects needed for zName */
001776    char *z;               /* Pointer to where zName will be stored */
001777    int i;                 /* Index in pIn[] where zName is stored */
001778  
001779    nInt = nName/4 + 3;
001780    assert( pIn==0 || pIn[0]>=3 );  /* Verify ok to add new elements */
001781    if( pIn==0 || pIn[1]+nInt > pIn[0] ){
001782      /* Enlarge the allocation */
001783      sqlite3_int64 nAlloc = (pIn ? 2*(sqlite3_int64)pIn[0] : 10) + nInt;
001784      VList *pOut = sqlite3DbRealloc(db, pIn, nAlloc*sizeof(int));
001785      if( pOut==0 ) return pIn;
001786      if( pIn==0 ) pOut[1] = 2;
001787      pIn = pOut;
001788      pIn[0] = nAlloc;
001789    }
001790    i = pIn[1];
001791    pIn[i] = iVal;
001792    pIn[i+1] = nInt;
001793    z = (char*)&pIn[i+2];
001794    pIn[1] = i+nInt;
001795    assert( pIn[1]<=pIn[0] );
001796    memcpy(z, zName, nName);
001797    z[nName] = 0;
001798    return pIn;
001799  }
001800  
001801  /*
001802  ** Return a pointer to the name of a variable in the given VList that
001803  ** has the value iVal.  Or return a NULL if there is no such variable in
001804  ** the list
001805  */
001806  const char *sqlite3VListNumToName(VList *pIn, int iVal){
001807    int i, mx;
001808    if( pIn==0 ) return 0;
001809    mx = pIn[1];
001810    i = 2;
001811    do{
001812      if( pIn[i]==iVal ) return (char*)&pIn[i+2];
001813      i += pIn[i+1];
001814    }while( i<mx );
001815    return 0;
001816  }
001817  
001818  /*
001819  ** Return the number of the variable named zName, if it is in VList.
001820  ** or return 0 if there is no such variable.
001821  */
001822  int sqlite3VListNameToNum(VList *pIn, const char *zName, int nName){
001823    int i, mx;
001824    if( pIn==0 ) return 0;
001825    mx = pIn[1];
001826    i = 2;
001827    do{
001828      const char *z = (const char*)&pIn[i+2];
001829      if( strncmp(z,zName,nName)==0 && z[nName]==0 ) return pIn[i];
001830      i += pIn[i+1];
001831    }while( i<mx );
001832    return 0;
001833  }
001834  
001835  /*
001836  ** High-resolution hardware timer used for debugging and testing only.
001837  */
001838  #if defined(VDBE_PROFILE)  \
001839   || defined(SQLITE_PERFORMANCE_TRACE) \
001840   || defined(SQLITE_ENABLE_STMT_SCANSTATUS)
001841  # include "hwtime.h"
001842  #endif