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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbecodec.c.

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