2 * Copyright 2014 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #ifndef FOLLY_VARINT_H_
18 #define FOLLY_VARINT_H_
20 #include "folly/Range.h"
25 * Variable-length integer encoding, using a little-endian, base-128
28 * The MSb is set on all bytes except the last.
31 * https://developers.google.com/protocol-buffers/docs/encoding#varints
33 * If you want to encode multiple values, GroupVarint (in GroupVarint.h)
34 * is faster and likely smaller.
38 * Maximum length (in bytes) of the varint encoding of a 32-bit value.
40 constexpr size_t kMaxVarintLength32 = 5;
43 * Maximum length (in bytes) of the varint encoding of a 64-bit value.
45 constexpr size_t kMaxVarintLength64 = 10;
48 * Encode a value in the given buffer, returning the number of bytes used
50 * buf must have enough space to represent the value (at least
51 * kMaxVarintLength64 bytes to encode arbitrary 64-bit values)
53 size_t encodeVarint(uint64_t val, uint8_t* buf);
56 * Decode a value from a given buffer, advances data past the returned value.
58 uint64_t decodeVarint(ByteRange& data);
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.
65 * if x >= 0, encodeZigZag(x) == 2*x
66 * if x < 0, encodeZigZag(x) == -2*x + 1
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));
75 inline int64_t decodeZigZag(uint64_t val) {
76 return static_cast<int64_t>((val >> 1) ^ -(val & 1));
79 // Implementation below
81 inline size_t encodeVarint(uint64_t val, uint8_t* buf) {
84 *p++ = 0x80 | (val & 0x7f);
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;
97 if (LIKELY(end - begin >= kMaxVarintLength64)) { // fast path
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
114 while (p != end && *p < 0) {
115 val |= static_cast<uint64_t>(*p++ & 0x7f) << shift;
118 if (p == end) throw std::invalid_argument("Invalid varint value");
119 val |= static_cast<uint64_t>(*p++) << shift;
122 data.advance(p - begin);
128 #endif /* FOLLY_VARINT_H_ */