ucw/varint.h

   1 /*
   2  *      UCW Library -- Coding of u64 into variable length bytecode.
   3  *
   4  *      (c) 2013 Tomas Valla <tom@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #ifndef _UCW_VARINT_H
  11 #define _UCW_VARINT_H
  12
  13 /***
  14  * The encoding works in the following way:
  15  *
  16  *  First byte                  Stored values
  17  *
  18  *  0xxxxxxx                    7 bits
  19  *  10xxxxxx  +1 byte           14 bits, value shifted by 2^7
  20  *  110xxxxx  +2 bytes          21 bits, value shifted by 2^7+2^14
  21  *  1110xxxx  +3 bytes          28 bits, value shifted by 2^7+2^14+2^21
  22  *    ....
  23  *  11111110  +7 bytes          56 bits, value shifted by 2^7+2^14+2^21+2^28+2^35+2^42
  24  *  11111111  +8 bytes          full 64 bits, value shifted by 2^7+2^14+2^21+2^28+2^35+2^42+2^56
  25  *
  26  * The values are stored in bigendian to allow lexicographic sorting.
  27  * The encoding and algorithms are aimed to be optimised for storing shorter numbers.
  28  *
  29  * There is an invalid combination: if the first two bytes are 0xff 0xff.
  30  ***/
  31
  32
  33 #define VARINT_SHIFT_L1                       0x80
  34 #define VARINT_SHIFT_L2                     0x4080
  35 #define VARINT_SHIFT_L3                   0x204080
  36 #define VARINT_SHIFT_L4                 0x10204080
  37 #define VARINT_SHIFT_L5               0x0810204080
  38 #define VARINT_SHIFT_L6             0x040810204080
  39 #define VARINT_SHIFT_L7           0x02040810204080
  40 #define VARINT_SHIFT_L8         0x0102040810204080
  41
  42 /*
  43  * The following code is already unrolled, to maximize the speed.
  44  * Yes, it is ugly.
  45  */
  46
  47 #define PUTB(j,i)  p[j] = (byte)((u >> (8*(i))));
  48 #define PUTB4(b)   PUTB(0,b-1) PUTB(1,b-2) PUTB(2,b-3) PUTB(3,b-4)
  49
  50 /* for internal use only, need the length > 4 */
  51 uns varint_put_big(byte *p, u64 u);
  52 const byte *varint_get_big(const byte *p, u64 *r);
  53
  54 /**
  55  * Encode u64 value u into byte sequence p.
  56  * Returns the number of bytes used (at least 1 and at most 9).
  57  **/
  58 static inline uns varint_put(byte *p, u64 u)
  59 {
  60         if (u < VARINT_SHIFT_L1) {
  61                 p[0] = (byte)u;
  62                 return 1;
  63         }
  64         if (u < VARINT_SHIFT_L2) {
  65                 u -= VARINT_SHIFT_L1;
  66                 PUTB(0,1)
  67                 p[0] |= 0x80;
  68                 PUTB(1,0)
  69                 return 2;
  70         }
  71         if (u < VARINT_SHIFT_L3) {
  72                 u -= VARINT_SHIFT_L2;
  73                 PUTB(0,2)
  74                 p[0] |= 0xc0;
  75                 PUTB(1,1) PUTB(2,0)
  76                 return 3;
  77         }
  78         if (u < VARINT_SHIFT_L4) {
  79                 u -= VARINT_SHIFT_L3;
  80                 PUTB4(4)
  81                 p[0] |= 0xe0;
  82                 return 4;
  83         }
  84         return varint_put_big(p, u);
  85 }
  86 #undef GETB
  87 #undef GETB4
  88
  89 /**
  90  * Decode u64 value from a byte sequence p into res.
  91  * The invalid combination is not detected.
  92  * Returns pointer to the next position after the sequence.
  93  **/
  94 static inline const byte *varint_get(const byte *p, u64 *res)
  95 {
  96         byte h = ~*p;
  97
  98         if (h & 0x80) {
  99                 *res = p[0];
 100                 return p+1;
 101         }
 102         if (h & 0x40) {
 103                 *res = (p[0] & 0x3f)<<8 | p[1];
 104                 *res += VARINT_SHIFT_L1;
 105                 return p+2;
 106         }
 107         if (h & 0x20) {
 108                 *res = (p[0] & 0x1f)<<16 | p[1]<<8 | p[2];
 109                 *res += VARINT_SHIFT_L2;
 110                 return p+3;
 111         }
 112         if (h & 0x10) {
 113                 *res = (p[0] & 0xf)<<24 | p[1]<<16 | p[2]<<8 | p[3];
 114                 *res += VARINT_SHIFT_L3;
 115                 return p+4;
 116         }
 117         return varint_get_big(p, res);
 118 }
 119
 120 /**
 121  * Decode at most u32 value from a byte sequence p into u32 res.
 122  * The invalid combination is not detected.
 123  * Returns pointer to the next position after the sequence.
 124  * If the stored number cannot fit into u32, fill res by 0xffffffff and returns p.
 125  **/
 126 static inline const byte *varint_get32(const byte *p, u32 *res)
 127 {
 128         byte h = ~*p;
 129
 130         if (h & 0x80) {
 131                 *res = p[0];
 132                 return p+1;
 133         }
 134         if (h & 0x40) {
 135                 *res = (p[0] & 0x3f)<<8 | p[1];
 136                 *res += VARINT_SHIFT_L1;
 137                 return p+2;
 138         }
 139         if (h & 0x20) {
 140                 *res = (p[0] & 0x1f)<<16 | p[1]<<8 | p[2];
 141                 *res += VARINT_SHIFT_L2;
 142                 return p+3;
 143         }
 144         if (h & 0x10) {
 145                 *res = (p[0] & 0xf)<<24 | p[1]<<16 | p[2]<<8 | p[3];
 146                 *res += VARINT_SHIFT_L3;
 147                 return p+4;
 148         }
 149         u64 r = (u64)(p[0] & 7)<<32 | (u64)p[1]<<24 | (u64)p[2]<<16 | (u64)p[3]<<8 | (u64)p[4];
 150         r += VARINT_SHIFT_L4;
 151         if (r > 0xffffffff) {
 152                 *res = 0xffffffff;
 153                 return p;
 154         }
 155         *res = r;
 156         return p+5;
 157 }
 158
 159 /** Does the byte sequence p code the invalid sequence? **/
 160 static inline int varint_invalid(const byte *p)
 161 {
 162         return p[0] == 0xff && p[1] == 0xff;
 163 }
 164
 165 /**
 166  * Store the invalid sequence.
 167  * Returns always 2 (2 bytes were used, to be consistent with varint_put).
 168  **/
 169 static inline uns varint_put_invalid(byte *p)
 170 {
 171         p[0] = p[1] = 0xff;
 172         return 2;
 173 }
 174
 175 /** Compute the length of encoding in bytes from the first byte hdr of the encoding. **/
 176 static inline uns varint_len(const byte hdr)
 177 {
 178         byte b = ~hdr;
 179
 180         uns l = 0;
 181         if (!b)
 182                 l = -1;
 183         else {
 184                 if (b & 0xf0) { l += 4; b &= 0xf0; }
 185                 if (b & 0xcc) { l += 2; b &= 0xcc; }
 186                 if (b & 0xaa) l++;
 187         }
 188         return 8 - l;
 189 }
 190
 191 /** Compute the number of bytes needed to store the value u. **/
 192 static inline uns varint_space(u64 u)
 193 {
 194         if (u < VARINT_SHIFT_L1)
 195                 return 1;
 196         if (u < VARINT_SHIFT_L2)
 197                 return 2;
 198         if (u < VARINT_SHIFT_L3)
 199                 return 3;
 200         if (u < VARINT_SHIFT_L4)
 201                 return 4;
 202         if (u < VARINT_SHIFT_L5)
 203                 return 5;
 204         if (u < VARINT_SHIFT_L6)
 205                 return 6;
 206         if (u < VARINT_SHIFT_L7)
 207                 return 7;
 208         if (u < VARINT_SHIFT_L8)
 209                 return 8;
 210         return 9;
 211 }
 212
 213 #endif