SQLite4
Check-in [7017d07fea]
Not logged in

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

Overview
Comment:Fix an off-by-one problem with encoding real values into index keys. Add a test for sorting numeric values.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 7017d07feac998fa797c58c27a253ec700cb2a29
User & Date: dan 2012-04-21 19:19:55
Context
2012-04-21
19:59
Additional comments on the key encoder. Remove an unused variable. check-in: fdaed18ddf user: drh tags: trunk
19:19
Fix an off-by-one problem with encoding real values into index keys. Add a test for sorting numeric values. check-in: 7017d07fea user: dan tags: trunk
18:55
Fixes to the text of the key encoding definition in key_encoding.txt. check-in: ee5b8b8d11 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/vdbecodec.c.

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
  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.
**
** The key encoding is the negative of the exponent E followed by the
** mantessa M.  The exponent E is one less than the number of digits to
** the left of the decimal point.  Since r is less than 1, E will always
** be negative here.  E is output as a varint, and varints must be
** positive, which is why we output -E.  The mantissa is stored two-digits
** per byte as described for the integer encoding above.
*/
static void encodeSmallFloatKey(double r, KeyEncoder *p){
  int e = 0;
  int i, n;
  assert( r>0.0 && r<1.0 );
  while( r<1e-8 ){ r *= 1e8; e+=4; }
  while( r<1.0 ){ 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++){

    int d = r;
    p->aOut[p->nOut++] = 2*d + 1;
    r -= d;
    r *= 100.0;
  }
  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.
**
** The key encoding is the exponent E followed by the mantessa M.  
** The exponent E is one less than the number of digits to the left 
** of the decimal point.  Since r is at least than 1.0, E will always
** be non-negative here. The mantissa is stored two-digits per byte
** as described for the integer encoding above.













*/
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>=100.0 && e<=350 ){ r *= 0.01; e++; }
  while( r<1.0 ){ r *= 10.0; e--; }
  if( e>10 ){
    n = sqlite4PutVarint64(p->aOut+p->nOut, e);
    p->nOut += n;
  }
  for(i=0; i<18 && r!=0.0; i++){

    int d = r;
    p->aOut[p->nOut++] = 2*d + 1;
    r -= d;
    r *= 100.0;
  }
  p->aOut[p->nOut-1] &= 0xfe;
  return e;
}


/*







<
<
<
<
<
<
<





|
|




>



<






|


|
|
|
|
|
>
>
>
>
>
>
>
>
>
>
>
>
>







|
<





>



<







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







*/
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, the encoded value consists of E as a varint
** followed by the mantissa as described above. Otherwise, it consists
** of the mantissa only.
**
** The value returned by this function is 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;
}


/*

Changes to test/simple.test.

12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
...
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
...
801
802
803
804
805
806
807
808






































809

#
set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix simple

#set sqlite_where_trace 1
#
if 1 {

do_execsql_test 1.0 { 
  PRAGMA table_info = sqlite_master
} {
    0 type text        0 {} 0 
    1 name text        0 {} 0 
    2 tbl_name text    0 {} 0 
................................................................................
    1 "SELECT * FROM t1 WHERE a = 7"        {7 seven}
    2 "SELECT * FROM t1 WHERE b = 'seven'"  {7 seven}
  } {
    do_execsql_test 42.$t.$u $sql $res
  }
}

}

#-------------------------------------------------------------------------
reset_db

do_execsql_test 43.1 {
  CREATE TABLE t1(a, b);
  INSERT INTO t1 VALUES('a', 1);
  INSERT INTO t1 VALUES('b', 4);
................................................................................
  INSERT INTO t1 VALUES('a', 2);
  INSERT INTO t1 VALUES('b', 5);
}

do_execsql_test 43.2 {
  SELECT a, sum(b) FROM t1 GROUP BY a;
} {a 3 b 9}







































finish_test








<







 







<
<







 








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

>
12
13
14
15
16
17
18

19
20
21
22
23
24
25
...
784
785
786
787
788
789
790


791
792
793
794
795
796
797
...
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
#
set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix simple

#set sqlite_where_trace 1
#


do_execsql_test 1.0 { 
  PRAGMA table_info = sqlite_master
} {
    0 type text        0 {} 0 
    1 name text        0 {} 0 
    2 tbl_name text    0 {} 0 
................................................................................
    1 "SELECT * FROM t1 WHERE a = 7"        {7 seven}
    2 "SELECT * FROM t1 WHERE b = 'seven'"  {7 seven}
  } {
    do_execsql_test 42.$t.$u $sql $res
  }
}



#-------------------------------------------------------------------------
reset_db

do_execsql_test 43.1 {
  CREATE TABLE t1(a, b);
  INSERT INTO t1 VALUES('a', 1);
  INSERT INTO t1 VALUES('b', 4);
................................................................................
  INSERT INTO t1 VALUES('a', 2);
  INSERT INTO t1 VALUES('b', 5);
}

do_execsql_test 43.2 {
  SELECT a, sum(b) FROM t1 GROUP BY a;
} {a 3 b 9}

#-------------------------------------------------------------------------
# Test sorting numeric values.
#
reset_db
do_execsql_test 44.1 { CREATE TABLE t1(x PRIMARY KEY, y) }
do_test 44.2 {
  set lVal [list]
  set val 5.0
  for {set i 0} {$i < 10} {incr i ; set val [expr {$val*5.0}] } {
    lappend lVal $val
  }
  set val 5
  for {set i 0} {$i < 10} {incr i ; set val [expr {$val*5}] } {
    lappend lVal [expr $val-1]
    set val [expr {$val*5}]
  }
  set val 5.0
  for {set i 0} {$i < 10} {incr i ; set val [expr {$val/5.0}] } {
    lappend lVal $val
    set val [expr {$val/5.0}]
  }

  set lVal2 [list]
  foreach val $lVal { lappend lVal2 [expr $val * -1] }
  set lVal [concat $lVal $lVal2]

  foreach v $lVal {
    execsql "INSERT INTO t1 VALUES(randomblob(16), $v)"
  }
} {}

do_execsql_test 44.3 {
  SELECT y FROM t1 ORDER BY y;
} [lsort -real $lVal]
do_execsql_test 44.4 {
  SELECT count(*) FROM t1;
} {60}

finish_test