ext/lsm1/lsm_varint.c

   1
   2 /*
   3 ** 2012-02-08
   4 **
   5 ** The author disclaims copyright to this source code.  In place of
   6 ** a legal notice, here is a blessing:
   7 **
   8 **    May you do good and not evil.
   9 **    May you find forgiveness for yourself and forgive others.
  10 **    May you share freely, never taking more than you give.
  11 **
  12 *************************************************************************
  13 **
  14 ** SQLite4-compatible varint implementation.
  15 */
  16 #include "lsmInt.h"
  17
  18 /*************************************************************************
  19 ** The following is a copy of the varint.c module from SQLite 4.
  20 */
  21
  22 /*
  23 ** Decode the varint in z[].  Write the integer value into *pResult and
  24 ** return the number of bytes in the varint.
  25 */
  26 static int lsmSqlite4GetVarint64(const unsigned char *z, u64 *pResult){
  27   unsigned int x;
  28   if( z[0]<=240 ){
  29     *pResult = z[0];
  30     return 1;
  31   }
  32   if( z[0]<=248 ){
  33     *pResult = (z[0]-241)*256 + z[1] + 240;
  34     return 2;
  35   }
  36   if( z[0]==249 ){
  37     *pResult = 2288 + 256*z[1] + z[2];
  38     return 3;
  39   }
  40   if( z[0]==250 ){
  41     *pResult = (z[1]<<16) + (z[2]<<8) + z[3];
  42     return 4;
  43   }
  44   x = (z[1]<<24) + (z[2]<<16) + (z[3]<<8) + z[4];
  45   if( z[0]==251 ){
  46     *pResult = x;
  47     return 5;
  48   }
  49   if( z[0]==252 ){
  50     *pResult = (((u64)x)<<8) + z[5];
  51     return 6;
  52   }
  53   if( z[0]==253 ){
  54     *pResult = (((u64)x)<<16) + (z[5]<<8) + z[6];
  55     return 7;
  56   }
  57   if( z[0]==254 ){
  58     *pResult = (((u64)x)<<24) + (z[5]<<16) + (z[6]<<8) + z[7];
  59     return 8;
  60   }
  61   *pResult = (((u64)x)<<32) +
  62                (0xffffffff & ((z[5]<<24) + (z[6]<<16) + (z[7]<<8) + z[8]));
  63   return 9;
  64 }
  65
  66 /*
  67 ** Write a 32-bit unsigned integer as 4 big-endian bytes.
  68 */
  69 static void lsmVarintWrite32(unsigned char *z, unsigned int y){
  70   z[0] = (unsigned char)(y>>24);
  71   z[1] = (unsigned char)(y>>16);
  72   z[2] = (unsigned char)(y>>8);
  73   z[3] = (unsigned char)(y);
  74 }
  75
  76 /*
  77 ** Write a varint into z[].  The buffer z[] must be at least 9 characters
  78 ** long to accommodate the largest possible varint.  Return the number of
  79 ** bytes of z[] used.
  80 */
  81 static int lsmSqlite4PutVarint64(unsigned char *z, u64 x){
  82   unsigned int w, y;
  83   if( x<=240 ){
  84     z[0] = (unsigned char)x;
  85     return 1;
  86   }
  87   if( x<=2287 ){
  88     y = (unsigned int)(x - 240);
  89     z[0] = (unsigned char)(y/256 + 241);
  90     z[1] = (unsigned char)(y%256);
  91     return 2;
  92   }
  93   if( x<=67823 ){
  94     y = (unsigned int)(x - 2288);
  95     z[0] = 249;
  96     z[1] = (unsigned char)(y/256);
  97     z[2] = (unsigned char)(y%256);
  98     return 3;
  99   }
 100   y = (unsigned int)x;
 101   w = (unsigned int)(x>>32);
 102   if( w==0 ){
 103     if( y<=16777215 ){
 104       z[0] = 250;
 105       z[1] = (unsigned char)(y>>16);
 106       z[2] = (unsigned char)(y>>8);
 107       z[3] = (unsigned char)(y);
 108       return 4;
 109     }
 110     z[0] = 251;
 111     lsmVarintWrite32(z+1, y);
 112     return 5;
 113   }
 114   if( w<=255 ){
 115     z[0] = 252;
 116     z[1] = (unsigned char)w;
 117     lsmVarintWrite32(z+2, y);
 118     return 6;
 119   }
 120   if( w<=32767 ){
 121     z[0] = 253;
 122     z[1] = (unsigned char)(w>>8);
 123     z[2] = (unsigned char)w;
 124     lsmVarintWrite32(z+3, y);
 125     return 7;
 126   }
 127   if( w<=16777215 ){
 128     z[0] = 254;
 129     z[1] = (unsigned char)(w>>16);
 130     z[2] = (unsigned char)(w>>8);
 131     z[3] = (unsigned char)w;
 132     lsmVarintWrite32(z+4, y);
 133     return 8;
 134   }
 135   z[0] = 255;
 136   lsmVarintWrite32(z+1, w);
 137   lsmVarintWrite32(z+5, y);
 138   return 9;
 139 }
 140
 141 /*
 142 ** End of SQLite 4 code.
 143 *************************************************************************/
 144
 145 int lsmVarintPut64(u8 *aData, i64 iVal){
 146   return lsmSqlite4PutVarint64(aData, (u64)iVal);
 147 }
 148
 149 int lsmVarintGet64(const u8 *aData, i64 *piVal){
 150   return lsmSqlite4GetVarint64(aData, (u64 *)piVal);
 151 }
 152
 153 int lsmVarintPut32(u8 *aData, int iVal){
 154   return lsmSqlite4PutVarint64(aData, (u64)iVal);
 155 }
 156
 157 int lsmVarintGet32(u8 *z, int *piVal){
 158   u64 i;
 159   int ret;
 160
 161   if( z[0]<=240 ){
 162     *piVal = z[0];
 163     return 1;
 164   }
 165   if( z[0]<=248 ){
 166     *piVal = (z[0]-241)*256 + z[1] + 240;
 167     return 2;
 168   }
 169   if( z[0]==249 ){
 170     *piVal = 2288 + 256*z[1] + z[2];
 171     return 3;
 172   }
 173   if( z[0]==250 ){
 174     *piVal = (z[1]<<16) + (z[2]<<8) + z[3];
 175     return 4;
 176   }
 177
 178   ret = lsmSqlite4GetVarint64(z, &i);
 179   *piVal = (int)i;
 180   return ret;
 181 }
 182
 183 int lsmVarintLen32(int n){
 184   u8 aData[9];
 185   return lsmVarintPut32(aData, n);
 186 }
 187
 188 /*
 189 ** The argument is the first byte of a varint. This function returns the
 190 ** total number of bytes in the entire varint (including the first byte).
 191 */
 192 int lsmVarintSize(u8 c){
 193   if( c<241 ) return 1;
 194   if( c<249 ) return 2;
 195   return (int)(c - 246);
 196 }