SQLite4
Check-in [9265ac66c8]
Not logged in

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 | SQL archive
Timelines: family | ancestors | descendants | both | sqlite4-num
Files: files | file ages | folders
SHA1: 9265ac66c85c9ea7cfdea3e646e2758442ab2b6d
User & Date: dan 2013-05-30 19:01:33
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
Hide Diffs Unified Diffs Show Whitespace Changes 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
...
599
600
601
602
603
604
605



































606



607
608
609
610
611
612
613
614
    p->aOut = aNew;
    p->nAlloc = sqlite4DbMallocSize(p->db, p->aOut);
  }
  return SQLITE4_OK;
}

/*
** Encode the positive integer m using the key encoding.
**
** 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
** 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;
}

/*
** 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);
    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;
}

/*
** 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;
}

/*
** 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;
  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;
}

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 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;


    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{
................................................................................
      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 ){
    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).  */







|
|
|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<











<
>

<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
|







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
...
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
** the usual value.


















*/




























































































































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.
*/








































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{
................................................................................
    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){
  KeyEncoder s;
  sqlite4_num num;

  num = sqlite4_num_from_int64(v);
  memset(&s, 0, sizeof(s));
  s.aOut = a;
  encodeNumericKey(&s, num);
  return s.nOut;
}

/*
** 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;
  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( flags & (MEM_Real|MEM_Int) ){
    if( enlargeEncoderAllocation(p, 16) ) return SQLITE4_NOMEM;
    encodeNumericKey(p, pMem->u.num);
  }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).  */