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