src/util.c

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