silo/varint.h

   1 #ifndef _VARINT_H_
   2 #define _VARINT_H_
   3
   4 #include <stdint.h>
   5 #include "macros.h"
   6
   7 // read unsigned varint32 from buffer. assumes the buffer will have enough size
   8 inline const uint8_t *
   9 read_uvint32_slow(const uint8_t *buf, uint32_t *value)
  10 {
  11   const uint8_t *p;
  12   uint32_t b, result;
  13
  14   p = buf;
  15
  16   b = *p++; result  = (b & 0x7F)      ; if (likely(b < 0x80)) goto done;
  17   b = *p++; result |= (b & 0x7F) <<  7; if (likely(b < 0x80)) goto done;
  18   b = *p++; result |= (b & 0x7F) << 14; if (likely(b < 0x80)) goto done;
  19   b = *p++; result |= (b & 0x7F) << 21; if (likely(b < 0x80)) goto done;
  20   b = *p++; result |=  b         << 28; if (likely(b < 0x80)) goto done;
  21
  22   ALWAYS_ASSERT(false); // should not reach here (improper encoding)
  23
  24 done:
  25   *value = result;
  26   return p;
  27 }
  28
  29 /**
  30  * Read a uvint32 from buf into value, returning the
  31  * next position in buf after the value has been read.
  32  *
  33  * Assumes buf points to a well encoded varint
  34  */
  35 inline ALWAYS_INLINE const uint8_t *
  36 read_uvint32(const uint8_t *buf, uint32_t *value)
  37 {
  38   if (likely(*buf < 0x80)) {
  39     *value = *buf;
  40     return buf + 1;
  41   }
  42   return read_uvint32_slow(buf, value);
  43 }
  44
  45 inline const uint8_t *
  46 failsafe_read_uvint32_slow(
  47     const uint8_t *buf, size_t nbytes, uint32_t *value)
  48 {
  49   const uint8_t *p;
  50   uint32_t b, result;
  51
  52   p = buf;
  53
  54   if (unlikely(!nbytes--)) return nullptr;
  55   b = *p++; result  = (b & 0x7F)      ; if (likely(b < 0x80)) goto done;
  56   if (unlikely(!nbytes--)) return nullptr;
  57   b = *p++; result |= (b & 0x7F) <<  7; if (likely(b < 0x80)) goto done;
  58   if (unlikely(!nbytes--)) return nullptr;
  59   b = *p++; result |= (b & 0x7F) << 14; if (likely(b < 0x80)) goto done;
  60   if (unlikely(!nbytes--)) return nullptr;
  61   b = *p++; result |= (b & 0x7F) << 21; if (likely(b < 0x80)) goto done;
  62   if (unlikely(!nbytes--)) return nullptr;
  63   b = *p++; result |=  b         << 28; if (likely(b < 0x80)) goto done;
  64
  65 done:
  66   *value = result;
  67   return p;
  68 }
  69
  70 inline ALWAYS_INLINE const uint8_t *
  71 failsafe_read_uvint32(
  72     const uint8_t *stream, size_t nbytes, uint32_t *value)
  73 {
  74   if (unlikely(!nbytes))
  75     return nullptr;
  76   const uint8_t ch = *stream;
  77   if (likely(ch < 0x80)) {
  78     *value = ch;
  79     return stream + 1;
  80   }
  81   return failsafe_read_uvint32_slow(stream, nbytes, value);
  82 }
  83
  84 inline ALWAYS_INLINE size_t
  85 skip_uvint32(const uint8_t *stream, uint8_t *rawv)
  86 {
  87   if (rawv) {
  88     if (likely((rawv[0] = stream[0]) < 0x80)) return 1;
  89     if (likely((rawv[1] = stream[1]) < 0x80)) return 2;
  90     if (likely((rawv[2] = stream[2]) < 0x80)) return 3;
  91     if (likely((rawv[3] = stream[3]) < 0x80)) return 4;
  92     if (likely((rawv[4] = stream[4]) < 0x80)) return 5;
  93   } else {
  94     if (likely(stream[0] < 0x80)) return 1;
  95     if (likely(stream[1] < 0x80)) return 2;
  96     if (likely(stream[2] < 0x80)) return 3;
  97     if (likely(stream[3] < 0x80)) return 4;
  98     if (likely(stream[4] < 0x80)) return 5;
  99   }
 100   ALWAYS_ASSERT(false);
 101   return 0;
 102 }
 103
 104 inline ALWAYS_INLINE size_t
 105 failsafe_skip_uvint32(const uint8_t *stream, size_t nbytes, uint8_t *rawv)
 106 {
 107   if (rawv) {
 108     if (unlikely(!nbytes--)) return 0;
 109     if (likely((rawv[0] = stream[0]) < 0x80)) return 1;
 110     if (unlikely(!nbytes--)) return 0;
 111     if (likely((rawv[1] = stream[1]) < 0x80)) return 2;
 112     if (unlikely(!nbytes--)) return 0;
 113     if (likely((rawv[2] = stream[2]) < 0x80)) return 3;
 114     if (unlikely(!nbytes--)) return 0;
 115     if (likely((rawv[3] = stream[3]) < 0x80)) return 4;
 116     if (unlikely(!nbytes--)) return 0;
 117     if (likely((rawv[4] = stream[4]) < 0x80)) return 5;
 118   } else {
 119     if (unlikely(!nbytes--)) return 0;
 120     if (likely(stream[0] < 0x80)) return 1;
 121     if (unlikely(!nbytes--)) return 0;
 122     if (likely(stream[1] < 0x80)) return 2;
 123     if (unlikely(!nbytes--)) return 0;
 124     if (likely(stream[2] < 0x80)) return 3;
 125     if (unlikely(!nbytes--)) return 0;
 126     if (likely(stream[3] < 0x80)) return 4;
 127     if (unlikely(!nbytes--)) return 0;
 128     if (likely(stream[4] < 0x80)) return 5;
 129   }
 130   ALWAYS_ASSERT(false);
 131   return 0;
 132 }
 133
 134 /**
 135  * write uint32_t as unsigned varint32 to buffer. assumes the buffer will have
 136  * enough size. returns the position in buf after the value has been written
 137  */
 138 inline uint8_t *
 139 write_uvint32(uint8_t *buf, uint32_t value)
 140 {
 141   while (value > 0x7F) {
 142     *buf++ = (((uint8_t) value) & 0x7F) | 0x80;
 143     value >>= 7;
 144   }
 145   *buf++ = ((uint8_t) value) & 0x7F;
 146   return buf;
 147 }
 148
 149 inline size_t
 150 size_uvint32(uint32_t value)
 151 {
 152   if (likely(value <= 0x7F))                                               return 1;
 153   if (likely(value <= ((0x7F << 7) | 0x7F)))                               return 2;
 154   if (likely(value <= ((0x7F << 14) | (0x7F << 7) | 0x7F)))                return 3;
 155   if (likely(value <= ((0x7F << 21) | (0x7F << 14) | (0x7F << 7) | 0x7F))) return 4;
 156   return 5;
 157 }
 158
 159 class varint {
 160 public:
 161   static void Test();
 162 };
 163
 164 #endif /* _VARINT_H_ */