folly/Varint.h

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #ifndef FOLLY_VARINT_H_
  18 #define FOLLY_VARINT_H_
  19
  20 #include "folly/Range.h"
  21
  22 namespace folly {
  23
  24 /**
  25  * Variable-length integer encoding, using a little-endian, base-128
  26  * representation.
  27  *
  28  * The MSb is set on all bytes except the last.
  29  *
  30  * Details:
  31  * https://developers.google.com/protocol-buffers/docs/encoding#varints
  32  *
  33  * If you want to encode multiple values, GroupVarint (in GroupVarint.h)
  34  * is faster and likely smaller.
  35  */
  36
  37 /**
  38  * Maximum length (in bytes) of the varint encoding of a 32-bit value.
  39  */
  40 constexpr size_t kMaxVarintLength32 = 5;
  41
  42 /**
  43  * Maximum length (in bytes) of the varint encoding of a 64-bit value.
  44  */
  45 constexpr size_t kMaxVarintLength64 = 10;
  46
  47 /**
  48  * Encode a value in the given buffer, returning the number of bytes used
  49  * for encoding.
  50  * buf must have enough space to represent the value (at least
  51  * kMaxVarintLength64 bytes to encode arbitrary 64-bit values)
  52  */
  53 size_t encodeVarint(uint64_t val, uint8_t* buf);
  54
  55 /**
  56  * Decode a value from a given buffer, advances data past the returned value.
  57  */
  58 uint64_t decodeVarint(ByteRange& data);
  59
  60 /**
  61  * ZigZag encoding that maps signed integers with a small absolute value
  62  * to unsigned integers with a small (positive) values. Without this,
  63  * encoding negative values using Varint would use up 9 or 10 bytes.
  64  *
  65  * if x >= 0, encodeZigZag(x) == 2*x
  66  * if x <  0, encodeZigZag(x) == -2*x + 1
  67  */
  68
  69 inline uint64_t encodeZigZag(int64_t val) {
  70   // Bit-twiddling magic stolen from the Google protocol buffer document;
  71   // val >> 63 is an arithmetic shift because val is signed
  72   return static_cast<uint64_t>((val << 1) ^ (val >> 63));
  73 }
  74
  75 inline int64_t decodeZigZag(uint64_t val) {
  76   return static_cast<int64_t>((val >> 1) ^ -(val & 1));
  77 }
  78
  79 // Implementation below
  80
  81 inline size_t encodeVarint(uint64_t val, uint8_t* buf) {
  82   uint8_t* p = buf;
  83   while (val >= 128) {
  84     *p++ = 0x80 | (val & 0x7f);
  85     val >>= 7;
  86   }
  87   *p++ = val;
  88   return p - buf;
  89 }
  90
  91 inline uint64_t decodeVarint(ByteRange& data) {
  92   const int8_t* begin = reinterpret_cast<const int8_t*>(data.begin());
  93   const int8_t* end = reinterpret_cast<const int8_t*>(data.end());
  94   const int8_t* p = begin;
  95   uint64_t val = 0;
  96
  97   if (LIKELY(end - begin >= kMaxVarintLength64)) {  // fast path
  98     int64_t b;
  99     do {
 100       b = *p++; val  = (b & 0x7f)      ; if (b >= 0) break;
 101       b = *p++; val |= (b & 0x7f) <<  7; if (b >= 0) break;
 102       b = *p++; val |= (b & 0x7f) << 14; if (b >= 0) break;
 103       b = *p++; val |= (b & 0x7f) << 21; if (b >= 0) break;
 104       b = *p++; val |= (b & 0x7f) << 28; if (b >= 0) break;
 105       b = *p++; val |= (b & 0x7f) << 35; if (b >= 0) break;
 106       b = *p++; val |= (b & 0x7f) << 42; if (b >= 0) break;
 107       b = *p++; val |= (b & 0x7f) << 49; if (b >= 0) break;
 108       b = *p++; val |= (b & 0x7f) << 56; if (b >= 0) break;
 109       b = *p++; val |= (b & 0x7f) << 63; if (b >= 0) break;
 110       throw std::invalid_argument("Invalid varint value");  // too big
 111     } while (false);
 112   } else {
 113     int shift = 0;
 114     while (p != end && *p < 0) {
 115       val |= static_cast<uint64_t>(*p++ & 0x7f) << shift;
 116       shift += 7;
 117     }
 118     if (p == end) throw std::invalid_argument("Invalid varint value");
 119     val |= static_cast<uint64_t>(*p++) << shift;
 120   }
 121
 122   data.advance(p - begin);
 123   return val;
 124 }
 125
 126 }  // namespaces
 127
 128 #endif /* FOLLY_VARINT_H_ */
 129