2015-05-30 11:49:58 +00:00
/*
* * 2015 May 30
* *
* * The author disclaims copyright to this source code . In place of
* * a legal notice , here is a blessing :
* *
* * May you do good and not evil .
* * May you find forgiveness for yourself and forgive others .
* * May you share freely , never taking more than you give .
* *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* *
* * Routines for varint serialization and deserialization .
*/
# include "fts5Int.h"
/*
* * This is a copy of the sqlite3GetVarint32 ( ) routine from the SQLite core .
* * Except , this version does handle the single byte case that the core
* * version depends on being handled before its function is called .
*/
int sqlite3Fts5GetVarint32 ( const unsigned char * p , u32 * v ) {
u32 a , b ;
/* The 1-byte case. Overwhelmingly the most common. */
a = * p ;
/* a: p0 (unmasked) */
if ( ! ( a & 0x80 ) )
{
/* Values between 0 and 127 */
* v = a ;
return 1 ;
}
/* The 2-byte case */
p + + ;
b = * p ;
/* b: p1 (unmasked) */
if ( ! ( b & 0x80 ) )
{
/* Values between 128 and 16383 */
a & = 0x7f ;
a = a < < 7 ;
* v = a | b ;
return 2 ;
}
/* The 3-byte case */
p + + ;
a = a < < 14 ;
a | = * p ;
/* a: p0<<14 | p2 (unmasked) */
if ( ! ( a & 0x80 ) )
{
/* Values between 16384 and 2097151 */
a & = ( 0x7f < < 14 ) | ( 0x7f ) ;
b & = 0x7f ;
b = b < < 7 ;
* v = a | b ;
return 3 ;
}
/* A 32-bit varint is used to store size information in btrees.
* * Objects are rarely larger than 2 MiB limit of a 3 - byte varint .
* * A 3 - byte varint is sufficient , for example , to record the size
* * of a 1048569 - byte BLOB or string .
* *
* * We only unroll the first 1 - , 2 - , and 3 - byte cases . The very
* * rare larger cases can be handled by the slower 64 - bit varint
* * routine .
*/
{
u64 v64 ;
u8 n ;
p - = 2 ;
n = sqlite3Fts5GetVarint ( p , & v64 ) ;
2019-01-11 19:27:55 +00:00
* v = ( ( u32 ) v64 ) & 0x7FFFFFFF ;
2015-05-30 11:49:58 +00:00
assert ( n > 3 & & n < = 9 ) ;
return n ;
}
}
/*
* * Bitmasks used by sqlite3GetVarint ( ) . These precomputed constants
* * are defined here rather than simply putting the constant expressions
* * inline in order to work around bugs in the RVT compiler .
* *
* * SLOT_2_0 A mask for ( 0x7f < < 14 ) | 0x7f
* *
* * SLOT_4_2_0 A mask for ( 0x7f < < 28 ) | SLOT_2_0
*/
# define SLOT_2_0 0x001fc07f
# define SLOT_4_2_0 0xf01fc07f
/*
* * Read a 64 - bit variable - length integer from memory starting at p [ 0 ] .
* * Return the number of bytes read . The value is stored in * v .
*/
u8 sqlite3Fts5GetVarint ( const unsigned char * p , u64 * v ) {
u32 a , b , s ;
a = * p ;
/* a: p0 (unmasked) */
if ( ! ( a & 0x80 ) )
{
* v = a ;
return 1 ;
}
p + + ;
b = * p ;
/* b: p1 (unmasked) */
if ( ! ( b & 0x80 ) )
{
a & = 0x7f ;
a = a < < 7 ;
a | = b ;
* v = a ;
return 2 ;
}
/* Verify that constants are precomputed correctly */
assert ( SLOT_2_0 = = ( ( 0x7f < < 14 ) | ( 0x7f ) ) ) ;
assert ( SLOT_4_2_0 = = ( ( 0xfU < < 28 ) | ( 0x7f < < 14 ) | ( 0x7f ) ) ) ;
p + + ;
a = a < < 14 ;
a | = * p ;
/* a: p0<<14 | p2 (unmasked) */
if ( ! ( a & 0x80 ) )
{
a & = SLOT_2_0 ;
b & = 0x7f ;
b = b < < 7 ;
a | = b ;
* v = a ;
return 3 ;
}
/* CSE1 from below */
a & = SLOT_2_0 ;
p + + ;
b = b < < 14 ;
b | = * p ;
/* b: p1<<14 | p3 (unmasked) */
if ( ! ( b & 0x80 ) )
{
b & = SLOT_2_0 ;
/* moved CSE1 up */
/* a &= (0x7f<<14)|(0x7f); */
a = a < < 7 ;
a | = b ;
* v = a ;
return 4 ;
}
/* a: p0<<14 | p2 (masked) */
/* b: p1<<14 | p3 (unmasked) */
/* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
/* moved CSE1 up */
/* a &= (0x7f<<14)|(0x7f); */
b & = SLOT_2_0 ;
s = a ;
/* s: p0<<14 | p2 (masked) */
p + + ;
a = a < < 14 ;
a | = * p ;
/* a: p0<<28 | p2<<14 | p4 (unmasked) */
if ( ! ( a & 0x80 ) )
{
/* we can skip these cause they were (effectively) done above in calc'ing s */
/* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
/* b &= (0x7f<<14)|(0x7f); */
b = b < < 7 ;
a | = b ;
s = s > > 18 ;
* v = ( ( u64 ) s ) < < 32 | a ;
return 5 ;
}
/* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
s = s < < 7 ;
s | = b ;
/* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
p + + ;
b = b < < 14 ;
b | = * p ;
/* b: p1<<28 | p3<<14 | p5 (unmasked) */
if ( ! ( b & 0x80 ) )
{
/* we can skip this cause it was (effectively) done above in calc'ing s */
/* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
a & = SLOT_2_0 ;
a = a < < 7 ;
a | = b ;
s = s > > 18 ;
* v = ( ( u64 ) s ) < < 32 | a ;
return 6 ;
}
p + + ;
a = a < < 14 ;
a | = * p ;
/* a: p2<<28 | p4<<14 | p6 (unmasked) */
if ( ! ( a & 0x80 ) )
{
a & = SLOT_4_2_0 ;
b & = SLOT_2_0 ;
b = b < < 7 ;
a | = b ;
s = s > > 11 ;
* v = ( ( u64 ) s ) < < 32 | a ;
return 7 ;
}
/* CSE2 from below */
a & = SLOT_2_0 ;
p + + ;
b = b < < 14 ;
b | = * p ;
/* b: p3<<28 | p5<<14 | p7 (unmasked) */
if ( ! ( b & 0x80 ) )
{
b & = SLOT_4_2_0 ;
/* moved CSE2 up */
/* a &= (0x7f<<14)|(0x7f); */
a = a < < 7 ;
a | = b ;
s = s > > 4 ;
* v = ( ( u64 ) s ) < < 32 | a ;
return 8 ;
}
p + + ;
a = a < < 15 ;
a | = * p ;
/* a: p4<<29 | p6<<15 | p8 (unmasked) */
/* moved CSE2 up */
/* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
b & = SLOT_2_0 ;
b = b < < 8 ;
a | = b ;
s = s < < 4 ;
b = p [ - 4 ] ;
b & = 0x7f ;
b = b > > 3 ;
s | = b ;
* v = ( ( u64 ) s ) < < 32 | a ;
return 9 ;
}
/*
* * The variable - length integer encoding is as follows :
* *
* * KEY :
* * A = 0 xxxxxxx 7 bits of data and one flag bit
* * B = 1 xxxxxxx 7 bits of data and one flag bit
* * C = xxxxxxxx 8 bits of data
* *
* * 7 bits - A
* * 14 bits - BA
* * 21 bits - BBA
* * 28 bits - BBBA
* * 35 bits - BBBBA
* * 42 bits - BBBBBA
* * 49 bits - BBBBBBA
* * 56 bits - BBBBBBBA
* * 64 bits - BBBBBBBBC
*/
# ifdef SQLITE_NOINLINE
# define FTS5_NOINLINE SQLITE_NOINLINE
# else
# define FTS5_NOINLINE
# endif
/*
* * Write a 64 - bit variable - length integer to memory starting at p [ 0 ] .
* * The length of data write will be between 1 and 9 bytes . The number
* * of bytes written is returned .
* *
* * A variable - length integer consists of the lower 7 bits of each byte
* * for all bytes that have the 8 th bit set and one byte with the 8 th
* * bit clear . Except , if we get to the 9 th byte , it stores the full
* * 8 bits and is the last byte .
*/
static int FTS5_NOINLINE fts5PutVarint64 ( unsigned char * p , u64 v ) {
int i , j , n ;
u8 buf [ 10 ] ;
if ( v & ( ( ( u64 ) 0xff000000 ) < < 32 ) ) {
p [ 8 ] = ( u8 ) v ;
v > > = 8 ;
for ( i = 7 ; i > = 0 ; i - - ) {
p [ i ] = ( u8 ) ( ( v & 0x7f ) | 0x80 ) ;
v > > = 7 ;
}
return 9 ;
}
n = 0 ;
do {
buf [ n + + ] = ( u8 ) ( ( v & 0x7f ) | 0x80 ) ;
v > > = 7 ;
} while ( v ! = 0 ) ;
buf [ 0 ] & = 0x7f ;
assert ( n < = 9 ) ;
for ( i = 0 , j = n - 1 ; j > = 0 ; j - - , i + + ) {
p [ i ] = buf [ j ] ;
}
return n ;
}
int sqlite3Fts5PutVarint ( unsigned char * p , u64 v ) {
if ( v < = 0x7f ) {
p [ 0 ] = v & 0x7f ;
return 1 ;
}
if ( v < = 0x3fff ) {
p [ 0 ] = ( ( v > > 7 ) & 0x7f ) | 0x80 ;
p [ 1 ] = v & 0x7f ;
return 2 ;
}
return fts5PutVarint64 ( p , v ) ;
}
int sqlite3Fts5GetVarintLen ( u32 iVal ) {
2016-02-05 21:09:26 +00:00
#if 0
2015-05-30 11:49:58 +00:00
if ( iVal < ( 1 < < 7 ) ) return 1 ;
2016-02-05 21:09:26 +00:00
# endif
assert ( iVal > = ( 1 < < 7 ) ) ;
2015-05-30 11:49:58 +00:00
if ( iVal < ( 1 < < 14 ) ) return 2 ;
if ( iVal < ( 1 < < 21 ) ) return 3 ;
if ( iVal < ( 1 < < 28 ) ) return 4 ;
return 5 ;
}