Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Use the same code to encode keys for rowid indexes as regular indexes.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | sqlite4-num
Files: files | file ages | folders
SHA1: 9265ac66c85c9ea7cfdea3e646e2758442ab2b6d
User & Date: dan 2013-05-30 19:01:33.498
Context
2013-05-31
17:13
Use decimal arithmetic in affinity routines. check-in: ae34cd8492 user: dan tags: sqlite4-num
2013-05-30
19:01
Use the same code to encode keys for rowid indexes as regular indexes. check-in: 9265ac66c8 user: dan tags: sqlite4-num
18:26
Change various things to use sqlite4_num instead of double. check-in: ba34125233 user: dan tags: sqlite4-num
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to src/vdbecodec.c.
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).  */