| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 ** 2015 May 30 | |
| 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 ** | |
| 13 ** Routines for varint serialization and deserialization. | |
| 14 */ | |
| 15 | |
| 16 | |
| 17 #include "fts5Int.h" | |
| 18 | |
| 19 /* | |
| 20 ** This is a copy of the sqlite3GetVarint32() routine from the SQLite core. | |
| 21 ** Except, this version does handle the single byte case that the core | |
| 22 ** version depends on being handled before its function is called. | |
| 23 */ | |
| 24 int sqlite3Fts5GetVarint32(const unsigned char *p, u32 *v){ | |
| 25 u32 a,b; | |
| 26 | |
| 27 /* The 1-byte case. Overwhelmingly the most common. */ | |
| 28 a = *p; | |
| 29 /* a: p0 (unmasked) */ | |
| 30 if (!(a&0x80)) | |
| 31 { | |
| 32 /* Values between 0 and 127 */ | |
| 33 *v = a; | |
| 34 return 1; | |
| 35 } | |
| 36 | |
| 37 /* The 2-byte case */ | |
| 38 p++; | |
| 39 b = *p; | |
| 40 /* b: p1 (unmasked) */ | |
| 41 if (!(b&0x80)) | |
| 42 { | |
| 43 /* Values between 128 and 16383 */ | |
| 44 a &= 0x7f; | |
| 45 a = a<<7; | |
| 46 *v = a | b; | |
| 47 return 2; | |
| 48 } | |
| 49 | |
| 50 /* The 3-byte case */ | |
| 51 p++; | |
| 52 a = a<<14; | |
| 53 a |= *p; | |
| 54 /* a: p0<<14 | p2 (unmasked) */ | |
| 55 if (!(a&0x80)) | |
| 56 { | |
| 57 /* Values between 16384 and 2097151 */ | |
| 58 a &= (0x7f<<14)|(0x7f); | |
| 59 b &= 0x7f; | |
| 60 b = b<<7; | |
| 61 *v = a | b; | |
| 62 return 3; | |
| 63 } | |
| 64 | |
| 65 /* A 32-bit varint is used to store size information in btrees. | |
| 66 ** Objects are rarely larger than 2MiB limit of a 3-byte varint. | |
| 67 ** A 3-byte varint is sufficient, for example, to record the size | |
| 68 ** of a 1048569-byte BLOB or string. | |
| 69 ** | |
| 70 ** We only unroll the first 1-, 2-, and 3- byte cases. The very | |
| 71 ** rare larger cases can be handled by the slower 64-bit varint | |
| 72 ** routine. | |
| 73 */ | |
| 74 { | |
| 75 u64 v64; | |
| 76 u8 n; | |
| 77 p -= 2; | |
| 78 n = sqlite3Fts5GetVarint(p, &v64); | |
| 79 *v = (u32)v64; | |
| 80 assert( n>3 && n<=9 ); | |
| 81 return n; | |
| 82 } | |
| 83 } | |
| 84 | |
| 85 | |
| 86 /* | |
| 87 ** Bitmasks used by sqlite3GetVarint(). These precomputed constants | |
| 88 ** are defined here rather than simply putting the constant expressions | |
| 89 ** inline in order to work around bugs in the RVT compiler. | |
| 90 ** | |
| 91 ** SLOT_2_0 A mask for (0x7f<<14) | 0x7f | |
| 92 ** | |
| 93 ** SLOT_4_2_0 A mask for (0x7f<<28) | SLOT_2_0 | |
| 94 */ | |
| 95 #define SLOT_2_0 0x001fc07f | |
| 96 #define SLOT_4_2_0 0xf01fc07f | |
| 97 | |
| 98 /* | |
| 99 ** Read a 64-bit variable-length integer from memory starting at p[0]. | |
| 100 ** Return the number of bytes read. The value is stored in *v. | |
| 101 */ | |
| 102 u8 sqlite3Fts5GetVarint(const unsigned char *p, u64 *v){ | |
| 103 u32 a,b,s; | |
| 104 | |
| 105 a = *p; | |
| 106 /* a: p0 (unmasked) */ | |
| 107 if (!(a&0x80)) | |
| 108 { | |
| 109 *v = a; | |
| 110 return 1; | |
| 111 } | |
| 112 | |
| 113 p++; | |
| 114 b = *p; | |
| 115 /* b: p1 (unmasked) */ | |
| 116 if (!(b&0x80)) | |
| 117 { | |
| 118 a &= 0x7f; | |
| 119 a = a<<7; | |
| 120 a |= b; | |
| 121 *v = a; | |
| 122 return 2; | |
| 123 } | |
| 124 | |
| 125 /* Verify that constants are precomputed correctly */ | |
| 126 assert( SLOT_2_0 == ((0x7f<<14) | (0x7f)) ); | |
| 127 assert( SLOT_4_2_0 == ((0xfU<<28) | (0x7f<<14) | (0x7f)) ); | |
| 128 | |
| 129 p++; | |
| 130 a = a<<14; | |
| 131 a |= *p; | |
| 132 /* a: p0<<14 | p2 (unmasked) */ | |
| 133 if (!(a&0x80)) | |
| 134 { | |
| 135 a &= SLOT_2_0; | |
| 136 b &= 0x7f; | |
| 137 b = b<<7; | |
| 138 a |= b; | |
| 139 *v = a; | |
| 140 return 3; | |
| 141 } | |
| 142 | |
| 143 /* CSE1 from below */ | |
| 144 a &= SLOT_2_0; | |
| 145 p++; | |
| 146 b = b<<14; | |
| 147 b |= *p; | |
| 148 /* b: p1<<14 | p3 (unmasked) */ | |
| 149 if (!(b&0x80)) | |
| 150 { | |
| 151 b &= SLOT_2_0; | |
| 152 /* moved CSE1 up */ | |
| 153 /* a &= (0x7f<<14)|(0x7f); */ | |
| 154 a = a<<7; | |
| 155 a |= b; | |
| 156 *v = a; | |
| 157 return 4; | |
| 158 } | |
| 159 | |
| 160 /* a: p0<<14 | p2 (masked) */ | |
| 161 /* b: p1<<14 | p3 (unmasked) */ | |
| 162 /* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */ | |
| 163 /* moved CSE1 up */ | |
| 164 /* a &= (0x7f<<14)|(0x7f); */ | |
| 165 b &= SLOT_2_0; | |
| 166 s = a; | |
| 167 /* s: p0<<14 | p2 (masked) */ | |
| 168 | |
| 169 p++; | |
| 170 a = a<<14; | |
| 171 a |= *p; | |
| 172 /* a: p0<<28 | p2<<14 | p4 (unmasked) */ | |
| 173 if (!(a&0x80)) | |
| 174 { | |
| 175 /* we can skip these cause they were (effectively) done above in calc'ing s
*/ | |
| 176 /* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */ | |
| 177 /* b &= (0x7f<<14)|(0x7f); */ | |
| 178 b = b<<7; | |
| 179 a |= b; | |
| 180 s = s>>18; | |
| 181 *v = ((u64)s)<<32 | a; | |
| 182 return 5; | |
| 183 } | |
| 184 | |
| 185 /* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */ | |
| 186 s = s<<7; | |
| 187 s |= b; | |
| 188 /* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */ | |
| 189 | |
| 190 p++; | |
| 191 b = b<<14; | |
| 192 b |= *p; | |
| 193 /* b: p1<<28 | p3<<14 | p5 (unmasked) */ | |
| 194 if (!(b&0x80)) | |
| 195 { | |
| 196 /* we can skip this cause it was (effectively) done above in calc'ing s */ | |
| 197 /* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */ | |
| 198 a &= SLOT_2_0; | |
| 199 a = a<<7; | |
| 200 a |= b; | |
| 201 s = s>>18; | |
| 202 *v = ((u64)s)<<32 | a; | |
| 203 return 6; | |
| 204 } | |
| 205 | |
| 206 p++; | |
| 207 a = a<<14; | |
| 208 a |= *p; | |
| 209 /* a: p2<<28 | p4<<14 | p6 (unmasked) */ | |
| 210 if (!(a&0x80)) | |
| 211 { | |
| 212 a &= SLOT_4_2_0; | |
| 213 b &= SLOT_2_0; | |
| 214 b = b<<7; | |
| 215 a |= b; | |
| 216 s = s>>11; | |
| 217 *v = ((u64)s)<<32 | a; | |
| 218 return 7; | |
| 219 } | |
| 220 | |
| 221 /* CSE2 from below */ | |
| 222 a &= SLOT_2_0; | |
| 223 p++; | |
| 224 b = b<<14; | |
| 225 b |= *p; | |
| 226 /* b: p3<<28 | p5<<14 | p7 (unmasked) */ | |
| 227 if (!(b&0x80)) | |
| 228 { | |
| 229 b &= SLOT_4_2_0; | |
| 230 /* moved CSE2 up */ | |
| 231 /* a &= (0x7f<<14)|(0x7f); */ | |
| 232 a = a<<7; | |
| 233 a |= b; | |
| 234 s = s>>4; | |
| 235 *v = ((u64)s)<<32 | a; | |
| 236 return 8; | |
| 237 } | |
| 238 | |
| 239 p++; | |
| 240 a = a<<15; | |
| 241 a |= *p; | |
| 242 /* a: p4<<29 | p6<<15 | p8 (unmasked) */ | |
| 243 | |
| 244 /* moved CSE2 up */ | |
| 245 /* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */ | |
| 246 b &= SLOT_2_0; | |
| 247 b = b<<8; | |
| 248 a |= b; | |
| 249 | |
| 250 s = s<<4; | |
| 251 b = p[-4]; | |
| 252 b &= 0x7f; | |
| 253 b = b>>3; | |
| 254 s |= b; | |
| 255 | |
| 256 *v = ((u64)s)<<32 | a; | |
| 257 | |
| 258 return 9; | |
| 259 } | |
| 260 | |
| 261 /* | |
| 262 ** The variable-length integer encoding is as follows: | |
| 263 ** | |
| 264 ** KEY: | |
| 265 ** A = 0xxxxxxx 7 bits of data and one flag bit | |
| 266 ** B = 1xxxxxxx 7 bits of data and one flag bit | |
| 267 ** C = xxxxxxxx 8 bits of data | |
| 268 ** | |
| 269 ** 7 bits - A | |
| 270 ** 14 bits - BA | |
| 271 ** 21 bits - BBA | |
| 272 ** 28 bits - BBBA | |
| 273 ** 35 bits - BBBBA | |
| 274 ** 42 bits - BBBBBA | |
| 275 ** 49 bits - BBBBBBA | |
| 276 ** 56 bits - BBBBBBBA | |
| 277 ** 64 bits - BBBBBBBBC | |
| 278 */ | |
| 279 | |
| 280 #ifdef SQLITE_NOINLINE | |
| 281 # define FTS5_NOINLINE SQLITE_NOINLINE | |
| 282 #else | |
| 283 # define FTS5_NOINLINE | |
| 284 #endif | |
| 285 | |
| 286 /* | |
| 287 ** Write a 64-bit variable-length integer to memory starting at p[0]. | |
| 288 ** The length of data write will be between 1 and 9 bytes. The number | |
| 289 ** of bytes written is returned. | |
| 290 ** | |
| 291 ** A variable-length integer consists of the lower 7 bits of each byte | |
| 292 ** for all bytes that have the 8th bit set and one byte with the 8th | |
| 293 ** bit clear. Except, if we get to the 9th byte, it stores the full | |
| 294 ** 8 bits and is the last byte. | |
| 295 */ | |
| 296 static int FTS5_NOINLINE fts5PutVarint64(unsigned char *p, u64 v){ | |
| 297 int i, j, n; | |
| 298 u8 buf[10]; | |
| 299 if( v & (((u64)0xff000000)<<32) ){ | |
| 300 p[8] = (u8)v; | |
| 301 v >>= 8; | |
| 302 for(i=7; i>=0; i--){ | |
| 303 p[i] = (u8)((v & 0x7f) | 0x80); | |
| 304 v >>= 7; | |
| 305 } | |
| 306 return 9; | |
| 307 } | |
| 308 n = 0; | |
| 309 do{ | |
| 310 buf[n++] = (u8)((v & 0x7f) | 0x80); | |
| 311 v >>= 7; | |
| 312 }while( v!=0 ); | |
| 313 buf[0] &= 0x7f; | |
| 314 assert( n<=9 ); | |
| 315 for(i=0, j=n-1; j>=0; j--, i++){ | |
| 316 p[i] = buf[j]; | |
| 317 } | |
| 318 return n; | |
| 319 } | |
| 320 | |
| 321 int sqlite3Fts5PutVarint(unsigned char *p, u64 v){ | |
| 322 if( v<=0x7f ){ | |
| 323 p[0] = v&0x7f; | |
| 324 return 1; | |
| 325 } | |
| 326 if( v<=0x3fff ){ | |
| 327 p[0] = ((v>>7)&0x7f)|0x80; | |
| 328 p[1] = v&0x7f; | |
| 329 return 2; | |
| 330 } | |
| 331 return fts5PutVarint64(p,v); | |
| 332 } | |
| 333 | |
| 334 | |
| 335 int sqlite3Fts5GetVarintLen(u32 iVal){ | |
| 336 if( iVal<(1 << 7 ) ) return 1; | |
| 337 if( iVal<(1 << 14) ) return 2; | |
| 338 if( iVal<(1 << 21) ) return 3; | |
| 339 if( iVal<(1 << 28) ) return 4; | |
| 340 return 5; | |
| 341 } | |
| 342 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2846743003:
[sql] Remove SQLite 3.10.2 reference directory. (Closed)
