332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
|
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
|
+
+
-
-
+
+
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
+
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
|
p->aOut = aNew;
p->nAlloc = sqlite4DbMallocSize(p->db, p->aOut);
}
return SQLITE4_OK;
}
/*
** Write value v as a varint into buffer p. If parameter bInvert
** is non-zero, write the ones-complement of each byte instead of
** Encode the positive integer m using the key encoding.
**
** the usual value.
*/
** To encode an integer, the integer value is represented as centimal
** (base-100) with E digits. Each centimal digit is stored in one byte
** with the most significant digits coming first. For each centimal
** digit X (with X>=0 and X<=99) the byte value will be 2*X+1 except
** for the last digit for which the value is 2*X. Trailing 0 digits are
** omitted, so that the encoding of the mantissa will never contain
** a zero byte.
**
** The key encoding consists of the E value (the number of
static void putVarint64(KeyEncoder *p, sqlite4_uint64 v, int bInvert){
unsigned char *z = &p->aOut[p->nOut];
int n = sqlite4PutVarint64(z, v);
if( bInvert ){
int i;
for(i=0; i<n; i++) z[i] = ~z[i];
}
p->nOut += n;
}
/*
** Write value num into buffer p using the key encoding.
** centimal digits in the original number, before trailing zero digits
** are removed), followed by the mantissa encoding M. This routine
** only writes the mantissa. The E values will be embedded in the
** initial byte of the encoding by the calling function. This
** routine returns the value of E. E will always be at least 1 and
** no more than 10.
**
** Note that values encoded by this routine have exactly the same
** byte representation as the equivalent floating-point values encoded
** by the encodeLargeFloatKey() routine below.
*/
static int encodeIntKey(sqlite4_uint64 m, KeyEncoder *p){
int i = 0;
int e;
unsigned char aDigits[20];
assert( m>0 );
do{
aDigits[i++] = m%100; m /= 100;
}while( m );
e = i;
while( i ) p->aOut[p->nOut++] = aDigits[--i]*2 + 1;
p->aOut[p->nOut-1] &= 0xfe;
return e;
static void encodeNumericKey(KeyEncoder *p, sqlite4_num num){
if( num.m==0 ){
p->aOut[p->nOut++] = 0x15; /* Numeric zero */
}else if( sqlite4_num_isnan(num) ){
p->aOut[p->nOut++] = 0x06; /* NaN */
}else if( sqlite4_num_isinf(num) ){
p->aOut[p->nOut++] = num.sign ? 0x07 : 0x23; /* Neg and Pos infinity */
}else{
int e;
u64 m;
int iDigit = 0;
u8 aDigit[12];
while( (num.m % 10)==0 ){
num.e++;
num.m = num.m / 10;
}
m = num.m;
e = num.e;
if( num.e % 2 ){
aDigit[0] = 10 * (m % 10);
m = m / 10;
e--;
iDigit = 1;
}else{
iDigit = 0;
}
while( m ){
aDigit[iDigit++] = (m % 100);
m = m / 100;
}
e = (iDigit + (e/2));
if( e>11 ){ /* Large value */
if( num.sign==0 ){
p->aOut[p->nOut++] = 0x22;
putVarint64(p, e, 0);
}else{
p->aOut[p->nOut++] = 0x08;
putVarint64(p, e, 1);
}
}
else if( e>=0 ){ /* Medium value */
if( num.sign==0 ){
p->aOut[p->nOut++] = 0x17+e;
}else{
p->aOut[p->nOut++] = 0x13-e;
}
}
else{ /* Small value */
if( num.sign==0 ){
p->aOut[p->nOut++] = 0x16;
putVarint64(p, -1*e, 1);
}else{
p->aOut[p->nOut++] = 0x14;
putVarint64(p, -1*e, 0);
}
}
/* Write M to the output. */
while( (iDigit--)>0 ){
u8 d = aDigit[iDigit]*2;
if( iDigit!=0 ) d |= 0x01;
if( num.sign ) d = ~d;
p->aOut[p->nOut++] = d;
}
}
}
/*
** Encode a single integer using the key encoding. The caller must
** ensure that sufficient space exits in a[] (at least 12 bytes).
** The return value is the number of bytes of a[] used.
*/
int sqlite4VdbeEncodeIntKey(u8 *a, sqlite4_int64 v){
int i, e;
KeyEncoder s;
s.aOut = a;
s.nOut = 1;
if( v<0 ){
e = encodeIntKey((sqlite4_uint64)-v, &s);
sqlite4_num num;
assert( e<=10 );
a[0] = 0x13-e;
for(i=1; i<s.nOut; i++) a[i] ^= 0xff;
}else if( v>0 ){
e = encodeIntKey((sqlite4_uint64)v, &s);
assert( e<=10 );
a[0] = 0x17+e;
}else{
a[0] = 0x15;
}
return s.nOut;
}
num = sqlite4_num_from_int64(v);
/*
** Encode the small positive floating point number r using the key
** encoding. The caller guarantees that r will be less than 1.0 and
** greater than 0.0.
**
** A floating point value is encoded as an integer exponent E and a
** mantissa M. The original value is equal to (M * 100^E). E is set
** to the smallest value possible without making M greater than or equal
** to 1.0.
**
** For this routine, E will always be zero or negative, since the original
** value is less than one. The encoding written by this routine is the
** ones-complement of the varint of the negative of E followed by the
** mantissa:
**
** Encoding: ~-E M
*/
static void encodeSmallFloatKey(double r, KeyEncoder *p){
int e = 0;
int i, n;
assert( r>0.0 && r<1.0 );
while( r<1e-10 ){ r *= 1e8; e+=4; }
while( r<0.01 ){ r *= 100.0; e++; }
n = sqlite4PutVarint64(p->aOut+p->nOut, e);
for(i=0; i<n; i++) p->aOut[i+p->nOut] ^= 0xff;
p->nOut += n;
for(i=0; i<18 && r!=0.0; i++){
r *= 100.0;
int d = r;
p->aOut[p->nOut++] = 2*d + 1;
r -= d;
}
p->aOut[p->nOut-1] &= 0xfe;
}
memset(&s, 0, sizeof(s));
/*
** Encode the large positive floating point number r using the key
** encoding. The caller guarantees that r will be finite and greater than
** or equal to 1.0.
**
** A floating point value is encoded as an integer exponent E and a
** mantissa M. The original value is equal to (M * 100^E). E is set to
** the smallest value possible without making M greater than or equal
** to 1.0.
**
** Each centimal digit of the mantissa is stored in a byte. If the value
** of the centimal digit is X (hence X>=0 and X<=99) then the byte value
** will be 2*X+1 for every byte of the mantissa, except for the last byte
** which will be 2*X+0. The mantissa must be the minimum number of bytes
** necessary to represent the value; trailing X==0 digits are omitted.
** This means that the mantissa will never contain a byte with the
** value 0x00.
**
** If E is greater than 10, then this routine writes of E as a varint
** followed by the mantissa as described above. Otherwise, if E is 10 or
** less, this routine only writes the mantissa and leaves the E value
** to be encoded as part of the opening byte of the field by the
** calling function.
**
** Encoding: M (if E<=10)
** E M (if E>10)
**
** This routine returns the value of E.
*/
static int encodeLargeFloatKey(double r, KeyEncoder *p){
int e = 0;
int i, n;
s.aOut = a;
encodeNumericKey(&s, num);
assert( r>=1.0 );
while( r>=1e32 && e<=350 ){ r *= 1e-32; e+=16; }
while( r>=1e8 && e<=350 ){ r *= 1e-8; e+=4; }
while( r>=1.0 && e<=350 ){ r *= 0.01; e++; }
if( e>10 ){
n = sqlite4PutVarint64(p->aOut+p->nOut, e);
p->nOut += n;
}
for(i=0; i<18 && r!=0.0; i++){
r *= 100.0;
int d = r;
p->aOut[p->nOut++] = 2*d + 1;
r -= d;
}
p->aOut[p->nOut-1] &= 0xfe;
return e;
return s.nOut;
}
static void putVarint64(KeyEncoder *p, sqlite4_uint64 v, int bInvert){
unsigned char *z = &p->aOut[p->nOut];
int n = sqlite4PutVarint64(z, v);
if( bInvert ){
int i;
for(i=0; i<n; i++) z[i] = ~z[i];
}
p->nOut += n;
}
/*
** Encode a single column of the key
*/
static int encodeOneKeyValue(
KeyEncoder *p, /* Key encoder context */
Mem *pMem, /* Value to be encoded */
u8 sortOrder, /* Sort order for this value */
u8 isLastValue, /* True if this is the last value in the key */
CollSeq *pColl /* Collating sequence for the value */
){
int flags = pMem->flags;
int i, e;
int i;
int n;
int iStart = p->nOut;
if( flags & MEM_Null ){
if( enlargeEncoderAllocation(p, 1) ) return SQLITE4_NOMEM;
p->aOut[p->nOut++] = 0x05; /* NULL */
}else
#if 0
if( flags & MEM_Int ){
sqlite4_int64 v;
sqlite4_num_to_int64(pMem->u.num, &v);
if( enlargeEncoderAllocation(p, 11) ) return SQLITE4_NOMEM;
if( v==0 ){
p->aOut[p->nOut++] = 0x15; /* Numeric zero */
}else if( v<0 ){
p->aOut[p->nOut++] = 0x08; /* Large negative number */
i = p->nOut;
e = encodeIntKey((sqlite4_uint64)-v, p);
if( e<=10 ) p->aOut[i-1] = 0x13-e;
while( i<p->nOut ) p->aOut[i++] ^= 0xff;
}else{
i = p->nOut;
p->aOut[p->nOut++] = 0x22; /* Large positive number */
e = encodeIntKey((sqlite4_uint64)v, p);
if( e<=10 ) p->aOut[i] = 0x17+e;
}
}else
#endif
if( flags & (MEM_Real|MEM_Int) ){
sqlite4_num num = pMem->u.num;
if( enlargeEncoderAllocation(p, 16) ) return SQLITE4_NOMEM;
encodeNumericKey(p, pMem->u.num);
if( num.m==0 ){
p->aOut[p->nOut++] = 0x15; /* Numeric zero */
}else if( sqlite4_num_isnan(num) ){
p->aOut[p->nOut++] = 0x06; /* NaN */
}else if( sqlite4_num_isinf(num) ){
p->aOut[p->nOut++] = num.sign ? 0x07 : 0x23; /* Neg and Pos infinity */
}else{
int e;
u64 m;
int iDigit = 0;
u8 aDigit[12];
while( (num.m % 10)==0 ){
num.e++;
num.m = num.m / 10;
}
m = num.m;
e = num.e;
if( num.e % 2 ){
aDigit[0] = 10 * (m % 10);
m = m / 10;
e--;
iDigit = 1;
}else{
iDigit = 0;
}
while( m ){
aDigit[iDigit++] = (m % 100);
m = m / 100;
}
e = (iDigit + (e/2));
if( e>11 ){ /* Large value */
if( num.sign==0 ){
p->aOut[p->nOut++] = 0x22;
putVarint64(p, e, 0);
}else{
p->aOut[p->nOut++] = 0x08;
putVarint64(p, e, 1);
}
}
else if( e>=0 ){ /* Medium value */
if( num.sign==0 ){
p->aOut[p->nOut++] = 0x17+e;
}else{
p->aOut[p->nOut++] = 0x13-e;
}
}
else{ /* Small value */
if( num.sign==0 ){
p->aOut[p->nOut++] = 0x16;
putVarint64(p, -1*e, 1);
}else{
p->aOut[p->nOut++] = 0x14;
putVarint64(p, -1*e, 0);
}
}
/* Write M to the output. */
while( (iDigit--)>0 ){
u8 d = aDigit[iDigit]*2;
if( iDigit!=0 ) d |= 0x01;
if( num.sign ) d = ~d;
p->aOut[p->nOut++] = d;
}
}
}else
if( flags & MEM_Str ){
}else if( flags & MEM_Str ){
Mem *pEnc; /* Pointer to memory cell in correct enc. */
Mem sMem; /* Value converted to different encoding */
int enc; /* Required encoding */
/* Figure out the current encoding of pMem, and the encoding required
** (either the encoding specified by the collation sequence, or utf-8
** if there is no collation sequence). */
|