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